Gas-efficient stateless shuffle implemented in Solidity/Yul, for all your onchain permutation needs.

👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇

    npm install solshuffle

👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆

You've probably tried writing a raffle in Solidity. How much does it cost to pick 10 winners? 100? 1000? Probably millions of gas. Using solshuffle, you can determine the draw sequence of the user at the time of claiming. Combine this with a Merkle tree and you can have extremely efficient raffles (think cutting 10M gas down to <100k gas). Check out my talk at EthCC to learn how you can do extremely gas-efficient raffles with the Lazy Merkle Raffle.

Another application for solshuffle is to shuffle NFT token identifiers. You've probably seen NFT contracts that simply add a randomised offset and call that a "shuffle". Now you can stop faking it and actually shuffle your token identifiers.

Shoutout to @rpal_ for shilling me cool shuffle algos!

Find the accompanying TypeScript library (and reference implementation) here.

Difficulty level: SHADOWY SUPER CODER 🥷

Shown below is a truncated example of how you'd shuffle your ERC721 metadata using the FeistelShuffleOptimised library, after calling a VRF (or whatever) to set a randomSeed.

import { Strings } from "@openzeppelin/contracts/utils/Strings.sol";
import { ERC721 } from "@openzeppelin/contracts/token/ERC721/ERC721.sol";
import { ERC721Enumerable } from "@openzeppelin/contracts/token/ERC721/extensions/ERC721Enumerable.sol";
import { FeistelShuffleOptimised } from "solshuffle/contracts/FeistelShuffleOptimised.sol";

contract ERC721Shuffled is ERC721, ERC721Enumerable {
    using Strings for uint256;

    /// @notice The first token ID. For most NFT collections, this is 1.
    uint256 public constant FIRST_TOKEN_ID = 1;
    /// @notice The max supply is used as the modulus parameter in the shuffle algos.
    uint256 public immutable maxSupply;
    /// @notice Random seed that determines the permutation of the shuffle,
    ///     should only be set once.
    bytes32 public randomSeed;

    /// @notice Return a shuffled tokenURI, calculated just-in-time when this function
    ///     is called
    /// @param tokenId token id
    /// @return URI pointing to metadata
    function tokenURI(
        uint256 tokenId
    ) public view virtual override returns (string memory) {
        require(randomSeed != 0, "random seed must be initialised!!!");
        _requireMinted(tokenId);

        // statelessly map tokenId -> shuffled tokenId,
        // deterministically according to the `randomSeed` and `rounds` parameters
        uint256 shuffledTokenId = FIRST_TOKEN_ID +
            FeistelShuffleOptimised.shuffle(
                tokenId -
                    FIRST_TOKEN_ID /** shuffle is 0-indexed, so we add offsets */,
                maxSupply /** Must stay constant */,
                uint256(randomSeed) /** Must stay constant (once set) */,
                4 /** Must stay constant */
            );

        // use the shuffled tokenId as the metadata index
        return string(abi.encodePacked(_baseURI(), shuffledTokenId.toString()));
    }
}

The stateless shuffle implemented by solshuffle is the Generalised Feistel Cipher, but we'll just call it the Feistel Shuffle. The Feistel shuffle is cheap, coming in at ~4350 gas to calculate a permutation for a single index for a list size of 10,000.

Feistel networks are based on round functions, and these are run a fixed number of times, as specified in the rounds parameter. As long as you input a cryptographically secure random seed, it is sufficient to set rounds = 4 to make a strong pseudorandom permutation [1].

The figure below shows the distribution of shuffled indices (y-axis) against their original indices (x-axis) when picking $y \mid 0 \leq y \lt 1000$ with modulus = 10_000. Each colour represents a different run, with its own 32-byte cryptorandom seed. Every run sets rounds = 4. Re-run this for yourself with yarn plot:feistel.

domain = 96_722
┌─────────────────────────┬────────┬──────┬───────┬──────┐
│         (index)         │ rounds │ min  │  max  │ avg  │
├─────────────────────────┼────────┼──────┼───────┼──────┤
│ FeistelShuffleOptimised │   4    │ 4008 │ 5430  │ 4040 │
│     FeistelShuffle      │   4    │ 7255 │ 11786 │ 7297 │
└─────────────────────────┴────────┴──────┴───────┴──────┘

This repository has not received an individual security audit. However, both FeistelShuffle.sol and FeistelShuffleOptimised.sol were audited by Trail of Bits as part of the Ethereum Foundation's Devcon Auction-Raffle contracts. View the audit here.

This library is permissively licenced with the MIT license. Send tokens to kevincharm.eth if you find the library useful for your project :^)

Ensure you understand the theory behind the Generalised Feistel Cipher, such as the iteration upper bounds, which may consume more gas than the expected average in unlucky scenarios.

soon™

[1] M. Luby and C. Rackoff, “How to construct pseudorandom permutations from pseudorandom functions,” SIAM Journal on Computing, vol. 17, no. 2, pp. 373–386, 1988.

[2] V. T. Hoang, B. Morris, and P. Rogaway, “An enciphering scheme based on a card shuffle,” in Annual Cryptology Conference, 2012, pp. 1–13.