How to Use Bitcoin to Play Decentralized Poker

Ranjit Kumaresan from MIT gave a talk about his recent CCS paper, “How to Use Bitcoin to Play Decentralized Poker.” It is an interesting piece of work, and I will provide a summary of the talk here. The paper has many technical details that I will omit for purposes of space. If you’re interested in learning more about the technical details, you can find the paper here.

The setting is that Alice and Bob want to play poker over the Internet. However, the main question is who will deal? In regular poker, there is a trusted casino dealer, but over the internet, who will be this dealer? Another setting is that Charlie and Diana want to participate in a sealed-bid auction. The loser shouldn’t reveal value of bid, and they don’t trust each other. These two settings seem to be a special case of joint computation. More concretely, each side has a part of the input, but the input must be kept secret.

The easy solution is to have a trusted third party. However, these trusted third parties on the Internet are not readily available. Cryptography can help solve this problem using secure computation (MPC). Computation without a trusted third party has been a hot research topic for the past 30 years. It works for any function and multiple parties, and it has become increasingly efficient.

Back to the original problem of the poker game. MPC is all about information. The question is how do you enforce payment in the poker game. More specifically, how do you convert information into money and vice versa? To solve this, they use Bitcoin. A Bitcoin is a special string and so is a transaction. Coins can be used as input for computation, and transactions can be computed securely.

Are we done yet? No. There’s a catch. MPC accomplishes these tasks without a trusted third party, but there’s a fairness issue. MPC’s guarantee is that either everyone gets the output, or no one does. However, fair computation is impossible. We can only achieve security with an abort. Any party can decide to abort, and the aborting party can get output first. No one else will get the output. This is clearly unfair.

Why is fairness important? Alice and Bob want to participate in a lottery where the winner receives all the money. However, the aborting attack will make it such that Alice learns the output first. If she lost, she can abort, and Bob will never get his money!

We need to change the model because there is no secure lottery in the standard model. They again use Bitcoin and the power of Bitcoin transactions. They don’t want to just transfer coin x to party y. They want to support complex scripts, such as “give coin x to party y if y publishes a secret z by date d.” Once published, the transaction is irrevocable. The owner of x can’t take it back before date d.

We still can’t get fair computation, but we can get something close: secure computation with penalties. Either you get your output, or you get cash. Alice can still abort, but then she has to pay Bob compensation. The amount of compensation is a parameter, which should be more than the bet.

Again, we’re not done because MPC with penalties is a one-shot game. Poker is a reactive game. There are multiple rounds, and it cannot be compressed into a one-shot computation. General transformation from one-shot to reactive exists by secret sharing intermediate secret state. This works from the “security with abort” notion but it’s not enough for “get your output or compensation” notion because you have to deal with aborts between rounds.

Their work is secure cash distribution. The reactive version of MPC with compensation. They use the special properties of the MPC protocol. The MPC protocol runs in rounds, and one player broadcasts in each round. The intuition is that they force players to continue computation. The current player is “in debt” until she publishes valid next message for MPC. The next message is used to claim compensation. The last player must publish valid output. If you’re interested in the details of the protocol, I refer you to the paper.

This is some interesting work as it leverages a decentralized log like Bitcoin to act as a trusted party of sorts without centralizing the trust. It is an interesting step toward decentralizing trust in many protocols.