Merkle Mountain Ranges are Optimal: On witness update frequency for cryptographic accumulators

Joseph Bonneau; Jessica Chen; Miranda Christ; Ioanna Karantaidou

Paper 2025/234

Merkle Mountain Ranges are Optimal: On witness update frequency for cryptographic accumulators

Joseph Bonneau

, New York University, a16z crypto

Jessica Chen

, New York University

Miranda Christ

, Columbia University

Ioanna Karantaidou

, New York University, George Mason University

Abstract

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 items, any construction with a succinct commitment ( storage) must induce at least total witness updates as items are sequentially added. In a certain regime, we strengthen this bound to 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 structures accumulators blockchain lower bounds Merkle 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}
}