Open huitseeker opened 2 years ago
Note that Alberto and co have a new variant of Tusk that does not do randomized leader election, but requires partial synchrony. However, it would suffer from the selective leader DoS problem. Maybe worth chatting with him before going ahead with leader election implementation.
Thankfully this doesn't come up before stage 3 in the roadmap.
My notes of a discussion with @punwai :
On random beacons:
We propose using threshold BLS-based randomness beacon to generate randomness, which is unbiasable and doesn’t provide lookahead to an attacker. The beacon for the next epoch is setup after validators for this new epoch have been elected. An epoch length is currently ball-parked to a week, but we don't want downtime at the epoch change.
Deploying this kind of system requires running a DKG protocol. Since the validators of the next epoch are known only after the epoch ends, this poses the challenge that we have to do the setup fast enough so the beacon doesn’t suffer downtime. DKGs can be asynchronous (and complex) or synchronous (and require delay tuning).
the posterchild for ADKGs is the work of @LefKok in 2019 and 2021
For synchronous DKGs, there are several alternatives: common DKG protocols, such as the 2/3-round Joint-Feldman DKG (1 2), work by broadcasting secret shares of random polynomials and proceed with a complaint round, where a participant can claim they haven’t received their share and a justification round, where a blamed participant can reveal the correct share. They work in the synchronous communication model. Since there’s great importance in knowing if a participant received their share, as otherwise they won’t be able to participate in randomness generation in the future, we practically have to make the round length long, causing a slow DKG.
What the algorithm looks like:
n
validators selectedt-of-n
DKG of pubkey P, each validator stores their own secret share s_i
sig_i
on message H(r || full BLS signature at round r-1)
with s_i
t
validators broadcasted sig_i
, each validator can recover full BLS signature at round r (the random beacon coin
)coin
to select committee.leader(coin mod validator set size)
For step 2, the two existing rust library we can leverage are: https://github.com/kobigurk/aggregatable-dkg and https://github.com/ZenGo-X/fs-dkr
You got the gist of it.
At round r, a set of n validators selected
It's actually at the start of one epoch, which marks a change in the # of participants. (one epoch is many rounds)
For step 2, the two existing rust library we can leverage are: https://github.com/kobigurk/aggregatable-dkg and https://github.com/ZenGo-X/fs-dkr
Note the later is doing key resharing, i.e. they do something a bit different, and they explain the difference in their readme.
I have some new research on resharing/refreshing the keys that saves off an O(n/logn) leveraging the existence of a blockchain that produces randomness. We have not yet benchmarked it but it should be fast enough for epoch rotations especially if we only need f+1 out of 3f+1 threshold keys. Happy to share a rough draft in private
This issue is stale because it has been open 60 days with no activity. Remove stale label or comment or this will be closed in 7 days.
The leader election in Tusk is a post-proposal leader pick based on a random coin.
The code we have right now is not a random coin, but rather a round-robin: https://github.com/MystenLabs/narwhal/blob/35319b17ece0bcfc6839fb23188138424da86a27/consensus/src/lib.rs#L210-L228
We should implement a real leader election based on a public coin.