As a ZK-Rollup, Fox is secure and efficient. Its operations are not limited to the following, swap, deposit, withdraw, and transfer. All the general-purpose dApps can run on Fox.

Deposit

Deposit refers to the process where users deposit Ethereum and ERC20 tokens into the Fox Layer 2 contract so that those tokens can be used on Layer 2. The Deposit process is initiated by the user on-chain. When Fox monitors that the user transfers tokens to the smart contract, it will update the status tree according to the transaction details. First, it will find the corresponding account to which the transaction belongs, then update the status of the corresponding token under that account based on the deposited amount. If there is no leaf node corresponding to the token under this account, then first create the leaf node corresponding to the token, and then update the status. When the status of the leaf node is updated, the hash of the root node will be updated accordingly. The updated hash of the root node of the state tree, together with the validity proof of the Deposit transaction, will be sent to the Layer 1 contract on-chain.

Withdraw

This operation means that the user withdraws the token from Layer 2, unlocks it from the Fox contract, and sends it to the corresponding Layer 1 account. The Withdraw process is initiated by the user from Layer 2. When the Fox contract receives the user’s withdrawal request, it will update the status of the corresponding token under the corresponding account, and send the updated root node hash and the proof of the Withdraw process to the Layer 1 contract on-chain. After the smart contract verifies it as valid, the contract will unlock the corresponding Token and send it to the account on the corresponding chain.

Transfer

It refers to the process where one user sends a certain token to another user in Layer 2. The Transfer process is initiated by the user on Layer 2. When Fox contract receives the Transfer request, it will find the corresponding sending and receiving accounts according to the request details. And it will update the status of the token under the accounts of the sender and receiver according to the sent amount. The hash of the root node of the state tree will be updated accordingly, and together with the validity proof corresponding to the transfer operation, be sent to the contract on Layer 2. Transfer does not change the on-chain status of the token, because the token is still locked in the Fox contract and has not been transferred on-chain.

Swap

A swap protocol system consists of on-chain smart contracts, an off-chain server, a zero-knowledge proof system, and a front-end user interface.

The swap server can use the Web Socket to interact with the user, and monitor transactions on the Ethereum blockchain. All valid transaction requests will be put into the swap protocol mem pool and processed by the Swap Engine. The Folder will roll up the transactions and generate a new block.

Fox adopts a distributed architecture and uses the latest zero-knowledge proof algorithm PLONK plus FRI to generate proofs.

Hardware Implementation is referred to GPU/FPGA/ASIC zkMiners and different ZK proof systems are based on different cryptographic assumptions and target different computational problems. Their implementations are written in different programming languages and run on a variety of hardware. Arithmetic circuit complexity is a reasonable measure for comparing various proof systems. The main parameters that affect the complexity of the proof system are circuit depth, circuit width (the number of gates in each "level" of the circuit), nondeterministic witness size, and multiplication complexity, i.e., the number of multiplication gates.

Hardware implementation is required to deal with the arithmetic circuit complexity. Fox is trying to design a GPU-friendly algorithm and is likely to use GPU as generalized hardware acceleration instead of FPGA/ASIC to execute the hardware acceleration. The ASIC circuit is "static", it brings composability issues, and it requires strong circuit design expertise, the developer experience is poor. ASIC is not the best choice for implementation from this aspect. FPGA requires smaller capital invested and a shorter manufacturing cycle, which is somehow better than ASIC in this aspect. For considering the huge number of Ethereum GPU miners will significantly transfer to zkRollup, GPU may be a better choice than FPGA.

CPU Implementation

The first step of hardware optimization is to perform a simple implementation of the operation that you would like to accelerate. This can help us to accelerate the computation from the algorithm level.

Python is often a good place to begin when implementing a new algorithm and the most commonly used package for numerical calculation is NumPy. NumPy is a library for the Python programming language, adding support for large, multi-dimensional arrays and matrices, along with a large collection of high-level mathematical functions to operate on these arrays.

Using NumPy in Python gives functionality comparable to MATLAB since they are both interpreted, and they both allow the user to write fast programs as long as most operations work on arrays or matrices instead of scalars. In comparison, MATLAB boasts a large number of additional toolboxes, notably Simulink, whereas NumPy is intrinsically integrated with Python, a more modern and complete programming language. Moreover, complementary Python packages are available; SciPy is a library that adds more MATLAB-like functionality and Matplotlib is a plotting package that provides MATLAB-like plotting functionality. Internally, both MATLAB and NumPy rely on BLAS and LAPACK for efficient linear algebra computations.

GPU Implementation

The graphics processing unit (GPU), as a specialized computer processor, addresses the demands of real-time high-resolution 3D graphics compute-intensive tasks. By 2012, GPUs had evolved into highly parallel multi-core systems allowing efficient manipulation of large blocks of data. This design is more effective than CPUs for algorithms in situations where processing large blocks of data is done in parallel.

Nvidia GPUs can be programmed in CUDA. CUDA is a parallel computing platform and allows software to use certain types of GPUs for general purpose processing. CUDA is a software layer that gives direct access to the GPU's virtual instruction set and parallel computational elements, for the execution of compute kernels.

While GPUs are highly parallel, affordable, and easy to buy, copying between host and device memory may incur a performance hit due to system bus bandwidth and latency (this can be partly alleviated with asynchronous memory transfers, handled by the GPU's DMA engine). Therefore, the GPU is not the best hardware candidate.

FPGA  Implementation

FPGA is the practical hardware for zero-knowledge proofs acceleration since it can be both more efficient and lower power consumption.

To define the behavior of the FPGA, the user provides a design in a hardware description language (HDL) or as a schematic design. The most common HDLs are VHDL and Verilog as well as extensions such as SystemVerilog. However, in an attempt to reduce the complexity of designing in HDLs, which have been compared to the equivalent of assembly languages, there are moves to raise the abstraction level through the introduction of alternative languages. For example, the Constructing Hardware in a Scala Embedded Language (Chisel) is an open-source hardware description language (HDL) used to describe digital electronics and circuits at the register-transfer level.

Chisel is based on Scala as an embedded domain-specific language (DSL). Chisel inherits the object-oriented and functional programming aspects of Scala for describing digital hardware. Using Scala as a basis allows describing circuit generators. High quality, free access documentation exists in several languages.

Although Chisel is not yet a mainstream hardware description language, it has been explored by several companies and institutions. The most prominent use of Chisel is an implementation of the RISC-V instruction set, the open-source Rocket chip. Chisel is mentioned by the Defense Advanced Research Projects Agency (DARPA) as a technology to improve the efficiency of electronic design, where smaller design teams do larger designs. Google has used Chisel to develop a Tensor Processing Unit for edge computing. Some developers prefer Chisel as it requires 5 times lesser code and is much faster to develop than Verilog.

ASIC Implementation

An application-specific integrated circuit (ASIC) is an integrated circuit (IC) chip customized for a particular use, rather than intended for general-purpose use. For example, a chip designed to run in a digital voice recorder or a high-efficiency video codec (e.g. AMD VCE) is an ASIC. ASICs have a higher main frequency so they are much faster and cheaper than FPGAs.

Specialized "ASIC" circuits can be designed for different dApps. This is the most traditional way to use zero-knowledge proofs. By customizing the circuit design, the overhead of each DApp will be smaller. However, since the circuit is "static", it brings composability issues, and since it requires strong circuit design expertise, the developer experience is poor. ASIC is not the best choice for implementation from this aspect.

Fox uses some algorithms to accelerate cryptography in its Folder & ZK-FOAKS.

One of the first places to look when accelerating cryptography is to evaluate various algorithmic approaches to the problem. Our protocol is a family of algorithms driven by low-level primitives such as modular multiplication. To begin it is best to understand what group operations are consuming the most compute resources/time, and then investigate the low-level algorithms that are used to implement the primitives of higher-level cryptographic protocols.

It is important to understand that every algorithm represents a unique set of tradeoffs between latency, throughput, power, and area. When selecting an algorithm it is imperative that you understand both the desired goal as well as the underlying hardware that is available for you to use. Algorithmic decisions can not be made in isolation and need to consider the target implementation.

While investigating the operations, we discovered that modular multiplication and modular squaring were consuming the vast majority of the compute cycles. In order to accelerate the above-mentioned cryptographic constructions, we began to evaluate various algorithms and representations that could be used to accelerate these operations. Some such algorithms include schoolbook multiplication, Montgomery multiplication, and Barrett reduction, while representations include polynomial form and residue numeral system.

We believe that hardware acceleration will be an essential component in enabling blockchains protocols to achieve the scalability required for practical use. Today blockchain protocols are limited by their ‘on-chain’ compute and storage capacities, as well as by their networking bandwidth. We believe that through the improvement of ‘off-chain’ hardware and client-side proof generation, we can drastically improve the performance of blockchain networks.

Why Need

The key reason why ZK-Rollup needs hardware acceleration is that ZKP is a very expensive and complex operation so it results in longer proof generation times. Even that it is also common for certain operations to be unfriendly to ZK (for example, bitwise operations used in SHA or Keccak), resulting in long generation times for proofs that might be very cheap operations on a classic computer. The proof generation process may vary depending on the proof system, but the bottleneck is always:

Multiplications of large number vectors (fields or group elements), especially multiscalar multiplications of variable cardinality and fixed cardinality (MSM); Or,

Fast Fourier Transform (FFT) and inverse FFT (although there are techniques for FFT-free proof systems).

In systems with both FFT and MSM, about 70% of the time for generating proofs is spent on MSM, and the rest of the time is dominated by FFT.

Both MSM and FFT are slow, but both have ways to improve performance:

MSM is embarrassingly parallel and can be accelerated by running them on multiple threads. But even on hundreds of kernels, if the length of each element vector is 225 (or 33 million elements, a conservative complexity for an application like zkEVM), multiplication can still end up taking a lot of time. This means repeating the same operations often and using up most of the available memory on the device. In short, MSM requires a lot of memory and is slow even when highly parallelized.

FFT relies heavily on the frequent shuffling of data at runtime. This makes it difficult for them to accelerate by distributing the load across computing clusters, as DIZK shows. In addition, they require a lot of bandwidth to run on hardware. Shuffling means that you need to load and unload elements "randomly," for example, >100GB data sets on hardware chips with 16GB or less memory. While operations on hardware are very fast, the time it takes to load and unload data over the network can end up slowing operations down significantly.

In short: MSM has predictable memory access and allows a lot of parallelisms, but they are still expensive because of the raw computation and amount of memory required.

FFTS have random memory access, which makes their hardware unfriendly and naturally difficult to run on distributed infrastructures.

What is the best hardware to use highly optimized MSM and FFT algorithms to speed up ZKP generation? The acceleration technology can be implemented on a variety of hardware technologies: GPU, FPGA, or ASIC. But which is the best choice? We expect that the winning players in the market will be companies that focus on GPUs over ASICs or FPGAs.

However, if only one or more ZK L1 or L2 eventually achieve dominant scale, and ZK demonstrates that the system is stable near a single implementation, then the likelihood of ASICS outperforming FPGAs may be higher. But if that happens, we may still be a few years away. then the ASICs may win over FPGAs and these two may win over GPUs.

This hardware acceleration can take two forms: 1) Better utilization of existing resources (e.g CPU, GPU) through improved software and algorithmic implementations and 2) The development of custom hardware (e.g. FPGA and ASIC) and novel algorithms suited for their hardware configuration and available resources.

We believe hardware acceleration will be an important part of enabling blockchain protocol to achieve the scalability required for real-world use. Today's blockchain protocol is limited by its "on-chain" computing and storage capacity, as well as its network bandwidth. We believe we can dramatically improve the performance of blockchain networks by improving "off-chain" hardware and client-proof generation.

Algebraic Intermediate Representation

Arithmetization is the simplification of computed statements to a set of algebraic statements involving a set of bounded degree polynomials. In STARK Protocol, the arithmetical output is an algebraic intermediate representation of a computation. A formal definition of AIR includes the following three elements:

(1) Execution trace is a two-dimensional matrix, where each line represents the state of a calculation at time points, each column corresponds to an algebraic register tracked over all the steps of the calculation. Let 𝑇 denote execution trace matrix.

(2) Transition constraints that define algebraic relations between two (or more) rows of the execution trace.

(3) Boundary constraints that enforce equality between some cells of execution and a set of constant values. Boundary constraints can be thought of as defining a set of constraints calculated input and output values.

FRI is an IOPP constructed for the RPT problem, which is executed interactively by both the Prover and the Verifier. At the beginning of the protocol, Verifier has learned the complete encoding f(S), but has not read this encoding, it can query any part of the encoding at any time during the execution of the protocol.

The aim of this section is to expound on how to verify the polynomial efficiently and correctly.

During the execution of the protocol, the Prover and the Verifier interact multiple times. In each interaction, the Prover sends a string to the Verifier, and the Verifier can randomly read any bits of the string without reading the entire string.

Now, let us recall our motivation. Initially, we want to prove that we certainly finished the computation correctly. Subsequently, we translate the original computation problem into a series of constraints expressed by wires and gates, which are actually so-called circuits. Next, it is known now that the circuits could be compressed to a set of polynomials, which can be verified by some methods. Consequently, if the polynomials are verified correctly, the verifier could believe that the procedure of the computation is precisely correct and we did not cheat.

In fact, there are several ways to implement this verification, for example, KZG. The reason why we choose FRI is that FRI does not need a trusted setup, which is an indispensable part of KZG.

For the FRI protocol, the complexity of the verification satisfies the logarithmic relationship. The algorithm ensures that the round consistency verifications can be passed if and only if the initial polynomial satisfies. The actual implementation may vary slightly.

zkFOAKS is a superfast ZKP that reduces the prover time to the theoretical lowest bound, O(|C|) proof time, O(log|C|) verification time, which is called “Doubly Efficient”. And zkFOAKS is transparent, without any setup.

We have the following 3 L1 Contracts deployed on L1(Ethereum) :

• FOX (Main) Contract

1. Main contract for executing various operations on Layer 1.

2. Serves as an interface contract(main entry) of Layer 1 which will collect block data(batch of transactions)and proof submitted from Layer 2 validator.

3. Calls verifier to verify blocks and revert back to Validator if block fails to verify.

4. Calls governance contract to check the validity of certain token before executing deposit/withdraw/transfer operation.

The FOX contract has the following functionalities:

1. Commit blocks

2. Verify blocks

3. Execute blocks

4. Deposit/Withdraw to L1 user’s root account

• Governance Contract

1. Serves as the admin of all contracts, has the authority to upgrade contracts or other operations.

2. Sets and changes the Roller list (further work)

3. Adds new ERC20 tokens

4. Only governor can pass the governance to new governor

• Verifier Contract

1. Verify proof that is generated from Layer 2 by applying zk-FOAKS protocol.

FOX is a scaling EVM-compatable engine for Ethereum. FOX is built on ZK Rollup architecture. ZK Rollup is an L2 scaling solution in which all funds are held by a smart contract on the mainchain, and Fox layer 3 is a high-performance or privacy solution.

DesignFor every Rollup block, a state transition zero-knowledge proof (ZK-FOAKS) is generated and verified by the mainchain contract. This ZK-FOAKS includes the proof of the validity of every single transaction in the Rollup block. Additionally, the public data update for every block is published over other networks at a lower cost.

Our architecture provides the following guarantees:

• The Folder(s) can never corrupt the state or steal funds (unlike side chains).

• Users can always retrieve the funds from FOX even if the folder(s) stop cooperation because the data is available (unlike Plasma).

There are 3 main parts in the Fox architecture: Sequencer, Folders, and L1 Contracts:

• Sequencer gathers transactions, runs the Geth node, leaves the traces of the execution for Folders, and sends the data to ZK-Ringer, which is deployed on other networks, IPFS, or decentralized storage.

• Folders use the traces to generate zero-knowledge proofs for every circuit. The folders then send the aggregated proofs as well as the updated states to the L1 Contracts. The Folder is the core of the Fox system.

• L1 Contracts keep all user’s funds, keep the states, verify the zero-knowledge proofs while updating the states, and manage the deposit and withdraw requests of users.

Folder

Folders calculate proof and commit to the L1 FOX contract through the Double-Deck Express. In this session, we illustrate the core logic of Layer 2 and explain what Folders need to prove in a conceptual way. The detailed proof algorithm can be found in the next two chapters.

Even if the workflow outside remains the same, the underlying processing procedure for Layer 1 and Layer 2 are entirely different:

Layer 1 relies on the re-execution of smart contracts.

Layer 2 relies on the validity proof of zkEVM circuit.

Let’s give a more detailed explanation of how things are going differently for transactions on Layer 1 and Layer 2.

In Layer 1, the bytecodes of the deployed smart contracts are stored in the Ethereum storage. Transactions will be broadcasted in a P2P network. For each transaction, each full node needs to load the corresponding bytecode and execute it on EVM to reach the same state (transaction will be used as input data).

In Layer 2, the bytecode is also stored in the storage and users will behave in the same way. Transactions will be sent off-chain to a centralized zkEVM node. Then, instead of just executing the bytecode, zkEVM will generate succinct proof to prove the states are updated correctly after applying the transactions. Finally, the Layer 1 contract will verify the proof and update the states without re-executing the transactions.

Let’s take a deeper look at the execution process and see what zkEVM needs to prove at the end of the day. In native execution, EVM will load the bytecode and execute the opcodes in the bytecode one by one from the beginning. Each opcode can be thought of as doing the following three sub-steps : (i) Read elements from stack, memory, or storage (ii) Perform some computation on those elements (iii) Write back results to stack, memory, or storage. For example, add opcode needs to read two elements from the stack, add them up and write the result back to the stack.

So, it’s clear that the proof of zkEVM needs to contain the following aspects corresponding to the execution process

• The bytecode is correctly loaded from persistent storage (You are running the correct opcode loaded from a given address)

• The opcodes in the bytecode are executed one by one consistently (They bytecode is executed in order without missing or skipping any opcode)

• Each opcode is executed correctly (Three sub-steps in each opcode are carried out correctly, R/W + computation)

Fox is building a zkRollup that is fully EVM compatible, for the convenience of Solidity contracts deployment. We will support direct validation of the Ethereum block with a concise validity proof approach called ZK-FOAKS.

The basic idea of ZK-FOAKS will be elaborated on below. It verifies the consistency and integrity of each opcode in the EVM execution trace, then sends the state proof and validity proof by Double-Deck Express, with the low-gas, high-secure Ringer contract to deal with the data availability. In this way, L1 smart contract can migrate seamlessly to Fox. Instead of using the new ZK-friendly primitives, we'll build reversely. We'll use custom optimizations to support native EVM. This gives us a huge advantage of being compatible with all existing Ethereum infrastructure without any modifications.

Given the EVM opcode compatibility, ZK-FOAKS is designed to verify state changes efficiently. It promises not only to be secure and efficient but also to accomplish competitive decentralization. In an effort to achieve high-speed proving and succinct proofs for quick verification, the Fox team is focused on the optimization of ZK-FOAKS.

The Fox network is permissionless, decentralized, secure, efficient, and comes with verifiable block data. Development efforts aim at permissionlessness, that is, allowing anyone to participate in the network. For instance, the consensus algorithm will give everyone the opportunity to be a Sequencer, an Aggregator, or a hardware accelerator.

Data availability is most crucial for decentralization, where every user has sufficient data needed to rebuild the full state of a rollup based on the decentralized storage that has got the best configuration for data availability. The aim is to ensure that there is no censorship and that no one party can control the network.

As an L2 solution, most of the Fox security is inherited from Ethereum. Smart contracts will warrant that anyone who executes state changes must do it correctly. ZK-FOAKS creates a proof that attests to the validity of a state change, and avails validity proofs on-chain for verification.

Fox Tech aims to improve scalability and performance in blockchains using ZK-FOAKS (Zero-Knowledge Fast Objective Argument of Knowledges) technology, providing cryptographic proofs that are zero-knowledge, no need for a trusted setup, quantum secure, and fully EVM-compatible.

Fox is building a ZK-EVM Rollups with a strong proof network, combining software and hardware to support fast and reliable generation and verification of computational integrity proofs for general computations, on which the universal dApps can easily be deployed and get their compatibilities.

Background

Along with the high gas and the slow problem of Ethereum, ZK-Rollup is recognized as the best scaling solution for Ethereum to fix it. It is as secure as Ethereum and has the shortest finalizing time compared to all other Layer 2 solutions such as State Channels and Plasma.

The basic idea of zk-Rollup is to aggregate a huge number of transactions into one Rollup block and generate a succinct proof for the block off-chain. Then the smart contract on Layer 1 only needs to verify the proof and apply the updated state directly without re-executing those transactions. This can help save the gas fee by an order of magnitude since proof verification is much cheaper than re-executing computations. Another saving comes from data compression, which only keeps minimum on-chain data for verification. In the Fox solution, we are able to save another 50% gas fee from Ring’s eternal on-chain data service.

Fox Tech uses Validity Proofs that present evidence that a state transition is correct. Validity Proofs reflect a more pessimistic view of the world. Blocks include values representing the L2 state only if that state is correct. A representation of some off-chain computation is sent to a smart contract. The smart contract updates the blockchain with this new value only after it is verified as correct. The main advantages of Validity Proofs are that the blockchain will always reflect a correct L2 state and that a new state can be immediately relied upon and used. The main disadvantage is that proofs are needed for each and every state transition, and not merely when such a transition is contested, and this impacts scalability. In the Fox solution, we use ZK-FOAKS to solve the scalability under Validity Proofs.

Although the validity proofs of ZK-Rollup are secure and efficient, the common applications are still limited to swaps and ERC-20 token transfers. It’s hard to build general-purpose DApps due to the following two reasons.

First, if projects want to develop DApps in a ZK-Rollup, they need to write all smart contract logic using a special and complicated language which requires extremely strong expertise in zero-knowledge proof. Second, different applications can’t interact with each other within the same zk-Rollup Layer 2, significantly undermining the composability of DeFi applications.

In a word, ZK-Rollup is developer-unfriendly and has limited functionality and composability for now without ZK-EVM. That’s the tricky problem we want to tackle. We want to provide the best developer experience and support composability within Layer 2 by supporting native EVM verification directly, so that existing Ethereum applications can simply migrate over onto the zk-Rollup. That is the reason why we are building the zkEVM.

ZK-Rollup is already more mature with regard to specialized applications but will travel a more gradual path with fully generalized smart contracts. Eventually, it will be possible to port any ZK-EVM-based smart contract to ZK Rollup. We estimate it will come true at the end of 2022 at the current pace of Fox's technological development.

ZK-EVM

To understand the role of zkEVM, we had better start with Ethereum, which is essentially a transaction-based state machine. In computer science, a state machine is a machine that transitions from an old state to a new state by reading a series of inputs. This state contains the status of all account addresses and their mappings.

The EVM, or Ethereum virtual machine, handles transactions. EVM runs as a stack machine in which programmers write code in high-level languages such as Solidity, which is then compiled into EVM bytecode that EVM can understand. The EVM performs standard stack operations as various EVM opcodes, eventually producing a new state.

Now here's the problem. We know that the ZK Rollup solution needs to generate zero-knowledge proofs for transactions on L2 and send them back to L1 for verification. To generate zero-knowledge proofs, transactions need to be processed in accordance with the ZK circuit proof specification. And when EVM was first designed a few years ago, the designers did not consider supporting zero-knowledge proofs. So we need zkEVM. Technically, zkEVM means a virtual machine running on a ZK Rollup network, EVM-compatible and zero-knowledge proof-friendly.

More and more, we see zkEVM as the key to scaling Ethereum increasingly. However, zkEVM is difficult to build. Despite years of intuition, no one has managed to build a native EVM circuit. Designing and implementing zkEVM is challenging for the following reasons:

• EVM has limited support for elliptic curves. Currently, EVM only supports BN254 pairing. It is difficult to prove recursion because cyclic elliptic curves are not directly supported. It is also difficult to use other proprietary protocols in this setting. The validation algorithm must be EVM-friendly.

• The EVM character length is 256 characters. EVM runs on 256-bit integers (much like most regular VMS run on 32-64 bit integers), while ZK turns out to work most "naturally" on prime fields. Doing "mismatched field arithmetic" inside the circuit requires proof of scope, which adds about 100 constraints to each EVM step. This requires 25600 bits, increasing the EVM circuit size by two orders of magnitude.

• EVM has a number of special opcodes. EVM differs from traditional VM in that it has many special opcodes, such as CALL, and error types related to execution context and gas. This brings new challenges to circuit design.

• EVM is a stack-based virtual machine. The SyncVM (zkSync) and Cairo (StarkWare) architectures define their IR/AIR in register-based models. They built a specialized compiler to compile the smart contract code into a new ZK-friendly IR. Their approach is language compatibility rather than native EVM compatibility. Fox zkEVM is a stack-based model and direct support for native toolchains which is also harder to prove.

• The Ethereum storage layout introduces significant overhead. Ethereum storage layouts are highly dependent on Keccak and huge MPT, both of which are not ZK-friendly and have huge proof overhead. For example, the Keccak hash is 1000 times larger than the Poseidon hash in the circuit. However, replacing Keccak with another hash can cause some compatibility issues with the existing Ethereum infrastructure.

• Machine-based proofs are significantly overhead. Even if you can handle all of the above, you still need to find an efficient way to put them together to get a complete EVM circuit. Even simple opcodes like ADD can cause overhead for the entire EVM circuit.

But why is zkEVM possible now? Thanks to the great progress made by researchers in this area, more and more efficiency problems have been solved in the last several years, and the proven cost of zkEVM is finally feasible! The biggest technological advances come from the following aspects:

• Use of polynomial commitments. Over the past few years, most compact zero-knowledge proof protocols have stuck with R1CS, encoding PCP queries in application-specific trusted Settings. Circuit sizes often explode, and can't do many custom optimizations because the degree of each constraint needs to be 2 (bilinear pairings only allow one multiplication in the exponent). With a polynomial commitment scheme, we can elevate the constraints to any degree with generic or even transparent Settings. This provides great flexibility in backend selection.

• Lookup table parameters and the appearance of custom widgets. Another powerful optimization comes from the use of lookup tables. Optimization was first proposed in Arya and then optimized in Plookup. This can save a lot on ZK unfriendly primitives (that is, bitwise operations like AND, XOR, etc.). Custom widgets allow us to be highly constrained efficiently. TurboPlonk and UltraPlonk define elegant program syntax to make it easier to use lookup tables and define custom widgets. This is very helpful in reducing the overhead of EVM circuits.

• The recursive proof is becoming more and more feasible. Recursive proofs have been costly in the past because they relied on special pair-friendly cyclic elliptic curves (i.e. constructions based on MNT curves). This introduces significant computational overhead. Yet more technology makes this possible without sacrificing efficiency. For example, Halo can avoid the need for pairwise curves and use special inner product parameters to amortize recursive costs. We can also do proof aggregation directly against existing protocols (lookup tables reduce the overhead of non-local field operations, thus making the validation circuit smaller). It can greatly improve the scalability of supported circuit sizes.

• Hardware acceleration makes proof more efficient. To the best of our knowledge, we build the fastest GPU and ASIC/FPGA accelerators for the prover. The GPU prover is about 5 to 10 times faster than the Filecoin implementation. This can greatly improve the efficiency of the prover's calculation.

There are two main implementation strategies for zkEVM.

• Direct support for existing EVM opcodes, fully compatible with the Solidity opcode set. The solution is used by Fox, Scroll, and the Ethereum foundation.

• Keep Solidity compatible by designing a new virtual machine that is zero proof of knowledge friendly and adaptable to EVM development tools. This scheme is mainly used for zkSync.

For the first strategy, because it fully supports the existing set of EVM opcodes and uses the same compiler as EVM, it is naturally fully compatible with existing ecosystems and development tools and better inherits Ethereum's security model.

The second strategy is not constrained by the original EVM opcode set, so it is more flexible to compile code into a more zero-knowledge proof-friendly opcode set. It also eliminates the heavy lifting required to be compatible with all the original EVM opcodes.

Overall, the first strategy is more compatible and secure, but requires more work; The second strategy is more flexible and requires less work, but requires additional adaptation effort. Fox chooses the first strategy as the best developer-friendly and highest security level solution.

Further, there are two ways to build a universal DApp in zkRollup.

The first and early one is to build dedicated circuits (" ASIC ") for different DApps. It requires developers to design specialized "ASIC" circuits for different DApps. This is the most traditional way to use zero-knowledge proofs. By customizing the circuit design, each DApp will have lower overhead. However, it introduces composability problems because circuits are "static" and the developer experience is poor due to the need for strong circuit design expertise.

This is a fatal problem at the early stage. So we choose the second way: to build a general  "EVM" circuit for smart contract execution. This approach does not require any special ZKP designer or developer expertise from the dApp side. The advanced idea of this machine-based proof is that any program will eventually run on the hardware, so we only need to build a universal CPU circuit to validate the low-level CPU steps. We can then use this CPU circuit to verify the execution of any program.