2024.11 Vol.2

And in the Darkness, Bind Them

There is a part in the the Schnorr protocol where a hash function is used to create a commitment. This commitment is introduced to make the signature scheme non-interactive since it commits the party to a value. A hash commitment is one type of commitment scheme.

c = H(x || r)

The hash commitment scheme produces commitment c by hashing the committed value x concatenated with a random value r.

Commitment schemes have two main properties, hiding and binding. Hiding requires that the commitment doesn’t reveal the committed value. Binding requires that the committer can’t change the committed value after making the commitment.

While a scheme must have both properties, the properties themselves can have different levels of security. They can be perfect or computational. Perfect, as the name implies, means that the property cannot be broken. Computational means the property can be broken if enough computational power is thrown at it. But this is often more than practically possible, so we are cool with it not being perfect. Why risk it though? Let’s just use a scheme with perfect hiding and perfect binding and never worry about it. Well, turns out that’s impossible, known as the “commitment paradox”. As far as we have seen, achieving perfect in one makes achieving perfect in the other impossible. Once you dig into the implementations this push and pull becomes obvious.

So back to the hash scheme.

Technically the scheme could just be c = H(x). A hash function is computationally a one-way function, so the output hides the commitment value. But hiding isn’t worth a lot if the input set for x is small. An attack could brute force each input to discover a committed value. This is where that extra r value helps, assuming it comes from a large set, it protects against brute force attacks. r also helps hide if the same value is committed to twice, each commitment will be different since it is a random nonce. Generating and storing an r per commitment is more bytes definitely worth it.

The hash commitment scheme is not perfect hiding. As hinted at before, a hash function could theoretically be reversed with unlimited computation, so it doesn’t make the cut for perfect. Still pretty good though.

The binding property of the hash commitment scheme depends on the hash function being collision resistant. It is computationally difficult to find two different inputs which hash to the same output, but it is possible (pigeonhole principle), so it is not perfect binding.

The hash commitment scheme has neither perfect binding or hiding, but it is very simple and cheap. It even has the cherry on top post-quantum resistance property. But one thing it lacks which limits its usefulness is algebraic structure. I wonder what to dig into next…

pedersen commitments

Pedersen commitments are created with another popular commitment scheme.

c = G^x + H^r  

A Pedersen commitment c is based on two different generators G and H.

At first glance, this looks very similar to a hash commitment. There is the committed value x and there is also still a random scalar nonce r. However, Pedersen commitments leverage the discrete logarithm problem to hide values instead of a hash function. The Pedersen commitment scheme also looks quite a bit like the Schnorr protocol, however, there are two generator points instead of one. What is going on here?

The r value exists for the same reason it does in a hash commitment, it protects against small input sets which can be brute forced. It is often referred to as the blinding factor since its job is to hide the x. Why not use the same generator point for simplicity? G^x + G^r = G^(x + r) = c, in this case the r still hides x in the c commitment. However, it breaks binding x. The committer is not bound to return x and r, they could just as easily return x+1 and r-1 and tons of other combinations. So that second generator is pretty important, r hides and H binds.

It is essential that the two generators are not related, for example if someone knows H = G^z then they are no longer bound to x since it is equivalent to one generator. Choosing a G and an H can be done with one of a handful of strategies, like using NUMS (Nothing Up My Sleeve) numbers or hashing strings to curve points. Assuming they are not related, it actually makes the Pedersen commitment have perfect hiding. c = G^x * H^r = G^x' * H^r', for any commitment c there are many x', r' combinations which satisfy the commitment. Given just c, all possible values of x are equally likely. There is no way to know for sure which one the committer is hiding from just the commitment. Now, to find these other values you need to break the discrete log problem, so the committer is still computationally bound to their commitment. The Pedersen commitment scheme has perfect hiding and computational binding.

The perfect hiding is nice compared to a hash commitment. But since Pedersen commitments use the discrete log problem, they are not post-quantum secure. While the commitments remain hidden due to the perfect hiding, they would no longer be computationally binding.

So why use these things? Pedersen commitments have algebraic structure. The homomorphic properties means you can perform operations on the commitments and it is the same as performing them on the commitment values. This is not the case with hash commitments.

c_1 = G^x_1 + H^r_1
c_2 = G^x_2 + H^r_2

c_3 = c_1 + c_2
    = (G^x_1 + H^r_1) + (G^x_2 + H^r_2)
    = G^(x_1 + x_2) + H^(r_1 + r_2)
    = G^x_3 + H^r_3

The c_3 commitment can be calculated with the commitments or the committed values.

One might think that the blinding factors would throw off practical use cases, but they are treated as part of the committed value and as seen above, they don’t mess with the homomorphic property.

sigma

Commitment schemes are focused just on the commitment part. The hiding and binding. If a committer wants to prove to a verifier that they know the committed values, they could reveal the values and blinding factors. A verifier could plug them in and make sure the commitments are equal. But it is a one-shot, the committed values are no longer secret.

Things get way cooler when a committer can prove they know the values without revealing them. Good ol’ zero knowledge proofs. Proofs, like the Schnorr Protocol, can be used with Pedersen commitments.

Let’s back it up a bit. Sigma protocols, whether it is a Schnorr implementation or not, requires a one-way function with a homomorphism. This unlocks the ability to operate on “encrypted” (a.k.a. the second group) values. For this previous walkthrough on the Schnorr protocol, the homomorphism is between the scalars (sometimes secret) and the curve points. This means the commitment is a public point, while the challenge and the demonstration are scalars.

C(a + b) = C(a) + C(b)  

The commitment of a plus b is equal to the commitment of a plus the commitment of b.

The homomorphism of pedersen commitments is between the commitments (technically a point) and a pair of scalars. The pair of scalars has the added requirement of the pair of unrelated generators, but this isn’t too much crazier than the normal single generator. This means the sigma protocol can be performed with a public random commitment (R), a scalar challenge c, and a pair of scalars as the response.

Bit of a recap/tangent, but this really hammered home for me how the challenge does not need to be in the same algebraic group as the response or commitment. That probably just lines up for simplicity in the standard Schnorr use cases. The only requirement for the challenge is that it comes from a large enough set that it can’t be brute forced.

So stepping through a proof, a prover wants to prove they know the committed value a and associated blinding factor r of a commitment C. The prover first generates a commitment C_r = G^t + H^s where t and s are both random values. The prover sends C_r over to the verifier. The verifier sends back challenge c. Recall that the verifier is going to check the returned pair, when raised but their respective generators, equals Cx + C_r.

C_s = xC + C_r

  s = x(a, r) + (t, s)  
  s  = (a*x + t, r*x + s)

Prover can calculate the response s pair.

Notice how the pair values can only be combine on the ones which share a generator. The prover can send over the pair s_q, s_p and the verifier can check that G^s_q + H^s_p equals Cx + C_r.

structure

The algebraic structure of Pedersen commits allows for some cool use cases. It is part of what makes confidential transactions possible. In a confidential transaction, the inputs and output amounts remain hidden, but verifiers can still check that outputs minus inputs equals zero.

Let’s say for a transaction input amount x_in we commit to it with C_in = G^x_in + H^r_in, with r_in as the blinding factor of the commitment. Same setup for the output C_out. For simplicity, this transaction has just one input and one output. So the following should be true C_in - C_out = 0, which still keeps the commitment amounts hidden.

What might not be immediately obvious is that this will require some sort of blinding factor management by the prover. If left completely random, these will never cancel out. And as long as the blinding factor still accomplishes its goal of no leaked information, the prover can set them to whatever they want. The algorithm for this is straight forward though, choose a random blinding factor for the input(s) and then set the blinding factor for the outputs so that r_out = r_in. If there are only one input and one output for a transaction, this is a special case where the blinding factors are equal. For multiple inputs and outputs though, you just choose random blinding factors for everything except the last (doesn’t really matter if input or output) and then use it to ensure they all cancel out.

range proofs

The structure of Pedersen commits allows for the transaction amounts to remain hidden, but it is not enough for a verifier to be totally sold that a transaction to be valid. Nothing is stopping the prover from using using negative values, -4 input with outputs of -5 and 1, effectively printing money out of thin air (who would do that!). While the verifier still wants the inputs and output amounts to cancel out, they need some supplemental proof that none of the amounts are negative. As in, the amounts are in a valid range.

Now at this point, I am just gonna point out that range proofs are a relatively new concept (2015-ish) and they have been iterated on a lot since then. The first iteration was kinda like “hey, we did it!” and the ones since then have been improving performance. When compared to a normal, in the clear transaction, range proofs explode the amount of work and space needed by a few orders of magnitude. Especially the first few versions. But I am still going to focus on that before graduating to things like Bulletproofs which introduce more complexity to improve performance.

Range proofs define a minimum and maximum. The minimum protects against the negative numbers and the maximum can help rule out overflow scenarios. That maximum makes more sense when the numbers are part of a cyclic field, like modulo a prime. A really “high” number would cause the sum to wrap around, having the same effect as a negative number (if those existed in modular arithmetic). So they have a window like [0, 2^n). Why the power of 2? Well, we need a way to compare numbers in zero knowledge and that is a little tricky, which is where binary decomposition enters the picture. Generally we want to prove a number x, which is part of a field modulo a big prime number, is under some value. In a computer program, this is really straight forward like if x < 10 {}, but such a comparison would reveal x in our case. How can we prove x is smaller than some number without revealing it? What if we instead prove that x can be represented with only y number of bits. For example, if y = 3 that means the largest number x could be is 111, or in decimal, 7. Then we could say that “if x can be represented in just 3 bits, it is less than 8”. Now you see what that upper bound is a power of two.

The idea is to decompose the amount x into binary x = 2^(0)*b_0 + 2^(1)*b_1 + 2^(2)*b_2 + ... + 2^(n-1)*b_n-1. Then the proof needs to show two things. First, that each b_i is either 0 or 1 (a.k.a. a bit). And second, that x equals is actually this bit representation. This breaks the large proof of “is x smaller than y” into many small proofs.

So first up, how do we prove that b_i is a bit? Well, it is either zero OR one, so a Schnorr protocol OR composition might work here. Usually an OR composition is used to prove knowledge of one of two things, but here it will be to show that the value is one of two things. If we commit to a bit with C = G^b + H^r then there are two possibilities.

b=0: C = r*H
b=1: C = G + r*H

Two possibilities for the commitment C given a bit value.

This creates a scenario where there are two possible pedersen commitments and those commitments are public keys. If there was only one generator point in the equations, we could do a simple OR composition across “I own one of these public keys”. Well, in the b=1 case, all you have to do to get rid of the G is subtract G. What if the verifier and prover agree that one public key is C and the other is just C' = C - G. The prover is tasked with creating an OR composition on {C,C'}. Can the prover do this for both b=0 and b=1 cases?

If C is a commitment to 1 (a.k.a. b=1) then C = G + r*H, and the prover cannot sign anything with C. They don’t know the discrete log since there are two generators. However, C' = r*H and they know r, so they can sign with C' and make a simulation for C. And what if C is a commitment to 0? Well then they known the discrete log for C and not C', still covered. That is nifty.

Now all the prover has to do is show that all these bit commitments (C_i) represent the original committed to value C. Well, if the range is fairly small there is a pretty clever way to do this with the structure of Pedersen commitments. What if instead of b being 0 or 1, it was 0 or 2^i (e.g. 1, 2, 4, 8, 16). This doesn’t change much about the OR compositions other than how many times G is subtracted. Then we could add up the C_i’s, and with some blinding factor management similar to the original confidential transaction manipulation, the sum would equal the original C commitment to the value.

This is all great, but the proof size grows linearly with the number of max bits.

polynomials

Polynomials are introduced to improve performance, namely, lowering how much data is needed for a proof.

For example, we can use a helpful polynomial equation (b-0)*(b-1) = 0. Based on the properties of multiplication, b must be zero or one. This equation can be extended with any other numbers b can be, but since we need it to be a bit, we only care about zero and one. The equation can obviously be simplified in this case to b*(b-1) = 0.

Next up is figuring out how Bulletproofs make this all better with inner products…but I am not there yet.