Running A Charity Token Auction

August 16 2022


Introduction


In this post we are going to be building a token auction program for the Solana blockchain. Participants will be bidding on a block of one hundred tokens, where their chance of being the next winner is proportional to the size of their bid. They will also be able to decide how much of their bid we keep, and how much we donate to charity, as well as selecting which charity we donate to from a set of provided options.

The more people that take part in the auction the faster new winners will be selected, with new rounds initially spaced out on minute timescales, but reducing to seconds as the number of participants increases. More people also means more winners will be selected in each round, starting with a single winner and increasing up to four. A participant's bid will roll over into subsequent rounds and can be added to at any point in order to improve their chances of being chosen as the next winner.

In describing the program we will reference a couple of our previous articles; Firstly we will be using Pyth to seed the random number generators used in the auction using the same process we described here, and secondly all the donations will be handled via The Giving Block as in our charity token launch post here.

We decided to make the chance of winning proportional to the size of the bid in order to make the auction as fair as possible to all participants, and avoid the situation where a small number of high-bidders end up receiving all the tokens. In order to do this, however, we need to store and process all the prevailing bids in order to produce a cumulative distribution whenever new winners are chosen. Given the limitations on how much computation can be done within a single transaction, we therefore impose a maximum number of bids that can be tracked at any point in time, which we set to 1024 in this example. If a new bidder enters the auction when this buffer is full, the oldest bid at that point in time is lost, and replaced with the new bid. Participants will however be able to 'refresh' the time of their bid by adding to it, and whenever new winners are selected this naturally frees up space in the buffer.

In addition to needing to save the size of each bid, we also keep a record of the time each bid is placed. This is to stop users from placing their bid in the same block that winners are being chosen, which could let them pre-determine the random numbers that will be generated and only bid if they knew they were going to win. By tracking the times of each bid we can ensure that for each round in the auction, we only include bids that were made a short interval before that round ends.

The program has four main functions, which we will go through in detail below:


At the end of the post you will also find a simple front end application that interacts with the token auction program currently running on the Solana devnet. You can skip to it here if you are interested in trying the final product before working through the code. You can find the source code both for the on-chain program, and a rust client that interacts with it here

Before going through the program functions themselves, however, we will just have a quick aside on managing large data accounts on the Solana blockchain.

Managing Lots Of Data On Chain


One issue that we ran up against a lot with this program was the 4kb stack frame that all programs running on the Solana blockchain must limit themselves to. This means that you need to ensure that you don't use more than 4kb of data within a given scope (for example, within a function). There are many posts online outlining the issue (for example, here), and while there are improvements in the pipeline, for example just increasing this to 8kb, for now programs that have lots of data stored on chain need to be careful how that data is accessed in the program.

In our case the data on chain is about 50kb, most of which is taken up with the vectors that contain the bid amounts, public keys, and bid times of the auction participant:



    // in state.rs
    pub struct State {


        // The last time we chose winners, used to compute how soon we can choose again
        pub prev_selection_time: i64,


        // the number of active bids in the system up to MAX_BIDDERS
        pub n_bidders: u16,
        // the sum of all the current bids
        pub total_bid_amount : u64,


        // for each bid we track the key, amount and time
        pub bid_keys : [Pubkey; MAX_BIDDERS],
        pub bid_amounts: [u64; MAX_BIDDERS],
        pub bid_times: [i64; MAX_BIDDERS],


        // the number of winners to be chosen, up to MAX_WINNERS, and their keys
        pub n_winners : u8,
        pub winners: [Pubkey; MAX_WINNERS],


        // summary of the charity stats for the auction
        pub charity_data : CharityData
    }

Note that although we define this in state.rs at no point do we ever try and access the whole state on chain, it is there primarily as a reference. The final entry charity_data is the same struct that we used in our charity token launch post to store the summary statistics of the donations made and the breakdown per charity.

In order to try and make it easier to grab different bits of data from this struct we first define the following enum, which includes an entry for each item in State. For the vectors the entries take an additional index argument, which is used to specify which element of the vector we want to access:



    // in state.rs
    // we can't unpack  the whole state in one go due to stack limits on chain.
    // we create an enum to make it easier to access elements  within the state
    pub enum StateEnum {


        PrevSelectionTime,


        NBidders,
        TotalBidAmount,


        BidKeys{
            index: usize
        },
        BidAmounts{
            index: usize
        },
        BidTimes{
            index: usize
        },


        NWinners,
        Winners{
            index: usize
        },


        CharityData  
    }

Given this enum we then define the following function, get_state_index, which takes an entry from StateEnum and returns a tuple that provides the start and end bytes for that element of the state.



    // in state.rs
    pub fn get_state_index(element: StateEnum) -> (usize, usize) {


        match element {


            // the unix timestamp that winners were last selected, 8 bytes
            StateEnum::PrevSelectionTime => {(0, 8)}
        
            // the number of bidders, 2 bytes
            StateEnum::NBidders => {(8, 10)}
            // the total amount bid currently in the ladder, 8 bytes
            StateEnum::TotalBidAmount => {(10, 18)},


            // the list of bidder pubkeys, each is 32 bytes
            StateEnum::BidKeys{index} => {(18 + index * 32, 18 + (index + 1) * 32)},
            // the list of corresponding bid amounts, each is 8 bytes
            StateEnum::BidAmounts{index} => {(32786 + index * 8, 32786 + (index + 1) * 8)},
            // the list of corresponding bid amounts, each is 8 bytes
            StateEnum::BidTimes{index} => {(40978 + index * 8, 40978 + (index + 1) * 8)},


            // the number of winners selected, 1 byte
            StateEnum::NWinners => {(49170, 49171)},
            // pubkeys of the selected winners, each is 32 bytes
            StateEnum::Winners{index} => {(49171 + index * 32, 49171 + (index + 1) * 32)},
            
            // the Charity data is 80 bytes
            StateEnum::CharityData => {(49299, 49379)}
        }
    }

While this is not the prettiest function, it means that wherever we access an element of State in the code we can simply ask for the byte range of that item by doing something like:



    let key_idx = get_state_index(StateEnum::BidKeys{index: 0});

and can then get the start and end bytes by accessing key_idx.0 and key_idx.1 without having to repeatedly hard code the values. If we change the contents of State we just update StateEnum and get_state_index and the rest of the code will work without change.

While the above would allow us to iterate through the vectors and to grab the elements individually, this is not very computationally cost effective. We therefore also define a few helped structs to allow us to access chunks of these vectors in sizes that won't violate the stack frame size.



    pub struct BidValues {
        pub bid_amounts: [u64; BID_BLOCK],
    }


    pub struct BidTimes {
        pub bid_times: [i64; BID_BLOCK],
    }


    pub struct WinnersKeys {
        pub keys: [Pubkey; MAX_WINNERS],
    }

In state.rs we define BID_BLOCK to be 64, so BidValues and BidTimes are each 512 bytes. Although this is well inside the 4kb limit, due to how these structures are accessed within the code trying to make them any larger led to the program violating the stack size limit.

Initializing The Program


When first initializing the auction program there are four steps that need to be taken:


The first three of these tasks are described in detail in our charity token launch post, which you can see here. In this program we just call the create_program_account, create_token_account and transfer_tokens functions described in that post.

Unfortunately the final task of creating the program's data account needs to be handled off chain. This is because there are limitations to the size of the account that can be created on chain of about 10Kb, and we exceed that by some margin. You can find the code for the rust client that implements this functionality here.

Much like when finding a program derived address, Solana provides the create_with_seed function to determine the address of a data account using a seed phrase and a base_key. These are passed as arguments along with the public key of the owner (the program in this case):



    let program_data_account = Pubkey::create_with_seed(
        &daoplays,
        "data_account",
        &program,
    )?;

The public key generated by this function can then be passed to the create_account_with_seed function, along with the size of the account and the balance that needs to be transferred to ensure it is rent exempt:



    let data_size: usize = 49381;
    let space : u64 = data_size.try_into().unwrap();
    let lamports = rent::Rent::default().minimum_balance(data_size);


    let instruction = solana_sdk::system_instruction::create_account_with_seed(
        &wallet.pubkey(),
        &data_account,
        &wallet.pubkey(),
        "data_account",
        lamports,
        space,
        &program,
    );

With that we have everything set up that the program will need, and we can move on to actually placing bids in the auction!

Placing A Bid


The process_place_bid function, which handles new bids from the auction's participants, has the following overall flow:


The first four of these tasks follow exactly the same format as when joining the charity token launch here, so we will skip over those in this post. The first new task is to create a new PDA for the program which will use the bidder's public key as the seed to find the address:



    Pubkey::find_program_address(&[&bidder_account_info.key.to_bytes()], &program_id);

This account needs to hold a single instance of the BidderData struct, defined below:



    // in state.rs
    pub struct BidderData {
        pub index : u16
    }

This will store the index into the three bid data arrays contained in the program's State (bid_keys, bid_amounts, and bid_times) that are associated with this participant's most recent bid. Whenever a new bid is made we can check if the participant has an existing bid by just checking the public key in the program's bid_keys array at position index, rather than searching through all the keys in the array, which is extremely inefficient.



    ...


    // get the bid index from the bidders account
    let bidder_data = BidderData::try_from_slice(&bidder_data_account_info.data.borrow()[..])?;




    // when adding the bid to the program state we have three possibilities:
    // i) there is already a bid and we just accumulate
    // ii) there is no bid but there is an empty spot
    // iii) there is no bid and no empty spot, so we replace the oldest bid


    // start by checking if a bid exists
    let mut bidders_index = bidder_data.index as usize;


    // check the public key that is present in the data account at bid_index
    let key_idx = get_state_index(StateEnum::BidKeys{index: bidders_index});
    let key = Pubkey::try_from_slice(&program_data_account_info.data.borrow()[key_idx.0..key_idx.1])?;


    ...

What we do next depends on whether the public key at that position matches the bidder. If it does then the bidder has a valid bid already in the system, and we just have to increment the value of the bid by the new amount:



    ...


    // if the keys match then we accumulate the bid
    // otherwise it must be a new bid
    if key == *bidder_token_account_info.key {


        // get the old bid
        let old_bid_idx = get_state_index(StateEnum::BidAmounts{index: bidders_index});
        let old_bid =  u64::try_from_slice(&program_data_account_info.data.borrow()[old_bid_idx.0..old_bid_idx.1])?;
                        
        new_bid += old_bid;
    }


    ...

If the keys don't match we know we have a new bid, and so we will either insert the bid into an empty slot in the program's State, or if there are no empty slots then we are going to need to replace the oldest bid.

Given we might need the oldest bid, we iterate through the bid_times array to find the first element that is zero, which indicates an empty slot. As we iterate through we also track oldest_bid_index, which if we make it all the way through the loop without finding an empty slot will point to the entry in the data that contains the oldest bid. Note in the below we are making use of our BidTimes helper struct, so that we can deserialize in chunks of BID_BLOCK entries and still remain in the 4kb stack frame limit.



    ...


    // if they were a new bidder add their bid to the ladder, first just try and find the first open spot
    let mut found_space = false;
    
    // if there isn't a space we will want to replace the oldest bid
    // so we find  that in the same loop
    let mut oldest_bid_index : usize = 0;
    let mut oldest_time = i64::MAX;
    for i in 0..N_BID_BLOCKS {




        let time_idx = get_state_index(StateEnum::BidTimes {index: i * BID_BLOCK});
        let times = BidTimes::try_from_slice(&program_data_account_info.data.borrow()[time_idx.0..time_idx.0 + BID_BLOCK * 8])?; 


        for j in 0..BID_BLOCK {


            let total_index = i * BID_BLOCK + j;


            // if the bid time is zero that indicates we have found an empty slot, so break out of the loop
            if times.bid_times[j] == 0 {
                bidders_index = total_index;
                found_space = true;
                break
            }


            // otherwise check if this is older than the oldest known bid so far
            if times.bid_times[j] < oldest_time {
                oldest_bid_index = total_index;
                oldest_time = times.bid_times[j];
            }
        }


        if found_space {
            break;
        }
    }


    ...

If we didn't find a slot then we are going to need to replace the bid at position oldest_bid_index. We therefore first have to check what bid was present at that position and subtract its value from bid_total which tracks the total quantity currently in the program's State, and also reduce n_bidders, which tracks the number of active bids in the State, by one.



    ...


    // if there was no open spot we overwrite the oldest bid
    if !found_space {


        bidders_index = oldest_bid_index;


        // if we are overwriting we need to subtract bid_amount and reduce n_bidders by one
        let existing_bid_idx = get_state_index(StateEnum::BidAmounts{index: bidders_index});
        let existing_bid = u64::try_from_slice(&program_data_account_info.data.borrow()[existing_bid_idx.0..existing_bid_idx.1])?;
        total_bid -= existing_bid;
        n_bidders -=1;
    }


    ...

With the new index found we can update the participants BidderData:



    ...


    // update their bid data
    let new_bidder_data = BidderData {index: bidders_index as u16};
    new_bidder_data.serialize(&mut &mut bidder_data_account_info.data.borrow_mut()[..])?;


    ...

and finally serialize the new bid, public key and the current time, before updating the total_bid and n_bidders data as well.



    ...


    msg!("update bid details for position {}", bidders_index);


    // insert the new bid, key and time into the program data
    let new_bid_idx = get_state_index(StateEnum::BidAmounts{index: bidders_index});
    let new_key_idx = get_state_index(StateEnum::BidKeys{index: bidders_index});
    let new_time_idx = get_state_index(StateEnum::BidTimes{index: bidders_index});


    let bidder_token_pubkey = *bidder_token_account_info.key;


    // serialize the new data
    new_bid.serialize(&mut &mut program_data_account_info.data.borrow_mut()[new_bid_idx.0..new_bid_idx.1])?; 
    bidder_token_pubkey.serialize(&mut &mut program_data_account_info.data.borrow_mut()[new_key_idx.0..new_key_idx.1])?; 
    current_time.serialize(&mut &mut program_data_account_info.data.borrow_mut()[new_time_idx.0..new_time_idx.1])?;  


    // update total bid
    total_bid.serialize(&mut &mut program_data_account_info.data.borrow_mut()[total_bid_idx.0..total_bid_idx.1])?; 


    //  update n_bidders
    n_bidders += 1;
    n_bidders.serialize(&mut &mut program_data_account_info.data.borrow_mut()[n_bidders_idx.0..n_bidders_idx.1])?;

Choosing Winners


When selecting new winners the program needs to perform the following sequence of tasks:


As we discussed in the introduction to this post, we need to make sure that bids can't be included within a round of the auction if they are made within the same block that the winners are selected. This is to stop someone checking the value of the Pyth streams we are using, and determining what the random numbers we generate will be before placing their bid with full knowledge of whether their's will be selected or not. More generally, the longer the time between the last bid and the selection of winners, the more secure the random number seed will be, because the range of possible values that will be passed by the Pyth streams will increase.

We therefore need to be able to find the subset of bids that occurred more than some threshold time before we enter the select_winners function, which in this example we have set to two seconds. We therefore define the following function, get_bid_state, which takes as an argument max_time, which is the latest time for a bid that we will consider in order to include it in this round of the auction. At this stage all we are interested in doing is finding both the total amount bid prior to that time, and the number of valid bids, so we simply iterate through the data, checking that the time of the bid is prior to max_time and returning these quantities at the end:



    pub fn get_bid_state(max_time : i64, program_data_account_info : &AccountInfo) ->  Result<(u16, u64), ProgramError> {




        // calculate the total bid amount and number of bidders at this time
        let mut total_bid : u64 = 0;
        let mut n_bidders : u16 = 0;
        for idx in 0..N_BID_BLOCKS {
            let bid_idx = get_state_index(StateEnum::BidAmounts {index: idx*BID_BLOCK});
            let time_idx = get_state_index(StateEnum::BidTimes {index: idx*BID_BLOCK});


            let bids = BidValues::try_from_slice(&program_data_account_info.data.borrow()[bid_idx.0..bid_idx.0 + BID_BLOCK*8])?; 
            let times = BidTimes::try_from_slice(&program_data_account_info.data.borrow()[time_idx.0..time_idx.0 + BID_BLOCK*8])?; 


            for jdx in 0..BID_BLOCK {
                if times.bid_times[jdx] < max_time && bids.bid_amounts[jdx] > 0 {
                    total_bid += bids.bid_amounts[jdx];
                    n_bidders += 1;
                }


            }
        }


        Ok((n_bidders, total_bid))
        
    }

Now that we know the number of valid bids, we can check whether or not we are in a position to select new winners at all. The logic for this is contained in the following function, check_winners_state, which starts by just checking whether there are any valid bids at all:



    pub fn check_winners_state<'a>(
        n_bidders : u16, 
        program_data_account_info : &AccountInfo<'a>,
        program_token_account_info : &AccountInfo<'a>
    ) ->  Result<u8, ProgramError> {


        // if there are no bidders then we have no-one to choose
        if n_bidders == 0 {
            msg!("no bidders to be able to select winners");
            return Ok(0);
        }


    ...

If there are bids, we next check whether the program has enough tokens to be able to select any winners. Each participant is bidding on a block of one hundred tokens, so there need to be at least that many in the program's token account. Note that for our example, the tokens have no decimal places, so we simply need to query the amount field of the token account:



    ...


        // if there aren't enough tokens available then we can't choose winners
        let min_tokens: u64 = TOKENS_WON;
        let program_token_account = spl_token::state::Account::unpack_unchecked(&program_token_account_info.try_borrow_data()?)?;


        let token_balance = program_token_account.amount;
        if token_balance < min_tokens {
            msg!("insufficient tokens in program account to select new winners: {} < {}", token_balance, min_tokens);
            return Ok(0);
        }


    ...

Assuming we have tokens in the bank, we next work out how many winners we are able to select this round, up to a maximum of four. We allow multiple winners each round because it means we are less likely to run into a situation where a single large bidder dominates the draw. Each time a winner is selected their bid is removed from the pool, and we recalculate the cumulative distribution of the remaining bids. This will give participants with lower bids a higher probability of being selected, and hopefully keep them more engaged in the auction process.

We also want the pool of bids to have the opportunity to grow, and selecting too many winners each round will make this difficult, so in this example we have settled on selecting one winner per 64 bids, up to the maximum of four. The number of winners selected in each round also needs to be limited by the number of tokens in the bank, and the following code makes these various checks to arrive at the final value of n_winners for this round:



    ...


        let max_token_blocks = token_balance / TOKENS_WON;


        // set the number of winners to the max and check if we should decrease from there
        let mut n_winners = MAX_WINNERS as u8;


        // check if we have enough token blocks for this many
        if n_winners as u64 > max_token_blocks {
            n_winners = max_token_blocks as u8;
        }


        // finally check if we have enough bidders for this
        let max_winners_from_bidders = n_bidders / 64 + 1;
        if n_winners as u16 > max_winners_from_bidders {
            n_winners = max_winners_from_bidders as u8;
        }


    ...

The final check we make is how long it has been since the last winners were selected. As with the number of winners, we want to strike a balance between allowing the pool of bids to build up, while still having winners being selected on a relatively short timescale. We chose five minutes as a reasonable time that the average bidder would have to wait to be selected as a winner. This means if there is only a single bidder in the auction they will have to wait five minutes until they can call select_winners, but already by the time there are ten bidders, new winners can be selected every 30 seconds. We also remove this limitation entirely once the expected time is below a few seconds, so that if more than one hundred bidders are in the pool new winners can be drawn immediately one after the other:



    ...


        let prev_time_idx = get_state_index(StateEnum::PrevSelectionTime);
        let prev_time_selected = i64::try_from_slice(&program_data_account_info.data.borrow()[prev_time_idx.0..prev_time_idx.1])?;


        let clock = Clock::get()?;
        let current_time = clock.unix_timestamp;
        let time_passed = (current_time - prev_time_selected) as f64;


        // on average we expect a single bidder to wait 5 minutes before being selected
        // we therefore calculate time_per_bidder based on the number of bidders, and number of winners being selected
        // if this is below 10 seconds we just allow new winners to be selected so that there is less friction with large
        // numbers of bidders


        let time_per_bidder = (5.0 * 60.0) / ((n_bidders as f64) / (n_winners as f64));
        
        msg!("time_per_bidder {} time_passed: {} n_bidders {} token_balance {} max_blocks {}", time_per_bidder, time_passed, n_bidders, token_balance, max_token_blocks);


        if time_per_bidder > 3.0 && time_passed < time_per_bidder {
            return Ok(0);
        }


        msg!("Selecting {} new winners! ({} {})", n_winners, max_token_blocks, max_winners_from_bidders);


        Ok(n_winners)
    }

To generate the seed for our random number generator we use data feeds from the Pyth oracle, and follow the same procedure that we outlined in our previous post here. As in that post we then use the xorshift random number generator with that seed to obtain the n_winner values we need. As a final step we then sort the vector of random numbers in order to increase the efficiency with which we can then search through the bid data and actually find the winning keys:



    ...


    // generate the seed for selecting winners
    let mut pyth_random = randoms::generate_seed(
        btc_account_info,
        eth_account_info,
        sol_account_info
    );


    let mut ran_vec : Vec<f64> = Vec::new();
    for _winner in 0..n_winners {
        pyth_random = randoms::shift_seed(pyth_random);
        let random_f64 = randoms::generate_random(pyth_random);


        ran_vec.push(random_f64);
    }


    ran_vec.sort_by(|a, b| a.partial_cmp(b).unwrap());


    ...

We now reach the main loop in this function, which is going to actually select the winners. When we reach this point valid_total_bid has been initialized to the value returned by get_bid_state, and so represents the sum of the bids that occurred more than two seconds prior to the time we entered this function. As before when iterating through all the bids, they will be split up into N_BID_BLOCK chunks each of size BID_BLOCK.

Each random number generated earlier is in the interval [0..1]. By multiplying valid_total_bid by these numbers we get the point in the cumulative distribution at which a winner will be chosen, which we define as the threshold in the code snippet below. As we iterate through the bids we will be tracking the cumulative bid amount, and comparing this to the threshold. The bid that causes the cumulative total to exceed the threshold will then be chosen as the next winner. As these random values were sorted into numerical order we can just iterate through N_BID_BLOCK in the outer loop, and only deserialize each block once in order to increase the computational efficiency of selecting winners.



    ...


    // initialize the starting state
    let mut cumulative_total : u64 = 0;
    let mut winners_found : [bool; MAX_WINNERS] = [false; MAX_WINNERS];


    for idx in 0..N_BID_BLOCKS {


        let bid_idx = get_state_index(StateEnum::BidAmounts {index: idx*BID_BLOCK});
        let mut bids = BidValues::try_from_slice(&program_data_account_info.data.borrow()[bid_idx.0..bid_idx.0 + BID_BLOCK*8])?; 


        let time_idx = get_state_index(StateEnum::BidTimes {index: idx*BID_BLOCK});
        let times = BidTimes::try_from_slice(&program_data_account_info.data.borrow()[time_idx.0..time_idx.0 + BID_BLOCK*8])?; 


        for current_winner in 0..n_winners {


            if winners_found[current_winner as usize] {
                continue;
            }


            // update the threshold
            let random_f64 = ran_vec[current_winner as usize];
            let threshold = ((valid_total_bid as f64) * random_f64) as u64;


    ...

Although previously we calculated the total bid amount and number of bidders that we will accept in this round of the auction, we didn't explicitly save the valid indices. As we loop through the bids we therefore check if the time of the bid was before the required threshold, and ignore it if it was not. If it was made long enough ago it contributes to the running bid total, which we compare against the threshold. If this bid exceeds the threshold then we have found our next winner:



    ...
            let mut sub_total : u64 = cumulative_total;
            for bid_index in 0..BID_BLOCK {


                // check if this is within the time threshold
                if times.bid_times[bid_index] >= threshold_time {
                    continue;
                }
                
                let current_bid =  bids.bid_amounts[bid_index];
                sub_total += current_bid;


                if sub_total > threshold {


                    winners_found[current_winner as usize] = true;


    ...

Now that we have found a winner we need to serialize their key into the winners array of the program's State, and then clear their entries in the bid_amounts, bid_times, and bid_keys arrays:



    ...


                    let winner_index = idx * BID_BLOCK + bid_index;


                    // get the winners key from the program data account
                    let key_idx = get_state_index(StateEnum::BidKeys{index: winner_index});
                    let winners_key = Pubkey::try_from_slice(&program_data_account_info.data.borrow()[key_idx.0..key_idx.1])?; 


                    // and insert it into the winners array
                    let winner_idx = get_state_index(StateEnum::Winners{index: current_winner as usize});
                    winners_key.serialize(&mut &mut program_data_account_info.data.borrow_mut()[winner_idx.0..winner_idx.1])?; 


                    // now clear the winners data in the program data account
                    // start by zero'ing their bid
                    let win_bid_idx = get_state_index(StateEnum::BidAmounts {index: winner_index});
                    0u64.serialize(&mut &mut program_data_account_info.data.borrow_mut()[win_bid_idx.0..win_bid_idx.1])?;  


                    // then the bid time
                    let win_time_idx = get_state_index(StateEnum::BidTimes{index: winner_index});
                    0i64.serialize(&mut &mut program_data_account_info.data.borrow_mut()[win_time_idx.0..win_time_idx.1])?;  


                    // and then clear their key
                    solana_program::system_program::id().serialize(&mut &mut program_data_account_info.data.borrow_mut()[key_idx.0..key_idx.1])?;


    ...

We then decrement the current known valid bid total, so that when we re-enter the loop for the next winner and recalculate the threshold with the next random value it will be for the new smaller amount. We also need to reduce the actual total bid amount as we will update that at the very end of the function, and zero out the bid in this blocks bid_amounts array, so that it won't get included as we continue to loop through for the next winner. If we finish the loop through the current block without having found a winner we update the cumulative total bid with the sum from this block, and move on to the next.



    ...


                    // finally decrement the number of bidders, and the total bid amount
                    valid_n_bidders -= 1;
                    valid_total_bid -= current_bid;


                    n_bidders -= 1;
                    total_bid -= current_bid;


                    bids.bid_amounts[bid_index] = 0;


                    break;


                }
            }


            // if this winner wasn't found in this block, move onto the next block
            if winners_found[current_winner as usize] == false {


                cumulative_total = sub_total;


                break;
            }
        }
    }


    ...

Finally at the end of the function the last thing we need to do is to serialize the updated values of total_bid and n_bidders, and to set the last time winners were selected to the current time:



    ...
            
    // update number of bidders
    let n_bidders_idx = get_state_index(StateEnum::NBidders);
    n_bidders.serialize(&mut &mut program_data_account_info.data.borrow_mut()[n_bidders_idx.0..n_bidders_idx.1])?;


    // update total_bid_amount
    let total_bid_idx = get_state_index(StateEnum::TotalBidAmount);
    total_bid.serialize(&mut &mut program_data_account_info.data.borrow_mut()[total_bid_idx.0..total_bid_idx.1])?;


    let prev_time_idx = get_state_index(StateEnum::PrevSelectionTime);
    current_time.serialize(&mut &mut program_data_account_info.data.borrow_mut()[prev_time_idx.0..prev_time_idx.1])?;

Sending Tokens


This is by far the simplest of the four main functions that are used in the token auction. As usual we start off by checking the main accounts that are passed, however in this case we also have to pass the function the associated token addresses of the winners, so this process is slightly more involved than normal, so we will just quickly go through that aspect below.

In order to know how many winners we have we deserialize the n_winners value from the program data account. We do this rather than passing the value as an argument to the program to ensure that users can't pass erroneous values. As this function can be called at any time, at this stage we also simply check that this value is greater than zero. If there are no winners we can exit immediately.



    // now check how many winners we expect and make sure the keys match the program data
    let n_winners_idx = get_state_index(StateEnum::NWinners);
    let n_winners = u8::try_from_slice(&program_data_account_info.data.borrow()[n_winners_idx.0..n_winners_idx.1])?;


    if n_winners == 0 {
        msg!("No winners selected, exiting send_tokens");
        return Ok(());
    }


    msg!("have {} winners to send tokens to", n_winners);

Given the expected number of winners, we now create a vector of references to AccountInfo objects, and push the winners onto that from the account iterator. We make use of the peekable functionality of iterators in order to check whether the correct number of accounts have been passed to the function:



    ...


    // get the winner's account info
    let mut winners_account_info : Vec<&AccountInfo> = Vec::new();
    for _w_idx in 0..n_winners {


        if account_info_iter.peek().is_some() {
            winners_account_info.push(next_account_info(account_info_iter)?);
        }
        else {
            msg!("n_winners {} exceeds the number of accounts passed", n_winners);
            return Ok(());
        }
    }


    // check that was the last account
    if account_info_iter.peek().is_some() {
        msg!("n_winners {} is less than the number of accounts passed", n_winners);
        return Ok(());
    }


    ...

We now need to make several different checks. Firstly we deserialize the public keys of the winning token accounts from the program's data account, and check that all the keys passed to the program match those that are stored in the data account. Secondly, we check none of the keys match the system program key, which is the value we store in our data structures to represent an empty slot.



    ...


    let winners_key_idx = get_state_index(StateEnum::Winners { index: 0 });
    let expected_winners = WinnersKeys::try_from_slice(&program_data_account_info.data.borrow()[winners_key_idx.0..winners_key_idx.0 + 32 * MAX_WINNERS])?;


    // check the winners sent are what we expect
    for w_idx in 0..(n_winners as usize) {
        msg!("winner {} : {}", w_idx, expected_winners.keys[w_idx].to_string());


        if expected_winners.keys[w_idx as usize] != *winners_account_info[w_idx].key {
            msg!("expected winner {} to have key {}", w_idx, winners_account_info[w_idx].key);
            return Err(ProgramError::InvalidAccountData);
        }


        // also check none of the winners are the system program which would indicate we have arrived here too early
        if *winners_account_info[w_idx].key == solana_program::system_program::id() {
            msg!("winner {} has system program key {}", w_idx, winners_account_info[w_idx].key);
            return Err(ProgramError::InvalidAccountData);
        }
    }
    ...

Finally we then iterate over the remaining keys in the data account up to the maximum number of winners to make sure that these are equal to the system program key. If they are not then somehow the n_winners variable must not have been set to the right value. Although this shouldn't ever happen, we check anyway:



    ...


    // finally check that the remaining entries in the winners data vec are the system program id
    for w_idx in (n_winners as usize)..MAX_WINNERS {
        msg!("winner {} : {}", w_idx, expected_winners.keys[w_idx as usize].to_string());


        if expected_winners.keys[w_idx] != solana_program::system_program::id() {
            msg!("expected winner {} to have key {}", w_idx, solana_program::system_program::id());
            return Err(ProgramError::InvalidAccountData);
        }
    }
    ...

With the winning token accounts in hand we can then make use of our transfer_tokens function to send the winning amount to each of the accounts in turn. Here that amount is defined as the constant TOKENS_WON, which in this example we have set to one hundred:



    // now we can transfer the tokens


    for w_idx in 0..(n_winners as usize) {


        utils::transfer_tokens(
            TOKENS_WON,
            program_token_account_info,
            winners_account_info[w_idx],
            program_derived_account_info,
            token_program_account_info,
            bump_seed
    
        )?;
    }

As a final step we then reset all the winning keys in the program's data account to the system program key, and set n_winners back to zero, so that the program can start selecting new winners again.



    // finally just reset the n_winners value to zero so we can select new winners again
    // and reset all the winners keys to their default
    for current_winner in 0..MAX_WINNERS {


        let winner_idx = get_state_index(StateEnum::Winners{index: current_winner});
        solana_program::system_program::id().serialize(&mut &mut program_data_account_info.data.borrow_mut()[winner_idx.0..winner_idx.1])?; 


    }


    0u8.serialize(&mut &mut program_data_account_info.data.borrow_mut()[n_winners_idx.0..n_winners_idx.1])?;

Live Example


Below we have a simple front end to the token auction program running on the Solana devnet blockchain, you can find the source code for it at our website's git repo here. At the top we show a summary of the donations that have been made, both as a total value and as a breakdown per charity. Below that you can see the current state of the auction, with the number of active bids, and the average bid price.

Whenever you make a bid it will automatically take care of sending out tokens to any winners that are currently waiting, and the program will also attempt to select new winners if the criteria for doing so are met. You can also see what your current chances are of being the next winner selected given the size of your bid, and the total amount bid by all users.

Finally, it will also show you how many bids by other users need to be made before your bid is removed as the oldest bid. You can opt to either increase your bid, which will refresh its lifetime, or select new winners which will free up space in the auction.

Overview

Total Donated
0.9899 SOL
Number Donations
1300

Account Info





We will be making use of this system in our own apps going forward, and hope that you might be motivated to try and launch your own charitable token auction in the future! If you are interested to see how we use it feel free to follow us on Twitter to keep up to date with future posts!