Polkadot’s Verifiable Randomness for Miner Nomination
Verifiable randomness is a powerful concept that allows a distributed network to generate secure random numbers. To understand why this is so interesting, let's explore how random numbers are created classically and then see how Polkadot uses this concept to nominate miners for its network.
Pseudorandom Number Generators
Firstly, there is no such thing as a true random action taken by a computer. Unless your computer is actually measuring the spins of electrons (I assume you are not browsing medium on a quantum computer), then there is a discrete and repeatable list of steps to produce every action it performs. So how can a deterministic process produce a random number? Put simply, it cheats.
Random number generations on computers are often called “pseudo-random” as they produce statistically random results that are fully repeatable. To do this, the computer takes in a seed value, using it as the input to some function, and then takes the resultant value as the next seed value. Following this recursive sequence to compute a limitless number of values. A crude example of some such a generator called the “middle square” generator looks something like the following:
What is expressed in the image is the recursive process of taking some number, square it, then extracting a subset of digits from the resultant number as the new base number. In theory, these resultant numbers would form a sequence sufficiently random to be useful. Issues could exist if the sequence is repeated or it does not fully cover the space. More modern approaches exist that use more complex sequences to better achieve these goals, but the concept is the same.
This approach runs into problems on a blockchain system tho. Since the seed phrase is fixed at the start at some point and then deterministically generated, a malicious party could pre-generate the full sequence and thus know the “future” of the random number generator. Knowing what number will be “randomly” generated next would allow the part to take actions in advance that would benefit them. This is clearly bad.
Verifiable Random Functions
I won't go into the full technical explanation of how they are implemented, if you are interested, there is a breakdown below, but I will go into what features they enable for us.
In a high-level sense, a Verifiable Random Function (VRF) starts with a client generating a private and public key pair (read more here). When given some seed value (similar to the example above), clients can use their private key to generate a random deterministic output value. This resultant random value is then able to be checked by others using the public key and the original seed.
More simply stated, VRF allows the generation of random numbers from seeds in a verifiable way that cannot be pre-generated by outside parties.
How Polkadot uses VRF for nomination
One aspect of Polkadot is a nomination system that allows a network of nodes to self-select who mines the next block rather than just opening the flood gates as bitcoin does. In this system, Polkadot divides the timeline into 6-second chunks, each of which can be filled with a block. Through their system, nodes can determine through VRFs if they are selected to mine that specific chunk without consulting the rest of the network. Let's explore that in more detail.
Firstly, we must understand that each block in the chain has a hashed value. This idea is what keeps each node linked into the chain. This value is effectively random and unpredictable as it is a product of all the transactions encoded in the block. This number itself is a value every node can agree on as a basis. We will use it as our seed value for VRF.
After a block is published onto the network, every node can use this seed value to generate a verifiable random number unique to that node. This value is then compared against some threshold value known across the network. If the node’s random value is less than then the threshold set on the network, it considers itself selected for the next chunk.
In the crude example above, 9 nodes each generate a number 1 to 100 and “self-select” when their generated number is less than 10. In this system, most times we will get a single node nominated to mine the given block. Since VRF keys and values are set before the seed is released, there is no ability for nodes to keep re-rolling until their value falls under the threshold, so the simulation above should reflect a real system rather well.
This method has some amazing features too it over traditional proof-of-work as it drastically limits the total number of nodes available to mine at a given time. In total, this approach will:
- Allow nodes to determine if they are selected without communication to the network. No need to be informed of your selection or require a central location to select miners
- Effectively cuts down the number of nodes fighting for a given block, making it mine faster, cheaper, and with less energy overhead.
But we also run into other issues, namely that we cannot verify one and only one node is selected for a given chunk. Similar to Bitcoin, the network can automatically adjust the threshold to some optimal value given the size of the network. But this optimal value will only ever have the best chance to produce one miner. In reality, there can often be more or fewer miners selected. As more nodes join, this becomes even harder to control.
In the above example, 36 nodes participate with an unchanged threshold of 10. In reality, this threshold will automatically adjust lower as it is clearly too high for a network of this size. In this example, 4 nodes are often selected, but given the size of the network, this will swing up and down more than a smaller network would.
In Polkadot's current system, there are both primary and secondary miners selected. If a primary miner fails to be nominated, then a secondary miner can step up and mine it. Through the secondary miner selection process, there will be many more miners in the secondary group. But this just rolls over into the other issue. What do we do when multiple miners self-select?
In this case, we are back to the old system, open the flood gates and allow all selected miners to take their shot at being first. This sounds bad, but for a large network, these nodes included in this group will be a fraction of the network as a whole. In effect, this system cuts down the competition for mining a given block by 99 percent or more. Not too bad.
Closing
Using VRFs, Polkadot allows nodes to self-select themselves for mining a given time chunk. In this method, the competition for blocks is mostly eliminated, reducing network congestion and speeding up network throughput. The full system is much more complicated when compared to this rather simple introduction, but the hope is this article gives people intuition onto how random numbers are used for self-selection.
Check out our new platform 👉 https://thecapital.io/