Topic: Proof of Knowledge without Trusting? (Read 2629 times)

And about open games, as I said, you could put some reward for playing a open game.
One example of reward is that the players play for free, the house does not take any percentage of the prize pot, while at secret tables, theres a 5% house edge on the prize pot.

Then serious poker players who are playing for recreatenational purposes, will play at open tables because it has so good rewards, while they will play at secret tables when they play "serious".
You need of thinking of a reward that will outweight the "cost" for a professional player to play at a open table instead of a secret table.

Also make it possible to play entirely for free and for fun, with chips that are not real Money. Free games are required to be open.
So Three table types can be used which is selected when CREATING a table (if you join a table, then you play at the creators type):

Paid open game - you get 100% prize pot. Game is played with real Money.
Paid secret game - you get 95% prize pot. Game is played with real Money.
Free open game - you win only "fake" Money. Game is played with "fake" Money.



Think of bitcoin. Bitcoin rewards miners because miners help to detect cheating (doublespending).
You game can be: Poker rewards open players because open players help to detect cheating (stuffed decks, decks not followed etc).

@gmaxwell, I like the multiple deck idea, but the compression of secrets from 65536 to 16 is something I'm having difficulty understanding.

Would not just two (2) decks suffice? For every hand, there is a 50% chance of detecting a cheat deck. Half the time, if there was a cheat, it will be discovered. Over tens or hundreds or thousands of games, any operator implementing this 2 deck system would be forced to use normal, standard, fairly shuffled decks or risk discovery and ruin.

That saves all the computing power and all the bandwidth and you can still retain 2 completely different and unrelated or unassociated deck secrets. They can be random.

@sebastian, while the idea has some merit, for a poker game I will probably not implement an "open" table. No one is going to sit down on that table. Newbies, maybe, but not the poker players I want to attract.

That can be a good idea.

Either a "secret" table, where theres only a small gurantee against rigging and fake decks (see verification protocol later), the player has to simply trust you, or a "open" table, that after end of game, are revealed to prove that they got a fair deck.
Of course, both tables could use same deck library, just that a deck used in a secret game will not be revealed, never ever.

You publish deck hashes prior to each day.
Deck selection can be based on player's bitcoin adresses, so all bitcoin adresses together, hashed, and then the unused deck hash closest to this hash, rounded upwards, is used, and then marked as secret forever if used in a secret game. If the hash is latest, simply use the deck prior to this, and if hash is first, use the deck after this.
Publish the deck selection protocol. Then the players can verify easly that you didn't give open gamers nonrigged decks and secret gamers rigged decks.

That means, you as house, cannot know which deck are gonna being used in secret and open games, and the player can easly verify that they got the intended deck.


thus those playing open games, automatically, by verifying the decks after a completed and revealed games, automatically assure secret games, because if you would stuff in a rigged deck, you risk that the rigged deck is being used in a open game. Also the public can then verify open games.

Players can also verify that you don't mark decks secret if they don't have been used in a secret game, because, lets say theres is 100 decks in library, and there is 60 secret games played and 40 open. If more than 60 decks are kept hidden, players know theres something fishy going. And those played a open game and didn't get the deck revealed know that you are cheating, because the game was supposed to be open.

To get players to the open tables, you could give the player a reward for playing open games which can be verifyed. The reward can be that theres no house edge on the prize pot, essentially, they play "for free", eg if 10 players bet 1BTC each, the Winner will get 10BTC.




I calculated, if a player are going to "crack" a deck hash by putting all possible deck permutations through it. Cracking a deck has is equvalient to:
52! (52 * 51 * 50 * 49 * 48 * .... * 2 * 1) = 8,0658175170943878571660636856404e+67 combinations
ln(8,0658175170943878571660636856404e+67) / ln(2) = 225,58100312370276194634244437667 bits equvalience

In other Words, cracking a deck hash by bruteforcing all deck permutations, is equvalient to cracking a 225 bit encryption key or hash.


So its safe to publish deck hashes of secret games. Nobody is gonna crack it for the forseeable future.


Selecting open/secret table can be done at table Creation. So theres Always one empty table, all empty table after this are deleted.
The first person who joins the empty table gets to select if the table should be open or secret.
Then a new empty table is created. In other Words, clicking a empty table means "create a new game" in other Words.

sebastian, that is an interesting idea. Maybe I can set up a separate table for that. Players must know which tables reveal the decks, and which tables keep their secrets forever.

We will then see for sure, where players will go to.

However, I am almost sure that people who bet real money, or in this case, real bitcoins, will prefer the forever secret tables, regardless of anonymity.

Thats one reason no poker site in existence today reveals or makes public logs of games. You simply will not attract the players if they know you will show their cards to the world. Even if its much later, like a day later or even a week later.

Its different when its a televised game of the world series of poker and there are hole cameras so the audience can see all the cards. Those players have contracts, so it could be a part of that. But in the games leading up to that tournament, they keep their strategies secret.

Why not?
I mean players who bet real Money, why would they not accept that the game is revealed at the end of the game?

If we say this then: When everyone has left the table, and the table is empty, AND the game is finished, then the game is revealed.

OK can find it acceptable that the random table join is not a good idea, but at least make sure only one running game per IP is allowed.
If the tables are large enough, it wont be possibe to deduce the unknown player's cards by collusion.

And why require accounts? It would be better with this:
1: You go to lets say wwww.dabsbitcoinpoker.com.
2: Then a bitcoin adress appears. Send your total bet (chips you want to purchase).
3: Once transaction appears on network, Your poker identity = Your bitcoin adress.
4: You can now proceed to select table and play poker.

All deck hashes are avaiable on the site, and maybe deck selected is based on all partipicants bitcoin adresses.

Leaving the site (by X in the corner) or any other means, will cashout your current chips provided that theres enough confirmations.
This will simply send all Money you have to your bitcoin adress.

Detecting leave, can be done in a multiple ways, but a easy way is to have some resource which refresh each 30 second, which reset a timer on 300 seconds.
if timer of 300 seconds goes to 0, player has leaved.


When the table is completely empty and all games at that table is finished, the game log including all revealed cards, are made available on site.

A poker player who uses a strategy he don't want to reveal, because it can be countered easly, can easly launder his bitcoin coins, to hide his prior poker identity, and then
join the poker with a new adress. Then any player who play against him, wont know that "hey its that player with the easy strategy".

I'll try to address your points now:


The problem is no poker player is going to want that. At least those who bet real money.

The only time cards or decks should be revealed is when an audit is being made to detect collusion or cheating, and usually that's restricted to employees of the online card room or casino.

I have a "dealer" secret that should be unique for every new deck, so this can function as the "deck" secret as well.


Really. Yes, poker may seem weird that way. The only reason we don't check physical table top card games that do not have this requirement, such as blackjack, is we make certain assumptions because we can see it with our own eyes.

In any card game where players eventually get to see all the cards, you don't need a secret for each card. You simply need a hash of the deck which can be represented by a string or array of 52 items in the final order.


That is an interesting term. Faithfully Fair. I will have to further explore this cut-and-choose you are talking about as I didn't quite get it yet.


Perhaps two or three additional secrets would work. 65536 just seems too much. And more cards in the deck make it suspect of being stacked.


Although I think I get what the point is by using that many decks, I think it might be possible without using additional decks, or only with additional cards. The additional decks can actually be revealed right before the start of the hand, so they are all eliminated already.

But I missed the part where AES is used. I can see where SHA-256 is used, and in fact, that's the only thing I used so far.

Just a quick answer, yes you can not reveal the deck at all at the end of the game. In a physical poker set up, the face down cards are simply scooped up and shuffled. No one will ever find out the cards that you never did see.

However, while this is much more difficult to implement online, internet play does have advantages such as no cheating through sleight of hand, no double dealing, side, top or bottom dealing, no hold outs (keeping cards for the next round), and no cowboys shooting each other.

As weird as it sounds, poker is not only a game of luck, chance, and skill, it is also a human game with psychology involved. There is bluffing, where there are stakes if you want to call it. If not, you fold. But at least no one else sees the cards.

Revealing the deck or even just the used cards will reveal their strategies, and almost all poker players will not want to play under such a system.

Revealing one hand is bad. Revealing the entire day's worth of games ... You'll get zero players once they find out.

Also, some players like to pick their seat positions in a table. That matters.

The suggestion of random people on random tables after every hand is a variant offered by some card rooms which are called names like zoom poker or rush poker or fast fold poker. Where you are "teleported" to a random available seat in a random table after every hand. And the only reason this is done is so players can play many more hands than if they remained at their table waiting for their turn, when they have already conceded.

I will study the proposals here and see if I can come up with something, but 65536 decks might be too much.

Maybe I'll just come up with a better argument to convince players that my implementation is indeed truly and provably fair.

There are already propose protocols that fall under Mental Poker, but they all involve fancy math. I like the idea of sticking to primitives like SHA and AES only.

gmaxwell: Thats why the deck needs to be generated long Before any player enters the party.

Since the "house" does not know who is gonna play when he generates the deck, still same security is given.
Another random numbers can be txids and such.

This to be able to provide sufficent security for user, even if all that is provided to user is a bitcoin adress to put in her bet on.

No, the protocol doesn't provide security if the house can guess at the users probable random values prior to issuing its own commitments.

gmaxwell: Its a better idea to use the player's bitcoin adresses as randoms. That of course means the decks need to be generated Before any player joins the party.

Another important thing is that the player's positions in table needs to be randomed too. If the player joins a game, is assigned a table at random, is assigned a random position, and the table using a random deck, and each IP can only have one single running game at the same time.

Everything is provable cryptographically.

Then theres no collusion, chipdumping or anything, that can make the experience bad for any other player. Its simply not possible to colluse with other players to reveal unknown player's cards.

You really can't reveal the deck at the _END_ of the game? really? ?  What a weird game.

In any case, you can make it unlikely that you are cheating with some moderate bandwidth cost, I mentioned this in passing above "and use cut-and-choose to prove that their actions were faithful"...

What you do is commit to MANY secrets, arranged in a tree ahead of time. Like ... 65536 of them.
Then you do the protocol with the users to compute  65536 encrypted decks.
You then provide a commitment tree for each deck and commit to those values with another hash root.

After that you and all of the users commit to random values. Then you reveal the random values. You hash up the random values and use them to select a single deck out of the 65535 you committed. This is the deck you will play with.

The rest of the decks you reveal the entire decks and decryption keys to your users.  If you added one cheating deck to the stack there would be only a 1/65536 chance of that deck being chosen, ... and a 65535/65536 = 99.998% chance of catching it. You can use larger numbers of decks to get higher security with an increase in bandwidth costs.  If your secrets are 128 bits and your encryption keys are 128 bits you would have to send 2Mbytes of data.  Though there are optimizations you can use if you use a tree structured CSPRNG to generate these secrets from a single master secret. In that case you could greatly reduce the data (to 16 + a few hash values, in fact)... but the margins of this post are too small to contain...(edit: I created another thread for that optimization)


By doing this you prove the decks are randomly ordered with perfect probability and contain all the right cards with as high a probability as you like.  And no fancy math involved... just sha256 and AES to encrypt the cards.

Dabs: Whats the problem with revealing the whole poker deck, and all other playe's cards, after the game is completed?

Now I mean when the WHOLE game is over. For a single poker session, one game = one deck.
In this simple case - reveal the deck after game is finished OR reveal all decks after day's end.
With "whole game over", is that this game must be done, nothing from this game may affect later games.
This means the game is consisted of completed when any player is free to leave any time.

In a competition, one game = multiple decks, where one single game consisting of say 100 entrants that are ejected one by one until theres one Winner left, can consist of multiple "sessions" with one deck each.
In a competition, its a forfeit to leave the game Before one single Winner is selected, and thus, all games affect all future games.

Thus if you want to hold a competition, use a other "deck secret" for this that are kept aside from "public" matches, that are kept secret until competition end.



To prevent people Learning other's strategies, you could make it so only a bitcoin adress is needed to join (like satoshidice), and people are advised to use a new bitcoin adress each game, so each game is Anonymous.
About chipdumping and collusion, its nothing to worry about, since chipdumping is only a problem in a economy where Money-launderying is non-permitted. In bitcoin economy, people are encouraged to Money-launder, to keep transactions Anonymous, so using your poker game to "chipdump" can be Another idea for such people who want high anonymity.


To prevent large scale collusion, where one single entrant may enter the game under multiple identities so theres only one foregin player, to then be able to find out the player's cards based on their own, make this:
1: No player can select a table, every player are assigned a table at random.
2: Each player can only be in one game concurrently, and this is identified by IP. You can hash the IP for anonymity.

That's essentially what I have been able to achieve with a slightly different implementation.

As a quick background, most poker games allow players to never reveal their cards, especially if the lose. Also, if you win because everyone else folded, the winner does not have to reveal his cards, since he is the only person left, he wins. It's possible for a game or a hand to not reveal any cards at all.

You, as the player, only ever get to see your own cards, usually these are just 2 cards. You'll never see the rest of the deck unless it goes to the next phase of the game or a showdown.

It's the fancypants math I'm worried about now, or the probability of my deck containing fake cards. I'd like to assure players that the cards are from the same set of 52 unique cards in a standard deck of 4 suits and 13 ranks.

I can only do so with some probability which is less than the probability of an encrypted card matching it's corresponding hash, which people already take as proof.

Crypto-proof = Provably Fair = it really is Probably Fair, but with a very very very very low probability of unfairness directly proportional to the collision resistance of the hash function used, in this case 2^256.

I am not following you here.

You use the technique there to generate the deck.

You generate a hash tree over the resulting cards and publish the root for all to see. You give the players their hands and the hashtree fragments. Any player can now prove to anyone else that their card was in the deck at whatever position it was at.

At the end of the came the dealer can reveal his secret and thus the whole deck, and everyone can verify the root.

If you actually need to _never_ reveal some of the cards (sorry, I know nothing about poker—) then you can encrypt each card before you shuffle the deck and also commit to a hash of the encrypted cards. You then do the same procedure, giving the users the decryption key for each card as you hand it to them. At the end the shuffle is proven faithful, and the identity of all revealed cards is known.  (though perhaps your deck contained fake cards in the set that were unrevealed— but thats a consequence of not revealing them. Fixing that requires you go into fancypants math)

Yes, I didn't give them their shuffle, and I later warned them that that was biased. I think they fixed it eventually. Its trivial to fix in any case.

All you should do is read ceil(log2(remaining cards)) random bits (uh, please with an integer implementation of the uprounding log2) and if the resulting index is too high throw out the number and retry.

@gmaxwell, it seems the link to your protocol has died. That game died a long time ago. But I did some research and found bits and pieces of it.

*edit* I used the way back machine and found this http://web.archive.org/web/20120323145517/https://bitjack21.com/cryptoproof

Unless I am missing something, that particular protocol wouldn't work for poker because it does not address the issue of not having to reveal mucked or folded cards. Cards that no one is ever meant to see.

Also, unless I am mistaken, that particular Fisher-Yates shuffle function is going to have a small bias. Kindly correct me if I am wrong.

I have been thinking of creating a Fisher-Yates shuffle which takes a string as input and spits out the new order based on the string. It could be a hex string. If I use 5 hex characters per card, then I have a range up to a little more than a million, discarding anything above a certain amount left in the deck that does not result in a round number.

What I mean is to generate an array of numbers randomly without bias, using the simple discard system.

Fisher-Yates takes 52 cards, grabs one at random, puts it in a new deck. Old deck now has 51 cards. New deck has 1. Then grab another one at random, put in the new deck. Optimized versions use a in-array or in-string swap, but I'm not concerned about that.

Any number generated above 52 gets discarded, then the next card, any number above 51 gets discarded. By using 5 hex digits, I have a million values of which any number above less than 47 from the maximum is discarded. I have the exact numbers I need to use from 52 down to 2 cards. The last card gets placed on top or at the bottom, depending on how the shuffle is implemented.

Alternatively, I use 52 hashes, then sort them. The uniform distribution of the hash result effectively randomizes the order of the deck. Overkill, inefficient and there is the very small possibility of a collision (which I will not worry about.)

Sorry, I do not understand what you are saying. Can you rephrase that?

This is important matter to consider because half knowledge is dangerous, so always try to get full knowledge about any matter and also give brief explanation to another.

@sebastian, I have already implemented the system you just described. I have a poker game I am actually hosting in the gambling section. You can go there and see.

https://bitcointalksearch.org/topic/provably-fair-online-poker-by-dabs-beta-test-1-274068

In fact, I used 52 different secrets, 1 for each card, and a dealer secret. Then I used an overkill function to randomize the deck which can be partially verified. Partially, because you can only ever see the public cards or the flop, and the hole cards (your own private cards.)

The problem with your solution is that, you end up having to reveal the entire deck, thus revealing the cards other players had. Blackjack players may not mind, but Poker players do not want this.

@gmaxwell, I will read your protocol later, I can't seem to access it now. My current method also allows players to cut or reshuffle the deck.


Sorry about the first post, I wanted to hide the fact that I wanted this for a poker game. hehehehe. I could have hidden it, but anyone looking at my post history would eventually find out.

I would appreciate it if you could provide the simple techniques you mention, or if it is already in your protocol (can't read it now for some reason, site is down?) or if what I am doing is already adequate.

What I could do is use more secrets or something, just to link the cards together, and / or as additional redundant "proof".

You know how bitcoin gamblers are, they accuse the house of cheating if they lose, if they don't understand. You have to make them understand, or at least make some of the smarter ones understand. Using anything that resembles quadratic residuosity makes it very difficulty to understand. To them, it's called voodoo math.

They will accuse you of cheating as long as they do not understand.

Most people now understand hashes because of the pioneering bitcoin casinos. You show the hash. They compute the hash. They prove to themselves, "Hey, I rolled this dice and I won or I lost fairly", or in this case "Hey, I got this card fairly." They might think "No one else is complaining, maybe they got their cards fairly too."

The only problems left with my solution are the same problems all other poker sites in existence have now: super-users (the house knows the cards) and collusion (players talking to each other.) I'll deal with those later.

Does the cryprographic protocol I made for btcjack21 accomplish what you want?

You can enhance it in the game by doing the split and sort of the deck, and then announcing a hashtree over the cards, allowing you to prove to each player that the card you gave to them was the right one, and then at the end you can also prove that you shuffled the deck fairly. ... though it's probably just adequate to prove the deck at the end.

Versions without a house doing the cards aren't too hard..., you just need users to encrypt and shuffle the deck, and use cut-and-choose to prove that their actions were faithful... but no need to go that route if you have a house.

But you could have non-random decks, including ones stacked in particular players favors (e.g. the Nth player, and then you make sure your compatriots play that role). I strongly suggest the protocol I linked above.

A idea is simply to create a game-specific secret, which are unique per gaming session, and card secret.

for example, the game-specific secret could be some random letters + the unix time of the game start. The random letters are unique for each game.
Then you PUBLISH the hashes of the whole deck.
The hashes is sha256(game-secret + card-symbol + card-number)

example, for aces of spades: sha256("lsjldslggdljdg1377684944SA")
example, for 5th of hearts: sha256("lsjldslggdljdg1377684944H5")
example, for king of diamonds: sha256("lsjldslggdljdg1377684944DK")
example, for queen of clubs: sha256("lsjldslggdljdg1377684944CQ")

So simply, you publish the hashes of the whole deck at game start. Nobody knows the content of the deck unless they can crack the random letters "lsjldslggdljdg". Thus the random letters need to be longer than in this example.

Any player are free to save the list of hashes.
All hidden cards should also display its hash, so your opponents cards will show the hashes.
Your cards will show hashes + the actual card value.

And the game should be recorded in a step-by-step file with all cards revealed. This file is stored on server.


When the game is over, and revelation of this game do not have any consequences to the outcome, you simply reveal the game-secret.
Every player who have saved the list of hashes to their computer or on paper or whatsoever, can validate that the deck randomization was not changed during the game.

The step-by-step file, is also revealed at game end, where player, can step the completed game step-by-step, but with all cards revealed.
Thus the player can validate that the game was conducted in a fair manner.


If multiple rounds are gonna being played before any game can be revealed, you can have deck serialization numbers:
example, for queen of clubs: sha256("lsjldslggdljdg1377684944CQ01")
01 means deck 01.
when next round is gonna played, you simply randomize a new deck, which will be called 02.



You could even have a daily secret like satoshidice has, so all decks for the next day's games is prepared one day before, and hashed being published.
And yesterday's secret is being published, proving that the deck for all the games during that day couldn't be changed without any noticing.
Then you would propably need 6-digit deck IDs, but then its even harder to cheat, since the decks are randomized daily.

To maintain security, you would need to have a way to determite player order. A good idea is to take the bitcoin adress, and give each player a position in the table that is equal to the numeric value of their bitcoin adress, so a player with adress 11111111111111111111111111111111111 will get their turn before a player with adress 1ZZZZZZZZZZZZZZZZZZZZZZZZZZZZ effectively making the order random.