Utreexo

What Is Utreexo?

Utreexo is a dynamic hash-based accumulator designed specifically for the Bitcoin UTXO set. Proposed by Tadge Dryja at the MIT Digital Currency Initiative in 2019, it allows full nodes to validate every transaction without storing the entire set of unspent outputs. Instead of maintaining a multi-gigabyte database of every UTXO on the network, a Utreexo node stores only a small number of root hashes that cryptographically commit to the entire set.

The Bitcoin UTXO set grows over time as new outputs are created. As of early 2025, it contains roughly 170 million entries and occupies around 8 to 12 GB on disk (depending on database overhead). This creates a real barrier for users who want to run full nodes on devices with limited storage: phones, single-board computers, or embedded systems. Utreexo addresses this by compressing the entire state into a structure small enough to fit in a QR code.

Importantly, Utreexo is not a consensus change. It does not require a soft fork or hard fork. It operates at the peer-to-peer layer: Utreexo nodes validate the same rules as any other full node, they simply store state differently. Bridge nodes translate between the two formats, ensuring backwards compatibility with the existing network.

How It Works

Utreexo uses a forest of perfect binary Merkle trees to represent all unspent outputs. Each leaf in the forest corresponds to one UTXO. The key insight: any set of n elements can be decomposed into at most log2(n) perfect binary trees, one for each power of two in the binary representation of n.

The Merkle Forest

Consider 18 UTXOs. In binary, 18 is 10010, so the forest contains two trees: one with 16 leaves and one with 2 leaves. A Utreexo node stores only the root hash of each tree. With approximately 170 million UTXOs, this means at most 27 root hashes of 32 bytes each: roughly 864 bytes total.

When a new block arrives, the forest is updated by adding new UTXOs (leaves) and removing spent ones. Adding a leaf may cause small trees to merge into larger ones (similar to carry propagation in binary addition). Removing a leaf requires a proof showing that it exists in the forest.

Inclusion Proofs

This is the core tradeoff. In a traditional full node, checking whether a UTXO exists means looking it up in a local database. In a Utreexo node, the spender must provide a Merkle inclusion proof: the sibling hashes along the path from the leaf to the root.

For a forest of 170 million leaves, each proof is at most 27 hashes (27 × 32 bytes = 864 bytes per input). A typical transaction with one or two inputs adds roughly 1 to 2 KB of proof data. The Utreexo node verifies the proof against its stored roots using SHA-256 hashing, confirms the UTXO exists, and updates the accumulator.

# Utreexo accumulator state (conceptual)
# Instead of ~170 million UTXO entries (~8-12 GB):
roots = [
  "a3f2...c91d",  # Root of tree with 2^27 leaves
  null,            # No tree of size 2^26
  "7b04...e8a2",  # Root of tree with 2^25 leaves
  ...              # At most ~27 roots total
]
# Total state: < 1 KB

Node Types

Utreexo introduces two complementary node types:

• Compact State Nodes (CSNs): store only the accumulator roots (under 1 KB). They require every transaction to include a Utreexo proof. These are the lightweight nodes that benefit from the storage reduction.
• Bridge Nodes: store the full Merkle forest and generate proofs on behalf of CSNs. They act as a compatibility layer, translating between legacy transactions (no proofs) and Utreexo transactions (with proofs). Bridge nodes use roughly the same storage as a traditional full node plus additional proof data.

Utreexo vs. AssumeUTXO

AssumeUTXO is another approach to making Bitcoin nodes faster to bootstrap. Merged into Bitcoin Core starting with version 26.0, it works differently: a hardcoded hash of the UTXO set at a specific block height lets a node download a pre-built snapshot and begin validating new blocks immediately, while verifying older blocks in the background.

The two approaches are complementary rather than competing. A node could use AssumeUTXO for fast initial startup and Utreexo for ongoing state compression. For more on lightweight node architectures, see the deep dive on Bitcoin light clients and SPV.

Use Cases

Mobile Full Nodes

Running a fully validating Bitcoin node on a smartphone has historically been impractical due to storage constraints. Even pruned nodes require several gigabytes for the UTXO set. Utreexo reduces this requirement to under 1 KB of state, making mobile full validation feasible for the first time. The Floresta project, a Rust-based Utreexo client, has already demonstrated full validation on a $15 Raspberry Pi Zero 2W using roughly 800 MB of disk space and under 300 MB of RAM.

Faster Initial Block Download

Initial block download (IBD) is one of the biggest friction points for new node operators. Utreexo enables out-of-order block validation: because the accumulator state is so compact, multiple block ranges can be processed in parallel. This replaces slow random disk reads (looking up UTXOs in a database) with fast SHA-256 hash computations, which modern CPUs handle efficiently.

Embedded Wallet Validation

Wallet applications can embed a Utreexo node directly, eliminating reliance on third-party servers for transaction validation. Instead of trusting an Electrum server or SPV client, a wallet with an embedded Utreexo node validates every transaction against the full consensus rules while using minimal storage.

Global Accessibility

In regions where high-capacity storage is expensive or unreliable, Utreexo lowers the hardware barrier for running full nodes. This supports censorship resistance by making it easier for anyone, anywhere, to independently verify the Bitcoin blockchain without trusting third parties.

Implementation Status

Utreexo has moved from research paper to working software, though it remains in active development:

• utreexod: a Go-based full validating Bitcoin node (forked from btcd) with native Utreexo support. Released in beta in May 2024 by Calvin Kim, funded by the Human Rights Foundation.
• Floresta: a Rust-based lightweight Bitcoin client built by Davidson Souza and the Vinteum team. Designed to be embeddable as a library in wallet applications.
• BIPs 181, 182, and 183: three draft Bitcoin Improvement Proposals (submitted August 2025) formalizing the accumulator data structure, validation rules, and P2P networking changes. These are authored by Calvin Kim, Tadge Dryja, and Davidson Souza.

Neither implementation is considered production-ready for securing significant funds. The draft BIPs are still undergoing community review.

Risks and Considerations

Increased Transaction Size

The most significant tradeoff is bandwidth. Every transaction input must carry an inclusion proof of roughly 864 bytes. During initial block download, simulations show Utreexo adds approximately 20 to 25 percent more data to transfer (reducible to around 12 percent with proof caching). For nodes on metered or slow connections, this additional bandwidth may offset the storage savings.

Bridge Node Dependency

Compact State Nodes cannot generate proofs on their own: they rely on bridge nodes to attach proofs to transactions relayed from legacy nodes. If bridge node availability is limited, CSNs may struggle to receive properly formatted transactions. However, any full node can serve as a bridge node, and the incentive structure naturally encourages their operation.

Wallet Software Changes

For Utreexo to reach its full potential, wallet software must learn to store and provide inclusion proofs when constructing transactions. This requires changes to wallet architectures and transaction relay logic. Wallets that do not store proofs for their own UTXOs would need to request them from bridge nodes before spending.

Proof Freshness

Inclusion proofs are valid only for a specific accumulator state. When a new block is mined, the accumulator roots change, potentially invalidating previously generated proofs. Wallet software must update proofs or regenerate them against the current state before broadcasting transactions. This adds complexity compared to the traditional model where UTXOs are simply looked up in a local database.

Why It Matters

Bitcoin's security model depends on a large, globally distributed set of full nodes that independently verify every transaction. As the UTXO set grows, the hardware requirements for running a full node increase, which risks centralizing validation among fewer, better-resourced operators. Utreexo directly addresses this by making full validation accessible on hardware that most people already own.

Layer 2 protocols like the Lightning Network and Spark benefit from a healthier base layer. The more users who can independently verify on-chain transactions, the stronger the trust assumptions underlying off-chain protocols become. Utreexo complements these scaling solutions by ensuring the base layer remains decentralized even as usage grows.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.