ZK Fee Mechanism Design

Apply Here

Problem Statement

The rise of Zero-Knowledge Proofs (ZKPs) in distributed payment system scaling offers a compelling research subject. ZKPs, appreciated for their cheap and near-instant state transition validation, have recently found many applications in high-performing payment systems. Until now, research has focused on designing cryptographic primitives, but recent ZKP deployments have demonstrated issues with transaction fee design. This underscores a need for refined fee mechanisms.

This proposal invites researchers for an empirical-theoretical investigation into ZKP-based systems' fee structures. The project requires a fusion of theoretical understanding and empirical inquiry into ZKP application data. Researchers will need to balance rigorous theoretical analyses and detailed empirical investigations, with an overarching goal to optimize ZKP mechanism design.

Background

The usage of ZKPs for scaling distributed payment systems has seen a surge of interest and major technological breakthroughs in recent years. The main promise behind ZKP-based distributed systems lies in their capacity to nearly instantaneously verify many state transitions with minimal computational overhead by validators. In the context of highly-performant payment systems, this is critical in achieving high throughput and low latency (settlement times) without compromising on the system’s security model. Until now, the majority of ZKP research has focused on the cryptographic primitives themselves, improving on efficiency trade-offs and the blockchain semantics that can incorporate them. However, recent mainnet deployments of ZKP-based scaling solutions have demonstrated the need for improved fee mechanisms for the underlying protocols so that they can retain the promise of low-cost and high-performance.

This RFP focuses on the efficiency trade-offs inherent to rollup architectures. More specifically, the important properties that affect minimal transaction fees need to be specified, with the overarching aim of formally reasoning about average transaction fees in a variety of real-world settings. A successful candidate should be able to reason about the following (modular) system variables:

1. ZKP generation time
2. ZKP computational cost (in kW or USD per proof)
3. Number of transactions verified per ZKP
4. ZKP proof size and L1 gas schedule
5. Data Availability cost
6. Current transaction throughput

Moreover, the effects that the above have on performance should be explored. The novel features provided by ZK-Rollups reduce to the following performance metrics:

1. (Average) Transaction Cost
2. Settlement Time (Latency)
3. Censorship-resistance / Centralization dynamics
4. Support for Privacy/Programmability

Proposal Objectives

A successful candidate should be able to reason about the interaction between the system variables with the above performance metrics in a formal way. More specifically, this RFP aims to answer the following question:

How can we design ZK-Rollups that minimize transaction fees in a variety of adversarial settings so that they can always provide (much) cheaper transaction costs than the underlying L1?

In order to satisfactorily answer the above question, the following issues need to be addressed:

1. Rollup Semantics: How does the rollup’s architecture affect transaction fees in existing mainnet protocols?
   1. There are a couple of different ways to implement rollup semantics, each with (probably?) different effects on transaction costs and performance metrics. Identification and classification of ‘in-the-wild' zk-rollup architectures should be conducted by looking at their features and design specifications.
   2. Differences between the efficiency of the above-enumerated architectures in terms of performance metrics and supported features should be identified and explored.
   3. Ideally, candidates should be able to propose the ‘most optimal’ semantics for designing a zk-rollup for different use cases and provide formal and/or empirical reasoning for their choices.
2. ZKP Cost vs. Batch Size: How does the number of transactions per ZKP affect transaction fees?
   1. This is probably the most important trade-off affecting transaction fees. Since ZKPs are expensive to generate, cost-efficiency is currently achieved by batching many transactions into one ZKP. It has been observed that at times of low transaction volume, this amortization improvement can be strictly lower than using the underlying L1 for settlement.
   2. Empirically, the ‘break-even’ point where (average) L1 fees and batch rollup fees can be discerned from on-chain data. Where does this point lie in current mainnet systems, and how does it compare across different implementations?
      1. An interesting direction would be to provide an apples-to-apples comparison with other types of rollup architectures with a different security model (Optimistic Rollups):
         1. Arbitrum
         2. Optimism
   3. Can we redesign the batching process so as to minimize the ‘maximal’ tx fee in ZKP systems?
      1. What is the minimal number of transactions per ZKP that should be supported?
      2. How does this interface with block frequency? I.e. what are the inherent latency trade-offs here?
   4. How do each of the system variables affect this analysis? 
      1. Is there any difference if we require programmability/privacy features?
      2. What happens during high and low compute cost regimes?
3. Transaction Fee Anatomy: In different L1s, the transaction fees are calculated using different metrics. What are the general underlying theoretical variables that affect this? A successful candidate should be able to reason about the following variables:
   1. Gas cost: how much does it cost to store data on-chain?
      1. What are the relevant parts of the gas schedule that affect this?
      2. Can we do better here by tweaking the gas schedule?
   2. ZKP computational cost: how ‘heavy’ is the ZKP compute?
      1. This depends on both the ZKP architecture and cost of energy.
   3. Are there any other aspects of the specific L1/rollup that affect this?
      1. For example, in fully-programmable rollups the ZKPs might change in size (and thus computational cost) depending on the logic that is being verified.
         1. STARKs and other variable-sized ZKPs depend on this.
      2. Recursive solutions (or “L3” settlement) use nested ZKPs. These might add extra variability to the transaction fee.
4. Ideal VC Properties: After empirically and formally analyzing the above aspects of rollup transactions, a successful candidate should be able to extract ‘ideal’ ZKP properties that can minimize transaction fees. These should serve as end-goals for ZKP designers to aim for when implementing new Verifiable Computation (VC) gadgets that can be compiled into rollups.
   1.  Composability: When two ZKPs are ‘rolled up’ into one, what kind of overhead is acceptable? Points of interest here are:
      1. ZKP size blow-up factor when composing different ZKPs together
         1. Can we compose more than two at a time? What is the variable cost here?
      2. Can we efficiently batch this process? I.e. are there any amortization gains that we can leverage, and will they make a difference?
   2. ZKP Size vs. Generation time trade-offs: Different ZKPs come with different tradeoffs with respect to their size and generation time (per constraint)
      1. Is there an optimal trade-off here? It could be that just minimizing one of the two variables is optimal with respect to maximizing performance metrics
      2. What other variables affect this tradeoff?
         1. Gas schedule
         2. Block frequency
         3. Latency Requirements
   3. Folding: New techniques for VC such as folding have recently shown promise in providing better performance with strictly lower overhead
      1. Do these provide any meaningful improvements for transaction fees?
      2. What kind of changes to mechanism design (if any) would they require?
5. Fee Market Mechanism Design: After the above have been formally and empirically analyzed, ideally a proposal for the transaction fee market should be specified. This could be similar to existing approaches, or improving on them in tangible ways.
   1. Threat model: are there any strategies on current fee market mechanisms that can induce sybil or other denial-of-service attacks?
   2.  Can we modify existing fee market designs to achieve strictly better results for all or any performance metrics?
      1. There could be different proposals for different rollup semantics and use-cases
      2. How does this interface with CFMMs?
         1. Can we leverage the orthogonality of designing a CFMM and a ZK-Rollup to achieve better results?
         2. What rollup semantics are best suited for use with CFMMs?
   3. Are there any additional metrics we should think about?
      1. MEV auctions
      2. Fully private computation (FHE or DP)

References

Current ZKP-based rollups on mainnet/testnet

• Starknet
• zkSync Era
• Scroll Alpha Testnet
• Polygon
  • Miden
  • Hermez
• AZTEC Protocol

Additional Performant ZKP Implementations/Resources

• Mina Protocol*
  • ZKP usage here is for state-verification
• Risc0
• ZCash 
• Aleo Network
• arkworks
• 0xPARC

VC Literature

• STARKs
  • PLONK-based FRI protocols (plonky2)
  • AIR-based FRI protocols
• SNARKs
  • Groth16
  • ZKP Aggregation
• Folding
  • Nova (also HyperNova, implemented here)
  • Protostar 
  • Sangria