header-langage
简体中文
English
Tiếng Việt
Scan to Download the APP
Partnered With:

a16z: Measure SNARK performance with three elements

Read this article in 17 Minutes
The verification cost of SNARKs may vary, but the results are usually very good.
Original title: "a16z: Measuring SNARK performance with three elements"
Original source: a16z
Original author: Justin Thaler
Original compilation: Katie Gu, Odaily Planet Daily


SNARK (Succinct Non-Interactive Argument of Knowledge) is an important cryptographic primitive for Discover applications of blockchain scalability (e.g. L2 Rollup) and privacy. SNARKs allow someone to prove to an untrusted validator V (such as the Ethereum blockchain) that they know some data (such as a batch of valid transactions). An easy way to prove this is to send data to V, which can then directly check its validity. SNARKs achieve the same effect, but at a higher cost to V. In particular the SNARK proof should be shorter than the original proof containing the data itself.


Verification costs for SNARKs may vary, but the results are generally good. For example, PlonK's proof costs about 290,000 gas to verify on Ethereum, while  StarkWare  's proof costs about 5 million gas. SNARKs may be suitable for a variety of different settings outside of blockchains, for example, allowing the use of fast but trustless servers and hardware.


But since SNARK verification is usually cheap, the main determinant of applicability is the cost of the SNARK prover P. This article explains how to estimate these costs to determine when to use SNARKs wisely, and how to improve SNARKs in the future. It is worth noting that this is a rapidly developing field, and several projects discussed in this article are actively improving its performance.


How are SNARKs deployed?


In a SNARK deployment, the developer typically writes a computer program that takes as input the data w that the prover claims to know (w stands for the verifier), and checks that w is it effective. For example, in Rollup, the program will check whether all transactions in w are digitally signed, whether they cause any account balance to fall below zero, etc. The program is then fed through the SNARK front end, which compiles the program into a format more suitable for the application of SNARK technology. This SNARK-friendly format is called an intermediate code (IR).


In general, IR is some kind of circuit satisfiability instance equivalent to . This means that the circuit C takes as input the data w, and some additional input, often called a "non-deterministic proposal", and operates on w. These suggested inputs are used to help C run while keeping C small. For example, whenever two numbers x and y are divided, the quotient q and remainder r can be provided as advice to C, and C can simply check that x = qy + r. This check is cheaper than having C run the division algorithm to compute q and r from scratch.


Finally, apply satisfiability circuit SNARKs to C. This is called a SNARK backend. For some highly structured problems, such as matrix multiplication, convolution, and some graph problems, known SNARKs can avoid this front-end/back-end paradigm, resulting in faster proofs. But the focus of this article is on general SNARKs.


As we will see, the SNARK backend verification cost grows with the size of C. Keeping C as small as possible is a challenge because circuits are an extremely limited computational format. They consist of doors, connected by wires. Feed some values to each gate g and apply a very simple function to these values. The result is then fed into a "downstream" gate via a wire from g.


How long will SNARKs be scalable?


The key question is how long does a SNARK prover take versus simply re-executing it on the data? The answer is SNARK's verifier, as opposed to direct verifier checks. The latter expression refers to the fact that in the original proof that P sends w to V, V checks the validity of w by executing w on w.


It is beneficial to divide prover overhead into "front-end overhead" and "back-end overhead". If computing the circuit C gate-by-gate costs F times as much as running , then we call the front-end overhead F. If applying the backend verifier to C costs B times as much as evaluating C gate-by-gate, then we call the backend overhead B. The total verifier overhead is F times B. Even if F and B are individually small, this multiplication can be expensive.


In fact, both F and B can be 1000 or greater. This means that the total overhead of the proof procedure relative to direct verifier checking could be anywhere from 1 million to 10 million or more. A program that runs for one second on a laptop can easily result in tens or hundreds of days of computation time (single-threaded) for a SNARK verifier. Fortunately, this work is usually parallelized to varying degrees (depending on the SNARK).


In short, if you want to use SNARKs in today's applications, one of the following three conditions must be met:


1. It takes less than a second to check the verifier directly on the laptop.

2. Direct verifier checks are particularly well suited to in-circuit, so there is very little front-end overhead.

3. You are willing to wait days for the SNARK verifier to complete and/or pay for huge parallel computing resources.


The rest of this article explains where the frontend and backend overhead comes from, and how I estimate it for different SNARKs. and prospects for future improvement.


Distinguish front-end and back-end


Because different back-ends support different types of circuits, So it's a challenge to completely separate the front end from the back end. Therefore, frontends can vary depending on the backends they expect to interact with.

SNARK backends usually support so-called arithmetic circuits, meaning that the inputs to the circuit are elements of some finite field, and the gates of the circuit perform addition and multiplication of elements of the two fields. These circuits roughly correspond to straight-line computer programs (no branches, conditional statements, etc.), which are algebraic in nature, that is, their primitive data types are field elements.


Most backends actually support most of the arithmetic circuitry, often called Rank-1 Constraint Satisfaction (R1CS) instances. Besides Groth16 and its predecessors, these SNARKs can also be used to support other IRs. For example, StarkWare uses something called Algebraic Intermediate Representation (AIR), which is similar to the PlonKish arithmetic operations supported by PlonK and other backends. The ability for some backends to support more generic IRs can reduce the overhead of the frontends producing those IRs.


Backends also vary in the limited fields they support natively. I will discuss this further in the next section.


Multiple approaches to the front end


Some (very specific) computer programs naturally correspond to Arithmetic circuits. An example is a computer program that performs simple multiplication of matrices over a field. But most computer programs are neither straight lines nor algebraic. They usually involve conditional statements, operations such as integer division or floating-point operations that have an unnatural counterpart to finite-field operations, and so on. In these cases, the front-end overhead will be considerable.


A popular front-end approach is to generate basic circuits stepping through some simple CPU, also known as a virtual machine (VM). Front-end designers specify a set of basic operations, similar to the assembly instructions of an actual computer processor. Developers who want to use the front end either write "validator checkers" directly in assembly language, or write "validator checkers" in a high-level language like Solidity, and let their programs automatically compile to assembly code.


For example, StarkWare's Cairo is a very limited assembly language with assembly instructions that roughly allow addition and multiplication over finite fields, function calls, and Reads and writes to immutable (i.e. write-once) memory. The Cairo VM is a von Neumann architecture, meaning that the circuits produced by the front end essentially take the Cairo program as public input and run that program in front of witnesses. The Cairo language is Turing complete - despite its limited instruction set, it can emulate more standard architectures, although doing so can be expensive. The Cairo frontend converts a Cairo program that executes T primitive instructions into a so-called "level 2 AIR, T lines, about 50 columns". It doesn't really matter what that means, but in terms of SNARK proofs, it's equivalent to a circuit with 50 to 100 gates for each T-step of the Cairo CPU.


RISC Zero takes a similar approach to Cairo, but its virtual machine is the so-called RISC-V architecture, an open source architecture with rich Software ecosystems are becoming more and more popular. Being a very simple instruction set, designing an efficient SNARK front end that supports it is probably relatively tractable (at least relative to complex architectures like x86 or ARM). As of May, RISC Zero is converting programs that execute raw RISC-V instructions into a Level 5 AIR with 3 rows and 160 columns. This corresponds to a circuit with at least 500 gates per step on a RISC-V CPU. Further improvements are expected in the near future.


Various zkEVM projects (eg, zkSync  2.0, Scroll, Polygo's zkEVM) use the virtual machine as the Ethereum Virtual Machine. The process of converting each EVM instruction into an equivalent "gadget" (i.e., an optimized circuit that implements the instruction) is much more complex than the simple Cairo and RISC-V architectures. For various reasons, some zkEVM projects do not directly implement the EVM instruction set, but compile high-level Solidity programs into other assembly languages before turning them into circuits. Performance results for these items have yet to be determined.


Programs like RISC-V and Cairo's "CPU Simulator" produce a single circuit that can handle all programs in the associated assembly language. Another approach is something like an ASIC chip, producing different circuits for different programs. This ASIC-like approach can result in smaller circuits for some programs, especially when the assembly instructions the program executes at each time step do not depend on the program's inputs. For example, it can potentially avoid the front-end overhead of straight-line programs (such as initial matrix multiplication) entirely. But the ASIC's approach also seems to be very limited / as far as I know, how to use it to support loops with no predetermined iteration bounds.


The final component of front-end overhead comes from the fact that all SNARKs use circuits that operate over finite fields. The CPU on your laptop can multiply or add two integers with a single machine instruction. If the field characteristics of the front-end output circuit are large enough, it can essentially simulate multiplication or addition with corresponding field operations. However, implementing field operations on a real CPU typically requires many machine instructions (although some modern processors do have native support for some fields).


Some SNARK backends support more flexible field selection than others. For example, if the backend uses encryption group G, the fields of the circuit must match the number of elements in G, which may be finite. Also, not all domains support practical FFT algorithms.


There is only one implementation of SNARK—Brakedown, which supports calculation of arbitrary (large enough) fields locally. Besides its next generation, it has the fastest known concrete verification performance on other SNARK-supported fields, but currently its proofs are too large for many blockchain applications. Recent work has attempted to improve the size of the proofs, but the provers are slow and there seems to be a barrier to practicality.


Some projects choose to work in areas where computing is particularly fast. For example, Plonky2 and other algorithms use a feature domain of 264 - 232 + 1 because the implementation of algorithms for this domain is several times faster than for unstructured domains. However, using such small features can lead to challenges in efficiently representing integer arithmetic through field operations. (For example, multiplying a 32-bit unsigned integer by any number greater than 232 may produce a result larger than the field's characteristics. Therefore, field selection naturally only supports arithmetic on 32-bit numbers.)


But in any case, for all the popular SNARKs today, to achieve 128-bit security (without significantly increasing the verification cost), they must work on domains larger than 2128. As far as I can tell, this means that each field operation will require at least 10 64-bit machine multiplications, and quite a few additions and bit operations. Therefore, at least an order of magnitude of front-end overhead should be considered due to the need for circuits operating over finite fields.


In summary, existing front-ends using virtual machine abstraction produce circuits of 100 to 1000 gates at each step of the virtual machine, for more complex virtual machines May generate more. On top of that, finite-field arithmetic is at least 10 times slower than similar instructions on modern processors (with possible exceptions if the processor has built-in support for certain fields). An "ASIC chip front-end approach" might reduce some of this overhead, but is currently limited to the types of programs it can support.


What is the back-end bottleneck?


SNARKs for satisfiability circuits are usually achieved by combining an information-theoretical security protocol called "polynomial IOP" and a "polynomial commitment scheme" Cryptographic protocol to design. In most cases, the specific bottleneck of the prover is the polynomial commitment scheme. In particular, these SNARKs cause the prover to cryptographically submit one or more polynomials of degree (at least) |C|, the number of gates in circuit C.


Accordingly, the exact bottleneck in a polynomial commitment scheme will depend on the scheme and circuit size used. But always one of three operations: compute FFT, exponentiation in encrypted group, or Merkle hash. Merkle hashing is usually only a bottleneck if the circuit is small, so we won't discuss it further.


Polynomial commitment based on discrete logarithm


Based on the password group G (KZG, BulletProof , Dory and Hyrax commit), the prover must compute the Pedersen vector commitment of the polynomial coefficients. This involves multiple exponentiations whose magnitude is equal to the degree of the polynomial. In SNARKs, this degree is usually the size |C| of circuit C.


Simply put, multiple exponentiations of size |C| require about 1.5·124400·|C| group operations, where 124G|- represents group G The number of elements in . However, there is a method called Pippenger's algorithm that reduces this by about log|C|. For large circuits (e.g. |C|225), this logarithmic |C| factor can be specifically 25 or larger, that is, for large circuits we expect that the Pedersen vector combination can be achieved by slightly more than 10 124C124 group operations to calculate. In turn, each set of operations tends to be around 10 times slower than finite-field operations (as a very rough field). SNARKs using these polynomial commitments are as expensive for P as about 100 |C| field operations.


But existing SNARKs have additional overhead besides the 100x multiplier. For example:


Spartan's proof uses Hyrax polynomial commitments, which must be powers of |C|½, each of size |C|½, weakening Pippenger's The speedup of the algorithm is about 2 times.


In Groth16, P has to work on pair-friendly groups, and its operations are usually at least two times slower than on non-pair-friendly groups. P also has to be raised to powers of 3 instead of 1. Combined, this results in at least an additional 6x slowdown relative to the 100 |C| estimated above.


Marlin    and PlonK also require pairings, and their provers commit much more polynomials than 3.


For any SNARK that uses bullet proofs (such as Halo2, which is roughly PlonK but uses bullet proofs instead of KZG polynomial commitments), the prover must be in The "start" phase of the commitment scheme computes logarithmic powers, which largely eliminates any Pippenger speedup.


In summary, known SNARKs use Pedersen vector promises with back-end overheads of at least 200x and up to 1000x or more.


Other polynomial commitments


For using other polynomial commitments (such as FRI and liigero -commit ), the bottleneck lies in the fact that the proof program needs to perform a large FFT. For example, in the 2-level AIR produced by Cairo (with 51 columns and T rows, Cairo CPU has 1 row per step), the verification program implemented by StarkWare performs at least 2 FFTs per column, and the length is between 16 T and 32 T between. The constants 16 and 32 depend on the FRI internal parameters set by StarkWare and can be reduced at the cost of increased verification costs.


Optimistically, a length 32 FFT requires approximately 64 T log(32T) field multiplications. This means that even if the value of T is relatively small (such as T220), the number of field operations per column is at least 64 25 T = 1600 T. So the backend overhead seems to be at least thousands. Also, the bottleneck for large FFTs may be memory bandwidth, not field operations.


In some contexts, the back-end overhead of performing SNARKs for large FFTs can be mitigated by a technique called proof aggregation. For Rollup, this means that P  (the Rollup service) breaks down a large batch of transactions into 10 smaller batches. For each mini-batch i, P generates a SNARK proving the batch validity of i. But P does not publish these proofs to Ethereum, because this would increase the gas cost by nearly 10 times. Instead, the SNARK is applied again, this time producing a proof that P knows 1, 10. That is, the witnesses P claims to know are the ten proofs 1, ..., 10, and direct witness verification applies the SNARK verification procedure to each proof. This simple proof is published to Ethereum.


In polynomial commits (like FRI and liigero-commit) there is a strong tension between P time and V spent, and the internal parameter acts as a knob that can Make a trade-off between the two. Since 1,...,10 are not released to Ethereum, the knob can be adjusted, so these proofs are large, and it is faster to produce them. Only in the final application of SNARK can 1 and 10 be aggregated into a single proof, and a commitment scheme needs to be configured to ensure small proofs.


StarkWare plans to deploy evidence aggregation immediately. This is also the focus of projects like Plonky2.


What are the other bottlenecks for SNARK scalability?


This article focuses on verification time, but other verification costs can also be scalability bottlenecks. For example, for many SNARK backends, the prover needs to store multiple field elements for each gate in C, and this space overhead can be prohibitive. A program that runs for one second on a laptop can perform a billion raw operations on a modern processor. In general, C requires more than 100 gates to perform such an operation. That means 100 billion gates, which depending on the SNARK could mean tens or hundreds of terabytes of space for P.


Another example is that many popular SNARKs (e.g., PlonK, Marlin, Groth16) require a complex "trusted setup ceremony" to generate a structured The "proof key", which must be stored by the prover. As far as I know, the largest such ceremony produced a proof key capable of supporting a circuit, approximately 228.25 billion gates. The proof key is tens of GB in size.


In environments that demonstrate a high probability of aggregation, these bottlenecks can be appropriately broken through.


Looking Ahead: Prospects for More Scalable SNARKs


Frontend and Backend Overhead All could be three orders of magnitude or more. Can we expect these numbers to drop significantly in the near future?


In a way, I think we will. First, today's fastest backends (such as Spartan and Brakedown and other SNARKs that combine checksum protocols and polynomial commitments) have large proof sizes - usually the square root of the circuit size, so people don't really use them. I expect a significant reduction in verification size and verification time in the near future through deep-synthesis and small verification hurdles. Similar to proof aggregation, this means that the prover will first generate a SNARK proof using the fast prover, big prover SNARK, but will not send to V. Instead, P will use a small proof SNARK to generate a proof that it knows, and send it to V. This can greatly reduce the backend overhead of the currently popular  SNARK .


Secondly, hardware acceleration can help. A very simple rule is that a GPU can buy 10x faster than a CPU, and an ASIC can buy 10x faster than a GPU.


However, I have three concerns. First, the bottleneck of large FFTs may be memory bandwidth, not field operations, so SNARKs performing such FFTs may have limited acceleration on specialized hardware. Second, while this paper focuses on the polynomial commitment bottleneck, many SNARKs require the prover to do other operations that are only marginally less expensive than the polynomial commitment bottleneck. Thus, breaking the polynomial commitment bottleneck (e.g. speeding up multiple powers in discrete log based SNARKs) may leave a new bottleneck operation that is not much better than the old one. (For example, SNARKs including Groth16, Marlin, and PlonK have verification procedures for FFT in addition to multiple powers.) Finally, the fields and elliptic curves that lead to the most efficient SNARKs may continue to evolve for some time, which may give ASIC-based Acceleration of verification poses challenges.


On the front end, we may increasingly find that the "CPU emulator" approach of projects like Cairo, RISC Zero, zkEVM can actually be very good scales (in terms of performance) the complexity of the CPU instruction set. In fact, this is what the various zkEVM projects hope for. This could mean that, while the front-end overhead is still three orders of magnitude or more, the front-end can support virtual machines that increasingly match real CPU architectures. A counter-intuitive concern is that, as hand-coded gadgets proliferate with increasingly complex instructions, the front end could become complex and difficult to audit. Formal methods of verification are likely to play an important role in addressing this issue.


Finally, at least in blockchain applications, we may find that most non-mainstream smart contracts mainly use simple, SNARK-friendly instructions . This could in practice reduce front-end overhead while retaining the generality and improved developer experience that comes with support for high-level programming languages like Solidity and rich instruction sets including the EVM.


Original link


Welcome to join the official BlockBeats community:

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

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

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

举报 Correction/Report
Choose Library
Add Library
Cancel
Finish
Add Library
Visible to myself only
Public
Save
Correction/Report
Submit