Skip to content
Crypto.world

Research

Systematization of Knowledge: Formal Verification of Consensus Protocols

Consensus bugs in blockchains cause irreversible financial loss and network failure, and formal verification is the strongest available defence, but the literature is scattered across incompatible…

Systematization of Knowledge: Formal Verification of Consensus Protocols
arXiv
2608.21935
Published
2026-08-22
Authors
Nikita Bondarev, Kirill Ziborov, Yury Yanovich

AI summary

Overview

Research area: Formal verification of blockchain consensus protocols, spanning distributed-systems theory, proof assistants, and model checking.

Technical level: Advanced. The paper is a survey, but its subject matter (inductive invariants, threshold automata, temporal logic, proof assistants such as Rocq, Isabelle/HOL, Agda, TLA+/TLAPS, Ivy, Dafny, and Lean) assumes familiarity with formal methods. The taxonomy and the summary tables are readable by a motivated non-specialist.

Scope in one sentence: A Systematization of Knowledge that classifies how more than 20 consensus protocols — from crash-fault-tolerant Raft to Byzantine-fault-tolerant HotStuff, DAG-based FairDAG, and the proof-of-stake Beacon Chain — have been formally verified, using a proposed maturity scale and a Protocol–Property–Method matrix.

What This Paper Is About

Consensus bugs in blockchains cause irreversible financial loss and network failure, and formal verification is the strongest available defence, but the literature is scattered across incompatible tools, protocol families, and property classes, so results do not accumulate. The authors organize this fragmented body of work into a single taxonomy, grading how deep each verification actually goes and which properties (safety, liveness, fairness, and protocol-specific guarantees) were really proved for which protocol. The goal is to tell researchers and practitioners what has been verified, what has not, and which tool fits which verification job.

Key Contributions

  1. A verification maturity scale running from informal reasoning up to machine-checked proofs over actual code, allowing different verification efforts to be compared on depth rather than only on which tool they used.

  2. A Protocol–Property–Method matrix mapping more than 20 consensus protocols to the safety, liveness, and fairness properties proved about them and to the tools and modelling approach used in each case (presented as Table 1).

  3. Identification of persistent gaps: liveness verification under asynchrony, handling of dynamic stake and validator churn, the disconnect between specifications and implementations, and scalability limits that confine many proofs to small networks.

  4. Practical guidance and a research roadmap: recommendations for tool selection and proof engineering grounded in protocol characteristics, plus directions toward what the authors call scalable, economically-aware verification.

Main Findings

  • Safety dominates the literature; liveness lags badly. Safety properties are more amenable to automated verification, and the authors state that liveness verification is substantially less common, because liveness depends on timeouts, message delivery, scheduler fairness, and sometimes randomization, making proofs sensitive to the execution model and much harder to mechanize. Many HotStuff-family works prove safety only.

  • Impossibility results shape what liveness proofs can claim. The authors invoke the classical Fisher-Lynch-Peterson result — deterministic consensus is impossible in a fully asynchronous network — to explain why liveness proofs assume partial synchrony or specific adversary models, such as the round-rigid adversary used for Red Belly Blockchain, or eventual synchrony in the Stellar Consensus Protocol.

  • Some "liveness" results are narrower than they sound. For Casper FFG's Gasper finality gadget, the verified property is plausible liveness: from any reachable state there exists a continuation in which checkpoints can be finalized again without violating slashing conditions, provided more than two thirds of stake follows the protocol. The authors characterize this as a recoverability property for the finality gadget rather than a full liveness theorem for the consensus stack.

  • Explicit-state model checking hits a hard combinatorial wall. In Tendermint Fastsync, TLC exposed a counterexample violating termination, but timed out after 24 hours on complex liveness checks. For TetraBFT, TLC failed to verify safety even for a minimal configuration of 4 nodes (1 Byzantine), 3 proposed values, and 5 views. Ceph safety was checked for up to 4 monitors and 2 proposed values, requiring 206 million states and roughly 11 minutes.

  • Symbolic and SMT-based checking buys scale but not full proofs. Bounded model checking with SMT solvers extended agreement verification to 8–11 processes where SPIN reached only 3 processes, and Tsuchiya et al. scaled to approximately 10 processes against 3–4 for explicit checkers. Apalache found Tendermint Fastsync errors in 10 minutes where TLC failed to terminate. ByMC's threshold-automata approach verified Red Belly safety and liveness for arbitrary N ≥ 3F+1.

  • Deductive verification gives the strongest guarantees at the highest cost. Woos et al. produced the first machine-checked proof of state machine safety for Raft in Rocq/Verdi, lifted to linearizability of client operations, but without a liveness proof. Velisarios verified PBFT in Rocq with explicit modelling of Byzantine behaviour. The authors note that deductive proofs scale poorly to liveness and are fragile under protocol evolution.

  • DAG-based protocols have benefited from reusable proof components. Bertrand et al. built TLA+ specifications with TLAPS proofs covering DAG-Rider, Cordial Miners, Hashgraph, Eventual Synchronous BullShark, and a variation of Aleph, organized around reusable DAG-construction and ordering components, which suggests proof libraries as a route to scaling.

  • Code-level verification is rare but exists. Cassez et al. verified a large, critical fragment of the Ethereum 2.0 Beacon Chain reference implementation in Dafny, proving absence of runtime errors plus functional-correctness specifications strong enough to uncover bugs and justify fixes — closer to software correctness than to consensus theorems.

  • Verification of blockchain-specific properties is emerging. Examples include Ordering Linearizability and γ-batch-order-fairness in FairDAG, blind order fairness in Fino (targeting MEV-style front-running), broadcast obligation and uniformity properties in Red Belly, delivery integrity for DAG-based consensus, a censorship vulnerability in Tendermint when enough validators refuse to vote, coalition attacks on Algorand that can bias the protocol toward empty blocks, non-triviality and strong non-triviality for CBC Casper, and external verifiability for Chained HotStuff/LibraBFT.

  • Dynamic stake is a specific blind spot. AleoBFT's blockchain non-forking property was proved while accounting for validators joining and leaving every block, using ACL2 — presented as an exception. The Agda formalization of Chained HotStuff/LibraBFT covers only a single epoch or configuration, with reconfiguration left to future work.

  • Hybrid frameworks are forming but are not yet complete. Veil, embedded in Lean, supports transition-system specification with bounded model checking through Lean tactics and SMT-discharged verification conditions, and was evaluated on Paxos and Stellar; as of March 2026, the authors state it does not yet natively support liveness verification.

  • The authors report no deductive-only work in their set whose primary verified contribution is fairness or censorship resistance, underscoring how narrow the verified property set still is.

Methodology in Plain English

This is a survey paper, not an experimental one. The authors read across the formal verification literature for consensus protocols and did three things with it.

First, they grouped the protocols into families: crash-fault-tolerant (Raft, Paxos variants, Ceph), Byzantine-fault-tolerant (Tendermint, HotStuff, PBFT, Red Belly, Streamlet, and others), proof-of-stake (Casper, Beacon Chain, Algorand), DAG-based (DAG-Rider, Hashgraph, Aleph, BullShark, AleoBFT, FairDAG), and others such as Stellar SCP.

Second, they classified the properties being proved into safety (nothing bad happens, including consistency, validity, no-forking, justification and finalization, and accountable safety), liveness (something good eventually happens, including termination, progress, eventual-progress liveness, and plausible liveness), and protocol-specific properties such as ordering fairness, broadcast correctness, attack resistance, non-triviality, and external verifiability.

Third, they classified the verification methods — interactive theorem proving, code-level deductive verification, explicit-state model checking, symbolic and SMT-based checking, timed automata, parameterized threshold-automata checking, and hybrid frameworks — and recorded the abstraction techniques each relies on: operational models that omit cryptographic details, property-oriented abstraction hierarchies, timeout abstraction, the Heard-Of communication model, threshold automata, and abstract communication specifications that deliberately drop properties irrelevant to the proof at hand.

These classifications are combined into the maturity scale and Table 1. Details such as a formal search protocol, the number of candidate papers screened, or inclusion and exclusion criteria are not reported in the provided content, and no quantitative meta-analysis of the surveyed studies is presented.

Why This Matters

Impact on research. The paper reframes consensus verification as a comparable design space rather than a set of isolated case studies. The maturity scale lets a reader judge whether a "verified" protocol has an informal argument, a bounded model check of a toy configuration, or a machine-checked proof over an implementation. The matrix exposes that the field has industrialized safety proofs while liveness, dynamic stake, and economic guarantees remain thin, which is a concrete agenda rather than a vague call for more work.

Real-world applications:

  • Ethereum 2.0 Beacon Chain clients: the arithmetic overflow incident cited by the authors and the Dafny verification of the reference implementation show where code-level proof effort pays off in production staking software.
  • BFT consensus stacks used by permissioned and Cosmos-style networks (Tendermint, HotStuff variants): the Tendermint Fastsync liveness violation and the verified termination counterexample demonstrate that model checking finds real defects before deployment.
  • DAG-based high-throughput protocols (DAG-Rider, BullShark, Hashgraph, AleoBFT): reusable TLAPS proof components and dynamic-stake proofs give these newer designs a starting point for verification rather than a blank slate.
  • Distributed storage and infrastructure built on Paxos variants (Ceph): the reproduced historical bug via TLC counterexample illustrates verification as regression testing for widely deployed systems software.

Industry relevance. Teams choosing a verification tool now have a comparison grounded in protocol structure: explicit checkers for early debugging and counterexamples, symbolic checkers for larger configurations, parameterized threshold automata for round-based quorum protocols, and proof assistants when parametric guarantees and code extraction matter. The authors' warnings about proof fragility under protocol evolution and about the specification–implementation disconnect are directly relevant to engineering budgets, since they imply that verification must be planned as a maintenance activity, not a one-off audit.

Future Directions

  • Making liveness verifiable at scale. The authors point to probabilistic liveness for randomized protocols such as HoneyBadgerBFT as unreachable for current SMT solvers, and to tree-structured protocols like HotStuff as resistant to inductive liveness invariants. A logic or tool that handles randomization and timing without exploding the state space is the central open problem.

  • Verifying dynamic stake and reconfiguration. With AleoBFT's ACL2 model as a rare exception and the Agda HotStuff formalization explicitly stopping at a single epoch, protocols where validators join and leave — and where committees, threshold certificates, and stake weights change — remain largely unverified.

  • Closing the specification–implementation gap. Code extraction from proof assistants and code-level efforts such as the Dafny Beacon Chain verification are early steps; extending this to full production clients is the stated route to real-world assurance. Hybrid frameworks like Veil, which still lacked native liveness support as of March 2026, are candidates for bridging modelling and proof.

  • Economically-aware verification. The authors' roadmap calls for verifying economic properties alongside safety and liveness, which the surveyed corpus largely does not do; the reward-distribution failure in federated learning consensus and MEV-oriented properties such as blind order fairness indicate the kinds of guarantees that would need formal treatment.

Target Audience

Researchers in formal methods and distributed systems who want a map of the field and a citable taxonomy; consensus protocol designers deciding what to prove and with which tool; blockchain client engineers and security auditors who need to judge verification claims made by a project; and graduate students entering the area who need the property classes, tool landscape, and known limits in one place. Practitioners without formal-methods background can read the taxonomy and the gap analysis, but the method-by-method discussion assumes familiarity with proof assistants and model checkers.

Authors’ abstract

Formal verification is increasingly critical for blockchain consensus protocols, where subtle bugs can cause irreversible financial loss and network failure. Yet the literature on verification methods is fragmented across tools, protocol families, and property classes, hindering cumulative progress. This Systematization of Knowledge paper analyzes over 20 verified consensus protocols--from crash-fault-tolerant Raft to Byzantine-fault-tolerant HotStuff, DAG-based FairDAG, and…

The full abstract on arXiv
Read the original paper