contract.NextShuffler

NextShuffler

Git Source

Returns the next value in a shuffled list [0,n), amortising the shuffle across all calls to _next(). Can be used for randomly allocating a set of tokens but the caveats in dev docs MUST be noted.

Although the final shuffle is uniformly random, it is entirely deterministic if the seed to the PRNG.Source is known. This MUST NOT be used for applications that require secure (i.e. can't be manipulated) allocation unless parties who stand to gain from malicious use have no control over nor knowledge of the seed at the time that their transaction results in a call to _next().

State Variables

numToShuffle

Total number of elements to shuffle.

THIS LINE IS DIFFERENT, ORIGINALLY THIS VALUE IS IMMUTABLE

uint256 public numToShuffle;

shuffled

Number of items already shuffled; i.e. number of historical calls to _next(). This is the equivalent of i in the Wikipedia description of the Fisher–Yates algorithm.

uint256 private shuffled;

_permutation

A sparse representation of the shuffled list [0,n). List items that have been shuffled are stored with their original index as the key and their new index + 1 as their value. Note that mappings with numerical values return 0 for non-existent keys so we MUST increment the new index to differentiate between a default value and a new index of 0. See _get() and _set().

mapping(uint256 => uint256) private _permutation;

Functions

constructor

constructor(uint256 numToShuffle_);

Parameters

Name	Type	Description
numToShuffle_	uint256	Total number of elements to shuffle.

_get

Returns the current value stored in list index i, accounting for all historical shuffling.

function _get(uint256 i) private view returns (uint256);

_set

Sets the list index i to val, equivalent arr[i] = val in a standard Fisher–Yates shuffle.

function _set(uint256 i, uint256 val) private;

_next

Returns the next value in the shuffle list in O(1) time and memory.

NB: See the dev documentation of this contract re security (or lack thereof) of deterministic shuffling.

function _next(PRNG.Source src) internal returns (uint256);

Events

ShuffledWith

Emited on each call to _next() to allow for thorough testing.

event ShuffledWith(uint256 current, uint256 with);