Bilinear Accumulator

A bilinear accumulator is a cryptographic commitment scheme that uses a bilinear pairing—a special mathematical function that maps two points from cryptographic groups to a third—to create a succinct digest of a set. Unlike a Merkle tree, where proof size grows logarithmically with the set size, an accumulator's proof remains a single, constant-size group element. This makes it exceptionally efficient for proving that a specific element is a member of the committed set, a property known as membership witness. The core security relies on cryptographic assumptions like the q-Strong Diffie-Hellman (q-SDH) assumption, which makes it computationally infeasible to forge a valid proof for a non-member.

The power of bilinear accumulators extends beyond simple membership proofs. They can also generate non-membership witnesses, proving that a given element is not in the accumulated set, without revealing the entire set's contents. This is achieved by showing that the element, when combined with the accumulator's value, does not satisfy the pairing equation required for membership. Furthermore, bilinear accumulators support dynamic updates, meaning elements can be added to or deleted from the set, and all existing witnesses can be updated efficiently without recomputing the entire accumulator from scratch, a property not inherent to all accumulator types.

In blockchain and decentralized systems, bilinear accumulators enable advanced scalability and privacy features. They are a foundational component for stateless cryptocurrencies, where validators do not need to store the entire UTXO set but can verify transactions using small witnesses. They are also crucial for anonymous credentials and group signatures, where proving membership in a group without revealing one's identity is required. Compared to RSA accumulators, another common type, bilinear accumulators often offer more efficient non-membership proofs and can operate within the same elliptic curve groups used for many other blockchain cryptographic operations, promoting system homogeneity.

A bilinear accumulator is a cryptographic data structure that uses bilinear pairings on elliptic curve groups to create a succinct, constant-size representation (the accumulator) of a set of elements, enabling efficient membership and non-membership proofs. Unlike a Merkle tree, which produces logarithmic-size proofs, a bilinear accumulator generates proofs of constant size, regardless of the number of elements in the set. This is achieved by encoding set elements into the exponents of group elements and leveraging the algebraic properties of pairings.

The core mechanism involves two cyclic groups, G1 and G2, with a bilinear map e: G1 × G2 → GT. To accumulate a set S = {x1, x2, ..., xn}, a trusted setup generates a secret value s. The accumulator value A is computed as A = g^(∏ (s + x_i)) in G1, where g is a generator. A witness (or proof) for an element y is computed as w_y = g^(∏_{x_i ≠ y} (s + x_i)), effectively the accumulator of all other elements. Verification checks the pairing equation e(A, g) = e(w_y, g^(s+y)) to confirm that (s+y) divides the accumulator's polynomial, proving y is a member.

A key advantage is support for non-membership proofs. To prove an element z is not in the set, the prover must demonstrate that (s+z) does not divide the accumulator polynomial. This is done using the polynomial remainder, requiring the prover to find coefficients for the identity: ∏ (s + x_i) = q(s) * (s+z) + r, where r ≠ 0. The witness becomes the pair (w_z = g^q(s), r), and verification checks e(A, g) = e(w_z, g^(s+z)) * e(g, g)^r.

Practical implementation requires a trusted setup to generate and later discard the secret value s, as its compromise would allow forging proofs. While highly efficient for verification, updating the accumulator (adding or removing elements) can be computationally expensive, often requiring knowledge of s or recomputation from witnesses. This makes bilinear accumulators particularly suitable for applications with infrequent updates but frequent verification, such as certificate transparency logs or stateless cryptocurrencies.

Compared to other accumulators like RSA accumulators, bilinear accumulators natively support non-membership proofs without additional cryptographic constructs. They are a foundational component in advanced cryptographic protocols, including zero-knowledge sets and verifiable decentralized storage. Their constant proof size offers significant scalability benefits for blockchain systems where proof data must be included in transactions or block headers.

A bilinear accumulator is a cryptographic primitive that uses a bilinear map (or pairing) to create a constant-size, aggregate representation of a set. The core idea is to encode each element of a set as an exponent in a group, typically within an elliptic curve like BN254 or BLS12-381. The accumulator value is computed as g^{∏ (s + x_i)}, where g is a generator, s is a secret trapdoor, and x_i are the set elements. This single value can then be used to generate membership witnesses for any element in the set, which are verified using the properties of the bilinear pairing.

The power of this construction lies in its ability to provide both membership and non-membership proofs. For membership, a prover generates a witness demonstrating that an element's factor is part of the product in the exponent. For non-membership, they must prove that the element is not a factor, which is achieved using a co-factor witness derived from the polynomial representing the set. Crucially, the accumulator value and all proofs are of constant size, independent of the number of elements in the set, making it highly scalable.

The security of a bilinear accumulator rests on cryptographic assumptions related to the underlying pairing-friendly elliptic curves, such as the q-Strong Diffie-Hellman (q-SDH) assumption. This assumption posits that given g, g^s, g^{s^2}, ..., g^{s^q}, it is computationally infeasible to compute a pair (c, g^{1/(s+c)}) for any c of the attacker's choice. The accumulator's trapdoor s must remain secret, as knowledge of it would allow forging proofs for arbitrary elements, compromising the entire system's integrity.

In practice, bilinear accumulators enable powerful applications like stateless cryptocurrencies, where a node can verify transactions without storing the entire UTXO set, and authenticated dictionaries with constant-size proofs. They form a mathematical foundation for more complex vector commitments and zero-knowledge accumulators. Compared to Merkle trees, they offer smaller proof sizes but require more computationally intensive pairing operations and trusted setup for the initial trapdoor generation.