Research Summary: REDSHIFT: Transparent SNARKs from List Polynominal Commitment IOPs

The mechanism to understand what’s new in quantum-secure blockchain

TLDR:

• Ethereum blockchain transactions are slow and expensive, Zero-Knowledge Proofs (ZPK) with a layer 2 solution could provide efficient verification for these transactions (meaning faster speeds) without compromising security.
• This paper describes REDSHIFT, a ZKP system based on a new Interactive Oracle Proof (IOP) primitive called list polynomial commitment, and a transparent SNARK algorithm.
• The system could solve one of the biggest problems with zero-knowledge smart contracts: it does away with application-specific trusted setups and creates a generalized system that allows developers to build on top of REDSHIFT without needing a trusted-parameter generation ceremony, and also support for smart contract.
• REDSHIFT improved from PLONK change the Kate commitment to FRI commitment to achieve plausibly quantum-resistant zk-SANRKs cryptography.
• REDSHIFT has garnered considerable interest, as this scheme does not require a trusted setup, nor does it rely on novel mathematical properties. Beyond quantum resistance, this ZPK algorithm may offer better efficiency and lower complexity than alternatives.
• The following is a simple table to show the similarities and differences between the REDSHIFT and PLONK algorithms, as follows:

Differences between RedShift and Plonk

Source

Citation

• Kattis, A., Panarin, K., & Vlasov, A. (2019). RedShift: Transparent SNARKs from List Polynomial Commitment IOPs. IACR Cryptol. ePrint Arch., 2019, 1400.
• In addition to the paper reference above, this summary also uses translated information from the following blog post to make the understanding of RedShift more accessible:
• 小白(2021)。REDSHIFT：不需要可信设置的PLONK。知乎https://zhuanlan.zhihu.com/p/355820474
• Quadratic Arithmetic Programs: from Zero to Hero | by Vitalik Buterin | Medium

Link

• https://eprint.iacr.org/2019/1400.pdf 5

Core Research Question

• In a PLONK algorithm, how do we ensure that the value provided by the prover is indeed the value of the polynomial at a certain point, rather than a value deliberately chosen to ensure that the verification passes?

Background

• PLONK is a zero-knowledge-proof scheme. Its name stands for “Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge”.

1. Legacy PLONK schemes require a trusted setup procedure similar to that needed for the SNARKs in Zcash; a “universal and updateable” trusted setup. This means there is one single trusted setup for the whole scheme after which you can use the scheme with any program.
2. There is a way for multiple parties to participate in the trusted setup such that it is secure as long as at least one of them is honest, and this multi-party procedure is fully sequential: first one person participates, then the second, then the third. The full set of participants does not even need to be known ahead of time. New participants could just add themselves to the end. This makes it easy for the trusted setup to have a large number of participants, making it quite safe in practice.

• Polynomial commitment: PLONK uses “Kate commitments”, based on a trusted setup and elliptic curve pairings, but you can instead swap them out with other schemes, such as FRI (which would turn PLONK into a kind of STARK) or DARK (based on hidden-order groups). This means the scheme is theoretically compatible with any (achievable) tradeoff between proof size and security assumptions.

1. The “fancy cryptography” it relies on is one single standardized component, called a “polynomial commitment”

Source: Vitalik Buterin. “Understanding PLONK“

This figure showcases the tradeoffs between proof size and security assumptions, STARKs are feasible post-quantum secure schemes and have a fully trustless setup, but have high computational overhead. PLONK has a minimal trusted setup, so the proof size of PLONK is smaller than SNARKs.

• Arithmetization: The first step of the zero-knowledge proof algorithm is Arithmetization, which converts the problem to be proved by the prover into the form of a polynomial equation. If the polynomial equation is true, it means that the original problem relationship is true. It is relatively simple to prove whether a polynomial equation relationship is true. According to the Schwartz-Zippel theorem, it can be inferred that two polynomials with the highest order of n have at most n points of intersection.
• Quadratic Arithmetic Programs: The first step of the zero-knowledge proof algorithm is Arithmetization, which converts the problem to be proved by the prover into the form of a polynomial equation. If the polynomial equation is true, it means that the original problem relationship is true. It is relatively simple to prove whether a polynomial equation relationship is true. According to the Schwartz-Zippel theorem, it can be inferred that two polynomials with the highest order of n have at most n points of intersection.
• zk-SNARKs Common reference:

1. Common Reference String (CRS) is both prover and verifier have access to the same string CRS taken from some existing distribution.
2. Universal Common Reference String (universal CRS) allows a single setup to support all circuits of some bounded size.
3. Updatable CRS/SRS allows an open and dynamic set of participants can contribute secret randomness to it indefinitely. Although this is still a trusted setup in some sense, it increases confidence in the security of the parameters as only one previous contributor must have destroyed their secret randomness in order for the SRS to be secure.

• Transparent zk-SNARK Constructions: A new approach to the above problem relies on creating a universal SRS at the preprocessing phase, which can then be used in tandem with any possible predicate (or circuit). This schemes relies on two main ingredients:

1. encoding the circuit satisfaction problem of the predicate in question as a property of some (lowdegree) polynomial f.
2. committing to f using a polynomial commitment scheme.

• Sonic: Universal, updatable, scheme that carries a small set of global parameters. Proof sizes are small (256 bytes) and verifier time is competitive with the fastest zk-SNARKs in the literature. It is especially well-suited to systems where the same zk-SNARK is run by many different services and verified by many different parties. This is exactly the situation for many blockchain systems.
• Polynomial Commitment Schemes: A polynomial commitment scheme that is both transparent and efficiently computable would yield transparent SNARK constructions that have the potential to satisfy all of the requirements of a fully succinct, transparent and plausibly quantum-resistant zk-SNARK.

Summary

• This paper is a ZKP algorithm called REDSHIFT that does not require Trusted Setup and does not rely on complex mathematical primitives. At the same time, it is quantum-resistant and offers better efficiency (STARK’s proof is too large) and lower complexity.
• There are certain questions about the above method, such as “How to ensure that the value provided by the prover is indeed the value of the polynomial at a certain point, rather than a value that you deliberately select to ensure that the verification passes. This value is not calculated by the polynomial?” This problem is guaranteed by the KCA algorithm in the classic SNARK algorithm. For the specific principle, please refer to V God’s zk-snarks series. In the PLONK algorithm, the concept of polynomial commitment (Polynomial Commitment) is introduced. The specific principle can be mentioned in “PLONK — Protocol for Zero-Knowledge Proof Algorithm”.

Method

• In the PLONK algorithm, in order to make the verifier believe that the polynomial equation is true, the prover randomly selects a point. Then, the prover provides the commitment of various polynomials (including setup poly, constraint ploy, and witness poly), due to the Kate commitment algorithm used. This requires a trusted setup and relies on the discrete logarithm problem. Therefore, as a sub-protocol in the PLONK algorithm, the PLONK algorithm naturally also requires a trusted setup and relies on the discrete logarithm problem.
• The following will introduce the protocol part of the REDSHIFT algorithm in detail. As mentioned earlier, this algorithm has great similarities with the PLONK algorithm below:

1. Setup

Fix FRI parameters and degree d for FRI games (that is, the degree of all quotient polynomials). The prover is given an explicit representation of all constraint polynomials and the verifier is given oracle access to them alongside the “distinguishing” point z (which in general is different for each constraint polynomial). The verifier is given P I(x) — the public inputs polynomial and the honest prover is additionally given fL,fR,fO, the witness-wire polynomials. All commitments mean FRI-commitments in this section.

2. Protocol

3. Prover chooses masking polynomials

h1(x), h2(x), h3(x) ∈ F<k[x.] where the choice of

k will be described later. Prover defines new witness

polynomials f1(x) = fL(x) + h1(x)Z(x), f2(x) =

fR(x) + h2(x)Z(x), f3(x) = fO(x) + h3(x)Z(x).

4. Prover sends commitments to polynomials f1, f2, f3 to the verifier.

5. Verifier chooses random β, γ ∈ F and sends them to the prover.

6. Verifier sends random a1, . . . , a6 ∈ F to Prover.

7. Define the following polynomials:

a) F1(x) = L1(x)(P (x) − 1)

b) F2 (x) = L1 (x)(Q(x) − 1)

c) F3(x) = P (x)p′(x) − P (xg)

d) F4(x) = Q(x)q′(x) − Q(xg)

e) F5(x) = Ln(x)(P (xg) − Q(xg))

f) F6(x) = qL(x) · fL(x) + qR(x) · fR(x) + qO(x) · fO(x) + qM(x) · fL(x) · fR(x) + (qC(x) + PI(x))

Later, they show that for honest provers all of {Fi(x)} are identically zero on domain H∗ . This means that all of {Fi(x)} are divisible by Z(x) in the ring F, hence so is their linear combination F(x) = P6 i=1 aiFi(x). Prover computes T(x) = F (x) Z(x) and sends the verifier a commitment to T(x).

Results

• After fully constructing Redshift and provisioning proofs, the researchers provide a concrete example of how all the parameters of the system can be instantiated and used for performance benchmarks.
• For realistic benchmarking, the authors instantiate RedShift with q = r · 2¹⁹² + 1, r = 576460752303423505 which is a Proth prime, and use ρ = 1/16.
• Oracles were instantiated as Merkle trees using the Blake2s hashing algorithm. The setup phase was performed using the approach from Section VIII, where a random point was sampled using Fiat-Shamir heuristics by placing all individual root hashes of oracles to the setup polynomials into the transcript. For comparison, they also implemented the PLONK prover using Kate commitments and used two curves: BN254 and BLS12–381 that are expected to provide ∼80 bits and ∼120 bits of security levels respectively.
• With these parameters, the authors benchmark Redshift proof sizes across different levels of target security, with a practical emphasis on 80-bit security.

• Different settings are tested to evaluate Redshift’s proof generation times (in seconds) relative to two competing schemes, namely PLONK BN254 and PLONK BLS12–381:

Discussion and Key Takeaways

• This work provides a solution to one of the biggest blockers for implementing zero-knowledge smart contracts; the lack of generalizable zk proof systems with sufficient efficiency and recursive composition.
• This is a major development since previous approaches to zkSNARKs, notably groth16, required application-specific trusted setups. Prior to this work, every new application that used zkSNARKs beyond simple asset transfers was required to perform a trusted setup ceremony in order to be safe.
• Redshift provides a universal approach to zkSNARKs as it enables any arbitrary program to be converted to probable zk circuits. As a result, developers can build syntax-rich programming languages and full-fledged applications atop Redshift without needing to perform a trusted parameter-generation ceremony.
• Additionally, Redshift is plausibly post-quantum secure since it relies exclusively on collision-resistant hash functions, which are standardized and well-understood.

Implications and Follow-Ups

• The set of trade-offs employed by Redshift carries a wide range of implications when it comes to existing approaches to smart contract privacy, execution, and scalability.
• The lack of feature richness in existing approaches to zkRollups has pushed industry researchers to pursue alternative scalability solutions, such as Optimistic Rollups, which replicate instances of the Ethereum Virtual Machine (EVM) off-chain, with regular timestamps on-chain.
• If proved successful, the advent of Redshift may lead to considerable design changes in the rollups field as the trade-offs between scalability, practicality and feature-richness continue to be explored.

Applicability

• Redshift is the zk proof system used in zkSync, an emerging approach to the development and implementation of feature-rich zkRollups.
• By using Redshift, zkSync can provide 10-minute economic finality of zkRollup transactions, which is considerably quicker than the current 1 to 2-week finality threshold that exists in Optimistic Rollups schemes. The succinctness of the system enables gas costs per transaction to be capped 0.5k gas.
• Zinc is the first general-purpose programming language built using Redshift. Both its syntax and semantics were borrowed from the Rust programming language. Through the reuse of proof circuits, Zinc smart contracts can be built to preserve the privacy of their users.