Hash-Based Commitment Scheme
Imagine a round of Rock Paper Scissors played over text messages, whereby two
players must
necessarily take turns throwing their signs. Say the one player is called Alpha and the other
Beta. As the players cannot shoot
their signs at the very same time, one player must go first and the other follow.
Now, if Alpha goes first, Beta can always win,
for they only need to choose the sign that beats Alpha's sign.
Needless to say, that is not a very exciting or fair way to play the game. One wonders if a fair
set up is possible when players cannot throw their signs in real time.
Well, as the
saying
goes, where there is a will, there is a
way. Alpha can commit to
their sign using a commitment scheme and send over their commitment to Beta, concealing their sign
in such manner that Beta cannot tell
what it really stands for. Then, only after Beta sends over their own chosen sign does Alpha reveal
their
committed
sign–one they can longer change after getting to know Beta's chosen sign.
Let us see how this can be carried out using a hash-based commitment scheme. Hash algorithms are
simply many-to-few functions. If you are not familiar with hashing, understand that what follows may
be difficult to grasp. Hashing is how Alpha "locks
in"
and commits to their chosen sign. Actually, Alpha hashes a concatentation of their chosen sign with
a
random
salt value. The reason a salt value is used is that if Alpha were to hash nothing but their chosen
sign–and there are only three possible signs to choose from–Beta could simply hash all three signs
and see which digest matches up with Alpha's. The salt value is added so there should be far too
many combinations to brute-force in reasonable time. At the end of a round, when Alpha's commitment
is revealed, the salt value is thrown out. What really matters is the concealed sign.
Now, if Alpha picks
scissors, Alpha sends Beta a hash of the concatenation of the word scissors with the
chosen
salt value. A longer
salt value should make cracking the sign harder. For ease of demonstration, the range for the
salt in this
round is ten digits long, but in practice,
the length would have to be long enough so as to make cracking infeasable in the average case.
This depends on the computations resources available to the players.
\[
\begin{aligned}
\text{if } sign &= \texttt{SCISSORS} \\ \\
\text{and }salt &= \texttt{9876543210} \\ \\
\text{then }salt || sign &= \texttt{9876543210SCISSORS} \\ \\
\end{aligned}
\]
Using a hash algorithm like the 256-bit Secure Hash Algorithm (SHA-256), Alpha hashes the
concatenation. Note that the hash digest is encoded in hexadecimal (base-16) to save space–the
digest really is just an ordinary number.
\[
\text{SHA256(} \texttt{9876543210SCISSORS} \text{)} =
\begin{gathered}
\texttt{C1BBB4ECAC62B2A0} \\
\texttt{48C90D2144680360} \\
\texttt{3B059CD204321DFC} \\
\texttt{818A89229C0FFE6E}
\end{gathered}
\]
Alpha then sends over that hash digest over to Beta. This marks the end of the commitment phase.
Once Alpha
commits the hashed concatenation, they cannot change the sign and reveal a different one
afterwards without Beta being able to
tell
unless Alpha finds another salt that, when concatenated with the changed sign, happens to collide
with the first digest upon hashing.
Remember, a
collision takes place when two
input messages turn out to have the same hash digest. Owing to the pigeon-hole principle, collisions
are
unavoidable since hash function are many-to-one functions, and for every ouput value, there are
bound to be many different
input values that hash to the same digest.
Nonetheless, with secure hash functions, intentional collisions should still be costly and
time-consuming to actually find.
Thereupon Beta simply sends over their chosen sign in the clear. The message transcript
looks like
this:
\[
\begin{array}{@{}r@{\quad}l@{}}
\text{Alpha:} &
\begin{array}{@{}l@{}}
\texttt{4C252B0D3F2CF6A4} \\
\texttt{74874341A5EE8BB1} \\
\texttt{A72AB5519537CA86} \\
\texttt{B89058253453181A}
\end{array} \
\\ \\
\text{Beta:} &
\begin{array}{@{}l@{}}
\texttt{ROCK}
\end{array}
\end{array}
\]
Now it is time for the revelation and verification phase. Alpha simply reveals their chosen
sign along with the random salt, which Beta verifies by running it through the hash algorithm. Since
Alpha has already chosen "scissors," Alpha cannot reveal a different
sign without the corresponding
hash digest changing as well. If
Beta finds that the resulting hash digest matches the one Alpha sent at the first, Beta can trust
Alpha's commitment to have been verified.
\[
\begin{array}{@{}r@{\quad}l@{}}
\text{Alpha:} &
\begin{array}{@{}l@{}}
\texttt{4C252B0D3F2CF6A4} \\
\texttt{74874341A5EE8BB1} \\
\texttt{A72AB5519537CA86} \\
\texttt{B89058253453181A}
\end{array} \
\\ \\
\text{Beta:} &
\begin{array}{@{}l@{}}
\texttt{ROCK}
\end{array}
\\ \\
\text{Alpha:} &
\begin{array}{@{}l@{}}
\texttt{9876543210SCISSORS}
\end{array}
\end{array}
\]
The only way for Alpha to have changed the sign before revealing it was if they had found another
random
salt value that, when
concatenated with the different sign, happened to result in the same exact hash digest as that of
the
first
commitment. No small feat. This would take considerable time, and
in practice, the salt string would likely be much longer, possibly hundreds of digits long so as to
make
brute-force attempts to find a collision practically impossible.
To illustrate, if Alpha were to reveal "paper" instead, the hash value of the concatenation
would be completely different than that of the first, and Beta would be able to tell that the sign
was changed.
\[
\text{SHA256(}\texttt{9876543210PAPER}\text{)} =
\begin{gathered}
\texttt{6C0DF113616E7935} \\
\texttt{A6A46AD4AC8E77C1} \\
\texttt{8DAEF21AA7F8F598} \\
\texttt{C3039ED999AF66C0}
\end{gathered}
\]
On the flip side, Beta could also try to brute-force Alpha's commitment to reveal it before sending
over
their own sign. They could do so by hashing the concatenations of one of the three signs with all
the possible permutations of the random salt until they happened to strike a match with the hash
digest of
Alpha's commitment. This would also take considerable time and effort.
As it turns out, no commitment scheme can be both perfectly concealing and perfectly binding. In
practice, one property is therefore made perfect while the other is only guaranteed
"computationally" secure against efficient cracking attempts.