Bitcoin Forum
May 21, 2024, 08:12:00 AM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 »  All
  Print  
Author Topic: Proof of Knowledge without Trusting?  (Read 2596 times)
Dabs (OP)
Legendary
*
Offline Offline

Activity: 3416
Merit: 1912


The Concierge of Crypto


View Profile
August 28, 2013, 03:05:25 AM
 #1

Hi,

I don't know where to place this as this is not exactly bitcoin, but rather a more general technical question.

How do you prove or assert beyond practical doubt that someone knows a secret without revealing the secret?

There is one way I know now, and it is through cryptographic hashes, such as SHA-256.

For example, the word "secret1" when hashed using SHA-256 results to 5b11618c2e44027877d0cd0921ed166b9f176f50587fc91e7534dd2946db77d6.

I can show the result, without revealing the secret until later or until after the required event. But what if I don't want to actually reveal the secret but still somehow prove I knew that?

So far, what I can see is to use another secret and add it to the first secret.

For example, the word "secret2" when hashed results to 35224d0d3465d74e855f8d69a136e79c744ea35a675d3393360a327cbf6359a2.

I can then combine both to make one longer word, such as "secret1secret2" which when hashed results to 9b1623d3c6e5c3e33ac15559b400d554868a3673efd4c088f575696b35d76407.

In this example, I publish the hash of "secret1" but keeping the secret secret. No one else knows it, yet. Then someone else publishes the hash of "secret2", but also keeping their secret secret. Both secrets are now essentially committed, and can't be changed.

Then that other person has to reveal his "secret2" to me or to the public, so that I can use both to come up with the combined hash of "secret1secret2" which is published. Two parties come up with the same result, without revealing the first secret, to prove that they both knew it, while the public only knows the second secret.

However that leaves the problem of me having to know both secrets. Is this enough proof that I knew the other secret without revealing it at all because of the relationship of both secrets and their resulting hashes?

That begs the question that the other party must be honest about the hash result of his "secret2". He can lie, and it breaks the whole concept.

My goal is in a scenario of 3 or more people. I'll use the "standard" names of Alice, Bob, and Charlie. Alice has a secret. Bob has a secret. How can Charlie tell that Alice and Bob have different secrets that remain unknown to the other, and to the public, but reasonably assume those secrets remain unchanged and in fact belong to the same set of unique secrets? I can, at this point, introduce a 4th person called "Dabs" who actually held all the secrets and distributed them to both Alice and Bob randomly.

One method I am using now is to hash each secret, and hand out those hashes publicly to both Alice and Bob. Alice will then be told the secret by Dabs. She can verify the secret against the hash. Bob is also told his secret by Dabs, who in turn can verify the secret against it's hash as well.

Without completely trusting Alice or Bob or Dabs, how can Charlie determine that Alice and Bob got their correct secrets from Dabs? Without Dabs, Alice or Bob revealing the secrets at all.

I've been reading a bit about zero knowledge proofs and other related matters, but their math is beyond me, so I attempted to do the same using hashes as that is much simpler to understand. We know, with a 1 in 2^256 probability, that if the hash result is one thing, the secret must be the original secret. I'm assuming the collision resistance of hash functions as more than enough reasonable proof that the secret is the secret.

A similar system is used in bitcoin gambling casinos, and they call it "Provably Fair".

Ok, this might be confusing and I may have mixed it up already. But I'm posting this anyway so I can get the discussion started, and if this is in the wrong forum, can be moved by a moderator.

gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4172
Merit: 8421



View Profile WWW
August 28, 2013, 04:17:24 AM
 #2

There is an entirely subfield of cryptography that deals with zero-knoweldge signatures of knowledge which are mathematical systems for producing convincing evidence that a person with knowledge of some specific secret data, matching a criteria set by an arbitrary computable function, signed a given public value without revealing anything about the secret data at all, except that the person knew it.

Though without a more concrete description of what you're actually trying to accomplish I can't say what else might meet the criteria you're going for... for many things involving a finite number of people set up in advance who can all interact there are other options beyond signatures of knowledge, including interactive proof protocols and secure group computing.

For some kinds of proof systems can be easily and understably constructed from nothing more than authenticated data-structures, or simple elliptic curve homomorphism.  I'd be happy to tell you exactly how to do so with one of these simple techniques if what you want is possible, but you've managed to write a lot of text without actually communicating to me what you're trying to accomplish.

Going from what you've said, I can't determine where this procedure fails you: Alice picks a random value, publishes the hash.  Bob picks a random value, publishes the hash. Done.

Obviously you want to accomplish more/different than that, but I can't tell what.

Quote
that remain unknown to the other
I believe that proving something known to one party is _unknown_ to another party, when they potentially could have cooperated is impossible (until you upload humans and can subject their minds to mathematical proofs). Smiley
jl2012
Legendary
*
Offline Offline

Activity: 1792
Merit: 1097


View Profile
August 28, 2013, 04:33:26 AM
 #3

Don't need to be so complicated: public-key cryptography is exactly what you need.......

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3 (Bitcoin ONLY)
LRDGENPLYrcTRssGoZrsCT1hngaH3BVkM4 (LTC)
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Dabs (OP)
Legendary
*
Offline Offline

Activity: 3416
Merit: 1912


The Concierge of Crypto


View Profile
August 28, 2013, 09:05:15 AM
 #4

This has actually been discussed elsewhere, but my potential application is a card game. You can take a guess which card game.

1. Some cards are known to everyone watching. Just reveal it and it's associated hash.
2. Some cards are known only to the player. Just reveal it to that particular player.
3. The rest are still in the deck. Everyone sees the hash of the cards in the deck without seeing the face of the cards. It's as if each card is individually and uniquely marked at the back. But no one knows
4. The player can prove to himself he got the cards he was supposed to get.
5. The other players have no clue except that the first player did get some cards, but they don't know which ones.
6. It's possible the other players will never be able to tell what those cards are.

Without reading the rest of the literature already available on the subject, I independently came up with something that does the first 2 above. I also came up with a way to shuffle the deck fairly, by having the players cut the deck.

I originally did not want to mention the application, but it seems after reading a lot on the subject, the original problem spawned all sorts of solutions to different cryptographic questions. Everything is related to Poker.

I read the old papers of SRA about Mental Poker and a bunch of others.

I am focusing on the solution where I am the dealer, thus I know all the cards; however I must be trusted. The other solutions being studied consider that there is no trusted third party, and while I think this might be possible (and someone already claims to have achieved it) it's really hard on the computer and the players.

So I need to find a way, to show to Alice that Bob got the cards he was supposed to get without revealing those cards to Alice.

I may have already achieved this but it doesn't seem obvious, so I need to make it apparent or point it out to the people how it is so. Otherwise I will have to do all sorts of advanced math that most people can't even begin to understand so it might defeat the whole point of it.

I believe that proving something known to one party is _unknown_ to another party, when they potentially could have cooperated is impossible (until you upload humans and can subject their minds to mathematical proofs). Smiley

In the poker world, that is called collusion. We will have to go by some assumptions that they do not do this, especially if they are direct opponents. Let's pretend that Alice and Bob do not want the other person to know what they are holding. If they did, they would send messages through an alternate channel (IM, chat, irc, phone call, or they are in the same room physically.)

We make an assumption that Alice and Bob will not tell each other their cards unless it goes to a show down.

The answer to this, in case this is not possible, is that, if Bob folds, Alice does not care what cards Bob had. Alice wins the pot.

But there are people out there who want to make sure that everyone got the cards they were supposed to get. Again, I think I have already achieved this, but it is just not obvious or I'm thinking I just have have a high probability of it.

I understand that using hashes just means that there is a 2 in 2^256 or 2^512 odds of 2 strings hashing to the same value or a collision, and not actual mathematical proof. But for most people, they'll accept it as proof enough. That's all I really need at this point. I think the SRA paper also accepts this and shows why it is impossible.

sebastian
Full Member
***
Offline Offline

Activity: 129
Merit: 118


View Profile
August 28, 2013, 09:29:20 AM
Last edit: August 28, 2013, 10:00:03 AM by sebastian
 #5

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.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4172
Merit: 8421



View Profile WWW
August 28, 2013, 10:43:51 AM
 #6

This has actually been discussed elsewhere, but my potential application is a card game. You can take a guess which card game.
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.

Quote
proving that the deck for all the games during that day couldn't be changed
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.
Dabs (OP)
Legendary
*
Offline Offline

Activity: 3416
Merit: 1912


The Concierge of Crypto


View Profile
August 29, 2013, 12:54:38 AM
 #7

@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://bitcointalk.org/index.php?topic=274068.0

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.

Quote
I'd be happy to tell you exactly how to do so with one of these simple techniques if what you want is possible, but you've managed to write a lot of text without actually communicating to me what you're trying to accomplish.

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.

crescendo
Newbie
*
Offline Offline

Activity: 29
Merit: 0


View Profile
August 29, 2013, 06:17:50 AM
 #8

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.
Dabs (OP)
Legendary
*
Offline Offline

Activity: 3416
Merit: 1912


The Concierge of Crypto


View Profile
August 29, 2013, 07:22:20 AM
 #9

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.

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

Dabs (OP)
Legendary
*
Offline Offline

Activity: 3416
Merit: 1912


The Concierge of Crypto


View Profile
August 30, 2013, 05:38:42 AM
 #10

@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.)

gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4172
Merit: 8421



View Profile WWW
August 30, 2013, 06:11:49 AM
 #11

@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.

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)

Quote
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.
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.
Dabs (OP)
Legendary
*
Offline Offline

Activity: 3416
Merit: 1912


The Concierge of Crypto


View Profile
August 30, 2013, 07:25:17 AM
 #12

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)

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.

sebastian
Full Member
***
Offline Offline

Activity: 129
Merit: 118


View Profile
August 30, 2013, 07:34:45 AM
Last edit: August 30, 2013, 07:48:07 AM by sebastian
 #13

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.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4172
Merit: 8421



View Profile WWW
August 30, 2013, 07:47:22 AM
Last edit: August 30, 2013, 09:08:49 AM by gmaxwell
 #14

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.
You really can't reveal the deck at the _END_ of the game? really? Huh?  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.
sebastian
Full Member
***
Offline Offline

Activity: 129
Merit: 118


View Profile
August 30, 2013, 08:01:17 AM
 #15

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.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4172
Merit: 8421



View Profile WWW
August 30, 2013, 09:07:30 AM
 #16

gmaxwell: Its a better idea to use the player's bitcoin adresses as randoms.
No, the protocol doesn't provide security if the house can guess at the users probable random values prior to issuing its own commitments.
sebastian
Full Member
***
Offline Offline

Activity: 129
Merit: 118


View Profile
August 30, 2013, 10:42:42 AM
 #17

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.
Dabs (OP)
Legendary
*
Offline Offline

Activity: 3416
Merit: 1912


The Concierge of Crypto


View Profile
August 30, 2013, 10:07:18 PM
 #18

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.

Dabs (OP)
Legendary
*
Offline Offline

Activity: 3416
Merit: 1912


The Concierge of Crypto


View Profile
August 31, 2013, 03:47:26 AM
 #19

I'll try to address your points now:

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

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.

Quote
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.

I'd probably want people to create accounts if I do have a poker site. They can remain anonymous anyway by hiding the name, or changing what is displayed. The server or dealer would know, but only as much information as provided by the user, so if you never give me your name or address, than all I have is a number.

Quote
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 will probably work for a version known as zoom, rush, or fast fold poker. Not all players will want this kind of set up.

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

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.

Quote
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"...

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.

Quote
What you do is commit to MANY secrets, arranged in a tree ahead of time. Like ... 65536 of them.

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.

Quote
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.

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.

sebastian
Full Member
***
Offline Offline

Activity: 129
Merit: 118


View Profile
August 31, 2013, 08:18:23 AM
 #20

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".
Pages: [1] 2 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!