I have declared failure in my attempt to create a truly distributed poker game. Many of the challenges I thought might be impossible were in fact solvable except one of the age old problems that even billion dollar casinos can not completely prevent: sharing knowledge of cards. However, collusion between players is particularly problematic in a distributed system as cheaters may be able to alter reality retrospectively. They are not just sharing knowledge of their cards, but information regarding their generation, like a trick dealer or cards up the sleeve.
A truly distributed system, by definition, has no trusted central server. In other words, there is no casino and the dealer is also a player, much like a game among friends. However, the rules of reality are also very different: the cards are not impermeable and we can not watch while they are shuffled.
My original solution, in a metaphorical sense, was to require each player to add his own spices to the shuffling soup (dining algorithms) and to keep note of his calculations and communication between other players (DHM). The calculations would be sealed in envelopes (SHA-1) and distributed to all the other players to be opened only at the end of the game (PK). This meant that any individual player could cheat, but that it would eventually be obvious to everyone. The problem is that collaborators could trade their secrets along with their calculations. I have not been able to work around that security attack.
But if we relax the distributed heuristic a bit and rely upon a trusted server to only generate a random ordered list of numbers and hold them in escrow we should be able to achieve all of our goals. And what are the goals? Allowing users to experiment with new games and interfaces; eliminating a single legally responsible entity, single point of failure, and middlemen with financial interests; keeping the interfaces simple and generic; and delegating the intelligence to the client application. Essentially the founding principals of the public internet.
So, we want an impartial third party to generate a shuffled set of cards and keeps them secret. We want players to publicly take cards off the stack without revealing the value. We also want to be able to take cards off the stack which are completely transparent (the act and the value). At the end of the game we would like to specify which cards should be revealed and which should not be revealed. All parties should be able to see the entire transaction history at any time. Finally, we should be able to lock out new transactions in order to give all parties the opportunity to verify the history while ensuring that no one is able to later peek at the folded or undealt cards. These requirements can be achieved with five interfaces. We would need to ensure that all transactions are secure, both authenticated and without eavesdroppers.
/**
* generateRandIntList
*
* creates a random ordered list of unique integers
* Specifying 0-51 could represent 52 shuffled cards
* the public_key_list is a set of public keys
* which limit and authenticate players
*/
generateRandIntList( min , max , public_key_list )
returns list_id
/**
* popIntFromList
*
* retrieve the next unique integer(s) from the
* ordered list. When is_locked is true, the
* result will not be available in the transaction
* history until it has been unlocked.
*/
popIntFromList( list_id , public_key , quantity , is_locked )
returns [ [ value , list_index ] ]
/**
* unlockIndexFromList
*
* makes a result visible in the transaction history.
*/
unlockIndexFromList( list_id , public_key , list_index )
returns success
/**
* closeList
*
* After calling closeList a list can never
* be reopened. A closed list will continue
* to display transaction history for a limited time,
* but integers can no longer be popped
* nor may indices be unlocked.
*/
closeList( list_id , public_key )
returns success
/**
* transactionHistory
*
* prints the entire transaction history
* including timestamps, requesting users,
* requests, arguments, and results.
* Locked results will be masked until unlocked.
*/
transactionHistory( list_id )
returns transaction_history
The above interfaces could be used for all card and dice games to which I am aware. Below is an example of what a transaction history might look like after the close of a single game of Texas Hold’em between three players:
2007-01-01 00:00:00
generateRandIntList( 0 , 51 , [ 23 , 45 , 67 ] )
-- comment card shuffle
returned 123
2007-01-01 00:00:02
popIntFromList( 123 , 23 , 2 , true )
-- comment player 23 dealt two hole cards
returned [ 49 , 0 ] , [ 48 , 1 ]
2007-01-01 00:00:03
popIntFromList( 123 , 45 , 2 , true )
-- comment player 45 dealt two hole cards
returned [ ?? , 2 ] , [ ?? , 3 ]
2007-01-01 00:00:04
popIntFromList( 123 , 67 , 2 , true )
-- comment player 67 dealt two hole cards
returned [ 32 , 4 ] , [ 31 , 5 ]
2007-01-01 00:01:00
popIntFromList( 123 , 23 , 1 , false )
-- comment player 23 requests the flop
returned [ 33 , 6 ]
2007-01-01 00:02:00
popIntFromList( 123 , 23 , 1 , false )
-- comment player 23 requests the turn
returned [ 51 , 7 ]
2007-01-01 00:03:00
popIntFromList( 123 , 23 , 1 , false )
-- comment player 23 requests the river
returned [ 50 , 8 ]
2007-01-01 00:04:00
unlockIndexFromList( 123 , 23 , [ 0 , 1 , 4 , 5 ] )
-- comment player 23 shows players 23 and 67
returned ok
2007-01-01 00:04:01
closeList( 123 , 23 )
-- comment player 23 collects the cards
returned ok
Truly secure interaction, and distributed systems in particular, rely on a web of trust. Have I played with this player before? Do people I trust also trust this player I’ve never played? Do people I do not trust seem to trust this player? What is the consensus of people I do not know?
Note, that I make no mention (until now) of exchanging value. With the intelligence at the edges (your machine), this system should work equally well with any type of card game, whether for imaginary points or real money. Money certainly adds complication and burden on the web of trust. While traditional money exchange would be possible, I envision transaction signed promissory notes producing a truly digital cash regime (whether it could be anonymous shall be left up to cryptographers).
