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 tell about the “correct” duty schedules, too). Or, that I began to annoy lately, the winner in any contest of reposts.

The problem is as follows. The organizers of the competition declare that here is a sequence of actions for you, make it to participate in the competition (for example, make a repost of this record), and then we will choose such and such a random winner from the repost. People do all these actions, a long-awaited day comes and we get ...
')
Winner At best, we also get the video, as the organizer selects a number using random.org 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 video hundreds of times, until the required number falls out, change the site on localhost and so on. There are no guarantees that we received a truly random selection.

I believe that the systems should be designed in such a way that to do something wrong in them was not possible, 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 received in an honest way.

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

But on the Internet, we can not see that someone really throws something somewhere.



Therefore, we need an algorithm that is not centralized and is easy to check. The first thing that comes to mind is to ask each participant for any random data, merge it with the data received from other participants, count some hash from it and use it as a grain for a pseudo-random number generator.

But in this 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 left their data, get them out of the ballot box and carry out the ritual of getting the True Random. In our reality, unfortunately, we do not have such an urn.

We can try to share our data with other participants, but time comes into play. Cannot share data at the same time. And then the participant who has to “leave” his data last, having the data of all the others can pick up such data that would force the random to take its side.

Or you can ask someone to “hold” the data for us, i.e. find a disinterested mediator. However, this option is not very reliable, because The mediator can still be interested in something.

The second thing that comes to mind is that we need to somehow encrypt our virtual urn, so that we could see its contents only after the end of the throw-in of its sheets.

You can really encrypt, for example, like this: each participant creates his own pair of public and private keys, shares his open data with all, encrypts his data, shares it with all encrypted. When the encrypted data exchange round is over - everyone opens their private keys, decrypts the encrypted data, gets unencrypted, sticks together, hashes, feeds the PRNG, gets the coveted rand.

But agree that to choose one random number to create crypto keys - quite expensive. Therefore, you can use the same hashes instead. In the beginning, everyone agrees on some salt, so that no one can use any dictionary of collisions and open completely different data. Then, hash their data (there must be enough bits so that it is impossible for a reasonable time to simply uncheck the hashes of all participants), divide, open.

Those. we get a decentralized three rounds (key exchange / choice of salt, “closed vote”, “open”) the system of choosing 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 affect the final outcome.

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