Commit to a bit

This is the second in a set of loosely-coupled shorter blog posts.

In the previous blog post, we discussed the answer to the puzzle 'how do you prove knowledge of the opening of a Pedersen commitment'?

In this post, we're going to extend that, but before continuing, make sure you 'grok' the idea of the previous post. You could see the idea as 'do the Schnorr protocol for both the value and the randomness of the original Pedersen commitment, then combine the two using the homomorphism, in the final verification'.

In any case, make sure it makes sense at least, even if you don't 100% grok it, before reading this one.

An extra dimension: I won't reveal it, but it's a bit!

Now the Prover wants to convince the verifier not only that he knows the value \(m\) in \(C = mG + rH\), but that that value is either 0 or 1, and nothing else.

The solution to this problem presented here, is taken from Section 2.3 of this paper, which we will be talking more about in the next blog post, so I won't discuss it further now.

Central concept: if I want to prove that a particular variable takes a value in \(x_1, x_2, \ \ldots\), the logical way to do this without revealing which, is to construct the polynomial:

\(p(x) = (x-x_1)(x-x_2)\ \ldots\ (x-x_n)\)

... and validate my claim by proving that \(p(x) = 0\) for the (presumably secret) value \(x\). This works because of the commutativity of multiplication (or to say it another way, the 'role' of each \(x_i\) in the polynomial is the same, which is sort of the very starting point of Evariste Galois' insight leading to his famous impossibility result).

Clearly this would be applied in this context, as proving that \(m(m-1) = 0\).

The Prover P starts by publishing the commitment to m, let's say: \(C = mG + rH\).

Now, following the \(\Sigma\)-protocol paradigm, P will send a one-time commitment (or commitments!) to the verifier V.

If P sends \(C_1 = aG +sH\), then V sends \(x\), then P sends responses as per the previous blog post: \(f = mx + a\), \(z=rx+s\), then the verifier has no construction using \(C, C_1, f, z\) that can provide evidence that \(m(m-1)=0\), of course.

To unpack that (very obvious!) statement further: to get a quadratic polynomial in \(m\) to be verifiable from the aforementioned 4 quantities received by V, we are going to need the 'm' term in \(f\) to be multiplied by the commitment containing \(m\), which is \(C\). (We can't just ask the verifier to 'multiply by \(m\)' of course - that's exactly the secret data we're hiding from V!).

This leads us naturally to look at \(fC\) - this is a Pedersen commitment to the value \(fm = m(mx+a)\), which is a polynomial, but the second factor \(mx+a\) is essentially uniformly random, so as expected, we have deduced no information about the value of \(m\), and that is of course by design - this is a commitment scheme, and it has the *hiding* property.

How can we massage this a bit to get it to be \(m(m-1)\) instead? If we try \((1-f)C\) we are committing to \(m - m^2x -am\) which is closer, but even the first two terms still don't work because of the factor \(x\), so instead let's try \((x-f)C\), which gives us instead \(x(m-m^2) -am\) and now we're nearly there; it's OK to use \(xm(m-1)\) of course, because \(x\) is known to the verifier.

But we have a dangling \(-am\). We handle that by adding a second one-time commitment - a commitment to \(am\), which will then be added in by V at the end, to cancel out the dangling term.

We will still have to handle the blinding factor (H) part of this extra commitment, as we see below.

The full protocol (interactive) becomes:

P holds \(C =mG + rH\)

P sends: \(C_1 = aG + sH,\ C_2 = amG + tH\)

V sends \(x\)

P sends: \(f = mx + a\), \(z = rx + s\), \(q = r(x-f) + t\)

V verifies:

\((x-f)C + C_2 \stackrel{?}{=} \textrm{Comm}(0, q)\)

\(xC + C_1 \stackrel{?}{=} \textrm{Comm}(f, z)\)

The construction of \(q\) is to make sure that the "H" part of the commitment \((x-f)C + C_2\) matches the randomness of our constructed Pedersen commitment to zero.

Completeness, soundness, zero-knowledgeness

As usual the first is just handle turning, and while the third is not, it follows the exact same pattern as usual (transcripts faked out of order).

The second is the most important: We refer the reader to the paper as linked above for the proof, but note a couple of key points: we need two transcripts, because we are extracting two unknown quantities, \(m\) and \(r\). Also, given the two challenges \(x, x'\), we build \(xC - x'C = \textrm{Comm}(m(1-m)(x-x'), \ldots)\) and here we can see that assuming random \(x\) gives us \(m \in \{1, 0\}\) with overwhelming probability. (though - you should work through the full algebra!)

The Fiat Shamir transform here must include the original commitment \(C\) in the hash, to avoid vulnerabilities of this type.

Useful?

Amusingly, the authors of the paper lay out this protocol as an introductory step and describe the protocol as "well-known". I have not been able to find it anywhere else, so I would call on my readers to tell me where it was first written down (certainly the concept of "committing to bits" is seen pretty widely, but I'd like to dig up the origin of this exact construction).

So the answer to is it useful is somehow an emphatic yes and an equally emphatic no.

• No - because this protocol requires two curve points and three scalars for every bit of any bit string you want to commit to. So I'm not going to use it, on its own, to prove, say that several bits in a bit string are zero or one or similar.
• Yes - because homomorphically committing to bits is an exceedingly useful thing. The first place I saw this usefulness was in relation to Confidential Transactions (see Section 3.3 "Range proof" in this old writeup); while there we encode amounts in base 4 for optimal space usage, the idea made sense with binary digits, too - you can ring-sign over all the potentially valid 'bits' (or 'quads'? what are they called..), ensuring that the actual commitment corresponds to at least one of them. What we'll see in the next blog post(s) is that bit-decomposition and proving that one of the bits is zero can give a surprisingly, even spectacularly good scalability.