Paper 2026/2362

The Structure of Witness-Update Tradeoffs in Additive Positive Accumulators

Abstract

An additive positive accumulator maintains a short public digest of a growing set while each accumulated element carries a membership witness. As new elements are inserted, old witnesses may need to be refreshed, creating a tradeoff between succinct public state and witness-maintenance cost. Previous lower bounds capture this tradeoff through particular scalar measures, such as the maximum lifetime update frequency [Qi, IACR Communications in Cryptology 2026] or the total number of witness updates [Bonneau--Chen--Christ--Karantaidou, CRYPTO 2025]. We instead characterize the structure of the entire labeled witness-update pattern. Our main result reduces witness-update tradeoffs to optimization over bounded-right-depth ordered binary trees. Except with negligible probability, every execution of a sound, NeedUpd-complete accumulator admits such a tree whose prescribed updates can be matched injectively to genuine updates of the same witnesses occurring no earlier. Conversely, every feasible tree profile is realized exactly by a bounded-width online merger [Mahmoody--Qi, ITC 2023], and efficiently generated merger schedules admit Merkle-forest implementations. Thus the same family of trees governs both the security lower bound and the constructive side of the tradeoff. Because the tree certificate is independent of the maintenance objective, the same structural event simultaneously controls every nonnegative coordinatewise nondecreasing function of the lifetime update vector. This recovers the known maximum- and total-update bounds as special cases and yields heterogeneous weighted, cohort, threshold, top-$k$, and nonlinear bounds from the same theorem. Heterogeneous costs model settings in which different witness holders face different computational, communication, availability, or delegated-maintenance costs. For efficiently specified weights, an optimal tree can be computed in polynomial time and realized by the corresponding merger schedule. The framework also extends beyond lifetime update counts. For per-witness update prices that are nondecreasing in time, the same tree optimization remains exact and yields matching lower bounds and merger realizations, together with an efficient dynamic program. More generally, arbitrary nonnegative time-dependent prices admit structural lower bounds. Our results therefore give a structure-first framework in which cryptographic security first forces a common combinatorial constraint on the update process, and different maintenance objectives are optimized only afterwards.