Cryptographic Accumulators: Part1
This post covers a basic introduction to cryptographic accumulators and their construction using RSA groups of unknown order. I decided to write this post after reading this paper. The paper is a very good read if you want dive deeper.
A cryptographic accumulator is a short binding commitment to a set of elements and allows for, short membership proofs for any element in the set and/or, non-membership proofs for elements not inside the set. These proofs, also called witnesses (witness to element being accumulated in the accumulator), can be verified against the commitment. They are often used as communication-efficient authenticated data structure for remote databases, where individual elements with their proofs can be retrieved and efficiently verify integrity of the database.
Accumulators can be categorized into Static and Dynamic. Unlike static variants, dynamic accumulators allow for addition/deletion of elements at cost independent of the size of the accumulated set. A dynamic accumulator is universal, if it supports both membership and non-membership proofs.
A Merkle Tree is also an example of an accumulator, it is a binding commitment to a set. The membership proofs and non-membership proofs are logarithmic in size of the set. Additionally, Merkle Trees are vector commitments, they are position binding commitments, i.e., each position in vector is bound to a unique value.
RSA based Dynamic Accumulators were 1st introduced in [CL02] , with application as efficient revocation of anonymous credentials. [LLX07] presents definition of Universal Accumulator and efficient algorithms for updating membership/non-membership witness, when accumulator is updated by addition/deletion.
A basic RSA based accumulator construction
Assume a RSA group with modulus N, and a random generator of the group g. Let S be set of integers to be accumulated. Hprime be hash function which hashes integers to unique odd primes. Sp be set of primes resulting from hashing elements of S. Let p_s be product of all primes in Sp. Then the value of accumulator is
A = g^(p_s) mod N
which is a single RSA group element. This value can be passed around as commitment to set S. For any element x in S, let p_x be corresponding element in Sp, such that
p_x = Hprime(x)
Membership proof of x or witness wx, which verifies that accumulated set corresponding to A contains x, is given by
wx = g^(p_s/p_x) mod N
Membership of x, can be verified against commitment A, using witness wx as follows:
wx^p_x mod N = (g^(p_s/p_x))^p_x mod N = g^p_s mod N = A
The requirement of accumulated values to be primes is for generating efficient non-membership proofs without any trapdoor information. Trapdoor information is order of the RSA group which is (p-1)*(q-1) for N = p*q, where p and q are large primes.
Non-membership proof for y, not part of set S, can be generated as follows:
- Calculate Bezout coefficients a,b, such that, a*p_y + b*p_s = 1 . Such coefficients exist because p_y and p_s are co-primes.
- Non-membership witness, u_y, for y is pair (g^a, b).
- To verify that y is not part of accumulated set, using u_y = (d, b), check,
(d^p_y)*(A^b) = (g^(a*p_y))*(g^(b*p_s))
= g^(a*p_y+b*p_s) = g
Above is what a implementation of function Add and Del to update accumulator states and generate witnesses in go could be like. If witnesses are stored, they need to be updated on each update(Add/Del). Efficient algorithms for updating both Membership/Non-membership witness on Addition/Deletion of an element are as proposed in [LLX07](section 4.2).
For example, If an element x is added to the accumulator A, and the wy be the current membership witness for all y != x in S. The new accumulator value and witness after update, A_new and wy_new are
A_new = A^(p_x) mod N
wy_new = wy^(p_x) mod N
such that, wy_new^p_y mod N = (wy^p_y)^(p_x) mod N
= A^(p_x) mod N = A_new
Batching And Aggregation Techniques for Accumulators
This section briefly describes batching and aggregation techniques for accumulators as contributed by paper (section 4). This work is in the direction of making accumulators usable for practical applications.
Batching refers to applying a single action to n items, than applying single action once for each item. Adding n items together, rather than adding 1 item one by one will be an example of batching.
Aggregating refers to combining n items to a single item. An example of aggregation would be to combine n membership witnesses to a single witness, verifying membership of all n items.
Thanks to recent work by [Wes18], the following functions will be used as a black-box in above batching and aggregation techniques:
the pseudocode for these functions can be found in paper(Figure 1).
- NI-PoE (Non-Interactive Proof of Exponent) :
Given u,x and w, such that u^x = w, NI-PoE generates a succinct proof, which can be used to verify u^x = w without calculating u^x . - NI-PoKE2 (Non-Interactive Proof of Knowledge of Exponent) :
Given u,x and w, such that u^x =w, NI-PoKE2 generates a succinct proof,
which can be used to verify that the prover knows x such that u^x = w, without revealing the x to the verifier.
Some other helper function to be used are:
- ShamirTrick: Given xth and yth root of an group element g, where x and y are co-prime, it returns xyth root of A.
ShamirTrick(x,y, g^(1/x), g^(1/y)) = g^(1/(x*y)) - RootFactor: Given y=g^x, and factorization of x = x1*x2…xn, returns
all xith roots of y i.e., y^(1/x1), y^(1/x2)…y^(1/xn). This algorithm runs in O(nlogn) time. This algorithm can be used to generate all membership witnesses of set S at once.
Batching Accumulator updates
BatchAdd: Adds a number of elements {x1, x2, … , xn} to accumulator A, instead of adding all elements one by one. The efficiency gain is due to a single group exponentiation and O(n) multiplications, instead of O(n) group exponentiations. A succinct proof using NI-PoE can be generated and distributed which verifies accumulator update was done correctly.
x_p_batched = Hprime(x1)*Hprime(x2)…*Hprime(xn)
A_new = A^(x_p_batched)
NI-PoE(x_p_batched, A, A_new) : succinct proof that accumulator was updated correctly
BatchDel: Deleting elements {x1, x2, …, xn} from accumulator A is not so simple. One inefficient way to do create accumulator from scratch without deleted elements. It can be slightly improved if we have membership witnesses for elements {(x1, wx1), (x2, wx2),…(xn,wxn)} to be deleted using following mechanism :
- Delete x1, the new accumulator value is simply the witness of x1, A_new = wx1
- update all other witnesses.
- repeat step 1 for remaining elements.
More efficient way to delete elements given their witnesses is by using ShamirTrick iteratively to calculate A^(1/x_p_batched), where
x_p_batched = Hprime(x1)*Hprime(x2)…*Hprime(xn)
We generate a succinct proof of the update by NI-PoE, i.e.,
NI-PoE(x_p_batched, A_new, A).
Aggregating Membership Witnesses
Given elements and their membership witnesses, {(x1, wx1), (x2, wx2),…(xn,wxn)}, a aggregated witness wx_p_batched for
x_p_batched = Hprime(x1)*Hprime(x2)…*Hprime(xn)
can be generated either if you have whole accumulator set S or witnesses wx1, wx2, … wxn . In the latter case, it is simply A^(1/x_p_batched), which is can be calculated using ShamirTrick as mentioned in BatchDel. Former case is trivial, it is by calculating g^(x_p_others), where
x_p_other = Hprime(y1)*Hprime(y2)*…Hprime(ym)
for all yi’s in S but not in {x1, x2…xn}.
Batching Non-Membership Witnesses
A single non-membership witnesses for elements {x1,x2,…xn}, can be created as follows:
- calculate s_p = Hprime(y1)*Hprime(y2)*…Hprime(ym) for all yi’s in S.
- calculate x_p_batched = Hprime(x1)*Hprime(x2)…*Hprime(xn) .
- calculate a,b = Bezout(x_p_batched, s_p)
- calculate v = A^b, d = g^a
- Generate proofD = NI-PoKE2(b, A, v) and
proofG = NI-PoE(x_p_batched, d, g*(v^(-1)) - Non-membership witness is {d,v, proofD, proofG}
If you notice the above process is very similar to generating a single non-membership proof upto step 3. Step 4,5,6 are essential for batching efficiency gain. We could have kept the process same and just sent {d, b} as witness, but size of b would be same as size of x_p_batched, There would be no significant gains vs sending n proofs separately.
Summing Up
This post briefly describes RSA based accumulators and, batching and aggregation techniques to amortize accumulator operations.
Next post on same topic cover, How to utilize accumulators in context of blockchains.
