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


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

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



  • 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。知乎
  • Quadratic Arithmetic Programs: from Zero to Hero | by Vitalik Buterin | Medium


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?


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


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


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


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


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

@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? @Jerry_Ho and @cipherix - I’d love to get your opinions on this thread.


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?


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?

Yeah, they’re definitely complementary in some ways. The biggest advantage of Redshift-based applications, such as zkSync, is that you still get the benefits of Plonk, such as the ability to reuse the zk circuit for different applications, without needing a trusted setup. The zkSync team is pursuing broader applications of this technology by enabling users to develop their own Dapps using the Zinc programming language, whereas other zkRollup solutions are focusing predominantly on the P2P exchange use case.


Continuing the discussion from Research Summary: REDSHIFT: Transparent SNARKs from List Polynominal Commitment IOPs:

One of the RedShift biggest contribution is that RedShift don’t need the trusted setup to compute the prover and verifier parameter at the beginning. This part is a security issue for zk-SNARKs because quantum computer may have the chance it figure it out before the transaction competete.

Ethereum community has suggested that using BLS signature aggregation as a pragmatic medium-term solution to the signature verification bottleneck of sharding and Casper, later replacing it with STARK-based aggregation for quantum security. Pragmatic signature aggregation with BLS

RedShift is improved from PlonK, but it is quantum resistance and support for smart contracts for zk-SNARKs transactions. PlonK is not quantum resistant because of the pre-processed parameters. I think the RedShift is one of the future development of the quantum resistance algorithm. It’s better to have more discussion between zk-STARK and zk-SNARK-based quantum resistance algorithm.


Great observations here!

I’m particularly interested in the quantum resistance argument here. @Larry_Bates did a research summary back in March exploring quantum resistance of Bitcoin. That suggested that some of the concerns about quantum attacks need to be thoroughly examined using realistic attacker parameters (at least that was my big takeaway).

Is there a similar mindset that we should be adopting for Ethereum, Plonk, Redshift, etc?


I have a slightly broad question about engineering shops like the one that created REDSHIFT – how does the business model work? Would they license the technology or is it an open-source project that anyone can use?


It’s a really great question!
I think Post-Quantum Security of the Bitcoin Backbone and Quantum Multi-Solution Bernoulli Search mentions that k-BerSearch problem and Chain-of-PoWs are very different to zk-SANRK and Redshift. The two of the quantum resistance methods are trying to prevent the parameter to be decipher during the computing/generation block.


It’s the key question. RedShift would support for smart contract and quantum resistance, which means it may become the world safest and privacy place to secure your fund. For example, the project can create NFTs platform without reveal your transactions of owners and its open-source.