Paper 2019/611

Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set

Thaddeus Dryja


In the Bitcoin consensus network, all nodes come to agreement on the set of Unspent Transaction Outputs (The “UTXO” set). The size of this shared state is a scalability constraint for the network, as the size of the set expands as more users join the system, increasing resource requirements of all nodes. Decoupling the network’s state size from the storage requirements of individual machines would reduce hardware requirements of validating nodes. We introduce a hash based accumulator to locally represent the UTXO set, which is logarithmic in the size of the full set. Nodes attach and propagate inclusion proofs to the inputs of transactions, which along with the accumulator state, give all the information needed to validate a transaction. While the size of the inclusion proofs results in an increase in network traffic, these proofs can be discarded after verification, and aggregation methods can reduce their size to a manageable level of overhead. In our simulations of downloading Bitcoin’s blockchain up to early 2019 with 500MB of RAM allocated for caching, the proofs only add approximately 25% to the amount otherwise downloaded.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
accumulatorsbitcoinmerkle proofs
Contact author(s)
tdryja @ media mit edu
2019-06-05: last of 2 revisions
2019-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thaddeus Dryja},
      title = {Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set},
      howpublished = {Cryptology ePrint Archive, Paper 2019/611},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.