Failure Accountability

[amiller]

Right now the main guarantee we provide is to tolerate faults.... however, if a fault occurs, we'd like not just to tolerate it, but also to identify the node responsible for the fault. Let's call "fault accountability" the property that failures produce verifiable evidence incriminating the node(s) responsible for the fault.

In the asynchronous communication model, it's impossible to tell the difference between a "crash" and a long network delay. So we can't hope to provide "complete" fault accountability. However, clearly some kinds of failures, for example equivocation, have more promise. (This is related to "slashing" in the world of blockchain Proof-of-Stake protocols).

Right now, we provide only non-transferable authentication along channels (e.g., each message comes with a MAC applied in a TLS session), so very little accountability. On the other extreme, we could in principle require signatures transmitted along with each message, and could store the entire transcript of messages received for later review. This would add a lot of expensive extra overhead.

This ticket is intended to start a design discussion to explore a range of proposals in between these two extremes.

One benefit to gain from fault accountability is optimism. Consider the Common Coin protocol. Each instance of the protocol requires collecting threshold signature shares from each node. Any f+1 correct signature shares can be combined to form the complete signature. However, if any one among f+1 purported signature shares is incorrect, then combining will fail. Fortunately each signature share can be verified independently, so we can toss out the incorrect ones; however, share verification is expensive (pairing operation). We could optimistically cut costs, only verifying the individual shares if combining fails, however, this introduces a DoS vulnerability, where a Byzantine node inserts bogus signature shares to trigger this fallback computation. A solution based on fault accountability would be to have nodes provide ordinary (inexpensive, non-threshold) signatures on each signature shares. If optimistically combining fails, then we know that at least one is incorrect, and therefore we are guaranteed to obtain incriminating evidence by performing the expensive per-share check.

This example illustrates the main idea of fault accountability: instead of performing an expensive validation operation right away, first perform a quick check that guarantees the expensive operation will produce verifiable evidence of a faulty node.

To make the example above more efficient in the optimistic case, we could amortize the ordinary signatures, e.g. by signing a Merkle tree of commitments over a batch of signature share values. This discussion should go in a separate issue...