TL;DR
This paper proves fundamental lower bounds on how often cryptographic accumulator witnesses must be updated as new elements are added. The authors show that for efficient accumulators, witness updates are unavoidable and, in many practical scenarios, are significantly more frequent than previously thought, demonstrating that constructions like Merkle Mountain Ranges are near-optimal.
What Problem Does This Paper Address?
Cryptographic accumulators are data structures that allow for efficient, succinct commitments to growing sets of data, enabling proofs of inclusion for individual elements. A key practical concern, especially in blockchain and certificate transparency systems, is how often the "witness" (the proof of inclusion) for an already added element needs to be updated when new elements are appended to the set. Many existing accumulator constructions, like Merkle trees or RSA accumulators, require updating almost all existing witnesses when a new element is added. While constructions like Merkle Mountain Ranges (MMRs) offer much better witness update efficiency (O(n log n) total updates for n elements), it was unclear if this was theoretically optimal or if a fundamental barrier existed. This paper aims to establish theoretical lower bounds on witness update frequency to understand this barrier and assess the optimality of constructions like MMRs.
Methods
The core of the paper's methodology relies on compression arguments, a common technique in proving lower bounds for data structures. The general idea is to set up a scenario where one party (Alice) wants to communicate a secret piece of information (a random subset of data) to another party (Bob) using the accumulator. If the accumulator is too efficient (e.g., has very few witness updates), Alice can communicate this information using fewer bits than theoretically required, leading to a contradiction.
The authors employ a two-step approach:
- Warm-up (One-shot Witness Updates): They first prove a weaker bound showing that a significant fraction of elements will have their witnesses change at least once as the set grows. This is achieved by Alice sending the accumulator and a list of elements whose witnesses changed. Bob attempts to reconstruct Alice's secret set by verifying witnesses. If a witness doesn't verify, Bob uses Alice's list to determine if the element was actually in the set or if its witness simply changed. If Alice can communicate the set using fewer bits than expected, it implies many witness changes.
- Boosting (Multi-shot Witness Changes): To show that witnesses change multiple times, they iteratively apply the compression argument. This involves constructing larger sets by concatenating smaller ones and showing that within these larger structures, not only do many witnesses change at least once, but a significant fraction of elements experience multiple witness updates over time. This is formalized through lemmas and theorems that progressively strengthen the lower bound.
Datasets
Not discussed in the paper. The proofs are theoretical and rely on abstract data universes and random subsets.
Key Insights and Ideas
- Witness updates are inherent to succinct accumulators: The paper demonstrates that for any accumulator with a succinct commitment size (polylogarithmic in the set size), a certain number of witness updates are unavoidable. This isn't just a limitation of specific constructions but a fundamental property.
- MMRs are near-optimal: The derived lower bounds closely match the performance of Merkle Mountain Ranges, suggesting that MMRs are an excellent practical choice for balancing accumulator size and witness update frequency.
- The "cost" of succinctness: The paper highlights a trade-off: achieving a small accumulator commitment size necessitates more frequent witness updates.
- Practical implications: The findings explain why systems using accumulators often need to manage frequent witness updates, impacting efficiency and complexity in applications like blockchains.
Key Results
- Lower Bound 1: Any succinct accumulator accumulating a set of size n requires at least $\Omega(n)$ total witness updates.
- Lower Bound 2 (Stronger): For accumulators that can handle superpolynomial-sized sets (like MMRs), the lower bound is $\Omega(n \log n / \log \log n)$ total witness updates.
- Optimality of MMRs: The paper shows that k-ary Merkle Mountain Ranges achieve an upper bound of $O(n \log_k n)$ witness updates, which is asymptotically tight with the $\Omega(n \log n / \log \log n)$ lower bound when $k$ is chosen appropriately (e.g., $k = \log^c n$).
Limitations and Future Work
- Random Oracle Model vs. Real-world: While the paper discusses MMR security in the Random Oracle Model, the lower bounds are proven for general succinct accumulators, implying their broad applicability.
- Specific Accumulator Types: The paper focuses on append-only accumulators and does not directly address dynamic accumulators (which support deletions) or universal accumulators (which support exclusion proofs). However, the authors suggest their bounds might extend to these more complex structures.
- Future Work: The paper opens avenues for exploring constructions that might achieve better trade-offs or for understanding witness update dynamics in more complex accumulator variants. The authors also note that their results do not say anything about the best-case number of witness updates, which is less interesting from a worst-case analysis perspective but could be relevant in specific scenarios.
Summary updated