Paper 2026/1407

HACC: A Scalable Hierarchical Accumulator with Sublinear Cost for Large Dynamic Sets

Abstract

Dynamic universal accumulators provide succinct set commitments for evolving datasets, but balancing efficiency and scalability remains challenging. In particular, Bilinear Pairing (BP) accumulators offer constant size witnesses, but their public parameters size and dynamic operation costs grow linearly with the global capacity of the set. To address this bottleneck, we propose a trapdoorless hierarchical accumulator (HACC) that keeps BP-style efficient witness update and verification while avoiding this linear dependence. For a set of current size $n$ and a pre-defined parameter $t$ ($t \ll n$), HACC requires only $\mathcal{O}(t)$ public parameters, while supporting addition, deletion, and witness generation in $\mathcal{O}(t\log_t n)$ time, which is far more efficient than the $\mathcal{O}(n)$ costs of BP accumulators (Nguyen, CT-RSA'05, Damg\r{a}rd et al., eprint'08, and Srinivasan et al., CCS'22); moreover, HACC has $\mathcal{O}(\log_t n)$ sized witnesses with amortized $\mathcal{O}(1)$ witness updates. We further integrate polynomial multiproofs to reduce witness verification to constant pairing complexity in read-heavy epoch-based settings. We prove correctness and soundness of HACC under the $t$-SDH assumption in the random oracle model. Experimental results show that under comparable parameter budgets, HACC is $9.7\times$ -- $1803.4\times$ faster than BP accumulators for element update and witness generation, and consumes $34.6\times$ -- $3679.4\times$ smaller public parameters size.