The randomness algorithm implements Sattolo's algorithm instead of Fisher-Yates

[cleanunicorn]

Description

The randomness function is called once to shuffle the tickets.

https://github.com/monoceros-alpha/review-elrond-launchpad-2021-10/blob/a32fe0b2ef7430e9b86d6b22da60b697f8eaac3c/code/launchpad/src/launchpad.rs#L123-L125

This method needs to loop over each position, select a random ticket and put the ticket at that position. The method shuffle_single_ticket is called to pick a random ticket and place it in the current position.

https://github.com/monoceros-alpha/review-elrond-launchpad-2021-10/blob/a32fe0b2ef7430e9b86d6b22da60b697f8eaac3c/code/launchpad/src/launchpad.rs#L136-L143

After each swap, the position is incremented by 1.

https://github.com/monoceros-alpha/review-elrond-launchpad-2021-10/blob/a32fe0b2ef7430e9b86d6b22da60b697f8eaac3c/code/launchpad/src/launchpad.rs#L136-L143

The method shuffle_single_ticket picks a random ticket and places it in the current position (current_ticket_position).

https://github.com/monoceros-alpha/review-elrond-launchpad-2021-10/blob/a32fe0b2ef7430e9b86d6b22da60b697f8eaac3c/code/launchpad/src/launchpad.rs#L438-L446

This part selects a number between current_ticket_position + 1 and last_ticket_position inclusive.

https://github.com/monoceros-alpha/review-elrond-launchpad-2021-10/blob/a32fe0b2ef7430e9b86d6b22da60b697f8eaac3c/code/launchpad/src/launchpad.rs#L447-L448

The Fisher-Yates algorithm states that you should pick a number between the current position and the last position. The current position should be included in the selection range.

Wikipedia describes a variation of this algorithm, named Sattolo's algorithm.

A very similar algorithm was published in 1986 by Sandra Sattolo for generating uniformly distributed cycles of (maximal) length n.[6][7] The only difference between Durstenfeld's and Sattolo's algorithms is that in the latter, in step 2 above, the random number j is chosen from the range between 1 and i−1 (rather than between 1 and i) inclusive. This simple change modifies the algorithm so that the resulting permutation always consists of a single cycle.

The current code actually implements the Sattolo's algorithm because it selects items to swap from the current_ticket_position + 1 instead of current_ticket_position.

The Wikipedia page warns this can be easy to accidentally implement.

In fact, as described below, it is quite easy to accidentally implement Sattolo's algorithm when the ordinary Fisher–Yates shuffle is intended. This will bias the results by causing the permutations to be picked from the smaller set of (n−1)! cycles of length N, instead of from the full set of all n! possible permutations.

Technically the current code version implements Sattolo's algorithm instead of Fisher-Yates which is mentioned in the comments.

https://github.com/monoceros-alpha/review-elrond-launchpad-2021-10/blob/a32fe0b2ef7430e9b86d6b22da60b697f8eaac3c/code/launchpad/src/launchpad.rs#L438-L440

Recommendation

Change the selection interval to include the current_ticket_position when selecting a random number.

This code should use current_ticket_position instead of current_ticket_position + 1.

https://github.com/monoceros-alpha/review-elrond-launchpad-2021-10/blob/a32fe0b2ef7430e9b86d6b22da60b697f8eaac3c/code/launchpad/src/launchpad.rs#L447-L448

References

• Fisher-Yates shuffle
• Sattolo's algorithm