sBTC Research - DKG Signing Parallelization / Performance

[AshtonStephens]

This is a research discussion post meant to be edited with research notes surrounding making the DKG signing implemented in parallel.

The primary concerns are:

• What changes would need to be made to both the DKG singing process and the signer itself to allow for parallel signing
• How much time would it take to make those changes?
• What other ways can we improve signing time that might be simpler?

[AshtonStephens]

Currently under investigation by @xoloki

[xoloki]

• To allow parallel signing, we would need to wrap up the round specific SigningRound state and alter the state machines keep a map of states per round. This will make several parts of the state machine more complex.
• One week minimum to make these changes, possibly several weeks if it goes badly
• For each signing round, we actually need to hold multiple votes, since signers can vote either yes or no. We can do these at the same time, by altering the current NonceRequest/NonceResponse/SignatureShareRequest/SignatureShareResponse messages to contain a map of the possible votes, and allowing each Signer to choose which to vote for. This way we don't have to change the state machine, which is potentially much worse than increasing the complexity of the messages and associated business logic.

This raises some interesting questions though. When doing FIRE or ROAST, we don't wait to get responses from everyone, once we have a non-malicious threshold we ask that threshold to sign. So if we are gathering NonceResponse, we can keep a tally of how many yes/no responses we have received. Once we have a threshold of yes or no, we can go ahead and ask for signature shares for that answer. We could also ask for shares from the non-threshold, or just record who sent nonces. The NonceResponse could have an added field which contains a signature of which vote the Nonce applied to, which could be used in the bitmap from other discussions.

A further question is how to handle signers who indicate they are willing to sign both yes and no. I would argue that this should be considered a malicious response, and the signer should be treated as such.

We could also use this simpler algorithm to run multiple signing rounds, not just multiple possible votes. The map becomes nested, and each top-level key represents a different round. This assumes that we know we need to hold multiple votes at the same time, each of which has multiple options.

[xoloki]

After discussing with @jcnelson, we only care about getting a bitmap in the case where we can't reach threshold on either yes or no. So the following algorithm will suffice:

1. Coordinator sends out a nonce request, with the message to sign and a set of possible votes.
2. Signers send nonce responses which include a separately signed vote ( msg hash, (yes|no), dkg round, signing round, signing iteration).
3. If Coordinator gets a threshold that agrees to sign, signing proceeds normally. Otherwise, once the nonce timeout is reached, Coordinator records all the signed votes in the bitmap.