cryptographic accumulator

A cryptographic accumulator compresses a whole SET of elements into one short value, while still letting you prove 'x is in the set' (membership) — or that it is not (non-membership) — with a tiny witness, without ever listing the set itself. Think of it as a hash of a set that supports succinct inclusion proofs.

There are two main families. Merkle trees are a hash-based accumulator: the root commits to the set and a membership proof is an O(log n) authentication branch. RSA accumulators give constant-size accumulator AND witnesses: A = g^(product of element primes) mod N; a member's witness is the accumulator without that member's factor, and verification is a single modular exponentiation — but they require a trusted setup because the modulus N's factorization is toxic waste. Bilinear-pairing accumulators are another constant-size option.

In blockchains, accumulators promise compact state. Stateless clients could carry a constant-size commitment to the UTXO set and prove a coin exists without storing the full set; RSA accumulators were explored for exactly this, and for revocation lists. Dynamic accumulators support adding and deleting elements, but the practical headache is that every existing witness must then be updated. Vector commitments and KZG (used in Verkle tries and danksharding) are close relatives offering constant-size proofs.