this post was submitted on 17 May 2024
53 points (93.4% liked)

Asklemmy

42630 readers
1013 users here now

A loosely moderated place to ask open-ended questions

Search asklemmy ๐Ÿ”

If your post meets the following criteria, it's welcome here!

  1. Open-ended question
  2. Not offensive: at this point, we do not have the bandwidth to moderate overtly political discussions. Assume best intent and be excellent to each other.
  3. Not regarding using or support for Lemmy: context, see the list of support communities and tools for finding communities below
  4. Not ad nauseam inducing: please make sure it is a question that would be new to most members
  5. An actual topic of discussion

Looking for support?

Looking for a community?

~Icon~ ~by~ ~@Double_[email protected]~

founded 5 years ago
MODERATORS
all 35 comments
sorted by: hot top controversial new old
[โ€“] [email protected] 34 points 2 months ago (2 children)
  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!

[โ€“] [email protected] 8 points 2 months ago (1 children)

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.

[โ€“] [email protected] 4 points 2 months ago* (last edited 2 months ago) (2 children)

Most remote coin tossing schemes incorporate commitment systems for this reason.

https://en.wikipedia.org/wiki/Commitment_scheme

[โ€“] [email protected] 2 points 2 months ago

Yes, that makes a lot more sense.

[โ€“] [email protected] 2 points 2 months ago

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.

[โ€“] [email protected] 4 points 2 months ago (2 children)

How does the group reach consensus on N?

[โ€“] [email protected] 7 points 2 months ago (1 children)

Polling, probably - if the majority of group members are bad actors you're fucked.

[โ€“] [email protected] 1 points 2 months ago (1 children)

Are we talking about American politics again?

[โ€“] [email protected] 4 points 2 months ago

Do we ever talk about anything else?

[โ€“] [email protected] 3 points 2 months 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 14 points 2 months ago (1 children)

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.

[โ€“] lemmefixdat4u 8 points 2 months ago

One independent source of true random numbers with timestamps:

https://csrc.nist.gov/Projects/interoperable-randomness-beacons/beacon-20

[โ€“] barsquid 6 points 2 months 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.

[โ€“] [email protected] 4 points 2 months ago* (last edited 2 months ago) (1 children)

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.

[โ€“] [email protected] 0 points 2 months ago

Or they can just talk to each other and resolve the dispute

[โ€“] [email protected] 4 points 2 months ago* (last edited 2 months ago) (1 children)

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.

[โ€“] [email protected] 8 points 2 months ago (1 children)

The last person to send the number decide the outcome

[โ€“] [email protected] 1 points 2 months ago (1 children)

It doesn't have to be addition. It could be a hash function, etc.

[โ€“] fishpen0 5 points 2 months ago

If the function is known by all parties then the last person to send still has control

[โ€“] [email protected] 4 points 2 months ago* (last edited 2 months ago) (3 children)
  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.

[โ€“] [email protected] 4 points 2 months ago

The last player (or server) still can choose a result, because it knows other tosses before making it's own.

[โ€“] Dkarma 2 points 2 months ago

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.

[โ€“] [email protected] 1 points 2 months 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

[โ€“] [email protected] 3 points 2 months ago (1 children)

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.

[โ€“] [email protected] 5 points 2 months ago* (last edited 2 months ago) (1 children)

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.

[โ€“] [email protected] 1 points 2 months ago (1 children)

But the hosting/tabulating server could publish the data afterwards, make it all public.

[โ€“] [email protected] 2 points 2 months 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?

[โ€“] [email protected] 3 points 2 months ago (1 children)

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

[โ€“] [email protected] 3 points 2 months ago (1 children)

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

[โ€“] [email protected] 2 points 2 months ago (1 children)
[โ€“] cucumber_sandwich 1 points 2 months ago

There's an actual article on [remote coin-flipping] (https://en.m.wikipedia.org/wiki/Coin_flipping#Telecommunications)