Breaking: Shuffle-based Provably Fair Implementations Can Cheat Players (proof)

[TrevorXavier]

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.

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.

[ndnh]

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.

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


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.

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

I thought OP was making that point with:

Except for the fact that your roll tendencies can be tracked. Maybe you ALWAYS go "Higher than 8".

So what if pocketdice's 30 "random numbers" have 9 1's, 7 2's 5 3's, 5 4's, 3 5's and 1 6?

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.

[ndnh]

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.

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

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.

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

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.

My argument is that if the Profit/EV is higher than 100%, the owner is more likely to cheat the investors than if it is lower. It will also make it largely unsuspicious (and of course undetectable anyway) than otherwise.

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 always prefer nonce method except in Moneypot style cases.

[Dogedigital]

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

**condensed quote

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?

[NLNico]

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.

[TrevorXavier]

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.

[Dogedigital]

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.

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.

[NLNico]

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

[TrevorXavier]

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.

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.

[ndnh]

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

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?

[JackpotRacer]

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

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?

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)

[ndnh]

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

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?

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)

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

[NLNico]

I don't think it is impossible, it will just be slow.

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

.. for a fast game like dice

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

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

[JackpotRacer]

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

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?

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)

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

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

[ndnh]

I don't think it is impossible, it will just be slow.

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

.. for a fast game like dice

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?

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

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

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)

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

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

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)

[TrevorXavier]

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

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.

[NLNico]

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

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

[koshgel]

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

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.

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.

[RHavar]

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

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.

yeah, wtf? I never heard of this site, but they seem to do it in the worst possible way. As you note, it allows a miner to costlessly cheat the site. (miners can have a fixed nonce, and purely fiddle with the coinbase) and theoretically allow the site to cheat players (I doubt this would happen though, if they were sophisticated to know how to cheat players they would realize players can do the exact same attack against them).

Making bets on the last (couple?) digit of the block hash seems a lot smarter, as now miners have to discard blocks in order to cheat, which is rather expensive.

[RHavar]

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.

pevpot had an extremely robust system that would make it provably fair for investors: https://web.archive.org/web/20151213003346/https://www.pevpot.com/provably-fair

But like all on-chain games, is doomed by a poor UX