I've given some thought to this and this whole thing starts to get complicated, but it seems to be possible.
(I've now added some
clarifications)
ColludingAs for the problem of colluding, it is not inherently a problem of distributed poker, it is a generic problem of all forms of online poker. And Bitpoker could deal with it the same way the centralized websites do: keeping track of how often players play with each other on the same table. (More specifically, it should probably keep track of the number of hands each user has played with other users on the same table.) This works fine if the number of players will be big enough.
There is one problem though: centralized poker platforms can enforce only one/few accounts per actual user, by requiring a real-world credit card, name, etc. This is obviously not the case with Bitpoker, if it will be anonymous in nature, there should be nothing stopping anyone from creating as many accounts as they want...
Right now I only see one way to do this and still keep everything anonymous: use the economy. It should be economically non-viable for players to create multiple accounts.
Maybe some will consider this "less" anonymous than having hundreds of accounts, or even having a new account for each table, but still, it seems anonymous enough. (A drawback of this is that unfortunately, this would make it easier to analyze each player, i.e., it would be difficult for good players for example to hide the fact that they are good, since all the history is stored in the network.)
A practical thought about how this could be done: to have a fee which will be high in the beginning of the career of each account, and will gradually get smaller and smaller, the more games the player participates in. This, together with some clever randomization of tables that someone else suggested here (for example the system could let each player choose a table only from a very small fraction of existing tables, and only change which tables are "allowed" once a day or so. This way it would still be possible to have some choice, or get to another table if the existing one has a crazy player, or for some other reason...) should be enough to keep collusion to tolerable levels.
That said, there should probably be a mode of "private tables", so that users that know each other could join the same table, but that is a secondary problem. (Also in that case, there will be no collusion as players already trust each other.)
Now, about who is keeping the money.When you first think of this, when several inherently hostile players play the same game, there will have to be a third party that will be handling the money, and it will also have to be trusted, because otherwise it could be suspected of colluding with some players, since they all are anonymous.
Except... this problem also comes to mind when you think of normal money, and until bitcoin came, it was the case, but not anymore...
Before in this topic, we were thinking about how to implement this *using* existing bitcoin network, how to have an account in bitcoins and manage funds on it.
But what if... we would implement another blockchain, a dedicated chain for the bitpoker chips?!
In this chain, let's say that along with "normal" addresses, there would be "hand" or "table" addresses, to which all the money is transferred as a hand progresses. And if we could incorporate secure shuffling of the cards into the chain, we could design the network in such way that funds on those "hand" accounts could only be claimed by the winning player, similar to a very complicated transaction script.
(This is way too complicated to implement using the current script system of course, so my idea is not to simply start a new chain and use clever scripts, but instead to design a whole new client and protocol.)(This needs more designing, because there basically must be 3 accounts per player and table, 1 main address, where the player has all his money away from any tables, 1 account of money on that table, and another 1 account of money currently in the pot, and all of those must be managed by the block chain in a verifiable manner.)Now, as for how to actually deal with the shuffling of cards, this is where I haven't thought it out completely, I see two ways:
1) still use the commutative-encryption approach described in the
wikipedia article. Before the hand is started, the shuffled and encrypted deck (or probably it's hash) is publicized in the block chain. Also, some kind of "proof-of-having-a-key" is publicized in the block chain, *for each player*. This can be for example arbitrary known value encrypted with the player's key, so that if you would have the key, you could do the same thing and state that yes, indeed, that is right key for that player. (this will make sense in a moment.)
As the hand progresses, cards are decrypted as required, by passing them around the players. The order of each player's actions is also recorded in the block chain as the hand progresses (let's just say for now there is a reliably way to do this, there is more about this at the end of the post). Finally, as the hand is completed and all cards must be shown to select a winner, the keys of all parties are made public in the block chain. Notice that now, using only information stored in the block chain (the initial deck, ordered decisions of each player, all the keys to decrypt the deck) it is possible to exactly determine the winner. This will be done in the same way transactions are claimed right now in the mainline bitcoin network: collaboratively. You cannot cheat, because it is the network that decides which player has won the money from the hand address.
Like in bitcoin, there will be block confirmations, and to generate those, miners will check each win themselves. Think of it as a transaction with a very complicated script that needs a number of conditions to be met for someone to claim the money.
What if at the end of the hand a player has already received all the other keys, and can decrypt the cards, and sees that he has lost, but has not yet made his key available? He could in that case never make his key public, and there would not be any way to tell for sure who has won? This is where "proof-of-having-a-key" comes in. If the network sees that for a given hand, not all keys have been made public, using that proof, it can determine exactly, whose keys HAVE been made public, and thus prove which player did not provide his key. In that case, the money will go back to each individual player, except the one (or the several) that did not provide their keys. Their money is split evenly between the rest of the players, and, since we are making accounts persistent by having a fee anyway, we increase the fee of the player that did not make his key public. This should be enough to discourage anyone from doing this. (Loosing the money + getting higher fee and bad will + not really loosing anything more by just making the key public as the network wants.)
(Just a side note: since we are dealing with internet and disconnects here, there should be nothing in the design of the network to stop a player from making the key public in the last step of the hand even after a reconnect, as long as he did reconnect in the given time.)
2) instead of relying on commutative encryption, randomly choose another node from the network to act as a "hand seed" and "dealer" for each hand, and probably rewarding that player with a small percentage of the hand pot.
In the beginning of a hand, this dealer generates a random seed, a cryptographically long enough value that will be used as the seed for the random number generator for the shuffling, and makes a hash of that value publicly available in the network. As a hand progresses, player's decisions are broadcasted in the network, and when the time comes, the dealer broadcasts the cards only to those players that are supposed to see them. This is easily done by public key cryptography, i.e. the dealer encrypts the cards a player is supposed to see with that player's public key and broadcasts that into the network.
When the hand is done, the dealer broadcasts the initial seed value, which can be easily checked for validity, since it's hash was broadcasted already in the beginning of the hand.
The winner will only be able to claim the winning transaction if the hash corresponds to the seed, and if the order of players' actions given that seed (and the order of cards in the deck it implies) corresponds to the win of that player.
The dealer only gets his cut if the seed is actually made public in time, and if that seed actually corresponds to it's hash that was made public before.
The problem as I see it is this: is there a reliable enough way to make sure that none of the players can ever cooperate with or even "find" the dealer? Even if the dealer will be random each time, maybe evil-doers will create a botnet of theese dealers and get them together somehow and find a way of quickly finding and communicating with them as a player? (Thus always knowing other players' cards.) Don't know, this needs more thought.
Determining the order of the actions, There must be a certain way to do this, something to prevent player sending two different actions (fold or call at the same time).
This is very similar to "double spending" problem the bitcoin manages to fix by waiting for confirmations. But block confirmations would be way too slow to do this. I think Geist Geld alternative cryptocurrency has used block speed of 15 seconds, and it has sort of worked, however it is still a little too fast I think, and even if we used 15 seconds, it would still be too slow for poker, because every *action* of every player during a game would have to wait for such confirmations (multiple perhaps).
But! After some thought I don't think we need to use confirmations for those small player actions after all.
There is no valid reason for any honest player to ever broadcast two conflicting actions. By conflicting i mean, say a fold and a bet *at the same stage of the hand*. Of course there will be different actions during the hand, but those can be distinguished by some system of counting.
So, if the network would ever see two conflicting actions targeted to the same stage of the hand from the same player (and since each action will be signed by the private key, that will be easy to determine), it is certain that the player has tried to cheat. In that case the network could simply rollback the hand and punish the player using the mechanism I described before using the fee, reposessing his funds in the pot to the rest of the players (or perhaps even all the funds he had on that table). This way noone could ever win anything by cheating in this way.
The confirmations will probably be used only for transferring coins between accounts, or to/from a table/pot. Most importantly, to withdraw funds that have been "won" from a pot must require confirmations. But that does not have to be superfast, if someone was to wait a couple of minutes before being able to enter a table, or before withdrawing his winnings, that is still not too bad.
Now, as for this whole "another block chain thing"Given what I have described, this would require a lot of transactions, and thus bloating the block chain even more so than on the main bitcoin chain. Thus it seems to need a built-in clean-up mechanism. So each account in this chain would be much more short-lived. Each X number of blocks all blocks older than Y will be "truncated", forgotten. (Where Y>X.) Economically wise, a small gesell-like negative interest enforced each block seems viable (instead of randomly loosing the money that happened to be in truncated blocks).
This chain will have to be very fast, very liquid, and people will try to keep cashing out directly. It will not be used so much to store the money, but just for the games themselves. By using faster blocks, and not requiring block confirmations for every single thing that will happen in this network, we could very likely make this chain fast enough for real time poker, however that also could make it more susceptible to splitting and other forms of attacks. However I don't really consider real life splitting as an issue, because right now it would take not much less than a meteorite to reliably split a distributed network like this in two halves. It is much more difficult than to firewall some sites like China does, and i believe has not ever been done yet?
Anyway, it is also the fact that this chain will be that much faster and more liquid will also greately reduce the damage, if any kind of attack on it was successfully executed.
To actually transfer money to and from this new chain, some exchanges would have to be created. To use them, you could still remain anonymous, though.
