[Lightning-dev] Payment points without 2p-ECDSA or Schnorr

uSEkaCIO uSEkaCIO at protonmail.com
Mon Nov 11 08:12:46 UTC 2019


Hi list,

It is generally believed that in order to do "payment points" we need either the two party multisignature scheme 2p-ECDSA or 2p-Schnorr.

I think we can do it without them.

TL;DR Just use 2-of-2 OP_CHECKMULTISIG and do a single signer ECDSA adaptor signature on one of the keys.

Background
---------------
There are many nice features that could be enabled by using "payment points" instead of hashes as the core lock mechanism for lightning as discussed in the threads below. The consensus from these threads seems to be that it is best to wait for BIP-Schnorr/Taporoot to hit (which could be years away) than to try and implement and specify a 2p-ECDSA protocol (which I think is very wise).

March'17:  Andrew demonstrates scripltess lightning:  https://lists.launchpad.net/mimblewimble/msg00086.html
Apr'18:  Pedro shows you can do it for ECDSA: https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-April/001221.html 
Nov'18: Long discussion on the impact of scriptless scripts: https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-November/001489.html
Oct'19: ZmnSCPxj shares thoughts on the choice between 2p-ECDSA and waiting for Schnorr: https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-October/002211.html

The core idea I will present is that the 2pECDSA adaptor signature Pedro and Aniket introduced can be applied to single signer ECDSA and OP_CHECKMULTISIG can fill the gap.

Payment points today, without 2p-ECDSA, Hip hip Hoorayy!
--------------------------------------------------------

Here's how to create the core discrete log based lock required to do payment points without a proper multisignature scheme. Let's say Alice wants to give Bob 1 BTC if he can reveal y, the discrete log of Y to her.

1. Alice tells Bob about her public key A, her 1 BTC input and her refund address
2. Bob tells Alice about his public key B and his redeem address
3. They both can calculate the txid of the fund transaction which spends Alice's inputs to an OP_CHECKMULTISIG 2-of-2 with A B as the keys
4. Bob also sends to Alice a signature under B on a refund transaction spending the OP_CMS output to her refund address
5. Alice sends an adaptor signature under A with "auxiliary point" Y on the redeem transaction which spends the OP_CMS output to Bob's redeem address
6. Bob completes the adaptor signature under A with y and makes his own signature on the redeem tx under B and broadcasts it.
7. Alice sees the redeem tx and her completed signature and extracts y from it.

Note that Y or y never go on-chain, all anyone sees is a plain 2-of-2 OP_CMS.

Single Signer ECDSA adaptor signatures
--------------------------------------

For the completeness of this post I'll show my version of the single signer ECDSA adaptor algorithms (please verify). This is just a single signer protocol translated from Pedro and Aniket's original work. The only semi-exotic thing is the DLEQ proof. A description of the interactive protocol can be found in https://cs.nyu.edu/courses/spring07/G22.3220-001/lec3.pdf (and can be made non-interactive by Fiat-Shamir transform).

// Sign such that y = DLOG(Y) is needed to complete signature
AdaptorSign((x,X),Y,m):
1. Choose k randomly, R' = k*G
2. R = k*Y;
4. proof = DLEQ_prove((G,R'),(Y, R))
5. s' = k⁻¹(H(m) + x_coord(R)x)
6. return (R, R', s', proof)

// Verify Adaptor signature is correct for the given message and keys
AdaptorVerify(X, Y, m , (R, R', s', proof))
1. DLEQ_verify((G,R'),(Y, R))
2. return x_coord(R') == x_coord(s'⁻¹(H(m) * G + x_coord(R) * X))

// Complete the adaptor with the secret
AdaptorComplete(y, (R, R', s', proof))
s = s'y⁻¹
return (x_coord(R),s)

// Extract y from the completed adaptor
AdaptorExtract(s',s, Y)
y' = s⁻¹s'
return y' * G == -Y ? -y : y; // Deal with ECDSA malleability

Security
--------
I am doing a security analysis on this scheme in a paper that will be in review soon (which is why I am posting this anonymously). Unlike in 2pECDSA case, the DLEQ NIZK proof is the only proof required. However, there is one flaw in scheme that I should warn about: from the ECDSA adaptor signature you can calculate the Diffie-Hellman key between the signer's key X and the auxiliary point Y e.g x*Y = y*X (to see this start with s'*R and go from there). Therefore care should be taken when composing this with any scheme that relies on the Computational Diffie-Hellman assumption. In practice, I don't know of any proposal that would be affected by this. Keep in mind that X and Y are usually both transient keys and so learning a DDH keys doesn't help an attacker at all.

Discussion
----------

Using this scheme I think it's possible to do anything you can do with 2p-ECSA/Schnorr scriptless scripts except that instead of a normal p2pkh/public key output you have a 2-of-2 OP_CMS P2WSH output. Aside from this the scheme has some nice advantages:


1. The key exchange protocol is far simpler than 2pECDSA and simpler even than 2pSchnorr. This makes it a natural step up in complexity from the current HTLCs towards Schnorr (2pECDSA is like 5 steps up in complexity and then 3 down towards Schnorr).
2. Because of its simplicity it is much easier to specify -- A single BOLT spec could cover the key generation, transaction structure and signing without too much pain (actually trying to write and review the spec for 2pECDSA would take far longer)
3. The actual transaction structure can be moved towards the ideal Schnorr based endpoint (i.e. almost completely scriptless except for OP_CMS) or you could even keep the transaction structure the same as it is today and just replace the pre-image spending path in script with OP_CMS

I think this is practical but there are still a number of ways you could go about it so I'd be interested to hear your thoughts. Any feedback on this would be greatly appreciated :)

Cheers,

uSEkaCIO


More information about the Lightning-dev mailing list