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)

    1. 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!

  •  Melllvar   ( @charonn0@startrek.website ) 
    link
    fedilink
    English
    6
    edit-2
    6 months ago

    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 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.

          •  mub   ( @mub@lemmy.ml ) 
            link
            fedilink
            26 months ago

            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.

              •  mub   ( @mub@lemmy.ml ) 
                link
                fedilink
                16 months ago

                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.

    • 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.

  •  tetris11   ( @tetris11@lemmy.ml ) 
    link
    fedilink
    3
    edit-2
    6 months ago
    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.
    spoiler
    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.

    • 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

  •  Revan343   ( @Revan343@lemmy.ca ) 
    link
    fedilink
    3
    edit-2
    6 months ago

    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.

  • 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.