jonasnick/nested-MuSig-FROST.md Secret

## nested-MuSig-FROST.md

      
    Raw
  

              nested-MuSig-FROST.md
            
          
    Requirements for a nested MuSig/FROST scheme

This document summarizes requirements for a nested MuSig or nested FROST scheme.
In a nested multi- or threshold-signature scheme the signers are organized in a tree instead of a multiset.
It is important to note that the ideas and concepts presented in this document are a collective effort, drawing from the knowledge and expertise of various individuals.
Possible applications


"multisig" Lightning where a node is split into multiple sub-signers.
For example, the signing policy of the node could be 2-of-2 or 2-of-3.
A "federation" consisting of multiple parties that jointly operate a Lightning node (e.g. Fedimint).
Here we'd have a t-of-n signing policy for potentially large t and n.
Also we have that t > 2/3*n because the federation would presumably run some asynchronous Byzantine failure tolerant consensus protocol.

Since all applications have trees of height 2, we use the term "multisig signers" to refer to the signers in the deepest level of the tree unless noted otherwise.
Assumption: we want to have liveness even if some of the multisig signers are offline or corrupted

Otherwise, it wouldn't be very attractive to run a multisig Lightning node as it decreases the availability compared to the singlesig case.
In the case of a n-of-n signing policy for a multisig Lightning node, this requirement implies that the signers do not only have backups but also reliable failover.
T-of-n policies will benefit from using ROAST for robustness.
Does the signing tree ever exceed height 2?

For all known applications, the signing tree has height two: there's a 2-of-2 on the top level and each of the two keys can be some t-of-n aggregate.
Would it useful if each of those keys is again an aggregate?
If not, the nesting scheme and security proof can be simplified.
Does Lightning need concurrent signing or is sequential signing enough?

Sequential signing is when there's always only one nonce "in-flight" for the signer, i.e., the signer does not broadcast a new nonce before having signed with an already broadcasted nonce. Sequential signing corresponds to the following sequence:
nonce <- NonceGen
Broadcast nonce
sig <- Sign(seckey, nonce, ...)
nonce <- NonceGen
Broadcast nonce
sig <- Sign(seckey, nonce, ...)
...

Concurrent signing is when there are multiple nonces in-flight, for example:
nonce1 <- NonceGen
Broadcast nonce
nonce2 <- NonceGen
Broadcast nonce2
sig1 <- Sign(seckey, nonce1, ...)
sig2 <- Sign(seckey, nonce2, ...)

Concurrent signing is also in effect when the signer signs for a differently tweaked seckey with multiple in-flight nonces (if the tweak is known to the attacker). For example, the following is not sequential signing:
nonce1 <- NonceGen
Broadcast nonce1
nonce2 <- NonceGen
Broadcast nonce2
sig1 <- Sign(seckey1, nonce1, ...)
sig2 <- Sign(seckey2, nonce2, ...)

if seckey1 = tweak(seckey, tweak1) and seckey2 = tweak(seckey, tweak2).
But it would be sequential signing if the seckey1 and seckey2 were each drawn independently uniformly at random.
If multisig Lightning only required sequential signing, the signing scheme and security proof would be significantly simpler.
Special Requirement in Lightning: Delayed Signing

Lightning has an additional important requirement:
After sending the signature nonce of the multisig to the channel counterparty and the counterparty replies with a partial signature, the multisig signers store the partial signature and may only complete it much later.
At that later point, the local signers must be able to complete the signature.
We can't generally guarantee this in FROST because one of the multisig signers who contributed to the nonce can just refuse to sign.
N-of-n MuSig with good backups/failover obviously does not suffer from this problem.
Delayed signing may not be a requirement in eltoo.
It is not possible that the signers immediately complete the partial signature from the counterparty and store it until needed.
The reason is that this signature is only needed in some circumstances and can lead to loss of funds when used in the wrong circumstances.
In particular, a malicious multisig signer could use the completed signature to broadcast a revoked state.
On the other hand, the multisig signers' must always be able to complete the signature.
They cannot just "close the channel" if that fails.
One could argue that in this regard multisig-LN is more fragile than singlesig, for which it is already difficult enough to broadcast transactions in a timely manner.
There are, however, a couple of potential solutions to this problem:

It would be possible to use distributed key generation (DKG) for the nonce such that t-of-n can reconstruct the nonce.
This would then be similar to the classic Stinson & Strobl (7 round?) threshold signature protocol. At nonce generation time it requires that all signers are online and a secure broadcast channel (a.k.a reliable broadcast) between them.
Another possibility is to have the signers verifiably encrypt their nonces to each other. Assume a 2-of-3 where one signer is offline at nonce generation and signing time. The two online signers send an encrypted secret nonce to the other online signer, such that the ciphertext can be decrypted by the offline signer and can be verified to be the encryption of the sending signer's public partial nonce. The online signers ACK the channel counterparty's signature only when they've received the (valid) encrypted nonce. Once the offline signer comes online and one of the online signers goes down, the previously offline signer receives the ciphertext from the remaining functioning online signer and decrypts it. This allows them to produce a signature. The communcation complexity of this approach grows exponentially with larger t and n. There are a couple of possible options for verifiable encryption:

Classic cut-and-choose which is rather inefficient (maybe ~100ms per verifiable encryption for prover and verifier).
Batched cut-and-choose: 100 verifiable encryptions at the 128-bit security level it takes around 750ms for the prover and 250ms for the verifier
Juggling: This could require very roughly and unoptimized about 256*( El-Gamal-{encryption,decryption}, rangeproof{,-verify}, signature{,-verify}, scalar_mul) for the prover {verifier}. Benchmarks indicate 138ms for each verifiable encryption, which would be very slow.


It may be possible to ignore the delayed signing requirement by having the multisig signers sign immediately when receiving the partial signature from the counterparty but don't output the plain signature. Instead they encrypt the signature to the t-of-n while signing. To do this, the multisig signers would create an adaptor signature that can be combined with the counterparty's partial signature after adapting it with the discrete log t of some adaptor T. This adaptor would need to be created through some distributed key generation protocol that will allow t-of-n multisig signers to recover t. But then it appears as if there's no benefit of this technique over running a DKG for the nonce.
Another option for a t-of-n is to send all partial nonces from all n signers to the other side of the LN channel, who replies with one signature for each subset of t partial nonces, (requiring n choose t many signatures in total).
Then every subset of t signers has a signature it can complete at a later time.
This requires all signers to be online at nonce generation time. Besides the possible blowup of communication complexity for large n, the downside is that this protocol would "leak into the state machine": the other side of the channel must be aware of t and n.
If we accept that the protocol leaks into the Lightning state machine, then another option is to replace the t-of-n FROST with a n-of-n MuSig but additionally commit to a backup script path that allows spending with the t-of-n. But this is far from simple and "requires significantly extending the Lightning protocol".

The inconvenience of having all signers be present at nonce generation time can be mitigated by pregenerating nonces during key setup.
Moreover, since the signers are only going to produce one delayed signature per channel, it should be possible to use just use a single nonce for all delayed signatures in a channel.
This requires exceptional care to avoid reusing nonces.
There's a problem with above solutions (including Stinson-Strobl and verifiable encryption) in a 2-of-3 that's somewhat related to the potential BFT requirement.
If an honest signer A goes offline and comes online again, a malicious signer M who stayed online may refuse to relay the nonces which were committed to while A was offline (or verifiable encryptions thereof) to A.
Also, M could try to send verifiable encryptions of nonces that have already been used in signing.
Would the signer set in a t-of-n multisig Lightning node be known before sending nonce?

If the signers would know which size t subset of n signers would produce a signature before generating the nonce, then the nested signing scheme would (presumably) end up being slightly simpler (because otherwise the signers in the multisig need an extra local nonce coefficient b_extra for concurrent security).
In Lightning, the answer to this question according to the Delayed Signing requirement seems to be no and the same answer holds for Fedimint.
Does the Lightning application need Byzantine failure tolerant (BFT) consensus between the multisig signers?

To see why this might be necessary, consider the following scenario where the owner of the 2-of-3 Lightning multisig wants to open a channel. To do that, one of the multisig signers proposes a transaction to the other signers. If that proposer is malicious it could create two transactions with non-overlapping inputs, send transaction 1 to cosigner 1 and transaction 2 to cosigner 2 for signing. This results in two valid, non-conflicting transactions that can end up on chain even though the owner only requested a single channel opening. This couldn't happen if the signers would run a protocol that establishes consensus on the transactions to sign.
Note that in this particular example, the signers could use some sort of deterministic coin selection to make sure that the two transactions would conflict because they share inputs. However, it's possible to imagine scenarios in LN where using the blockchain to prevent Byzantine failures does not work. For example, the malicious signer may control a different node from which it tries to send a payment through the multisig node. Perhaps the malicious signer can trick one cosigner to route it through channel 1 and the other cosigner to route through channel 2, which would result in two outbound HTLCs for just single inbound HTLC. This would be prevented if the signers had consensus on their state. Maybe there are other very subtle issues that arise if they don't.
Another way to state the problem is to look at a 2-of-3 where honest signers go offline at unfortunate times.
Assume a scenario where we have honest signers A and B and malicious signer M.
If A is offline for a while and comes online at the same time as B goes offline, then M can lie to A about what the latest state is.
In this case, A could refuse to sign unless it can be synced to the latest state from two other signers.
If BFT consensus is necessary, then 2-of-3 doesn't work because it's impossible in an asynchronous setting. For f faulty signers need n=3*f+1 and t=f+1, so for f=1 we need 2-of-4 threshold signing. But it could simplify dealing with the previous requirements (e.g., BFT consensus somewhat simplifies the DKG)?
Note: 2-of-3 can be set up much simpler than other t-of-n policies

2-of-3 is a special case where we can use MuSig instead of FROST and thereby avoid distributed key generation (H/T @real-or-random).
This works by starting the key setup process with regular MuSig key aggregation between the three signers.
Assume that the signers are numbered 0, 1, 2.
Every signer i sends their signing key to signer i + 1 mod 3.
When signer i receives the signing key from i - 1 mod 3 it sends an ACK to i + 1 mod 3.
The signer is ready to sign once it receives the signing key and an ACK from i - 1 mod 3.
After this key setup, every subset of two signers can sign for the 3-of-3 multisig because the signing key of the missing signer is known to one signer in the subset.