Abstract
Blockchain systems rely on complex data structures to maintain state integrity and cryptographic security. This paper details the formal verification of Plebeia, a Merkle Patricia Tree (MPT) library used for state storage in the Tezos blockchain. By porting the library from OCaml to the F* programming language, we mathematically proved its structural invariants and functional correctness. The verification process successfully identified a critical bug in the tree's deletion logic that had evaded traditional unit testing. Our results demonstrate that formal verification can be applied to production-level storage libraries with negligible performance overhead, ensuring that the underlying cryptographic security is tied directly to established standards like BLAKE2b.
Introduction
In blockchain ecosystems like Ethereum and Tezos, Merkle Patricia Trees (MPTs) serve as the backbone for storing account balances and smart contract data. These structures must be space-efficient and cryptographically verifiable to allow nodes to prove the state of the network without downloading the entire history. However, the optimizations required for production-level performance—such as those found in the Plebeia library—introduce significant complexity.
A single flaw in the storage layer, such as an error in node deletion or hash calculation, could lead to catastrophic financial loss or network forks. While unit testing is a standard industry practice, it cannot guarantee correctness across all possible edge cases. This research addresses these risks by applying formal verification to the Plebeia library using F*.
Methodology
The F* Framework
The authors utilized F, a functional programming language designed for program verification. F leverages the Z3 SMT solver to automatically discharge mathematical proofs, allowing developers to define and verify complex properties of their code.
Verification Workflow
The verification process followed a structured, five-step approach:
- Gradual Porting: Core modules of the original OCaml implementation, including node types and hashing logic, were manually translated into F*.
- Defining Invariants: The team formalized "structural invariants" (SI). For example, they defined rules ensuring that an "extender" node cannot have another "extender" as a direct child, maintaining the tree's canonical form.
- Functional Correctness: The team proved that high-level operations—
get,insert, anddelete—behave identically to a mathematical key-value store. - Zipper Verification: Plebeia uses "zippers" (functional pointers) for efficient tree traversal. Verifying these is notoriously difficult but essential for ensuring that pointer-like movements within the tree remain memory-safe and logically sound.
- Extraction: Once verified, the F* code was extracted back into OCaml to be integrated with the broader Tezos ecosystem.
Key Insights and Results
Bug Discovery
The most significant outcome of the formalization process was the discovery of a bug in a previous version of Plebeia’s delete function. Despite passing a comprehensive suite of unit tests, the formal proof revealed that the function failed to preserve a specific structural invariant (SI4). This discovery highlights the limitations of testing-based quality assurance for complex data structures.
Cryptographic Security
The authors established "Relative Collision Resistance." Rather than attempting to prove the absolute security of the underlying BLAKE2b hash function, they proved a mathematical reduction: any collision found in a Plebeia Merkle hash can be transformed into a collision in BLAKE2b. This ensures the library's security is as robust as the cryptographic standards it employs.
Performance Evaluation
To ensure the verified code was production-ready, it was benchmarked against the original OCaml implementation. The performance gap was found to be minimal:
- Original OCaml: 261 seconds
- Verified F* (Extracted): 275 seconds
This ~5% overhead is a negligible trade-off for the mathematical certainty provided by the proof. The total verification effort required approximately 8,000 lines of F* code.
Limitations and Future Work
While successful, the project faces certain limitations. The verification is currently partial; some modules relying on unmodeled OCaml standard libraries remain unverified. Additionally, the authors currently assume "totality" for disk-accessing functions—assuming they will always terminate—which remains a challenge to prove for complex I/O operations.
Future efforts will focus on porting the remaining modules and exploring the use of Low (a subset of F) to generate high-performance C code, potentially closing the performance gap entirely while maintaining the same rigorous security guarantees.
Summary updated