Paper 2026/1407

HACC: A Hierarchical Accumulator with Constant Public Parameters and Logarithm Time Complexity for Large Evolving Sets

Abstract

Dynamic universal accumulators compress an evolving set into a short digest with membership and non-membership witnesses for each element. Bilinear Pairing (BP) accumulators offer succinct witnesses and fast verification, but their public parameters size, witness generation and dynamic costs scale linearly with the set size in the trapdoorless setting. To address this bottleneck, we present HACC, a trapdoorless hierarchical accumulator that organizes capacity-bounded BP accumulators over ordered buckets into a $t$-ary tree. By fixing the node capacity $t$, HACC is a pairing-based accumulator whose public parameters can be independent of the set size $n$. Its ordered buckets yield native non-membership proofs and $\mathcal{O}(t\log_t n)$ witness generation cost, and non-cascading bucket split and merge mechanisms keep it fully dynamic at worst-case $\mathcal{O}(t\log_t n)$ dynamic cost with amortized $\mathcal{O}(1)$ witness updates. Its witnesses are of size $\mathcal{O}(\log_t n)$ and verify with as many pairings, which an optional path compression via polynomial multiproofs reduces to a constant for read-heavy epoch-based settings. We prove HACC correct and sound under the $t$-SDH assumption in the random oracle model. Experimentally, under comparable budgets, HACC accelerates element update and witness generation by $8.0\times$--$5087\times$ over a monolithic BP accumulator (Nguyen, CT-RSA'05, Damgård et al., eprint'08, and Srinivasan et al., CCS'22) while consuming $15.6\times$--$15933\times$ smaller public parameters.