Asynchronous Ratchet

[amiller]

Consider the Common Coin protocol. In this protocol, every message is of the form COIN(r, A, B), which indicates a threshold signature share for the rth sequential coin, sent from A to B.

Right now, a node accepts an incoming COIN message for any value r >= 0, even a round arbitrarily far in the future. Processing this message includes storing and verifying the signature share (an expensive pairing operation). This leads to a potential hard-to-attribute (in the sense of #11) resource exhaustion attack where an attacker node sends lots of spurious (but valid) signature shares.

Let's apply some ratcheting to messages sent along the asynchronous channels. Recipients recipients can discard some unsolicited messages received too early, before they're "ready". The main idea is that each sender keeps track of some partial view of the progress of each recipient (like a vector clock). The sender is then expected to queue up messages until the recipient is "ready."

For example, considering the Common Coin example above, we should have node A discard any received message COIN(r+1, B, A) until the message COIN(r, A, B) has been sent.

This approach effectively trades off some queuing at the recipient for queuing at the sender. This ticket is meant to start a discussion exploring when this approach is advantageous.

In the example above, the recipient's queuing could be unbounded (messages received from Byzantine nodes can be at any round), whereas (honest) senders' queues would be bounded in expectation (only constant expected number of common coin iterations in each run of binary agreement).

[sbellem]

Note: the link Right now, a node accepts an incoming COIN message (https://github.com/amiller/HoneyBadgerBFT/blob/dev/core/commoncoin.py#L43) is no longer valid.

Should be https://github.com/amiller/HoneyBadgerBFT/blob/dev/honeybadgerbft/core/commoncoin.py#L43, perhaps?