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

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 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.

  • The algorithm is most similar to PLONK, the only difference being that their polynomial scheme primitives are different.

  • 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:

    Algorithm Name Arithmetization Proven QAP Feature
    PLONK Statement → Circuit → QAP Kate commitment General CRS
    REDSHIFT Statement → Circuit → QAP FRI commitment No Trusted Setup

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

Link

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”

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.

  • Sonic: Sonic is a 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.

  • 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.

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.

  1. Protocol

  2. 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).

  1. Prover sends commitments to polynomials f1, f2, f3 to the verifier.
  2. Verifier chooses random β, γ ∈ F and sends them to the prover.

  1. Verifier sends random a1, . . . , a6 ∈ F to Prover.
  2. 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^192 + 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.
5 Likes

@Sean1992076 thank you so much for a really thorough and exciting contribution. I’m hoping you or someone else can help me put this into context a little bit. How does this fit into Ethereum’s plans for the future? I understand there are a couple of major updates on the horizon, where would something like this fit in? And what are the tradeoffs?

4 Likes

I’m also interested in what @jmcgirk is asking here. In particular, I’m interested in the implication:

Redshift isn’t the only ZKP solution, so I’m curious about its competitive advantages. There is another paper (PlonK paper) where @Jerry_Ho and @cipherix are also starting to discuss a different ZKP solution. It seems like there should be some strong parallelism between these two threads.

Or maybe I’m misunderstanding and these two solutions don’t really have to “battle it out” so much as they could be simultaneously implemented into an Ethereum future?

3 Likes