[oh_sigh]

Is this a problem with commitment schemes?

I want a heads to come up. I add a couple of hacked members to the group, so there are 3 honest members, and lets say 3 coordinated dishonest members.

Everyone shares their commitment hash, and the dishonest members share their actual commitments amongst themselves. Once everyone has the commitment hashes, the 3 honest members broadcast their commitment. The three dishonest members now have everyone's commitments, but honest members only have other honest member commitments. Dishonest members compute the ultimate value - if it turns up heads, then they just share their commitments with everyone, and the final answer is heads.

If it turns up tails, then the dishonest members compute possible permutations of various dishonest members dropping out and never sending their commitments. So maybe if dishonest member 1 drops out, the resultant value from just the group of 5 would be heads. So dishonest member 2 and 3 share their commitments and dishonest member 1 goes offline.

So, this system will work when it is composed of only people you trust, but will not work when it may be composed of people you don't trust. And if you trust everyone in it, why go through this process in the first place? And if you decide that when someone drops out and doesn't share their commitment, you just have to rerun the algorithm, then you have just given a very easy way to give the dishonest people a way to spike your coin flipper, so that no one can ever get a value out of it, or the dishonest members can just keep dropping out until they encounter a round where the final value is determined to be heads.

[leetbulb]

1. All members generate a random value (high entropy).

2. All members submit a hashed value of that random value (the commitment).

3. All commitments are distributed to all members. At this point, no more commitments may be submitted.

4. All members reveal their random values to each other and validate each value against its hash.

5. All values are then used to deterministically calculate the coin flip.

A dishonest member will not receive any values used in the coin flip calculation before step 4. If a member decides to change their random value, the hashed value / commitment will be invalid.

[oh_sigh]

Sorry, I think I may have used the wrong terminology in my post above. I was referring to the random value as the 'commitment' and the hash of that as the 'commitment hash'.

But what I proposed doesn't require anyone to change their random value. It relies on the fact that step #4 does not happen instantaneously, and honest clients will send their random values as soon as they transition into step #4.

So from my above example, the process reaches step #4 as normal - all honest clients send out their random values, and all dishonest clients wait. Once the dishonest clients have all of the honest random values, they can now determine what the result for #5 will be(because they know all other dishonest client random values because they are colluding, along with all honest client random values), whereas the honest clients cannot do so, because they don't know the random values from the dishonest clients.

So at that point(half way through step #4), dishonest clients can then determine if they want that value to be the end result, or if some of them should drop out(never broadcast their random value), in order to modify what everyone determines to be the final value from step #5.

[leetbulb]

I have implemented an extremely similar protocol for a side project game.

In my implementation, step 4 happens in two phases:

4a. All members submit their secret values to the server.

4b. Once all secret values are submitted, they are all sent to each member at once.

This ensures that members cannot determine the outcome before anyone else.

What you are describing could actually be an issue if there is no server involved, however something like commitment encryption (rather than hashing) utilizing secret sharing could help resolve this issue in a p2p environment.

Another option would be that all possible outcomes are randomly shuffled with their positions encrypted and distributed to all members prior to the game beginning.

My protocol implements the latter... all possible outcomes are encrypted and publicly available on IPFS to members before and after the game.

[wildmanx]

Only after step #5 is the value valid, i.e., after everybody has broadcasted their value. This includes everybody who broadcasted anything in previous stages. As long as the dishonest clients have not all broadcasted theirs, the procedure is not done and there is simply no consensus yet.

One could argue that the dishonest clients could use this to basically abort the procedure before the value is determined (by not broadcasting their values). But once the procedure is complete, being dishonest does not mean anything.

[ummonk]

Yup. It's pretty gameable using collusion due to the ability to refuse to reveal.