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