This article outlines how to use hashing functions to create commitment schemes.

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value or statement while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding.
—Wikipedia

The article builds 2 simple, terminal-based examples and serve to build the mental model for how committments are used as primitives in more complex structures. In Bitcoin for example, hash-based committments are used in HTLCs on the Lightning Network.

A Hash Time Locked Contract (HTLC) is a class of payments that use hashlocks and timelocks to require that the receiver of a payment either acknowledge receiving the payment prior to a deadline by generating cryptographic proof of payment or forfeit the ability to claim the payment, returning it to the payer.

Problem statement

A typical toy example for committment schemes is set out like so: two players, Alice and Bob, wish to play a simple game of rock-paper-scissors, but asynchronously. How can Alice send her choice to Bob, without having to trust that Bob will not simply respond with his answer after seeing her choice, effectively winning every time?

The way to solve the issue is by having Alice and Bob send each other commitment hashes, which “lock-in” their answers without revealing them. Once they have exchanged their committments, both players can send each other the hash pre-image, revealing their choice. They can then separately verify that the choices correspond to the committments shared prior.

Naive approach

How could we do this in practice? Here is a “naive” approach: hash the string of your answer and share it with your opponent.

echo -n "paper" | shasum --algorithm 256
# 382635c9325bf3273d195ff1b8a44e5b11afd7d97addeb8863ea35feb98c1a07

I call this the naive approach because it can easily be broken using some form of dictionnary attack. Note that if I know what I expect the potential committed messages to be, I could easily hash them all and verify if any of the hashes correspond:

# rock:     350a770c0ec9f353e1a5629895f374fdaa299876c3870c03feb60eb4a3769d94
# paper:    382635c9325bf3273d195ff1b8a44e5b11afd7d97addeb8863ea35feb98c1a07
# scissors: 493a15e7bda88b07272071cbcfd3cb05920b999872b6f3cfa6e4d16712dbf434

In this case it’s a trivial task to match the hash, and we find that the committed message was paper before the sender reveals anything.

Better approach

A better approach consists of adding a set of random bytes to the committed message, which makes the solution space one needs to scan in order to find the pre-image impractical to brute force. You can generate a set of random bytes using:

xxd -len 16 -ps /dev/urandom
# example: 453a7e985310761793dea4b06545d0d1

Now adding this to our committment message makes it much harder to attack (and the more randomness we add the more secure the committment). Adding random data to the message can be done in many ways, and in this case we’ll just add special characters between the important part of the committment and the added randomness for security. Note also that for the sake of simplicity the bytes are not added as-is, but rather the hex simply used in the string.

echo -n "paper ## 453a7e985310761793dea4b06545d0d1" | shasum --algorithm 256

Multi-layered

An extension of the idea consists of hiding a committment hash inside another committment hash, creating a chain of committments that can be revealed one at at time.

Suppose Alice and Bob wish to play two rounds of rock-paper-scissors. Here is how Alice could do it:

1. Hash both rounds choices with some random bytes (i.e., “rock | paper ## fac9bf”`)
2. Put this hash as the randomness part of her 1st round answer

Suppose her two rounds consist of rock, then paper.

xxd -len 16 -ps /dev/urandom
# fac9bfb78c0329c2ce3a4e096e9b554b

echo -n "rock | paper ## fac9bfb78c0329c2ce3a4e096e9b554b" | shasum --algorithm 256
# e0177543bb7279ee5c5f7a7f15b91e23293cd7fb495a26eb037f940dc4b48bd5

echo -n "rock ## e0177543bb7279ee5c5f7a7f15b91e23293cd7fb495a26eb037f940dc4b48bd5" | shasum --algorithm 256
# 35a1307c43ace0543a85c69a65f14b24534a2ee2056ec92c7dd5bd77c522ca3d

She can send committment 35a1307c43ace0543a85c69a65f14b24534a2ee2056ec92c7dd5bd77c522ca3d to Bob, and reveal her rounds one at a time.

# Alice's committment: 35a1307c43ace0543a85c69a65f14b24534a2ee2056ec92c7dd5bd77c522ca3d

# Alice to Bob: "My round 1 pre-image was 'rock ## e0177543bb7279ee5c5f7a7f15b91e23293cd7fb495a26eb037f940dc4b48bd5'

# Bob can verify
echo -n "rock ## e0177543bb7279ee5c5f7a7f15b91e23293cd7fb495a26eb037f940dc4b48bd5" | shasum --algorithm 256
# 35a1307c43ace0543a85c69a65f14b24534a2ee2056ec92c7dd5bd77c522ca3d -> correct

# Alice to Bob: "My round 2 pre-image was 'rock | paper ## fac9bfb78c0329c2ce3a4e096e9b554b'

# Bob can verify
echo -n "rock | paper ## fac9bfb78c0329c2ce3a4e096e9b554b" | shasum --algorithm 256
# e0177543bb7279ee5c5f7a7f15b91e23293cd7fb495a26eb037f940dc4b48bd5 -> matches with hash in string of round 1 pre-image