Skip to main content

Improving the Devcon Raffle

The main parts of the relevant code in AuctionRaffle.sol that orchestrated the 2022 Devcon Raffle is shown below. The full repository can be found at https://github.com/TrueFiEng/devcon-raffle.

/**
  * @notice Draws raffle winners and changes contract state to RAFFLE_SETTLED. The first selected raffle winner
  * becomes the Golden Ticket winner.
  * @dev Sets WinType of the first selected bid to GOLDEN_TICKET. Sets WinType to RAFFLE for the remaining selected
  * bids.
  * @param randomNumbers The source of randomness for the function. Each random number is used to draw at most
  * `_winnersPerRandom` raffle winners.
  */
function settleRaffle(uint256[] memory randomNumbers) external onlyOwner onlyInState(State.AUCTION_SETTLED) {
    require(randomNumbers.length > 0, "AuctionRaffle: there must be at least one random number passed");

    _settleState = SettleState.RAFFLE_SETTLED;

    uint256 participantsLength = _raffleParticipants.length;
    if (participantsLength == 0) {
        return;
    }

    (participantsLength, randomNumbers[0]) = selectGoldenTicketWinner(participantsLength, randomNumbers[0]);

    uint256 raffleWinnersCount = _raffleWinnersCount;
    if (participantsLength < raffleWinnersCount) {
        selectAllRaffleParticipantsAsWinners(participantsLength);
        return;
    }

    require(
        randomNumbers.length == raffleWinnersCount / _winnersPerRandom,
        "AuctionRaffle: passed incorrect number of random numbers"
    );

    selectRaffleWinners(participantsLength, randomNumbers);
}

function addRaffleWinner(uint256 bidderID) private {
    setBidWinType(bidderID, WinType.RAFFLE);
    _raffleWinners.push(bidderID);
    emit NewRaffleWinner(bidderID);
}

function addGoldenTicketWinner(uint256 bidderID) private {
    setBidWinType(bidderID, WinType.GOLDEN_TICKET);
    _raffleWinners.push(bidderID);
    emit NewGoldenTicketWinner(bidderID);
}

/**
  * @dev Selects `_winnersPerRandom` - 1 raffle winners for the first random number -- it assumes that one bidder
  * was selected before as the Golden Ticket winner. Then it selects `_winnersPerRandom` winners for each remaining
  * random number.
  * @param participantsLength The length of current participants array
  * @param randomNumbers The array of random numbers to select raffle winners from
  */
function selectRaffleWinners(uint256 participantsLength, uint256[] memory randomNumbers) private {
    participantsLength = selectRandomRaffleWinners(participantsLength, randomNumbers[0], _winnersPerRandom - 1);
    for (uint256 i = 1; i < randomNumbers.length; ++i) {
        participantsLength = selectRandomRaffleWinners(participantsLength, randomNumbers[i], _winnersPerRandom);
    }
}

/**
  * @notice Selects a number of raffle winners from _raffleParticipants array. Saves the winners in _raffleWinners
  * array and sets their WinType to RAFFLE.
  * @dev Divides passed randomNumber into `_randomMaskLength` bit numbers and then selects one raffle winner using
  * each small number.
  * @param participantsLength The length of current participants array
  * @param randomNumber The random number used to select raffle winners
  * @param winnersCount The number of raffle winners to select from a single random number
  * @return New participants length
  */
function selectRandomRaffleWinners(
    uint256 participantsLength,
    uint256 randomNumber,
    uint256 winnersCount
) private returns (uint256) {
    for (uint256 i = 0; i < winnersCount; ++i) {
        uint256 winnerIndex = winnerIndexFromRandomNumber(participantsLength, randomNumber);

        uint256 bidderID = _raffleParticipants[winnerIndex];
        addRaffleWinner(bidderID);

        removeRaffleParticipant(winnerIndex);
        --participantsLength;
        randomNumber = randomNumber >> _randomMaskLength;
    }

    return participantsLength;
}

/**
  * @notice Removes a participant from _raffleParticipants array.
  * @dev Swaps _raffleParticipants[index] with the last one, then removes the last one.
  * @param index The index of raffle participant to remove
  */
function removeRaffleParticipant(uint256 index) private {
    uint256 participantsLength = _raffleParticipants.length;
    require(index < participantsLength, "AuctionRaffle: invalid raffle participant index");
    _raffleParticipants[index] = _raffleParticipants[participantsLength - 1];
    _raffleParticipants.pop();
}

/**
  * @notice Calculates winner index
  * @dev Calculates modulo of `_randomMaskLength` lower bits of randomNumber and participantsLength
  * @param participantsLength The length of current participants array
  * @param randomNumber The random number to select raffle winner from
  * @return Winner index
  */
function winnerIndexFromRandomNumber(uint256 participantsLength, uint256 randomNumber)
    private
    pure
    returns (uint256)
{
    uint256 smallRandom = randomNumber & _randomMask;
    return smallRandom % participantsLength;
}

Using the above code, the settleRaffle transaction costed 9,660,228 gas to pick 80 winners for the raffle.

Can we do better?​

Since the Devcon Raffle is already a fully-on-chain raffle, we don't even need to use the RaffleChef contract or have anything to do with Merkle trees.

First, we'll extend the AuctionRaffle contract with an ERC721 implementation so we can mint winning tickets as NFTs. Then, we simply need to import and call the FeistelShuffle library to shuffle (produce a pseudorandom permutation of) the participants list that we will pick winners from. As a consequence, the contract also becomes much simpler.

public uint256 _randomSeed;

/**
  * @notice Draws raffle winners and changes contract state to RAFFLE_SETTLED. The first selected raffle winner
  * becomes the Golden Ticket winner.
  * @param randomSeed A single 256-bit random seed.
  */
function settleRaffle(uint256 randomSeed) external onlyOwner onlyInState(State.AUCTION_SETTLED) {
    _settleState = SettleState.RAFFLE_SETTLED;
    // NB: This sufficiently finalises the shuffled list. Winners may begin
    //    claiming their winning tickets after the following statement.
    _randomSeed = randomSeed;
}

/**
 * @notice Claim a winning ticket as an NFT. The token ID minted corresponds to
 *    the winner's drawn index.
 * @param participantIndex The index of the participant in the
 *    `_raffleParticipants` array that wishes to claim a winning ticket. The
 *    function will revert if the participant isn't actually a winner.
 */
function claimWinningTicket(uint256 participantIndex) external {
    uint256 randomSeed = _randomSeed;
    require(randomSeed != 0, "Raffle not yet settled");
    uint256 participantsLength = _raffleParticipants.length;
    require(participantIndex < participantsLength, "Index out-of-bounds");

    // Calculate the shuffled index
    uint256 shuffledIndex = FeistelShuffle.getPermutedIndex(
        participantIndex,
        participantsLength,
        randomSeed,
        4 /** Feistel shuffle rounds; can be increased as desired but must be immutable */
    );
    require(shuffledIndex < _raffleWinnersCount, "Not a winner!");
    uint256 winningBidderId = _raffleParticipants[participantIndex];

    // Mint an NFT to the winning bidder's address. The token ID corresponds to
    // their drawn index, i.e. tokenId=shuffledIndex=0 is the golden ticket winner.
    _mint(_bidders[winningBidderId], shuffledIndex);
}

Implementing the contract as shown above would reduce the gas required from 9,660,228 down to ~60,000 to pick 80 winners. In fact, we can pick any amount of winners and the gas consumption stays constant for settleRaffle. This makes it economically viable to perform the raffle on Ethereum Mainnet, and enables us to use on-chain entropy sources such as the Beacon Chain RANDAO or Chainlink VRF.

Additionally, we don't risk modulo bias like in Fisher-Yates shuffles as the Feistel Shuffle produces pseudorandom permutations of the original participants list.

There is however an extra requirement that users must claim a winning ticket NFT to record the winners on-chain (we are applying the pull-over-push pattern commonly used in airdrops here); but this part is not strictly necessary, as the list of raffle winners may be deterministically reproduced once a random seed has been committed. We can optimistically consider the raffle winners as finalised as soon as settleRaffle is successfully called with a random seed.