Or: how to shuffle a deck, surrounded by enemiesMarch 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…
Article word count: 1416
HN Discussion: https://news.ycombinator.com/item?id=19360497
Posted by aston
(karma: 6493)Post stats: Points: 160 - Comments: 62 - 2019-03-11T16:52:56Z
Or: how to shuffle a deck, surrounded by enemies
March 11, 2019 by Chris Coyne
A screen recording of a group coinflip in Keybase chat
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 c1e8c05797af6d535d4d86056c19087cfb6978b97f1c2751a6a3a289c4bdd3c3
Barb What? LOL
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.
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.
The tails side of a 1oz Chinese gold panda coin
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^5 = 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:A screenshot of a Keybase chat coinflip randomly selecting Detroit from a list of cities
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:A screenshot of the list of participants of a Keybase chat coinflip
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.A screenshot of a coin flip variant randomly dealing 5 cards each to 4 participants
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.
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-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.
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.
Your last name is COYNE. What were the odds of THAT?!
HackerNewsBot debug: Calculated post rank: 127 - Loop: 418 - Rank min: 100 - Author rank: 38