Cryptographic coin flipping, now in Keybase

Decision-making is often improved by adding an element of chance. Who's ordering lunch? Should you take that job? Ought you buy that Corvette?

Also, games need chance. Pairing people off. Dividing a party into poker tables.

These situations are settled, in person, with ceremony. Online or over the phone is another story. One person must take charge. That person could be a liar.

A mental exercise

Alice and Barb, frenemies since college, are kidney donor matches to their mutual friend, Charlie. They talk on the phone.

Tensions grow.

Failure. If Alice goes first, Barb cheats. And vice versa. Texting is also bad, worse even, since emojis cannot relay the tones of deceit.

There is a way around this "Who goes first?" problem, however. Keep reading for an answer, or, if you like programming puzzles, stop to think about it.

A solution!

This has been solved, theoretically, for a long time.

What's going on here?

Barb could check Alice's claim in a terminal:

> echo -n 'I call heads. And I have a secret. I hate your lasagna.' | shasum -a 256

This outputs Alice's hash from earlier in the convo:

5fe0e5d3fdcf7b68c189a85018b8c921308d0cdf5c3b279d6a0cd4401f870ccd

Assuming SHA-256 is not broken, then Alice is being honest. She committed to calling heads.

Cryptography calls this solution a commitment scheme. All the participants commit to their answers, and then share them.

Brilliant, whoever invented this!

Simplifying things, yet adding more people

We now understand that participants can commit to some data, and then share it, solving the "Who goes first?" problem.

Next step. How might 4 people team up, to make a flip even stronger?

The following works, but let's start thinking of 0's and 1's, instead of heads and tails.

1. Alice flips a 1 or 0
2. Barb flips a 1 or 0
3. Charlie flips a 1 or 0
4. Danika flips a 1 or 0
5. Just add the flips together.
6. If the final answer is odd, the flip is TAILS.

Example: 1 + 1 + 0 + 1 = 3. TAILS it is!
Tech term: This is called taking the XOR ("ecks-or") of the bits

Amazing! No individual or coalition could cheat.

More than just coins

If these friends can generate one coin flip (one "bit") fairly, they can generate many. Here's how they might generate 5 bits to get a number under 2⁵ = 32. The columns are added up, just like our 1-bit example.

Seeing it in Keybase!

Starting in today's release of Keybase, if you type /flip, you'll see a coin flip. Anyone online contributes.

Keybase can also do randomized shuffles:

18 participants were online in my team's chat. I was online, so I know this flip was fair. I'm honest, after all.

What if I wasn't online?

I can review who participated in the ceremony by clicking the list of participants:

Great, I trust mlsteele, my friend Miles. He would never run a hacked Keybase app. It doesn't matter what I think of everyone else in the list. Just having Miles there makes it fair.

Otherwise, I'll need to decide if all 18 of them conspired. Maybe, but 18 is a big conspiracy.

Cards

The Keybase app can deal M cards into N labeled hands. I don't know what you would do with that, but enjoy.

Wrapping up

I left out a few details...see the FAQ below and online discussions. And of course, the Keybase apps are all open source, so you can read or copy our source code. Or just install it already.

💖 This was a fun toy for us to make at Keybase. Every day is an adventure.

---

FAQ

Who invented commitment schemes?

My wife Not sure.

How do you know the participants aren't pretending to be each other?

Everyone signs their commitment.

Why did Alice add that bit about the lasagna?

Alice needs to introduce some randomness. Otherwise, Barb could check the hashes of "heads" and "tails." and reverse Alice's commitment to guess her flip.

How do you roll, say, a 6-sided die? Your JavaScript demo above worked on powers of 2.

Let's say you need a random integer, greater than or equal to 0 and less than n. We use the standard algorithm, which is to pick a random number below the next power of 2 greater than n. If this number also happens to be less than n, then output it. Else, reflip and try again. This protocol takes two rounds in expectation.

How do you generate a random sequence of integers that all flippers securely agree on?

Getting into the weeds:

• All flippers generate a random 32-byte secret. This is a better secret than "your lasagna sucks."
• All flippers commit to the HMAC-SHA256 of the game information and their secret.
• All flippers reveal their secrets, and check the validity of commitments.
• All players XOR together the secrets. This is the sharedKey they all agree on.
• All players generate a pseudorandom sequence seeded with the sharedKey, by computing: AES(sharedKey, 0x1), AES(sharedKey, 0x2), etc.

Thus, all players agree upon a stream of pseudorandom data. It is extremely unlikely that flips would need more than 1K of data from this stream (or 64 calls to AES). From here, the players can use the above technique to pick random integers, or the below technique to shuffle:

How do you shuffle?

We use the Fisher-Yates Shuffle. If we need to shuffle a deck of cards, we need one random number from 0 to 51, then another between 0 and 50, etc. Thus a shuffle is fully determined by the random sequence generated in the prior FAQ.

What cryptographic assumptions is this protocol based on?

Though there has been much interesting work building commitment schemes out of weaker assumptions, we are using a rather blunt instrument and assuming that HMAC-SHA256 is a pseudorandom function.

What if there's a flaw in the protocol?

Feedback appreciated! We'll introduce version 2, and the apps will stop accepting V1 flips.

How do you prevent re-using flips?

The commitment includes extra information about the flip game, not just the secret, to prevent replay attacks.

Metadata?

Keybase's servers see there's a flip of some kind happening, and who the participants are. Keybase cannot decrypt the outcome options (for example, if you're sorting playing cards or loved ones), nor can it know the final outcome.

What if someone loses network before the secret stage?

A bad actor can't change the outcome of a flip but could prevent it from resolving.

The Keybase app will highlight this scenario. Odds are it was just a network issue, but if you have such a person disappearing often, you should break up with them.

Any other caveats?

The device requesting the flip decides who gets under the gun, time-wise, with their commitments. This is packaged up into something accepted by all the participants. If you're excluded as a participant despite being online, AND if you don't trust ANYONE ELSE on the flip, then maybe there's something fishy going on there.

Remember, the rule of thumb is whether you trust any of the participants. If you trust none of them, you can call BS. If you trust one of them, it's fair.

Why did you do this?

Because we'd never seen it done before! And because we could! All the pieces were there.

How do I get Keybase?

https://keybase.io/download or just the Google Play or iTunes store.