A sealed bid you cannot change
A commitment is a value that seals a secret now and lets you reveal it later, with proof that you did not change it. It works like a sealed envelope.
Zero-knowledge proofs, sealed-bid auctions and fair online games all start with one.
By the end of this lesson
Note
I can make a commitment to a value and check that it opens correctly.
Key words
| Word | What it means | Example |
|---|---|---|
| Commitment | a sealed value that is opened later | |
| Opening | the value and the salt that unseal it | |
| Salt | a random string mixed in before hashing | |
| Hiding | the commitment does not show the value | |
| Binding | the commitment cannot be opened as a different value | |
| Group | a set of numbers with one way to combine them | powers of 4 mod 1019 |
The cells students fill in are left blank in this preview.
A commitment has two jobs
First, it must hide the value: seeing the commitment tells you nothing about what is inside. Second, it must bind: once published, it can only be opened as the value that went in.
A hash does the binding, because nobody can find two inputs with the same hash. A random salt does the hiding, because nobody can guess it.
Commit to a move and open it
docker exec jupyter python3 steps/commit.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.
Read what the lab printed
The script published a commitment starting 4e219afe2a8aa485. Opened as rock with the salt it checked out as True, and as paper False. That is binding.
Then it committed with no salt. A guesser hashed all three moves and rock matched. With only three possible values, a hash alone hides nothing. The salt is what makes it hiding.
Try it: three sealed bids
import hashlib
def commit(value, salt):
return hashlib.sha256((salt + ":" + value).encode()).hexdigest()
# Three sealed bids for a used laptop, published before anybody opens one.
bids = [["Ines", "120", "q81z"], ["Jo", "95", "t4kk"], ["Kai", "130", "m2pa"]]
for bid in bids:
print(bid[0], "publishes", commit(bid[1], bid[2])[:12])
# Later Kai claims the bid was 140. Does it open?
print("Kai opens as 140:", commit("140", "m2pa") == commit("130", "m2pa"))
# Change 140 to 130 and run again.
A Pedersen commitment uses a group
The lab also has a group: the powers of G = 4, worked out mod P = 1019. There are Q = 509 of them. A second number, H = 9, is in the same group.
A Pedersen commitment to a number m with a random r is G to the m times H to the r, mod P. The random r hides m. Binding holds as long as nobody knows how to write H as a power of G.
Commit to 42 in a small group
docker exec jupyter python3 steps/pedersen.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.
Worked example: what the lab printed
| Commitment | m | r | Value |
|---|---|---|---|
| commit(42) with r = 100 | 42 | 100 | 130 |
| commit(42) with r = 7 | 42 | 7 | 278 |
| commit(20) times commit(22) | 20 + 22 | 11 + 30 | 630 |
| commit(42) with r = 41 | 42 | 41 | 630 |
The cells students fill in are left blank in this preview.
Pedersen commitments can be added
The same 42 gave 130 and 278, so you cannot spot a repeated value. And multiplying two commitments gave 630, the commitment to 20 + 22 with 11 + 30. You can add sealed numbers without opening them.
Proof systems use this to check sums of secrets. With only 509 elements, though, anybody could try every power and break the binding.
A common mistake
Warning
Many people think hashing a value is enough to hide it. It is only enough when the value could be one of very many. For a vote, a move or a small number, a guesser hashes every option. Always mix in a long random salt.