I am trying to get my head around how the protocol selects validators.
So far here is what I pieced together:
At the beginning of each epoch a randomized committee is chosen to run a coin toss.
The coin toss takes place in two stages: the commitment stage and the reveal stage. This is to limit the ability of bad actors to pick results that favor them.
At the reveal stage the results of the coin toss are Xored and committed to the ledger. These effectively pick the 21600 validators for the next epoch.
Can someone walk me through teach stage showing me what exactly happens in a system with letâs say 100 coins? I am not sure exactly how the results of a random number generation get mapped to specific coins whose owners get to sign blocks.
Imagine there are only two nodes and each has one coin. Two coins in total. For each slot in the next epoch algorithm will calculate newRandom(seed, 2) which will give in result a number: either 1 or 2 - the number of a coin. Whoever is the owner of selected coin - Is the leader for this slot. Each of two nodes have 50% chance.
Now imagine there are two nodes, but three coins. One nodes has two, and other - one. For each slot algorithm will calculate newRandom(seed, 3) which will give in result a 1, a 2, or 3 - the number of a coin. Whoever is the owner - the leader. Now one node have ~66% chance to win a slot. Thatâs why stake size matters.
But how do you make a coin toss in code? You cant code something to give a random outcome. I mean you can cheat by using some external output that cant easily be calculated and use that to generate ârandomâ - I guess the best random generates would be using quantum mechanics.
Again it is not random, but completely predictable, which is why it cant be used unencrypted for security reasons - and even though the outcome might be able to be used and accepted as a random input, it wasnât truly random.
Perhaps a device using elements of quantum physics could actually be a true random-generating device, if it is true that positions are truely probability based.
There are no true random numbers but numbers that are very close to them. And, theyâre good enough for any cryptography. For getting more close to the true ones, some companies use different techniques such as lava lamps or similar.
Anyway, back to coin tossing, in very brief:
to be involved in coin tossing you need to have at least, if I remember correctly, 1% of the stake.
Every participant generates an x bits long entropy,
but the stakeholder (meant leader) selection is based on a seed which is the aggregates of these entropies, so it does not matter if somebody playing bad, the generated seed will be proven secure.
But, itâs a bit more complicated process than to explain it here in few sentences.
1% was only used as as an example in the original Ouroboros paper. Would be quite hard to have 1% threshold along with the k~=100. If Cardano does not manage to move to Praos along with Shelley - there ought be quite smaller threshold. Which is ok and possible, since 1% is not a magical number - the only point of the threshold is to limit the chain bloat since original PVSS requires quadratic communication overhead. So even having threshold at 0.1% would keep participants at max(1000) and much fewer in practice .
Afaik, the k is related to the pools, which has nothing to do anything w/ the coin tossing (Shared Seed Computation).
For coin tossing everybody who has more than 2% (had just checked and itâs 2% and defined in genesis-mainnet.json as mpcThd) is selected for coin tossing.
I meant in the current config in the bootstrap era.
If you have 100 pools (nodes) with 1% stake each - that would be quite hard to find participants with 2% of stake to perform the tossing
2% is defined only for Byron, afaik. I donât see how it can be technically used after Shelley release if k is not set to <50. Which is possible of course for a short period between Shelley and Praos (if not implemented initially).
Anyways it doesnât really matter that much, since Cardano will be on Praos eventually anyhow And thatâs what really matters (for me at least) - in what form will IOHK hand the system over, not in what form it is during development.
Thanks. this is starting to make more sense. combined with below.
âŚSo to bring it back to our example (ignoring the min stake requirement (if any) for now):
At epoch T-1, a committee is selected using say random.random() function.
The committee then generates entropy and reaches consensus on a seed.
This is when it gets tricky for me: Assuming each seed ==one vote, the seed generation function used 21600 times to select slot leaders? Or maybe one seed can be used to select all the slot leaders in an epoch? How?
Slot leaders are locked and loaded onto blockchain. This makes sure that the network calls onto them to validate a block.
At Epoch T the selected slot leaders need to be online for the whole duration as they donât know when exactly they will be called.
At Epoch T the process of committee/slot selection is repeated.
Is this sequence roughly correct???
This is a good question. I think they grappled with this one quite a while, since any source of external entropy could be contaminated. I think they solved the issue. In this video, Philipp Kant of IOHK touches upon how they âsourceâ entropy internally.
I guess you could argue that random.random() function in python could effectively replace entropy in a closed system like Cardano, if every Lovelace has an equal chance of being selected to validate a blockâŚ
Common seed is derived from all the random values generated by committee members. Imagine there are two of us: you have a node and I have a node. Neither of us can be trusted to provide the final seed, since we could grind a value that would prefer ourselves over the other node. So what we do is - each of us creates a local PSEUDO-random value (@jb455) using simple random.random() (or any other function from any other language) and we send this value to the blockchain (in 2 steps). When we open both of our local PSEUDO-random values we XOR them together to get final common seed. And this seed is used by the protocol to call newRandom(seed, max_coin, slot_number) to select a winning lovelace. Because the seed is known and common to all of us - every new call of newRandom(seed, max_coin, slot_number) is predicatable and will return the same values if called again with the same arguments.
With this mechanism - neither of us could âgrindâ a local PSEUDO-random value to make the resulting seed to be in our favour. So the problem is deriving the common seed, and once it is done - the rest is easy.
Network does not call anyone. What is ânetworkâ? Slot leader himself waits for his slot and then sends out a new block, and everyone else use newRandom(seed, max_coin, slot_number) to check if heâs a valid leader for current slot.
They know exactly beforehand which slots are âtheirsâ. And everyone else knows it (not in Praos).