0xPage ¶

This BIP describes the Utreexo accumulator. It specifies the operations of the accumulator, including how it is updated as elements are added and removed, and how to generate and verify inclusion proofs demonstrating that a given element is part of the set.

The Bitcoin network is composed of different types of nodes. Among them, full nodes validate blocks and transactions as they are received. To fulfill their role, these nodes must maintain a record of all coins that have been created but not yet spent, a collection known as the UTXO set.

This set is typically stored in a database that must be accessed frequently and unlike block data, cannot be discarded. As a result, the cost of running a full node is directly tied to the size of the UTXO set. Since it can grow indefinitely, bounded only by the rate of block production, it represents a long-term scalability concern.

Utreexo is a dynamic cryptographic accumulator that enables the UTXO set to be represented in just a few kilobytes, by requiring peers that support Utreexo to provide inclusion proofs for the UTXOs being spent. This allows for the construction of nodes that perform the same full validation as a standard full node, without the need to store the entire UTXO set.

This BIP defines how the Utreexo accumulator works, defining the data structure and algorithms used to maintain the accumulator, as well as how to generate and verify inclusion proofs for elements in the accumulator. It does not define how the accumulator is used in the Bitcoin protocol, but rather provides a foundation for BIP-182 and BIP-183, which define how to integrate Utreexo into Bitcoin transaction validation and P2P network protocol respectively.

An accumulator is a value constructed by recursively applying a combining function to a set of elements. In the context of Utreexo, that combining function is a cryptographic hash function applied to pairs of values, forming a cryptographic accumulator. This allows the UTXO set to be represented compactly, enabling efficient membership proofs without requiring storage of the entire set.

The Utreexo accumulator builds on the append-only Merkle forest design of Reyzin and Yakoubov ¹, where the accumulator value is a vector of tree roots and inclusion proofs consist of the sibling hashes along the path from a leaf to its root. Utreexo extends this design to support deletions, while preserving the O(log₂(N)) size of the accumulator state, where N is the total number of elements ever added, and introducing a deletion mechanism suited to Bitcoin’s requirements. Unlike additions, which leave existing proofs valid without update, deletions require holders of inclusion proofs to update them as the Merkle forest is restructured.