Verification of a Merkle Patricia Tree Library Using F

Sota Sato, Ryotaro Banno, Jun Furuse, Kohei Suenaga, Atsushi IgarashiarXiv 2021 · arXiv

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:

  1. Gradual Porting: Core modules of the original OCaml implementation, including node types and hashing logic, were manually translated into F*.
  2. 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.
  3. Functional Correctness: The team proved that high-level operations—get, insert, and delete—behave identically to a mathematical key-value store.
  4. 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.
  5. 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

Abstract

A Merkle tree is a data structure for representing a key-value store as a tree. Each node of a Merkle tree is equipped with a hash value computed from those of their descendants. A Merkle tree is often used for representing a state of a blockchain system since it can be used for efficiently auditing the state in a trustless manner. Due to the safety-critical nature of blockchains, ensuring the correctness of their implementation is paramount. We show our formally verified implementation of the core part of Plebeia using F*. Plebeia is a library to manipulate an extension of Merkle trees (called Plebeia trees). It is being implemented as a part of the storage system of the Tezos blockchain system. To this end, we gradually ported Plebeia to F*; the OCaml code extracted from the modules ported to F* is linked with the unverified part of Plebeia. By this gradual porting process, we can obtain a working code from our partially verified implementation of Plebeia; we confirmed that the binary passes all the unit tests of Plebeia. More specifically, we verified the following properties on the implementation of Plebeia: (1) Each tree-manipulating function preserves the invariants on the data structure of a Plebeia tree and satisfies the functional requirements as a nested key-value store; (2) Each function for serializing/deserializing a Plebeia tree to/from the low-level storage is implemented correctly; and (3) The hash function for a Plebeia tree is relatively collision-resistant with respect to the cryptographic safety of the blake2b hash function. During porting Plebeia to F*, we found a bug in an old version of Plebeia, which was overlooked by the tests bundled with the original implementation. To the best of our knowledge, this is the first work that verifies a production-level implementation of a Merkle-tree library by F*.
BibTeX
@misc{sato2021verification,
  author = {Sota Sato and Ryotaro Banno and Jun Furuse and Kohei Suenaga and Atsushi Igarashi},
  title = {{Verification of a Merkle Patricia Tree Library Using F}},
  year = {2021},
  eprint = {2106.04826},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.04826},
}
Figure