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

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.

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.

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?

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

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.

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?

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?

Very interesting write-up! Thank you OP.

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?

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:

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

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

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

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 = 2³² - 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.

Yeah, but still better than I thought.



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:

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.

Thank you for writing, Angelina Jolie!

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.

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!

I'd like to know your take on the provably fair system of www.luckyb.it & www.bitcoinbetting.website.

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):







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):





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_!

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)

Thank you for the replies.

I don't know much about mining either particularly in this case on what the nonce is etc.


https://en.bitcoin.it/wiki/Nonce

So the nonce value is set by the miner. I was thinking it was automatically computed or something..




Yeah    Never thought of that.


So the block hash is the only reliable (or most reliable) string in a block that can be used for provably fair?

This is the same type of deflection Nitrogensports is infamous for. They have a clearly rigged Blackjack system but whenever anyone questions it they link to "provably fair". Good to see hard data out there that doesnt make the Casino skeptics looks crazy.

Disclaimer: I am not a mining expert, so anyone please correct me if I am wrong here....



satoshinonce would not be fair for investors and that site is technically not even provably fair for the player.

For player: if satoshinonce is also a miner, they could specify block-nonces (last 1 or 2 digits only) in their mining software which makes the incoming transactions/bets lose (or at least whichever is best for them.) So even if they have 2% mining power, players would most likely lose 2% more often. That's why I think for the player it's better to have TX+VOUT+SECRET like Luckyb.it (and SD before.) Might be tough to change it since.. well.. the site is called "Satoshi Nonce".

For investor: if satoshinonce is also a miner, they could adjust the mining software to only check nonces with 2 specific last digits and include some of those winning 98x transactions in it (and not even broadcast those transactions before finding the block!) Then if they find a correct block, they send it out including those winning transactions. It seems like a guaranteed way to win with no risk. So doesn't help investors much. Would be even worse for investors with TX id though obviously.

Also miners who like to attack/cheat satoshinonce can do this right now BTW. But I assume that adjusting the mining software to only use those specific nonces might take some work and I guess with the low max bet it's not worth it for them.



Ps, hope TrevorXavier doesn't mind we are going a bit off-topic here It's still somewhat on the same topic of faulty provably fair implementations though (:

You bring up a good point.

When I first published the side-channel attacks a couple years ago, some casino operators dismissed it by saying things like, "We would never cheat," or "if we did this, we'd get caught" or "if we were caught, we'd lose all our players," without addressing their implementations of provably fair. So, they are countering a cryptanalysis with a PR/marketing spin, which doesn't make sense.

By saying, "We would never cheat," without addressing their implementation, they are only offering a simple promise of fairness, which is no different than a non-provably fair casino.

Yeah, I read that. (just read don't think it is possible part too many times )

I wanted to know your opinion on everything except that part - If satoshinonce accepted investments, is such a risk entirely eliminated?




I think decentralized trust-less gambling/investing is very possible.




Er.. was saying, provably fair wouldn't be invented if we kept thinking - it will not solve all the problems and all we need to do is trust the casino owner.


(edited)

provably fair was invented for the player and imo the best invention in gambling business so why to do it away? please correct me if I am wrong

Yes, that's why I said "fast game"




I agree.

Although in theory in the future there could be true decentralized trust-less gambling/investing with sidechains and investors that run some program to sign transactions/bets on the fly (like JoinMarket.) That would mean all investors have to put their BR in a (own-controlled like their own computer) "hot wallet" though and it's not as fast as dice now. Also I am not sure how the random process would work (either dependent on miner or third-party like most ETH smart contract gambling atm.) So I am not sure how practical it will all be, but sounds like a technical interesting project when the time is there

If everyone is really going to trust the owners we could do away with the provably fair too.

let's say this problem is solved and investors can't be cheated by casino owners. it will not solve the hit n run option for a casino owner imo and this would mean that investors coins are always at risk

at the end the magic word will be trust (the casino owner)

This one http://satoshinonce.com/ (don't know if this is still running fine) appears provably fair to an investor?

I don't think it is impossible, it will just be slow. We need one variable that is not determined by the server or the client and cannot be influenced by either but becomes known soon-after like a block hash?

That's a great question. This is a common issue among crypto-developers. You may have heard the mantra from developers, "Write it, even if it breaks." Unfortunately, crypto-developers aren't afforded the luxury. If crypto is implemented and breaks, it can cause direct harm. Total losses, breached accounts, really bad stuff. Look at Meteor. They had SRP implemented but reverted back to bcrypt because maintaining the crypto code required far more resources that were best used elsewhere.

In a nutshell, I had penned an implementation a couple of years ago, had it in peer review but it quickly became cost prohibitive.

Granted, I can't speak for an organization that is interested in the research. It may end up being a benefit to all. Some time and resources to fully publish, maintain, and be there to actively improve the work.

I am pretty skeptical about that and I still don't think it's possible for a fast game like dice. But yeh, if you don't publish "how" then we cannot check it obviously (:

If the goal is to increase transparency and honesty, why would one hold it back?  Just curious. 

It's not like people are going to automatically jump at a new company that first introduces the method.

I have a fair method for investors – will publish in due time – but currently in talks with another group that wants to license it to be first-to-market.

Either way, it appears likely to be open-sourced.

Betting on sidechains (with 1s blocks) where investors are all part of each multi-sig ("smart contract") transaction(=bet) by running a program like JoinMarket.

Okay, no, currently that is not possible

Logs/code irrelevant tbh.

I once made an audit idea that was discussed again last month (here) but not really worth the effort.

Any suggestions on how to make this as transparent as possible?

Not a concrete solution, but what if trusted members were able to pop under the hood periodically and check the logs and back-end code?

It (Edit: Stunna's) is a valid point. There is no investor provably fair implementation yet. (I like the concept here. https://etherdice.io/ )



I always prefer nonce method except in Moneypot style cases.

Oh I see. I was thinking it was something else (to do with the shuffle thing).

I thought OP was making that point with:
when he was actually still talking about 30 and he fails to mention they don't need to track roll tendencies - just every single roll.

Just checking in with you, casinobitco, if RHavar provided enough information for you to examine shufflepuff in greater detail.


A Provably Unfair Blueprint

Here's what a malicious casino would do if they wanted to cheat.

#1: Take your standard roulette wheel and letter encoding.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36
0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z	A

#2: Convert the wheel to a point deck based on the desired optimization.

Here, we represent the wheel as a set of points. For illustration, we'll keep it simple and use a zero (0) as neutral and a one (1) for the wheel positions that favor the house. You could use weighted values, like -1 and 1 to show the exact deviation in favor of the house or player. I prefer 0s and 1s to stay aware of the count within a space (just a math thing).

Examples:

Optimize for Color (red/black)
0 000000 000000 000000 111111 111111 111111

Optimize for Green
1 000000 000000 000000 000000 000000 000000

Optimize for Third
0 111111 111111 000000 000000 000000 000000

For this example, I'll choose to optimize for color.

#3: Run shufflepuff with the desired seed space.

First, let's compare the seed space (2³² = 4,294,967,296) and the arrangement space (37! / 19! / 18! = 17,672,631,900). The seed space covers about 24.3% of the arrangement space (4,294,967,296 / 17,672,631,900). What does this mean? It means that there are some final shuffles that are unattainable if the house decides to optimize the deck. In roulette, we're drawing one "card" (number). To optimize, we want to push as many favorable shuffles for the house into the seed space, and push as many favorable shuffles for the player outside of the seed space (into the unattainable space). This seed space covers a relatively "large" portion of the arrangement space, so one would expect there to be optimization, but smaller optimization than in other games, such as blackjack.

Someone might say, "Wait, there are actually 37! possible initial decks in roulette." That's true, but since we're optimizing for color, we can cut down our search space by ignoring the order of the numbers and focus on the position of the colors. You'll see why in a bit.

As a toy example, let's reduce the seed space to something small, like 40. Fire up shufflepuff and you'll see this:

0000000000000000000111111111111111111: 16
0000000000000000001101111111111111111: 17
0000000000000000001111011111111111111: 18
0000000000000001000111011111111111111: 19
0000000000000001001101011111111111111: 20
0000000000000001001111011101111111111: 21
0000000000001001001101011101111111111: 22
0000000000001001001111011100111111111: 23
0000000000011001001111011100110111111: 24
0000000000111001001111011100110011111: 25
0000000001001001001101011100111111111: 26
0000000001001001001111011100110111111: 27
0000000001011001001111011100110011111: 28
0000000001111001001111011100110001111: 29
0000000011111001001111011100110001110: 30
...
0000111001001001001111011100110001110: 35

The last line indicates the arrangement and the number of seeds (out of 40) that are beaten. So, in this example, if we optimize for the house, the house will win 35/40, or 87.5% of the time.


#4: Partition the roulette encoding scheme and randomize.

For this instance, I'll optimize for black, meaning I want black to appear 87.5% of the time. So, I'll partition the encoding into red + green, and black:

Red + Green: "013579cegijlnpruwyA"
Black: "2468abdfhkmoqstvxz"

Now we randomize each encoding:

Red + Green: "Awp1yejr5c3ngi07u9l"
Black: "davhk4mtz82sbof6qx"


#5: Zip the shuffled encoding onto the optimized arrangement.

0000111001001001001111011100110001110 =
Awp1     ye  jr   5c  3n       g      i0     7u9      l
        dav   h   k    4   mtz8  2sb    of       6qx

Result: Awp1davyehjrk5c43nmtz8g2sbi0of7u96qxl

You can keep randomizing to create 19! * 18! = 7.788 x 10³² cold decks. Using this deck, or any under this optimization, results in black appearing 87.5% of the time, despite an expectation of 18/37 = 48.65%. There is no way for the client to randomize their seed enough to beat this optimization.

Granted, with a 2³² seed space, you're not going to get such a dramatic result. Additionally, even if you found a high optimization, you probably wouldn't play it often (tuck it away as your "nuclear" option).

Here's the big thing: You also have all the arrangements > 20 that also work well. They can also be randomized and used against the player. Again, the casino doesn't necessarily want to find the best deck, just a better deck.

It's also easy to optimize for red now. Just flip the red and black (leave green alone).


Let me know if you have more questions. Thanks for reading!

Addendum
Remember, the shufflepuff code does not adhere perfectly to any one particular casino, so while it will give you optimized decks for its configuration, the decks will fail if implemented. This is intentional.

For multi-draw results I see your point.  

the cut is never enough believe me and even with a reshuffle the player needs to be sure that the decks are exactly as they should be and no cards taken out or added

I think either works tbh.

don't think a cut will help but a reshuffle could help as in real life

Potential solution is to let the user "cut" the randomized set to determine the starting place.

Might be a bit of a UI nightmare though.

You will have to be a programmer to be able to see if the clientseed was really generated in a cryptographically secure way in your browser (after getting the serverseed hash already.)

That's why changing clientseed manually is still better.

That's also why the "nonce implementation" is preferred since you only need to change it once and u can make as many bets as you like. Not like the "per roll implementation" where you indeed have to change the clientseed every bet.





There is some more specific advantages/disadvantages to that, for example a script/bot should be able to work more easily with the "per roll implementation". Also in reality with the "nonce method" you make like 1000 bets but only verify that last 10 losing streak.. so still not perfect. But I really believe on average "nonce method" is better.

I guess the fix seems easy.

Now they use Fisher–Yates shuffle with Mersenne Twister RNG.

They should use Fisher–Yates shuffle with "modulo of sha256 RNG".

But TrevorXavier said he will still give his implementation, so we can wait for that too

yes this what we would like to see!

There needs to be a fix to eliminate this "deck stacking" and users need to avoid any casino that does not utilize the fix.

No doubt that some(not all) of these "provably fair" casinos have utilized a technique like this to "increase" the house edge....

Its funny to me since most bitcoin casinos offering BJ offer terrible rules anyway + human error, is that not enough for some of them...

There needs to be a fix to eliminate this "deck stacking" and users need to avoid any casino that does not utilize the fix.


Otherwise provably fair is just a fancy word while the casino robs you blind.  


Another thing that I have always been curious about is how can you tell for sure that the "randomly generated" client seed is really randomly generated..is there any way to really tell..such a pain to change it manually every time and if this post from the OP is all true it makes no difference.

It's really just a problem with *bad* shuffles.  After you shuffle an "initial deck" of cards, a good shuffle will give you a possible 52! arrangements (or as close to it as possible). 52! is a mind boggling big number ( 80658175170943878571660636856403766975289505440883277824000000000000 ) but if you're using a shitty shuffle, there will only be 4294967296 possible results, which small enough you can feasibly try them all and see if the initial shuffle is good, bad, great or terrible.

Yes. For every initial shuffle you try, there will be a ~50% chance, that it is more biased to the house than expected. So it's an extremely practical attack, in that sense. And you could also precompute a bunch of "bad shuffles" which you potentially serve to high-rollers. It's 100% transparent, so that's what makes it insidious.  The thing is that it's a weakness of provably fair systems that use this method, so they should simply be fixed.


But the impact however, is pretty minor I suspect. I'm guessing that BJ is going to be the most vulnerable game (because it draws so few cards), and I'd honestly be shocked if you can find an initial shuffle that gives the house more than an extra ~0.1% edge.  (Although I might be wrong, I'm just pulling a number from my ass)

It would probably gain interest from the peers and casino owners, seeing that there is a possibility that shuffle-based games could be exploited after all. I'm still a bit confused on how would that work exactly, given that I don't have a deep knowledge on how does shuffle-based games work technically.

OK, I follow that. Let's talk practical --- are there really 2^31 outcomes that are good for the house (only) in Blackjack, Roulette, Video Poker?

Still would love seeing some real proof where I can change the client seed to anything I want, and still get one of those 'rigged' shuffles; otherwise this is just a thread with a ton of people (not you, or the OP) chiming in who have no understanding of how math or provably fair works.

 

I think the original post is very well articulated, far better than I could, so I feel a bit bad trying to repeat it. But the point that some provably fair systems are kind of stupid and only allow 2^32 combinations -- which is small enough you can literally just try them all. If > 2^31 of the final outcomes are good for the house, then the house knows that it'll have an increased house edge by using that initial shuffle.

So really it's not a problem with provably fair, just bad ones. Provably fair systems like bustabit already prevent against precomputing a favorable initial seed. For a shuffling one, you just need to use logic that gives a shit load more possible final shuffles. (I recommend the pseudo code in my previous post, which shouldn't reduce the space at all)

I agree with you, because who sets the order and picks which "provably fair" roll goes in which order. We don't know when they are generated or even how. I mean sure they random but they can tip towards choosing a certain hash.

I was just referring to my version, moduloing a random 2^256 number by is going to be for all intents and purposes perfectly distributed.



Also, I think you're grossly overestimate the risk in releasing your code -- it's not a huge task to write, and I really doubt it's worth the effort to even implement (assuming you were a psychotic casino owner), unless you were running a 0 edge game. (If you assume that user play is loss-constrained, it's **better** for a casino to have a lower edge). That's not an excuse, and casinos should definitely fix it. But it's not like casinos are going to be scrambling to rip off players

I'm still not following: With the user providing a random client seed (which is used for the final shuffle); how can your shufflepuff algorithm predict with precision that it will serve up the rigged deck?

I'm not discounting a site like Bitzino (or even ours) couldn't rig shuffles, as both sites produce the first shuffle and client seed - but if the user changes the client seed (which they are absolutely always encouraged to do, otherwise what's the point of even playing a provably fair game?), how can you predict the final shuffle (with the new, random, client seed) would in fact still be 'rigged'?

So, maybe I'm not reading it correctly, but the idea is not to produce a deck that wins every single time, if that's what you meant by "100% success." Rather, to produce a deck that causes the player to lose more than the expected average. In other words, you're not looking to have a dealer 20 every time, just perhaps more often.

Imagine we're playing 6-deck blackjack described at the Wizard of Odds. For each hand, the net summarized win is as follows: player wins 42.42% of the time, pushes 8.48% of the time, and loses 49.09% of the time. What shufflepuff can do is create decks that incrementally perform like this:

Average: win 42.42%; push 8.48%; loss 49.09%
Iteration n: win 41.20%; push 8.50%; loss 50.3%
Iteration n + p: win 40.85%; push 8.62%; loss 50.53%
Iteration n + p + q: win 39.10%; push 8.75%; loss 52.15%

When you use iteration n + p + q, there will be seeds where the dealer loses (player wins), but the player will lose more often than before (on average). So, using this arrangement, the casino can permanently alter the house edge.

Yes, so that's part of the heuristic I mentioned earlier. There are games, such as roulette, which require play history. However, there are others, such as blackjack, that are exclusive. The exploit works regardless. In addition, you don't really need to account for 'strange' plays, as the goal is to reduce favorable cards for the player, or encourage favorable cards for the dealer. Since the dealer doesn't play strangely, the exploit works. Here's a brief overview:

Roulette

• Optimizations: favor one color over another; favor thirds; favor number; reduce instance of number, color, or third.
• Heuristic: Brute-force. The arrangement space is computationally feasible.
• Deployment: Requires at least one game played to stack decks.

Blackjack

• Optimizations: player receives bust hand (13-16); deny player ace; house starts with 10, Ace, or non-bust card; reduce splitting; reduce doubling; reduce dealer busts, and more
• Heuristic: Create translation decks using the seed space. Since most blackjack games average 6-7 cards total dealt, attempt to optimize by best-fit.
• Deployment: Mutually-exclusive. Exploit works regardless of prior play.

For blackjack, you're not necessarily attempting to combat random play (random hits, random doubles), but rather, encourage favorable cards to the dealer and encourage bad cards for the player. So, you're looking for arrangements that give the dealer an Ace more often than not, give the player a 6, reduce the likelihood of splitting, doubling, and so on. Beyond that, you'd want to allow for the house to make their hand (try to keep a slug of low cards beyond the 7th position of the final deck, etc.). You can also optimize to combat basic strategy and 'upgrade' the cold decks when prior play history suggests the player is playing this way.

Blackjack works due to the extremely large arrangement space. You're talking 416! / 128! / (32!)⁹ possible arrangements in an 8-deck game. Since your target is only 2³², that means you need to find an arrangement that works well against the 2³² / (416! / 128! / (32!)⁹) shuffles in the final space. The number is so small that most calculators can't even represent it. It's possible there exists an arrangement that beats all possible seeds.


Video Poker

• Optimizations: encourage dead hands for the first 10 cards; reduce royal flush, straight flush, and so on; allow for good primary hands (like four to a straight flush), but deny matching card, and more
• Heuristic: Create translation decks using the seed space. Reduce translations to first 10 cards and attempt a best-fit optimization.
• Deployment: Mutually-exclusive. Exploit works regardless of prior play.

This is just a partial list. I'll elaborate more when I publish the optimized decks. This is pretty much where I started when I attacked the problem.

Addendum: Also, remember, the goal of shufflepuff is to not discover the uber-optimized deck, just ones that perform better than others. So, a casino operator performing a random search would probably do well in the short term with shufflepuff vs. hiring a mathematician to construct a heuristic.

I think that would be extremely valuable... also, how would a 'rigged casino' account for games that have unexpected customer behaviors? Like hitting or staying in Blackjack, or going randomly red / black in roulette?

Not discounting what you're saying technically, but I just don't see how a rigged casino could account for these variables.

Thanks for the feedback!

I thought about doing a video, but didn't really know if it would cultivate interest. I'll rethink the idea. Might be nice seeing the exploit visually.

The last line of your (trevor) post hit me big. From the start, I don't really like playing shuffle-based games (like baccarat, card games or the likes), as I thought that they can be somewhat rigged. Well, turns out that I'm right on my thoughts after all, but with that I'd like to see a video demo of the exploit as "provably fair" casinos seemed to not be fair at all.

I'm intentionally waiting on this for a bit until players become aware of the exploit. If I were to drop the optimized decks right now, they could immediately be used to cheat players.

You can generate your own non-reference decks using the code I provided. Simply let it run. On a single-core machine, it takes less than a day to scroll through an arrangement. A few tweaks and you can go multithreaded and cut the time down significantly. For reference decks, you'll have to rewrite parts of it to conform to the target casino.

In roulette, for example, you will receive a deck arrangement and a number. The number corresponds to how many seeds were beaten. If the number exceeds the expected probability of the draw, then it is a partially-optimized deck.

I fully agree with you that a player needs to know if any exploit exists and decide himself to play at those casinos or not

thx again for your very interesting findings

I'd love to see some working examples of a 'rigged deck' in blackjack, baccarat, roulette, whatever - where the client seed has no effect on the end shuffle using Provably Fair Shuffle.

You're welcome! It's natural for any cryptographic mechanism to show weaknesses over time. They (almost never) get stronger. Eventually, they are replaced with modern versions, which I think will happen here as well.

If I were a card player, I would rather know that an exploit exists than not know and be silently cheated out of my coins.

thx for confirming it but to be frank I am not happy about your findings because players could stay away from those popular card games

You're right, JackpotRacer, the exploit works regardless of client seed. You could change the client seed every time with random data; the house will still win more often than expected if it uses an optimized deck.

Kinda like Crypto-Games.net does?

did I miss the point the OP did or you? I understood that OP said that even you change the client seed the casino has an advantage (if they want) in card games like BJ or Baccarat

Agreed Stunna... All players should change the client-seed when offered, and not trust the casino's version of it; regardless if they've been around forever (like Bitzino or PrimeDice), or been around since 2013 (Us).

Can you give us a list of casinos that use bitzeno?
I think it would be helpful

Thankd

Thanks! More results to follow. The code is in the wild, I suspect someone will rewrite it to conform to the reference implementation. I'll reveal the arrangements I found and the raised house edge here soon. Since they're "drop in" exploits, a casino can deploy them immediately, and I don't want to be the direct cause of players getting cheated.

I actually did hit the modulo bias quite often, since I'm searching the entire space. I think it's silly that bitZino even had a modulo bias. It's a casino. Quick and easy fix:

Adapted from (https://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator)

A player may actually hit the modulo bias quite often for some games, such as blackjack, since it requires 314 random numbers per round of 8-deck. The Fisher-Yates shuffle actually requires a uniform random distribution to result in non-biased shuffles. An extreme example: shuffle a deck but always use the number 5 as the random number.

Thank you!

It's more than that. I'm claiming that the shuffle-based games are actually not provably fair. This is a direct attack against the algorithm.

Here's why:

• On a mid-range CPU (like a Core i5), a casino can calculate a single arrangement in about 17 hours.
• Since it is not looking for the "ultimate" arrangement (just a better one), it can continuously search one arrangement at a time and update its "master list" of cold decks that result in a higher house edge.
• These deck arrangements, over time, will always perform better.

I have written a new implementation that I will share here soon. I won't go so far as to say that it is "perfect" (since there is no perfect crypto), but maybe "next generation"?

I don't think that's a great idea. You're better off by creating a random number stream like this:



(i.e. something along the lines of how dice sites currently generate outcomes.) The modulo-bias is so insigificant, that you could run it for a billion years and not hit a case of it. Anyway, instead of assigning a random number to each card and sorting you're better off sticking with a Fisher–Yates shuffle, which is proven to be perfect with no bias. (Which is a fancy way of saying, you loop through the deck of cards and for each card you generate a random index. Then you SWAP the current card, with the one at that index. And continue on your loop. Once you get to the end of the loop, you're guaranteed to have perfectly shuffled it.

The psuedo code from wikipedia:

Nice work! But I think you're missing out the most interesting part, in a game of X how much can this exploit raise the house?


Also regarding the exploit, this type of attack was first noticed a while ago (although in the context of bustabit):
https://bitcointalksearch.org/topic/m.8535291 who was able to raise the house edge by 0.2%.

Anyway, I ended up solving by mixing in the hash of a yet-unmined bitcoin
block (see: https://www.bustabit.com/faq#fair).

please let me state that I have no clue about the provably fair option and I see more and more that it is anyway not an easy task.

my point of view is that we as  casino owners don't want to cheat the players and don't want to be cheated by players. therefore I asked for the perfect way or best solution to offer a provably fair card game like BJ, Baccarat, Poker etc?

NLNico mentioned now that it could be like unique dice results and I am not sure if I understand this because BJ or Baccarat is played with 6 or 8 decks (reshuffled after each game) and up to 10 + cards could be dealt in a game. real BJ and Baccarat players are interested in the cards they get dealt and not in dice decisions. my question is if it would be like provably fair shuffled 6 or 8 decks?

sorry for my english and I hope you could understand my question

thx

Wow, I have never considered this, but it makes sense.

So basically all the major casinos that offer card games are not PROVABLY fair...

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 guess that could work. (Potentially modulo bias though?)

You could probably also loop all 52 cards and assign random numbers to them and sort it from high to low. The random number for each card would be calculated in same like seed/nonce way (with 1 more nonce), so a bit like 52 (unique) dice results.

How about something like this:

PseudoCode:

So take a "brand new" deck. Pick 1 card at random from the deck and put it at the top (or bottom) of a new deck. Continue doing this until there are no more cards left n the unruffled deck. The random card picked from the deck depends on the client seed and the nonce of the bet.
If you feel this isn't random enough, repeat the shuffle using the shuffled deck as the new unshuffled deck

Ah, right. So this seems like a limitation of MT19937. So if they would use MT19937-64, would this be a sufficient solution? This is still less than 52! but at least less feasible to calculate? (I guess there is no JS code for MT19937-64 though.)

Like JackpotRacer I am wondering what "the best solution" would be to get a provably fair random card deck.

I can imagine something like the "dice nonce method" but adding an extra nonce so it could calculate more numbers (since a "duplicate card" cannot happen, so might need to loop a bit more.) But this might get a bit heavy in performance the more unique cards you need

These kinds of statements just show the immaturity of some of the casino owners. It doesn't stongly suggest anything. Any of those casinos you mentioned before could have been losing legitly. Any of those casinos could have gotten lucky and could have a positive return on ev, and could still be taking a 10% cut by playing against the investors money. Beking being 140% on profit does not suggest the fact that you could not be cheating the investors and neither would losing suggest that you are.

Good catch, but sadly, the seed maxes out at 2³² – 1.

bitZino combines the server seed and client seed, hashes it with SHA256, but then only uses the first 8 bytes of it. So, the range is 0x0 to 0xFFFFFFFF. (FFFFFFFF)₁₆ = (4294967295)₁₀. They write about this in their techblog: https://techblog.bitzino.com/2012-06-30-provably-fair-shuffling-through-cryptography.html

Stunna always bashes crowdfunded bitcoin casinos.

I can see why but people are smarter now and no one is investing large amounts in new sites with questionable owners who are likely to scam (Dicebitco.in and dice.ninja).
I wonder what his honest opinion is on BetKing.io/me when it comes to trust and investing.

But your argument doesn't make much.
If the Profit/EV is high then it is far less likely that the owner has been cheating the investors. If the owner was cheating then the Profit/EV would be lower.

Of the 5 Bitcoin investment sites on dicesites.com only 2 are under EV and people could accuse them of playing against investors.

People think SafeDice is legit though and is just below EV because of their risky invest model and were unlucky.

I've never trusted Bitdice so I won't go into that.

BetKing.io has a profit/ev of 140% so it strongly suggests that there is no cheating going on of investors.
Good job it's also provably fair so you can prove the house hasn't cheated players too

I've proved over and over that your funds are safer in BetKing than any other crowdfunded casino and it is a fact that it is the most trusted.
Primedice is certainly more popular but Stunna doesn't secure as many Bitcoin of other users as BetKing does at one time.
Though he may very hold more than the whole of BetKing in his own personal wallet

Moneypot looks like it might be safe to invest in as a couple of their owners (not all) are respectable members of the community, though the owners have only had it for 5 months so who knows.

SatoshiDice you would think would be safe since they have been around a long time but it seems common knowledge that they have changed owners more than a few times.

In response to OP. That is an interesting claim and I will look in to it a bit more. It would be good to see some ideas of solutions to the problem.

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


OP says that even when the distribution of numbers in the "initial deck" is fair, the outcome can still be influenced to have a slightly bigger chance to have an outcome the house prefers. This could be done by calculating what the different client seeds do with a specific initial deck.


^ I am more curious about above. BitZino allows 32 "aZ09" characters (62^32?) as clientseed and the MT seed is a SHA256 based on that. Isn't that a lot more than 2^32? Maybe I misunderstand that part though.

True. Straight forward provably fairness is always better than complicated provably fairness.

this means that Black Jack, Baccarat, Poker etc are in danger to not be provably fair?

what would be the perfect provably fair implementation for those popular card games?

thx for the work you did

No wonder I always lost on online casinos 

Glad I am not a fan of table games



Can't agree more. I am not sure if many investors are aware of this possibility especially the ones with relatively high Profit/EV.



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?

Quite interesting read. Hopefully this will spark a change in the way sites implement their provably fair schemes regarding decks shuffling but I doubt it.
Thanks for sharing your findings. 

Thanks!

Edit: Thought about it some more... The answer is 'not exactly' (see new reply).

Totally right. You bring up another really good point. Using shufflepuff, we can feed it a truly fair roulette wheel (36 cards) playing red or black and still optimize the initial deck in a way that favors the house.

After a few minutes:

000000000000000000111111111111111111: 2496
000000000000000001111111111110111111: 2500
000000000000000010011111111111111111: 2526
000000000000000010111111011111111111: 2533
000000000000000010111111110111111111: 2538
000000000000000010111111111110111111: 2545
000000000000000011111111111110011111: 2546
000000000000000110111111110110111111: 2549
000000000000000110111111111110011111: 2553
000000000000001010111111011110111111: 2560
000000000000001010111111110110111111: 2565
000000000000001010111111111110011111: 2569
000000000000001110111111110110011111: 2573
000000000000010110111111110110011111: 2577
000000000000011010011111111110011111: 2581
000000000000011010111111010110111111: 2584
000000000000011010111111011110011111: 2588
000000000000011010111111110110011111: 2593

Anything above 2500 actually favors the house, despite the cards being in a "fair" distribution (18 red, 18 black).

Granted, advertising a 0% game would be silly and raise red flags, but an ultra-low edge would work well.

Pretty interesting

I always dislike those complicated shuffle-based provably fair methods anyway. For roulette/slots/whatever it should be easy to just use the "normal dice nonce method" and generate numbers/results based on that, right?


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 ) Unfortunately they still didn't improve this.

Very true, with normal online casinos I think this usually isn't as much of a threat as a 5-15% edge will simply rake in tons of profit for the owners. But with many bitcoin casinos the operator can claim an ultra low edge to drag in volume but the actual edge would be multiple times that if they aren't playing fair.

Another important threat in the bitcoin space is investment based sites, there's absolutely no way to know if the owners will play against the house and steal from investors in an undetectable manner. It's this type of theft along with what you outlined in your post that are major threats to this community because the sites that do this will never get caught. I'm sure many of us have known people in real life who we could trust in a room with a million dollars and a video camera and they wouldn't touch a single bill, but when you remove the camera from the equation you'd often get a different result.

Hi Stunna! Thanks for the reply.

You're right, the post excludes dice sites.

For other casinos, however, there is no amount of randomization that the player can do to prevent the attack. Even entering their own seed won't help. The optimized shuffle will win more often than expected.

A quick example of roulette using a pretend seed space of 5000 (0 - 4999) and running the code:

0000000000000000001111111111111111111: 2561
0000000000000000011111111111101111111: 2562
0000000000000000100111111111111111111: 2590
0000000000000000101111110111111111111: 2599
0000000000000000101111111101111111111: 2605
0000000000000000101111111111101111111: 2611
0000000000000001101111110111101111111: 2613
0000000000000001101111111101101111111: 2619
0000000000000001101111111111100111111: 2623
0000000000000010101111110111101111111: 2624
0000000000000010101111111101101111111: 2630
0000000000000010101111111111100111111: 2634
0000000000000011101111110111100111111: 2636
0000000000000011101111111101100111111: 2642
...
0000010111000110111110101111000011100: 2743

I stopped after a few moments. According to this setup, the probability of a win (for the house) is (19/37) = .5135. However, the last permutation wins 2743/5000, or .5486. We now have an arrangement that will always result in an average higher win rate. There is nothing the player can do (with this implementation) to overcome the optimized shuffle.

Provably fair is usually only as strong as the reputation and trustworthiness of the casino. Dice isn't as vulnerable to the attack you mentioned as users can roll over/under and use unpredictable multipliers but you still raise a valid concern, any website can recognize a pattern and plant a seed that makes the player more likely to lose. That's why it's important to set your own custom seed and when re-randomizing you should write in your own seed rather than let the website hand one to you.

Witty

(Due to space constraints, this is highly abridged. I'll post a more detailed analysis on GitHub with the sample and optimized code shortly.)

Any shuffle-based provably fair casino that used bitZino as a reference implementation can exploit players.

A few years ago, I published an analysis of side-channel attacks on bitZino's provably fair method. It received a warm response. Today, I present a direct attack against the method. I call it "shufflepuff" — a tool a casino can use to optimize decks against players, effectively creating cold decks.

There are many recent, modern casinos that can deploy this exploit.

Here are the claims:

• Casinos can choose initial decks that perform strictly better against other initial decks, regardless of any Mersenne Twister seed.
• The result of the game is verifiably "provably fair" without compromising any code.
• The exploit can permanently alter the house edge of the game beyond expected outcomes.
• Due to the large arrangement space, the exploit is effectively undetectable. At the very least, refutable.

Woah. Pretty strong claims, eh? I'll explain it in a little more detail. But I'll assume you're familiar with how this provably fair method works. Please see bitZino's if you need a refresher (https://bitzino.com/about/fair). This attack applies to any casino that derives its method in a similar fashion.

You, as a player, have no ability to determine the actual Mersenne Twister seed. You can influence it, but the final seed is indirectly attributed to your client seed. However, the casino is free to determine the initial shuffle. It can be whatever they want. There is no guarantee that this shuffle (we'll call it initial deck from now on) is in any way random, and this is where the exploit begins.

In a nutshell, the house knows that the final shuffle will be one of 2³² possible shuffles. Since the initial deck space can be astronomically larger than the final shuffle space, the house simply needs to find an initial deck that performs well against as many final shuffles as possible.

How do we determine the optimized, stacked decks?

Let's try roulette, since it has the smallest search space. In the real world, it's a wheel game, but casinos like bitZino treat it like a card game nonetheless.

• First, we degenerate the deck into point-values based on the outcome we want. For example, if we want to optimize the deck for red, we convert all the red cards to +1 and the rest (including green) to 0.
• We arrange the point deck in lexicographic (sorted) order: { 0000000000000000000111111111111111111 }.
• For all permutations (without repetition), perform a Fisher-Yates or Durstenfeld shuffle with all possible Mersenne Twister seeds (which range from 0 to 2³² – 1). Add the first value of the shuffle to the rolling count.
• Compare two permutations. If one has a higher count than the other, it is strictly better than the other. Meaning, a casino can use it to permanently alter the house edge.

Shufflepuff Code (C++)


Things to Note

• This is a proof-of concept and intentionally different than bitZino. It is not a direct one-to-one implementation, so you will need to modify it to discover actual optimized shuffles. After some time has passed (to spread the word), I'll post the optimized arrangements I found that will work as a "drop-in" exploit for bitZino and others.
• The program will output the permutation and the number of seeds that it beat. Divide the number of seeds beaten by the seed space (plus 1) to get the probability of a win. If this exceeds the theoretical expectation, then it is a partial optimized arrangement.
• This code is not optimized for speed. It will take a long time (17+ hours) to calculate a single 2³² seed space. If you want to see it in action, you can lower the SEED_SPACE (to 5000, for example) to get the idea, although the results are not valid. The code can be adapted for distributed or parallel computing.
• BitZino also suffers from a modulo bias in the way it calculates random numbers. See source (https://bitzino.com/about/fair), line 801, so the shuffle algorithm in the C++ code also needs to be hand-written to mimic this.

Implications

• Once an arrangement has been found, it can be easily masked to prevent detection. In the example, the arrangement only represents the position of red and blacks, but a casino can fill it with any red or black card, effectively producing shuffles that appear different.
• The casino presents the shuffle first, but it can learn from subsequent play. A player who consistently plays red or black (or green) can be exploited in the next round.
• A casino doesn't need to find the most optimized shuffle, just one that beats the theoretical expectation. So, a nefarious casino would collect many optimized shuffles on a rolling basis, making it effectively undetectable.
• The shuffles can be used to help you win as well. For example, the house could produce good shuffles to help dust bettors win, in the hopes they bet more (where they could then be cheated with bad shuffles for more bitcoin).

I know this is a lot to digest in the limited space I have. I tried to distill a proof and large distributed computing code into something simple, so more to come. I'll be around for a few hours to answer some questions. Thanks for reading!

Update
Added "A Provably Unfair Blueprint" in this thread. (https://bitcointalksearch.org/topic/m.15071925)