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.Or they can just talk to each other and resolve the dispute
In a scenario completely without trust, no - in a scenario with minority proportion of untrusted actors, yes.
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.
Specifically one of the imperfections is that the server and players are not trusted. If a player doesn’t like the result, they could claim the server lied about what number they had picked, or the server could actually lie. The remaining players wouldn’t know which one is telling the truth.
Your scenario assumes a trustworthy server that won’t manipulate the secretly held ledger of throws - it also doesn’t seem resilient to even a single bad actor client as there isn’t a clear way for the server to choose a result (though maybe your imagining everyone submitting a 1 or 0, summing those numbers and then mod 2ing the result?)
Edit, actually to that point OP - it’d help to know what lack of trust we’re optimizing for - the comment above (assuming the mod2 approach) would work for a very large untrusted pool of servers as long as you fully trust one arbitrator server - while other concensus based approaches would work better for a network of servers that are mostly trust worthy but contain a proportion of untrustworthy servers.
But the hosting/tabulating server could publish the data afterwards, make it all public.
Let’s break out some scenarios, I’ll assume we are always an honest actor…
Scenario 1, the data is all collated and published - you look at the ledger and see the value you reported is accurately recorded in the ledger… you poll other servers and they all also report that the inputs were accurate, you also take the ledger and re-evaluate the result and it matches what the server reported. What action should be taken? How many bad actors exist? Is the server a bad actor?
Scenario 2, the server collects and reports the data, the ledger looks right to you, but one server reports that their value was manipulated. The ledger does match the computed value though and it’s currently 1, should it be 0 instead? What action should be taken? How many bad actors exist? Is the server a bad actor?
Scenario 3, the server collects and reports the data… 70% of clients report manipulation, the ledger is consistent, though. What action should be taken? How many bad actors exist? Is the server bad actor?
-
Decide on a random N and what tails (even) and heads (uneven) mean.
-
Each party generates a random number
-
Combine the numbers with a conmutative operation of some sort, the harder the operation the better.
-
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)
- 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!
Step 3 is where the issue occurs. The last party to submit their value has control over the output. Any complex calculations can easily be passed off as network lag. One solution I can think of is to pass the values round in a circle, one by one. This would require each party to share their value before they have seen all other values. At the end each party would share their calculated values to verify they match. Probably other solutions as well.
Most remote coin tossing schemes incorporate commitment systems for this reason.
Amazing solution, didn’t arrive to that one, I was thinking just making a timing constraint to reveal the number that would make the precaculation practically imposible, but the commitment schmeme is waaaay more elegant.
Yes, that makes a lot more sense.
How does the group reach consensus on N?
Polling, probably - if the majority of group members are bad actors you’re fucked.
Are we talking about American politics again?
Do we ever talk about anything else?
Not very important, even if generated by a single actor N has not such a big importance. If I were implementing something like this I’d just probably make it -hardcoded-.
If you reaaaallyyyy want to decide on a N on the fly, I’d put a restricction (a<Nx<b) make each participant generate a Nx and then sum then all, -multiply’em If you wanna be hardcore- But I’d be tricky to get it right, for example a party might be able to consistently make N whatever the max value of N is by making their Nx very big -Which, well, I don’t really know how it would benefit that party and how would they exploit it-. Maybe using a operation like a XOR on the Nx would be robust enough, and would mitigate the kind of attack that I described above
Tl;dr: you can just have a random party generate 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.
One independent source of true random numbers with timestamps:
https://csrc.nist.gov/Projects/interoperable-randomness-beacons/beacon-20
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.
The last person to send the number decide the outcome
It doesn’t have to be addition. It could be a hash function, etc.
The last person would still decide the outcome. They could keep choosing values for whatever function until it produces their desired result and then post that.
What you would want instead is for everyone to post a (salted) hash, and after the hashes are posted, reveal what the original numbers were and then publicly add them. Everyone could verify everyone else’s numbers against those hashes.
Could you do it in 2 phases? First, everyone selects a random partner and exchanges their random number. Each pair then has a result that is locked in. Then everyone submits their result to be summed up as already suggested (Pos/neg = heads/tails).
If there are an uneven number of players, then one player makes a three-some.
I think you run into other issues, depending on OP’s meaning of “untrusted.” If people are paired off, whoever is in the last group to report can control the outcome. Either if there is a risk of collusion within the group or if one member doesn’t like what the outcome is going to be they can claim whichever of them is reporting the group outcome is lying, or the person reporting actuality could lie.
I think this vulnerability will come up most of the time when information is shared with only part of the group and not the entire group.
The risk of a pair collision should be mitigated by all pairings being random. And both pairs announce 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.
How do you do fair random pairing, though? If you are able to safely do that randomly, you might as well use that same method to do the random flip.
Edit: And even ignoring collusion, there’s still the issue of lying (or lying about lying). Only one of a pair would need to be a cheater for the system to fail, if the rest of the group is unable to determine which is the cheater.
If the function is known by all parties then the last person to send still has control
If the clients only communicate through the server, then without prior knowledge of one another, such as gpg keys, no.
Otherwise, maybe they could both generate an RSA key. Then they would both encrypt a string of this format “<RANDOM_STRING>_<RSA_PRIVATE>”, and send that to the other. After receiving the other’s package, each one sends over their own private key. They can use this to decrypt the string, which both of them had chosen before knowing what the other had. They can use the string to decide who won based on predetermined rules.
I put the private key in the package because this way clients can check that it was in fact the key used to encrypt it in the first place. Faking that would require infinite computing power or quantum shenanigans, I suspect.
Also this is probably way overkill and has flaws I didn’t think of.
This! The prior knowledge is even fairly small, everyone can toss in a random string + key. The only drawback is that all participants need to have synchronized rounds (one for collecting the random values, one for the decryption keys), and the whole protocol fails if someone decides not send timely their decryption key
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.
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.
- Everyone tosses three coins, and posts it in the chat
- If a player tosses three of the same, they have to toss again.
- Everyone chooses the mode coin from their neighbour, and adds it to their stack
- 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.
- 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 "p2" : [1,1,0], ## cheating "p3" : [1,1,0], ## cheating "p4" : [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.
The last player (or server) still can choose a result, because it knows other tosses before making it’s own.
Second attempt that factors in cheating.
spoiler
from numpy import median from random import choice from pprint import pprint # Functions get_mode_coin = lambda x: int(median(x)) def pick(player, wants): for neighbor in players: if player != neighbor: neighbor_purse = players[neighbor]["purse"] if wants: if wants in neighbor_purse: # Cheat players[play]["purse"] = players[play]["purse"] + [wants] continue players[play]["purse"] = players[play]["purse"] + [choice(neighbor_purse)] # Main players = {"p1" : {"purse": [1,0,1], "wants": False}, ## playing fair "p2" : {"purse": [0,0,1], "wants": 0}, ## cheating "p3" : {"purse": [1,1,0], "wants": 1}, ## cheating "p4" : {"purse": [1,1,0], "wants": 0}, ## cheating "p5" : {"purse": [0,0,1], "wants": False}} ## playing fair for play in players: ## Players pick a desired coin from each of their neighbours pick(play, players[play]["wants"]) print("First picks:") pprint(players) for play in players: ## Players collapse their collections to mode players[play] = [get_mode_coin(players[play]["purse"])] print("Last modes:", players) print("Final choice:", get_mode_coin([x for x in players.values()]))So, my method doesn’t work
First person gets a box showing heads tails. Once that is picked player 2 is shown a flip coin button. This isn’t fucking hard except the sync between apps which you do via db on the back end.
- Everyone tosses three coins, and posts it in the chat
If you’re interested in that kind of problems, here’s some pointer: https://en.m.wikipedia.org/wiki/Secure_multi-party_computation
For a more frivolous, but equally rigorous, approach
