Owner: @David Rusu
Reviewers: 🟢@Álvaro Castro-Castilla 🟢@Giacomo Pasini 🟢@Thomas Lavaur 🟢@Mehmet 🟢@Marcin Pawlowski 🟢@Daniel Sanchez Quiros 🟢@Youngjoon Lee
Cryptarchia is the consensus protocol of the Nomos Bedrock. This document specifies how the Bedrock comes to agreement to a single history of blocks.
The values that Cryptarchia optimizes for are resilience and privacy. These come at the cost of block times and finality. These values have significant implications on user experience and we should understand them well.
In consensus, we are presented with a choice of prioritizing either safety or liveness in the presence of catastrophic failure (this is a re-formalization of the CAP theorem). Choosing safety means that the chain never forks, instead the chain halts until the network recovers. On the other hand, choosing liveness (a la Bitcoin/Ethereum) means that block production continues but finality will stall, leading to confusion around which blocks are on the honest chain.
On the surface both options seem to provide similar guarantees. If finality is delayed indefinitely, is this not equivalent to a halted chain? The differences come down to how safety or liveness is implemented.
Chains that provide a safety guarantee do so using quorum-based consensus. This requires a known set of participants (i.e. a permissioned network) and extensive communication between them to reach agreement, which restricts the number of participants in the network. Furthermore, quorum based consensus can only tolerate up to 1/3rd of the participants becoming faulty.
A small participant set and low threshold for faults generally pushes these networks to put large barriers to entry, either through large staking requirements or politics.
Chains that prioritize liveness generally do so by relying on fork choice rules such as the longest chain rule from Nakamoto consensus. These protocols allow each participant to make a local choice about which fork to follow, and therefore do not require quorums and thus can be permissionless.
Additionally, due to a lack of quorums, these protocols can be quite message efficient. Thus, participation does not need to be artificially reduced to remain within bandwidth restrictions.
These protocols tolerate up to 1/2 of participants becoming faulty. The large fault tolerance threshold and the large number of participants provides for much higher resilience to corruption.
The motivation behind the design of Cryptarchia can be boiled down to this statement:
A block proposer should not feel the need to self-censor when proposing a block.
Working to give leaders confidence in this statement has had ripple effects throughout the protocol, including that: