# Leader selection for HotStuff-rs 0.4

## Weighted Round Robin

Here is a stateless version of [Interleaved Weighted Round Robin](https://en.wikipedia.org/wiki/Weighted_round_robin#Interleaved_WRR). Stateless, meaning that unless the leader for this view has already been computed, computing the leader for the view does not depend on any data other than the arguments to the `view_leader` function.

For Weighted Round Robin, we would like that the frequency with which a particular validator is chosen as a leader is proportional to their power. However, with validator set updates it is impossible to guarantee complete fairness. Therefore, we aim at fairness as defined above in the best case (of a stable validator set), and all validators being chosen as leaders with the same frequency in the worst-case. This naturally leads to chosing Interleaved Weighted Round Robin over Classical Weighted Round Robin, since the latter selects a validator to act as the leader for a number of subsequent views proportional to the validator's power, and hence (assuming validator set updates) is biased towards the validators with lower indices (lower public keys).

To illustrate Interleaved Weighted Round Robin, suppose we have validators identified by `v1, v2, v3, v4, v5` with the following powers:

v1 -> 2
v2 -> 1
v3 -> 4
v4 -> 2
v5 -> 3

Hence, the total power is 12. Then for every subsequent 12 views while this validator set is in power, the leader assignment can be visualised by the following array, consisting of subsequent segments - a segmented with ordered validators with power at least 1, next segement with ordered validators with power at least 2, then at least 3, and at least 4:

| View Number mod 12 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| ------------- | ------------- | --- |--- |--- |--- |--- |--- |--- |--- |--- |--- |--- |
| Validator | `v1` | `v2` | `v3` | `v4` | `v5` | `v1`| `v3` | `v4` | `v5` | `v3` | `v5` | `v3` |
| Power check | $\geq 1$ | $\geq 1$ | $\geq 1$ | $\geq 1$ | $\geq 1$ | $\geq 2$| $\geq 2$ | $\geq 2$ | $\geq 2$ | $\geq 3$ | $\geq 3$ | $\geq 4$ |

Except that, in order to avoid (1) notifying the pacemaker about each validator set update, and (2) having to store and re-compute this array for each new validator set, even if it changes often, we don't store this array, but rather compute its values on-demand, from an abstract specification of the array.

    fn view_leader(
        &mut self,
        cur_view: ViewNumber,
        validator_set: &ValidatorSet
    ) -> VerifyingKey {

        // I the leader for this view has already been computed, it is stored in the latest_view_and_leader field.
        if self.latest_view_and_leader.is_some() && self.latest_view_and_leader.unwrap().0 == cur_view {
            return self.latest_view_and_leader.unwrap().1
        }
        
        // Length of the abstract array.
        let p_total = validator_set.total_power();
        // Total number of validators.
        let n = validator_set.len();
        // Index in the abstract array.
        let index = cur_view % p_total as u64;
        // Max. power among the validators.
        let p_max = validator_set.validators_and_powers().iter().map(|(_, power)| power).max().unwrap().clone();

        let mut counter = 0;

        // Search for a validator at given index in the abstract array of leaders.
        for threshold in 1..p_max {
            for k in 0..(n-1) {
                let validator = validator_set.validators().nth(k).unwrap();
                if validator_set.power(validator).unwrap() >= &threshold {
                    if counter == index {
                        self.latest_view_and_leader = Some((cur_view, validator.clone()));
                        return *validator;
                    }
                    counter += 1
                }
            }
        }

        // If index not found, panic. This should never happen.
        panic!()
        
    }

<!-- So when a given validator becomes the leader of a view is determined by its position in the abstract array of leaders.

Conceptually, the array consists of subsequent segments, each segment containing validators (ordered by public key) with power greater or equal to a given threshold. Thus, the first segment contains all validators with power at least equal to 1, the second segment consists of all validators with power at least equal to 2, and so it goes until a threshold equal to
the maximum power of a validator in the validator set. -->

The array is not stored in memory, since we want to keep this function pure, or at least not dependent on maintaining a stored array, which would have to be re-computed and re-stored on updating the validator set. Instead, the element (validator) at a given index is computed by iterating through validators for increasing thresholds (representing the segments), until a number of elements matching the index have been traversed.

However, the result is stored in the `latest_view_and_leader` field, so in case the algorithm thread needs to check who the leader is again, it does not need perform the traversal again.

pub struct DefaultPacemaker {
    minimum_view_timeout: Duration,
    latest_view_and_leader: Option<(ViewNumber, VerifyingKey)>,
}

## Randomised

This is more involved, and has serious security implications if done incorrectly, or if it is exploitable.

Possible solutions include:
1. Find a random seed in the recent blockchain data, and deterministically sample a leader from this seed and a distribution determined by the relative powers of validators.
- But in blockchain everything is deterministic, so it's difficult to find a random seed. For example, the hash of the most recently committed block is not necessarily random because it can be manipulated by ordering certain transactions.
- We can't rely on very recent data because validators may be slightly out of sync, with some validators having committed a given block, some not yet. On the other hand, using old blockchain data defeats the purpose of trying the reduce the window for a DoS attack where the leader is predictable before it starts to rule to minimum possible, as then the leader can be predicted well in advance.
2. Use Verifiable Random Functions (VRF). VRFs generate a random value, along with a proof of its randomness. Then the seed generation or leader election can be outsourced to some validator (e.g., the leader), and their randomness can be verified and they can be embedded in the blockchain. Effectively, this can become part of consensus, as the random values can be proposed and their validity can be verified by others, but agreement on the order is required. One comerically-successful example is [ChainLink's VRF](https://medium.com/@MyceliumNetwork/what-is-chainlink-verifiable-random-function-vrf-dd4f4f8f13a6).
- Note: Requires storing extra data in blocks.
- The VRF libraries in Rust are experimental ([vrf mod](https://crates.io/crates/vrf-mod/0.1.2) and [vrf](https://crates.io/crates/vrf/0.2.1/dependencies)), it might not be safe to rely on them, and writing VRFs ourselves is not a very good idea.