How to select a random node when nodes are untrusted in a distributed network?

Question

Assume in a distributed network, where the nodes are not trusted and are identified by their public keys, we intend to select one of them in a random process. In such a situation, all of the nodes have the same chances to be elected.

Since the system is not centralized and there is no trusted server performing the election process, how to select one of the nodes truly randomly (where each of the nodes is able to manipulate the client code such that they would be elected in all the rounds)?

Complementary explanation: I mean that as there is no trusted and centralized server to perform the randomness process, thus it is performed locally in each node by a client code, such that each node can be able to manipulate the client code to be always elected. Assume there are 10 nodes, each of which has a client code to perform a decentralized randomness process. What happens if one of them manipulate the code to be elected in all the rounds? And how to prevent such malicious behavior?

Answer 1

If you have anonymous nodes, then you have the problem of spawning fake nodes under your control. That is, you have worse problems than a node voting for itself.

So some kind of reputation is needed for each node. I am a fan of "bartering exchanges", where transactions happen within a local group. Trust grows from that small group succeeding to add value equally for each other. That group can form a group identity for performing larger transactions with larger groups, but initially starting small between those groups.

It's important that fair trade is used as the basis for gaining trust. Therefore if a relationship is asymmetric, then it won't last

I don't know what your network is doing so I can't help more without knowing what "value" is exchanged. But I want to assure readers that this value need not mean "money". In the digital world, computing resources may be exchanged, disk storage may be rented, and human laboured services can be rendered anonymously. With a "bartering" model you don't track a currency, but rather trust and equality.

When it comes to vote that occurs within a trusted group, then that groups outcome is signed by group members and shared onward to other peer groups, and so on. Barter trade value is the reputation that either validates the vote or multiplies the weighting of the group vote.

Answer 2

That's one (and one of the few) use cases that a blockchain will easily solve.

You first generate one block of information (it can be anything, but it must have a strong hash of the information on it), and you hard-code this hash on the client code. Every new client joins the network and synchronizes itself with all the other nodes, downloading every single block and validating the hash of each one.

After one block (or more), all the clients have the same image of the blockchain, and you can start the election. You can make all clients put themselves to vote by submitting one token to the blockchain and the clients have to sign that token with their own public key, and submit the results to a block.

Now you have a special block with an array [userID -> hashed challenge], those are in the blockchain and cannot be changed. Your client code now just need a reproducible but not easily deduced way to turn that array into a new elected leader.

One crypto currency that I looked into the code would take that hash and calculate the distance between the hashes of the clients and the hash of the block. Since nobody can deduce the hash of the block before the block is generated, you can be sure that the nodes cannot influence the network to be elected. And no client code can be changed to make itself the leader because the other clients will calculate the leader and it won't be the cheating node.