A Roadmap for Understanding Blockchain Consensus

This note summarizes several assumptions and modules that are useful when learning blockchain consensus. Consensus protocols differ not only in their algorithms. They also differ in their timing model, adversary model, cryptographic assumptions, data path, and complexity metric. A good way to read this area is to make these assumptions explicit before comparing protocols.

Network Assumptions

The first axis is the network model.

Partial synchrony. This is the path from PBFT to three-chain HotStuff and then to two-chain HotStuff variants such as Jolteon and Aptos. One central issue in this line is the commit-interruption problem. In pipelined HotStuff, a block is committed only after enough consecutive certified blocks are formed. If an intermediate view fails to produce a quorum certificate, the protocol may lose useful work and restart from a later view. Many later designs try to reduce this wasted work while preserving safety.

Asynchrony. Asynchronous consensus includes protocols based on Asynchronous Common Subset (ACS), Multi-Valued Byzantine Agreement (MVBA), Binary Byzantine Agreement (BBA), and DAG-based structures. HoneyBadger is a standard entry point for ACS. VABA and Dumbo-MVBA are useful entry points for MVBA-style protocols. These protocols need randomness to avoid the FLP impossibility result. Intuitively, the common coin gives honest nodes a shared source of uncertainty that the adversary cannot fully control. Understanding why this coin is needed is often more important than memorizing the protocol steps.

Synchrony. Synchronous consensus uses a stronger timing assumption. I do not discuss this line in detail here. Ling Ren’s work and the Decentralized Thoughts blog are good starting points.

Adversary Assumptions

The second axis is the corruption model. A protocol may be secure against a static adversary, a mildly adaptive adversary, or a strongly adaptive adversary.

Under static corruption, the adversary chooses the corrupted nodes before the protocol starts. The corrupted set then stays fixed.

Under mildly adaptive corruption, the adversary can change the corrupted set during the execution. However, it cannot corrupt an honest node after that node has already sent a target message and then erase or modify that message.

Under strongly adaptive corruption, the adversary can corrupt a node after the node has sent a message. This model is much harder, because the adversary can react to protocol progress. The paper Adaptively Secure Broadcast, Revisited is a useful reference for this line.

Cryptographic Assumptions

The third axis is the cryptographic interface. Signatures, threshold signatures, and hash functions are not only implementation tools. They change what can be certified, what can be aggregated, and what information a leader can carry into the next view.

This point is especially important for uncertified consensus. If a protocol removes or weakens certificates, it must replace the missing evidence with another safety argument. This is why signatures and certificates should be treated as part of the protocol model, not as implementation details.

Mempool

The mempool decouples data dissemination from the critical path of consensus. Without this decoupling, a consensus proposal may need to carry the full block data. This increases latency and makes the leader a bottleneck.

Modern protocols usually let consensus messages carry only block digests. Nodes fetch or reconstruct the full data through a separate data-availability layer. This design makes the consensus path lighter, but it introduces a new problem. A Byzantine leader may propose a digest for data that it has not actually made available. The protocol must therefore ensure data availability before the digest can safely enter consensus.

Narwhal is the standard reference point for this design space. Its pull-based structure is widely used. DispersedLedger is also useful to read because it presents the role of the mempool and data dissemination in a very explicit way.

Sleepy, Permissionless, and Classic BFT Models

Consensus assumptions can also be grouped by participation model.

In the sleepy model, the set of online nodes may change over time. The core requirement is that, at any time, enough honest nodes are awake relative to the adversarial nodes.

In the permissionless model, nodes can join and leave without a fixed membership list. The protocol cannot simply assume a known value of $n$ and a fixed committee of replicas.

In the classic BFT model, the protocol assumes a fixed set of $n$ replicas, with at most $t$ Byzantine replicas. Many consensus papers start from this model because it gives a clean setting for proving safety and liveness.

Complexity

Complexity is another basic tool for reading consensus papers. Two metrics are especially common: message complexity and bit complexity.

Message complexity counts the number of messages sent to decide one value or commit one block. It is the most direct theoretical metric. Bit complexity counts the total number of transmitted bits. This metric is closer to practical network cost, because large messages and certificates may dominate bandwidth even when the message count is small.

The Dolev-Reischuk lower bound shows that deterministic Byzantine agreement has a quadratic message lower bound in the standard setting. This result explains why many BFT protocols naturally pay $O(n^2)$ communication. PBFT has quadratic communication in the normal case, and its view-change path can become much heavier. HotStuff reduces the cost of view change by letting the new leader broadcast a compact certificate instead of collecting and redistributing a large amount of pairwise state.

Many public-chain protocols claim sub-quadratic or even sub-linear complexity. These claims should be read carefully. Some protocols rely on probabilistic sampling. Some do not provide deterministic finality in the same sense as classic BFT. Some move cost into committee selection, data availability, or recovery. The complexity claim is meaningful only after the model and the finality notion are clear.

Asynchronous protocols usually have higher complexity. This is not accidental. To make progress without timing assumptions, the protocol must tolerate many possible message schedules. Reliable broadcast, common coin, ACS, and MVBA components all add communication. The benefit is a stronger liveness model. The cost is higher protocol complexity and usually higher communication overhead.

This is why complexity analysis is useful when evaluating new ideas. If an idea has the same complexity as the state of the art, uses stronger assumptions, and does not improve practical performance, it is probably not a useful direction. If it changes one of these dimensions, then the contribution becomes easier to evaluate.