Schnorr signature support (with ROAST)

[jkitman]

Supporting Schnorr signatures will enable several interesting new features:

• Support federations with >20 peers (Taproot transactions)
• Much cheaper on-chain fees (Taproot transactions)
• BOLT12 support
• Statechains
• Federated LN nodes?

@nickfarrow has offered to implement ROAST to enable the federation to create Schnorr signatures. Some questions:

• ROAST should be compatible with our existing consensus model because we assume an asynchronous network and only a threshold of honest peers, but are there any assumptions we are overlooking?
• Should we try to run this over HBBFT?
• Do we need to modify our DKG algorithm?

[elsirion]

BOLT12 support

I think that's independent of TR but needs FROST/ROAST, right?

I also talked to @real-or-random about ROAST yesterday, key points:

• Without a central coordinator, meaning every signer acts as an independent coordinator, there's no guarantee that everyone gets the same signature, although everyone will get some valid signature. That's a potential footgun when dealing with consensus/committing to these signatures somehow.
• To avoid this problem we could run ROAST over an atomic broadcast protocol like HBBFT, but that's kinda wasteful since ROAST sends more messages than strictly necessary to reduce latency in an asynchronous environment. Inside an atomic broadcast protocol we kinda have a synchronous environment though afaik (epochs being discrete time steps and 2f+1 guarians are expected to contribute to each epoch).
• So maybe we can just use the "ban misbehaving guardians" approach. The fact that there are multiple rounds and the first seems to determine who participates in the second makes it a bit messier (different epochs have different sets of contributing guardians), maybe we can build an adaptation of ROAST for atomic broadcast.

Do we need to modify our DKG algorithm?

Afaik we could run the same DKG on secp256k1, but rust-secp might not support that, so we'd need to hack that maybe?

[real-or-random]

• To avoid this problem we could run ROAST over an atomic broadcast protocol like HBBFT, but that's kinda wasteful since ROAST sends more messages than strictly necessary to reduce latency in an asynchronous environment.

I think if you run it over HBBFT, it would't send many more messages than necessary. (And do more messages per epoch really make HBBFT much slower?)

And I don't think the HBBFT really creates a synchronous environment. If one of the nodes has a slow network connection for some epoch, its message won't be included in the result of the epoch. But that doesn't mean you can conclude it's malicious and should be banned. (Or can you make that conclusion in your setting?)

[jkitman]

I think running ROAST over HBBFT may actually be much simpler to implement and require less messages, since HBBFT can act as the semi-trusted coordinator, so we do not need f+1 peers to act as coordinators.

• Since the number of "responsive signers" in an HBBFT epoch is always >= t, every epoch instantiates a new signing session which all peers are aware of.
• Peers who do not contribute valid presignature shares and signature shares for all their signing sessions are banned.

[elsirion]

I think after Tim's talk at TABConf I now understand the concept sufficiently well. We can (and probably shoudl) essentially use ROAST inside HBBFT. It would proceed as follows (for a t-of-n scheme with $t=2f+1$):

• On signing request, every honest member proposes a ROAST nonce to consensus
• If the subset of $t$ contributions that were accepted contains $t$ nonces for session 1 ( $N_1$):
  • In the next consensus round the $t$ guardians that made it into consensus now contribute their signature shares for the first session $S_1$ and nonces for a second session $N_2$. The guardians that didn't make it into consensus previously contribute nonces for session 2.
  • There should be $t$ nonces and $\leq t$ signature shares in the round's output. The set of guardians who's nonces were part of consensus starts a new signing session and contributes $S_2$.
  • If a guardian's signature share didn't make it into a previous consensus round they try to resubmit it until it does (each time also attacking a nonce for the next session that could be started).
  • If a guardian doesn't contribute a signature share/nonce even though they made it into the consensus they are banned.
  • Repeat until any session has had $t$ signature shares agreed on in consensus. The signature is extracted and the protocol ends. In case there are multiple sessions that terminate at once the one with the lowest number is chosen to provide the signature.
• If any guardian didn't contribute:
  • They are banned from participating in consensus.
  • In this case no signing session can be started yet. Honest guardians who's nonces for session 1 didn't make it into consensus yet resubmit them. Other honest participants don't contribute anything till there is a set of nonces with $|N_1| \geq t$.

I think the argument for eventual termination of the protocol made in ROAST still applies here, we just use the consensus as our coordinator.

[m1sterc001guy]

POC implementation of ROAST in Fedimint here: https://github.com/m1sterc001guy/roastr