Guess what … CypherPoker v2.0 isn’t going to be ready by the end of November.
I was feeling pretty good with the pace of my progress with the last two posts and then came time to tackle the Ethereum smart contracts.
Almost everything that could go wrong did, from mysterious FlashDevelop crashes and resets, to an unexpected Morden-to-Ropsten hardfork (which, in hindsight, needn’t have been unexpected), and all the way down to the core CypherPoker source code and issues with the multi-threaded cryptosystem in cooperative mode. This last problem was especially vexing as it was repeatedly halting my attempts at any new new updates.
To add icing to this delicious cake, my home internet connection is no longer available so I’ve been dragging my broke ass to the public library for connectivity. Suffice it to say, it’s an experience on numerous levels.
Nevertheless, I stuck in there over many late nights and sleepy days and yesterday I finally completed the penultimate breakthrough: CypherPoker is now able to play a game through to completion with full Ethereum support – escrow, status tracking, validation, and payout; the works. All of the functionality and options are there in the copious settings, hidden behind the barren interface that’s been there since the early days.
There are so many new pieces in this update I’m not sure if I’ll be able to cover them in this post but if you’re of the tl;dr persuasion then let me just say that all that remains now is a nice user interface, some code cleanup, and if possible maybe an integrated Bitcoin (and other cryptocurrency) to Ether conversion service.
However, if you’re sticking around, here’s what’s new and exciting:
Delays and Defers
Before I was able to start seriously interacting with Ethereum smart contracts I had to solve a problem, one that exists for potentially any application that uses Ethereum’s smart contract system for some of its functionality: transaction delays.
These delays have two primary causes.
The first is the nature of the Ethereum blockchain itself which requires anywhere from 12 to 20 seconds to generate new blocks. Since interactions with the blockchain require new blocks to be mined, and since this may take anywhere from 12 to 20 seconds (sometimes longer), any actions we may want to take within CypherPoker would be limited to one per block, or one per 12-ish seconds. Imagine playing a game of poker in which each player must wait up to 20 seconds (or more), after the previous player has bet before betting themselves. It wouldn’t make for a very good game experience.
To make matters worse, there’s no guarantee that an action will be included in the next block. Transactions are sent to a queue where they wait for a miner to include them in a block. If the new block is full or if the miner doesn’t include the transaction for some other reason we could end up waiting considerably longer than 20 seconds, as I discovered during development:
In comparison to this delay, 20 seconds seems pretty good!
To address this I implemented a two-part solution.
In the first half of the solution I addressed potential delays in deploying or mining new contracts for hands/games. In order to ensure that contracts are available on the blockchain as soon as players want to start a new hand the CypherPoker software has to be able to pre-deploy or pre-mine contracts before a game begins. For example, while playing a current game the software can silently deploy/mine a new contract in the background so that when the game is complete the next contract is on the blockchain and ready to go.
To make this happen I needed to implement a system that is able to not only mine contracts automatically (without player interaction), and silently (in the background), but also track and manage those contracts between sessions so that, for example, if we shut down the computer the software retains information about deployed/mined contracts and can also verify that those contracts actually exist on the blockchain when we start up again. In future revisions the game client should also be able to pick up the contract state and update itself in order to continue from where the game left off.
This is accomplished by managing contract information in the global settings data of the application. This makes the information available outside of the game code so that it can be inspected and managed even when no game is currently running. Each contract’s information is stored in a descriptor node that includes its blockchain address, creation transaction hash, and ABI or interface which describes the contract’s variables and functions. In order to future-proof the solution I also separate the smart contracts according to network ID since Ethereum uses these to isolate individual blockchains (such as Morden, Ropsten, and mainnet), and according to the client type which is currently just “ethereum”.
The second half of the solution was a bit trickier as it required what I call contract state-dependent or deferred function invocations.
To understand this bit it’s useful to understand how CypherPoker game clients communicate.
To keep the game moving along at a good pace actions are communicated between game clients using a peer-to-peer communication channel while being posted independently to the blockchain in the background using the Ethereum client. At least this is the present setup; State Channels (see below) will probably make much of this obsolete but even then we might want to send keep-alive messages to the blockchain to prevent timeouts.
This direct peer-to-peer channel could be RTMFP (as currently used), Tor, XMPP/Jabber, Whisper, or any other method of (relatively) fast communication; the ultimate implementation isn’t really that important.
Because of the delays of getting actions stored on the blockchain the game client has to hold back or defer posting dependent actions until previous actions have been verified to exist – the claimed state of the contract must first be verified or guaranteed somehow.
For example, my game client may communicate to your client directly that I’ve bet 1 Ether while in reality I’ve committed only 0.5 Ether. If both bet values are valid in the context of the current game you may proceed by matching my apparent 1 Ether bet and posting it to the blockchain only to later discover that I’d bet just 0.5 Ether.
This may not seem terribly drastic but it’s still not something we want and there are other points in the game where the repercussions could be more dire.
In order to address this what we want is to hold back your 1 Ether bet until mine can be verified, and this is what is meant by deferring an action until a certain contract state (in this case my bet amount), can be verified. This mechanism works together with State Channels as a backup verification method when direct communication fails.
Channel Your Inner State
A while ago it was suggested to me on the CypherPoker Slack that I should consider using something like State Channels for CypherPoker. If you don’t know what those are, you’re not alone — I had only a vague idea of how they worked and even less about how to implement them. Besides, I wasn’t sure they were necessary so I put the idea aside and pressed on.
At the time I was mulling rewinding actions in the game to the last verified contract state but the more I thought about it the more it looked like it would be a bitch to implement; I’d have to figure out a way to store, and restore, arbitrary states in the game client. Even then it wouldn’t make for a good experience as the client might suddenly jump backwards to an earlier point in the game if the other player failed to record their claimed action to the contract.
And there was an even bigger problem: what if the game had come to an end on the client and its first steps were still being recorded on the blockchain — a practical certainty if we want games to play quickly? If a player had lost they could simply inject a “fold” action into the contract interactions when their turn came around even if they had actually bet at that point. From the contract’s point of view everything would look kosher — it was that player’s turn to record a bet or fold action and they folded; what proof would I have that they didn’t?
I came up with some convoluted solutions involving commutative crypto in my head but I couldn’t quite make the pieces fit. One night I ended up staring at the bedroom ceiling until about 3 a.m. filled with dread about not being able to fill this gaping hole. What the hell, I thought; let’s have a gander at this State Channel business and see if I can extract some ideas from it.
By four o’clock I was buzzing with excitement — not only would State Channels be the solution, they would help to solve a bunch of other problems too.
I read lots of explanations about State Channels that morning and most of them seemed intent on confusing the reader. It was the implementation details that really threw the doors of understanding open and I quickly realized that a State Channel is really nothing more than a series of provably authorized actions or authenticated promissory notes. There are variants that require superseding messages and multi-party agreements but these tend to muddy the waters.
When I place a bet I create a message that I sign with my private key, which is directly linked to my account. I can send that message directly to you and you can verify it using the public half of my key, a verification that proves that I did indeed create that message. The smart contract also has this capability so if there’s some dispute I can simply submit the signed message you sent me and the contract will understand that you authorized a specific bet – there’s no way for you to back out.
Now every time a player bets they create a message like “BET:100” (the actual message is pretty similar), hash the message in order to create properly-sized data for the signing function, and sign it with their private key. They then send the original message, hash, and signature to their opponent(s) who can instantly verify that the message produces the hash and that the hash was signed by the correct player. All of this is done without involving the smart contract.
I now hold irrevocable proof that the player has pledged a 100 bet and because the smart contract has the same capability to verify the signer as I do there’s no way for the player to claim that they didn’t make the bet, even if they somehow manage to sneak in an out-of-order “fold”.
That got me to thinking: if this works for bets, why couldn’t it work for just about every contract action? Yes, there does need to be some initial contract set up but most of the game can happen off the blockchain. This can easily add up to huge cost saving.
Consider the following approximate costs for a full-blown, newly-deployed, on-the-blockchain game:
PokerHand contract deployment (Dealer) -> 3700000 gas (C$1.03, US$0.77)
Validator contract deployment (anyone) -> 2100000 gas (C$0.58, US$0.44)
Contract initialization (Dealer) -> 190000 gas (C$0.05, US$0.04)
Contract agreement (per player) -> 101000 to 120000 gas (C$0.03, US$0.02 to C$0.03, US$0.03)
Encrypted deck storage (per player) -> 1430000 gas (C$0.40, US$0.30)
Private card selections storage (per player) -> 79000 gas (C$0.02, US$0.02)
Private card decryptions storage (per player) -> 140000 gas (C$0.04, US$0.03)
Bet storage (per player) -> 93000 gas (C$0.03, US$0.02)
Public flop cards selections storage (Dealer) -> 114000 gas (C$0.03, US$0.02)
Public flop cards decryption storage (per player) -> 119000 gas (C$0.03, US$0.02)
Public turn card selection storage (Dealer) -> 66000 gas (C$0.02, US$0.01)
Public turn cards decryption storage (per player) -> 73000 gas (C$0.02, US$0.02)
Public river card selection storage (Dealer) -> 64000 gas (C$0.02, US$0.01)
Public river cards decryption storage (per player) -> 71000 gas (C$0.02, US$0.01)
Winner declaration (winning player) -> 60000 gas (C$0.02, US$0.01)
Level 1 validation (per player) -> 845000 gas (C$0.23, US$0.18)
Level 2 validation, indexes 0 to 4 (per index, per player) -> 360000 to 435000 gas (C$0.10, US$0.08 to C$0.12, US$0.09)
Level 2 validation, indexes 5 to 9 (per index, per player) -> 172000 to 2700000 gas (C$0.05, US$0.04 to C$0.75, US$0.57)
Level 2 validation hand scoring (per player) -> 1500000 to 4000000 gas (C$0.42, US$0.32 to C$1.11, US$0.84)
Winner resolution (winning player) -> 100000 to 300000 gas (C$0.03, US$0.02 to C$0.08, US$0.06)
In some scenarios spending roughly C$8.50 (US$6.40) as the dealer and C$6.70 (US$5.10) as the player on a single hand of poker may be acceptable but being the poor miser that I am I’m not impressed. Even if I got some of the calculations wrong, and my late-night brain probably did, the numbers are still not great.
With State Channels and contract re-use (as opposed to deploying a new contract each time), it should be possible to whittle the cost down to a few pennies, perhaps less. Most of this is implemented and ready for version 2.0 so the numbers listed above are the nightmarish worst case scenario.
It’s worth pointing out that the costs of storage in re-used contracts, when implemented correctly, are cut significantly. For example, the cheapest single-card, first-time storage above runs at around 64000 gas (C$0.02, US$0.01) but a re-used contract requires only about 28000 gas for the same storage slot or CAD$0.008 (US$0.006). If no one is offering free contracts for re-use, rental contracts that charge a nominal fee would be a far better option than deploying one’s own, especially if such contracts have some advanced and attractive features.
Flow My Cheers, the Player Said
You may be wondering about some of the items preceding the gas costs/prices in the section above. What exactly is a “Level 1 validation”? How is a winner both declared and resolved? What’s up with the Validator contract?
Let’s walk through the flow of a complete hand for the deets.
When the game first starts it may or may not engage the Rochambeau protocol, a fancy name for what is essentially an electronic version of rock-paper-scissors that determines who the initial dealer will be. The dealer then either deploys or selects a new PokerHand smart contract which, as the name implies, is intended to cover a single hand of a game.
The dealer then initializes the contract with a few values: the players involved (in betting order), the prime number value that becomes the basis for all other cryptographic values, the base or lowest plaintext card value which should be a quadratic residue modulo the supplied prime (more on that here), the required buy-in value (in wei) for all players, the block delta timeout value or number of blocks that must elapse without any activity for the contract to time out, and an address for the Validator contract.
With the latest update I’ve pruned the number of contracts down to just two: PokerHandBI (the full name of the “Buy-In” contract), and the Validator. The PokerHand contract is responsible for ensuring that the correct game flow is maintained (bets are in order, cards are stored in sequence, etc.), while the Validator has all the functionality for decrypting, organizing, evaluating, and scoring the results. The Validator is designed to be used simultaneously by multiple PokerHand contracts through one-shot interactions while storing the results in the calling PokerHand contracts. In this way a single Validator can service multiple PokerHands but those contracts are not coupled to the Validator if a new and better one becomes available.
Once the PokerHand contract has been initialized all the players may examine it and if everything’s in order they will agree to the contract and simultaneously send the required buy-in; failure to do so is a lack of agreement and non-agreed-to contracts may be cancelled, refunding all Ether submitted. The buy-in is stored in a playerChips variable per player and deducted from whenever a player makes a bet or is penalized.
At this point the block timeout timer begins. Ethereum smart contracts have the ability to also use timestamp offsets (hours, minutes, etc.), but because blocks are generated at irregular intervals it’s better to use the number of elapsed blocks instead. Recall that each block is roughly equivalent to 12 seconds and the default timeout is 12 blocks — about 144 seconds or 2.4 minutes. If a player fails to interact with the smart contract within this period they are considered to be timed out and become eligible to lose all of their playerChips. This behaviour will almost certainly be updated once full State Channel support is implemented but this is how it works in the current version.
All the players now take turns encrypting the deck in sequence and storing the results in the smart contract. Once the fully-encrypted deck is stored players take turns picking two cards for themselves and storing the encrypted values in the contract. The partial decryptions of those cards by other players are also stored in the contract so that there is a traceable record should any players provide incorrect or false values.
Currently, players receive signed messages of the above interactions from other players that are verified upon receipt. If the verifications fail or there is simply no communication then the game freezes until the smart contract has caught up to the current state and the contract’s committed values are read and used instead. If something is still amiss at this point (for example, private cards don’t correctly decrypt), players may issue a challenge which requires everyone to submit their keys to determine who’s mucking up the works. The offending player loses their playerChips which are distributed to the remaining players, and the hand is closed and reset. If nothing appears wrong then the challenging player loses all of their playerChips. This prevents issuing challenges just to get out of a bad hand.
With signed messages this process can be sped up somewhat as players can provide the false/incorrect values without depending on the offending player to respond. While on the topic I should point out that I’ve been experimenting with a zero-knowledge proof that provides a way to verify that cards were correctly encrypted or decrypted immediately on receipt but this functionality won’t be in v2.0
With private cards selected and decrypted players enter into a round of betting. In the current version each bet is stored in the contract and a signed betting message is sent to all the other players. As with card encryption/selection/decryption rounds, a failure to verify a signed betting message will cause the game to pause while the game is actually committed to the contract, otherwise the game continues while actions are posted in the background.
Next the dealer selects three cards for the flop which are stored in the contract and accompanied by signed messages to the players. As each player takes turns decrypting the public/community cards they also store their results to the contract and send signed messages to their fellow players.
Another betting round follows, then another public/community card selection and decryption round, followed by another round of betting, another selection and decryption round, and a final betting round.
During any round of betting a player may fold which causes them to be removed from the betting order. Their remaining playerChips are refunded to them at the end of the game unless they’ve been introducing false/incorrect data at which point they lose everything.
Although I’ve been coding everything to support more than 2 players, CypherPoker will initially support only heads-up play. I believe that State Channels will solve the problems of players abandoning the game and failing to validate the game results so I’m optimistic that 2+ player support will be available shortly after version 2.0 but for now it’s one step at a time.
Now that a game is complete each player broadcasts their decryption and decryption keys to all other players who run a gamut of cryptographic verifications* to ensure that all values were properly generated and that the results are correct.
While this is happening the winner declares themselves to the contract. If no one raises an objection the contract is allowed to timeout and the winner calls the contract one last time to resolve the game. The pot plus the winner’s remaining playerChips are sent to the winner while the other player’s remaining playerChips are refunded to them. In future updates this behaviour may be modified to retain players’ chips for a new hand.
If a problem is suspected between winner declaration and resolution other players may issue a challenge by starting a Level 1 validation. In this step each player submits their encryption and decryption keys plus their 5 best cards – the combination of their private/hole and public/community cards that produces the best hand. This gives players the opportunity to double-check the entire game using values that have now been committed to the contract.
If the Level 1 challenge reveals something incorrect then players may start a Level 2 challenge. To begin this challenge each player is required to put up the funds necessary to cover the costs of the entire Level 2 challenge for each player. Using the numbers from the previous section, each player is required to add 0.567 Ether (CAD$6.29, US$4.76) per player to the contract. In this way if the initiating player is issuing a challenge just for the heck of it these funds will cover the validation costs of the other players but if something is actually found to be wrong then the offending players’ funds will be used to cover the initiating player’s validation costs.
Either way, each player must now go through the Level 2 validation process which involves repeatedly calling a high-gas function in the smart contract. This function will initially decrypt the player’s best hand (supplied during Level 1), then convert the decrypted values to [index, suit, value] tuples unless the decrypted cards fall outside of the range of the plaintext deck, a validation failure. The decryption operations are fairly pricey since they require multiple rounds of modular exponentiation with multiple keys from multiple players, and conversion operations are similarly expensive since the “index” value is determined by calculating the card’s quadratic residue offset from the initial base card value (as supplied by the dealer during initialization).
After ten Level 2 “pumps” the cards are in their final, fully-decrypted state and should match the players’ own decryptions when they performed an end-game verification. One more call to the Level 2 validation function causes an analysis to be performed on the five cards and a score is produced for the hand.
The scores produced fall into the following ranges:
800000000+ = Straight Flush / Royal Flush
700000000 to 799999999 = Four of a Kind
600000000 to 699999999 = Full House
500000000 to 599999999 = Flush
400000000 to 499999999 = Straight
300000000 to 399999999 = Three of a Kind
200000000 to 299999999 = Two Pairs
100000000 to 199999999 = One Pair
0 to 99999999 = High Card
The ranges in these values accommodate sub-rankings. For example, three fours beat three threes even though they’re both three of a kind.
With no further actions possible the contract will time out at which point the winner resolves the hand. Obviously the player with the highest hand score is considered the winner but in the rare case when exactly the same score is generated for more than one player the pot is split evenly.
At each point during Level 2 validation an index value is incremented when a step has been successfully completed. Even if Level 2 validation hasn’t been successfully completed a player will be resolved as the winner if they have the highest validation index and the contract has timed out. If all players are at the same validation index without a hand score then the declared winner will become the winner. A declared winner will always exist at this point since validation can’t start until one is declared.
Generally speaking, players will lose all of their playerChips if they fail to complete a required action or fail to achieve the same validation index as other players. For this reason players will always need to keep extra Ether (or Bitcoin) on hand. Players who successfully complete validation will receive a refund of their validation deposit plus validation costs which are covered by the initiating player (since validation wasn’t necessary).
Some of these particulars may change once State Channels are fully implemented and there are still details to be worked out for 2+ player games, such as how validation deposits are handled with multiple failures, but this is a good foundation with an easy-to-update implementation.
* While functionally similar, verifications happen in the game client while validations happen in the smart contract.
BigInt in the Rearview
I’ve now had a chance to more thoroughly run the numbers on the multi-round encryption changes I made in update 1 and I’m putting the Ethereum (Solidity) arbitrary-length integer library on semi-permanent hiatus because I’m now much more confident that I can achieve equivalent security using Ethereum’s native mulmod function.
As I’ve explained in a previous post, CypherPoker’s security is based on the difficulty of calculating very large numbers. To be safe I’m assuming that we’ll need to use numbers that are larger than 256 bits which are the largest numbers that Ethereum supports.
However, we don’t really need every number in the equation to be very large, just the exponent or “K” value in: (mK) mod P
Performing this calculation multiple times with different “K” values is equivalent to performing the calculation once with a really large “K” value. For example, if we assume that the largest value we can use for “m”, “K”, or “P” is 107 it would initially seem that we can achieve just under 7 bit security.
However, if we apply the calculation multiple times with different values for “K” – the encryption/decryption key and only non-public value – we can produce the same result as if we had multiplied the three “K” values.
If we let:
K1 = 3
K2 = 25
K3 = 73
… we should produce an encryption that’s equivalent to using a single composite key:
K1 x K2 x K3 = 3 x 25 x 73 = 5475
If we use a value such as 6 for “m” we get:
(65475) mod 107 = 22
…which is the same as:
((63 mod 107)25 mod 107)73 mod 107
= (225 mod 107)73 mod 107
= 8873 mod 107
This effectively means that by performing multiple sequential calculations we’re increasing the encryption strength by a factor of “P” on each round. In other words, if our single-encryption security in the above example is 6 bits then by using three keys we’re getting 6 x 3 = 18 bits of security.
What’s nice is that we can keep increasing the number of keys/operations arbitrarily and because we don’t need to reveal our private information (keys) until the end of the game each player can use their own arbitrary security settings. These are done in multiples of 240 bits or 30 CBL in order to prevent overflows should any value near its maximum due to the way that modular exponentiation is calculated in the smart contract. I have a potential fix that covers the entire 256-bit range but I’ll save that for a near-future release.
I’ve set up a mirror of this blog over at Medium because stuff happens and I don’t particularly care how my content is shared as long as it gets to the fine people who read it. The Medium content is a verbatim copy of what you see here but only covers CypherPoker topics.
In addition to what I’ve mentioned here there are lots of changes to the CypherPoker source code which I’ll be cleaning up and submitting to the GitHub repository over the next few days.
I know better than to make promises about when v2.0 will be ready but with the smart contract work the heavy lifting is done. User interface development is something I have much more experience with and I already have a good head start. Also, I shouldn’t need to do a lot of sitting and waiting around for blockchain state updates so that should help speed things along.
But just between you and me, I’d love to have CypherPoker v2.0 ready before the end of the year and I’ll be working hard to make that happen.
Also published on Medium.