Cambrian cryptography proves a big explosion, how to choose dozens of zero-knowledge proof systems?

Written in front: Original author Professor Eli Ben-Sasson is the co-founder and chief scientist of StarkWare. In this article, he outlines nearly 20 zero-knowledge proof systems and gives his views on these proof systems. This article was also highly recommended by Zcash founder Zooko, "Mastering Bitcoin" author Andreas M. Antonopoulos, and others.

(Picture from: tuchong.com)

Note: The article was originally published on nakamoto.com. The content is more suitable for people with a cryptographic background. The following is a translation:

I. Introduction

3.5 billion years ago, life on Earth was still primitive single-celled organisms. Then, in a period known as the Cambrian life explosion, almost all animal species we know today appeared.

• Will Bitcoin be a harder asset than gold? About value, scarcity, and S2F
• Bitcoin Core developers: Bitcoin build time has decreased by 42% since its peak and has dropped to 135 seconds
• Dry Goods Sharing | How to Build a Professional Crypto Asset Portfolio

By analogy, we are currently experiencing the "Cambrian explosion" in the field of cryptographic proof (CI) of computational integrity, a subset of which includes zero-knowledge proofs . A few years ago, about 1-3 new zero-knowledge proof systems appeared in a year, but now it has been developed to every month (or sometimes weekly), and you can see an approximate number of new systems. . In 2019, we learned about new zero-knowledge proof structures, such as Libra , Sonic , SuperSonic , PLONK , SLONK , Halo , Marlin , Fractal , Spartan , Simple Aurora , and OpenZKP , Hodor, and GenSTARK implementations. Oh well, by the time this article was written, RedShift and AirAssembly had already appeared.

How to understand these wonderful innovations? The purpose of this article is to determine what all CI systems implemented in the code have in common and discuss some different factors.

Please note that this article will be a bit technical because it assumes the reader has some cryptographic background! However, it may also be worth a cursory glance for interested non-cryptographic readers, as you can learn some jargon used in this field.

Nonetheless, our description will be short and deliberately avoid mathematical stuff. Another main purpose of this article is to explain why our StarkWare company puts all the cores of science, engineering and products into a specific sub-family of the CI field. From now on, we will call them symmetric STARKs ( symmetric STARKs) .

Common ancestor

The computational integrity proof system helps to solve the two basic problems that plague decentralized blockchains: privacy and scalability . Zero-knowledge proof (ZKP) ^[1] provides privacy by masking certain inputs to calculations without compromising integrity. The simple and verifiable CI system provides expansibility by exponential compression to verify the amount of calculation required for the integrity of large-volume transactions.

All CI systems implemented in code have two things in common: they all use something called Arithmetization , and all passwords force a concept called "low-order compliance" (LDC) ^[2] .

Arithmetization refers to the reduction of computational statements through a proof algorithm. You can start with a conceptual statement like this:

"I know the keys that allow me to spend a shielded Zcash transaction"

It is then transformed into an algebraic statement containing a set of bounded polynomials, such as:

"" I know four polynomials A (X), B (X), C (X), D (X), each of degree less than 1,000, such that this equality holds: A (X) * B² (X) -C (X) = (X¹⁰⁰⁰–1) * D (X) ”” (I know the four polynomials A (X), B (X), C (X), D (X), each of which is less than 1000 , So this equation holds: A (X) * B² (X) -C (X) = (X¹⁰⁰⁰–1) * D (X))

Low-order compliance (LDC) refers to the use of cryptography to ensure that the provider actually selects low-order polynomials ^[3] , and evaluates these polynomials at random selection points requested by the verifier. In the example above (this article will continue to mention), a good LDC solution assures us that when asked about x₀, it will use the values ​​of a₀, b₀, c₀, d₀ to answer A on input x₀ , B, C, and D. The tricky part is that the provider may choose A, B, C, and D after seeing the query x₀, or it may decide to answer with any a₀, B₀, C₀, D 它们, and they will appease the verifier and compare with the preselected low No evaluation of order polynomials corresponds. Therefore, all cryptography is designed to prevent such attack vectors. (Requires the provider to send a complete simple solution of A, B, C, and D that provides neither scalability nor privacy.)

With this in mind, the CI universe can be drawn in three ways: (i) cryptographic primitives used to enforce LDC, (ii) specific LDC solutions built with these primitives, and (iii) what these options allow Arithmetization.

Dimensions of Comparison

Cryptographic assumptions

From a height of 30,000 feet, the biggest theoretical difference between different CI systems is whether their security requires symmetric or asymmetric cryptographic primitives (see Figure 1). Typical symmetric primitives are SHA2, Keccak (SHA3) or Blake. We assume they are collision-resistant hashing (CRH) functions. They are pseudo-random and behave like random oracles. Asymmetric assumptions include the difficulty of solving discrete logarithm problems of modular prime numbers, RSA modules, or elliptic curve groups, difficulty in calculating the size of RSA ring multiplication groups, and similarities to the "exponential knowledge" assumption and the "adaptive root" assumption Such a singular variant.

Figure 1: Cryptographic Hypothesis Family Tree

This symmetric / asymmetric partitioning between CI systems has many consequences, including:

A. Computing efficiency

The security of asymmetric cryptographic primitives implemented today in code ^[4] requires the operation and solution of LDC problems on large algebraic domains: large prime number domains and large elliptic curves above them, where each domain / group The elements are hundreds of bits long, or each element in an integer ring is thousands of bits long.

In contrast, a construction that relies only on the symmetric hypothesis performs arithmetic operations on any algebraic field (ring or finite field) containing a subgroup of smooth ^[5] and performs LDC, including a very small binary field and 2 smooth prime fields ( 64-bit or less), where arithmetic operations are fast.

Conclusion: The symmetric CI system can perform arithmetic operations on any field, thereby improving efficiency .

B. Post-quantum security

When a quantum computer with a sufficiently large state (measured in qubits) appears, all the asymmetric cryptographic primitives currently used in CI-verse will be effectively destroyed. On the other hand, symmetric cryptographic primitives seem to be post-quantum safe.

Conclusion: Only symmetric systems are reasonable post-quantum security systems .

Figure 2: Cryptographic assumptions and the economic value supported by them

C. Withstand the test

The Lindy effect theory proposes:

"Some things that are not perishable, such as a technology or an idea, have a life expectancy that is proportional to their current age."

Or in layman's terms, old things live longer than new ones. In the field of cryptography, this can be translated into the statement that relying on older, field-tested primitive systems is safer and easier than the newer assumptions that tires have been kicked less often Survive (see Figure 2). From this perspective, new variants of asymmetric cryptographic assumptions, such as knowledge of unknown order groups, general group models, and exponential assumptions, are compared to older assumptions (such as those used for digital signatures, identity-based encryption, and SSH initialization). More standard DLP and RSA assumptions) are younger. These assumptions are more resistant to future tests than symmetric assumptions (such as collision-resistant hashing algorithms), because the latter assumption (or even a specific hash function) is used to protect computers, networks, and the Internet. And e-commerce.

In addition, there is a strict mathematical hierarchy between these assumptions. The CRH hypothesis is dominated at this level, because if this assumption is broken (meaning no secure password hash function is found), then especially the RSA and DLP assumptions are also broken. The premise of these assumptions is that a OK CRH!

Similarly, the DLP hypothesis dominates the exponential knowledge (KoE) hypothesis, because if the former (DLP) hypothesis cannot hold, then the latter (KoE) cannot hold. Similarly, the RSA hypothesis dominates the unknown order group (GoUO) hypothesis, because if RSA is destroyed, then GoUO is also destroyed.

Conclusion: The new asymmetric cryptographic assumptions will be the basis for higher risk for financial infrastructure ;

D. Argument length

The above points are all conducive to a symmetric CI structure rather than an asymmetric CI structure. But in one aspect, asymmetric structures perform better. The communication complexity (or argument length) associated with it will be 1-3 orders of magnitude smaller (Nelson's Law ^[6] ). It is well known that Groth16 SNARK is less than 200 bytes in the estimated level of 128-bit security level, and all the symmetric structures that exist today require tens of KB to have the same security level. It should be noted that not all asymmetric structures are as concise as 200 bytes. The Groth16 architecture has been improved by (i) eliminating the need for trusted settings (transparency) and (ii) handling general-purpose circuits (Groth16 requires a trusted setting for each circuit). But these newer structures have longer parameters, with sizes ranging from half a KB (such as PLONK) to two-digit KB, close to the argument length of a symmetric structure.

Conclusion: The asymmetric circuit dedicated system (Groth16) is the shortest, it is shorter than all asymmetric universal systems and all symmetric systems .

Then reiterate the points above:

1. The symmetric CI system can perform arithmetic operations on any field, thereby improving efficiency;
2. Only symmetric systems are reasonable post-quantum security systems;
3. New asymmetric assumptions will be the basis for higher risk for financial infrastructure;
4. The asymmetric circuit dedicated system (Groth16) is the shortest, it is shorter than all asymmetric universal systems and all symmetric systems.

2.2 Low-level compliance (LDC) scheme

There are two main ways to achieve low-order compliance: (i) hidden queries, and (ii) commitment schemes (see Figure 3). Let's discuss the differences.

Figure 3: Hidden query & commitment scheme

Hiding Queries

This method is Zcash-style SNARKs, such as those used by Pinocchio, libSNARK, Groth16, and systems built on them, such as Zcash's Sapling, Ethereum's Zokrates, and so on. In order for the prover to answer correctly, we use homomorphic encryption to hide or encrypt x₀ and provide enough information so that the prover can calculate A, B, C, and D on x₀.

In fact, the prover is given an encrypted sequence of x₀ power (ie, encryption of x₀¹, x₀²,… x₀¹⁰⁰⁰), so that the provider can calculate any order of -1000 polynomials, but at most it can only calculate polynomials of order 1000. Roughly speaking, the system is safe because the provider does not know what x₀ is, and this x₀ is randomly (pre-selected), so if the provider tries to cheat, they are likely to be exposed. A credible preprocessing setup phase is needed here to sample x₀ and encrypt the above power sequence (and additional information) to obtain a proof key that is at least as large as the computing circuit being certified (and a shorter authentication key). key). Once the setup is complete and the key is released, each proof is a single, concise, non-interactive knowledge argument (SNARK for short). Please note that this system does require some form of interaction, in the form of a preprocessing stage, which is unavoidable for theoretical reasons. Please also note that the system is opaque, which means that the entropy used to sample and encrypt x₀ cannot be just a public random coin, because anyone who knows x₀ can destroy the system and prove its error. Therefore, encryption that generates x₀ and its power without exposing x₀ is a security issue that constitutes a potential single point of failure.

Commitment Scheme

This method requires the provider to submit a set of low-order polynomials (A, B, C, and D in the example above) by sending some cryptographically constructed commitment messages to the verifier. With this promise, verifier now samples the randomly selected x₀ and asks the prover, and now the prover uses a₀, b₀, c₀, and d₀, and additional password information that convinces verifier that the four values ​​revealed by the prove match the promise previously sent to verifier To answer.

This scheme is naturally interactive, and many schemes are transparent (all messages generated by the verifier are just open random coins). Transparency allows people to compress protocols into non-interactive protocols through Fiat-Shamir heuristics (it treats pseudo-random functions like SHA 2/3 as random oracles that provide "common" randomness), or use other randomness public Source (such as the block header). The most popular transparent commitment scheme is through the Merkle tree. This method seems to be post-quantum safe, but it will lead to a larger argument length in many symmetrical systems (because all authentication paths need to be revealed and attached to each prover's answer). This is the method used by most STARKs (such as libSTARK and succinct Aurora) and succinct proof systems (such as ZKBoo, Ligero, Aurora, and Fractal) (even if these systems do not meet STARK's formal definition of scalability).

In particular, the STARKs we build in StarkWare (such as the StarkDEX alpha and StarkExchange we are about to deploy) fall into this category. One can also use asymmetric cryptographic primitives to construct commitment schemes, such as the difficulty of discrete logarithm problems on elliptic curve groups (this is the method used by BulletProof and Halo) and unknown order hypothesis groups (such as those used by DARK and SuperSonic). ). The use of asymmetric commitment schemes has the aforementioned advantages and disadvantages: shorter proofs, but longer calculation times, susceptibility to quantum computing, newer (and less researched) assumptions, and in some cases, Loss of transparency.

2, 3 Arithmetization

The choice of cryptographic assumptions and LDC methods also affects the range of possibilities for arithmetization in three obvious ways (see Figure 4):

Figure 4: Arithmetization effect

A. NP (circuit) vs. NEXP (program)

Most implemented CI systems reduce the computational problem to an arithmetic circuit and then convert it to a set of constraints (generally the R1CS constraints we will discuss below). This method allows circuit-specific optimization, but requires verifier or some entity it trusts to perform calculations that are as large as the calculation (circuit) being verified. For multi-purpose circuits like Zcash's Sapling circuit, this algorithm is sufficient. However, for extensible and transparent (no trusted settings) systems being built by libSTARK, concise Aurora, and StarkWare, a concise computational representation must be used. This representation is similar to a general computer program and its description is better than Validated calculations are small exponential. Two existing implementations: (i) the algebraic intermediate representation (AIR) method used by libSTARK, genSTARK, and TaskWS systems, and (ii) the compact R1CS of the compact Aurora, best described as a general-purpose computer program (as opposed to a circuit) arithmetization. These concise representations are sufficient to capture the complex classes of non-deterministic exponential time (NEXP), which are more exponential and powerful than the non-deterministic polynomial time (NP) classes described by circuits.

B. Alphabet size and type

As mentioned above, the cryptographic assumptions used also largely determine which algebraic domains can be used as the alphabet for our arithmetic operations. For example, if we use bilinear pairing, the alphabet we will use for arithmetization is a cyclic group of elliptic curve points. This group must be a large prime number, which means we need to perform arithmetic operations on this domain. As another example, the SuperSonic system (in one of its versions) uses RSA integers, in which case Alphabet will be a large prime field. In contrast, when using Merkle trees, the size of Alphabet can be arbitrary, allowing arithmetic operations on any finite field. This includes the examples above, as well as arbitrary prime fields, extensions of small prime fields, such as binary fields. The field type is important because the smaller the field, the faster the proof and validation time.

C. R1CS vs. General Polynomial Constraints

Zcash-type SNARKs use bilinear pairings on elliptic curves to compute constraints. This special use of bilinear pairing ^[7] limits the gate operation of the quadratic rank 1 constraint system (R1CS). The simplicity and generality of R1CS has led many other systems to use this form of arithmetic for circuits, although more general forms of constraints such as arbitrary rank quadratic forms or higher order constraints can be used.

STARK vs. SNARK

Let's clarify the differences between STARKs and SNARKs. Both terms have specific mathematical definitions, and some structures can be instantiated as STARKs or SNARKs, or both. Different terms emphasize different properties of the proof system. Let's examine it in more detail (see Figure 5).

Figure 5: STARK vs. SNARK

STARK

Here S stands for scalability, which means that as the batch size n increases, it proves that the time size and n are in a quasi-linear relationship, and it is verified that the time size and n are in a multi-logarithmic relationship ^[8] .

T in STARK stands for transparency, which means that all verifier messages are public random coins (without trusted settings). According to this definition, if there are any preprocessing settings, it must be concise (multi-logarithmic) and must only include sampling public random coins.

SNARK

Here S stands for simplicity, which means that the verification time is logarithmic in n (no quasi-linear proof time is required), and N means non-interactive, which means that after the preprocessing stage (which may be non-transparent), The proof system cannot allow any further interaction. Note that according to this definition, a non-concise trusted setup phase is allowed. Generally speaking, the system does not need to be transparent, but it must be non-interactive (after the pre-processing phase, this is inevitable).

Looking at the CI-verse (see Figure 5), it is noticed that some of its members are STARKs, others are SNARKs, some are both, and others are not (for example, the verification time and n The relationship is worse than the multiple logarithm). If you are interested in privacy (ZKP) applications, then ZK-SNARKs and ZK-STARKs, even those (weak) simplicity systems that do not have STARK scalability and SNARK, will work well. For example, Bulletproofs used by Monero is a notable example in which the verification time is linearly related to the circuit size. And when it comes to code maturity, SNARKs have advantages because there are many good open source libraries to build on. However, if you are interested in scalability applications, then we would recommend using symmetric STARKs, because at the time of writing, they have the fastest proof time and guarantee that no part of the verification process (or building the system) needs to exceed Multi-logarithmic processing time. If you want to build a system with minimal trust assumptions, then again, you will want to use symmetric STARK, because the only components needed are some sources of CRH and common randomness.

Fourth, summary

Figure 6: Summary

We are fortunate to have experienced the amazing Cambrian explosion of the systemic integrity cryptography proof system universe, and we believe that the proliferation of systems and innovations will continue to proceed at an increasing rate.

In addition, with the emergence of new insights and structures in the future, the above attempts to describe the expansion and change of the CI universe are likely to become outdated. Having said that, looking at today's CI field, the biggest dividing line we see is (i) systems that require asymmetric cryptographic assumptions, which lead to shorter proof times, but higher proof costs, and they have newer Assume that these assumptions are susceptible to quantum computing, many of which are opaque, and (ii) systems that rely only on symmetric assumptions, which makes them computationally efficient, transparent, and possibly post-quantum safe, and According to the Lindy effect, they may also be the most future-proof.

The debate over which proof system to use is far from over, but from StarkWare's point of view, we would say that for short arguments, Groth16 / PLONK SNARKs can be used, and for other cases, symmetric STARKs can be used.

Author: Eli Ben-Sasson

Special thanks to Justin Drake for his comments on the draft article.

footnote

1. The term ZKP is often misused to refer to all CI systems, even some informal ZKP systems. To avoid this confusion, we use loosely defined terms "Cryptographic Proof" and "Computational Integrity (CI) Proof"; ↵

[[2]] You can read about STARK arithmeticization and low-order compliance here:

Arithmetization: blog [ 1 , 2 ], presentation slides and video presentations ; low-level compliance: blog posts (about STARKs);

2.

↵

The use of unary polynomials can be widely extended to multivariate polynomials and algebraic geometric codes, but for simplicity, we insist on using the simplest unary case;

3.

↵

We specifically exclude case-based constructs from the discussion because they have no code base yet. This structure is asymmetric and seems to be post-quantum safe, and usually uses small (prime) domains.

4.

↵

A domain is k-smooth if it contains a subgroup (multiplication or addition) and all its prime factors do not exceed k. For example, all binary fields are 2-smooth, so the q-1 field q-1 can be divided by the power of 2;

5. ↵

Nielsen ’s Internet Bandwidth Law states that user bandwidth will increase by 50% per year, which applies to data from 1983 to 2019;

6. ↵

Other systems (such as PLONK) only use pairings to obtain (polynomial) commitment schemes, not for arithmetic arithmetization. In this case, arithmeticization may lead to any lower order constraints;

7. ↵

Formally, "quasilinearity in n" means O (n logᴼ⁽¹⁾ n), and "multilogarithm in n" means logᴼ⁽¹⁾ n. [[8]]

We will continue to update Blocking; if you have any questions or suggestions, please contact us!