Fisher-Yates (GLI-19 certified)

TL;DR

Use this algorithm if your application needs to be GLI-19 compliant.

This algorithm is the original Fisher-Yates shuffle algorithm as described here. It has been the subject of an in-depth audit by Gaming Laboratories International and has received the GLI-19 certification.

It's a bit more computation intensive than the 2 other algorithms so the maximum number of winners supported by this algorithm is 100.

Solidity

function algorithmFisherYatesOriginal(bytes totalEntropy, uint32 nbParticipants, uint32 nbWinners) private returns (uint32[] memory)
{
    uint32[] memory winnerIndexes = new uint32[](nbWinners); // Fixed sized array, all elements initialize to 0
    uint32 from = 0;

    for (uint32 i = 0; i < nbWinners; i++) {
        bytes8 extractedEntropy = extractBytes8(totalEntropy, from);
        from += entropyNeededPerWinner;

        // When i winners are already selected, we only need a random number between 0 and nbParticipants - i - 1 to select the next winner.
        // ⚠️ Using 64-bit integers for the modulo operation is extremely important to prevent scaling bias ⚠️
        // Then it is fine to convert the result to a 32-bit integer because we know that the output of the modulo will always be stricly less than nbParticipants which is a 32-bit integer
        uint32 randomNumber = uint32(uint64(extractedEntropy) % uint64(nbParticipants - i));
        uint32 nextWinningIndex = randomNumber;
        uint32 min = 0;

        // Once a participant has been selected as a winner, it can never be selected again for that draw.
        // We enforce that by looping over all participants and ignoring those who are already known winners.
        // The offset variable keeps track of how many participants are ignored as we loop through the list and increments the next winning index accordingly.
        // When there is no more participants to ignore (offset == 0), it means we have reached the proper winning index so we break the loop and save this index.
        while (true) {
            uint32 offset = nbValuesBetween(winnerIndexes, min, nextWinningIndex, i);
            if (offset == 0) {
                break;
            }
            min = nextWinningIndex + 1;
            nextWinningIndex += offset;
        }

        winnerIndexes[i] = nextWinningIndex;
    }

    // We want to display line numbers, not indexes, so all indexes need to be +1
    for (uint32 i = 0; i < nbWinners; i++) {
        winnerIndexes[i] += 1;
    }

    return winnerIndexes;
}