foreword

foreword

image description

first level title

What is a computing agent

With the expansion of applications and users on Ethereum, the degree of congestion on the Ethereum mainnet continues to increase. Using zkRollup for Layer 2 expansion has become an attractive solution. FOX is a project that focuses on using the FOAKS algorithm for zkRollup. The feasibility of zkRollup essentially lies in the principle feasibility of the zero-knowledge proof algorithm used. Simply put, the function implemented by the zero-knowledge proof algorithm is to make the prover prove something to the verifier without revealing any information about it. The construction of zkRollup is to take advantage of this property, so that the nodes of Layer 2 can execute the calculations originally performed on Layer 1, and at the same time provide proof of the correctness of the calculations to the Layer 1 nodes.

From a broader perspective, we can understand the above process as, because the verifier (Layer 1 node) has limited computing power, this part of the calculation is delegated to the prover (Layer 2 node) to perform, and the prover completes After completing this task, the result needs to be returned to the verifier. From this perspective, we can say that the zero-knowledge proof algorithm enables the realization of a "computing agent" that guarantees correctness. From a macro perspective, the example of this kind of computing agent can be expressed as an application in the form of zkRollup. Specifically, in the zero-knowledge algorithm, the idea of ​​this kind of computing agent also has various applications.

first level title

Why do you need a computing agent

From the perspective of system practicability, in many cases, the computing power of computing nodes is limited, or computing resources are very precious. For example, all calculations on the Layer 1 chain (including transfers and contract calls) need to go through the consensus of all nodes, and users need to pay high fees for this. Therefore, in this case, it is a natural idea to "proxy out" the calculations originally handled by consensus nodes to off-chain nodes to avoid consuming on-chain resources. And this is exactly the off-chain computing service that FOX focuses on.

From the perspective of cryptography theory, in the GMR model, the prover is limited to have unlimited computing power, and the verifier has polynomial computing power. The fundamental properties of zero-knowledge proofs cannot be satisfied if the verifier also has infinite power. So naturally, tilting the calculation to the prover's side and letting the prover undertake more calculations is a problem that many zero-knowledge proof algorithm designs will consider.

first level title

Code Switching

This section introduces the Code Switching technique used in Orion. Both Orion and FOAKS use Brakedown as a polynomial commitment scheme, and Code Switching is a process named in Orion where the prover replaces the verifier to perform verification calculations.

In the article "Understanding the Polynomial Commitment Protocol Brakedown in FOAKS", we have introduced that the verification calculation of the verifier is the following process:

Now if the prover is asked to undertake this part of the calculation, in addition to performing these calculations, the prover must also attach a proof value to prove that his calculation is correct.

The way to do this is to write the above equation as an R1CS circuit as well:

first level title

Computational Agents in FOAKS

Similar techniques are also used in FOAKS to complete the calculation agent. It is worth mentioning that FOAKS realizes non-interactive proofs due to the use of Fiat-Shamir heuristic techniques. To learn more, readers can refer to "How to Transform Interactive Proofs into Non-Interactive Proofs?" Fiat-Shamir Heuristic! ". Therefore, the challenge generation of FOAKS is different from the Code Switching method used by Orion, and a new equation needs to be added to the circuit:

In this way, the prover in FOAKS also generates a calculation proof for the proxy verifier to verify. For the process of verifying the proof, FOAKS uses the algorithm itself to iterate, which is also the key content of FOAKS to achieve recursion. For details, see "How to Design an Exquisite Recursive Proof Scheme".

epilogue

epilogue

secondary title

references

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