# 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 arevector 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)forN = 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 Nwy_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

= 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**x**th and**y**th root of an group element**g**, where**x**and**y**are co-prime, it returns**xy**th 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**xi**th 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.