The paper on the Bulletproofs Zero-Knowledge proof protocol states in paragraph 3:

In Protocol 1 the element $u$ is raised to a verifier chosen power $x$ to ensure that the extracted vectors $a, b$ from Protocol 2 satisfy $\langle a, b\rangle =c$.

I can't make sense of this.

I guess it is because the scalar $u$ is not given in the relation, thus the value $P'$ can be computed incorrectly. Am I right?

Also I wonder assuming $u$ is public and given in the corresponding relation, if we can omit this step and directly run Protocol 2?


1 Answer 1


One of the authors give an anwser:

Protocol 2 proves the following statement: "given a point P, there exist vectors a and b such that P = aG + bH + *G". This problem is that this statement isn't very useful. If I give you a point P, it's nice to know that I can deconstruct it into some sort of inner product thing, but in practice you typically know what should be, and you want a proof that it's the correct thing. We'll call the statement being proved here Statement 1.

So the statement we really want is "Given P and c, there exist vectors a and b such that P = aG + bH and c = ". Same as above, but I've moved the actual inner product "out of hiding" by taking it out of P and making it explicit. Call this Statement 2.

The obvious way prove Statement 2, which we want, given only a proof system for Statement 1, which we have, would be for the verifier to compute "P' = P + cG" and ask for a proof of Statement 1 on P'. This doesn't work, because a malicious prover could simply prove Statement 1 on a point P', then choose c to be whatever he wanted and provide c, P = P' - cG to a verifier.

There are a few ways to prevent this. The tactic chosen in the paper is to force the prover to choose P before he learns what G is. Then he can't set P = P' - cG; for a given P' this is either true or it isn't! Instead, the prover is forced to choose P' = P + cG, which is exactly what we want him to.

So how can we force the prover to choose P before knowing G? Easy, hash P to get a new value x and replace G with xG.


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.