Merkle Mountain Ranges are Optimal: On witness update frequency for cryptographic accumulators
发表信息
作者
- Joseph Bonneau
- Jessica Chen
- Miranda Christ
- Ioanna Karantaidou
笔记
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(λ polylog n) storage) must induce at least ω(n) total witness updates as n items are sequentially added. In a certain regime, we strengthen this bound to Ω(nlogn/loglogn) 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.
我们研究具有高效更新和包含证明的仅可追加集合承诺（append-only set commitments），即密码累加器（cryptographic accumulators）。具体而言，我们分析了当新元素被加入累加集合时，单个元素的包含证明（即见证值 witnesses）必须更改的频率。通过压缩论证法（compression argument），我们无条件证明：若要累加含 n 个元素的集合，任何具有简洁承诺（仅需 O(λ polylog n) 存储空间）的构造，在顺序添加 n 个元素的过程中，必然引发至少 ω(n) 次总见证值更新。在特定参数范围内，我们将此下界强化至 Ω(n log n / log log n) 次总见证值更新。这些下界不仅适用于最坏情况，且在随机选择累加集合时以压倒性概率成立。我们的结果表明，Merkle Mountain Range（一种实践中广受欢迎的优雅构造）的近似变体本质上是最优的。
关键词提炼（按重要性降序）：
- 见证值更新下界（核心结论）
- 密码累加器（研究对象）
- Merkle Mountain Range 最优性（实践意义）
- 压缩论证法（关键证明技术）
- 随机集合概率保证（理论强化特性）