Paper 2021/340

Merkle Trees Optimized for Stateless Clients in Bitcoin

Bolton Bailey and Suryanarayana Sankagiri


The ever-growing size of the Bitcoin UTXO state is a factor preventing nodes with limited storage capacity from validating transactions. Cryptographic accumulators, such as Merkle trees, offer a viable solution to the problem. Full nodes create a Merkle tree from the UTXO set, while stateless nodes merely store the root of the Merkle tree. When provided with a proof, stateless nodes can verify that a transaction's inputs belong to the UTXO set. In this work, we present a systematic study of Merkle tree based accumulators, with a focus on factors that reduce the proof size. Based on the observation that UTXOs typically have a short lifetime, we propose that recent UTXOs be co-located in the tree. When proofs for different transactions are batched, such a design reduces the per-transaction proof size. We provide details of our implementation of this idea, describing certain optimizations that further reduce the proof size in practice. On Bitcoin data before August 2019, we show that our design achieves a 4.6x reduction in proof size vis-a-vis UTREEXO [Dryja 2019], which is a different Merkle-tree based system designed to support stateless nodes.

Available format(s)
Publication info
Published elsewhere. Fifth Workshop on Trusted Smart Contracts, Financial Cryptography 2021
Stateless CryptocurrencyMerkle TreesEmpirical AnalysisAverage-Case Complexity
Contact author(s)
bolton bailey @ gmail com
suryasan94 @ gmail com
2021-03-17: received
Short URL
Creative Commons Attribution


      author = {Bolton Bailey and Suryanarayana Sankagiri},
      title = {Merkle Trees Optimized for Stateless Clients in Bitcoin},
      howpublished = {Cryptology ePrint Archive, Paper 2021/340},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.