1. 19

  2. 8

    The proposed solutions provided in the article all swarm around the idea of finding a third-party source randomness that everyone can agree on. Almost all the proposed solutions on the reddit thread do the same. (Props to this person for walking to the beat of a different drummer.)

    I think they (or we) can do better! But, I don’t know how, yet.

    I think the solution should be cryptographic in nature… So, I’ll try to get close to the answer by clicking anything in Wikipedia’s Cryptography Portal and connected nodes and sharing anything that looks remotely related.

    These look really promising:

    These look … interesting? Hopefully unnecessary.

    1. 5

      What about this?

      1. Each party generates a secret string
      2. Each party publishes the hash of their string to the entire group
      3. Once all hashes have been published, each party publishes their original string to the entire group
      4. The random number is the hash of the concatenated strings

      There’s nothing in this protocol enforcing that the secret strings be random, but I believe that it’s game-theoretically in each party’s interest to do so, so as to avoid e.g. dictionary attacks. I can’t see how any party gains anything by generating a string that is anything except truly random, ensuring a random hash of the concatenated strings.

      Am I thinking about this correctly?

      EDIT: Ah, I see, this is basically the “commitment scheme” idea mentioned in the Wikipedia article you posted. Cool!

      1. 1

        I came up with a variant of this, but instead of strings, each person picks a number, which is then hashed, then the resulting number is the sum of the chosen numbers, mod 20, plus 1.

        Another thing you could do is send a message, and the millisecond it was received at, mod 20, plus 1, is your number. You would have to trust that the internet makes the timing random enough, and that you can trust your chat system, but usually you can.

      2. 4

        They don’t need to agree on the source of randomness, it just needs to be reasonably beyond manipulation by dev1. Like @asrp says, stuff like Bitcoin IDs will work. You could also hash the fifty first characters of the first article of a newspaper published the day of. Just as long as you announce the method before the event happens, and that the data source is sufficiently out of your control, you’re good.

        1. 2

          It depends on what they mean by their constraint 2. If there’s no input from the other devs or any third party then the only remaining source of information is the first developer and so I think it cannot be done.

        2. 4

          There exists an interesting cryptographic solution to this that doesn’t rely on third party randomness (which can usually be manipulated).

          The variant more commonly used is phrased as “Coin Tossing Over the Telephone” and here’s a write-up of a solution that relies on the discrete log assumption (this breaks in quantum world): http://www.cs.cmu.edu/%7Eryanw/crypto/lec14.pdf

          1. 2

            Tell them to until the next draw of a large lottery and use the results.

            For instance, using EuroMillions where each ball draw is a number from 1 to 50, there are 50 ^ 3 = 125000 = 6250 * 20 possible draws from the first 3 balls. Order them somehow, create bins, done.

            1. 2

              I came up with a solution to the first problem with solution 2 in the article. However my solution still violates constraint 2.

              Each developer generates a random number n and some key k. They then send h = hash(n || k) to the group chat. Once they have all sent this h, they then each send their n and k. Then each person can verify (by computing h and comparing with the given value) that the n sent by each other person was independent of any information that they had already received from the other developers.

              Hence any participant cannot be in control of the sum or product or exclusive-or of the inputs, modulo 20.

              1. 1

                Get a trusted fifth developer to make the choice using their preferred method of generating randomness and let them communicate the result on your behalf (including the method they used, so the other devs can verify you didn’t manipulate the fifth developer).

                1. 1

                  I found the question pretty interesting but the discussion of the (hidden) solution too long (everything after 3 seem to be a rehash of 3).

                  State a timestamp in the future (distant enough for the email to reach everyone before the timestamp) and select a random public event at that time (or the first one to occur right after it).

                  I think this was stated many times on reddit with bitcoin hash id as the public event.

                  Example: If its 9:10 now, write an email with “take the bitcoin id that appears after 9:25 and apply <transformation to get it to a random number between 1 and 20>” and send it now. Wait. Look at the ID.

                  Edit: actually on Reddit a lot of solutions of this form were suggested like solar activity or stock prices.

                  1. 3

                    Instead of Bitcoin, solar activity, or stock prices, there also exists the NIST Randomness Beacon.

                  2. 1

                    Find a live stream from a tropical region where it’s not raining at the time of receiving the message, take modulo 20 of the time elapsed until the next rain shower. Keep video proof as evidence.