Coin Toss Function in Ouroboros

I am trying to get my head around how the protocol selects validators.

So far here is what I pieced together:

  1. At the beginning of each epoch a randomized committee is chosen to run a coin toss.

  2. 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.

  3. 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.

2 Likes

“Follow The Satoshi” algorithm:

https://www.google.com/amp/s/amp.reddit.com/r/sp8de/comments/7se11q/fts_is_the_base_of_ouroboros_protocol_but_what/

1 Like

Not sure if there is more but I didn’t see a detailed explanation.

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.

2 Likes

How is “random” calculated anyway? since there is no mathematical formula for randomness, since that doesn’t exist, so what is being used?

Try reading that post:

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.

Sure but that is not random.

What mathematical formula would you use to generate a random number?

Cool! :+1:

https://docs.python.org/2/library/random.html

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.

Good to know! :+1: :+1:

Yeah I was just curious what crypto used for randomness… It is not something I know that much about, but I definitely find it interesting.

Randomness is a funny and interesting concept, perhaps it might just be a wishful human idea.

Like a coin-toss, once the coin is in the air, where and side it lands on has already been determined, and how far back this goes, who knows.

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.

4 Likes

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.

1 Like

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 :slight_smile:

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 :slight_smile: 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.

2 Likes

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):

  1. At epoch T-1, a committee is selected using say random.random() function.

  2. The committee then generates entropy and reaches consensus on a seed.

  3. 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?

  4. Slot leaders are locked and loaded onto blockchain. This makes sure that the network calls onto them to validate a block.

  5. 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.

  6. 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…

1 Like

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).

2 Likes

This is my understanding too. Since we need a separate seed for each slot leader, do you think the coin-toss algorithm is repeated 21,600 times?