A short post that while answering an earlier question, also leads into my next post(s) about a meatier topic.

Talk from March 2022 on Sigma Protocols

The talk I gave at "Advancing Bitcoin" in London, March 2022 was posted on vimeo here.

The slides are here:

At the end of the talk (around 26 minutes in the video I posed a homework question:

Sketch an outline of a proof of knowledge of the opening of a Pedersen commitment.

and the clue was: what is the homomorphism? The central insight, as was explained well by Dan Boneh on this talk on discrete based log zkproofs (feel free to sidetrack there - it was a great talk!), is that we get sigma protocols exactly out of the existence of a homomorphism in an encryption scheme (which are very close cousins to commitment schemes).

The homomorphism of the Pedersen commitment

\(C(a + b) = r^{*}G + (a+b)H = (r_1 G + aH) + (r_2 G + bH) = C(a) + C(b)\)

... is true if (and only if):

\(r_1 + r_2 = r^{*}\) .

The homomorphism of this construction is a direct consequence of the homomorphism of the underlying Elliptic Curve group.

Note that the 'distribution' \(f(a+b) = f(a) + f(b)\) is isolated for the two base points, where we assume (as we must for this commitment scheme) that the relative discrete log between G and H is not computable.

Answer to the homework

We follow the commit-challenge-response paradigm (as expanded on in some detail in my talk).

Assume as above that the Prover holds a commitment \(C\) to a hidden value \(a\) with hidden randomness \(r\), and shares \(C\) with the Verifier. He now wants to prove he knows the opening, without revealing it.

First, the Prover constructs a PC to a random value:

\(t,s \leftarrow \mathbb{Z}_{n}\)

Prover sends \(C_1 = tG + sH\) to Verifier.

Verifier sends \(x\) to Prover as challenge.

Prover constructs:

• \(xa+s = p\)
• \(xr + t = q\)

and sends \(p, q\) to Verifier.

Verifier checks if \(xC + C_1\) is equal to \(qG + pH\); if so accepts, otherwise rejects. Notice how this exactly exploits the above homomorphism.