Speaker : | Matthieu Rambaud |
Télécom-Paris | |
Date: | 07/07/2021 |
Time: | 2:00 pm - 3:00 pm |
Location: | Zoom + LINCS |
Abstract
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.