March 11, 2019 by Chris Coyne
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.
|Alice||Ok, B, loser donates her kidney. You flip, then I'll call it.|
|Barb||Jeez. Ok. Wait for it.... it's heads.|
|Alice||YES! I called heads.|
|Barb||Wait one second. That doesn't work.|
|Barb||Ok let's try again. Loser donates the kidney.|
|Alice||I call heads.|
|Barb||And...flipping....tails it is! I win.|
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.
This has been solved, theoretically, for a long time.
|Alice||Ok Barb, I've decided to call heads or tails.|
|Barb||Tell me which, then I'll flip!|
|Alice||No, but I will tell you that I've written down a little sentence about my decision.|
|Barb||Ok, then tell me that.|
|Alice||Nah, but here's something. The SHA-256 hash of my sentence is c1e8c057|
|Alice||It's a digital fingerprint of my sentence. Go ahead and flip. Loser donates.|
|Alice||I'm sorry Barb. My sentence was "I call heads. And I have a secret. I hate your lasagna." I called it correctly, so you're the donor.|
|Barb||How do I believe you?|
|Alice||Hash my sentence, B.|
|Barb||You're a real asshole.|
|Alice||An asshole with two kidneys!|
What's going on here?
Barb could check Alice's claim in a terminal:
> echo '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:
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.
- Alice flips a 1 or 0
- Barb flips a 1 or 0
- Charlie flips a 1 or 0
- Danika flips a 1 or 0
- Just add the flips together.
- If the final answer is odd, the flip is TAILS.
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 25 = 32. The columns are added up, just like our 1-bit example.
It's interactive: Click "Reflip" to re-randomize. You can see how the result is as honest as the single most honest participant.
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.
The Keybase app can deal M cards into N labeled hands. I don't know what you would do with that, but enjoy.
💖 This was a fun toy for us to make at Keybase. Every day is an adventure.
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. Keybase's chat is like Slack, except messages are end-to-end encrypted and verified.
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.
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-SHA256of 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,
Thus, all users agree upon a practically infinite sequence of random data (268 bytes worth), and from here 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.
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?
Your last name is COYNE. What were the odds of THAT?!