• HappyRedditRefugee@lemm.ee
    32·
    1 month ago

    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!

    • 56!@lemmy.ml
      8·
      1 month ago

      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.

      • HappyRedditRefugee@lemm.ee
        3·
        1 month ago

        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.

  • lemmefixdat4u@lemmy.world
    12·
    1 month ago

    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.

  • barsquid@lemmy.world
    5·
    1 month ago

    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.

  • tetris11@lemmy.ml
    51·
    1 month 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.

    • tetris11@lemmy.ml
      1·
      1 month ago

      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@lemmy.ca
    4·
    1 month 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.

  • Melllvar@startrek.websiteEnglish
    62·
    1 month 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.

  • Tolookah@discuss.tchncs.de
    3·
    1 month ago

    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.

    • xmunk@sh.itjust.works
      5·
      1 month ago

      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.

        • xmunk@sh.itjust.works
          2·
          1 month ago

          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?

  • xmunk@sh.itjust.works
    52·
    1 month ago

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

    • lluki@feddit.de
      2·
      1 month ago

      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