feat(protocol): allow the proposer to select a prover

[Brechtpd]

Describe the feature request

Currently the proposer and the prover are completely separated. In practice however it's extremely likely block builders already know provers. It's also possible to allow these two to communicate with each other (PBS style).

This allows the proposer to find the prover that is willing to prove the block at the lowest price using an offchain auction, and this can be done on a block per block basis and taking into account the expected gas costs at the time. It also allows the prover to only prove blocks for which it has the capacity to do so.

Conceptually the idea is the same as when a block would be proposed directly with its proof. But because that is currently not possible (proof generation takes too long), instead a bonded promise is attached from the prover.

Onchain things are very simply:

• When the block is proposed, a signature is provided from the prover that it will prove the block. This is done by the prover signing the hash of all the block data (so that the block data itself can remain hidden if necessary when auctioning the block to provers) and specifying the expected fee payment.
• The protocol checks this signature and checks if the prover is bonded.
• If all those checks pass than the proposed block is accepted.
• When the block gets proven, the prover gets his expected fee payment.

When the block isn't proven in time, the bond of the prover gets partially slashed and those funds are used to pay for all the blocks the prover failed to prove.

The prover can also offer the reward for the proof to some other prover. When a block gets proven by another prover and a signature is provided by the expected prover, that prover will get the reward instead. This allows the original prover to avoid getting slashed, and encourages provers to work together to get the proof submitted in time, which benefits the stability of the chain.

Blocks could still be proposed without a specified prover, that will use the open proving path instead.

Benefits:

• Very easy and gas efficient
• Automatically as efficient as possible: the proposer will select the prover willing to prove the block for the lowest price to maximize its own profit. Or not and use the open path.
• Permissionless because any prover can become a prover by just posting the required bond. Lower upfront capital requirements.
• Censorship resistant because the proposer can pick any prover willing to prove the block and can prove the block themself if necessary. Some provers may not want to prove a block and they can just avoid proving those specific blocks without ever being forced to prove any other blocks.

Combating centralization

The approach above is great for efficiency, but will also be centralizing, So we now try to ensure prover redundancy for liveness while sacrificing efficiency as little as possible.

The methods below can be combined with one another.

Method A. Random (per block) burn per prover

Each block will have some randomness (the block number for example) that will add a random additional cost to each prover that will change for each block. The max burn amount would be specified by some protocol constant MAX_BURN, and per block some random burn amount is chosen per prover in the prover_burn := [0, MAX_BURN] range. For each block, the burn amount for some prover should be zero.

The proposer now simply has to pick the prover that minimizes prover_fee + prover_burn for each block.

For the staking based system, the MAX_BURN could be a function of the amount staked (but needs to have a lower bound that is not 0).

Method B. Sub-groups

Each block will have some randomness (the block number for example) which will select a random sub-group in the provers. The goal is to have random sub-groups that still have to compete against each other on price to make sure the proving cost is still low, while preventing a single most efficient prover to prove all the blocks. For example if there are 4 provers A, B, C, and D, the following sub-groups of 2 provers could be selected:

• A, B
• A, C
• A, D
• B, C
• B, D
• C, D

For a specific block, the proposer can only use one of the provers in the selected sub-group, using any other prover will be rejected. However, this would be artificially limiting the pool of selected provers. So this needs to be combined with Method A, just now applied on the sub-group level instead of a per prover level.

We could also make sure that each subgroup contains as least one prover selected by PoG (see below) to make sure that that prover can always be contacted to sign a request and provide a minimum level service to proposers.

Method C. PoG (or dPoS)

Provers could be whitelisted using some sort of governance mechanism (the easiest being some sort of token voting, which would basically be delegated PoS) instead of based of just the amount bonded/staked. These whitelisted provers can add themselves to a smart contract and post a bond, which will allow them to sign blocks to prove. Giving a prover more weight to have them have a bigger chance to prove a block can simply be done by allowing the prover to be in the prover list multiple times.

Benefits:

• The bond can be some fixed amount that is deemed enough to ensure missed proofs can be proven by other provers, maybe in the range of ~1,000 to ~10,000 expected block proof costs, which should be a fairly small amount of money. This lowers the entry cost for provers and should thus also lower the prover fee for users.
• Slashing cost can now be reduced to basically just the extra cost to have some other prover interested in proving the missed blocks. If the prover misses too many blocks for no good reasons, the prover will be removed using governance.
• Can actually ensure there are actually different provers and not just a single prover using multiple addresses

Downside:

• Only whitelisted provers can prove blocks, so more difficult for provers to join.

We could also see these whitelisted provers as provers that simply are preferred because they can guarantee a guaranteed minimal level of service, and they get their weight boosted next to the permissionless system.

Open proving system

We may still want to allow proposers to submit proofs without selecting a prover manually.

Because we want to keep things as simple, the proving system when the offchain method isn't used should be disincentivized (because would give the opportunity to prove a block away to another prover) and be as simple as possible. An OPEN_FEE is charged to the proposer and that fee needs to be sufficient to prove the block at all times. This will be completely open and whoever proofs the block first could get the reward. 50% of the OPEN_FEE is burned to prevent abuse. Any of the bonded provers would be able to submit a proof to get the reward in the normal proof window, and to encourage them to do so multiple provers could get a reward for a block like this.

Describe alternatives you've considered

Description of the alternatives you've considered here.

Additional context

Additional context here.

[adaki2004]

I like it generally and have 2 questions.

• You mentioned block per block basis, is there an existing solution for low latency communication (not-centralized or among whitelisted-only participants) so that a block proposer has time to query and validate all the offers he/she has per every block ?
• We likely still need something like a simplified prover staking pool for wannabe provers, so that we can secure the slashing (but obv. assigning blocks would not depend on the staked amount) ?

[Brechtpd]

• You mentioned block per block basis, is there an existing solution for low latency communication (not-centralized or among whitelisted-only participants) so that a block proposer has time to query and validate all the offers he/she has per every block ?

I think this is pretty standard peer discovery which is done in nodes and things like bittorent, but I don't really know much about it. Provers will make it so that their information is as widely available as possible, so proposers shouldn't have much trouble finding out how to connect with them. When using PoG, this will be whitelisted so will definitely not be a problem

• We likely still need something like a simplified prover staking pool for wannabe provers, so that we can secure the slashing (but obv. assigning blocks would not depend on the staked amount) ?

Depends a bit on how often we still think the open mode will be used. If we think normally it won't be used, than simplifying as much as possible makes sense (which could mean a separate path that is as simple as possible or reuse the normal system as much as possible somehow).

The staking amount could still be important for the sub-group selection (bigger chance to be selected to the sub-group), though PoG may be a better way to assign weights. (I added some new sections to the original post that builds the system out with some more details).

[dantaik]

I like the idea that each proposer can choose a prover for each of his blocks, as long as the per-block bond is good enough for the core protocol. Our current Prover Pool can serve a s special Prover impl that can also be chosen by proposers. There can also be other implementations of Prover contracts that proposers can choose, as long as the Prover contract must guarantee a bond per block. I think this will be a nice abstraction on top of the current implementation.

We can define a virtual prover as:

interface Prover {
    function onSelected(address proposer, uint blockId, uint bond) external returns (address proofSubmitter);
    function onReleased(address proposer, uint blockId, uint bond, uint reward) external;
}

When a Prover is selected, the core protocol first burn X token from it as a bond, then call the onSelected function to ensure it did not revert. Then when the block is finalized using a proof provided by the given prover, mint X + Y token as reward back to the Prover and call its onReleased function.

If the selected prover is an EOA, we check there is an authentication signature (do not call these two functions).

[hugo-blue]

Thank @Brechtpd for introducing this proposal. After a simple review, I find it to be quite meaningful. And, I have a few comments that I would like to share.

Firstly, I am concerned about the potential for proposers to submit redundant blocks for the purpose of winning provers' profits. While combining proposers and provers could have some benefits, the current design on the testnet separates these roles to mitigate this risk.

Secondly, eliminating redundant proposed blocks is a separate issue that we wish to address. I suggest a solution of exploring the possibility of combining Ethereum's POS with the current staking-based prover solution. The rough idea is to select a super-prover (a proposer and prover role) through a consensus mechanism, who would then propose block, generate proof (or delegate the prover role via a second layer) and submit it. This approach would avoid the need for extra POS incentives as we already have them in A4 and resolve the issue of redundant proposed blocks.

The implementation of POS and the PBS design of flashbot is not very simple. It would need some additional time to develop a more detailed proposal, but I would like to throw out a nugget for pearls of wisdom.

[Brechtpd]

There can also be other implementations of Prover contracts that proposers can choose

Depends a bit I think on the implementation, because if the proposer can choose freely without any additional cost for a specific implementation things may centralize again to a single solution. I think If there are multiple possible implementations, each of them need to mitigate centralization on their own as well. You could do the random burn solution on the prover system as well, but assuming there is only one that is actually used almost at all times, that seems to just increase overheads most of the time.

as long as the Prover contract must guarantee a bond per block. I think this will be a nice abstraction on top of the current implementation

If the bond is per block, won't it be either too expensive to prove a lot of blocks in parallel for provers, or the bond will be so low that slashing isn't really something to be afraid of? A single bond per prover seems to make more sense to me, higher slash risk per block, but shared between multiple blocks. I think this also makes sense because for the network stability it doesn't really matter that much if just 1 proof is missing or 1000 proofs are missing. A single missing proof stops the chain from being able to reach verification status.

[Brechtpd]

Firstly, I am concerned about the potential for proposers to submit redundant blocks for the purpose of winning provers' profits. While combining proposers and provers could have some benefits, the current design on the testnet separates these roles to mitigate this risk.

Could you explain a bit more? Not sure I understand the problem you're addressing. Proposers could propose redundant blocks, but they would have to pay the prover for all of those, so doesn't seem like something that can be exploited.

Secondly, eliminating redundant proposed blocks is a separate issue that we wish to address. I suggest a solution of exploring the possibility of combining Ethereum's POS with the current staking-based prover solution. The rough idea is to select a super-prover (a proposer and prover role) through a consensus mechanism, who would then propose block, generate proof (or delegate the prover role via a second layer) and submit it. This approach would avoid the need for extra POS incentives as we already have them in A4 and resolve the issue of redundant proposed blocks.

Could you describe what redundant proposed blocks are for you? In the proposed solution, the proposer + prover can be seen as a single entity, but because we're a based rollup they have to go through the Ethereum validator. So using the PBS model you can see the proposer + prover as the block builder, and the Ethereum validator as the proposer.

The prover centrist model is indeed also an interesting one, but not one that is compatible with based rollups, which is still our current goal.

The implementation of POS and the PBS design of flashbot is not very simple. It would need some additional time to develop a more detailed proposal, but I would like to throw out a nugget for pearls of wisdom.

A full PBS design for the prover market will be a bit of work though other parties should be interested in making that. It also depends a bit how that will play out. Provers will want to broadcast their address where proposer can request proofs as far and wide as possible. We can even allow provers to post their API URL on the pool smart contract so that all proposers can simply contact and get a quote of them directly on that URL.

[hugo-blue]

Firstly, I am concerned about the potential for proposers to submit redundant blocks for the purpose of winning provers' profits. While combining proposers and provers could have some benefits, the current design on the testnet separates these roles to mitigate this risk.

When a proposer and prover can earn a small profit from a single block, they have the motivation to produce more blocks for greater earnings. Since the proposer+prover is permissionless, they may generate numerous duplicated or similar blocks and still earn some profit. Therefore, it is likely that the proposer and prover will engage in this behavior.

Could you explain a bit more? Not sure I understand the problem you're addressing. Proposers could propose redundant blocks, but they would have to pay the prover for all of those, so doesn't seem like something that can be exploited.

Secondly, eliminating redundant proposed blocks is a separate issue that we wish to address. I suggest a solution of exploring the possibility of combining Ethereum's POS with the current staking-based prover solution. The rough idea is to select a super-prover (a proposer and prover role) through a consensus mechanism, who would then propose block, generate proof (or delegate the prover role via a second layer) and submit it. This approach would avoid the need for extra POS incentives as we already have them in A4 and resolve the issue of redundant proposed blocks.

Could you describe what redundant proposed blocks are for you? In the proposed solution, the proposer + prover can be seen as a single entity, but because we're a based rollup they have to go through the Ethereum validator. So using the PBS model you can see the proposer + prover as the block builder, and the Ethereum validator as the proposer.

The prover centrist model is indeed also an interesting one, but not one that is compatible with based rollups, which is still our current goal.

The implementation of POS and the PBS design of flashbot is not very simple. It would need some additional time to develop a more detailed proposal, but I would like to throw out a nugget for pearls of wisdom.

A full PBS design for the prover market will be a bit of work though other parties should be interested in making that. It also depends a bit how that will play out. Provers will want to broadcast their address where proposer can request proofs as far and wide as possible. We can even allow provers to post their API URL on the pool smart contract so that all proposers can simply contact and get a quote of them directly on that URL.

[dantaik]

In this PR, I'm trying to further separate the current prover pool from the core protocol. This detachment facilitates flexibility, allowing the core protocol to easily adapt to alternative or superior prover pool designs without alterations. We're handing the task of finding the best prover pool design to third parties, and our role is to create the glue that connects the core protocol to multiple prover pools. This glue is embodied by our tokenomics, not by any particular pool.

The concept stems from Brecht's feature request above, but this PR concentrates solely on the glue aspect and does not incorporate any advanced features. Specifically, it permits a block proposer to select a prover when proposing a block. If the prover's address is 0, the block is immediately open; otherwise, the selected prover must validate the block within a defined time window.

The functional details are as follows:

• If the assigned prover's address is non-zero and an EOA, the system verifies a signature to confirm the prover's agreement to validate the block at a capped fee-per-gas.
• If the prover is a contract (assumed to be an IProver contract), the method prover.onBlockAssigned is invoked. This method may include authorization and other logics. If it does not revert, the block can be proposed; otherwise, the proposal is rejected.

In all cases, the protocol enforce the burn of a bond of a minimal value, 32 x block_deposit, in the implementation.

To avert unnecessary gas consumption, there are no notification calls to the prover contract when a block is proven or verified. This design prevents a malicious prover contract from exploiting callbacks like onBlockProven or onBlockVerified to exhaust gas.

Instead, the prover contract's deployer or owner manages off-chain authentication of block proposers and updates the prover contract's state. All prover contracts must have owners, as they cannot automatically modify their contract state or the behavior of the onBlockAssigned function on-chain without core protocol knowledge.

This approach may initially appear undesirable, but it corresponds with the fact that a prover's ability is based on off-chain information.

In this PR, it is also delineated that, generally, the proposer burns a block_deposit to cover the proving fee (block fee) using the block's gasLimit. If the gasUsed is less, a portion is refunded, making the proposer's payment equal to what the prover receives. The exception occurs when a block is not initially open and is verified by a prover other than the assigned one outside the proof window. In this case, we mint avgFeePerGas * 1.5 * gasUsed to the actual prover, but the proposer pays his expected amount, i.e., feePerGas * gasUsed. The prover's bond is not returned and will cover the additional cost. This almost guarantees the total supply of Taiko token decreases over time.

Tests are not updated and not runnable. I'd like to get your initial feedback first.

[dantaik]

RE: Method A. Random (per block) burn per prover

This will force the owner of the same set of hardware to use as many addresses as they can afford, so for every block, this pool of provers always have an address that will burn a really small amount of tokens. But it is still the very same prover off chain.

[Brechtpd]

RE: Method A. Random (per block) burn per prover

This will force the owner of the same set of hardware to use as many addresses as they can afford, so for every block, this pool of provers always have an address that will burn a really small amount of tokens. But it is still the very same prover off chain.

Yep, that's why it also requires a sybil resistance detection mechanism. The designs above assumes staking, but proposes governance (PoG (or dPoS) as an alternative (or an additional mechanism on top of staking).

[joohhnnn]

In this PR, I'm trying to further separate the current prover pool from the core protocol. This detachment facilitates flexibility, allowing the core protocol to easily adapt to alternative or superior prover pool designs without alterations. We're handing the task of finding the best prover pool design to third parties, and our role is to create the glue that connects the core protocol to multiple prover pools. This glue is embodied by our tokenomics, not by any particular pool.

The concept stems from Brecht's feature request above, but this PR concentrates solely on the glue aspect and does not incorporate any advanced features. Specifically, it permits a block proposer to select a prover when proposing a block. If the prover's address is 0, the block is immediately open; otherwise, the selected prover must validate the block within a defined time window.

The functional details are as follows:

• If the assigned prover's address is non-zero and an EOA, the system verifies a signature to confirm the prover's agreement to validate the block at a capped fee-per-gas.
• If the prover is a contract (assumed to be an IProver contract), the method prover.onBlockAssigned is invoked. This method may include authorization and other logics. If it does not revert, the block can be proposed; otherwise, the proposal is rejected.

In all cases, the protocol enforce the burn of a bond of a minimal value, 32 x block_deposit, in the implementation.

To avert unnecessary gas consumption, there are no notification calls to the prover contract when a block is proven or verified. This design prevents a malicious prover contract from exploiting callbacks like onBlockProven or onBlockVerified to exhaust gas.

Instead, the prover contract's deployer or owner manages off-chain authentication of block proposers and updates the prover contract's state. All prover contracts must have owners, as they cannot automatically modify their contract state or the behavior of the onBlockAssigned function on-chain without core protocol knowledge.

This approach may initially appear undesirable, but it corresponds with the fact that a prover's ability is based on off-chain information.

In this PR, it is also delineated that, generally, the proposer burns a block_deposit to cover the proving fee (block fee) using the block's gasLimit. If the gasUsed is less, a portion is refunded, making the proposer's payment equal to what the prover receives. The exception occurs when a block is not initially open and is verified by a prover other than the assigned one outside the proof window. In this case, we mint avgFeePerGas * 1.5 * gasUsed to the actual prover, but the proposer pays his expected amount, i.e., feePerGas * gasUsed. The prover's bond is not returned and will cover the additional cost. This almost guarantees the total supply of Taiko token decreases over time.

Tests are not updated and not runnable. I'd like to get your initial feedback first.

I've got some concerns about a few things:

1. It seems that right now, provers only get incentivized by the native tokens from the proposer. How do we ensure a direct value relationship between the prover's collateral and the proposer's native tokens? Is there a risk of malicious attacks between provers? For instance, if a timeout occurs, one-fourth of the collateral can be taken by other provers. This could lead to attacks if the value of that collateral is greater than the proposer's native tokens.

2. It looks like the proposer's token rewards are received right when they propose. If the reward is worth more than what is sent to the prover, could the proposer spam a bunch of blocks just to profit?

3. Proofs take time, but the prover's native token reward is fixed when the proposer proposes a block. What if the base gas price spikes during that time, making the gas fee greater than the reward? Would provers hold off on submitting proof transactions? This could slow down the network's block production speed, even without considering the 90-minute collateral penalty.

4. For the situation with other provers who aren't chosen by the proposer, I didn't see a clear handling of this in the code. From what understand, if you've submitted a proof within 90 minutes, the collateral tokens are returned to the prover selected by the proposer. However, provers who were not selected but have still provided a proof don't seem to receive any rewards.

If I have any incorrect views, feel free to point them out. Appreciate the perspectives from you all.

[dantaik]

John, thank you for your questions. Let me to answer the question based on the latest protocol code (alpha-5), which is quite different from alpha-3 and alpha-4.

1. It seems that right now, provers only get incentivized by the native tokens from the proposer. How do we ensure a direct value relationship between the prover's collateral and the proposer's native tokens? Is there a risk of malicious attacks between provers? For instance, if a timeout occurs, one-fourth of the collateral can be taken by other provers. This could lead to attacks if the value of that collateral is greater than the proposer's native tokens.

Provers are actually paid with ETH directly by the block proposers. But it is also possible for the proposer to pay any ERC20 token to the prover if the prover is a IProver contract (using transferFrom(proposer, address(this), amount) inside the contract). A block can only be proven by the assigned prover within a proof window, other provers will have to wait for 1) the first proof from the assigned prover to be submitted or 2) the the proof window ends.

2. It looks like the proposer's token rewards are received right when they propose. If the reward is worth more than what is sent to the prover, could the proposer spam a bunch of blocks just to profit?

This is to guarantee the liveness of the blockchain, making sure there will be at least one block after a certain seconds even if there are not many transaction on L2.

3. Proofs take time, but the prover's native token reward is fixed when the proposer proposes a block. What if the base gas price spikes during that time, making the gas fee greater than the reward? Would provers hold off on submitting proof transactions? This could slow down the network's block production speed, even without considering the 90-minute collateral penalty.

Provers no longer receive native token reward, going forward, proving fees are negotiated off-chain per block (not per gas used) and paid by block proposers.

4. For the situation with other provers who aren't chosen by the proposer, I didn't see a clear handling of this in the code. From what understand, if you've submitted a proof within 90 minutes, the collateral tokens are returned to the prover selected by the proposer. However, provers who were not selected but have still provided a proof don't seem to receive any rewards.

The idea is not to ask more than one prover (the assigned one) to start proving the same block at all to avoid unnecessary waste of resources. Taiko tries to lower user transaction fees which requires us to lower the cost per block proving. ZK-proving a block is not a PoW game.

[joohhnnn]

Hey @dantaik . Thank you for the insightful explanation. The 'negotiated off-chain' mechanism indirectly answers many questions.

The idea is not to ask more than one prover (the assigned one) to start proving the same block at all to avoid unnecessary waste of resources. Taiko tries to lower user transaction fees which requires us to lower the cost per block proving. ZK-proving a block is not a PoW game.

Regarding the fourth question, could the fixed 90-minute period be adjusted? For example, if the average time for generating a proof is x minutes, could we reduce the 90-minute window to x and implement a gradient reduction in collateral after x minutes? This could ensure that provers can't submit proofs anytime within 90 minutes without any constraints and also make block-proving times more consistent.

[hugo-blue]

After reviewing the codes, I have a couple of comments to make:

1. If multiple proposers propose blocks in the same L1 block, only the first proposer can get ttko. This may lead to a gas war in sepolia, as the transaction with more gas fee will become the first one and get the ttko, when sepolia ETH is cheap.
2. What if we transfer the ETH to the prover after the block is verified? It can encourage the prover to submit the proof honestly.

[adaki2004]

After reviewing the codes, I have a couple of comments to make:

2. What if we transfer the ETH to the prover after the block is verified? It can encourage the prover to submit the proof honestly.

Although it is technically possible, would increase a bit on complexity but other than that also the bond has to be much bigger than a proving fee. So dishonest provers would risk much more than they gain.

[hugo-blue]

In my opinion, it would be beneficial to reduce or eliminate the bond or penalty for zkp provers. As explained in my article found at part 5 of https://mirror.xyz/aoraki-labs.eth/5RoLVYZo5T2Lj4xLO5AB0uzVEaKKegGLlbUcdGQQTCg, zkp provers face a greater risk compared to ETH validators. Despite receiving fewer rewards, they must still pay for high computation cost, gas and assume penalty risks. In cases where network issues arise, the prover may fail to submit the proof and suffer significant losses. This creates added pressure for those running the zkp prover.

[Cryptoastt]

Is it still in the loop?

[dantaik]

In the latest protocol code, for each block, a prover is required to put 2 bonds: a liveness bond and a validity bond. The liveness bond is to guarantee the prover is online to provide the proof in time, the validity bond is to make sure the proof shall be a valid one.

The liveness bond should be small and the liveness bond shall be much larger. When a prove is offline, he only lose his liveness bond. The proving window in mainnet shall also be much larger than it is for testnet, to allow provers to restart servers, patch software, and/or resync the blockchain (L1 and L2).

We will have a PR soon to review the alpha-6 testnet configs, please try to influence our decision for your own (prover's benefit).

[github-actions]

This issue is stale because it has been open for 30 days with no activity.

[github-actions]

This issue was closed because it has been inactive for a week since being marked as stale.