search

axelarnetwork / tofn

A threshold cryptography library in Rust
Apache License 2.0
107 stars 22 forks source link

GG20 keygen round 2 bcast message size is not constant #171

Open ggutoski opened 2 years ago

ggutoski commented 2 years ago

The byte length of GG20 keygen round 2 bcast message is proportional to the threshold of the key being generated. That's bad---we want all message byte lengths to be constant.

https://github.com/axelarnetwork/tofn/blob/07dc66353ab175790a33d5903074ca4daae71104/src/gg20/keygen/r2.rs#L22-L25

vss::Commit is a commitment to a verifiable secret share. It's size is proportional to the threshold of the key being generated. In the past we broke up large bcast messages by splitting them into constant-size p2ps, but that works cleanly only when the message size scales with the number of shares. Because the size of this message grows with the threshold and not the number of shares, there is no clean way to implement the p2p solution. (It could be done, but it would be ugly.)

My rough estimate is that this message will become the largest keygen message at threshold ~100. Beyond that point this message will exceed the current maximum limit for message byte length for keygen. (This limit is selected to accommodate the largest keygen message as described in #169 .) If and when that happens we can simply raise the limit to accommodate the threshold we need. The raised limit might be significantly higher than all other keygen messages but it would still be an effective guard against a long-message attack.

Conclusion: it sucks but it's not a clear and present danger.

Question: should we pre-emptively raise the limit now to avoid the need to change it in the future? The limit is currently 9kB. A 100kB limit should suffice for threshold 1000.

milapsheth commented 2 years ago

To think out loud, the ugly solution would be something like, out of the the n peers in keygen, peers 0...t-1 will get one commit each as a p2p message, and the rest getting a default placeholder value, from each peer. Then, each peer will have to gather the commits of peer i by retrieving the p2p messages sent by peer i to peers 0...t-1.

Although, this has a bigger performance cost since we're now generating a lot more messages, so having a limit based on a threshold of 100 might be better for now.

milapsheth commented 2 years ago

To address this is at the protocol layer, we would have to generalize it to allow sending multiple bcasts per peer, the expected number of bcasts can signalled in the header along with the message type. Then, each peer would wait for those many number of bcasts from the same peer.