Is it possible for devices on an online group chat to toss a coin without trusting each other and the server?

1. Decide on a random N and what tails (even) and heads (uneven) mean.

2. Each party generates a random number

3. Combine the numbers with a conmutative operation of some sort, the harder the operation the better.

4. Take the hash N times. (Can be done independently by each participant)

(4.5) optional: for extra robustness, do some hard-to-calculate transformations to the result of 4. (Can be done independently by each party)

5. The final result is either uneven or even === coin toss. (0 will be treathed as even*.*)

This is not infalibe, one party could get all the numbers a precalculate a answer to get a specific result but they will need to randomly try numbers. adding some timing constrains, using big numbers and hard operations would make that sort of attack not really practicable.

Nice question, had fun thinking about it!

If the random number comes from an event beyond the control of the group or server, why not? For example, many Keno games post results online. It is agreed by all parties that when the server says, "flip", the next number generated by the Keno game will have modulus 2 applied to it (even or odd), resulting in the coin flip - 0 for tails and 1 for heads. Everyone can see the source of the number independent of the server and no party has control over the source of the number.

Alternately, any independent source of true random numbers that are time stamped can be used. The agreement is that the server will specify a time in the future and the number generated closest to that time will be used. The number is independently verifiable and out of the control of all parties.

Everyone generates a one-use key pair to for encryption. Starting with plaintext values, each player in turn encrypts the values they are given, sorts them randomly, and passes those to the next player. At the end, we have randomly sorted numbers encrypted by everyone. The first value is selected as the result. Everyone publishes their one-use private keys so that selection can be decrypted. The other selection is also decrypted to confirm it is the opposite value, otherwise the result is discarded.

All participants select their own random whole number and publish it to the group. All participants add all the numbers together. The result is either odd or even (heads/tails) and everyone arrives at the same result independently.

Coin flipping

Suppose Alice and Bob want to resolve some dispute via coin flipping. If they are physically in the same place, a typical procedure might be:

Alice "calls" the coin flip,
Bob flips the coin,
If Alice's call is correct, she wins, otherwise Bob wins.

If Alice and Bob are not in the same place a problem arises. Once Alice has "called" the coin flip, Bob can stipulate the flip "results" to be whatever is most desirable for him. Similarly, if Alice doesn't announce her "call" to Bob, after Bob flips the coin and announces the result, Alice can report that she called whatever result is most desirable for her. Alice and Bob can use commitments in a procedure that will allow both to trust the outcome:

Alice "calls" the coin flip but only tells Bob a commitment to her call,
Bob flips the coin and reports the result,
Alice reveals what she committed to,
Bob verifies that Alice's call matches her commitment,
If Alice's revelation matches the coin result Bob reported, Alice wins.
For Bob to be able to skew the results to his favor, he must be able to understand the call hidden in Alice's commitment. If the commitment scheme is a good one, Bob cannot skew the results. Similarly, Alice cannot affect the result if she cannot change the value she commits to.

1. Everyone tosses three coins, and posts it in the chat
   • If a player tosses three of the same, they have to toss again.
2. Everyone chooses the mode coin from their neighbour, and adds it to their stack
3. Each player, with 3+N coins, picks the mode coin in their own collection.
   • Ideally: the player's own bias, is outweighed by the other player's biases.
4. The final coin is the mode of all players coins.

from numpy import median
from pprint import pprint

players = {"p1" : [1,0,1],  ## playing fair
           "p2" : [0,0,1],  ## cheating
           "p3" : [1,1,0],  ## cheating
           "p4" : [1,1,0],  ## cheating
           "p5" : [0,0,1]}   ## playing fair
print("Initial rolls:")
pprint(players)

get_mode_coin = lambda x: int(median(x))
get_all_mode_coins = lambda x: [get_mode_coin(y) for y in x]

for play in players: ## Players add the mode coin from their neigbours
    players[play] = players[play] + get_all_mode_coins(players.values())
print("First picks:")
pprint(players)

for play in players: ## Players collapse their collections to mode
    players[play] = [get_mode_coin(players[play])]
print("Last modes:", players)

print("Final choice:", get_mode_coin([x for x in players.values()]))

Which as you can see, is no better than simply picking the median coin from the initial rolls. I thank you for wasting your time.

If you're interested in that kind of problems, here's some pointer: https://en.m.wikipedia.org/wiki/Secure_multi-party_computation

Everyone throws a number at the same time, the result is the checksum/sum of the throws. Server throws first publicly, keeps the device Numbers secret until the last throw. It's not perfect, but it'll do.

In a scenario completely without trust, no - in a scenario with minority proportion of untrusted actors, yes.

I think the responses with an encrypted/committed guess being made public, a public result, and then a reveal of the key, have it right for the scenario of people making guesses as to the result of a flip.

Re-reading your question, though, refers more to there being an agreed result for a group of people as opposed to checking a guess. I think this would require a bit of a variation. The trivial method would be to use the previous method and assign "correct guess" to heads and "incorrect guess" as tails, but this only works if you don't believe that any two members are colluding with each other.

Another solution would be to have each member generate a random number and encrypt it, and post the encrypted value. After all have been posted, everyone posts the key to decrypt their number, and adds up all the numbers together and takes the sum modulo the number of options (2 in the case of a coin) and matches it with a predetermined mapping. For instance, if 1 is heads and 0 is tails, and the sum of the numbers is 63752, 63752 % 2 = 0 which is tails.

There are a couple gotchas to prevent errors. There has to be an agreed upon maximum number which is one less than a multiple of the number of options. For instance, if random numbers are allowed from 0 to 2 inclusively, there is a bias towards tails (0 % 2 == 0, 1 %2 == 1, 2 % 2 == 0). The other is the encryption algorithm would need to be chosen such that multiple keys can't easily be created to provide different valid decrypts. This would also likely require some padding to the clear text, which could be achieved by some member of the group posting some arbitrary text first, and then all members appending that text to their number before encrypting it.

Permanently Deleted

The risk of a pair collision should be mitigated by all pairings being random. And both pairs announce who they pair with so that they can't lie.

But collusion is possible if they happen to pair with another cheater which is not guaranteed unless every is a cheater.