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 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.