Exploring the Technological Developments Behind zkEVM: From Polynomial Commitment to Hardware Acceleration

Jan 09, 2023

Greetings

Happy new year subscribers. It's 2023 and it's the year of zk-rollups, which will see significant advancements in zero-knowledge technology. This week, we'll be exploring various aspects of zero-knowledge technology. Even beyond this week, this year my content will focus heavily on zk-tech, as it is the holy grail.

In a previous article, we examined the challenges facing zkEVM. In this article, we'll examine the technological developments that have made zkEVM possible. I'll try to simplify it as much as possible to make it easy to understand. Here are the four technological developments that have enabled the advancement of zkEVM:

1. Polynomial Commitment

In a zero-knowledge proof, polynomial commitment schemes are used to reflect the constraints of the proof in a flexible and effective way. When using zero-knowledge proof protocols, a prover must demonstrate to a verifier that they are aware of a specific piece of data (referred to as a "witness") without disclosing what that data is. This is often accomplished by constructing a mathematical argument, or "proof," that relies on the witness in some way, but does not directly reveal it.

One way to do this is to use a method called "R1CS with PCP query encoded in an application-specific trusted setup." (R1CS- Rank-1 Constraint System is a type of circuit that supports addition and multiplication only and PCP- Probabilistically Checkable Proof is a type of proof that can be quickly verified by a computer using a limited amount of randomness and by reading only a small part of the proof. Randomness here means the generation of numbers or data that lacks any discernible pattern).

The above involves constructing a circuit (a program used in zero-knowledge proof which involves limited expressions) that encodes the constraints of the proof, and then using a special type of query called a "PCP query" to check that the circuit is correct. However, one limitation of this approach is that the circuit size can become very large, making the proof inefficient. Additionally, it is only possible to use bilinear pairing (a specific type of mathematical operation that satisfies certain properties, such as bilinearity, non-degeneracy, and computability. These properties make it useful for constructing cryptographic protocols that have desirable security properties, such as resistance to attack) to encode the constraints, which limits the types of optimizations that can be used.

Polynomial commitment schemes allow for a more flexible and efficient way to represent the constraints of the proof. With a polynomial commitment scheme, it is possible to "lift" the constraints to any degree (that is, represent the constraints using polynomials of any degree). This allows for greater flexibility in the types of optimizations that can be used, and can also make the proof more efficient by reducing the circuit size. Additionally, polynomial commitment schemes can be used with either a "universal setup" or a "transparent setup," which refers to the way in which the scheme is implemented.

2. Lookup table arguments and customized gadgets

Lookup tables and customized gadgets are techniques that can be used to optimize the performance of certain types of computer programs. These techniques were originally proposed in the Arya and Plookup systems, and were later refined in TurboPlonk and UltraPlonk. Lookup tables can be particularly useful for optimizing programs that perform bitwise operations like AND, XOR, etc., and customized gadgets can be used to efficiently implement high degree constraints. Together, these techniques can help to reduce the overhead of the Ethereum Virtual Machine (EVM) circuit and make it more efficient.

Techniques like lookup tables and customized gadgets can be used to optimize zkEVM by reducing the size of the circuit and increasing the efficiency of certain types of operations. This can help to make zkEVM more practical and scalable.

3. Recursive Proof

Recursive proof is a method used to prove the correctness of a computation by breaking it down into smaller pieces and proving each piece independently. In zero-knowledge proof systems (zkps), this process can involve proving a proof, and multiple proofs can be aggregated into a single proof. In the past, pairing-friendly cyclic elliptic curves were used to support recursive proof, but these could be computationally expensive. However, newer methods have been developed that enable recursive proof with less computational effort. For example, Halo can use an inner product argument, a specific type of mathematical concept, to reduce the cost of recursion, while Aztec can use lookup tables to reduce the cost of non-native field operations and improve the efficiency of the verification process. These methods can increase the scalability of the method by making it more efficient.

In a future post, this will be explained further.

4. Hardware Accelerators

Hardware accelerators, such as ASICs (Application-Specific Integrated Circuits), GPUs (Graphics Processing Units), and FPGAs (Field-Programmable Gate Arrays), can help to improve the computation performance of provers in zero-knowledge proof systems. In the case of zero-knowledge proof systems, hardware accelerators can be used to speed up the process of generating and verifying proof constructions, which can be computationally intensive.