Dialogue With Cypher Poker Auther Re: Protocols

PB and JS discussed some fundamental concepts of mental poker implementation.  The dialogue will be choppy and verbose because of the nature of “chat”.  JS’s questions and comments are removed.

PB: The smart contract would have a timeout so that if a player hasn’t submitted their keys, the other player automatically wins.
This works well in a heads-up scenario but has some problems when more players are involved.
Game messaging is primarily between the client (game) software. The contract receives only a handful of messages during the game and most of these are betting messages (Ether is sent to the contract).
If a player is able to access an Ethereum account (i.e. the password for the account), then they could forge messages. In that case, though, it would probably be redundant since they could just clean out the account with a single transaction.
The crypto keys are kept local (to the player’s machine) until the end when the hand needs to be validated/verified. There may be a slight alteration to the protocol in which hashes of keys would be stored with a contract (until the end of the game), but this is effectively the same as holding the keys privately.
At the validation/verification phase, a player’s keys are temporarily stored in the contract and therefore available to anyone. Should the other player read the keys and decrypt the results for themselves they face two options: 1) submit their own keys to fully complete the game 2) cease further interactions with the contract. Option 1 is necessary if the player discovered that they won because otherwise the contract would time out and award the other player the pot. This is what happens in the second scenario in which the player simply “walks away” from the game.
In heads-up play this process if fairly straightforward but when other players are involved in the hand it complicates the matter.
Keys are needed for a full verification of the game. The game could be partially verified using only one player’s keys but this opens the door to cheating.
If I want to see my hole cards, for example, I would first ask you to decrypt them with your keys and send me the results. I would then decrypt those values with my keys to reveal the cards. Your keys remain private throughout this process (otherwise the security is effectively broken).
The contract would store the fully encrypted hole cards I’ve chosen and also the results of the decryption on those cards that you performed (still encrypted with my keys).
However, the contract knows how to perform the decryptions so at the end of the hand (when I’ve submitted my keys), the contract can verify which hole cards I’ve been dealt (from the results that you sent me).
However, this isn’t a full validation since the contract really should also perform your decryptions on the fully encrypted hole cards I’ve chosen. It can compare the results of that decryption to the results that you sent to me, and then apply my keys to complete the decryption.
I could, for example, store completely different values for my partially decrypted hole cards and then submit a different set of keys than used throughout the game. Without access to your keys to verify that these cards actually came from the fully-encrypted deck, the contract has no way of determining that these aren’t the cards I selected and keys I used.
So both players’ keys are needed to trace all the cards’ “lineages”; that is, to prove that the hole cards that were chosen are directly decrypted from the fully encrypted deck.
If I tried to cheat and claim that you sent me partially-decrypted cards A and B (when really you sent me C and D), by submitting your keys at the end the contract could verify that the results I claimed are bogus. At that point there’s mathematical proof that I was cheating so you’d be awarded the pot.
Storing hashes of our keys at the beginning of the game further helps to establish these proofs at the end. Not only do my keys have to produce the hashes I claimed but they (keys) must also produce the cryptographic results I claim that they did.
In a multiplayer scenario this gets complicated and has some problems.
Consider the following scenario: I’m playing against two colluders, one of whom has folded early on in the hand (maybe they know that their friend’s hand is much more likely to win). The remaining colluder plays through to the end at which point I’ve submitted my keys to the contract. Both colluders read my keys from the contract, fully decrypt all the results locally, and realize that they’ve lost. Now the colluder who’s folded out can simply “walk away” without submitting their keys which leaves the contract unable to fully validate the game. However, because the remaining colluder has also submitted their keys, from the contract’s point of view two of us played by the rules and one didn’t, but without being able to validate the game who wins the pot?
One option might be to split the pot, which provides a really nice mechanism for colluders to minimize their losses (they should’ve lost the whole pot but by withholding one of their keys they can at least get part of it back).
So between the two colluders, one of them ​appears​ honest because they’ve submitted their keys. However, without the folded player’s keys, the contract can’t reliably determine a winner so how is the pot to be distributed among the remaining two players.
Let’s say it’s a simple 50/50 split…
If the game was honestly (and fully) played, I should’ve won the whole pot! However, because the colluders were able to see the results at the end before submitting their own keys (keep in mind that they are colluding and so can simply exchange keys using another communications channel), one of the players can refuse to submit keys and thereby cause the contract to have to split the pot between myself and the remaining “honest” player who did submit their keys.
In this scenario, not only have the colluders minimized their losses but they’ve also effectively prevented me from seeing the results of the game (I’m also missing the folded player’s keys).
In this scenario yes, they can. My keys have been stored to the contract and they can simply exchange keys with each other outside of the contract (using Skype, for example).
With access to all players’ keys, they can decrypt the entire game. However, since only one of the colluders submitted their keys to the contract for me to see (the other walked away), I have the same incomplete information as the contract and can’t fully validate the entire game.
I’d have 2 sets of keys, they’d have all 3.
This same problem can be exploited by a single player acting as two.
If both colluders failed to submit their keys then the contract would simply declare me the winner. Knowing this, one of the colluders would submit their keys to the contract so that the results are now inconclusive (without the other colluder’s keys).
Adding more players into the mix makes the problem even worse. In a 3-player game I stand to potentially lose half of the pot (if this is how the contract splits inconclusive games). With 4 players (3 colluders), the results would have to be split 3 ways between the players who submitted keys (the remaining colluder would have walked away and so gotten nothing). Rather than getting 1/2 the pot here, I’d only get 1/3. With 5 players, I could expect only 1/4 of the pot when facing off against 4 colluders. With 6 players I would get 1/5 of the pot…and so on.
This same problem applies to honest games too. In the 3-player scenario, if one player fails to submit their keys then the contract would have no option but to split the pot between the remaining players (or potentially worse, refund contributions to the hand). I imagine I’d be somewhat peeved if I had a royal flush but the game couldn’t be completed because one player disconnected (maybe their computer crashed, maybe their power went off…)
I tried to address this early on in what I call the Dropout Protocol in which the game can continue by re-encrypting the card deck but it has a flaw because it effectively returns the dropped-out player’s cards back to the deck. This does reduce the problem significantly but it still allows for cards that should be out of circulation to be potentially re-introduced into play. If colluder 1 has an ace, for example, and colluder 2 has two aces, colluder 1 could drop out (effectively putting the ace back into the live deck) and increase the chances of colluder 2 to draw the ace to produce a four of a kind, for example. If that ace was never returned to the deck then colluder 2 would have a 0% chance of having a four of a kind, but this way there’s a slight chance that increases as the hand progresses (since there are fewer remaining cards in the deck).
The ideal solution would allow the game to continue ​without​ putting the dropped-out player’s cards back into the deck. At that point the contract, like the players, wouldn’t need all players’ keys and the problem would be solved.
The problem with that solution is: how does the contract know who’s honest and who’s cheating? If only one player failed to submit their keys then from the contract’s perspective the other players have played honestly.
Without all of the keys the contract can’t perform all of the decryptions so it effectively can’t validate/verify the game.
The scenario I was describing was in relation to cash games (no upfront investment). However, the problem remains even when the buy-in is fixed. If there are 8 players for a pot of $800 and only one player fails to submit their keys, the contract would have to split that $800 somehow among the remaining “honest” players. That means that, as a winner, when I should’ve walked away with all $800 I actually only get $114 ($800 / 7). Effectively, the colluding players have secured a $686 “refund” when they actually should’ve lost everything.
In order to be guaranteed (at least) the full pot if the game is incomplete, I’m using the following formula to determine the insurance (escrow) amount:(pot – (pot / (players – 1))) * (players – 1)
With a $100 pot and 3 players, the insurance/escrow would need to be:(100 – (100/2)) * 2 = 100
If one player fails to submit their keys the remaining players would receive:$100 / 2 = $50 (pot)
$100 / 2 = $50 (insurance)
Total = $100
With more players these numbers will grow. With a $1000 pot and 8 players:(1000 – (1000/7)) * 7 = (1000 – 142.86) * 7 = $5999.98 insurance/escrow
If one player dropped out, each remaining player would get:$1000 / 7 = $142.86 (pot split)
$5999.98 / 7 = $857.14 (insurance/escrow split)
Total = $1000
Technically this seems doable. But I wonder if people would be willing/able to put up to $7000 into a contract with a maximum pot of $1000.
I don’t have the answer to that. It’s obviously very subjective.
Ideally no such solution would be necessary (if re-encrypted cards weren’t returned to the deck). In lieu of that, however, I don’t see too many alternatives.
From my perspective there’s nothing preventing CypherPoker from supporting multiple approaches – the game engine still works more-or-less the same way, it’s primarily the Ethereum contract that needs some tweaks.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s