# RSA accumulators

The RSA accumulator must be set up by a trusted operator that randomly chooses two strong 1024 bit RSA primes *p, q*, and publishes the integer *N* = *pq*. The values of *p *and *q* are kept secret. The operator discards the values *p *and *q *after publishing *N*.

*Secure MPC: *The integer *N* can be generated through a *secure multi-party computation *among several independent parties. Unless all the participating parties collude to corrupt the system, then nobody will learn the secret values *p *and *q*. Only a single participating party has to be trusted for the process to work. For Findora deployments, the integer *N* will be generated through a secure MPC among several parties including the initial validator set.

*Initialization:* Set *A* = 3. This value of *A* is the accumulator state head.

*Insertion: *Insertion of a new value *val* into the accumulator uses a function *HashPrime* that hashes arbitrary data to prime integers in the range [0, 2^256). The accumulator state head *A* is updated to the new integer *A := A^**HashPrime(val) **mod N*. The first step of *HashPrime* outputs *hashval* = *SHA256*(*val)*. Then, starting with a counter *nonce = *0, it computes *SHA256*(*nonce, hashval*) and checks if this is prime. If it is not prime then it increments *nonce *and repeats the process until the first value of *nonce* that outputs a prime. The parallel implementation of *HashPrime* tests a range of consecutive *nonce* values in parallel. If more than one output is prime then it selects the lowest, otherwise, it shifts to the next consecutive range.

*Membership witness*: The membership witness for a value *val* inside an accumulator with current state head *A* is the value *A**^(1/x)* mod* N* with *x = HashPrime(val)*. This is an integer value *w* such that *w^**x** = A *mod* N. *The state head of the accumulator just before *val* is inserted is the initial membership witness for *val*. Membership witnesses are updated as the state head changes every time a new value is inserted into the accumulator. When a new value *val** is inserted into the accumulator the current membership witness *w *is updated to *w* := *w^**y* with *y = HashPrime(val*)*.

*Non-membership witness: * If the value *val* is not in the accumulator with current state head *A = 3^**y* *mod N*, then *x* = *HashPrime*(*val*) is co-prime with *Y*. The Euclidean algorithm is used to find a large integer *a* (proportional to *y*) and a smaller integer *b* (proportional to *x*) such that *ax *+ *by* = 1. The non-membership witness for val is (D, b) where D=3^a. The non-membership witness is verified by checking that D^xA^b = 3.

*Deletion: * *Deletion of a value val with x = HashPrime(val) from the accumulator requires computing a value A1/x mod N *(the same as a membership witness for val in A) and updating the state head to A := A^(1/x) mod N. This can be computed in linear time w.r.t to the size of the set if all the values that have been inserted into the accumulator are known. If a membership witness *w* for *val *in A is already known, then deleting *val* is simple: set *A* := *w*.

Membership witnesses for all other values also need to be updated when a value is deleted. If the current state head is A and a value val is removed resulting in the new state head A1 = A^(1/x), then the membership witness w* = A^(1/y) for a value val* with y = HashPrime(val*) is updated to w* := w*^(1/y). Note that w*^(1/y) = A^(1/(xy)).

The efficient algorithm to compute the new membership witness A^(1/(xy)) from the old membership witness w* = A^(1/y) and new state head A1 = A^(1/x) first uses the Euclidean algorithm to find integers a, b satisfying an equation ax + by = 1, and then outputs the integer (A1)^b(w*)^a mod N. This output is a value A^(1/(xy)) because [(A1)b(w*)^a]^xy = [(A^(b/x)A^(a/y)]^(xy) = A^(by + ax) = A.