IOSG: Why are we optimistic about zero-knowledge proof hardware acceleration?

Original title: "IOSG Weekly Brief | Why we are optimistic about zero-knowledge proof hardware acceleration #150"

Original source: Bryan, IOSG Ventures

< /p>

This article will mainly discuss the development status of ZKP as an expansion solution, describe the main dimensions that need to be optimized in the process of generating proofs from the theoretical level, and introduce the acceleration requirements of different expansion solutions. Then focus on the hardware solution and look forward to Moore's Law in the field of zk hardware acceleration. Finally, some opportunities and status quo in the field of hardware zk acceleration will be elaborated at the end of the article. First of all, there are three main dimensions that affect the proof speed: the proof system, the scale of the circuit to be proved, and the algorithm hardware and software optimization.

For the proof system, any algorithm that uses elliptic curve (EC) is the mainstream Groth 16 (Zcash), Galo2 on the market (Scroll), Plonk(Aztec, Zksync) These zk-snark algorithms, the point multiplication of large numbers (MSM) involved in the process of generating polynomial commitments, currently have long time (high computing power requirements) bottlenecks. For FRI-based algorithms, such as ZK-Stark, the polynomial commitment generation method is Hash Function, which does not involve EC, so it does not involve MSM operations.

The proof system is the foundation, and the scale of the circuit to be proved is also one of the core hardware optimization requirements. ZKEVM, which has been hotly discussed recently, has different degrees of compatibility with Ethereum, resulting in different complexity of the circuit. For example, Zksync/Starkware has built a virtual machine different from the original Ethereum, thereby bypassing some of the original Ethereum. Using the underlying code processed by zk reduces the complex length of the circuit, and the circuit of zkevm, such as Scroll/Hermez, which is compatible from the bottom to the bottom, will naturally be more complex.

An easy-to-understand analogy is that the complexity of the circuit can be understood as the seats on a bus. For example, the number of passengers that needs to be carried on a normal day is 30 Below, some buses choose seats for 30 people, these buses are Zksync/StarkWare, and there are some days of the year that there are so many passengers that ordinary buses cannot fit, so some buses are designed with more seats (Scroll). But these days may be less, resulting in a lot of vacant seats in normal times.

Hardware acceleration is more urgent for these circuits with more complex circuit designs, but this is more of a Specturm thing, and it is also beneficial to ZKEVM. Different certification systems have different requirements and focuses for system optimization.

Basic:

When a thing to be proved is processed by a circuit (such as R1CS/QAP) After that, a set of scalars and vectors is obtained, which is then used to generate polynomials or other forms of algebraic forms such as inner product argument (groth16). This polynomial is still very verbose, and if the proof is generated directly, both the proof size and the verification are often very large. So we need to further simplify this polynomial. The optimization method here is called polynomial commitment, which can be understood as a special hash value of polynomials. Algebra-based polynomial commitments include KZG, IPA, and DARK, all of which use elliptic curves to generate commitments.

FRI uses Hash Function as the main way to generate promises. The choice of polynomial commitment is mainly around several points - security, performance. Security here is mainly considered in the set up phase. If the randomness used to generate the secret is public, such as FRI, then we say that the set up is transparent. If the randomness used to generate the secret is private and needs to be destroyed by the Prover after use, then this set up needs to be trusted. MPC is a means to solve the need for trust here, but it is found in practical applications that this requires users to bear a certain cost.

The FRI mentioned above, which is relatively excellent in terms of security, is not ideal in Performance. At the same time, although the Performance of Pairing-friendly elliptic curves is relatively excellent, but When considering adding recursion, there are not many suitable curves, so there is a considerable overhead.

Industry Status:

Current Whether it is based on Plonk (matterlabs) or Ultra-Plonk (Scroll, PSE), their final polynomial commitment is based on KZG, so most of Prover's work will involve a lot of FFT calculations (generating polynomials) and ECC point multiplication MSM operation (produces a polynomial commitment).

In pure plonk mode, since the number of points that need to be committed is small, the proportion of Prove time occupied by MSM operations is not high, so optimizing FFT performance can bring short-term benefits for greater performance improvement. However, under the UltraPlonk (halo2) framework, due to the introduction of the customer gate, the number of commit points designed in the prover stage increases, making the performance optimization of MSM operations very important. (At present, after the pippenger optimization of the MSM operation, log(P(logB)) is still required (B is the upper bound of exp, and p is the number of points participating in the MSM).

The polynomial commitment used by the new generation of Plonky2 proof system is no longer KZG but the common FRI in the STARK system, so that the prover of Plonky2 does not need to consider MSM, so theoretically, the performance improvement of the system no longer depends on MSM Relevant algorithm optimization. The author of plonky2, Mir (currently Polygon Zero), is vigorously promoting the system. However, because the number field Goldilocks Field used by plonky2 is not particularly friendly to programming elliptic-related hash algorithm-related circuits (such as ECDSA), so although Goldilocks Field has obvious advantages in machine word calculation, but it is still difficult to judge which is the better solution between Mir and PSE/Scroll.

Based on Plonk, Ultraplonk, Considering the comprehensive consideration of Plonky2's Prove algorithm, the modules that need hardware acceleration will most likely be concentrated in the three directions of FFT, MSM, and HASH.

Another bottleneck of Prover It is the generation of witnesses. Usually, ordinary non-zk calculations will omit a large number of intermediate variables, but in the process of ZK prove, all witnesses need to be recorded and will participate in the subsequent FFT calculations, so how to efficiently parallel witness calculations will also It is the direction that prover mining machines need to potentially consider.

Attempts to speed up ZKP: recursive proof - StarkNet's fractal L3 concept is based on the concept of recursive proof, Zksync's fractal Hyperscaling and Scroll have similar optimizations.

> The concept of Recursive zkSNARK is to prove the verification process of a Proof A, thereby generating another Proof B. As long as the Verifier If B can be accepted, it is equivalent to accepting A. Recursive SNARK can also aggregate multiple proofs, such as aggregating the verification process of A1 A2 A3 A4 into B; recursive SNARK can also split a long calculation process The solution is divided into several steps, and the calculation proof S1 of each step must be verified in the calculation proof of the next step, that is, one step of calculation, one step of verification, and the next step of calculation, so that the Verifier only needs to verify the last step and avoid constructing a The difficulty of large circuits of indefinite length.

Theoretically, all zkSNARKs support recursion. Some zkSNARK schemes can directly implement Verifier with circuits, while others need to split the Verifier algorithm into parts that are easy to circuit And the part that is not easy to be circuitized, the latter adopts the strategy of hysteresis aggregation verification, and puts the verification process in the last step of the verification process.

In the future application of L2, the advantages of recursion can further reduce the cost and performance requirements through the induction of things with proofs.

The first case (application-agnostic) is for different things to be proved, for example, one is state update and the other is Merkle Tree. The proofs that prove things can be combined into one proof, but there are still two output results (public keys for separate verification)

The second case (applicative recursion) It is for the same kind of things to be proved. For example, if both are state updates, then these two things can be aggregated before generating the proof, and there is only one output result, which is the state difference after two updates. (The method of Zksync is also similar, user cost is only responsible for state difference)

In addition to recursive proof and the hardware acceleration mainly discussed below, there are other accelerations The way of ZKP, such as custom gates, removing FFT (the theoretical basis of OlaVM), etc., but this article will not discuss it due to space reasons.

Hardware acceleration

Hardware acceleration has always been a common accelerated cipher in cryptography Whether it is for RSA (the underlying mathematical logic of RSA is similar to that of elliptic curves, and also involves many complex large number operations), or the early GPU-based optimization of zk-snark for zcash/filecoin Way.

Hardware selection

After The Merge of Ethereum, there will inevitably be a large number of GPU computing power redundancy (partially affected by the consensus change of Ethereum, GPU giant Nvidia’s share price has fallen by 50% since the beginning of the year, and inventory redundancy is also increasing). The following figure shows the transaction price of Nvidia’s flagship GPU product RTX 3090 , also shows that the buyer's power is relatively weak.

GPU prices are at a low point, and a large amount of GPU computing power On idle, a natural question is, is a GPU the right hardware to accelerate zk? There are three main options on the hardware side, GPU/FPGA/ASIC.

FPGA vs GPU: 

Look at the summary first: The following is trapdoor-tech’s summary of GPU (Nvidia 3090 as an example) and FPGA (Xilinx VU9P as an example) in several dimensions. A very important point is : GPU is higher than FPGA in terms of performance (speed of generating proofs), and FPGA has more advantages in energy consumption.

  A more intuitive specific running result from Ingoyama:  

Especially for operations with higher bit width (2^20), GPUs are five times faster than FPGAs while consuming significantly more power.

For ordinary miners, cost performance is also an important factor to measure which hardware to use. Both U55C ($4795) and VU9P ($8394) are much more expensive than GPUs (RTX 3090: $1860).

Theoretical level, GPU is suitable for parallel computing, FPGA pursues programmability, but in the environment of zero-knowledge proof generation, these advantages cannot be perfectly applied. For example, the parallel computing applicable to GPU is for large-scale graphics processing. Although it is logically similar to the processing method of MSM, the scope of application (floating number) is not consistent with the specific finite field targeted by zkp. For FPGA, the application scenario of programmability in multiple L2 is not clear, because considering that L2 miner rewards are linked to the demand undertaken by a single L2 (unlike pow), it may appear in subdivided tracks The situation of winner takes all makes it less likely that miners need to change algorithms frequently.

ASIC Yes In terms of performance and cost, we weigh the better solution (including throughput, delay, etc.), but whether it is the best solution is still inconclusive. The problem is:

Long development time - It needs to go through the process from complete chip design to chip production. Even if the chip has been designed, chip production is a lengthy, costly and variable yield process. In terms of foundry resources, TSMC and Samsung are the best chip foundries. At present, TSMC’s orders have been scheduled for two years. Competing with ZK chips for foundry resources are AI chips, electric vehicle chips and other web2 chips. Compared with the designed products that have been proven by demand, the demand for ZK chips is not clear.

Secondly, the performance of the whole chip is negatively correlated with the size of a single chip, that is, 20nm and 18nm as people often say, that is to say, a single chip The smaller the chip, the more chips the chip can hold, that is, the higher the performance of the whole chip, and the current technology for manufacturing high-end chips is monopolized (such as the most complicated part of chip manufacturing, lithography technology, is Monopolized by the ASML company in the Netherlands), for some small and medium-sized foundries (such as domestic SMIC), this technology is one or two generations behind the top, which means that it is behind the best in terms of yield rate and chip size. of the foundry. This will lead to some suboptimal solutions for ZK chips. Of course, based on cost considerations when the demand side is not so clear, choose non-high-end chips around 28nm.

Current ASIC solutions mainly deal with operators with relatively high computing power requirements in two common ZK circuits, FFT and MSM, and are not specific to specific It is designed for a project, so the efficiency of specific operation is not the highest in theory. For example, the logic circuit of Scroll's prover has not yet been fully realized, and naturally there is no hardware circuit that matches one by one. Moreover, ASIC is application-specific and does not support subsequent adjustments. When the logic circuit changes, for example, the client of the node needs to be upgraded, whether there is a solution that is also compatible is currently uncertain.

At the same time, the lack of talents is also an industry status quo of ZK chips. It is not easy to find talents who understand cryptography and hardware. Mathematical attainments and years of experience in hardware product design and maintenance.

Closing thoughts - prover development trend EigenDA

Above It is all the industry's thinking and attempt to accelerate ZKP, and the ultimate meaning is that the threshold for running prover will become lower and lower. Periodically speaking, the prover needs to go through roughly the following three stages:

Phase I: Cloud-based prover

Cloud-based prover can greatly increase the entry threshold for third-party prover (non-user/project party), similar to aws/google cloud of web2. In terms of business model, the project party will lose part of the rewards, but from the perspective of decentralized narrative, this is a way to attract more participants at the economic and executive levels. And cloud computing/cloud service is the existing technology stack of web2. There is already a mature development environment available for developers to use, and it can take advantage of the low threshold/high cluster effect unique to the cloud. It is an option for short-term proof outsource .

At present, Ingoyama also has an implementation in this regard (the latest F1 version even reaches twice the benchmark speed of pipeMSM). However, this is still a way for a single prover to run the entire proof, and in phase II, the proof can exist in a splittable form, and the number of participants will be larger.

Phase II: Prover marketplace

proof The generation process includes different operations, some operations have a preference for efficiency, and some operations have requirements for cost/energy consumption. For example, MSM calculation involves pre-computation, which requires a certain amount of memory to support different scalar particles on pre-computation, and if all scalars exist on a computer, the memory requirements for the computer are high, and if different scalars Stored on multiple servers, then not only the speed of this type of calculation increases, but also the number of participants.

Marketplace is a bold thinking on a business model for the above outsourced computing. But in fact, there are precedents in the Crypto circle - Chainlink's oracle service, the price feed of different trading pairs on different chains also exists in the form of a marketplace. At the same time, Howard Wu, the founder of Aleo, once co-authored DIZK, which is a zero-knowledge proof generation methodology for distributed ledgers, which is theoretically feasible.

Having said that, this is a very interesting thought in terms of business model, but it may be difficult to implement it in practice, such as this How to coordinate between class operations to generate a complete proof must not lag behind Phase I at least in terms of time and cost.

Phase III: Everyone runs prover

In the future, Prover will run locally on the user (web or mobile). For example, Zprize has competitions and rewards related to ZKP acceleration based on the webassembly/andriod execution environment, which means that the privacy of users will be guaranteed at a certain level (the current centralized prover It is just for expansion, and does not guarantee user privacy), and most importantly - privacy here is not limited to on-chain behaviors, but also off-chain behaviors.

An issue that must be considered is the security of the webpage. The execution environment of the webpage has higher prerequisites for security than hardware (an industry Witness is a web-side wallet like metmask, which is less secure than a hardware wallet).

In addition to the off-chain proof of on-chain data, the off-chain data is uploaded to the chain in the form of ZKP, and at the same time 100% protects user privacy. This Phase may be established. The current solutions inevitably face two problems - 1. Centralization, which means that user information is still at risk of being censored 2. The form of verifiable data is single. Because off-chain data forms are diverse and not standardized, verifiable data forms need to go through a lot of cleaning/screening, while still being in a single form.

The challenge here is not even just to prove the generated environment, whether it is compatible with the algorithm level (the transparent algorithm must be used first), and cost/time/efficiency All need to think about. But the same demand is also unparalleled. Imagine that real-life credit can be mortgaged in a decentralized way to lend and borrow on the chain without the risk of being censored.

Original link

a>

Telegram Subscription Group: https://t.me/theblockbeats

Telegram Discussion Group: https://t.me/BlockBeats_App

Official Twitter Account: https://twitter.com/BlockBeatsAsia