Impossibility of a multi player provably fair scheme?

[syskall]

Hi all,

I've been trying to develop a provably fair scheme that would work with multiple players (e.g. multiple players each betting on the same coin flip). After doing some research[0][1], I'm drawn to the conclusion that such a scheme is impossible to achieve.

As with the 2 party provably fair scheme, we assume in our model that the "House" knows how each players will bet in advance (because players can be predictable in practice). The coin toss can be represented as 0 = Heads and 1 = Tails. The final outcome is determined by adding up all the coin tosses, checking if it's even for Tails and Heads otherwise (this is equivalent to XORing all the tosses). A commitment is a secure one way function (e.g. sha256(nonce + value)).

1) House, Alice and Bob each pick a coin toss and share a commitment to all (so that they can't alter it during the reveal phase)
2) Alice reveals coin toss
3) Bob reveals coin toss
4) House reveals coin toss

So far so good: all of the participants had an input in the coin toss and none of them could have influenced it somehow in their favor.

The issue arises when Bob is in fact a puppet of the House (e.g. Bob is a fake player controlled by the House). After step 2 when Alice reveals her coin toss, the House knows the final outcome (since it already knows Bob's coin toss). If the outcome is unfavorable (e.g. Alice would win her bet), it could make Bob abort the protocol (e.g. "oops, wifi disconnected"). We either have to continue and ignore Bob's coin toss or we cancel the round.

- If we ignore Bob's coin toss, the House now has a 50% chance to lose instead of 100% if Bob hadn't aborted.
- If we cancel the round, the House can never lose: it could just always have Bob abort when it knows it is going to lose.

There appears to be solutions to this problem if

- Majority of players are honest (e.g. using Shamir secret sharing). but that's an overly optimistic assumption from the point of view of a player.
- A trusted third party is allowed.

Possible line of research: each player picks multiple coin tosses instead of just one. Instead of revealing it all at once, use a fair key exchange protocol to exchange the tosses... This would have some drawbacks as well.

Feedback and thoughts appreciated.

0) https://www.cs.bgu.ac.il/~ilanorv/CryptoFinal.pdf

1) https://link.springer.com/chapter/10.1007/978-3-642-14623-7_29

edit: this reddit thread appears to confirm what I thought: https://www.reddit.com/r/crypto/comments/95d8rd/multiparty_random_number_generation/

[crwth]

Wouldn't it be the same as betting on the same seed and having only two outcomes? I don't think it's impossible, though.

Possibly you could use that Shamir's Secret Sharing parts would be automatically given to the players. After that, they can verify the two that it's part of one game. It is preventing alterations or something. Have the tiniest elements of the secret to a minimum of two or three.

Or maybe have it like a trusted computer that would not cheat and act as a judge or an arbiter towards the game — giving another part of the secret making a minimum of three.

[PrimeNumber7]

The house can have a potentially unlimited number of sockpuppet players. I also don't think the majority of the players being honest will solve your problem. If there is a single sockpuppet player, the house can choose between two outcomes, and will choose the one with the lessor loss, or greater profit.

[LoyceV]

I've been trying to develop a provably fair scheme that would work with multiple players (e.g. multiple players each betting on the same coin flip). After doing some research[0][1], I'm drawn to the conclusion that such a scheme is impossible to achieve.

Have you seen Bustabit's solution? They have many users bet on the same bet all the time. Although the site knows the outcome ahead for 10 million rolls, they can't change it anymore to adjust for players' behaviour.

See: Bustabit (v2) Seeding Event

[syskall]

Wouldn't it be the same as betting on the same seed and having only two outcomes? I don't think it's impossible, though.

Possibly you could use that Shamir's Secret Sharing parts would be automatically given to the players. After that, they can verify the two that it's part of one game. It is preventing alterations or something. Have the tiniest elements of the secret to a minimum of two or three.

Or maybe have it like a trusted computer that would not cheat and act as a judge or an arbiter towards the game — giving another part of the secret making a minimum of three.

The problem is that if you use Shamir's Secret Sharing and there is a majority of dishonest players, they can collude to reveal your seed before picking theirs (giving them the ability to effectively pick the game outcome). There are indeed solutions using a trusted third party.

[syskall]

I've been trying to develop a provably fair scheme that would work with multiple players (e.g. multiple players each betting on the same coin flip). After doing some research[0][1], I'm drawn to the conclusion that such a scheme is impossible to achieve.

Have you seen Bustabit's solution? They have many users bet on the same bet all the time. Although the site knows the outcome ahead for 10 million rolls, they can't change it anymore to adjust for players' behaviour.

See: Bustabit (v2) Seeding Event

No, I haven't seen. The ability to immediately verify a bet was fair is part of the appeal for single player provably fair schemes. That said, it's true that by relaxing this requirement (e.g. having to wait a while before verifying a bet), it'd be possible to show that a site wouldn't have been able to adjust for a player's behavior.

I will have a look at Bustabit's solution, thanks for the reference.

[crwth]

The problem is that if you use Shamir's Secret Sharing and there is a majority of dishonest players, they can collude to reveal your seed before picking theirs (giving them the ability to effectively pick the game outcome). There are indeed solutions using a trusted third party.

Isn't it that the seed or the part of that secret is only going to be given to the players and they could just verify it and not change the outcome itself?

From what I understood with Shamir's secret is that you have a secret and split it into other secrets with having the same size as the original. You cannot have the whole secret to be reconstructed without all the parts right? Or having the minimum threshold which you will define.

Let's say every game, you have an arbiter and 3 players. Making which threshold be 3. I think n - 1 with regards to the number or Total Players would be sufficient. n is the total number of players.

Even if you have 2 dishonest players, the total secret cannot be reconstructed unless you have that piece of the arbiter.

Giving power to that arbiter could be the crucial part and just like you included, trusted third party would be allowed.

[StackGambler]

bustabit does this perfectly with a reverse SHA-256 hash chain. Each game can be instantly verified, and it's multiplayer.