Auction for future chunk space

[ilblackdragon]

This is idea on building prioritization for multi-shard transactions.

TLDR: auction off chunk space in the future, allowing a single party that won auction to prioritize across multiple shards in the near future

Motivation

Transactions which are all touch multiple different shards don't have a very effective way to be prioritized across multiple different shards.

Proposal

There is a constant auction running for (T; T + K] blocks in the future, where T is current block number and K is auction window.
Third parties (off-chain) can bid on a set of {(blocknumber, shard_id, price)} tuple, where each individual (blocknumber, shard_id) tuple has individual auction.

On auction completion, it's known which account id has won which set of future chunks. This account's submitted (signer_id) receipts are getting prioritized in the given chunks.

Pros:

• Moves prioritization process off-chain to providers, which can intelligently analyze transaction traffic and contract layout to understand prioritization in which shards is needed. Multiple such providers means that there will be competition to keep prices fair.
• Creates additional value capture for NEAR tokens, as proceeds from auction will be burnt.
• Non prioritized transactions are just handled in the normal fashion. If the user wants to prioritize during congestion they either use a meta-tx relayer or can directly bid (via Wallet UI) on future space in the chunks where their receipts is going to get priority which will proiritize their receipts even if transaction is already in-flight.
• Excluding initial transaction inclusion proof, the rest of implementation seem straightforward, without needing any additional per-shard auctions, additional APIs for "adding gas".

Open Questions

• Parameters for window and for auction process: e.g. should auction finalize for each block T at T-1?
• Can there be censoring of auction transactions by chunk producers?
• Initial transaction inclusion of the winner of an auction, as the validator that produces given shard may not include tx from account that won auction.

[bowenwang1996]

@ilblackdragon a few questions on this:

• how global is the auction? Can an account only participate in the auction of the shard they reside in or can they try to participate in auctions of other shards as well? If they can, how do we aggregate the auction proposals across all shards? We can propagate through block headers but that may get unwieldy if many people bid at the same time
• How does accounting for auctioned chunk space work? Do we allow users to say they want to auction X Tgas per chunk? If so, there needs to be a mechanism to ensure that 1) we properly account for all auctions and do not exceed the chunk gas limit and 2) users have a way to understand how much gas their transaction will consume in each step of the execution
• Bidding through a third party provider (using meta transactions) has its problems. For example, we have not solved the issue of attaching deposit for meta transactions and currently relayers pay for attached deposit of a meta transaction. That means sending transfer transactions through meta transaction is very awkward, as users have to first send the amount they transfer to the relayer and trust that the relayer will send their transaction on their behalf

[bowenwang1996]

I worked out some more details on how auction for chunk space could work:

Prioritized Chunk Space
Only part of the chunk space is prioritized to leave room for "normal" traffic. The idea is that when there is congestion, people can pay more to get in, but for those who do not want to pay more, their transaction will eventually go through. This is similar to how express lanes on highways work. There should be a protocol level constant that specifies the percentage of chunk gas limit that is prioritized.

Auction Overview
To simplify things, only an account in a shard can bid for chunk space in that shard. Otherwise the auction has to specify shard id, which implies that auction participants need to be aware of sharding anways. Not allowing bidding for a different shard pushes the problem offchain and makes the implementation on the protocol level simpler. An alternative design is to make the auction global, i.e, the auction runs for all shards at the same time and therefore there is no need to specify shard id.

A bid for auction is in the following form

pub struct AuctionAction {
   price: Balance,
   block_height: BlockHeight,
   duration: u64,
}

It means that the signer wants to bid for the chunk space in [block_height, block_height + duration) and the price means the auction price per chunk space. An auction either wins an entire chunk or does not win anything, i.e, the priority space of a chunk is not further dividable. This allows us to push auctions on the transaction level offchain and simplify the protocol level implementation.

There is a protocol constant T which specifies the auction window, i.e, at every block h, chunk spaces in [h + 1, h + T] are auctionable. At the start of block h (or the end of block h-1), the auction winner for block h is computed based on the maximum bid. Note that even though the AuctionAction has a duration, there is no atomicity guarantee that the winner either wins all chunks in duration or wins nothing. T should be a small number (like 10) to ensure that computing the auction winner has minimal computational overhead.

Economics
When an auction is processed, the bidder needs to put down 50% of the total amount (price * duration) as a deposit. This is to prevent spamming of auctions. When an auction concludes at every block, deposit is returned to bidders who did not win. For the winner, the deposit is burnt. When the winner uses the priority space of a chunk, they must pay the remaining 50% of the auction fee. Otherwise the attempt to use the priority space will fail. The remaining 50% fee, when used, is added to the validator reward pool. This incentives validators to actually include transactions from auction winners. If we implement a naive solution where the fees are collected or burnt upfront (at the conclusion of an auction), then there is no incentive for a validator to include transactions from the winner and there is no way to punish the validator either.

Implementation
There are two main difficulties here: storing auction information and implementing the economics of auction

• Storing auction information. There is a question of whether to store the information in the state. The problem with storing it in the state is that there could be many bids and also we need to store it under some special key, which makes the state more complicated to deal with. On the other hand, not storing it in the state has two problems: 1) a node that is just synced through state sync needs to know the auction info and 2) not sure how it works with fraud proofs.
• Implementing the economics. For deposits, they could be sent to a special account auction and the deposit information is maintained as part of the state of that account. For collecting the auction fee during execution, since it is isolated on the chunk level, we just need to maintain a boolean during chunk execution to record whether the fee has been paid or not.

[walnut-the-cat]

To simplify things, only an account in a shard can bid for chunk space in that shard. Otherwise the auction has to specify shard id, which implies that auction participants need to be aware of sharding anways.

there is no atomicity guarantee that the winner either wins all chunks in duration or wins nothing.

When an auction concludes at every block, deposit is returned to bidders who did not win

I may not have a full understanding of Bowen's proposal, but there can be some sub-optimal user experiences.

• user needs to know what shards a txn will touch
• user needs to know what 'height' they should target
• user does not know the result of the auction right away (they have to wait and see what happens for a while). user needs to track the bidding status and retry potentially for every block until they make through.
• there is no holistic prioritization/guarantee on their txn request as prioritization will be limited to a signal shard,

[bowenwang1996]

@walnut-the-cat it is not users who will care about this. Entities participate in auctions should be service providers with sophisticated setup that allows them to track the chain very closely and they will then auction the space off to regular users. That experience can just be built into wallets.

[walnut-the-cat]

@walnut-the-cat it is not users who will care about this. Entities participate in auctions should be service providers with sophisticated setup that allows them to track the chain very closely and they will then auction the space off to regular users. That experience can just be built into wallets.

When you say service providers, do you refer to contract developers?
If so, doesn't this introduce additional workload for service providers to integrate with the feature? Is our assumption that they are willing to put additional effort to get their request prioritized? In my opinion, ideal situation is where someone willing to pay additional cost to prioritize their requests can simply do so with minimal change than series of rather complicated set up

[bowenwang1996]

When you say service providers, do you refer to contract developers?

No they are service providers who specialize in running auctions and they provide this as a service to developers and users. How exactly they do it is their own concern.

[walnut-the-cat]

I see. so this is somewhat of an add-on feature that can be leveraged by developers.

Then do we expect these service providers to naturally emerge once we start supporting this usecase? Or should we look for potential partners?

[bowenwang1996]

Then do we expect these service providers to naturally emerge once we start supporting this usecase? Or should we look for potential partners?

I think it will be a combination of both.

[ilblackdragon]

Closing this and replacing it with #532.

This is too complex and requires additional actors, complex mapping logic which shards are going to be touched in the future.