RSA Accumulator

An RSA accumulator is a cryptographic construction that uses an RSA modulus and a random generator to create a single, constant-sized commitment (the accumulator value) to a set of elements. The core operation is accumulation, where elements are added to the set by exponentiating the current accumulator value with the element's representative (typically a prime number). This results in a deterministic, one-way function due to the difficulty of the RSA problem and the need for the group's unknown order. The final accumulator value acts as a short cryptographic digest of the entire set.

The power of an RSA accumulator lies in its ability to generate succinct membership proofs (witnesses) and, with additional cryptographic machinery, non-membership proofs. A membership witness for an element is a value that, when raised to the power of the element and compared to the accumulator, proves the element is in the set. Because the accumulator's size is constant regardless of the number of elements, it is highly efficient for representing large sets in systems like stateless blockchains, where nodes must verify transactions without storing the entire state.

A critical requirement for security is that the group order (the totient of the RSA modulus) must remain secret and unknown to all users. This property prevents the forging of witnesses and is typically established by a trusted setup or through a class group construction, which provides a group of unknown order without a trusted party. This makes RSA accumulators a foundational tool for more advanced protocols, including verifiable registries, anonymous credentials, and zero-knowledge set operations, where proving set relationships with minimal data leakage is essential.

An RSA accumulator is a one-way, collision-resistant function that compresses a set of elements into a single, constant-size value called the accumulator. It is constructed using a trusted setup that generates a strong RSA modulus N = p * q, where p and q are large, secret primes, and a random generator g. To add an element x (typically a prime number representing a hashed data item) to the accumulator A, the accumulator is updated to A' = A^x mod N. This deterministic operation allows anyone to compute the new accumulator state given the old state and the element.

The core utility of an RSA accumulator lies in its ability to generate succinct membership witnesses. For any element x in the accumulated set, a prover can compute a witness w such that w^x ≡ A (mod N). This witness proves that x was indeed incorporated into the accumulator A without revealing any other elements in the set. Verification is a single modular exponentiation, making it extremely efficient. Crucially, it is computationally infeasible to forge a valid witness for an element not in the set under the strong RSA assumption.

A more advanced feature is support for non-membership proofs. Using the fact that accumulated elements are primes, a prover can demonstrate that an element y is not in the set by providing integers (d, a, b) such that d = gcd(y, φ) and a * y + b * φ = d, where φ is the product of all accumulated primes. This allows the accumulator to function as a universal set for both inclusion and exclusion, a property leveraged in privacy-preserving protocols and credential systems.

In blockchain and decentralized systems, RSA accumulators enable stateless validation. For example, in a stateless cryptocurrency, the entire set of unspent transaction outputs (UTXOs) can be accumulated into a single root hash. A spender includes a membership witness for their UTXO in the transaction, and a validator only needs the constant-size accumulator to verify its validity, eliminating the need to store the entire UTXO set. This dramatically reduces the storage burden on consensus nodes.

The primary drawback is the requirement for a trusted setup to generate the RSA modulus, as knowledge of the primes p and q (the trapdoor) allows the creation of fraudulent witnesses. Recent constructions like class groups of imaginary quadratic fields offer similar accumulator functionality without a trusted setup. Despite this, RSA accumulators remain a foundational tool in cryptographic protocol design for their simplicity, efficiency, and powerful ability to provide compact proofs for set membership.

An RSA accumulator is a cryptographic construction that uses a trapdoor function based on the hardness of the RSA problem to create a succinct, constant-size representation (the accumulator value) of a large set of elements. It allows a prover to generate a short, computationally verifiable witness for any element, proving it is a member of the set. Crucially, without the trapdoor secret, it is computationally infeasible to forge a valid witness for a non-member, a property known as collision resistance. This makes it a foundational tool for privacy-preserving protocols and stateless blockchains.

The core mechanism relies on an RSA modulus N = p*q, where p and q are large secret primes. To accumulate a set of prime numbers {e1, e2, ..., ek}, the accumulator value A is computed as A = g^(e1 * e2 * ... * ek) mod N, where g is a public base. A witness for element e_i is a value w such that w^(e_i) ≡ A mod N, proving that e_i divides the product in the exponent. The security of the scheme depends on the Strong RSA Assumption, which posits that given N and a random z, it is hard to find any pair (x, e > 1) such that x^e ≡ z mod N.

A key advantage of RSA accumulators over Merkle trees is their constant size for both the accumulator and the witness, independent of the number of elements in the set. This property is critical for stateless blockchain designs, where validators do not need to store the entire UTXO set but can instead verify transactions against a single accumulator state. Furthermore, they support efficient non-membership proofs using techniques involving co-primality and Bezout coefficients, allowing a prover to demonstrate that an element is not in the accumulated set.

In practice, the requirement for the accumulated elements to be distinct primes necessitates a prime mapping function, like a hash-to-prime algorithm, to convert arbitrary data into suitable inputs. While highly efficient for verification, updating the accumulator (adding or deleting elements) typically requires the trapdoor (the factorization of N) or knowledge of all set elements, making dynamic updates a challenge. This has led to designs for universal accumulators and dynamic accumulators that delegate update capabilities using zero-knowledge proofs or a trusted setup.

RSA accumulators are utilized in several blockchain and cryptographic applications. They are a core component of protocols like Bulletproofs for range proofs and zk-SNARKs for circuit preprocessing. In cryptocurrencies, they enable compact client-side validation, as seen in concepts like UTXO commitments, where the entire set of unspent transaction outputs can be represented by a single value. Their ability to provide both membership and non-membership proofs in constant space makes them uniquely suited for systems requiring verifiable data with minimal on-chain footprint.