Shuffling of Validators (Validator selection/proposer selection) in Ethereum

In topic RANDAO, we learned how the random number is generated to assign validators to committees and select block proposers. In this topic, we look at the question of how the validators are actually assigned to their committee or slot. This process is called shuffling.

Definition of Shuffling in Ethereum: Shuffling is the process of randomly assigning attestors to committees and proposers to slots.

The basic problem is: We have a list of validators that should be ordered randomly (Creating a permutation of the original order. The original order could follow the address of the validator from the lowest to the highest). The first 128 validators become members of committee 1, the next 128 validators become members of committee 2, and so on.

One important property of a shuffling algorithm is that it is truly random. Every permutation should occur with the same probability. While there are efficient shuffling algorithms like the Fisher-Yates shuffle, Ethereum decided to use the less efficient “Swap or not” algorithm. The reason behind that is that light clients should also be able to calculate their position in the committee without knowing the whole set of candidates. So, they can determine the index of a single element without shuffling the whole list of validators.