“Maliciously secure consensus from succinct arguments, and short transparent threshold signatures”

Speaker : Matthieu Rambaud
Date: 07/07/2021
Time: 2:00 pm - 3:00 pm
Location: Zoom + LINCS


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.