For those interested I've recently integrated the above refinements and tried to coherently package the whole idea together here: https://github.com/LLFourn/witness-asymmetric-channel
The main difference is that the protocol now uses what I am calling "revocable signatures" as the main primitive. This allows for O(1) storage complexity in both key aggregated and "multisig" constructions. LL On Thu, Sep 10, 2020 at 1:56 PM Lloyd Fournier <lloyd.fo...@gmail.com> wrote: > > >> >> >> Fortunately, I am wrong. At least in the case of non-aggregated 2-of-2 you >> can deterministically produce the encrypted signature by yourself for any >> commitment transaction as long as you use a deterministic nonce. >> But I think if using MuSig you would need to store each two party generated >> encrypted signature. >> Seeing as the likely way forward would be to use MuSig on an output which >> has a taproot which hides a discrete 2-of-2 this may not be a problem. > > > Upon further reflection I was missing something obvious when I came to this > conclusion. You can't produce the adaptor signature for a commitment > transaction deterministically without the encryption key (the other party's > publication point). > As long as we have to store the other party's per-commitment publication > point we still need O(n) storage where n is the number of commitment > transactions. Sorry for the confusion. > > Fortunately I had a bit of a breakthrough which allows us to eliminate > publication points altogether and enables O(1) storage when 2-of-2 > multi-signatures are instantiated with or without key aggregation (i.e. MuSig > or OP_CHECKMULTISIG). > > ### Eliminating Publication Points In favor of "revocable signatures" (for > OP_CHECKMULTISIG) > > I propose replacing the publication point with a static key that remains the > same with each commitment transaction. > The encryption key for each commitment transaction adaptor signature is (Ra + > A) for Alice and (Rb + B) for Bob. > Therefore, Alice broadcasting her commitment transaction would reveal the > discrete log of Ra + A (and Bob Rb + B). > Note that if Alice has not revealed her recvocation key (Ra) for this > commitment transaction she is not in trouble since her static key A is > blinded by Ra. If she has then Bob will learn her static secret key for A. > The intuition here is that the revocation key acts as a blinding factor for > the static key in the same way a nonce blinds your secret key in a schnorr > signature (more on that later). > If you haven't revealed your revocation key then you are free to use that > signature. If you have revealed the revocation key then you have in effect > "revoked" the signature. > > Now we need to make sure that if a party learns the secret key of the other > they can efficiently punish them so make the following changes to my original > proposal: > > Balance output for Alice is 2-of-2(A , Rb + B) > Balance output for Bob is 2-of-2(Ra + A, B) > > The implication of the above structure is that if you broadcast a commitment > transaction the other party can take their balance immediately. > If you broadcasted a revoked commitment transaction then they can take their > output and yours immediately. > > PTLC outputs and all subsequent transaction outputs then simplify to > 2-of-2(A,B) on every output. Yay! > Consider a PTLC paying to Alice. The PTLC-success output can be 2-of-2(A,B). > If Alice broadcasted it and it has been revoked then Bob knows A and B so he > can punish her. > The converse is true for the PTLC-timeout. > This elegant uniformity extends to other off-chain protocols hosted in these > channels e.g. DLCs > > Since A and B are static per channel and the secret keys for Ra and Rb can be > incrementally derived from subsequent values (as in the present lightning > spec) we have O(1) communication. > In practice each 2-of-2(A,B) should be randomized so they don't all look the > same. > > ### Revoking key aggregated schnorr signatures (for MuSig) > > Even with the above improvement there is still O(n) storage if using key > aggregation (MuSig) on the funding transaction output. > Key aggregation may be desirable here since you may want to not use a taproot > spend to broadcast a commitment transaction. > Since the two party adaptor signature scheme needs randomness from both > parties, you would have to store the other party's nonce and retrieve it to > deterministically produce the adaptor signature so you can extract Ra + A (if > Alice broadcasts) from the witness of the commitment transaction. > > Fortunately, there is a natural way to revoke a key aggregated signature you > helped produce without using adaptor signatures at all: just reveal the nonce > you used for it to the other party. > This prevents you from broadcasting it since the other party can now extract > your secret key from it! > Explicitly, two party signature generate two Schnorr signatures for the key A > + B in the form: > > sa = ra + rb' + H(Ra + Rb' || A + B || m)(a + b) > sb = ra' + rb + H(Ra' + Rb || A + B || m)(a + b) > > - (ra,rb) are the revocation secret keys, > - (ra', rb') are typical deterministically produced[1] nonces with Ra' = ra' > * G etc. > - (a,b) are the static secret keys > > Only Alice knows sa and only Bob knows sb but they are both signatures on the > same commitment transaction. > This is the witness asymmetry in the protocol. > > When revoking the commitment transaction associated with sa Alice reveals ra > to Bob and vice versa. If Alice uses sa after that, Bob can deterministically > produce rb' and ra (because each revocation key can be derived from the last) > and therefore can produce: > > ra + rb' + H(Ra + Rb' || A + B || m)b > > which when subtracted from sa and divided by H(Ra + Rb' || A + B || m) will > yield b (Bob's static secret key). > > The advantage of witness asymmetric channels using discrete keys over present > lightning seems to boil down to a simpler transaction structure (in favour of > using more complicated cryptography). > However, for key aggregation there is a measurable improvement in > communication complexity: It halves the amount of interactive signatures that > need to be computed per payment. > This is because each PTLC does not need to be duplicated across the > asymmetric state of both parties. > > Zeeman pointed out in [2] that the number of signing rounds (which this does > not improve) may be prohibitive anyway for payment applications at least so > it remains to be seen whether this efficiency can be utilised for payment > PTLCs in LN. > Thankfully, there are still advancements being made in Schnorr key aggregated > signing so the right answer to this might change over time.[3] > > [1] The caveats about not using deterministic nonces in MuSig can be avoided > here since we necessarily have state in LN. > [2] > https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-December/002375.html > [3] > https://medium.com/blockstream/musig-dn-schnorr-multisignatures-with-verifiably-deterministic-nonces-27424b5df9d6 > > Cheers, > > LL _______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev