Bitcoin Forum
April 18, 2014, 04:19:22 PM *
News: Due to the OpenSSL heartbleed bug, changing your forum password is recommended.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Distributed/Decentralized Poker Proposal  (Read 727 times)
W-M
Member
**
Offline Offline

Activity: 112

In Crypto we Trust.


View Profile

Ignore
December 08, 2013, 09:54:42 PM
 #1

I recently read about people wanting to implement a decentralized poker system using bitcoin-esque techniques:

here and here.

However, these topics mostly talked about 'if' such an idea would be possible. I thought about it a little and came up with a concept that resolves most of their problems.

This is still a rough draft, and might contain some grammar mistakes (or even huge logical flaws) but I want to hear what you think about it, and how we might be able to resolve the few issues that are still left to solve.

Distributed/Decentralized Poker Proposal:

(Use Texas Hold'em rules for the basic implementation, since it is the most played variant of poker today.)

Requirements for a good working multi-table decentralized poker system with payments:
1.The basic game needs to be working decentralized:
   -Players sit down on table (possibly paying a small sum of money to get in the game: the blind)
   -Shuffling the deck
   -Giving each player 2 cards without the other players knowing them
   -Drawing and showing 3 public cards to everyone. (flop)
   -Betting opportunity.
   -Draw and show the 4th public card (turn)
   -Betting opportunity.
   -Draw and show the 5th public card (river)
   -Winner gets declared, gets all money bet.
   -Players leave the table.
2.Showing what tables are waiting for more players should work decentralized
3.Betting money (e.g. bitcoin) and receiving the earnings should be decentralized.
4.Prevent multi-account play (a person playing on multiple seats at a table at once), or at least make this difficult.


How can we do this?
A. Basic Poker:
 There is a great cryptographic method called 'Mental Poker' which enables a set of cards (or other set of values) to be shuffled by multiple people without using a trusted third-party.
   -Alice starts out with an unshuffled deck.
   -Alice picks an encryption key A, and encrypts all cards using that key.
   -Alice shuffles the deck.
   -Alice passes the shuffled deck to Bob.
   -Bob does not know what order the cards are in, since he doesn't know A (and thus doesn't know what values represent what cards in the new stack).
   -Bob picks an encryption key B, and encrypts all cards using that key.
   -Bob shuffles the deck.
   -Bob gives the deck back to Alice.
   -Alice now has no idea either about the values/positions of the cards.
   -Alice uses her key A to decrypt all cards. (though she still doesn't know the values since Bob's key B is still in place)
   -Alice encrypts all cards using a special key for each card.
   -Alice passes the deck to Bob.
   -Bob decrypts all cards. (though he still doesn't know the values since Alice's many keys are in place).
   -Bob encrypts all cards using a special key for each card.
   
The deck is now shuffled: All players can see the stack, but they do not know what value is what card, since all players hold a key needed to decrypt it.
If the protocol decides that a certain player should be able to see a certain card, all players give that player their keys for that card.
Now only this player has all keys needed to look at the card.

This can be used to implement most of the poker scheme.

B. The Blockchain:
To enable multiple games to be played at the same time, enable players to be able to look for games with open seats, to keep track of payments, and to increase trust in the system, a Blockchain is used.
Transactions in this Blockchain are events happening in a game:
   -Game created
   -Player joins/pays ante.
   -Cards shuffled & dealt.
   -Player bets on flop or folds.
   -Next payer bets on flop or folds.
   -Turn dealt.
   -Player bets on turn or folds.
   -Next player bets on turn or folds.
   -River dealt, rest of deck now opened to be visible for everyone. Winner gets declared, gets winnings.
   
These transactions all have:
   -An ID/address to identify the game they belong to.
   -A signature(public key) from all players (still) in the game.
   -A signature(public key) from the player signing the current transaction.
   
   Game joinging transactions have on top of this:
      -game-specific public key to be used when dealing cards to this player. (so only he can see the cards dealt to him).
   
   Betting transactions have on top of this:
      -Bitcoin address to send data to
      -Transaction ID from the action to cross-reference with the bitcoin-blockchain.
   
   Shuffling transactions have on top of this:
      -A sequence of values representing the shuffled deck.
      
   Card-dealing transactions have on top of this:
      -The position of the card to be dealt.
      -The key used by the player to encrypt the card at this position, encrypted with the recieving player's (game-specific) public key (so only he can read it).


-Betting and Shuffling transactions are only made by the player doing the action. The other players can confirm these transactions, as can the rest of the network.
-Card-dealing transactions are made by all players simultaneously. They should be only confirmed(put in a block) by the network after a copy of this transaction with each of the player's signatures is found.   

Propagation time should be fast. As clients will primarily talk with eachother using the blockchain, new transactions should known throughout the whole network within a minute.

As the blockchain will quickly grow in size, and as games are mostly unrelated, most home clients won't need to store the whole history of it, if they don't want to.
However, some larger nodes should keep it whole. This way, players can cross-reference other players to see how they played before. (see Trust).


3. Trust
By using a Blockchain where all events from all games will be stored, it is possible to check what games a player played before.
This way, a player can decide whether he wants to join a table, considering for instance:
-How many games did a player play before? (if none, this is a new account, thus low trust: do not bet high.)
-How often did the players at the current table play together before?
-How much did these players bet in the past?

Someone doing multi-account play will play many games with the same players (his puppets).
To prevent this from being visible, he will create new accounts regularly.
However, if checking how many games an account has played is also possible, one can take precautions against these kinds of players, by for instance only betting low when around new players.

4. Issues
This system still has issues that need to be resolved:
-What might be the incentive of mining, of keeping the Blockchain secure and up-to-date?
-Bitcoin might be too slow for bets. We might need to use another (dedicated or not?) coin and exchange these for bitcoins like pokerchips get exchanged in a casino.
-Payment. We could implement M-of-N addresses so players get access to the funds when all(or a specified part of) the players agree to give them the money. Of course, when players disconnect from the game while it is being played, nobody will be able to get to the jackpot.


To ensure that you know that I really wrote this, this message is signed using my donation bitcoin address (1Cg76Ft1Juhorwxs1HV8ER7D3rpvPpq9yF).
(this is v. 1.0 of this message)

1397837962
Hero Member
*
Offline Offline

Posts: 1397837962

View Profile Personal Message (Offline)

Ignore
1397837962
Reply with quote  #2

1397837962
Report to moderator
GAWMiners.com
ASIC Scrypt Miners
Guaranteed Satisfaction + Same-Day Shipping For FREE!
Simply Enter "freeshipping" at checkout

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1397837962
Hero Member
*
Offline Offline

Posts: 1397837962

View Profile Personal Message (Offline)

Ignore
1397837962
Reply with quote  #2

1397837962
Report to moderator
1397837962
Hero Member
*
Offline Offline

Posts: 1397837962

View Profile Personal Message (Offline)

Ignore
1397837962
Reply with quote  #2

1397837962
Report to moderator
1397837962
Hero Member
*
Offline Offline

Posts: 1397837962

View Profile Personal Message (Offline)

Ignore
1397837962
Reply with quote  #2

1397837962
Report to moderator
1397837962
Hero Member
*
Offline Offline

Posts: 1397837962

View Profile Personal Message (Offline)

Ignore
1397837962
Reply with quote  #2

1397837962
Report to moderator
W-M
Member
**
Offline Offline

Activity: 112

In Crypto we Trust.


View Profile

Ignore
December 08, 2013, 09:55:44 PM
 #2

Signature from the first post(v1.0): IFdHS27k/jllnXsTUXPoaPhduavdXSpReRot0TtchKy/cvqLjpRvjU8679OBpa8WcpoGUTHsx1zUX6I3DRX3PRA=

Natanael
Newbie
*
Offline Offline

Activity: 25


View Profile WWW

Ignore
December 09, 2013, 10:03:52 AM
 #3

The generic term is Secure Multiparty Computation (usually abbrevated as MPC). I've been thinking of doing all kinds of round-based games this way together with Bitcoin and optionally with anonymizing networks like I2P. All kinds of cools things could be done this way, including reputation tracking and setting up tournaments. If done right it could practically be cheat proof. (It would however be harder to verify that somebody with 1000 wins haven't been playing against his own 1000 fake accounts.)

My bitcoin addresses: 19e75K6cWAFDNeNRg7hmsbaFtsS2WtVcvq
greBit
Full Member
***
Offline Offline

Activity: 234


View Profile

Ignore
December 09, 2013, 11:06:42 AM
 #4

You may already done so, but you should get in touch with Sergio Demian Lerner (@SDLerner) who has created a Mental Poker Framework (http://www.dc.uba.ar/inv/tesis/licenciatura/2010/lerner). He also has patents covering this.

It all looks very interesting but in order to do the shuffling etc it is still very performance intensive - i.e. minutes not seconds, but once a game has started the shuffling can be pre-computed for the next hand.

I'd love to see this implemented!

1WiLLByBzAWMwBdqGsWct3x8BBe2PB6ob
DMstore
Newbie
*
Offline Offline

Activity: 3


View Profile

Ignore
December 09, 2013, 06:29:40 PM
 #5

I like this idea.. any way to prevent collusion is what's going to take the cake
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!