We introduce a new abstraction for expressing fault-tolerant consensus protocols in open, permissionless networks. It generalizes fail-prone systems and Byzantine quorum systems, asymmetric distributed trust, and gives a new characterization of the model used in the Stellar blockchain.

Quorum systems, Byzantine faults, and permissionsless consensus

Traditional consensus protocols for distributed systems use the so-called Byzantine-fault tolerance (BFT) model: A known set of N nodes participate in a protocol and the protocol tolerates up to F < N/3 of these nodes to exhibit Byzantine faults, such as trying to get an unfair advantage or attacking the protocol. Many protocols of this kind can be found in textbooks on distributed algorithms, and the recent HotStuff protocol also works in this model. Every node knows all others that participate. (Proof-of-Stake is similar, except nodes know how much total stake there is instead of the identity of the other participants.) In these algorithms and also in the corresponding practical systems, any set of more than (N+F)/2 participating nodes form a quorum.

In contrast, the model introduced by Bitcoin and used by the Nakamoto consensus protocol is open: anyone can participate without knowing of others, no contact with other nodes is needed, and more importantly, no assumptions about other nodes are involved. This model has been called permissionless.

Partial and subjective trust

Let us consider a middle ground between these two models: a world in which every node knows only a part of the nodes. Moreover, each node makes its own, subjective failure assumption about the others.

Several researchers have explored this world: Damgård, Desmedt, Fitzi, and Nielsen in 2007 or Sheff, van Renesse, and Myers in 2014, for example. Cachin and Tackmann in 2019 introduced the asymmetric-trust model to capture such assumptions in the form of asymmetric Byzantine quorum systems, which generalize the traditional notion of Byzantine quorums.

Several practical blockchain networks have also explored this world: Ripple developed and deployed an open consensus protocol based on selective knowledge of other nodes and subjective trust assumptions in 2012. In the corresponding XRP ledger protocol, every node declares a Unique Node List of nodes that it trusts. Stellar later followed suit with a different permissionless model based on subjective trust.

Even though all nodes are free to make their own failure assumptions in these models, a critical and unsolved problem exists: maintaining consistency requires compatible assumptions, such that the quorums have sufficient overlap. Prior common knowledge or prior synchronization seems necessary to achieve this, which is not desirable.

Permissionless quorum systems

In a recent paper, we formulate Quorum Systems for Permissionless Networks, a model that generalizes the theory of fail-prone systems for permissionless protocols. The work is co-authored by Luca Zanolini and Christian Cachin of the University of Bern and Giuliano Losa of the Stellar Development Foundation.

Our new model lets each node not only name groups of nodes that it knows and state whom among them might fail, but each node may also make assumptions about the assumptions of other nodes. By transitivity this means that nodes may not even know of any common nodes and nevertheless have intersecting quorums. This enables them, in principle, to run protocols for consensus, such as a blockchain network.

This model generalizes asymmetric quorum systems and also gives a new characterization with standard formalism of the model used by the Stellar blockchain.

For more information, see our preprint Quorum Systems in Permissionless Networks, which will be presented at the OPODIS 2022 conference and later appear in the proceedings.