We consider consensus protocols, for application to state machine replication, in the model of Castro-Liskov-Dolev-Lynch-Stockmeyer (partial synchrony, black box leader election, malicious corruptions). These protocols enable n players to output the same value, such that the output satisfies some publicly verifiable validity condition.
Efforts since “PBFT” (Castro-Liskov ’99), aim at reducing the communication complexity. A breakthrough was achieved by Hotstuff (Podc’19), implemented in Facebook’s Diem. It has complexity quasi linear in n the number of players, but at the price of extra latency.
We show how to overcome this limitation. First, with an explicit elementary construction in O(n log(n)), with a small constant overhead. Then, from the use of succinct noninteractive arguments of knowledge.
If time allows, we will explain the simplest: an argument of knowledge of k BLS signatures on the same message m, out of n public keys. This provides the first threshold signature with logarithmic size without trusted setup.