1
$\begingroup$

In the ZeroCoin paper, it uses a zk-proof from Camenisch's dynamic accumulator that shows a Pedersen commitment hides an element of an RSA accumulator (https://link.springer.com/content/pdf/10.1007/3-540-45708-9_5.pdf). However, it looks like that the proof can also be used to prove that a subset of elements belong to the accumulator.

Now the question is: how does ZeroCoin prove that the Pedersen commitment hides a single element?

$\endgroup$

1 Answer 1

2
$\begingroup$

Every element in the accumulator is a prime, between some chosen bounds. In this case, the Pedersen commitment

$$ c = g^Sh^r \pmod{p}$$

is chosen so that $c$ is prime. Then, all these values $c$, each representing a "coin", are accumulated into the RSA accumulator $$u^{\prod {c_i}} \pmod{N}.$$

Whenever a coin is spent, the network checks that $c$ is indeed prime (meaning it cannot represent more than one accumulated value), and that its membership witness inside $A$ is valid. Note that this is done indirectly via the proof of knowledge you mentioned, but that proof of knowledge does indeed require $c$ to be prime. A proof is given in the full version of the paper, Theorem 4.

$\endgroup$
4
  • $\begingroup$ I was reading the ZeroCoin paper. For the coin $c$, when it's spent, it looks like it is NOT disclosed to the public (that's why Camenisch's zk-proof is used). The check of $c$ is prime is performed when $c$ is added (created) and saved to blockchain, but not when it is spent (because $c$ is anonymous). So here, when it's spent, I could actually try to submit a proof for $c_1 * c_2$ and submit proof $c_1*c_2 = g^{S_1 + S_2} h^r'$. This looks like an attack? $\endgroup$
    – Sean
    Feb 21, 2022 at 13:54
  • $\begingroup$ As mentioned, Theorem 4 of the full paper says that a valid proof also proves that $c$ is prime. You are correct that $c$ is not disclosed, so as to not leak where the spent coin came from. That's why I wrote "that this is done indirectly" $\endgroup$ Feb 21, 2022 at 20:26
  • $\begingroup$ Thanks. I'd assume it's the range proof that limits it to be a single prime? $\endgroup$
    – Sean
    Feb 22, 2022 at 23:10
  • $\begingroup$ It is more than just a range proof, it is a full proof of knowledge, but that is just one of the things it proves. $\endgroup$ Feb 23, 2022 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.