Paper 2025/234
Merkle Mountain Ranges are Optimal: On witness update frequency for cryptographic accumulators
, New York University, a16z crypto, New York University, Columbia University, New York University, George Mason UniversityAbstract
We study append-only set commitments with efficient updates and inclusion proofs, or cryptographic accumulators. In particular, we examine how often the inclusion proofs (or witnesses) for individual items must change as new items are added to the accumulated set. Using a compression argument, we show unconditionally that to accumulate a set of $n$ items, any construction with a succinct commitment ($O(\lambda \text{ polylog} \ n)$ storage) must induce at least $\omega(n)$ total witness updates as $n$ items are sequentially added. In a certain regime, we strengthen this bound to $\Omega(n \log n/\log \log n)$ total witness updates. These lower bounds hold not just in the worst case, but with overwhelming probability over a random choice of the accumulated set. Our results show that a close variant of the Merkle Mountain range, an elegant construction that has become popular in practice, is essentially optimal.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- authenticated data structuresaccumulatorsblockchainlower boundsMerkle Mountain Range
- Contact author(s)
-
jcb @ cs nyu edu
jessicachen @ nyu edu
mchrist @ cs columbia edu
ikaranta @ gmu edu - History
- 2025-02-17: approved
- 2025-02-14: received
- See all versions
- Short URL
- https://ia.cr/2025/234
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/234,
author = {Joseph Bonneau and Jessica Chen and Miranda Christ and Ioanna Karantaidou},
title = {Merkle Mountain Ranges are Optimal: On witness update frequency for cryptographic accumulators},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/234},
year = {2025},
url = {https://eprint.iacr.org/2025/234}
}
