Solshuffle: Gas-Efficient Stateless Shuffles on EVM

30 June 2024

kevincharm.eth

0x77fb..e693

Today I’m releasing a library that I’ve been using for a couple of years to power raffles and other kinds of onchain permutations. It’s called solshuffle and you can find it on github and npm.

solshuffle implements the Feistel Shuffle, which is a generalised Feistel cipher that implements format-preserving encryption, bijectively mapping $X \rightarrow X$ with pseudorandom permutation $\pi^S$ determined by a random seed $S$. This algorithm was originally proposed by Black & Rogaway ¹. Using the Feistel Shuffle, we can efficiently compute shuffles in the EVM by eliminating writes to storage due to its stateless nature.

But what for can I use it, sir?

You’ve probably tried writing a raffle in Solidity. How much does it cost to pick 10 winners? 100? 1000? Probably millions of gas… and it might not even fit in a block. 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 less than 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.

Let’s dive into some examples of how you can use this library!

Example #1: Raffles

The conventional, naïve way to draw winners in a raffle is to use the Fisher-Yates shuffle as shown below. This involves writing to storage multiple times per winner, which is expensive on the EVM. You must also draw winners sequentially before prizes can be claimed, and gas cost is linear with the number of winners to be picked. This puts a limit on the number of winners you can draw in a single transaction (because of block gas limits).

contract Raffle {
    // Number of winners to pick
    uint256 public immutable numberOfWinners;
    // List of participants in the raffle
    address[] public participants;
    // Random seed from VRF
    uint256 public randomSeed;

    // Tired: sequentially draw winners
    function draw() public {
        require(randomSeed != 0, "set a random seed");
        uint256 rand = randomSeed;
        for (uint256 i; i < numberOfWinners; ++i) {
            // Generate a random index without modulo bias
            uint256 n = participants.length;
            uint256 upperBound = type(uint256).max - (type(uint256).max % n);
            rand = uint256(keccak256(abi.encodePacked(rand)));
            if (rand >= upperBound) {
                rand = uint256(keccak256(abi.encodePacked(rand)));
            }

            // Pick a winner
            uint256 index = rand % n;
            address winner = participants[index];
            // Remove winner from participants list
            participants[index] = participants[n - 1];
            participants.pop();
            // Transfer some prize to the winner here...
        }
    }
}

With solshuffle, you can draw winners in a raffle with constant gas cost, regardless of the number of winners to be picked. The gas cost is also independent of the number of participants or winners. After a random seed is set, winners of the raffle can asynchronously claim prizes, in any order. This is similar to a Merkle airdrop, pushing a minimal gas cost overhead to the user during claiming. An example of how to do this is shown below.

import {FeistelShuffleOptimised} from "solshuffle/contracts/FeistelShuffleOptimised.sol";

contract Raffle {
    // Number of winners to pick
    uint256 public immutable numberOfWinners;
    // List of participants in the raffle
    address[] public participants;
    // Claim nullifier
    mapping(uint256 p => bool) public isClaimed;
    // Random seed from VRF
    uint256 public randomSeed;

    // Wired: winner permissionlessly claims a prize
    function claimNthPrize(uint256 n) public {
        require(randomSeed != 0, "set a random seed");
        require(n < numberOfWinners, "not a winner, sorry!");

        // Map the nth winner back to the original participant index
        uint256 p = FeistelShuffleOptimised.deshuffle(
            n,
            participants.length /** Must stay constant */,
            randomSeed /** Must stay constant (once set) */,
            4 /** Feistel rounds; must stay constant */
        );
        require(!isClaimed[p], "already claimed");
        isClaimed[p] = true;
        require(participants[p] == msg.sender, "only winner may claim!");
        // Transfer some prize to the caller here...
    }
}

Example #2: Shuffle NFT tokenIds

Shown below is a truncated example of how you’d shuffle your ERC721 metadata using the FeistelShuffleOptimised library, after setting the 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()));
    }
}

In the wild: Devcon Auction-Raffle

If you’ve been on CT lately, you’ve probably seen the Devcon Auction-Raffle: a fun way of distributing early tickets to people who wish to attend Devcon while showing off what you can do with smart contracts on Ethereum. The tl;dr — it’s a combined auction and raffle where the 20 highest bidders each win a ticket, and the rest of the participants are entered into a raffle for the remaining 184 tickets.

The original code was written by the chads at Archblock, and implements a max-heap to efficiently sort the auctions in order of bid value. I had the pleasure of optimising the raffle part of the code by replacing the Fisher-Yates shuffle with the Feistel Shuffle. The previous version of the raffle used 9,660,228 gas to pick 80 raffle winners, and integrating the Feistel Shuffle would have reduced the cost to around 60,000 gas (for any number of winners)! This year we are drawing 184 raffle winners, so it presents even more gas savings.

This repository was audited by Trail of Bits, which included FeistelShuffle.sol and FeistelShuffleOptimised.sol. You can read the audit here.

I look forward to seeing more usage of the Feistel Shuffle onchain. Let me know if you use it in your project!

Acknowledgments

Shoutout to @rpal_ for shilling me stateless shuffles in the first place, and to Vitalik for his (not-quite-invertible?) Python implementation that inspired this library.

References