The concept of the “correct” definition of a random winner

Hello.

You know, sometimes I see that a group of people needs to choose some random object. For example, the duty officer, if there is no schedule, or he is confused (I would also tell about the “correct” duty schedules). Or, what has recently begun to annoy me, a winner in a contest of reposts.

The problem is as follows. The contest organizers declare that here is the sequence of actions for you, take it to participate in the contest (for example, repost this entry), and then we will choose a random winner from those who reposted on a certain date. People do all these actions, the long-awaited day comes and we get ...

Winner. In the best case, we will also receive a video like the organizer using random.orgselects a number, and then finds the winner in some table.

However, there is one problem here. The organizers promise an honest random, but we have nothing but their honest word. They can shoot videos hundreds of times until the right number falls out, replace the site on the localhost, and so on. There are no guarantees that we got a truly random choice.

I believe that systems should be designed in such a way that it was not possible to do something wrong in them, therefore ...



So, we have a group of N participants. We need to get something random so that each participant agrees that this random object was obtained in an honest manner.

In the real world, if the choice is binar - we can ask someone toss a coin (however, you can throw it for a long time, get the desired number of bits and then get anything). And we will see that he really threw it, that it took off, swirled in the air, landed and really fell an eagle or tails.

But on the Internet we can’t see that someone is really throwing something somewhere.



Therefore, we need an algorithm that is not centralized and easily verifiable. The first thing that comes to mind is to ask each participant for any random data, glue them with data received from other participants, calculate some hash from this and use it as a seed for a pseudo-random number generator.

But in such a scheme there are two drawbacks - time and mediator.

In the real world, we could write random data of each participant on pieces of paper, throw them into the ballot box, and then, when everyone threw their data, get them out of the ballot box and carry out the ritual of receiving the True Random. In our realities, unfortunately, we do not have such an urn.

We can try to exchange our data with other participants, but time comes into play. You cannot exchange data at the same time. And then the participant who should “throw” his data last, having the data of everyone else, can pick up such data that would make the random stand on his side.

Or you can ask someone to “hold” the data for us, i.e. find an uninterested intermediary. However, this option is not very reliable, because You can still be interested in an intermediary.

The second thing that comes to mind is that you need to somehow encrypt our virtual ballot box so that you can see its contents only after the end of throwing in your leaves.

You can really encrypt, for example, this way: each participant creates his own pair of public and private keys, shares with all his public, encrypts his data, shares with all encrypted. When the round of encrypted data exchange is over - everyone opens their private keys, decrypts the encrypted data, receives unencrypted, glues, hashes, feeds the PRNG, and receives the coveted random.

But you must admit that creating crypto keys is quite expensive to select one random number. Therefore, you can use the same hashes instead. At the beginning, everyone agrees on a certain salt so that no one can use any dictionary of collisions and open completely different data. Then they hash their data (there must be enough bits so that it is impossible in a reasonable amount of time just to brute-force the hashes of all participants), divide, open.

Those. we get a decentralized three-round (key exchange / salt selection, “closed ballot”, “open”) system of selecting a certain random grain by a group of people. Moreover, each of the people can personally verify the legitimacy of the final choice. And neither the participants nor the organizer can influence the final outcome.

Is this applicable in practice in the form of something? Is it possible to improve the circuit?