Topic: Breaking: Shuffle-based Provably Fair Implementations Can Cheat Players (proof) - page 3. (Read 4659 times)

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'?