Commitment schemes

The first stop in my journey into Ouroboros is commitment schemes — a very common cryptographic primitive. Most cryptocurrencies use them in some way, but in Cardano they’re especially relevant. The Ouroboros protocol chooses slot leaders for the next epoch using a “coin flipping” game in the present epoch. To play that game you need a commitment scheme (among other things).

To demonstrate the idea, ask yourself: How could we play scissor, paper, rock by email? It wouldn’t really work. If you go first, you’re at a disadvantage because I can read your move before sending mine. What we need is a way for you to send me a commitment to your move without actually revealing it. That’s what a commitment scheme gives us.

More explicitly the two properties we need for a commitment scheme are:

  • Hiding: The receiver shouldn’t be able to figure out the move from the commitment.
  • Binding: The sender shouldn’t be able to change their move after they’ve made the commitment.

If we translate the above into the properties of a mathematical function, they are:

  • Hard to invert (one-way): Given an input it’s easy to calculate the output, but given an output it’s hard to the calculate the corresponding input. (this gives us hiding)
  • Second-preimage resistance¹: For any given input it’s hard to find another input that gives the same output. (this gives us binding)

There’s two main types of functions that have the above properties:

  • Cryptographic hash functions are not invertible² and collision resistant. Collision resistance is a stronger assumption that implies second-preimage resistance. They give us perfect hiding and and computational binding.
  • One-way permutations are hard to invert and have no collisions. They give us perfect binding and computational hiding. Public-key encryption schemes are usually based on one-way permutations.

It’s actually impossible to get perfect hiding and perfect binding. Computational binding or hiding means that it has the property assuming some bound on the adversary’s computational power. For this post, I’ll show you a scissor rock game I built with a commitment scheme based on the cryptographic hash function SHA256. In the next one we’ll use a one-way permutation.

Example

To practically demonstrate a commitment scheme I wrote a scissor-paper-rock game between Alice (🧑🏻) and Rob (🧔🏾). The full code for the example is here. I decided to use Rakudo Perl 6 because it has great unicode support. I like putting emoji and mathematical characters in my code! It’s fun and means I can make the code look like the diagrams I make on my whiteboard.

A single play of the game where Alice plays honestly and wins.

Here’s how each each part of the game plays out in the code:

Alice creates her commitment

my \𝑐 = do {
# Prompt alice for her move and secret
my \𝑠 = CHOOSE-SECRET(🧑🏻);
my \𝑚 = CHOOSE-MOVE(🧑🏻);
# Return the resulting commitment
COMMIT(𝑠, 𝑚);
};

She choses chooses a random secret 𝒔 and a move 𝒎 and passes them both to COMMIT and receives her commitment 𝒄. In practice you should use a random number generator to produce 𝒔, but for this demonstration I prompt the player for it. COMMIT is implemented as follows:

sub COMMIT($secret, $move) {
my @sha256bytes := sha256(($secret ~ $move).encode());
return @sha256bytes».&byte-to-hex.join;
}

sha256() is implemented using the native OpenSSL library. The secret is necessary because if Alice just hashes 𝒎 by itself to Rob could just hash each possible 𝒎 (Scissor, Paper or Rock) and figure out which one corresponds to 𝒄. COMMIT returns a string like:

b556ba2589fb73ceb95c5ed3fa760c05c4030d4b8b79138db13865394c8d1044

which we assign to 𝒄 and send to Rob:

🧑🏻 ⟹ { commitment => 𝒄 };

Rob sends his move

Now Rob has 𝒄, a SHA256 hash. He can’t get 𝒎 from it because SHA256 is hard to invert. Assuming he can’t guess her secret 𝒔, he has no way of figuring out 𝒎. So Rob just picks a move 𝒎ᵣ and sends it in the clear to Alice.

my \𝒎ᵣ = CHOOSE-MOVE(🧔🏾);
🧔🏾 ⟹ { move => 𝒎ᵣ };

Alice reveals her move:

Alice, having seen Rob’s 𝒎ᵣ, knows whether she has won or lost or tied (but Rob doesn’t yet). Alice sends her claim about her original 𝒔ʹ and 𝓶ʹ to Rob.

my (\𝒔ʹ, \𝒎ʹ) = CLAIM(🧑🏻);
🧑🏻 ⟹ { secret => 𝒔ʹ, move => 𝒎ʹ };

Rob calculates 𝒄ʹ from them and if 𝒄ʹ = 𝒄 Rob can be pretty sure that 𝒔ʹ = 𝒔 and 𝒎ʹ =𝒎 because SHA256 is collision resistant — Alice shouldn’t be able to find another 𝒔ʹ and 𝒎ʹ pair that give the same 𝒄. Now both Alice and Rob know who won the game, and neither of them could have cheated!

my (\𝒔ʹ, \𝒎ʹ) = CLAIM(🧑🏻);
🧑🏻 ⟹ { secret => 𝒔ʹ, move => 𝒎ʹ };
my \𝒄ʹ = COMMIT(𝒔ʹ, 𝒎ʹ);
say "Alice's claim: {𝒄ʹ}";
if 𝒄ʹ eq  𝒄 {
say ‘Alice's claim is the same as her commitment.’;
CHECK-RESULT(𝒎ʹ, 𝒎ᵣ);
}
else {
say "Alice is lying! Her claim is not the same as her commitment.";
say "Rob wins by default!";
}

In reality, Once Alice figures out she lost she could decide to run away from the keyboard instead of sending her move claim to Rob. This is of practical concern and what you do is situation dependent. In this case, we’d just make Rob win by default. Ouroboros’ coin flipping game has a way of getting “Guaranteed Output Delivery”, so that even if a party decides to abort the protocol the other parties can reconstruct their equivalent of 𝒎.


In the next post, we’ll take another step closer to how Ouroboros works by making a coin flipping game based on commitment scheme using the discrete logarithm problem (a one way permutation).

Notes

  1. I incorrectly called this “collision resistance” when I first wrote this. Noticed the mistake while reading: https://blog.cryptographyengineering.com/2018/04/07/hash-based-signatures-an-illustrated-primer/
  2. I struggled to word this correctly. Cryptographic hash functions are not invertible unless you know something about the input space, in which case you may be able to determine the input (or at least a probability of an input) by brute forcing it. This is why in the scissor-paper-rock game I prefix the player’s move with a random secret of an arbitrary length so the input space is impossible to brute force.

Disclaimer: All code is for demonstrative purposes only. Please don’t actually use unicode math characters and emoji in real code. Random numbers are not produced on a secure manner. Don’t take articles on the internet like this one as an implementation recommendation. Don’t even assume it’s correct! As always, never roll your own crypto.