[Lightning-dev] Payment point+scalar (was: Re: Proposal: AMPs With Proof of Payment)

ZmnSCPxj ZmnSCPxj at protonmail.com
Mon Oct 7 09:00:08 UTC 2019


Good morning list,

I was contacted off-list about the below statement:

> Since bip-schnorr probably will have 1 year of arguing, 1 year of testing+ developing, and 2 years of miners delaying activation before another UASF, I am currently tempted to consider implementing 2p-ECDSA already.

The person who contacted was concerned that encouraging 2p-ECDSA would divert attention from development of bip-schnorr, and in particular pointed out that developers should in fact try to implement Schnorr-like signatures and taproot in their software so as to further validate the design that will eventually be put into Bitcoin, hopefully faster.

Let me apologize for not considering this and I will now consider this possibility further in the future.

-----

In any case, I will now also pointlessly spam the list with a long post that needlessly analyzes the above single statement in detail.

> 1 year of arguing, 1 year of testing+ developing, and 2 years of miners delaying activation before another UASF

The above is my understanding of a high-level view of what occurred with SegWit v0 deployment.
This is a technique known as Reference Class Forecasting.

* https://en.wikipedia.org/wiki/Reference_class_forecasting
* https://conceptually.org/concepts/reference-class-forecasting
* https://simplicable.com/new/reference-class-forecasting

Put simply, "what happened before is likely to happen again", or "history repeats".

I observe the below facts:

* Humans have a well-known flaw known as "Planning Fallacy", wherein they *consistently* underestimate how long it takes to do anything.
  * https://en.wikipedia.org/wiki/Planning_fallacy
  * https://medium.com/the-mission/the-planning-fallacy-why-you-miss-your-deadlines-and-what-to-do-about-it-db5e162307b7
* Nearly all Bitcoin developers are either human, suspected of being human, or claim to be human.
* Aggregation of quantifiable information ("wisdom of crowds" technique) remains subject to pervasive systemic flaws, including the above "Planning Fallacy".

Against planning fallacy the most reliable weapon is the aforementioned Reference Class Forecasting.
This is simply taking a previous effort with known time-to-completion, then reusing its actual time to create estimates.

Now, it can be argued that:

* We already learned things from previous efforts, thus our current effort should be shorter.
* We cannot find any reason for bad things to happen during performance of the new task.

And therefore we should take less time for the new task than for the tasks in the existing reference class.

However, the above is a manifestation of the well-known "Optimism Bias" humans pervasively have, and which is implicated in the persistence of the "Planning Fallacy" among humans.

* https://en.wikipedia.org/wiki/Optimism_bias
* https://www.verywellmind.com/what-is-the-optimism-bias-2795031

Counterarguments include:

* We had to learn new things in the previous effort, what makes us think we will not be forced to learn new things in our new effort?
* We already found reasons for the bad things happening that delayed the previous task, what makes us think we will not encounter bad things that delay our new task?

Thus, it is far better to ignore **all** arguments for reducing the estimate (and thereby avoid Optimism Bias, and also reduce cognitive resource utilization as a bonus, which can be important when you are renting cognitive hardware, do not let sub-agents run wild and consume CPU needlessly people) and go with the original Reference Class Forecasting result.

For what it is worth I consider the "1 year of arguing" to already be drawing to a close by now, so potentially we might have Schnorr-like signatures on Bitcoin mainnet in 3 years or so.

Arguments for an earlier or later estimate of Schnorr-like signatures activated on mainnet must consider far more data and statistics, and the basic analysis above should still hold for much of it.


> I am currently tempted to consider implementing 2p-ECDSA already

Note the precision of this statement.
It does not say "I am planning to implement 2p-ECDSA".
It does not say "I am considering to implement 2p-ECDSA".

It simply says "I am tempted to consider to implement 2p-ECDSA".
Let us also be very precise: "to consider" means "to think about whether to do so or not", and is in no way a precommitment to actually implementing 2p-ECDSA, merely a precommitment to *consider* whether or not to do so.

Since I was already so tempted to ***consider*** this, let me now ***actually consider*** this at this point, and lay out the reasoning in detail.

The decision to not take 2p-ECDSA and instead focus on Schnorr-like signatures was considered in the Adelaide 2018 meetup.
The inputs to the decision were:

* The known complexity of implementing 2p-ECDSA.
* The known relative security drawbacks of 2p-ECDSA relative to Schnorr-like multisignatures.
* The known technique of payment decorrelation, which requires payment points, which requires either 2p-ECDSA or Schnorr-like signatures.
* The known technique of High AMP, which requires payment points, which requires either 2p-ECDSA or Schnorr-like signatures.

However, after the Adelaide 2018 meetup, the following new techniques were derived, all of which require payment points and scalars.

* Stuckless payments, which uses the blinding key to allow multiple parallel payments to be made for the same invoice while ensuring only one payment succeeds.
  * Escrow-over-Lightning, which shares the blinding key between the payer and the escrow service.
* Pay-for-signature, which uses the proof-of-payment to encode a component of an ECDSA or Schnorr-like signature.

The above new features serve as trigger to be tempted to consider whether to take the 2p-ECDSA "sidestep".

We should now also lay out the reasoning why 2p-ECDSA was rejected.

* 2p-ECDSA requires two cryptosystems, Paillier and SECP256K1.
  * The Paillier cryptosystem has fewer bits of security (80 bit, I believe) than SECP256K1.
    * Thus we expect that we *will* use Schnorr-like signatures on SECP256K1 even if we ever implement 2p-ECDSA.
  * We already have a widely-vetted library for SECP256K1, *including a branch that already implements the necessary primitives for using Schnorr-like signatures to implement payment point+scalar*, but not for Paillier.
    * Creating our own library for Paillier is dangerous as it effectively "rolls our own crypto", violating the sacred Zeroth Commandment of Cryptographers:

> Zeroth Commandment: Thou shalt not roll thy own crypto, until thou can beat Daniel Bernstein, Bruce Schneier, *and* Pieter Wuille in an epic rap battle.

(That is obviously a joke! / The intent is not to choke / the development of crypto just to keep them rappers woke! / The intent is instead / make you smile and shake your head! / So don't you go a-rapping / when you should be go a-crypting / YO~! Zeeman out!)

With regards to Schnorr-like signatures on Bitcoin, on the other hand, we can consider the below new fact that was also not available during Adelaide 2018:

* There now exists a proposal bip-schnorr to add Schnorr signatures to Bitcoin.

There is no similar new fact that improves on the use of 2p-ECDSA rather than Schnorr-like signatures.

Thus, the core of this consideration lies in the tension of the below facts:

* Given the many now-known benefits of payment points and scalars, we should consider getting them enabled on Lightning earlier if possible.
* 2p-ECDSA is theoretically implementable on Bitcoin as it exists today without waiting for SegWit v1.
* However, we will still switch to Schnorr-like signatures later anyway, due to improved security relative to 2p-ECDSA.

Again, when considering whether to take 2p-ECDSA or not, we should also remember the "planning fallacy", and consider that implementation and debugging of a decent library for Paillier would take at least as much time as implementation and debugging for a decent library for SECP256K1.

The first commit of bitcoin-core/secp256k1 is in March 2013.
The commit in bitcoin/bitcoin that makes libsecp256k1 from an optional requirement to a permanent one (I think) was merged in November 2015.
So I will take this time (1 year and 8 months, 1 + 2/3 years) as the time it would take to polish an existing Paillier library to sufficient level to be acceptable for Bitcoin mainnet (i.e. Reference Class Forecast).

Now let us consider the libsecp256k1 fork that includes Schnorr-like signatures, libsecp256k1-zkp.
The common commit between it and libsecp256k1 is from May 2019, but the first unique commit in libsecp256k1-zkp is in August 2019.
This makes it difficult to judge when the fork started, so let us take the center of May 2019 to August 2019 and call it as June 2019.
This means that the Schnorr-like part of libsecp256k1 has been in development for the past 5 months.
We can thus expect a "good enough for Bitcoin mainnet" in about 1 year and 3 months (subtracting 5 months from the previous forecast of 1 year and 8 months).

The question now is how long it takes to implement pointlocked timelocked contracts to replace the hashlocked timelocked contracts.
I now take as reference, AdamISZ/CoinSwapCS.
CoinSwap is "just" HTLC implementation, thus seems a good reference for implementing new pointlocked timelocked contracts that implement essentially the same swapping behavior.
CoinSwapCS started in April 2017 and last commit was in October 2017.
However, looking over the commits, it seems most of the code was stable as of June 2017, so I will take the region April 2017 to June 2017, 3 months, as the reference to implement a new atomic swap mechanism.

Thus, going the 2p-ECDSA route, looks like it will take 1 year and 11 months for a proof-of-concept reckless mainnet implementation.

Going the Schnorr-like route, looks like it will take 1 year and 6 months for a proof-of-concept testnet implementation with a stable libsecp256k1 interface for Schnorr-like signatures.
As we expect mainnet to activate SegWit v1 3 years from now, such an implementation cannot be deployed on mainnet until then.

------

In any case, let us consider further how points and scalars would deploy.

A common issue is that "channel closure == bad", because fees.
This means that we would have to implement pointlocked timelocked contracts on top of existing multiple-signature ECDA Poon-Dryja channels, with only a software update, and without closing and re-opening channels.

Fortunately, anything that the blockchain can enforce, any offchain updateable cryptocurrency system, including Poon-Dryja, can also enforce (by the threat of dropping onchain).
Thus, existing channels can enforce pointlocked timelocked contracts once they are supported onchain.

Obviously, we would want to eventually switch to Schnorr-like for channel funding transaction outputs.
This is because multiparticipant signatures can be implemented with a single MuSig signature, slightly reducing the costs of channel closure.

The other question is whether to take the new Decker-Russell-Osuntokun (which would make sense to bring directly to Schnorr-like) and leave Poon-Dryja using the existing ECDSA P2WSH, or to also upgrade Poon-Dryja mechanism to using Schnorr-like signatures.

Of note is that Poon-Dryja does not in fact need Taproot:

* Pointlocked timelocked contracts can be implemented using pre-signed transactions: one with a future `nLockTime` representing the timelock branch, the other with a current `nLockTime` with an adaptor signature that leaks the pre-negotiated secret.
  * This would require `NOINPUT` signatures for those transactions, though, as the PTLCs need to be re-instantiated on each update.
    * Even if the timelock branch is expressed in SCRIPT, the pointlock branch is not expressible in SCRIPT (*cough* "Scriptless" Script *cough*), so you need `NOINPUT` for that branch.
    * But note that we exchange signatures for all surviving HTLCs on each update anyway, so we could use non-`NOINPUT` keypath spend by simply re-exchanging signature for each PTLC.
      * Note the counter however, that MuSig signatures (and 2p-ECDSA signatures for that matter) need two communication rounds rather than one, requiring a more complex `commitment_signed` protocol.
  * Given that `NOINPUT` might require an opt-in hidden via the Taproot mechanism, we might still end up requiring Taproot anyway.

Regards,
ZmnSCPxj

(Out yo~!)


More information about the Lightning-dev mailing list