Lloyd Fournier [ARCHIVE] on Nostr: 📅 Original date posted:2020-10-08 📝 Original message: For those interested I've ...
📅 Original date posted:2020-10-08
📝 Original message:
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.fourn at 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
📝 Original message:
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.fourn at 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