A Verifiably Fair Poker Game
With the advent of Ethereum smart-contracts, there has been a rush to create and publish “provably fair” gambling DApps, including provably fair poker. Reference for example, EtherRoll (http://etheroll.com/), Etherdice (https://etherdice.io/), EtherSlots (http://etherslots.win/), and Pokereum (http://www.pokereum.io/).
Uncle Finney’s Poker (UFP), the first game released by the E4ROW team, is a poker game — or more accurately a poker-inspired contest based on five-card stud, between two players. It is built as a hybrid of a centralized poker manager, controlled via a traditional back-end server, a decentralized front-end (which runs on smart-phones), and an Ethereum-contract which serves as an escrow service.
To assess the fairness of the game we need to define a few terms:
A “provably fair” game is one in which the source code of the game can be analyzed, and can be shown, via analysis of the algorithm, to be fair. Contrast this to a “verifiably fair” game is one in which practical tests which are performed after each game (or at least a random subset of games) that can show that any particular game, with respect to particular fairness measures, was indeed fair.
Both the E4ROW contract (which provides the escrow function for UFP), and the frontend smart-phone app, are both open source and available to the public for examination to ensure their fairness. The weakest link in the UFP design, from the perspective of provable fairness, is clearly the back-end server which manages the flow of the game. Since the code running on that back-end server is not available for analysis, it cannot be characterized as provably fair under the above definition. UFP does however provide substantial features to solidly classify it as verifiably fair. These are explained below.
The specific fairness measure that is addressed here regards the assurance that cards are dealt without bias. That is, the assurance that the back-end server is not “cherry-picking” better cards for one player over another. A related fairness concern (which we will also address), is the assurance that both players have access to cards of the same quality. That is, the assurance that the back-end server has not “stacked the deck” with higher value cards at the top, eg. to benefit the player that receives the first 5 cards. Of course there are other fairness concerns. One can argue that some of these are addressed by the design of a head-to-head game in which all the funds are processed by a third party escrow -effectively limiting the back-end server’s monetary incentive to cheat. But here we will limit ourselves to the aforementioned fairness measure(s).
To prove the fairness of a particular game one might simplistically be tempted to reveal all of the cards in the shuffled deck (after the end of the game). That is, the cards comprising the entire deck could be encrypted and sent to the players before the game. Then at the end of the game the keys to decrypt the deck would be provided. This simplistic approach is problematic however, because as any experienced poker player will tell you, hiding your discarded cards is an important part of poker strategy (this of course also applies to your initial hand when you fold). That is, it reveals too much about a player’s playing strategy to reveal their discards.
The solution to this problem is to only reveal the final cards that comprise the hand that a player would reveal anyhow in a “showdown”. While this approach of course reveals less about the entirety of the deck and the cards that were dealt, the approach is sufficient to show that A) the back-end server pre-allocated the cards, and B) dealt the pre-allocated cards fairly, without any modification to the pre-allocated order. By adding a provision to allow each player to “cut” the deck, and thus select the pre-allocated cards that will be dealt, it is also possible to show that no favoritism is shown to either player. That is, since the back-end server would not know, a-priori, which player will receive which cards, it is not practical for the server to “stack the deck.”
In a simple poker game the cards are shuffled, and then dealt in a specific order. The cards that any player receives consist of the original 5 cards that are dealt and replacement cards for up to 3 discards. In the end, the 5 cards that comprise the player’s hand are determined by the original shuffle, and by the discard selections.
In a traditional poker game the deck is shuffled once, and then all cards are dealt from the top of the deck, and so one may presume that player B’s replacement cards may be influenced by player A’s discard selections. However, this effect is purely illusory. To see this, simply imagine a game in which instead of preparing the deck ahead of the game, each card is randomly generated (of course ensuring that no cards are duplicated) before it is dealt. The illusion is that in the former case, we imagine that the cards were “pre-determined”, and so later cards are influenced by earlier card selections. In fact, probability theory tells us that in either case the cards were unknown and therefore in the second case any dealt card had the same probability of eg. being an ace, as in the first case: random is random is random. Thus, presuming that the deck is truly shuffled randomly, there is no compromise in “fairness” by for example, cutting the deck into multiple portions, or piles, and then using one portion of the deck to deal cards to player A, while using a different pile to deal to player B.
Using this technique, of “cutting the deck” it is possible to reduce the number of permutations of specific cards that any player will receive. Each player will receive 5 initial cards, and then replace either 0, 1, 2, or 3 cards, in any order. In each case the number of permutations in the player’s hand are:
We can supply each player with all 26 permutations of cards from each pile; and then allow each player to choose their pile; and then reveal the keys to allow each player to verify: a) their own initial cards, b) their final hand (which includes all their replacement cards), and c) the opposing players final hand.
Before the beginning of any game the back-end server shuffles a deck of cards and then creates at least three piles of 8 cards. Next the server creates strings representing 5 cards. The first string represents the original hand, which consists of the first 5 cards from the pile; subsequent strings represent the hand after one to three cards have been discarded and replaced. In general we can use a binary representation to indicate which cards have been replaced. In the table below, each digit represents a card position. A zero indicates that at card at that position is from the original deal; A one indicates that the card has been replaced. To make the description concrete, we will stipulate that the low (rightmost) bit represents card position zero, and that the high (leftmost) bit represents card position 4. Note that the table is 29 entries long, but only 26 entries are valid, because a player can only replace a maximum of 3 cards.
In order to ensure that the server and the front-end app agree on the ordering of the cards we can stipulate that replacement cards (the sixth, seventh, and eighth cards form the pile) are dealt in order to card positions starting from the lowest card position to the highest card position. The card positions have no significance in poker, but it will be important for the server and the front-end app to generate the same strings.
After receiving the encrypted arrays of card sequences, each player effectively “cuts the deck” by selecting their own array; that is, each player selects their pile of cards. As the game proceeds, after each player has selected the cards that they wish to have replaced, both the server and the front end app can create the correct index into the array of encrypted strings. At the end of the game the server sends to each player:
- The key that correspond to the player’s original 5 cards (key 0) within the selected array;
- The key that corresponds to the player’s final hand, also within the player’s selected array; and
- The key that corresponds to the opposing player’s final hand, from the opposing player’s selected array.
Each player uses the supplied keys to decrypt the strings at the computed indices of the appropriate array’s, and thereby verifies that the cards were delivered fairly. The above protocols can be utilized in future games developed by the E4ROW team to ensure verifiable fairness, while reaping the benefits of a hybrid system.