This is an old archived article with out of date content.
One-way cryptographic accumulators allow parties to combine many elements into a constant-sized data structure. This structure allows one to prove efficiently that a specific value is contained within the set, without disclosing the value of the member. In Zerocoin, the network computes an accumulator A over all coin commitments (c1, …., cn), along with the appropriate membership witnesses for each item in the set. The witness is simply the accumulator of all coins with the exception of one, and during a zerocoin spend transaction, the user needs to prove knowledge of one such witness.
The accumulators used in zerocoin have the following properties:
The Zerocoin accumulator is defined as
A = uc1\ c2\ c3\ …\ c\ …\ cn (mod N)
where the integers A, u and N are known to everyone. The coin c is a prime number that is a Pedersen commitment of a coin serial number S and random number r. The witness w of a coin c is defined as the accumulation of all coins with the exception of c
w = uc1\ c2\ c3\ …\ cn (mod N).
For computational efficiency, it is noted that the accumulator can be updated incrementally with a new value x by the equation
An+1 = Anx (mod N).
Given A, w, and v, it can be verified that the coin v was accumulated in A if
A’ = wv mod N = A.
A zero-knowledge proof for knowledge of the coin c and witnesss w is given by Camenisch and Lysyanskaya (2002).
Benaloh, J., and M. de Mare (1994). One-way accumulators: a decentralized alternative to digital signatures, in EUROCRYPT ’93, vol. 765 of LNCS, pp. 274–285.
Camenisch, J., and A. Lysyanskaya (2002). Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials, CRYPTO 2002, LNCS 2442, pp. 61–76.