Bitcoin Forum
May 11, 2021, 04:43:42 AM
 News: Latest Bitcoin Core release: 0.21.1 [Torrent]
 Home Help Search Login Register More
 Pages: [1]
 Author Topic: Impossibility of a multi player provably fair scheme?  (Read 243 times)
syskall
Newbie

Offline

Activity: 20
Merit: 13

 August 27, 2019, 09:45:16 AMLast edit: September 02, 2019, 04:10:57 AM by syskallMerited by Zedpastin (6), LoyceV (2), bones261 (2), ETFbitcoin (1), o_e_l_e_o (1), PrimeNumber7 (1)

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

1620708222
Hero Member

Offline

Posts: 1620708222

Ignore
 1620708222

1620708222
 Report to moderator
1620708222
Hero Member

Offline

Posts: 1620708222

Ignore
 1620708222

1620708222
 Report to moderator
1620708222
Hero Member

Offline

Posts: 1620708222

Ignore
 1620708222

1620708222
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1620708222
Hero Member

Offline

Posts: 1620708222

Ignore
 1620708222

1620708222
 Report to moderator
1620708222
Hero Member

Offline

Posts: 1620708222

Ignore
 1620708222

1620708222
 Report to moderator
1620708222
Hero Member

Offline

Posts: 1620708222

Ignore
 1620708222

1620708222
 Report to moderator
crwth
Copper Member
Legendary

Offline

Activity: 1666
Merit: 1023

Everybody needs a PRO License ;) https://gunbot.ph

 August 28, 2019, 02:40:46 AM

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.

 .BEST..CHANGE.BEST EXCHANGE RATES ➊➊➊➊➊ .........BUY & SELL........ ..............FAQ............AFFILIATE PROGRAM ➊➊➊➊➊ ░██████████████████░█████████████████████████████▀░░░████████████████░░▄███████████████▀▀░░▀▀██████████████▄▄░░▄▄████████████████░░██████████████████░░██████████████████▄▄█████████████████████████████░██████████████████░ ░██████████████████░████████████████████████████████▀▀▀█▀██████░▀█████▀░░░░░▀██████▌░░░▀▀▀░░░░░░████████▄░░░░░░░░░░░█████████▀░░░░░░░░░███████████▄░░░░░▄▄███████████▄▄▄▄███████████████████████████████░██████████████████░ ░██████████████████░███████████████████████████████████████████████████▀▀░░▐███████████▀▀░░▄░░░█████████▀░░░▄█▀░░░▐██████████▄▄█▀░░░░░█████████████▌░▄▄▄░▐██████████████████████████████████████████████░██████████████████░
Copper Member
Hero Member

Offline

Activity: 812
Merit: 986

Am I real?

 August 28, 2019, 06:44:28 AM

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.

 ████████████████████████████████████▀▄▄▄▄▄██▀▀█████████████▀▄█▀▀▄▄▄▄▄▄▄▀▀▄▄▀█████████ █▀▄███████████▄▀█████████▄█ ███████▀ ██████ █ █████▀█ ███  ▀▀█  ▀██████ █ ████ █ ████▄▄      ▀▀▀██ █ ████ █ █████▌        ▄██ ███████▄█ █████▄▄   ▄▄███ █▀███████▀█▄▀█████▌  ▀██▀▄█ █████████▄▀▀▄▄▀▀▀▀   ▄▄█▀▄█████████████▄██▀▀▀▀▀▀█████████████████████████████████████ .R O O B E T. ▄███▄▄█████▄█████████▐███▄▄▄███▌███████████████▀▀▀███████████████▄█████████████▄█████████████████▄▄▄▄    ███████    ▄▄▄▄▄██████▄   █████   ▄██████▄█████████▄███████▄█████████▀███████████████████████▀ P L A Y   S L O T S   o n    CRYPTO'S FASTESTGROWING CASINO ‎★ ‎★‎ ★ ▄▄███████▄▄▄█████▀█▀█████▄████▀▀▀ ▀ ▀▀████████████  ██  ▐████████████      ▀████████████  ███  █████████▄▄▄   ▄▄▄████▀█████▄█▄█████▀▀▀███████▀▀▄▄▄▄▄▄▄▀▀███████▀▀ ▄▄███████▄▄▄██████▀██████▄███████▀ ▀██████████████     █████████████▄     ▄████████████▄▀▄▄▄▀▄████████████▄   ▄██████▀██████▄██████▀▀▀███████▀▀▄▄▄▄▄▄▄▀▀███████▀▀ ▄▄███████▄▄▄█████████████▄███████▌ ▐███████████████  ██████████████▀▀   ▄▄██████████████  ███████████████▌      ▄████▀█████████████▀▀▀███████▀▀▄▄▄▄▄▄▄▀▀███████▀▀ L I T E C O I N                  DEPOSITS & WITHDRAWALS      A V A I L A B L E   N O W ! ▄▄████▄         ▄▄▄▄▄▄▄▄████▀▀████     ▄▄█████████████▄▄  ███    ▄█████████████████▄███   ▄█████████████████████   █████████████████████   █████████████████████   █████████████████████  █████████████████████▀ ███▀█████████████████▀███▀ ▀▀█████████████▀▀███▄▄▄▄███▀▀▀▀▀▀▀▀▀█████▀▀ ..PLAY NOW..
LoyceV
Legendary

Offline

Activity: 2212
Merit: 7942

 August 28, 2019, 04:53:16 PMMerited by Zedpastin (2), ETFbitcoin (1), crwth (1)

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

 ░░░░░▄▄██████▄▄░░▄████▀▀▀▀▀▀████▄░███▀░░░░░░░░░░▀█▀████░░░▄██████▄▄░░░██░░░░░█████████░░░░██▌░░░░█████████████████░░░░█████████████████░░░░░███████████████████▄░░▀██████▀░░░████▀█▄▄░░░░░░░░░░▄███░░▀████▄▄▄▄▄▄████▀░░░░░▀▀██████▀▀ .ChipMixer.{ MIXING REINVENTED FOR YOUR PRIVACY #.ChipMixer. ░░░░░▄▄██████▄▄░░▄████▀▀▀▀▀▀████▄░███▀░░░░░░░░░░▀█▀████░░░▄██████▄▄░░░██░░░░░█████████░░░░██▌░░░░█████████████████░░░░█████████████████░░░░░███████████████████▄░░▀██████▀░░░████▀█▄▄░░░░░░░░░░▄███░░▀████▄▄▄▄▄▄████▀░░░░░▀▀██████▀▀
syskall
Newbie

Offline

Activity: 20
Merit: 13

 August 29, 2019, 01:27:01 PM

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
Newbie

Offline

Activity: 20
Merit: 13

 August 29, 2019, 01:32:27 PM

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
Copper Member
Legendary

Offline

Activity: 1666
Merit: 1023

Everybody needs a PRO License ;) https://gunbot.ph

 September 02, 2019, 05:15:56 AM

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.

 .BEST..CHANGE.BEST EXCHANGE RATES ➊➊➊➊➊ .........BUY & SELL........ ..............FAQ............AFFILIATE PROGRAM ➊➊➊➊➊ ░██████████████████░█████████████████████████████▀░░░████████████████░░▄███████████████▀▀░░▀▀██████████████▄▄░░▄▄████████████████░░██████████████████░░██████████████████▄▄█████████████████████████████░██████████████████░ ░██████████████████░████████████████████████████████▀▀▀█▀██████░▀█████▀░░░░░▀██████▌░░░▀▀▀░░░░░░████████▄░░░░░░░░░░░█████████▀░░░░░░░░░███████████▄░░░░░▄▄███████████▄▄▄▄███████████████████████████████░██████████████████░ ░██████████████████░███████████████████████████████████████████████████▀▀░░▐███████████▀▀░░▄░░░█████████▀░░░▄█▀░░░▐██████████▄▄█▀░░░░░█████████████▌░▄▄▄░▐██████████████████████████████████████████████░██████████████████░
StackGambler
Full Member

Offline

Activity: 378
Merit: 100