Introduction Zkrollups offer a promising solution to Ethereum’s scalability problem by aggregating multiple transactions off-chain and only presenting their cryptographic proof on-chain. The efficiency and reliability of zkrollup networks depends heavily on the robustness of the underlying mechanisms. Currently, zkrollups are in a stage of development regarding system mechanisms and aim to be compatible with Ethereum’s features, hence the need for innovation and research in this area. As an extension of Ethereum, it is essential that zkrollups embody core values such as decentralization, transparency, security and fairness. While the current research landscape in this ecosystem predominantly focused on optimizing the sequencer actor, there is a notable lack of emphasis on provers. This gap in the literature motivates our research to address challenges related to selecting, managing and incentivizing provers in zkrollups. Inadequate prover selection and incentives may result in network congestion, security vulnerabilities and diminished user trust, making it imperative to tackle this problem. By evaluating the existing research and methods, the research aims to answer the following questions: What characteristics define an optimal incentive structure? What is an optimal decentralized prover network design? Our proposed solution begins with a detailed examination of existing research on prover mechanisms. Following this, we aim to establish and quantify criteria that accompany the development of a mathematical model to simulate the network of provers. By adopting this comprehensive approach, we aim to contribute valuable insights that advance the evolution of zkrollups, fostering a more robust and secure decentralized ecosystem.

Introduction Zkrollups offer a promising solution to Ethereum’s scalability problem by aggregating multiple transactions off-chain and only presenting their cryptographic proof on-chain. The efficiency and reliability of zkrollup networks depends heavily on the robustness of the underlying mechanisms. Currently, zkrollups are in a stage of development regarding system mechanisms and aim to be compatible with Ethereum’s features, hence the need for innovation and research in this area. As an extension of Ethereum, it is essential that zkrollups embody core values such as decentralization, transparency, security and fairness. While the current research landscape in this ecosystem predominantly focused on optimizing the sequencer actor, there is a notable lack of emphasis on provers. This gap in the literature motivates our research to address challenges related to selecting, managing and incentivizing provers in zkrollups. Inadequate prover selection and incentives may result in network congestion, security vulnerabilities and diminished user trust, making it imperative to tackle this problem. By evaluating the existing research and methods, the research aims to answer the following questions: What characteristics define an optimal incentive structure? What is an optimal decentralized prover network design? Our proposed solution begins with a detailed examination of existing research on prover mechanisms. Following this, we aim to establish and quantify criteria that accompany the development of a mathematical model to simulate the network of provers. By adopting this comprehensive approach, we aim to contribute valuable insights that advance the evolution of zkrollups, fostering a more robust and secure decentralized ecosystem.

Nilu's Prover Strategy Objectives 1. Cost The primary goal of a rollup is to reduce user costs by scaling Ethereum. Minimize Computational Cost associated with the computation performed by provers. Subject to

Week 15 & 16 Update Over the past two weeks, we have successfully finalized and submitted our decentralized prover network proposal to Aztec: [Proposal] Decentralized Prover Network (Staking, Reputations and Proof Races) In summary, we present an innovative mechanism that facilitates decentralization, encourages permissionless entry, ensures liveness, and enhances cost-efficiency. It’s an in-protocol mechanism that integrates staking for eligibility and slashing as a security mechanism to disincentivize malicious behavior. It also employs reputation score to measure prover uptime and failures. The provers are selected through a VRF from a pool with the highest reputation score. The design has a backup mechanism for emergencies in times of prover failure and network congestion. The backup mechanism is proof racing in a more confined environment, which promotes competition and liveness. Other features like proof batching and distributed proving can be added on top of this simple design. I'm finishing up the last touches for the final development update and getting ready for the project presentation. After Devconnect, my plan is to dive deeper into the simulation, making it more detailed to gather valuable insights. The goal is to make the system more detailed and to address important questions. Key aspects to be added include: Prover Efficiency ($\gamma_i$): The efficiency of each prover, indexed by 'i,' which scales the cost and proving delay. More efficient provers have lower costs and shorter proving delays. Cost to Prove a Batch (Ci(D)): The cost to prove a batch of size 'D' by prover 'i' is determined by a simple scaling factor: $C_i(D) = \frac{D}{\gamma_i}$. This means that the cost to prove a batch increases linearly with its size, but the scaling factor γi depends on the efficiency of the specific prover. More efficient provers (higher γi) have lower costs. Proving Delay (Ti(D)): The time it takes prover 'i' to prove a batch of size 'D' is also scaled by its efficiency: $T_i(D) = \frac{D}{\gamma_i}$. This means that the proving delay is directly proportional to the size of the batch, and more efficient provers (higher γi) can prove larger batches in the same amount of time.

[Proposal] Decentralized Prover Network (Staking, Reputations and Proof Races) Authors: Norbert, Nilu, Rachit Special thanks to Barnabé Monnot (RIG/EF) for his review and suggestions. Summary We propose a simple mechanism that enables decentralization, permissionless entry, liveness and cost-efficiency. It's an in-protocol mechanism that integrates staking for eligibility and slashing as a security mechanism to disincentivize malicious behavior. It also employs reputation score to measure prover uptime and failures. The provers are selected through a VRF from a pool with the highest reputation score. The design has a backup mechanism for emergencies in times of prover failure and network congestion. The backup mechanism is proof racing in a more confined environment, which promotes competition and liveness. Other features like proof batching and distributed proving can be added on top of this simple design. Permissionless Entry and Eligibility Anyone meeting the eligibility criteria can join as a prover and leave at any time. In the exit case, the stake can be withdrawn in a week.

Week 14 Update Last week was all about cadCAD and learning to design mathematical equations to model the flow of inputs and outputs of the system. So far, the model simulates random incoming transactions and processes them according to the number of provers available. It also calculates user value based on the rate of random data size and user cost based on the unprocessed transactions. You can find the github repo for the model and simulation here: https://github.com/niluferokay/Prover-Mechanism-Simulation/blob/main/Prover%20Mechanism%20Simulation.ipynb I also created simulation notes. I really enjoyed the cadCAD course, I even created a meme and got the approval of the CADLabs team! Even though I haven't gotten into radCAD yet, I look forward to it!https://twitter.com/CADLabs_org/status/1716117655973777466 Next steps are to integrate an equation for prover efficiency into the model, followed by adding constraints and criteria. Besides using Monte Carlo Simulation method, I plan to explore Parameter Sweeps and A/B testing for further experimentation.

Simulation Notes Modelling 1. State Variables A state variable is one of the set of variables that are used to describe the mathematical "state" of a dynamical system. (Wikipedia) Time as a system state 1 timestep == 1 minute 2. System Parameters

Week 11 & 12 Update On weeks 11 and 12 worked on: 📊 Formulating prover criteria for the optimization modelFull version 📝 Taking notes on the prover mechanism research Had a very productive discussion with Norbert. We decided to start designing the simulation model alongside formulating metrics. Preparing for agent-based simulation with cadCAD: Here's a great link for getting started: cadCAD Onboarding

Prover Mechanism Notes Applications will pursue decentralized proving for a few reasons: Liveness: Multiple provers ensure that the protocol operates reliably and doesn’t face downtime if some provers are temporarily unavailable. Censorship Resistance: Having more provers improves censorship resistance. A small prover set could refuse to prove certain types of transactions. Competition: A larger prover set can strengthen market pressures for operators to create faster and cheaper proofs. Proof Networks Internalizing the prover role improves native token utility by allowing a protocol to leverage its own token for staking and prover incentivization.

The goal is to find a set of design parameters that optimize a weighted combination of the following objectives while respecting the constraints. Multi-objective optimization algorithms can be applied to solve this complex problem and find a set of design choices that best meet the desired objectives. Decentralization The mechanism should avoid unintentionally leading to centralization or monopolization. Some selection mechanisms might inadvertently favor well-funded or resource-rich participants, leading to centralization. The mechanism should aim to reduce such biases. 1. Maximize Geographic Diversity Geographic distribution shows the spread of prover network across different physical locations. The Geographic Diversity Index (GDI) is a measure that can quantify the degree of decentralization or geographic diversity in a network. Geographic Diversity Index (GDI) = Number of distinct geographic regions or countries where provers are located / Total number of provers in the network

Week 10 Update I have published the list of resources for the prover mechanism on github so that other researchers can benefit from it. Announced our project and resources on twitter:https://x.com/niluokay/status/1703737201295540305?s=20 https://x.com/niluokay/status/1703743165469950095?s=20 The rollup economics repo is featured in the Flashbots weekly letter! So happy about it! :) https://preview.mailerlite.io/emails/webview/11209/99765783893116817 Created notes on prover mechanisms: https://hackmd.io/@nilu/provernotes

Week 9 Update In week 9, we had a very productive meeting with our mentor Barnabe. We went through important aspects of our project, especially with regards to quantifying prover criteria and defining expectations from the simulation. Here are some key points of our discussion: Quantifying Criteria We recognized the need to translate our criteria and metrics into a mathematical format, likely in the form of optimization and allocation problems. This approach would enable us to integrate them into our simulation model. One of the central concerns raised was the need to quantify the costs associated with prover failures. If the rollup plans to release batches infrequently, the reliance on a single prover becomes a potential bottleneck. We must explore the delay it introduces to the system and find a way to measure the economic loss it incurs. Our conversation touched upon the concept of decentralization. We need to define and quantify parameters, such as the maximum number of provers in the system, and consider metrics like the Gini coefficient to measure economic decentralization. To minimize costs, it's essential to incentivize the most efficient provers in the system—those who produce proofs at the lowest cost. We discussed mechanisms that induce healthy competition among provers to increase efficiency. Block rewards were one such mechanism, as they encourage individuals to compete for tokens. However, a balance needs to be struck to avoid overpaying or underpaying provers.

List of Prover Mechanisms Research AZTEC Ideas on a proving network Decentralized and permissionless proving design discussion B52 or [Proposal] Sequencer Selection: B52 — PBS with a federated prover network Fernet or [Proposal] Sequencer Selection: Fernet Whisk-y: should we use Whisk for sequencer selection? [Proposal] Sequencer Selection: Cookie Jar! Aztec Upgrade Training Wheels [Upgrade Proposal] - The Empire Stakes Back

Week 8 Update Unfortunately, I came down with a cold while traveling over the weekend and I'm currently in the process of recovery, which is why I couldn't attend the EPF meetings this week. 😷 Throughout this week, I have scanned zk forums and Ethereum research portals to compile a comprehensive list of resources on prover research. In the upcoming days, we plan to review these sources. Our approach will be guided by the criteria we have set and we will conduct a thorough review of the literature. 📚🔍 I added new resources to the awesome-rollup repo and provided additional details to recognize active researchers in the field and the relevant time period. Furthermore, I prepared notes on rollup economics based on the resources I've covered.

Rollup Economics Notes Understanding rollup economics from first principles by Barnabé Monnot (Feb, 2022) Rollups guarantee correctness of the off-chain execution, as well as availability of the data behind the execution. Players in the rollup game: Users transact on L2, operators interface between them and the base layer, where data is eventually published. Rollup Costs Costs as "energy sinks" in a rollup system. It highlights that running such a system incurs costs, including L2 operator costs, L1 data publication costs, and congestion costs. These costs are associated with different parties in the ecosystem. L2 Operator Costs: These are the tangible costs incurred by rollup operators to maintain the infrastructure behind the rollup, including processing transaction data and computing state roots/state diffs/validity proofs, etc. L1 Data Publication Costs: This refers to the cost associated with publishing a compressed summary of a set of transactions from the rollup to the Ethereum base layer. Data is published by simply posting it as “CALLDATA”, a transaction attribute which allows the sender to add an arbitrary sequence of bytes. The cost of publishing data is incurred by the base layer. To publish data on Ethereum, the current market price of data is governed by EIP-1559, where each non-zero byte of CALLDATA consumes 16 gas, while each zero byte consumes 4 gas.

Prover Mechanism Design Criteria Decentralization Liveness Censorship Resistance Sybil Attack Resistance Permissionless Transparency and Fairness Scalability Cost

Week 7 Update In week 7, we focused on preparing for the project presentation and successfully presented our project to the protocol fellows. We also reached out to our mentor Barnabe, to share our updates and get his valuable feedback on our progress and direction. I look forward to our upcoming meeting with him next week!✨ I began working on the list of prover mechanism and incentives, following Starknet's proposed research for decentralization. Here are all the resources related to the provers I found on the Starknet community portal: StarkNet decentralization : Kicking off the discussion Starknet Decentralized Protocol IV - Proofs in the Protocol Simple Decentralized Protocol Proposal Decentralization: simplest suggestion Starknet Decentralization Day Summary

Week 6 Update During week 6, Norbert and I prepared a comparison table for zk-rollups. While we plan to add more rollups to this table, our preliminary analysis points to a worrying trend: most zk-rollups lack decentralized seqeuencers or provers. This centralized tendency in the system significantly increases risks and vulnerabilities that are counterintuitive to the core philosophy of Ethereum. Consequently, we turned our attention to the resources of the rollup research community to create a comprehensive list of prover selection methods and related incentives. This part of research is a bit like a journey of discovery into new territories. The prospect of discovering valuable insights is really exciting! 🗺️⛵🦜💎 Additionally, based on the information from these research portals, we formulated a set of criteria and questions to critically evaluate various prover mechanisms. Furthermore, edited the project proposal to include the prover selection method besides incentives and to cover the prover mechanism in general.

Week 5 Update In week 5, I conducted research on the zkrollups' system architecture, focusing in particular on the methods for selecting provers and sequencers, the incentives associated with them, and the measures taken to address potential risks such as sequencer or prover failures. I also examined how they ensure resistance to censorship, among other concerns. My research focused on Aztec and Starknet. Notably, both rollups are currently working with centralized operators and their documentation does not provide clear details about their incentive structures. As the provers are centralized, they are likely to be paid outside the protocol. Despite this centralized approach, both projects have goals to move towards decentralization in the foreseeable future. My research presentations of Aztec and Starknet. 🌈🌟 Although Aztec is not currently active, it has an impressive research team working diligently to reinvent the design mechanism of their protocols. In a recent initiative, Aztec organized a competition to identify the most efficient decentralized sequencer selection mechanism. Out of several proposals, B52 and Fernet emerged as the top contenders. The general opinion is that Aztec is inclined to integrate the Fernet mechanism and is currently looking for a suitable prover selection method. It is exciting that our goals intersect in this way with a pioneering research team. As our research into prover mechanisms and incentives progresses, I am enthusiastic about the possibilities of sharing our discoveries with them or developing a dialog to get their valuable insights. 🔮

Week 4 Update In week 4, we met with protocol fellows Rachit and Norbert and discovered that we have a similar interest in the project topic. After a fruitful discussion, recognizing the vast scope and depth of the subject, we decided to join forces and work together on the project. Working together will make it possible for us to cover more areas, brainstorm ideas more effectively and provide support to each other throughout the entire process. This week, we will be reaching out to Barnabe to announce our decision to collaborate. Additionally, we will clearly outline our individual roles and responsibilities within the project. We believe this will ultimately lead to more comprehensive and impactful findings in the field of prover incentive structures in rollups. I created a repo with awesome resources to dive into the world of rollups from a cryptoeconomic and game theory perspective! 🎲✨ https://github.com/niluferokay/awesome-rollup-economics I plan to embark on my research with these captivating questions that fuel my curiosity: