Lloyd Fournier [ARCHIVE] on Nostr: 📅 Original date posted:2020-09-10 📝 Original message: > > > Fortunately, I am ...
📅 Original date posted:2020-09-10
📝 Original message:
>
>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20200910/db11d979/attachment.html>;
📝 Original message:
>
>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20200910/db11d979/attachment.html>;