---

What is it good for?

Say, there is a game being played, consisting of rounds.

And we know a secret information (we do not want to share it for this turn). We want to convince the other party that, we have the information, and we will not change it in the upcoming rounds. How to do this, while keeping our information secret for this round?

With commitment, a party can commit to a message, and once committed, the message cannot be changed afterwards (if changed, the prior commitment will create a conflict with the new message, and we can tell the original message is changed).

The difference from digital signatures is that, the other party cannot tell what is being committed in the first step (we are keeping our info secret in this turn). This can be achieved with encryption schemes, or with hash functions . But, encryption schemes need some setup phase, and hash functions do not, utilizing hash functions will be more practical.

Let’s see 2 real-world examples where the commitment scheme would be useful

---

Example 1: ROCK-PAPER-SCISSORS:

Say there are 2 parties, namely Alice and Bob. These parties would like to play paper-scissors-rock. Considering the network delays and other factors, we have to be sure that no one changes their answer till the next round starts. Let me be clearer. Say, Bob has “ROCK” in this mind, and Alice has “SCISSORS”, they haven’t revealed their answers yet. They said “let’s reveal the answers in 3, 2, 1…” And Bob revealed his answer “ROCK”. Alice wanted to cheat, send the answer “PAPER”, and claimed “there was a lag, sorry :)”

Well… Damn.

We can prevent cheating, by using a trusted 3rd party. Both Alice and Bob can submit their answers to this trusted 3rd party. But, you know, we don’t like 3rd parties (maybe this 3rd party’s connection will be problematic, maybe Alice will bribe him). The second alternative is, we can achieve honesty by a cryptographic scheme (commitment), without the need for any trusted 3rd party.

---

How it works?

We will represent Alice with A, Bob with B.

Say, A selected “PAPER”, and B selected “SCISSORS” before knowing each others answers.

Naïve approach:

1. A → B : $h_A = H(R_A \mathbin\Vert paper)$
2. B → A: $h_B = H(R_B \mathbin\Vert scissors)$
3. A → B: $R_A \mathbin\Vert paper$
4. B → A: $R_B \mathbin\Vert scissors$
5. B checks if $h_A = H(R_A \mathbin\Vert paper)$
6. A checks if $h_B = H(R_B \mathbin\Vert scissors)$

Verbal explanation of Naïve approach:

1. A crafts a message, which is consisting of her selection “PAPER” and a random value $R_a$ (do not worry, I’ll explain below why we need the random value). Then computes the hash of this message, and sends it $(h_a)$ to B.
2. B does the same for his selection “SCISSORS”.
3. A now sends the “PAPER” and a random value $R_a$ to B.
4. B does the same for his selection.
5. B checks whether the hash of “PAPER” and a random value $R_a$ is equal to $(h_a)$. If so, he knows that A did not cheat.
6. A applies the same checks on B’s input.

The need for random values:

Now, imagine the above procedure without the random values, will it be insecure? Yes!

1. Say A did not put any random value in her message, and calculated $h_a$ from the hash of “PAPER”.
2. B knows that there are only 3 options (paper, scissors, rock). He can try to hash every one of them, compare it with $h_a$. Ultimately, learning the content of A’s commitment.
3. However, if $h_a$ includes a random value, B also has to guess this random value for each of the options. And if this random value is large enough, B will run out of time guessing it, making the procedure secure.

Some parts are actually not needed. Because as the first step, A sends the encrypted form of “PAPER”. Although B received the encrypted form of A’s commitment, B still does not have any information about what is inside this commitment (paper, scissors, or rock?). So, B does not need to conceal his commitment, he can send it as plaintext. And it does not matter if A can learn about B’s choice, since A already committed to her selection, and cannot change it after learning about B’s choice. But A will know about the result (whether she won, lost, or it is a tie). The worst thing A can do at this point is, choosing not to play anymore, and not reveal her answer. Because of the timeout, B will still win in this case. Effectively, A cannot do better than being honest.

Optimized approach:

1. A → B: $h_A = H(R_A \mathbin\Vert paper)$
2. B → A: $scissors$
3. A → B: $R_A \mathbin\Vert paper$
4. B checks if $h_A = H(R_A \mathbin\Vert paper)$

---

Example 2: Puzzle Contest

Say, there is an online contest upon a mathematical puzzle. The first one to find the answer, will be the winner. The network is build upon Gossip Protocol . Basically, we have to broadcast our message (solution) to everybody. The problem here is, what if somebody else steals our answer, and starts broadcasting also? We cannot rely on our message will be delivered faster than the stealer’s message, since we are surrounded by Gossip Protocol. Using Digital Signatures will be in vain as well. Because our solution will also be presented as plaintext in Digital Signature schemes, and the stealer can still get the plaintext, sign it with his private key, claiming he is the real owner.

Again… Damn.

Using the commitment scheme, we can first commit to our answer, broadcast this commit message, wait for a bit (calculate network delays and round-trip-times, etc…), or wait for an answer from the reward giver (which could be a smart contract). As the last step, we can broadcast the real solution confidently.

This solution will come in very handy in blockchains.

---

How it works?

We will represent the player (first one to find the solution) with P, and the stealer with S.

Solution:

1. P generates $M = ID_P \mathbin\Vert Solution$
2. P generates $C = H(M)$
3. P broadcasts C
4. P waits
5. P broadcasts M

Verbal Explanation:

1. P will construct a message, which includes his solution, and his ID as plaintext. BUT BEWARE! P will not broadcast this message (for now). We will refer to this plaintext message as M.
2. P will calculate the hash of M (in other words, P is committing to M). We will refer to this commitment (hash of M) as C.
3. P broadcasts C confidently. Since nobody can derive M from C (it is infeasible to reverse hash function). By broadcasting C, P is basically claiming that he has a solution (others do not know whether the solution is valid yet).
4. P waits for a bit, then broadcasts M (the reason for waiting is, P has to be sure that M will be delivered later than C to all other nodes. Remember, we are in Gossip Protocol).
5. Now, everybody knows the content of the solution from M, and also they know P is the owner (because P’s ID was present in M). P securely proved that he has the solution, and nobody could steal it from P, even in Gossip Protocol.

Why S cannot steal:

When P broadcasts C, S will learn about C. Why S is not claiming he is the owner of C?

Well, he can claim, but he cannot prove. Since C is the hash of M. And in M, there is an ID of P. If S wants to get the reward, he has to prove that, his ID is present in M.

Recall that, S has no way to get M from the C. He has to wait for P to broadcast M to learn the contents of M. Even after learning the contents of M, he is hopeless.

Say S changed the P’s ID in M, with his ID. Now M has the solution and S’s ID.

The problem is, since the original M’s content is changed, its hash is also changed. Now, C will be conflicting with the tampered M. Proving that S is not the owner of the solution.

Let’s think of another scenario. S will learn about M when P broadcasts M.

Now, S knows the solution. He can create a new message with his ID (call it M2), and create a commitment C2 to this newly crafted M2. Yes, that will be consistent.

However, S had to wait for the 2nd round to receive M (remember, C was broadcasted in the previous round). Here will be the chronological order of this attack:

1. S receives C
2. S receives M
3. S crafts M2 and C2. Broadcasts C2

At this point, we are sure that C will be propagated much earlier than C2 in a gossip network. In this scenario, S will not be guilty of stealing (because he also might have found the solution, only later than P). But it does not matter, since the reward will be given to the winner, and C2 will be discarded by the network when the network is convinced M is a valid solution, and is consistent with C.