Author: Fox Tech CTO Lin Yanxi, Fox Tech Chief Scientist Meng Xuanji

Introduction

The concept of computational delegation between Prover and Verifier is one of the core elements of zero-knowledge proofs, serving as a tool to balance the trade-off between the workload of the prover and the verifier and their respective complexities. The essential difference among various zero-knowledge proof algorithms lies in the degree of computational delegation; high levels of delegation may simplify the verification process but can increase the complexity of the proof, leading to longer proof times or larger proof sizes. Conversely, low levels of delegation may impose a heavier burden on the verifier.

Figure 1: The impact of computational delegation degree in zero-knowledge proofs

What is Computational Delegation

With the expansion of applications and users on Ethereum, congestion on the Ethereum mainnet has increased, making the use of zkRollup for Layer 2 scaling an attractive solution. FOX focuses on using the FOAKS algorithm for zkRollup. The feasibility of zkRollup fundamentally relies on the viability of the underlying zero-knowledge proof algorithm. In simple terms, the function of a zero-knowledge proof algorithm is to allow the prover to demonstrate to the verifier that something is true without revealing any information about that thing. The construction of zkRollup leverages this property, enabling Layer 2 nodes to perform computations originally conducted on Layer 1 while providing proof of computational correctness to Layer 1 nodes.

From a broader perspective, we can understand the above process as the verifier (Layer 1 node) having limited computational capacity, thus delegating part of the computation to the prover (Layer 2 node) to execute. Once the prover completes this task, they need to return the results to the verifier. From this angle, we can say that zero-knowledge proof algorithms enable the realization of "computational delegation" that ensures correctness. Macroscopically, examples of such computational delegation can be manifested in applications like zkRollup, while specifically within zero-knowledge algorithms, this concept of computational delegation has various applications.

This article mainly introduces the Code-Switching technique mentioned in Orion, which allows the prover to assist the verifier in executing the verification computation process, as well as how FOAKS applies this technique for recursion, thereby reducing the size of the proof and the overhead for the verifier.

Why Computational Delegation is Needed

From the perspective of system practicality, in many cases, the computational power of nodes is limited, or computational resources are very precious. For example, all computations on Layer 1 chains (including transfers and contract calls) require consensus from all nodes, and users must pay high fees for this. Therefore, in such cases, the idea of "delegating" computations that would normally be handled by consensus nodes to off-chain nodes is a natural one, avoiding the consumption of on-chain resources. This is precisely what FOX focuses on with its off-chain computing services.

From a cryptographic theoretical perspective, the GMR model stipulates that the prover has unlimited computational power while the verifier has polynomial computational power. If the verifier also had unlimited capacity, the fundamental properties of zero-knowledge proofs could not be satisfied. Thus, it is natural to tilt the computation towards the prover, allowing them to bear more of the computational load, which is a consideration in the design of many zero-knowledge proof algorithms.

Of course, to achieve this, special techniques are required.

Code Switching

This section introduces the Code Switching technique used in Orion. Both Orion and FOAKS utilize Brakedown as a polynomial commitment scheme, and Code Switching refers to the process in Orion where the prover replaces the verifier in executing verification computations.

In the article "Understanding the Polynomial Commitment Protocol Brakedown in FOAKS," we previously introduced the verification computations for the verifier as follows:

idxI,C0[idx]==\<0,C1[:,idx]>and EC(y0)==C0

idxI,C1[idx]==\<r0,C1[:,idx]>and EC(y1)==C1

Now, if we let the prover take on this computation, the prover must not only perform these calculations but also provide proof values to demonstrate that their computations are correct.

The approach is to express the above equations as R1CS circuits:

Statement:

EC(y0)=C0, EC(y1)=C1

idxI,C0[idx]=\<0,C1[:,idx]>and EC(y0)=C0

idxI,C1[idx]=\<r0,C1[:,idx]>and EC(y1)=C1

y=\<r1, y1>

idxI, EC(C1[:,idx]) is consistent with ROOTidx, and ROOTidx's Merkle tree proof is valid.

Then, the Virgo algorithm is used for verification.

Computational Delegation in FOAKS

In FOAKS, similar techniques are used to achieve computational delegation. It is worth mentioning that FOAKS implements non-interactive proofs using the Fiat-Shamir heuristic. For more information, readers can refer to "How to Transform Interactive Proofs into Non-Interactive Ones? Fiat-Shamir Heuristic!" Therefore, the challenge generation in FOAKS differs from the Code Switching method used in Orion, and new equations need to be added to the circuit:

0=H(C1,R, r0,r1)

I=H(C1,R, r0,r1,c1,y1,c0)

After this, the prover in FOAKS also generates the computational proof for the delegated verifier. For the verification process of the proof, FOAKS utilizes its own algorithm for iteration, which is a key aspect of FOAKS achieving recursion. For specific details, see "How to Design an Ingenious Proof Recursion Scheme."

Through a certain number of iterations, the size of the proof can be compressed, significantly reducing the computational burden and communication complexity for the verifier. This is the significant importance of the FOAKS zero-knowledge proof scheme for FOX's zkRollup.

Conclusion

The degree of computational delegation in the zero-knowledge proof algorithms used in zkRollup needs to be meticulously designed; it must be just right to achieve optimal overall efficiency. The FOAKS algorithm realizes adjustable computational delegation through its iterative recursion, specifically designed as a zero-knowledge proof algorithm for zkRollup.

References

1. Orion: Xie, Tiancheng, Yupeng Zhang, and Dawn Song. "Orion: Zero knowledge proof with linear prover time." Advances in Cryptology--CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15--18, 2022, Proceedings, Part IV. Cham: Springer Nature Switzerland, 2022.