Nakamoto’s consensus protocol works in a permissionless model, where nodes can join and leave without notice. However, it guarantees agreement only probabilistically. Is this weaker guarantee a necessary concession to the severe demands of supporting a permissionless model?
We show that, at least in a benign failure model, it is not. We present Sandglass, the first permissionless consensus algorithm that guarantees deterministic agreement and termination with probability 1 under general omission failures. Like Nakamoto, Sandglass adopts a hybrid synchronous communication model, where, at all times, a majority of nodes (though their number is unknown) are correct and synchronously connected, and allows nodes to join and leave at any time.
Permissionless Blockchains with Deterministic Consistency?
The publication of Bitcoin’s white paper, besides jumpstarting an industry whose market is expected to reach over $67B by 2026, presented the distributed computing community with a fundamental question: how should the agreement protocol at the core of Nakamoto’s blockchain construction be understood in light of the combination of consensus and state machine replication that the community has studied for over 30 years? The similarities are striking: in both cases, the goal is to create an append-only distributed ledger that everyone agrees upon, which Nakamoto calls a blockchain. But so are the differences. Unlike traditional consensus algorithms, where the set of participants n is known and can only be changed by running an explicit reconfiguration protocol, Nakamoto’s consensus is permissionless: it does not enforce access control and allows the number and identity of participants to change without notice. To operate under these much weaker assumptions, Nakamoto adopts a new mechanism for reaching agreement: since the precise value of n is unknown, Nakamoto forsakes explicit majority voting and relies instead on a Proof of Work (PoW) lottery mechanism [19], designed to drive agreement towards the blockchain whose construction required the majority of the computational power of all participants. Finally, whereas traditional consensus protocols guarantee agreement deterministically, NC can do so only probabilistically; furthermore, that probability approaches 1 only as termination time approaches infinity.
Is settling for these weaker guarantees the inevitable price of running consensus in a permissionless setting?
Defying Betteridge, the answer is yes – we show that one can do much better.
In a technical report we publish today, we show that these weaker probabilistic guarantees do not arise from permissionlessness, but rather from the choice of a probabilistic PoW mechanism: In Bitcoin (and all PoW blockchains), the miners provide only statistical proof they have calculated a certain number of hash functions. The safety of these protocols relies on the majority of computational power generating the majority of blocks; however, with some probability, even a small miner might get lucky and generate the majority of blocks.
Sandglass
We show that if instead we can send all work, achieving a full (rather than statistical) PoW, it is possible to achieve deterministic safety in a permssionless model.
We present Sandglass, a permissionless consensus algorithm that guarantees deterministic agreement and terminates with probability 1. It operates in a model based on Nakamoto’s. Our model allows an arbitrary number of participants to join and leave the system at any time and stipulates that at no time the number of participants exceeds an upper bound N (though the actual number n of participants at any given time is unknown). Further, like Nakamoto’s, it is hybrid synchronous, in that, at all times, a majority of participants are correct and able to communicate synchronously with one another. We call these participants good; our protocol’s safety and liveness guarantees apply to them. Participants that are not good (whether because they crash, perform omission failures, and/or experience asynchronous network connections) we call defective.
Sandglass proceeds in virtual rounds. Nodes propose a value by broadcasting it; in the first round, each node proposes its initial value; in subsequent rounds, nodes propose a value chosen among those received in the previous round. Values come with an associated priority, initialized to 0. The priority of v depends on the number of consecutive rounds during which v was the only value received by the node proposing v – whenever a node receives a value other than v, it resets v’s priority back to 0. When proposing a value in a given round, node p selects the highest priority value received in the previous round; if multiple values have the same priority, then it selects randomly among them. A node can safely decide a value v after sufficiently many consecutive rounds in which the proposals it receives unanimously endorse v (i.e., when v’s priority is sufficiently high); and termination follows from the non-zero probability that the necessary sequence of unanimous, consecutive rounds will actually eventually occur.
The keen eye might notice that Sandglass is surprisingly reminiscent of Ben-Or’s classic consensus protocol. However, Ben-Or establishes that it is safe for a node to decide v after having observed two consecutive, unanimous endorsements of v. This is because any two majority sets of its fixed set of n nodes will intersect in at least one correct node. This approach is clearly no longer feasible in a permissionless setting, where n is unknown and the set of nodes can change at any time. Instead, Sandglass’s approach to establish safety is inspired by one of the key properties of Nakamoto’s PoW: whatever the value of n, whatever the identity of the nodes participating in the protocol at any time, the synchronously connected majority of good nodes will be faster in proceeding to new rounds than the defective nodes that do not communicate with good nodes. So much faster, that eventually defective nodes either propose the same value as the good nodes, or their round is so far behind that they cannot affect the good nodes.
Conclusion
The discovery that deterministic safety is possible in a permissionless setting leads to the question of whether there exists a protocol that also achieves deterministic termination in a hybrid synchronous model. Another natural question is whether there exists a deterministically-safe solution to consensus in a hybrid-synchronous model with Byzantine failures (Lewis-Pye and Roughgarden have shown that a deterministic-consesus protocol does not exist). Answering these questions might pave the way to a qualitative improvement of permissionless systems that would provide deterministic guarantees; or, at the very least, give us more insight about the nature of consensus.
Read more in our technical report.