Scalable, Secure DLT Protocol without Consensus

A new way of tackling Byzantine fault-tolerant systems

In their paper, the authors distinguish their protocol from previous Byzantine fault-tolerant (BFT) systems by noting that they have designed the algorithm in such a way as to replace quorums with stochastic samples:

“We generalize the Byzantine reliable broadcast abstraction to the probabilistic setting, allowing each of its properties to be violated with a fixed, arbitrarily small probability. We leverage these relaxed guarantees in a protocol where we replace quorums with stochastic samples. Compared to quorums, samples are significantly smaller in size, leading to a more scalable design. “

The paper goes on to outline a “Gossip-based algorithm” — a probabilistic broadcast to ensure the validity and totality of all messages broadcast in the system, in which the links are reciprocated and undirected.

This is distinct from and more efficient than existing Byzantine broadcast protocols, they argue, which build on quorum systems with “strong intersection guarantees,” resulting in “linear per-process communication and computation complexity.”

Extended Version of their Paper:

Scalable Byzantine Reliable Broadcast

(Extended Version)
Rachid Guerraoui1, Petr Kuznetsov2, Matteo Monti†1, Matej Pavlovic1, and Dragos-Adrian Seredinschi1

Télécom ParisTech, Université Paris-Saclay