Bilinear accumulators are cryptographic primitives that allow multiple elements {ai}\{a_i\} from a set to be combined into a single, compact value called an accumulator. This accumulator enables efficient verification of whether an element is a member (or not a member) of the accumulated set without revealing the entire set or requiring large amounts of data.

They are defined using a polynomial constructed from the elements to be accumulated:

A(x)=∏i(xβˆ’ai).A(x) = \prod_{i}(x - a_i).

To commit to this set, we evaluate this polynomial at a point of unknown order Ο„\tau, resulting in an accumulator that is a group element:

A=gA(Ο„)=g∏i(Ο„βˆ’ai).A = g^{A(\tau)} = g^{\prod_{i} (\tau - a_i) }.

​
Points of Unknown Order

A point of unknown order is a group element gΟ„g^\tau where gg is the generator of the group, and Ο„\tau is an unknown scalar. We can make such a point and its powers gΟ„ig^{\tau^i} up to some maximum power tt public without revealing Ο„\tau using a trusted setup ceremony.

The use of a point of unknown order is crucial because it ensures that we can commit to various polynomials by evaluating them at a random point - but the random point is preset and we don’t have to find one from scratch each time. This is particularly important when we start a protocol and haven’t sent any messages with which to use to compute some deterministic random point.

​
Accumulator Computation

The accumulator is computed by evaluating the polynomial:

A(Ο„)=g∏i(Ο„βˆ’ai)=gβˆ‘iaiΟ„i=∏i(gΟ„i)aiA(\tau) = g^{ \prod_{i} (\tau - a_i)} = g^{\sum_i a_i \tau^i} = \prod_i \left(g^{\tau^i}\right)^{a_i}

This method requires explicit computation of A(x)A(x), which involves multiplying linear factors corresponding to each element in the set. Although this computation is linear in the size of the set, it is practical for sets of reasonable size.

​
Accumulators and Trade-offs

Different types of accumulators have varying trade-offs:

  • RSA-based Accumulators: Rely on the hardness of factoring large integers. They allow for dynamic updates and efficient proofs without needing to recompute the entire accumulator. However, they require large key sizes and complex key management due to the need for secure generation and storage of an RSA modulus with unknown factorisation.

  • Merkle Tree Accumulators: Use hash trees to accumulate elements. They provide efficient (logarithmic-size) membership proofs and are widely used in blockchain systems. Updates (adding or removing elements) have logarithmic time complexity, but the proofs are larger compared to bilinear accumulators.

  • Bilinear Accumulators (This Scheme): Offer constant-size accumulators and proofs for both membership and non-membership. However, updates require recomputing the accumulator polynomial from scratch, resulting in linear-time updates. They require the use of elliptic curves, bilinear pairings, and points of unknown order, but do not require any secret parameters.

​
Membership and Non-Membership Proofs

Bilinear accumulators enable efficient and compact proofs of both membership and non-membership.

​
Membership Proofs

To prove that an element aia_i is part of the accumulated set, a prover provides a witness polynomial W(x)W(x), which is the accumulator polynomial without the factor (xβˆ’ai)(x - a_i):

W(x)=A(x)(xβˆ’ai)=∏jβ‰ i(xβˆ’aj).W(x) = \frac{A(x)}{(x - a_i)} = \prod_{j \neq i} (x - a_j).

The prover computes the witness value:

W(Ο„)=g∏jβ‰ i(xβˆ’aj).W(\tau) = g^{\prod_{j \neq i} (x - a_j)}.

The verifier can check the membership of aia_i using bilinear pairings:

e(W(Ο„),g2Ο„βˆ’ai)=e(A(Ο„),g2),e(W(\tau), g_2^{\tau-a_i}) = e(A(\tau), g_2),

where ee is the bilinear pairing with properties:

  • Bilinearity: e(aP,Q)=e(P,aQ)=e(P,Q)ae(aP, Q) = e(P, aQ) = e(P, Q)^a
  • Non-degeneracy: e(P,Q)β‰ 1e(P, Q) \neq 1
  • Computability: e(P,Q)e(P, Q) can be efficiently computed

​
Non-Membership Proofs

To prove that an element bb is not part of the accumulated set, the prover uses the Polynomial remainder theorem which says that we can always represent our polynomial as:

A(x)=q(x)(xβˆ’b)+A(b).A(x) = q(x)(x - b) + A(b).

Using this, the prover can then find q(x)q(x) and send q(Ο„),A(b)q(\tau), A(b) to the verifier. The verifier can then check:

e(g1A(Ο„)βˆ’A(b),g2)=e(g1q(Ο„),g2Ο„βˆ’b).e(g_1^{A(\tau)-A(b)}, g_2) = e(g_1^{q(\tau)}, g_2^{\tau-b}).

This demonstrates that bb is not in the accumulated set.

​
Efficient and Compact Proofs

Both membership and non-membership proofs are constant-size (do not depend on the size of the accumulated set) and can be verified efficiently using bilinear pairings.

​
The Role of Elliptic Curves, Bilinear Pairings, and Points of Unknown Order

​
Elliptic Curves

Elliptic curves over finite fields provide group structures suitable for cryptographic operations. Points on the curve can be added together, and scalar multiplication (repeated addition) is computationally efficient. The security of operations relies on the hardness of the Elliptic Curve Discrete Logarithm Problem (ECDLP).

​
Points of Unknown Order

In our scheme, we use a point GG on an elliptic curve where the order of GG is unknown to all parties. This prevents anyone from reducing exponents modulo the group order, which enhances security by making discrete logarithm attacks infeasible.

​
Bilinear Pairings

A bilinear pairing is a map:

e:G1Γ—G2β†’GTe: G_1 \times G_2 \rightarrow G_T

with the properties:

  • Bilinearity: e(aP,bQ)=e(P,Q)abe(aP, bQ) = e(P, Q)^{ab}
  • Non-degeneracy: e(P,Q)β‰ 1e(P, Q) \neq 1
  • Computability: Efficient algorithms exist to compute e(P,Q)e(P, Q)

Bilinear pairings enable verification of accumulator proofs by translating group operations into scalar operations in GTG_T.

​
Security Assumptions

Our bilinear accumulator scheme does not require any secret parameters. Its security is based on hardness assumptions such as:

  • Strong Diffie-Hellman (SDH) Assumption: Given G,xG,x2G,…,xqGG, xG, x^2G, \dots, x^qG, it is hard to compute (1/(x+c))G(1/(x + c))G for some c∈Zpc \in \mathbb{Z}_p.

  • Discrete Logarithm Problem (DLP): Given GG and aGaG, it is hard to find aa.

These assumptions ensure that an attacker cannot forge membership or non-membership proofs or manipulate the accumulator without detection.

​
Applications of Bilinear Accumulators

Bilinear accumulators are used in various cryptographic applications that require efficient and secure management of dynamic sets:

  • Blockchain Systems: Manage sets of valid transactions or state data, enabling nodes to verify inclusion or exclusion without downloading the entire blockchain.

  • Digital Certificates and Revocation Lists: Efficiently manage certificate revocations, allowing entities to verify the revocation status of a certificate quickly.

  • Anonymous Credentials: Allow users to prove membership in a group without revealing their identity.

  • Zero-Knowledge Proofs: Serve as building blocks in complex cryptographic protocols requiring efficient verification of set membership.

Elliptic CurveszkSNARKs