This is a simple explanation of cryptographic commitment schemes, requiring minimal math or cryptography background.
What is a commitment scheme?
A commitment scheme is effectively a cryptographic envelope. I can put a secret value in an envelope and then seal the envelope. We call this committing to the secret value. And then I send the envelope to someone or put it somewhere I cannot tamper with it, to open and reveal the secret value I committed to at some later time.
The two important properties of this scheme are:
- Hiding: No one can see inside the envelope until it is opened.
- Binding: Once I have commited to this secret value and sent it, I cannot change the value. The commitment has bound me to a specific value.
This is an imperfect analogy, but it gets across these two important properties of commitment schemes.
Cryptographic Commitments
For cryptographic commitments, we’re going to need two algorithms: Commit and Verify. Let’s go through each one now.
Commit
The Commit algorithm lets us create commitments. Let’s call a commitment com. To commit to a value value:
com = Commit(value, randomness)
where randomness is another secret value, but one picked randomly, hence the name. The result com is what we’ll send or broadcast, i.e. com is our sealed envelope.
Verify
When we’re ready to open the commitment, anyone can verify the commitment
was opened correctly once they get the values for value and randomness:
Verify(value, com, randomness) = [accept, reject]
The result of the Verify algorithm is either to accept or reject the opening as valid.
Hiding and Binding
Remember that we wanted our commitment scheme to share the security properties as the toy example: hiding and binding. For this cryptographic scheme, what does this mean a bit more concretely?
Hiding
com should not reveal anything about the committed secret value. You should not be able to see inside the envelope.
Binding
Given a commitment com = Commit(value_1, randomness_1) it should not be possible to find
another valid opening, i.e. another value_2 and randomness_2 such that com = Commit(value_2, randomness_2), where we exclude the trivial value_2 != value_1.
Hash Commitments
Now let’s turn to some ways to make real cryptographic commitment schemes.
We can make a commitment scheme from a collision-resistant hash function H().
Our commitment will be generated by simply hashing our value and randomness:
com = H(value, randomness)
And then we can verify openings using:
H(value, randomness) == com
If H is collision-resistant, then the scheme is binding. Because if you can find
a second valid opening, then you’ve found a collision in H and it is not collision-resistant.
If H produces random outputs, then you learn nothing about value, so the scheme is
hiding.
Pedersen Commitments
Given a finite cyclic group, such as an elliptic curve group, we can compute:
com = Commit(value, randomness) = [value]G + [randomness]H
where G and H are two points from the elliptic curve group, and value and randomness are scalars.
We get another elliptic curve point as a result.
We can then verify by checking:
[value]G + [randomness]H == com
One handy feature about Pedersen commitments is that they are homomorphically additive. This means when we add the commitments, we get the commitment of the sum of the values we committed to: all without knowing the secret values.
Let’s show this. Given two commitments com_1 = Commit(v_1, r_1) and com_2 = Commit(v_2, r_2):
com_1 + com_2
= [v_1]G + [r_1]H + [v_2]G + [r_2]H
= [v_1 + v_2]G + [r_1 + r_2]H
= Commit(v_1 + v_2, r_1 + r_2)
We end up with the commitment to the sum of the input secret values.