Randomness in Avalanche Consensus

[zjasper666]

I know in snowman++, a leader is chosen randomly every epoch. How is the leader chosen? How does Avalanche consensus generate the random beacon for randomly selecting the leader and other purposes?

[aaronbuchwald]

Hey @zjasper666 thanks for moving the question here. You can find the documentation in the ProposerVM README here: https://github.com/ava-labs/avalanchego/blob/master/vms/proposervm/README.md#snowman-proposers-selection-mechanism

Let me know if you have any further questions on it

[zjasper666]

Thanks @aaronbuchwald. Based on the documentation of this README:

• A seed S is generated by xoring H and the chainID. The chainID inclusion makes sure that different seeds sequences are generated for different chains.
• Validators are pseudo-randomly sampled without replacement by weight, seeded by S.

the seed and the selection of validators are predictable beforehand. Does that cause some unfairness? For example, a user can know which validators will be proposers in the next block and bribe them. Or a validator can change its nodeID to let itself have more chances to be selected as proposers in the next several blocks.

Just my two cents: using the block hash will be a better (not perfect) solution. A more complicated solution will be using a VRF like what Ethereum does. Here's some reference for randomness:

1. https://www.paradigm.xyz/2023/01/eth-rng
2. https://a16zcrypto.com/posts/article/public-randomness-and-randomness-beacons/

[StephenButtolph]

Wouldn't they just pay the validators that proposed a block and didn't include the transaction?

[zjasper666]

But if the proposers are unpredictable, it's harder for the briber to make a deal with them.

Another possible issue is that if an attacker learns who the upcoming leader is, it might launch a Denial of Service (DoS) attack on them to prevent them from publishing a block. The attacker could then take down the next leader and so on, bringing the blockchain to a halt. https://a16zcrypto.com/posts/article/leader-election-from-randomness-beacons-and-other-strategies/#section--2

[StephenButtolph]

Yeah I understand there are trade-offs. Not trying to say that there are no benefits in using a VRF. There can also be situations where the block producer knowing that they will be the next block producer can be important.

But I'd disagree strongly that using block hash would be an improvement. Using a commit reveal scheme (like Ethereum) is pretty dirty and requires economic arguments around the value of gaming the system. (Just a matter of time before we see someone from the MEV community try to attack it imo). In my ideal world we'd be able to use a threshold VRF - but that isn't practical in a setting with a large number of validators (and especially one with a large number of validators and a changing validator set). So, the best solution we were able to come up with (at the time) was to optimize for minimally game-able, while not optimizing for being unpredictable.

[StephenButtolph]

Side note on the DoS concern - the list of nodes you would need to DoS increases (becoming the full network after 30s of no blocks). So I wouldn't consider this something that could actually cause the whole chain to halt.

[zjasper666]

In the current setting, it's possible to predict the proposers for any future block (even the 100th block from the moment). Using a block hash makes predicting the proposers for any blocks after the next block impossible but is still not ideal. I agree that a threshold VRF is not practical for a dynamic validator set. Hopefully, some researchers can come up with a better and more practical solution for leader election.

The point that after 30s of no blocks, any node in the full network can propose a block indeed makes DoS attack much less possible.

Thanks for the explanation!