CryptoDB
Merkle Mountain Ranges are Optimal: On the Witness Update Frequency of Cryptographic Accumulators
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | We study append-only set commitments with efficient updates and inclusion proofs, or cryptographic \emph{accumulators}. In particular, we examine how often the inclusion proofs (or \emph{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 accumulator value ($O(\secpar\ \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. |
BibTeX
@inproceedings{crypto-2025-35679,
title={Merkle Mountain Ranges are Optimal: On the Witness Update Frequency of Cryptographic Accumulators},
publisher={Springer-Verlag},
author={Joseph Bonneau and Jessica Chen and Miranda Christ and Ioanna Karantaidou},
year=2025
}