feat(protocol): Auction

[cyberhorsey]

Describe the feature request

We want to try an implementation of an auction mechanism, ideally as an L3 running parallell with our L2 running the current tokenomics, to compare and contrast. This thread can serve as a discussion among core members to figure out the best way to make a simple, early, non-gas optimzied proof of concept.

Describe alternatives you've considered

Description of the alternatives you've considered here.

Additional context

Additional context here.

[cyberhorsey]

The main thing I like about this strategy vs other tokenomics is:

• Less math, less things can "go wrong" or be obtuse to understand.
• Proofs are only generated by people who will actually be able to submit them, not wasting resources, or other peoples time/hardware.
• Slightly more fair distribution depending on implementation, largely I think a core small group would still prove most of the blocks though, as you could bid through multiple addresses.
• Less manualy tweaking of parameters (proofTimeTarget, proofTimeIssued, etc) that cause the fee to either go exponentially to infinite, or approach 0.

[cyberhorsey]

This is a very simple, one day WIP:
taikoxyz/taiko-client#241

#13811

It ignores more complicated concepts like "bidding for batches" (which is obviously more gas efficient), and simply says:
after a block is proposed, you bid, and then an auction ends, and whoever says they will accept the least amount of wei per gasUsed as the reward, wins.
and the proposal fee becomes some multiplier of the averageProofReward.

and then the client says
here is the bidding strategy I would like to use (Always bid, Profitable only [if you can estimate the cost of proofs only], Down to a minimum amount, etc etc), and then if you are the successful bidder, you start to generate the proof.

The protocol code also has the concept of a deposit, but hasnt implemented something like, if you are late on the proof, we slash your deposit and half goes to the burner / half goes to the new prover. It also has no concept of minimum decrease under previous bid to be valid, and the auction can be postponed indefinitely by submitting a "1" wei smaller bid, because there is no concept of "the auction is over N seconds after the first bid", its only most recent bid.

It is missing a lot, obviously, but it simply something to get the discussion/ball rolling.

[dantaik]

Implementing a simple, batch-based auction system for prover cost-efficiency

Background

Our current tokenomics framework rewards the fastest prover, encouraging prioritization of speed over cost-effectiveness. This conflicts with Taiko's commitment to delivering cost-efficient proofs. By incentivizing cost-effective proofs, we can significantly reduce Taiko's overall Layer 2 (L2) expenses, enhancing our competitive edge in the marketplace.

Proposed Solution

I suggest introducing an auction mechanism to recalibrate provers' incentives, guiding them towards prioritizing cost-effectiveness. This mechanism facilitates provers to bid for block rewards, creating a transparent fee market. Moreover, this model promotes resource conservation, permitting provers to commit to resource-intensive Zero-Knowledge Proof (ZKP) computations only once they have definitively secured a block reward.

Design Considerations

Batch-Based Strategy

Given the high gas fees associated with Ethereum, we endorse a batch-based strategy for running auctions. This approach bestows the winning bidder with proving rights for a batch of blocks, thereby reducing per-block gas costs. During the testnet phases, we anticipate starting with a smaller batch size, with plans to scale up to 256 blocks by the mainnet launch.

Considerations for Future Blocks and Gas Costs

To mitigate the potential for accumulated ZKP delays, I suggest conducting auctions for upcoming blocks even before they are proposed. This approach does introduce uncertainty for provers due to the unknown block gas used and data size at the auction's outset. To address this, I propose a pricing model for the auction based on the gas/data usage of the auctioned block, with the block reward calculated as x*y if the winning bid is x TKO token per gas and the actual gas used by the block is y. Here, x will be termed as the bid per gas, or simply bid.

Bidding Procedures and Deposit Requirements

I suggest setting the initial bidding price for new auctions at s=2*p, while maintaining a moving average bid for all verified blocks, represented as p. Each successive bid should be at least 5% lower than the current bid. Bidders would need to deposit s * max_block_gas_limit * num_blocks * 1.5 Taiko tokens for the batch. A penalty of s * max_block_gas_limit * 1.5 Taiko tokens will be imposed and then burnt for each block the winner fails to prove within the stipulated timeframe; if successful, the deposit will be refunded.

Auction Window, Proving Window, and Multiple Auction Management

The auction window starts with the first bid and ends after either 5 minutes or 25 Ethereum blocks( or if the bid falls to 50% smaller than p?). Blocks become eligible for proving only once the auction has officially ended. The auction winner must submit the first ZKP for the block within 60 minutes of the block proposal or the auction's end, whichever is later. Other provers can submit proofs to create additional fork choices after the initial ZKP submission or upon the proving window's expiration. Multiple concurrent auctions for different batches are allowed, but I suggest limiting the upcoming 100 batches for improved manageability.

Reward and Penalty Mechanisms

If the verified block's chosen fork choice originates from the auction winner's proof, the winner's deposit and reward TKO tokens are refunded. If the chosen fork choice comes from another prover's proof, the latter receives half the deposit, and the remaining half is burnt. This mechanism ensures fair competition and deters manipulation, such as winners submitting correct proofs via different addresses.

Absence of Fallback Mode

There is no fallback fee/reward model for blocks that are not auctioned. This simplifies the auction design and eliminates the need for dual tokenomics systems - an auction-based primary system and an alternative fallback one.

Block Fees

I propose to charge a fee in Taiko tokens from the block proposer calculated as p * gas_limit, where p is the moving average bid for all verified blocks. We could introduce another moving average q to cover the bid of all unverified blocks that have been auctioned. For instance, the fee could be calculated as (p * 0.5 + q * 0.5) * gas_limit.

Challenges

Insufficient Competition

The success of the proposed auction framework heavily relies on the participation of many independent entities. If provers collude or form alliances to increase their profits, they could strategically place a single bid at the initial/highest price s, leading to a constant rise in rewards. Such behavior contradicts the system's intended cost-efficient competition.

Nevertheless, this behavior may unintentionally incite competition. As the proving reward considerably increases, it is likely to catch the attention of other provers, thus encouraging their participation. This market self-regulation could restore balance and maintain the competitive integrity of the auction process.

Additional Verification Delay

Introducing an auction window inevitably adds an extra delay to the proving time. This delay might not be noticeable when the average proving time is relatively long (over 30 minutes). Still, it could become significant in future scenarios where proof generation takes just a few minutes.

However, as emphasized at the outset of the proposal, our goal is to optimize for cost, not speed. While this additional delay is an important consideration, it's unlikely to pose a major hurdle to our primary objective of cost-effectiveness.

[Brechtpd]

Some previous discussion on this: https://github.com/taikoxyz/internal/issues/121

Also let's take into account batch verification of proofs onchain when possible! Otherwise we'll have to modify things again when we can do this.

• Less math, less things can "go wrong" or be obtuse to understand.
• Less manualy tweaking of parameters (proofTimeTarget, proofTimeIssued, etc) that cause the fee to either go exponentially to infinite, or approach 0.

It seems underappreciated that the current proving system works exactly the same as the L2 proposing fee, which in turn is based on the data blobs EIP-1559 system (which in its turn is based on the current EIP-1559)! Same mechanism, same inputs, exactly the same math, exactly the same code (well in theory, unfortunately our current code base contains two pretty distinctive paths for doing the same thing). Even on the nodes side exactly the same logic needs to be followed when proposing blocks as is currently required for submitting proofs! This is why I like in the first place, same well known system, all code we already have basically reused as is, but in practice it seems like it's not really seen that way. :(

Slightly more fair distribution depending on implementation, largely I think a core small group would still prove most of the blocks though, as you could bid through multiple addresses.

Yeah that's also my fear about an auction system. Will it actually have a different outcome then the current prover system that allows us to reuse code, in exchange for a completely new system that may end up being the same (single prover winning everything).

Why would multiple addresses help though?

after a block is proposed, you bid, and then an auction ends, and whoever says they will accept the least amount of wei per gasUsed as the reward, wins.

• Will it take into account just the expected reward? Or also the expected proving delay? In the issue linked above I think it makes sense to take both into account.
• To minimize game theory things like the most efficient prover submitting a high bid, and then other provers having to bid lower, and then that same more efficient prover submitting a new lower bid only when somebody outbid him (and thus wasted gas and so won't bid anymore in the future, so price will remain higher) I think an auction that defines a curve where the prover fee/delay goes up in time is probably better. That way only the prover that wins the auction (bids the fastest, lowest prover fee/expected proof delay) spends gas (when using flashbots).

Our current tokenomics framework rewards the fastest prover, encouraging prioritization of speed over cost-effectiveness. This conflicts with Taiko's commitment to delivering cost-efficient proofs. By incentivizing cost-effective proofs, we can significantly reduce Taiko's overall Layer 2 (L2) expenses, enhancing our competitive edge in the marketplace.

Hmm it doesn't! It very much aims to find the most efficient prover for the target time.

To mitigate the potential for accumulated ZKP delays, I suggest conducting auctions for upcoming blocks even before they are proposed. This approach does introduce uncertainty for provers due to the unknown block gas used and data size at the auction's outset. To address this, I propose a pricing model for the auction based on the gas/data usage of the auctioned block, with the block reward calculated as x*y if the winning bid is x TKO token per gas and the actual gas used by the block is y. Here, x will be termed as the bid per gas, or simply bid.

Unfortunately gas is not a great proxy for proving cost. I think a couple of smallish risks here:

• Because of the likely significant varying proving costs (well probably! Unprovable blocks may make this much less so) it could be that provers will only want to bid on the worst expected case to not lose money, which in turn makes sure the proving fee is higher than needed.
• If the batch size is reasonably small the variance in blocks that need to be proven can be high, so the prover may again have to take into account the worst case scenario that makes sure he can prove all the blocks. This can increase the required prover fee as well.

I suggest setting the initial bidding price for new auctions at s=2*p, while maintaining a moving average bid for all verified blocks, represented as p. Each successive bid should be at least 5% lower than the current bid.

I think a curve going up in time has some nice properties (see above).

The auction window starts with the first bid and ends after either 5 minutes or 25 Ethereum blocks( or if the bid falls to 50% smaller than p?). Blocks become eligible for proving only once the auction has officially ended. The auction winner must submit the first ZKP for the block within 60 minutes of the block proposal or the auction's end, whichever is later.

So you propose to still have a built-in target time into the protocol, similar to the current proving system?

Multiple concurrent auctions for different batches are allowed, but I suggest limiting the upcoming 100 batches for improved manageability.

The auctions can be for block ids %n, and so also n the number of auctions that need to be run for a sequential range of blocks, that way we make the system more parallelizable because now the prover doesn't have to be able to prove all sequential blocks himself, the work can be shared between up to n provers.

I propose to charge a fee in Taiko tokens from the block proposer calculated as p * gas_limit, where p is the moving average bid for all verified blocks.

Using the gas cost to estimate the prover cost isn't great because, regardless of the gas used in the L2 block, the prover has to pay the same gas fees to get the proof on-chain. These on-chain fees will (hopefully) be the biggest part of the proof generation cost (batching proof verification on-chain will obviously help here!).

Introducing an auction window inevitably adds an extra delay to the proving time. This delay might not be noticeable when the average proving time is relatively long (over 30 minutes). Still, it could become significant in future scenarios where proof generation takes just a few minutes.

Auctions make the most sense when we're pessimistic about prover times in the future. The redacted fee proving system would work well in the optimistic and pessimistic case which is part of why I like it.

[cyberhorsey]

Brecht:

Also let's take into account batch verification of proofs onchain when possible! Otherwise we'll have to modify things again when we can do this.

I'm out of the loop on this, is there another issue/TLDR? One proof can be proofs for multiple blocks?

Why would multiple addresses help though?

In the event we put some code in that says same prover can not win N blocks/batches in a row.

The auctions can be for block ids %n, and so also n the number of auctions that need to be run for a sequential range of > >
blocks, that way we make the system more parallelizable because now the prover doesn't have to be able to prove all >sequential blocks himself, the work can be shared between up to n provers.

This is great, imo.

So you propose to still have a built-in target time into the protocol, similar to the current proving system?

I would think so, because we need to slash the prover's deposit if they take a week to submit a proof for a block. I was thinking some small constant grace window + state.avgProofTime though, rather than a specific built-in target time. This window ending also allows someone else to submit the proof, and receive the other % of the deposit that wasnt slashed.

I propose to charge a fee in Taiko tokens from the block proposer calculated as p * gas_limit, where p is the moving average > bid for all verified blocks.

Daniel:

I propose to charge a fee in Taiko tokens from the block proposer calculated as p * gas_limit, where p is the moving average > bid for all verified blocks. We could introduce another moving average q to cover the bid of all unverified blocks that have > > been auctioned. For instance, the fee could be calculated as (p * 0.5 + q * 0.5) * gas_limit.

What is the advantage to use the bid instead of the proof reward itself?

[Brechtpd]

I'm out of the loop on this, is there another issue/TLDR? One proof can be proofs for multiple blocks?

There currently is no loop to be in on. Yeah a proof of proofs so the proof verification cost on-chain can be lowered. I haven't really thought much about it to be honest, it also depends a bit on how blocks are assigned to provers, but only really two options that I currently see:

1. Proofs are still submitted per block, but those proofs are not immediately verified. The proof data is just made available on-chain, and that prover will get the reward for that block. Afterwards another prover (or of course maybe the same one) comes in and collects those proofs and verifies them all in a new proof that is verified on-chain. Only at this point are the blocks actually proven. This extra prover also needs to be paid somehow.
2. The block prover and the batch block prover are the same, we basically just allow multiple blocks to be proven at the same time in the smart contract, which internally supports batching to lower the verification cost. Easiest solution because no changes needed to the fees.

2 seems to be a good fit for an auction system. 1 seems to fit well when blocks aren't assigned to specific provers.

I would think so, because we need to slash the prover's deposit if they take a week to submit a proof for a block. I was thinking some small constant grace window + state.avgProofTime though, rather than a specific built-in target time. This window ending also allows someone else to submit the proof, and receive the other % of the deposit that wasnt slashed.

We have to be very careful with average proof times. If I understand correct that mean that the fastest prover can bring down the average time so much that only he would be able to submit proofs in a way that would not get slashed. After that happens, the most efficient provers cannot bid on the auction anymore because the given window would be impossible for them to achieve.

[cyberhorsey]

Agreed, this is the idea behind the configurable grace window, to make sure it's always somewhat realistic.

Thanks for the info on proof of proofs!