## Analysis of Taiko's prover concepts

**Acknowledgements:** Special thanks to Lisa and Brecht from the Taiko team for their valuable comments and suggestions.
### Introduction
Among the scaling solutions of Ethereum the rollup-centric approach has been taking central-stage in the past years. While optimistic rollups have the early-starter advantage, the development of zk-rollups has gained exponential traction. One of the key players at the heart of zk-rollups is the prover that generates the zero-knowledge proof (also called validity proofs) for the batch of transactions "rolled-up" by the block proposer.

A well-crafted prover selection and incentive mechanism is paramount to ensure security, resiliance, decentralization, trustlessness as well as censorship-resistance of a zk-rollup protocol. In this article, we will delve into the evolution of Taiko's prover models to explore the design considerations and the key concepts behind.

#### Taiko’s design priorities:

Taiko is an Ethereum-equivalent zk-rollup that emulates Ethereum, natively supports all EVM opcodes and follows a [type-1 zkEVM architecture](https://vitalik.ca/general/2022/08/04/zkevm.html). As a based-rollup in which the sequencing is performed by the L1 validator set, Taiko prioritizes utmost Ethereum-equivalence over the speed of proof generation. Besides Taiko has been focusing on decentralization from day 1, thus fostering censorship-resistance and strengthening the network's resilience, and promoting permissionsless entry for newly joining provers.

### Prover mechanisms

#### Alpha-3 testnet

The [approach on Alpha-3](https://community.taiko.xyz/t/taiko-proving-design-overview-grimsvotn-and-eldfell-cases/1014) testnet was a competitive one based on a **'conditioned' proof racing**. In a pure proof racing all provers are racing to generate a proof for the L2 block but only the first prover to submit a valid proof gets rewarded. The probability of a valid proof being generated is very high but due to the competitive design the compute requirements to become profitable may unintentionally create a higher entry barrier than initially anticipated and limit permissionless entry. It also bears a significant risk for centralization as more resource-rich provers could easily become dominant, and force less resourceful provers to exit the network. The mechanism based on pure competition carries significant waste of compute resources. This could be viewed as redundancy, and thought of as promoting efficiency and ensuring liveness, however its centralization risks outweigh the advantages by far. Centralization could also increase the risk of censorship and the impact of an attack.

By introducing an optimal target window for proof submission, Taiko was able to address the above risks at a certain level. A target reward 'x' (adjusted based on historical reward values) was paid to the prover if it submitted the proof exactly at the target window 'n'. If proven earlier, the reward was lower, if later, the reward was higher.

 <div style="text-align: center"> Source: Taiko </div>

With the above addition to the proof-racing the provers had to find an optimal trade-off point between submitting a proof as late as possible to maximize rewards but also submitting earlier than all other provers. In this model more resourceful provers could still become dominant by submitting early proofs even at the cost of profitability thus forcing other provers to exit.

#### Alpha-4 testnet

The **staking-based prover design** implemented [on Alpha-4 testnet](https://community.taiko.xyz/t/taiko-proving-design-overview-grimsvotn-and-eldfell-cases/1014) included a random prover selection from the top 32 provers. Every prover had to meet three conditions:
* provide a stake,
* indicate their expected reward per gas (which was limited to 75-125% of the gas fee adjusted based on historical values),
* specify their compute capacity which is dynamically adjusted (decreased by one if they are assigned a proving task, and increased when a proving task is completed).

Every prover was assigned a prover weight calculated based on their stake and their expected reward per gas. This reflected their probability to be selected. The selected prover had to submit a valid proof for verification within a pre-set time window, failing which its stake was slashed.

The staking requirement creates financial interest and promotes honest behavior. However if the required amount is too high, it limits permissionless entry and poses a risk of centralization. On the other hand unregulated stake amounts could lead to imbalances in selection probability, issuing rich provers unequal advantages and weight. A bidding system results in increased efficiency and lower proof costs (and also transaction fees) through competition, and also avoids wasting compute resources. By combining it with with random selection Taiko managed to mitigate the risks of economically powerful provers submitting bids with losses to kill competition and gain dominance.

In this model the provers with the highest stakes and the lowest expected rewards (i.e. bids) had the highest chances for being selected. While Taiko successfully eliminated several risks and downsides compared to Alpha-3, this mechanism was still unintentionally leaning towards more resourceful participants (who could afford to put up a high stake amount and to receive low rewards, e.g. either because they possessed expensive hardware to produce proofs in a cost-efficient way, or by being able to operate without profit). Also, having only 32 provers in the prover set the design was not fully inclusive, especially considering solo provers.

#### Alpha-5 testnet

In its most recent testnet Taiko implemented a [proposing and proving design inspired by PBS](https://taiko.mirror.xyz/0jc5XA5RVjOUNVdRdGmw9prlsC4deA1XgZJppmXh8rs) (Proposer-Builder Separation) and introduced an **off-chain proof market** where proposers actively seek proof service providers.

Provers need to provide a bond of 2.5 TKO to be assigned a block. There are two ways to assign a block to a prover:

1. A local Taiko-node's proposer would select its own local prover by default.
2. A proposers can also choose any prover from the open proof market. Once the proposers send the L2 block’s transaction list to an open prover market, provers will submit bids with the rewards they expect for the proving task and the proposer will select the prover based on that.

 <div style="text-align: center"> Source: Taiko </div>

Once the selected prover commits to deliver the proof within the agreed timeframe, the prover fees are paid by the proposer to the prover, i.e. even before the proof is delivered. This is possible because the bond is a much more significant incentive for the prover to submit the proof.
If a valid proof is submitted on time, the bond will be released back. In case of a prover failure, 25% of the bond is used to pay the new prover generating the proof instead of the failed one, while 75% is burnt.

This model is financially more inclusive as the provers do not need to lock up a certain amount of stake for the whole duration of their active participation. Instead, it is enough for them to provide a financial commitment (bond) for the assigned proving tasks, that results in a lower entry barrier. On the other hand it may be easier for provers to 'free-ride', i.e. join and leave the network more flexibly. Due to this, the cost of a coordinated attack in which a large number of provers become inactive at the same time is much lower. The mechanism promotes competition via bidding, and network efficiency through not wasting compute resources.

The risk of prover failure is low due to the financial interest to act honestly, as well as the other available active proof service providers in the market, however the risk of economically powerful provers becoming dominant through submitting lower bids even at their own loss is still present.

### The future is open

Overall the evolution of prover concepts is clearly visible along the different implementations. In Alpha-5 testnet Taiko managed to create the lightest mechanism, maximizing advantages and addressing several risks and weaknesses, and [constantly considering further improvements](https://github.com/taikoxyz/taiko-mono/issues/14452).

But this is not the end of the road. Sequencer and prover models of zk-rollups are constantly evolving, new ideas and concepts are born every day looking to find the most optimal mechanism that is secure, inclusive, permissionless and trustless, and at the same time promoting efficiency and censorship resistance. Curious to how the prover design will be further improved and fine-tuned as Taiko approaches mainnet launch in 2024.

### Resources:

https://community.taiko.xyz/t/decentralized-and-permissionless-proving-design-twitter-spaces-wrap-up/1087
https://community.taiko.xyz/t/taiko-proving-design-overview-grimsvotn-and-eldfell-cases/1014
https://taiko.xyz/docs/reference/prover-market-page
https://youtu.be/9LT6B1pgkI8
https://taiko.xyz/docs/concepts/proving https://taiko.mirror.xyz/0jc5XA5RVjOUNVdRdGmw9prlsC4deA1XgZJppmXh8rs
https://github.com/taikoxyz/taiko-mono/issues/14452