🃏 solshuffle 🃏

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

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

pnpm add solshuffle

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

Solidity 0.8.13 or newer is required.

1) What

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!

Version 2 replaces the old generalised Feistel construction with a Thorp shuffle. This is a breaking change. There are deliberately no Feistel compatibility wrappers.

Usage

Both libraries have the same API:

shuffle(uint256 x, uint256 domain, uint256 seed, uint256 rounds)
deshuffle(uint256 x, uint256 domain, uint256 seed, uint256 rounds)
defaultRounds(uint256 domain)

ThorpShuffle is the readable implementation. ThorpShuffleOptimised implements the same thing in Yul and is the one you'll probably deploy.

Example: Just-in-time NFT tokenId<->metadata shuffle

Difficulty level: SHADOWY SUPER CODER 🥷

Call defaultRounds once and cache the result as an immutable. No round count is calculated or enforced inside shuffle or deshuffle.

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

contract ERC721Shuffled {
    uint256 public immutable maxSupply;
    uint256 public immutable shuffleRounds;
    bytes32 public randomSeed;

    constructor(uint256 maxSupply_) {
        maxSupply = maxSupply_;
        shuffleRounds = ThorpShuffleOptimised.defaultRounds(maxSupply_);
    }

    function shuffledTokenId(uint256 tokenId) public view returns (uint256) {
        require(randomSeed != 0, "random seed must be initialised!!!");
        return 1 + ThorpShuffleOptimised.shuffle(
            tokenId - 1,
            maxSupply,
            uint256(randomSeed),
            shuffleRounds
        );
    }
}

The full example lives in contracts/examples/ERC721Shuffled.sol.

Keep domain, seed, and rounds constant for the lifetime of a permutation. A secure seed is the caller's responsibility; use VRF or another source appropriate to your threat model. If somebody can choose or retry the seed after seeing the result, you have built a seed-shopping machine.

Specifications

For a requested domain D, the implementation operates on the evenised domain M = D + (D & 1). Each Thorp round splits an index into one bit and a half-index, then uses the low bit of:

keccak256(abi.encodePacked(seed, M, halfIndex, round))

All four values are uint256, so the preimage is exactly four packed 32-byte words in that order. deshuffle applies the same round functions in reverse.

defaultRounds(D) returns 4 * ceil(log2(M)). The returned round count is an empirical default, and is not calculated inside shuffle or deshuffle. An exactly uniform permutation and a bound on a distinguisher's advantage are not guaranteed at this round count. Supplying zero rounds gives the identity permutation. The libraries accept a one-element domain, and reject zero, an out-of-range index, and type(uint256).max.

An exactly uniform permutation cannot be sampled from a uniform 256-bit seed for any D >= 3, because D! does not divide 2**256. The exact small-domain results quantify the idealised Thorp bias separately from that finite-seed limit.

The concrete CCA result in the CRYPTO 2009 paper assumes N = 2**n, independent ideal round functions, a query budget q, and r * (4n - 2) rounds. Its bound is:

Adv <= (2q / (r + 1)) * (4nq / N)**r

The default profile is close to that theorem's r = 1 schedule; it is not derived from your query budget, attack model, or target advantage. Odd-domain cycle walking and the use of keccak256 are outside the theorem's assumptions.

Odd domains and the actual worst case

When D is odd, evenisation adds one excluded element. The implementation evaluates the complete permutation once and, only if the result is the excluded element, evaluates it once more. That is the entire cycle walk.

The bound is two complete permutation evaluations, not 2D. The excluded element has exactly one preimage. If a valid input maps to it, the excluded element cannot also map to itself, so the second result must be valid. Therefore:

• even domains require exactly rounds hashes;
• odd domains require at most 2 * rounds hashes.

The same argument holds for deshuffle.

Selecting more rounds costs linearly more gas. The NFT example and statistical test suite use the profile returned by defaultRounds. Callers with a query volume, attack model, or target advantage that needs a different policy can supply another round count directly.

Statistical tests

Four rounds is included as a negative control: a fixed input can reach at most 16 outputs after four binary rounds.

Marginal distributions, pairwise projections, and whole-permutation features are sampled by the native C17 oracle and compared with a uniform Fisher-Yates baseline. The even-domain ideal round-bit model is calculated exactly by dynamic programming, and complete idealised permutations are enumerated for domains 1-8. The deep profile is configured for 10 million seeds and 10,000 complete permutations per distinct domain and round count.

See the generated statistical report, including the marginal bias plot, the exact even-domain plot, and the whole-permutation comparison.

Failure to detect bias is not proof of uniformity or PRP security. In particular, the empirical keccak256 results, the exact ideal-round-bit calculation, and published Thorp bounds answer different questions. The assumptions for each are stated separately in the report.

Run the quick CI profile with:

pnpm stats:smoke

You can run the expensive deep profile with:

pnpm stats

pnpm stats:full remains available as a one-million-seed intermediate run. Raw native counts and intermediate reports are written to the ignored .stats/ directory. The profile is recorded in the committed report during generation.

Gas benchmarks

The benchmark includes even domains, odd inputs that finish after one evaluation, and odd inputs that hit the two-evaluation bound, in both directions. See the complete gas table. For a 10,000-element even domain, an optimised shuffle using the default round count currently costs 34,892 gas through the benchmark consumer. The corresponding odd-domain two-evaluation witness costs 47,142 gas.

pnpm benchmark

CI fails if an optimised measurement exceeds the committed snapshot by more than 2%.

Development

The repository uses Node 24, pnpm 10, Hardhat 3, Viem, Node's test runner, Solidity tests, a C17 oracle, and a PEP 723 Python analysis script run through uv.

pnpm install --frozen-lockfile
pnpm check
pnpm test
pnpm oracle:test
pnpm stats:smoke

The Solidity tests fuzz round trips, inverse round trips, bounds, and readable/Yul equivalence. The TypeScript tests add exhaustive small-domain bijectivity, boundary vectors, example behaviour, C/Solidity differential vectors, and the gas snapshot.

Security

The v2 Thorp implementation has not received an individual security audit. Trail of Bits reviewed the old v1 Feistel implementation as part of the Ethereum Foundation's Devcon Auction-Raffle contracts; that audit does not cover ThorpShuffle or ThorpShuffleOptimised.

License

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

WEN TOKEN?

soon™

References

• Ben Morris, Phillip Rogaway, and Till Stegers, How to encipher messages on a small domain, CRYPTO 2009.
• Ben Morris, The mixing time for simple exclusion, 2009.