The Core Concerns: Cost, Time, and Security

At the heart of any transaction system are three fundamental concerns: cost, time, and security. Users want their intents to be executed quickly, affordably, and securely. As the Web3 ecosystem grows, zero-knowledge (ZK) proofs have emerged as a key primitive for this agenda by compressing the verification checks required for complex transactions into the validation of a single proof. However, generating ZK proofs involve significant computational and storage overhead; modern protocols use proof marketplaces like Fermah to efficiently match their proving needs with hardware operators with appropriate computational capacity.

Proof Aggregation: A Game Changer for the Proof Market?

Proof aggregation introduces an interesting tool for middleware operators in this marketplace by allowing for the validity of multiple ZK proofs to be verified through a single, aggregated proof. For example, Halo2, a well-maintained proof aggregation system, produces aggregated proofs that have sizes logarithmic in the number of constraints of the largest subproof, and can be verified in linear time to the number of constraints of the largest subproof. Such techniques have the capacity to reduce the number of resulting proofs to be submitted for verification, but the time needed to wait for a “critical mass” of proofs and to aggregate them into a single proof poses a tradeoff. Additionally the cost of generating additional aggregated proofs is an additional consideration in finding a sweet spot in balancing the verification cost reductions granted by proof aggregation and the additional time and costs spent to accumulate enough transactions for aggregation.

Breaking it Down

It’s helpful to simplify this problem by considering the process of aggregating a bunch of identical atomic ZK proofs. We define the key parameters involved in proof generation and aggregation as follows:

* \( \mathbf{n} \): Total number of atomic proofs to be aggregated at once.

* \( \mathbf{t_g} \): Time elapsed between the arrival of two consecutive atomic proofs (aka transaction frequency).

* \( \mathbf{t_p} \): Time required to generate a single atomic proof. We assume \( t_g > t_p$.

* \( \mathbf{t_a} \): Time required to perform a single proof aggregation step.

* \( \mathbf{t_v} \): Time required to verify a single proof.

* \( \mathbf{c_p} \): Cost of generating a single atomic proof.

* \( \mathbf{c_a} \): Cost of performing a single aggregation step.

* \( \mathbf{c_v} \): Cost of verifying a proof.

 We will assume that the cost to verify an aggregated proof is equal to the cost to verify an atomic proof, as the size of an aggregated proof only depends on the number of constraints of the largest atomic proof. 

Total Time to Final Proof: Proof Generation Phase

We further analyze the time and cost of the proof aggregation in the generation and aggregation phases independently.

Each proof arrives at an interval of \( t_g \) and takes \( t_p \) to generate. The last proof begins generating at \( (n-1) \cdot t_g \) and takes \( t_p \) to complete. Let \( \pi_i\) represent the \( i^{\mathrm{th}}\) atomic proof to be generated.

Therefore, time taken to generate all atomic proofs is:

\[T_{\text{gen}} = (n-1) \cdot t_g + t_p\]

Total Time to Final Proof: Proof Aggregation Phase

Aggregation follows a binary tree structure, requiring \) \log_2(n) \) rounds. Each round aggregates pairs of existing proofs, taking \) t_a \) per round. At time \)t_g + t_p \), the first two proofs are available, and we aggregate them as so:

After \(2 t_g\) later, we have the next two atomic proofs and we repeat this aggregation.

Aggregation starts as soon as proofs are available, but the final round cannot begin until all base proofs have been generated. 

Therefore, the total aggregation time after proof generation is:

\[ T_{\text{agg}} = \log_2(n) \cdot t_a,\]

and combined with the time taken to verify the final aggregated proof, the total end-to-end time to obtain the final aggregated proof is:

\[ T_{\text{total}} = (n-1) \cdot t_g + t_p + \log_2(n) \cdot t_a + t_v \]

Total Cost of Final Proof: Proof Generation Phase

We perform a similar analysis for the cost of the proof generation phase. Each atomic proof costs \( c_p\) to produce, so thus the total cost of generating all atomic proofs is \(C_{\text{gen}} n\cdot c_p.\)

Total Cost of Final Proof: Proof Aggregation Phase

Aggregation again requires \(\log_2 (n)\) rounds, so the total aggregation cost is simply \(C_{\text{agg}} = \log_2 (n) \cdot c_a \).

We submit the final proof to the verifier, which incurs a singular cost of \(c_v\). 

Factoring in the cost to verify the final aggregated proof, our total end-to-end cost is

\[C_{\text{total}} = n \cdot c_p + \log_2(n) \cdot c_a + c_v.\]

‍

Note that without proof aggregation, we would verify each atomic proof as it arrives, requiring \(n \cdot c_v\), but no aggregation costs.

Takeaways

Time Complexity: The total time is linear in the number of proofs due to \( (n-1) \cdot t_g \) and logarithmic in aggregation rounds (due to \( \log_2(n) \cdot t_a \)). Therefore, if aggregation time \( t_a \) is much lower than proof generation time \( t_p \), the time overhead added by aggregation steps is negligible. However, if \( t_g\) is high (slow transaction arrival), aggregation delay may dominate.

Cost Complexity: The total cost is logarithmic in aggregation overhead. Additionally, note that only one verification cost is incurred in this end-to-end aggregation loop. Compare this to the otherwise \(n \cdot c_v\) verification costs that would need to be paid if all atomic proofs were to be verified individually. Therefore, aggregation leads to significant reductions in cost for processes in which \(c_v\) is very large.

R1CS Proof Aggregation

We first consider R1CS atomic proofs, which can be aggregated with systems such as SnarkPack which have cost and time considerations that are strongly dependent on the number of proofs aggregated at once. SnarkPack generates proofs that have a cost logarithmic in the number of proofs aggregated at once and a verification time that is also logarithmic in the number of proofs aggregated at once. Additionally, the time taken for SnarkPack proofs to be generated is linear in the number of proofs aggregated at once. Under SnarkPack, the more proofs that are aggregated at once, the faster the verification. Therefore, a proof aggregation loop with a large \(n\) would be extremely effective under SnarkPack. However, this strategy may not be optimal under all proving systems.

Halo2 Proof Aggregation

We now assume that we are working with the Halo2 proof aggregation system and consequently provide a cost analysis using the Halo2 benchmarks. 

In a Halo2 system, the time taken to verify a proof is approximately always 10x faster than the time taken to generate an aggregated proof. Generating many aggregated proofs with the goal of reducing verification costs can therefore be extremely time-intensive.

Furthermore, the cost of proving or verifying a circuit depends on the size of the circuit of the atomic proof, as it directly dictates the size of the prover or verifier needed. In Halo2, the size of the verifier is nearly constant with the size of the atomic circuit, while the size of the prover needed increases linearly with the logarithm of the size of the circuit. If the circuits in our atomic proofs were extremely complex, involving tens of millions of constraints, it may be optimal to directly verify atomic proofs for large circuits to avoid incurring additional proving costs. Conversely, if the atomic proof only involved small circuits, such as proving group membership in ECDSA public keys (~8k constraints), the cost of generating a single proof may shrink to about ~8x less than the cost of proof verification. Thus, it may be advantageous to aggregate together many smaller atomic proofs for simpler circuits together as to reduce the number of verifications needed, while being careful to also balance the time overhead of aggregating proofs.

Conclusion

In conclusion, proof aggregation is a game-changer for optimizing cost, time, and security in Web3 transactions. By carefully weighing the tradeoffs between proof generation, verification, and aggregation, users can unlock significant efficiency gains and cost savings. Understanding these dynamics is key to navigating proof marketplaces like Fermah, where strategic aggregation can dramatically reduce verification overhead and streamline operations. Whether dealing with simple or complex proofs, mastering the art of aggregation empowers users to scale smarter and faster in the zero-knowledge proof ecosystem.