feat(protocol): Open multi-proof for Proposer & Prover

[CeciliaZ030]

Describe the feature request

Description of the feature request here.
From discussions with @Brechtpd and Vitalik's enshrined ZK-EVM

Background

Taiko's current proof system relies on a tier oracle that impose a centralized control of proof type. Such implementation corresponds to a "close" multi-client system under Vitalik's definition:

Another option is a closed multi-client system, where there is a fixed set of proof systems that is known within the protocol. For example, we might decide that we use three ZK-EVMs: the PSE ZK-EVM, the Polygon ZK-EVM and Kakarot. A block would need to come with proofs from two of these three to be valid. This is better than a single proof system, but it makes the system less adaptable because users would have to maintain verifiers for each proof system that exists, there would be an inevitably political governance process for incorporating new proof systems, etc.

On the contrary, an "open" multi-client system is also proposed:

This motivates my preference for an open multi-client system, where proofs are placed “outside the block” and verified by clients separately. Individual users would use whatever client they want to verify blocks, and they would be able to do so as long as there is at least one prover creating proofs for that proof systems. Proof systems would gain influence by convincing users to run them, and not by convincing the protocol governance process. However, this approach does have more complexity costs, as we will see.

The obvious difference differences between these two is whether the protocol has some enshrined precompiles for verification. Vitalik also proposes an "in-protocol ZK-EVM feature" for L1, which implies more nuances for the proof supply chain:

• verification is based on consensus
• proof generation is modular, which separate execution logic and underlying proof system (ZKP/TEE)
• all blocks needs to be type-1 in order to standardized the consensus and modular design (true for L1, but not for most L2s)

To illustrate:

Propose Change

We should implement a semi-open multi-client system on the prover to builder side, while keeping the enshrined verification. For the following rationals:

• We are type-1.
• We have multi-clients already (geth, reth).
• We collaborate with Powdr to support various ZKP compiled from multi-clients, plus SGX, plus PSE.
• We have opened prover's market.
• Can be compatible with current BCR as long as verifiers are pre-deployed and we can assign tiers to proofs type.

We could require the Taiko proposer to specify the proof type at proposal time, more than one types of preferable proofs can be required to get the benefit of multiplexing (the more proofs the better). If the type or amount does not meet the tier requirement, proposeBlock() reverts. Another potential benefit is simplifying proving fee calculation since the proof type is deterministic and uniform; we only need to check the TKO bond.

Further implementation details may need to be considered, but moving in this direction alligns with ZK team's road map with compilation, and will make us the first rollup explicitly practicing the open design of "in-protocol ZK-EVM feature".

Describe alternatives you've considered

Description of the alternatives you've considered here.

Additional context

Additional context here.

[Brechtpd]

We could require the Taiko proposer to specify the proof type at proposal time

Should be left to the prover I think because the proposer only cares about maximizing profits, so the prover with the lowest fee will be selected. So the prover decides what proofs to generate that minimizes his costs and will be accepted by the rollup smart contract.

If the type or amount does not meet the tier requirement, proposeBlock() reverts. Another potential benefit is simplifying proving fee calculation since the proof type is deterministic and uniform; we only need to check the TKO bond.

My opinion is that all blocks should have the same requirements, so no random minimal tier. That solves the deterministic problem and also makes things very easy for the proposer because the proposer does not have to care about proofs at all, the proposer just has to find a prover willing to prove its block. The prover will do so for a fee, and at the risk of losing his bond will generate the required proofs to get its bond back.

We should implement a semi-open multi-client system on the prover to builder side

If we have to do check the validity in a smart contract, following the definition of Vitalik, it would still fall under a closed system I believe. But #15376 would be a good way to still use it in some way.

The interesting thing is that the open system seems incompatible with validity proofs because they require strict and known rules to function. So that narrows things down how we could use it without this enshrined precompile being available on L1. And when it's available on L1, it will be tricky to prove on L2 because we cannot verify it directly in a validity proof, so we would have to propagate these enshrined EVM proofs done on L2 back to L1 for verification I think.

[CeciliaZ030]

Should be left to the prover I think because the proposer only cares about maximizing profits, so the prover with the lowest fee will be selected. So the prover decides what proofs to generate that minimizes his costs and will be accepted by the rollup smart contract.

I guess I say it because I think it's a way to circumvent the TierProvider, feel like when we get rid of this centralized thing a mid-way solution is to let proposer choose, while the protocol specify a minimum requirement. But if there's no tier system at all if we just wanna multiplex proof soundness, it's also okay that we just require a bond which will be taken away if the minimum criteria is not met. In this way we don't really care who's making decision of proof type.

My opinion is that all blocks should have the same requirements, so no random minimal tier.
That would be great, so that no backward compatible is needed.

If we have to do check the validity in a smart contract, following the definition of Vitalik, it would still fall under a closed system I believe. But #15376 would be a good way to still use it in some way.

You're right in strict definition, as long as there is precompiled deploy then the system is closed. However we should certainly leverage Taiko being type1 and our prover market being opened to approach openness in the proof supply chain. Like in #15376, use cryptoecohomy backed verifier or something to decrease the "enshrinement".

And when it's available on L1, it will be tricky to prove on L2 because we cannot verify it directly in a validity proof, so we would have to propagate these enshrined EVM proofs done on L2 back to L1 for verification I think.

This I don't follow 🤔 can you explain?

[Brechtpd]

The enshrined precompile depends on those claim blobs when following the design set out by Vitalik. And the proofs accepted by the protocol for those claim blobs in the open system are without known verifiers, and so not part of the Ethereum spec directly (only indirectly as in those proofs should verify that the spec was correctly implemented, but how that is done is left open and so clients can choose).

So if you want to create a validity proof for this precompile (and so for those claims), you can't really write code that is able to support that really because you don't know what proofs should be accepted. There is no code that can be general enough to support the verification of all possible proofs that can show the correctness of a state transition. You could write code that supports the proof types supported by all major Ethereum clients, but even then you run into the problem that when one of those proofs get updated you would have to update the validity proof as well. So you're back to a closed system.

That's why I say that if somebody would call this precompile on L2, we can't directly create a validity proof for it. The only way to really implement it in an open way is to collect all claims from the L2, repost them to L1 and then let the L1 decide on those claims instead, because that way we avoid having to prove the precompile directly on L2 and instead make use of the open system on L1.

[CeciliaZ030]

I see ... so literally Zk L2 is a precursor to Zk L1. If Ethereum wants open multi-SNARKed without enshrining anything from let's say PSE, then they'd have to leverage the rollup ecosystem which already has battle-tested ZKP for clients. Naturally the major Zk rollup's validity proof will be picked by the community to installed in their verification client. That's cool!

Yooo i think there's some big alpha here :) Although I now agree with you on L2s validity proofs can only be closed.

But we should def ride the tide and articulate this idea from Vitalik to the public. And say that our system (although it's closed) is the most suitable for testing validity proofs for open client systems.

[Craziefire]

1. Hybrid Multi-Client System:
   -Combine aspects of both closed and open systems.
   -Enshrine a set of core proof systems in the protocol for standardization and efficiency.
   -Allow users to propose and adopt new proof systems through a decentralized governance process.
   -Users can choose to run standard verifiers or opt for alternative ones.

2. Dynamic Proof System Registration:
   -Allow proof systems to be registered dynamically on the blockchain.
   -Provers can register their proof systems, and clients can choose which ones to use.
   -Use a decentralized reputation or token-based system to incentivize trust in proof systems.
   -Implement strict security standards for registration to prevent malicious actors.

3. Incentivized Open Multi-Client System:
   -Emphasize an entirely open system where any prover can provide proofs.
   -Introduce economic incentives for users to run and verify specific proof systems.
   -Use a decentralized marketplace for proof systems, where users can choose based on cost, performance, or other criteria.
   -Employ a reputation system to assess the reliability of different proof systems.

4. Layered Verification:
   -Introduce a layered approach to verification, where different layers handle specific aspects of proof validation.
   -Base layer for core and widely accepted proof systems.
   -Additional layers for experimental or niche proof systems, allowing users to choose their level of security and adaptability.

5. Dynamic Consensus-Driven Proof System Switching:
   -Allow the blockchain to dynamically switch between different proof systems based on consensus rules.
   -Implement a protocol-level voting mechanism to decide on proof system changes.
   -Ensure a transition period to allow users to adapt to the new proof system.

6. In-Protocol ZK-EVM Feature with Flexible Implementation:
   -Implement the proposed in-protocol ZK-EVM feature for Layer 1 with a focus on modular design.
   -Allow users to plug in different ZKP or TEE libraries, fostering flexibility.
   -Maintain a high-level of abstraction, separating execution logic from underlying proof systems.

Considerations for Alternatives:
1.Security and Standardization: Balance between openness and the need for standardization to ensure security and interoperability.
2.Governance and Decentralization: Address challenges related to governance processes for proof system updates or additions.
3.Usability: Ensure that users can easily adapt to changes and that the system remains user-friendly.
4.Economic Incentives: Design mechanisms to incentivize users to participate in the chosen proof system.

Selecting the most appropriate alternative would depend on the specific goals, use cases, and considerations of the blockchain protocol in question.

[obamacash]

Great work good people!!

[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.