Paper 2021/340
Merkle Trees Optimized for Stateless Clients in Bitcoin
Bolton Bailey and Suryanarayana Sankagiri
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Published elsewhere. Fifth Workshop on Trusted Smart Contracts, Financial Cryptography 2021
- Keywords
- Stateless CryptocurrencyMerkle TreesEmpirical AnalysisAverage-Case Complexity
- Contact author(s)
-
bolton bailey @ gmail com
suryasan94 @ gmail com - History
- 2021-03-17: received
- Short URL
- https://ia.cr/2021/340
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/340,
author = {Bolton Bailey and Suryanarayana Sankagiri},
title = {Merkle Trees Optimized for Stateless Clients in Bitcoin},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/340},
year = {2021},
url = {https://eprint.iacr.org/2021/340}
}
