Marginal Price Sealed Bid Auction Module - External Submission and External Evaluation

Oighty commented 8 months ago

Objective

Implement an Auction Module for Marginal Price Sealed Bid auctions.

Marginal Price Auction Methodology

A marginal price multiunit auction allocates capacity to the highest bidders until it is expended. However, each bidder only pays the price of the last "marginal" bidder (meaning the lowest price submitted that receives an allocation). Because of this, you can't just total up the capacity expended by the price each person bid. Therefore, we determine the winning bids in two steps:

Calculate the marginal price of the auction

// calculate the marginal price of the auction based on the inputs
// assume inputs are sorted by price and there are N bids
var amountIn = 0;
var winningIndex = N;
for (var i = 0; i < N; i++) {
    var bidPrice = bidAmountsIn[i] / bidAmountsOut[i]; // watch decimals for precision loss
    var expended = (amountIn + bidAmountsIn[i]) * bidPrice;
    if (expended >= capacity) {
        // this is the marginal bid
        marginalPrice = bidPrice;
        winningIndex = i;
        break;
    } else {
        amountIn += bidAmountsIn[i];
        // TODO handle case where this is the last bid and we haven't reached capacity
    }
}

Calculate the winning bids from the marginal price

var expended = 0;
for (var i = 0; i < winningIndex; i++) {
    winningBidAmountsIn[i] = bidAmountsIn[i];
    winningBidAmountsOut[i] = bidAmountsIn[i] / marginalPrice;
}
winningBidAmountsOut[winningIndex] = capacity - expended;
winningBidAmountsIn[winningIndex] = winningBidAmountsOut[winningIndex] * marginalPrice;

Sealed Bids

In order to keep bid data sealed and improve the user experience, users will submit encrypted bids which will be stored in an off-chain, decentralized database. Therefore, there will be no user transactions for bid submission. In order to allow for the off-chain orders to be encrypted in a way that will eventually be readable, the frontend will create and provide a public key for sellers to submit along with their auction creation transaction that users will use for encrypting their bids.

Auction Creation

Sellers will create auctions on this module by submitted a transaction to the AuctionHouse.auction with the Keycode for this type specified. Aside from the standard Routing and Auction Parameters, the following variables need to be provided:

Public key for bid submission
Minimum price for the auction (probably encrypted with the public key above)
Minimum amount of tokens to sell? (i.e. minimum capacity filled)

User Bids

See above. These will be submitted off-chain.

In order to avoid gas issues with settlement, we will need to enforce a minimum bid size and minimum price on the bids that are collected and then provided for settlement. This can be validated on the front-end prior to the bid being encrypted. We need to ensure that bids can't be submitted to the database in another way that would circumvent these checks. Additionally, we can check when the settlement algorithm is run on the bids stored in the database and throw out ones that do not meet the required criteria.

Auction Settlement

Settlement of the sealed bid auction is the trickiest part of the implementation. The ideal situation is that the settlement of auctions is decentralized so that any one can get the off-chain bid data and submit it to the AuctionHouse for settlement after the auction ends and receive a fee for doing so. The main challenge with this approach is that you need to ensure that the bid data submitted is a true representation of the bids received off-chain. There are two versions of this:

The settler must submit only the winning bids and some artifact that validates it is indeed the correct data. In this case, the contract is trusting the external system both included all the bids that were submitted AND implemented the settlement algorithm correctly.
The settler must submit all the bids for the auction and some artifact that validates that it is indeed the correct data. In this case, the contract is trusting the external system to include all the bids that were submitted (perhaps above the minimum price) and handles the settlement of the auction itself. This is more gas intensive, but also more transparent.

In either case, you need to validate some data using an off-chain artifact. This could take the form of a signature from a wallet stored on the auction that represents a trusted, "system" wallet. The storage and permission of only allowing the decentralized front-end to access this may not be possible. It may require a private service that simply provides a signature that any data submitted matches the decentralized database for a particular auction. Zero knowledge proofs may be usable to validate that the settlement algorithm has been applied correctly offline, but I do not currently see a way to validate that the data provided matches that of the off-chain database for a particular auction (outside of a signature like the first option). This is the biggest roadblock currently.

We can solve this "bid provenance" problem by storing the encrypted bids on-chain, but there are tradeoffs with UX and gas costs on settlement (though they are lower than originally thought if you provide the decrypts as well as the key). The biggest problem with the on-chain approach is that the number of bids could cause an out of gas problem.

Auction Cancellation

The seller should be able to cancel an auction after it is created, but there should be a point (perhaps one day from ending) after which they shouldn't be able to cancel the auction. The main reason to cancel an auction should be due to a configuration issue, not because you changed your mind on whether you want to go forward with the auction. It may even make sense to let it be cancellable for only a certain window after it starts (instead of from the end).

A key concern for bidders is if an auction is cancelled after they submit a bid. If the auction is then restarted, their bid may be leaked prior to the end of the auction. Therefore, it would be ideal to have the encryption key not shared for an auction if it is cancelled. Using Lit Protocol, this may entail having the key not be revealed if the auction is cancelled (perhaps it checks a time to reveal, but also whether a certain variable is true/false).

0xJem commented 8 months ago

This description relates more to off-chain bid storage and on-chain settlement, which would be in-scope for a later version. I feel we should create a spec for local storage, off-chain settlement MPSBA.

Oighty commented 6 months ago

Closing since this version will not be implemented at this time. Due to the gas costs of submitting an array of bids on-chain to settle, there are some technical hurdles to overcome with off-chain auctions.

Axis-Fi / axis-core