Coin flipping with discrete logarithms

In Ourobors, committee members play a coin flipping game on the blockchain to produce a random number. I want to eventually recreate this game in all its complexity, but in this article I’ll just demonstrate an extremely simplified two player version of it. Ouroboros’ coin flipping game uses uses discrete logarithms, so that’s what we’ll use here.

This article is part of a series on the cryptography in Cardano’s consensus algorithm Ouroboros. The previous article introduces the idea of commitment schemes.

The discrete logarithm problem

The discrete logarithm problem (DLOG) is based on the fact that exponentiation is easy but logarithms can be hard under a modulus. Consider the following function 𝒇 where all variables are integers:

𝒇(𝒙) = 𝒈ˣ mod 𝒑, where 1<𝒙<𝒒

For some carefully selected values of 𝒑,𝒈 and 𝒒, 𝒇 is hard to invert — given 𝒙 it’s easy to find 𝒇(𝒙), but given 𝒇(𝒙) it’s hard to find 𝒙. For 𝒙 in the range 1<𝒙<𝒒, every𝒇(𝒙) is unique so 𝒇 is also collision free. Therefore we can use the DLOG problem to create a commitment scheme.

Chooising parameters

How do we choose 𝒈,𝒑 and 𝒒? This is the best way to do it:

If you don’t understand any of those terms it doesn’t really matter. I just thought i’d include them to give the curious something to google¹:

What’s important is the last line. 𝒇(𝒙) = 𝒈ˣ mod 𝒑 is a one way function that maps integers in the range of 0..𝑞-1 to unique elements of 𝔾.

To choose the concrete numbers for this post, I just took the smallest 𝒑 from IETF RFC3526. It suggests the following 1536 bit value for 𝒑 to get around 90 bits of security.

llfourn$ perl6
> my \𝑝 = 0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA237327FFFFFFFFFFFFFFFF;

Which gives us a 𝒒 of:

> my \𝑞 = (𝑝 - 1) div 2
> 𝑞.is-prime
True
> say 𝑞.base(16)
7FFFFFFFFFFFFFFFE487ED5110B4611A62633145C06E0E68948127044533E63A0105DF531D89CD9128A5043CC71A026EF7CA8CD9E69D218D98158536F92F8A1BA7F09AB6B6A8E122F242DABB312F3F637A262174D31BF6B585FFAE5B7A035BF6F71C35FDAD44CFD2D74F9208BE258FF324943328F6722D9EE1003E5C50B1DF82CC6D241B0E2AE9CD348B1FD47E9267AFC1B2AE91EE51D6CB0E3179AB1042A95DCF6A9483B84B4B36B3861AA7255E4C0278BA36046511B993FFFFFFFFFFFFFFFF

And a 𝒈 of 2 (The first member of 𝔾 that > 1):

# expmod is Perl 6’s builtin way of doing exponentiation under a modulus.
>my \𝑔 = (2..𝑝).first: *.expmod(𝑞,𝑝) == 1
>say 𝑔
2

It’s fine for us to hardcode these values into our code. You don’t lose security by reusing the same values and they’re all meant to be known publicly².

It’s worth noting that for 𝒈 = 2, some small values of 𝒙 make 𝒇(𝒙) easy to invert. For example 𝒇(5) = 2⁵ mod 𝒑 = 32. Since 32 is just a power of 2 it’s easy to invert. Given how large ℤ𝒒 is you are incredibly unlikely to pick such a number at random.

Let’s go through the commitment scheme I built with the above values.

A coin flipping game

Alice (🧑🏻) and Rob (🧔🏾), will once again face off. This time in a coin tossing game. Both Alice and Rob choose random numbers which are xor’d together to produce a final random number. If it’s even then heads wins otherwise tails wins. Alice and Rob are allowed to behave dishonestly: They can choose an arbitrary number that they think will bias the final number in their favour.

This is why the game needs a commitment scheme. If either of them know the other’s random number before they choose theirs then they can choose a number that results in their win condition. In Ouroboros there’s the same problem: If the final block producer of an epoch can see what numbers everyone else has chosen she can choose one that gives her the most number of slots in the next epoch.

The full code is here. Now I’ll go through it step by step.

Setup

First, I translate the definitions for ℤ𝒑, ℤ𝒒 and 𝔾 above into Rakudo Perl 6. I converted them into subset types and use them to constrain variables and function parameters throughout the code. They’ll give an error at runtime if something doesn’t satisfy their constraint.

constant $ℤ𝑝 = ^𝑝; # Perl 6 for 0..(𝑝-1);
constant $ℤ𝑞 = ^𝑞;
# The types derived from the ranges
subset ℤ𝑝 of Int:D where $ℤ𝑝;
subset ℤ𝑞 of Int:D where $ℤ𝑞;
# The multiplicative group of order 𝑞 ( generated by 𝑔 )
subset 𝔾 of ℤ𝑝 where *.expmod(𝑞, 𝑝) == 1;

Alice’s turn

Alice chooses her move 𝒎 (heads or tails) and her secret randomness 𝒔ₐ∊ℤ𝒒. If she’s honest then she’ll let her computer choose the randomness for her, otherwise she chooses a particular number that she hopes will improve her odds of winning — it won’t work unless she can somehow guess whether Rob’s number 𝒔ᵣ will be even or odd with >50% accuracy (before he has even chosen it!).

# Keep a hint around so Alice doesn't have to remember her number
my $*HINT;
# Prompt alice for heads or tails;
my Coin \𝑚 = CHOOSE-MOVE(🧑🏻);
my 𝔾 \𝑐 = do {
# Prompt alice for her randomness
$*HINT = my ℤ𝑞 \𝑠ₐ = CHOOSE-RANDOMNESS(🧑🏻);
# Return the resulting commitment
COMMIT(𝑠ₐ);
}

With 𝒔ₐ Alice produces her commitment 𝒄∊𝔾 from COMMIT which is just a Perl 6 translation of 𝒇(𝒙) = 𝒈ˣ mod 𝒑.

sub COMMIT(ℤ𝑞 \𝑥 --> 𝔾) { expmod(𝑔, 𝑥, 𝑝) }

Alice then sends 𝒄 and 𝒎 to Rob.

>>>=====Alice sends====>>>
move: Heads
commitment: 0x72559a4e9babdd92d44e3b0c81c2099c210fdc69a632b6c4d977fc045de611f9699545cb954845b3dcb4bf433630d028b87b044dc44cf17493206f6febcc0d1682510e132b3acb117e9916a5d1bc44a2b447dce08fe137121a2773ed994b95d9033586f7afa9dda864522283abd0d185f46482be97cd7334bcfa983423e610bae65eb85a2a65b80ec4e5d446b59c554b3f675e58e233986df171da9a6a08fabae1874fb92b8b4400f27ee0a83df7b7061e3ea2e95bf5977ecab4cb465d1fb0f8
==========================

Rob’s Turn

Rob doesn’t have to choose a move (it’s just the opposite of Alice’s) but he does have to choose his random number 𝒔ᵣ∊ℤ𝒒.

my ℤ𝑞 \𝑠ᵣ = CHOOSE-RANDOMNESS(🧔🏾);
🧔🏾 ⟹ ( randomness => 𝑠ᵣ );

Like Alice, he can choose it dishonestly — unlike Alice he might have way to use this to his advantage depending if he can learn something from Alice’s commitment 𝒄. The hash based commitment scheme from my previous article is perfectly hiding and computationally binding. This gave Alice a small advantage: If she could find a SHA256 collision she could potentially change her move after seeing Rob’s. Conversely, this DLOG commitment scheme is computationally hiding and perfectly binding⁵. It has the opposite problem: Alice can’t change the value 𝒔ₐ she committed to but Rob might be able to find out what it is and choose 𝒔ᵣ accordingly.

To exploit this, Rob has to have some way to test whether 𝒔ₐ is even or odd before he chooses 𝒔ᵣ. The only way for him to do this should be to figure out 𝒔ₐ from 𝒄 completely³. Our choice of 𝒒 should give 𝒄 90 bits of security. He should have to do roughly 2⁹⁰ operations during his turn to get it. That should be impossible (if not we should just choose a bigger 𝒒 and 𝒑)⁴.

In any case Rob sends 𝒔ᵣ to Alice in the clear:

>>>=====Rob sends====>>>
randomness: 0x2f2ef4c313717a3c0574dd45550c7bc6cc2da2ff22b93ce6584a631da420285b16c5dd7db9678635fc77b76c4e8ef2fdf59ae30890fed852307eb6879eba66b3c0d56db0bbfebd752c247942c1880a5cd8b174e62f19c5f2ee6e7f40be8a583ad9d64c2889acb36eb7fca0f9058d8b28ec026647cfd8a7b5583b3b1237ee317f5be388ec21474b19220f99ebefeed689858634acef85240043900c05748efe4455f32ca1258c3d841d7dbab7927d77ff1ea3515657faa13648fc4232c42a09bd
========================

Alice Reveals 𝒔ₐ

Alice makes her claim about what 𝒔ₐ was. Unlike in my last article, it’s impossible for her to get away with lying here because this scheme is perfectly binding — Alice is bound to her choice. So she sends 𝒔ₐʹ to Rob. Rob computes 𝒄ʹ from 𝒔ₐʹ and checks 𝒄ʹ= 𝒄. If it is, he can be 100% sure that 𝒔ₐʹ = 𝒔ₐ.

my ℤ𝑞 \𝑠ₐʹ = CLAIM(🧑🏻);
🧑🏻 ⟹ { randomness => 𝑠ₐʹ };
my 𝔾 \𝑐ʹ = COMMIT(𝑠ₐʹ);
if 𝑐ʹ eq 𝑐 {
say ‘Alice's claim is the same as her commitment.’;
my \𝑠 = 𝑠ᵣ ⊕ 𝑠ₐʹ;
CHECK-RESULT(𝑚, 𝑠);
}
else {
say "Alice is lying! Her claim is not the same as her commitment.";
say "Rob wins by default!";
}

Now that both 𝒔ₐ and 𝒔ᵣ are public we can finally calculate 𝒔 = 𝒔ᵣ ⊕ 𝒔ₐʹ (⊕ is a bitwise xor). The winner is chosen by whether 𝒔 is even (heads) or odd (tails).

The whole point of this exercise is to demonstrate how a coin flipping game can produce a uniformly random number even when controlling the number could benefit one of the players. In this game, the number should be uniformly random given Alice’s move 𝒎 as long as:

  • At least one player is honest
  • Rob can’t solve the DLOG of Alice’s 𝒄

Ouroboros’ coin flipping game produces randomness on the blockchain under similar conditions if no one aborts the protocol (every member of the committee plays the game all the way through). As long as one of them is honest and none of them can solve the DLOG problem, the epoch seed, which selects slot leaders for the next epoch, will be uniformly random and therefore unbiased towards any party.

Of course that if “no one aborts the protocol” is a big if. That’s why Ouroboros coin flipping game isn’t as simple as the one above — It uses a more complicated PVSS scheme which ensures uniform randomness even with dishonest parties aborting the protocol as long as < 50% abort.

Alice and Rob play the game. Alice plays honestly, Rob tries to cheat by not choosing his number randomly (he chooses 3). He loses anyway.

This is the simplest way you can use the DLOG problem in any kind of cryptographic scheme. There’s a lot cooler things you can do with it. In the next article I’ll demonstrate a signature scheme based on the DLOG problem.

Notes

  1. If you want the details on this topic I suggest Jonathan Katz and Yehuda Lindell’s Introduction to Modern Cryptography, 2nd Edition (which I’m reading through at the moment).
  2. This is not entirely true — There are methods of solving the DLOGs like the index calculus algorithm that are faster if you re-use the same 𝐠 and 𝔾 but that’s factored into the 90 bits of security. In practice you should use elliptic curve groups instead of the “multiplicative groups” I demonstrated in this article because index calculus doesn’t work on them.
  3. There’s a proof for this which I haven’t been able to find online in a simple form. Note that it doesn’t work if you choose 𝒒 so that 𝒒 = 𝒑 ˗ 1 (𝒒 not a Sophie Germaine prime). Rob can easily figure out whether 𝒔ₐ is even or odd in this case (without figuring out what 𝒔ₐ is). This is why it’s especially important to choose 𝒒 in the correct way in this example. Check out this crypto stack exchange for a demonstration on how to reveal whether an exponent is even or odd if 𝒒 = 𝒑 ˗ 1 (or any other even number).
  4. If he has a quantum computer with enough q-bits he could do it in much less operations but we are far away from building one. The biggest number factored with a quantum computer so far is 291311!
  5. Discrete logarithm commitment schemes needn’t be perfectly binding and computationally hiding. For example, The Pederson commitment scheme is perfectly hiding and computationally hiding.

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.

Like what you read? Give LLFOURN a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.