Pages:
Author

Topic: Breaking: Shuffle-based Provably Fair Implementations Can Cheat Players (proof) (Read 4713 times)

jr. member
Activity: 86
Merit: 5
i doubt bitzino cheats on their BJ, i played it constantly while at the same time playing live $1-3 NL on the riverboats here in shreveport. once, i turned $23 into $1200 over a few weeks. i liked the option to bet microscopic bets and martingale endlessly since u could bet 1 1 millionth of a bitcoin.

this morning, bitzino closed without notice, i would love to know why. no matter how much i search google this morning, i cannot find the reason for the closure. luckily i was able to withdraw my balance. its in coinbase now.

so--where else can those of us in Trump's USA play for microscopic units in BJ? for say like 1c or less worth of bitcoin instead of the min $1 bets on nonbitcoin sites? 15 millionths of a bitcoin was worth close to 1cent.
legendary
Activity: 3416
Merit: 1912
The Concierge of Crypto
256 bits modulo 52 cards. Forget about the bias, let players gamble on it....

I also had this crazy idea of using 64k decks. Then let the player decide which deck to use. (This is for the poker game.) Reveal the order of all the other 65535 decks but keep secret the one deck. For poker purposes (because you're not supposed to reveal cards which are face down that others can not see.

If that is too much, just use any other power of 2 number of decks. 2, 4, 8, 16, ... 128, 256. I mean, there is a 1/256 chance that the house is going to rig your game, but you have a 254/256 chance of being fair, or something along those lines. So the house will simply not bother.
legendary
Activity: 1582
Merit: 1006
beware of your keys.
Yeh, with more decks it becomes a bit more difficult. For 8 decks I guess you will get something like this: card numbers will be 0-415, use 3 characters instead from final seed (= 0-65535), convert to number, then use the number if the number is 0-65311 (so skip 65312 and higher), with that number do a modulo of 416 so you will get a result of 0-415 = 1 card out of 8 decks. Again, if you got number already previously - skip it.

Video poker is like a slot reel where each reel is 52 cards, right? So I think that would be the same, but doesn't need the "check if double" thing because each reel can have exact same number than previous. After someone uses the "hold" option, it will use the 6th number, 7th, etc.

Normal slot reel is even easier, because it can just use 1 character instead of 2/3 (when you don't have more than 16 options per reel.) Crypto-Games also uses this for their slot games.





I wonder what OP, RHavar and others that participated in this thread think about above options rather than Fisher–Yates method. It seems easier to me because anyone can verify it with simple SHA256/512 and Hex-to-Decimal online tools - rather than running a Fisher–Yates and modulo-seed-loop-rng script.

regarding video poker

normal slot is different and maybe therefore easier as you are saying. video poker cause of the hold option a player could use an optimal strat. video poker is a 52 cards one deck game

yes I agree and would like to know what OP is thinking and if he has the solution

thx again
is that means in case of the possible output amount, not the power of 2, will be possibly tampered by adding special secret script? i mean, in a nutshell, the equivalent result can be shuffled again by order to manipulate the fairness, like 999dice? Huh
legendary
Activity: 1974
Merit: 1014
All Games incl Racer and Lottery game are Closed
Yeh, with more decks it becomes a bit more difficult. For 8 decks I guess you will get something like this: card numbers will be 0-415, use 3 characters instead from final seed (= 0-65535), convert to number, then use the number if the number is 0-65311 (so skip 65312 and higher), with that number do a modulo of 416 so you will get a result of 0-415 = 1 card out of 8 decks. Again, if you got number already previously - skip it.

Video poker is like a slot reel where each reel is 52 cards, right? So I think that would be the same, but doesn't need the "check if double" thing because each reel can have exact same number than previous. After someone uses the "hold" option, it will use the 6th number, 7th, etc.

Normal slot reel is even easier, because it can just use 1 character instead of 2/3 (when you don't have more than 16 options per reel.) Crypto-Games also uses this for their slot games.





I wonder what OP, RHavar and others that participated in this thread think about above options rather than Fisher–Yates method. It seems easier to me because anyone can verify it with simple SHA256/512 and Hex-to-Decimal online tools - rather than running a Fisher–Yates and modulo-seed-loop-rng script.

regarding video poker

normal slot is different and maybe therefore easier as you are saying. video poker cause of the hold option a player could use an optimal strat. video poker is a 52 cards one deck game

yes I agree and would like to know what OP is thinking and if he has the solution

thx again
legendary
Activity: 1876
Merit: 1295
DiceSites.com owner
Yeh, with more decks it becomes a bit more difficult. For 8 decks I guess you will get something like this: card numbers will be 0-415, use 3 characters instead from final seed (= 0-65535), convert to number, then use the number if the number is 0-65311 (so skip 65312 and higher), with that number do a modulo of 416 so you will get a result of 0-415 = 1 card out of 8 decks. Again, if you got number already previously - skip it.

Video poker is like a slot reel where each reel is 52 cards, right? So I think that would be the same, but doesn't need the "check if double" thing because each reel can have exact same number than previous. After someone uses the "hold" option, it will use the 6th number, 7th, etc.

Normal slot reel is even easier, because it can just use 1 character instead of 2/3 (when you don't have more than 16 options per reel.) Crypto-Games also uses this for their slot games.





I wonder what OP, RHavar and others that participated in this thread think about above options rather than Fisher–Yates method. It seems easier to me because anyone can verify it with simple SHA256/512 and Hex-to-Decimal online tools - rather than running a Fisher–Yates and modulo-seed-loop-rng script.
legendary
Activity: 1974
Merit: 1014
All Games incl Racer and Lottery game are Closed
For Blackjack you can use the method I just described (which is used by Crypto-Games.) Blackjack only needs like 4 - 10 cards in normal game (even though 4 decks are used.) I like the way Crypto-Games does it, because it's very easy/understandable.

That method keeps looping looking for unique cards within those 4 decks. That's fine for like 10 cards, but if you would need like 40 cards, that probably gets pretty bad in performance (because it keeps looping for unique cards while not really discarding/removing them) and additionally that "final hash" would not provide enough characters.

So if you need to select more cards for other games:
Now they use Fisher–Yates shuffle with Mersenne Twister RNG. They should use Fisher–Yates shuffle with "modulo of sha256 RNG".

first of all thx for taking the time to explain it in more depth

4 - 10 cards imo is not enough depending on the rules an OP could offer. for example dealer hits soft 17 and resplit up to 4 hands

what does it mean when you are saying "unique cards" in a 4 deck game?

4-10 was example. In reality there are 64 sets of 2 characters in a SHA512 hash. Some of those 64 numbers will be out of reach (208-255) or double numbers, but it should be still enough. One could do the math of odds of running out of numbers in biggest blackjack game (depending on "split rules" too), but I am bit lazy to do that. I do assume its enough even with all the splits.

If you have a multi-player blackjack game, it would probably not be enough. It could still easily just add a nonce to further loop or just use the Fisher–Yates shuffle. Still IMO the simple hash without Fisher–Yates shuffle is easier / more clear. So I would only use Fisher–Yates shuffle if it's really needed (=need lots of cards selected.)

Unique card: I mean, that Crypto-Games has 4 deck of cards, but actually its just numbers from 0-207, see: https://www.crypto-games.net/blackjackcards.html We will just pick numbers between 0-207 and each number represents a card. So any card, like a King of Hearts, appears 4x in total (numbers: 23,75,127,180.) When I say "unique" I mean that the specific number 0-207, like "75" cannot be repeated, since normally a specific card cannot be repeated either. However, the king of hearts can appear up to 4 times with those 4 numbers (23,75,127,180.)



edit: I guess this method is mostly nice up to 4 decks, since 2 hexadecimal characters are between 0-255. If you want more decks, you would probably need some ugly modulo thing with 3 hex characters. So probably better just Fisher–Yates shuffle with "seed RNG" for more decks. I am not sure if there is a site already that implemented that?

thx again for explaining, very much appreciated cause I am not an expert but we love the provably fair option.

the reason I asked for more than a 4 deck game is that a 6 or 8 deck would have a slightly better HE for the OP and would give the option to offer some rules a player would like to have and again reduce the HE so the HE will not be to low. I hope you understand my point

am I right when assuming the same provably fair option could be used with video poker?

legendary
Activity: 1876
Merit: 1295
DiceSites.com owner
For Blackjack you can use the method I just described (which is used by Crypto-Games.) Blackjack only needs like 4 - 10 cards in normal game (even though 4 decks are used.) I like the way Crypto-Games does it, because it's very easy/understandable.

That method keeps looping looking for unique cards within those 4 decks. That's fine for like 10 cards, but if you would need like 40 cards, that probably gets pretty bad in performance (because it keeps looping for unique cards while not really discarding/removing them) and additionally that "final hash" would not provide enough characters.

So if you need to select more cards for other games:
Now they use Fisher–Yates shuffle with Mersenne Twister RNG. They should use Fisher–Yates shuffle with "modulo of sha256 RNG".

first of all thx for taking the time to explain it in more depth

4 - 10 cards imo is not enough depending on the rules an OP could offer. for example dealer hits soft 17 and resplit up to 4 hands

what does it mean when you are saying "unique cards" in a 4 deck game?

4-10 was example. In reality there are 64 sets of 2 characters in a SHA512 hash. Some of those 64 numbers will be out of reach (208-255) or double numbers, but it should be still enough. One could do the math of odds of running out of numbers in biggest blackjack game (depending on "split rules" too), but I am bit lazy to do that. I do assume its enough even with all the splits.

If you have a multi-player blackjack game, it would probably not be enough. It could still easily just add a nonce to further loop or just use the Fisher–Yates shuffle. Still IMO the simple hash without Fisher–Yates shuffle is easier / more clear. So I would only use Fisher–Yates shuffle if it's really needed (=need lots of cards selected.)

Unique card: I mean, that Crypto-Games has 4 deck of cards, but actually its just numbers from 0-207, see: https://www.crypto-games.net/blackjackcards.html We will just pick numbers between 0-207 and each number represents a card. So any card, like a King of Hearts, appears 4x in total (numbers: 23,75,127,180.) When I say "unique" I mean that the specific number 0-207, like "75" cannot be repeated, since normally a specific card cannot be repeated either. However, the king of hearts can appear up to 4 times with those 4 numbers (23,75,127,180.)



edit: I guess this method is mostly nice up to 4 decks, since 2 hexadecimal characters are between 0-255. If you want more decks, you would probably need some ugly modulo thing with 3 hex characters. So probably better just Fisher–Yates shuffle with "seed RNG" for more decks. I am not sure if there is a site already that implemented that?
full member
Activity: 393
Merit: 107
Very interesting write-up! Thank you OP.
legendary
Activity: 1974
Merit: 1014
All Games incl Racer and Lottery game are Closed
For Blackjack you can use the method I just described (which is used by Crypto-Games.) Blackjack only needs like 4 - 10 cards in normal game (even though 4 decks are used.) I like the way Crypto-Games does it, because it's very easy/understandable.

That method keeps looping looking for unique cards within those 4 decks. That's fine for like 10 cards, but if you would need like 40 cards, that probably gets pretty bad in performance (because it keeps looping for unique cards while not really discarding/removing them) and additionally that "final hash" would not provide enough characters.

So if you need to select more cards for other games:
Now they use Fisher–Yates shuffle with Mersenne Twister RNG. They should use Fisher–Yates shuffle with "modulo of sha256 RNG".

first of all thx for taking the time to explain it in more depth

4 - 10 cards imo is not enough depending on the rules an OP could offer. for example dealer hits soft 17 and resplit up to 4 hands

what does it mean when you are saying "unique cards" in a 4 deck game?


legendary
Activity: 1876
Merit: 1295
DiceSites.com owner
For Blackjack you can use the method I just described (which is used by Crypto-Games.) Blackjack only needs like 4 - 10 cards in normal game (even though 4 decks are used.) I like the way Crypto-Games does it, because it's very easy/understandable.

That method keeps looping looking for unique cards within those 4 decks. That's fine for like 10 cards, but if you would need like 40 cards, that probably gets pretty bad in performance (because it keeps looping for unique cards while not really discarding/removing them) and additionally that "final hash" would not provide enough characters.

So if you need to select more cards for other games:
Now they use Fisher–Yates shuffle with Mersenne Twister RNG. They should use Fisher–Yates shuffle with "modulo of sha256 RNG".
legendary
Activity: 1974
Merit: 1014
All Games incl Racer and Lottery game are Closed


If you need more/all cards, I guess Fisher–Yates shuffle with proper simple RNG (not MT) is faster than that long loop though :p

hi

I am very interested in a provably fair option for Black Jack and that all cards of a 4 -8 decks are included

did I understand it right that the fisher yates shuffle would be fine to use and acceptable to be provably fair?

thx





legendary
Activity: 1876
Merit: 1295
DiceSites.com owner
It's not about the seeds used, but the MT RNG just has that seed input limitation. MT19937 is normally used and has a 32 bits limit, there is MT19937-64 which would be better with 64 bits but still not enough (although less feasible to brute-force results.)



Anyway for a lot of games, like blackjack, very easy solution can be possible. For example Crypto-Games.net does this:

1. Gets "final hash" (with "per roll" method but could be with "normal dice nonce" method.)
2. Has 4 decks so 208 cards: https://www.crypto-games.net/blackjackcards.html
3. Gets 2 characters from "final hash" and convert to decimal (= value of 0-255)
4. Use that as card (if within 0-207 range and not double.)
5. Repeat with next 2 characters till you have all the cards you need.

So that is easy/good imo?

For roulette it's even easier.. just loop those 2 characters from hash till its 0-36. (Crypto-Games does this too.) No need for "initial" stuff.



If you need more/all cards, I guess Fisher–Yates shuffle with proper simple RNG (not MT) is faster than that long loop though :p
legendary
Activity: 3416
Merit: 1912
The Concierge of Crypto
Hey, it's you again. I missed this thread, and sorry for the 3 or 4 month bump. But my one comment is to simply not use the "reference implementation" and make sure your final shuffle has a space much bigger than 32 bits. This means both client and server seeds must be larger than 52! or whatever is the size of the deck.

Dice sites have been using SHA256 and SHA512 since forever.

My poker version is difficult and unwieldy but I believe it's the best way to shuffle a deck without revealing the cards to players who shouldn't know. (If you fold, no one else see's your cards.) It's also overkill, so I'm trying to see if there is a simpler implementation that would be just as effective, but that eludes me. (Go look for my "Provably Fair Poker" thread from 3 years ago.)

For all other normal card games where you can reveal the entire deck after the game, 256-bit client seed, 256-bit server, 256-bit "anything else needed/nonce" should be more than enough "provably fair".
newbie
Activity: 27
Merit: 10
I think betking is an exception, but I would love to hear from some of the other providers about how the intend to fix this situation...

I looked at BetKing's provably fair implementation and determined that they can use shufflepuff as an exploit AND their shuffle algorithm has a modulo bias. In general, for an eight deck blackjack game, the modulo bias occurs once every 200,000-400,000 hands. Not a lot, but easily fixable. To fix the modulo bias, BetKing would want to discard any number n where n >= MAX - MAX % modulus, where MAX = 232 - 1.

A good thing about BetKing is that they keep their code simple and easy to read. This is in contrast to some casinos that have very complicated methods for similar functions.
legendary
Activity: 1302
Merit: 1005
New Decentralized Nuclear Hobbit
Isn't it a bad implementation though? They generate the 30 initial numbers, without your client seed, and they can generate what ever they want, and you can't verify that they cheated with the inital generation. So while it is technically provably fair, because of how the initial shuffle is generated, they could create a higher house edge by predicting what the gambler likes to do (ie over 7) and generate the inital deck so it is more likely to get under 7?

Yeah, but still better than I thought. Cheesy



Quote
They should just get rid of the initial generation and play with a fair deck (5 ones, 5 twos, 5 threes, e.t.c)
They can't do that either.
Let us say, we have 5 of each. Each number appears once every six times.
It is shuffled and two numbers are selected.

Now the odds that the second number is "1" when the first number is "1" is less than the odds that the second number is "2" when the first number is "1". while it should be equal.
That is, if the first number is "x" there is only 4/30 chance that the second number is also "x". The probability should be 5/30.


I suggested this:
Quote
Possible solution: (just a suggestion)
Two rolls are generated separately in the same process with the same server seed and a standard initial numbers that is the same for every roll.

First die inputs:
Standard initial numbers (6. 30 is good too) (I)
One server seed (S)
One client seeds (C1)

Second die inputs:
Standard initial numbers (6. 30 is good too) (I)
One server seed (S)
One client seeds (C2)

Process:
The same.

So it looks like this:

Time: 2016-06-07 22:28:37
Game:Over 7
Roll:6 - 5
Bet Amount. mBTC: 0.01227
Profit, mBTC: +0.01656
Server Seed:
0c1a6e80e45753bf1018eeee76eb3244
Initial Numbers:
[1, 2, 3, 4, 5, 6]  (or 30 standard numbers, for example 1,2,3,4,5,6,1,2,3,....5,6 or 1,1,1,1,1,1,2,2,2,2,2,2,....6)
Initial Hash:
fb02ecd1a7814103bd718de5e21e6f21ca746cc9e36ec8d683bc7eb3b93acdd0
Next Hash:
232270e0092a9f4c52cbbade6fb4174f9f58878485d558a5d6f1f43c51da38bc
Client Seed (1):
0.2707008711765295
Final Numbers (1):
[6, 1, 4, 3, 2, 5]  (.... for 30)
Client Seed (2):
0.2938293211765295
Final Numbers (2):
[5, 3, 2, 4, 1, 6]  (.... for 30)
legendary
Activity: 2772
Merit: 3282
From my perspective, if the provably fair system isn't "provable" then it can only degenerate into a simple promise of fairness.
I'd like to know your take on the provably fair system of www.luckyb.it & www.bitcoinbetting.website.
I'll give you my take on bitcoinbetting.website's provably fair system, since TrevorXavier isn't going to comment. bitcoinbetting.website is for the most part, provably fair. For bitcoinbetting.website to cheat, they would need to own a large % of the network hashrate, and if a winning bet is in the block they just found, they could withhold the block and let another miner get a different block, with possibly a different last digit. This would be hard to do though, as the hashing power needed would cost a lot of BTC, and the payout has to be over 25 BTC for it to be worth it to withhold the block. I doubt they have that much money to get a large share of the network, and the bets are still pretty small so I am 99.99% sure they don't cheat. They can, but it is extremely unlikely.

TL:DR : They can cheat, but they probably won't unless they own a large amount of the network's hashing power and the payout for a bet is over 25 BTC, and is included in a block that they mine.
newbie
Activity: 27
Merit: 10
I'd like to know your take on the provably fair system of www.luckyb.it & www.bitcoinbetting.website.

Thank you for writing, Angelina Jolie! Smiley

I'd love to, but I try not to comment on specific casinos unless I've taken a fairly deep look into how they operate. This takes a considerable amount of time. Hopefully, there are some sources where others have taken a look at these websites? Are the ones you're referring to on-chain betting?

I can make some general comments about shuffle-based provably fair systems, in case you encounter them. I know it may not be helpful for the specific casinos you're referring to, but you never know. Smiley

When I looked into the shuffle-based provably fair systems, many of them suffered from the following:

  • Sole control over the initial arrangement of the cards. This is the basis of shufflepuff, which I believe "breaks" the provable aspect of "provably fair" for many of these casinos. Adapting shufflepuff to their provably fair method would allow a casino to take advantage of you.
  • Modulo bias in the shuffling algorithm. This is normally not a big deal for most applications but a considerable gaffe for a casino (which markets fairness). It shouldn't exist, really. In general, depending on where the Fisher-Yates algorithm starts shuffling (the beginning or the end of the deck), a casino can favor cards in certain spots. Though rare, sophisticated usage of it can result in the player being denied a card (like an Ace in blackjack) or given a card (like a 5 or 6).

If you have any other questions, let me know!
member
Activity: 169
Merit: 10
Global Risk Exchange - gref.io
From my perspective, if the provably fair system isn't "provable" then it can only degenerate into a simple promise of fairness.
I'd like to know your take on the provably fair system of www.luckyb.it & www.bitcoinbetting.website.
newbie
Activity: 27
Merit: 10
Isn't it a bad implementation though? They generate the 30 initial numbers, without your client seed, and they can generate what ever they want, and you can't verify that they cheated with the inital generation. So while it is technically provably fair, because of how the initial shuffle is generated, they could create a higher house edge by predicting what the gambler likes to do (ie over 7) and generate the inital deck so it is more likely to get under 7? They should just get rid of the initial generation and play with a fair deck (5 ones, 5 twos, 5 threes, e.t.c)

I can't render an opinion on Pocketdice, but it looks like NLNico and RHavar have seen obvious defects which would preclude it from being provably fair.



The way I see it, "provably fair" (the concept) is marketed by casino operators with several claims. Here's a sample (emphasis added in bold):

Sorry to hear that you are skeptical about the site.

All of our games are provably fair. Therefore, it is impossible for us to change the outcome depending on the bet amount. Big bets and small bets have the same chance of winning.

We cannot influence the odds of any wagers you place in bitZino, other than simply changing the rules to the game in question, which you will know (for example, if we paid out 6 to 5 on a blackjack instead of 3 to 2, you'd be able to easily notice this).

Provably fair systems allow players to independently verify every single wager they make - usually immediately after the wager is complete. Effectively, this is a zero-trust system: players don't have to trust third-party licensing providers to be confident they're getting a fair game.




When presented with a viable weakness, however, casino operators seem to resort to a promise (which requires trust) or marketing (emphasis commentary added in bold):

your provably fair is not fair  Tongue (should be 'not provable')

see here for reference.

https://bitcointalksearch.org/topic/breaking-shuffle-based-provably-fair-implementations-can-cheat-players-proof-1494470

Thanks for brining this to our attention.
We absolutely always use a random number for every single game, and would never even consider cheating our loyal customers. (trust me)
After reviewing the post in question,  I don't think this is an even accurate criticism anyhow.
It would take 17+ hours to generate a single seed to influence a single round of play, but our casino allows you to play as many games per second as you would like. (didn't read the method correctly)
For example, in May there were more than 25,000,000 games played on our site.  That works out to about ten games per second.
Regardless,  our casino has much much better odds than anything in Vegas. (marketing)

Cheers

...you are right about our Mersenne Twister (MT) truncates to 32-bits. However, our dealer shuffle doesn't just use MT and Fisher-Yates, it also uses the Java RNG and therefore the process as a whole has enough randomness. (trust me)



From my perspective, if the provably fair system isn't "provable" then it can only degenerate into a simple promise of fairness. A promise requires that you trust the casino, which is contradictory to the casino's claims.

Many of these casinos have been around for some time, so they tend to be a little dismissive when an attack is presented. It's natural: they have established a base of players, some of whom might play regardless of provable fairness, some who don't verify anymore, some who may amplify claims, and so on. And they've likely received more than their fair share of claims from players about cheating.

Truly interesting responses. Thanks for the question, DarkStar_!
legendary
Activity: 2772
Merit: 3282
Ps, there is actually one dice site "pocketdice" that uses "initial random numbers" which was proven to have a bad provably fair implementation (for more simple reasons than OP Tongue) Unfortunately they still didn't improve this.

How the system works exactly is still beyond me but I can't see the logic on the relatively complex way it is implemented or the mystery behind the 30.
But how is this?
The client's seed is not really used to generate the random result.
Pocketdice's problem is more simple. They could simply generate all 1's as "initial deck", and obviously it would be impossible for you to win if you don't bet on number 1 - no matter how random you shuffle all those 1's with your client seed Tongue

Pocketdice is provably fair alright. Tongue

I just found out. Grin (was thinking the hash was just that of server seed)

Quote
We generate 30 initial random numbers ranging from 1 to 6.
We generate random server seed.
The initial numbers are hashed using hash("sha256", json_encode($initial_numbers) . $server_seed). The resulting hash is made public.
When you start a game, we use javascript in your browser to create a client seed.
The initial numbers are shuffled calling Fisher-Yates shuffle with client seed.
Isn't it a bad implementation though? They generate the 30 initial numbers, without your client seed, and they can generate what ever they want, and you can't verify that they cheated with the inital generation. So while it is technically provably fair, because of how the initial shuffle is generated, they could create a higher house edge by predicting what the gambler likes to do (ie over 7) and generate the inital deck so it is more likely to get under 7? They should just get rid of the initial generation and play with a fair deck (5 ones, 5 twos, 5 threes, e.t.c)
Pages:
Jump to: