First-price sealed-bid auction

Auctions are core to trading (e.g. treasury auctions, order flow auctions) and can be thought of as the building block for how most centralized exchanges operate today. In this example, we consider a first-price sealed-bid auction over encrypted bids.

How will our algorithm work?

Our program finds the highest bid amount and who placed the highest bid in a sealed-bid auction. The algorithm takes the first bid in the list and marks it as the winning bid. Then, subsequent bids are compared to this winning bid in turn using a for loop. If a higher bid is found, it replaces the current winner. Finally the result is returned as the winning bid and its index in the original list.

Normal program (aka no privacy)

Here is the plaintext version of the program (providing no privacy) so that the auctioneer can view all of the the bids and the winning bid.

Let’s start by defining the output structure that will hold the winning bid and its index.

typedef struct Winner {
    uint16_t bid;
    uint16_t idx;
} Winner;

We then define the auction function, which loops through the bids in order and finds the highest one.

void auction(
    uint16_t *bids,
    uint16_t len,
    Winner *winningBid
) {
    // The first bid is the initial winner
    winningBid->bid = bids[0];
    winningBid->idx = 0;

    // Iterate through the remaining bids, replacing the winner if a higher bid
    // is found
    for (uint16_t i = 1; i < len; i++) {
        bool isWinner = bids[i] >= winningBid->bid;

        winningBid->bid = isWinner ? bids[i] : winningBid->bid;
        winningBid->idx = isWinner ? i : winningBid->idx;
    }
}

Private program walkthrough

To create a private auction, we update the function’s signature with [[clang::fhe_program]] and the inputs/outputs with [[clang::encrypted]]. And that’s it, we’re done! The program now hides all the bid values.

[[clang::fhe_program]]
void auction(
    [[clang::encrypted]] uint16_t *bids,
    uint16_t len,
    [[clang::encrypted]] Winner *winningBid
) {
    // The first bid is the initial winner
    winningBid->bid = bids[0];
    winningBid->idx = 0;

    // Iterate through the remaining bids, replacing the winner if a higher bid
    // is found
    for (uint16_t i = 1; i < len; i++) {
        bool isWinner = bids[i] >= winningBid->bid;

        winningBid->bid = isWinner ? bids[i] : winningBid->bid;
        winningBid->idx = isWinner ? i : winningBid->idx;
    }
}

Running the program

If you’d like to run the program, feel free to look at the corresponding code here.

Performance

Running the program with 8 bids takes 0.630 seconds on an AWS c7a.16xlarge machine (64 cores) and 2.29 seconds on an 14 inch M2 Macbook Pro with 10 cores (6 performance, 4 efficiency).

What’s missing?

In a real-world deployment, we would likely want to use threshold FHE to implement an auction. Doing so ensures that only the winning bid is known and losing bids remaing private/hidden.