Utreexo
Utreexo is a hash-based accumulator for the Bitcoin UTXO set, proposed by Thaddeus Dryja. A node that uses Utreexo stores a small Merkle forest that commits to every unspent output, rather than the full UTXO set. Transactions carry inclusion proofs for the coins they spend. The design aims to shrink the disk and memory required for a fully validating full node, at the cost of extra proof data on the network and more hashing per block.
A conventional full node stores every unspent output in order to verify that new transactions spend existing coins and do not double-spend. The UTXO set has grown to many gigabytes, which is a barrier to archival-style validation on constrained hardware. Pruned nodes discard old blocks but still keep the full UTXO set. Accumulators can replace that set with a constant-size or logarithmic-size commitment if spends carry proofs of membership. Utreexo uses a forest of perfect Merkle trees (a "utreexo") that can be updated in a streaming fashion as UTXOs are created and spent. It does not require a trusted setup, unlike some RSA accumulators.
Each UTXO is a leaf hash. Leaves are grouped into a forest of perfect binary trees whose roots are the public accumulator state. Adding a UTXO inserts a leaf. Spending a UTXO deletes a leaf, which requires a Merkle proof to the relevant root. After each block the forest is rebalanced by merging trees of equal size. The number of roots is logarithmic in the number of UTXOs. A bridge node stores the full forest and can produce proofs for any spend. A compact node stores only the roots (and perhaps a cache of recently needed nodes). Compact nodes verify incoming proofs, update the roots, and discard the proofs. Validity of a block still requires checking scripts, amounts, inflation, and that every spent leaf was in the accumulator and is now deleted.
Proof size depends on forest shape and on how much of the proof can be cached from earlier blocks. Batching spends in a block allows sharing internal nodes. The extra bandwidth is paid by whoever provides proofs: bridge nodes, or peers in a Utreexo-aware P2P overlay. Utreexo does not change Bitcoin consensus. A Utreexo node is compatible with the existing chain if it verifies the same rules. It cannot be convinced of a UTXO that the honest accumulator does not contain. Deployment therefore needs a P2P dialect or a sidecar that carries proofs, and enough bridge nodes to serve them.
utreexod (based on btcd) and related libraries implement the accumulator, bridge nodes, and compact nodes. Bitcoin Core does not ship Utreexo. Research and testnet deployments have demonstrated initial block download with a small accumulator state. Wallet software is unaffected if it talks to a node that already verified the chain; the proofs are a node-to-node concern. Related lightweight verification approaches include SPV (headers and Merkle proofs of inclusion in a block, without proving UTXO membership in the global set).