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.