Transparent SNARKs from List Polynomial Commitments

Understanding RedShift: Transparent SNARKs from List Polynomial Commitments

Introduction

Zero-knowledge proofs represent one of cryptography’s most powerful innovations, allowing one party to prove to another that a statement is true without revealing any additional information beyond the statement’s validity. Among these, SNARKs (Succinct Non-interactive Arguments of Knowledge) have gained popularity for their efficiency — they produce small proofs that can be verified quickly.

However, traditional SNARKs have a critical vulnerability: they require a “trusted setup” phase that generates parameters which, if compromised, could undermine the entire system’s security. This requirement directly contradicts the trustless philosophy that underpins many blockchain and cryptocurrency systems.

In this detailed exploration, I’ll break down the RedShift paper by Kattis, Panarin, and Vlasov, which introduces a breakthrough approach to creating transparent SNARKs — eliminating the need for trusted setups while maintaining reasonable efficiency in both proof size and verification time.

The Trust Problem in Traditional SNARKs: A Deeper Look

How Traditional SNARKs Work

Traditional SNARKs like Groth16 achieve remarkable efficiency with proofs consisting of just 3 group elements (approximately 1KB in size). Their verification is incredibly fast, making them ideal for blockchain applications where space and computation are at a premium.

However, they require a complex setup procedure that:

1. Generates a structured reference string (SRS)
2. Creates a proving key and a verification key
3. Produces “toxic waste” — secret parameters that must be destroyed

The Vulnerability Explained

Imagine Alice is creating a system that uses SNARKs to verify transactions privately. During setup, some random value (let’s call it ‘s’) is generated. The setup procedure creates public parameters from ‘s’, and then ‘s’ should be destroyed.

If an attacker Eve somehow learns ‘s’, she can:

• Create fake proofs that would verify as legitimate
• In a cryptocurrency context, she could potentially generate proofs claiming to own tokens she doesn’t have
• Compromise the entire system while leaving no evidence of the attack

Here’s the key innovation in simple terms:

1. Traditional PLONK: Uses “Kate commitments” based on elliptic curve cryptography, which require a trusted setup
2. RedShift: Replaces Kate commitments with a novel “List Polynomial Commitment” (LPC) scheme based on FRI, which requires no trusted setup

Traditional Mitigation: Multi-Party Computation (MPC)

To mitigate this risk, systems employ Multi-Party Computation ceremonies where multiple participants each contribute to generating the parameters. As long as at least one honest participant destroys their contribution, the setup remains secure.

For example, ZCash’s “Powers of Tau” ceremony involved dozens of participants across the globe, each adding randomness to the parameters and then supposedly destroying their contribution. However, this approach still requires trust in at least one participant’s honesty.

Key Mathematical Concepts Behind RedShift

Polynomial Commitments: The Foundation

To understand RedShift, we first need to grasp polynomial commitments. Let’s start with a simple example:

Imagine I have a polynomial :

A polynomial commitment scheme allows me to:

1. Commit to this polynomial (analogous to sealing it in an envelope)
2. Later open the commitment at specific points (e.g., prove that f(4)=57 without revealing the entire polynomial)

Simple Example:

• I commit to

• Later, I claim that f(4)=57
• I provide a proof that convinces you my claim is true
• You verify this proof without learning anything about ff f beyond the fact that f(4)=57

Kate Commitments: Efficient but Requiring Trust

Traditional SNARK systems like PLONK use Kate polynomial commitments. While efficient, these commitments require a trusted setup to generate parameters like:

Where g is a generator of an elliptic curve group, s is a secret value that must be destroyed, and dd d is the maximum degree of polynomials in the system.

Reed-Solomon Codes: Error Correction for Polynomials

Reed-Solomon codes are error-correcting codes used in technologies like QR codes, DVDs, and deep space communications. They work by encoding information as polynomials.

Simple Example: Let’s say we want to send a message [2,5,1] over a noisy channel:

1. We encode this as a polynomial :

2. We evaluate this polynomial at several points: f(1)=8,f(2)=16,f(3)=28,f(4)=46,f(5)=70,f(6)=100

3. We send these evaluations [8,16,28,46,70,100]

4. Even if some values are corrupted during transmission, the recipient can recover the original polynomial (and thus the message) as long as enough correct values are received

A Reed-Solomon code RS[F, D, ρ] consists of all functions f:D→F where there exists a polynomial of degree less than ρ∣D∣ that agrees with f on the domain D.

The Innovation: List Decoding and List Polynomial Commitments

RedShift introduces a new primitive called List Polynomial Commitments (LPC) that builds upon concepts from error correction and list decoding.

In traditional error correction, we try to find the single closest valid message to what we received. In list decoding, we find all possible valid messages within a certain distance of what we received.

Simplified Example:

• Instead of committing to exactly

• In LPC, we effectively commit to “a polynomial that agrees with

on at least 90% of points in some domain”

This seemingly small difference is the key to removing the trusted setup requirement.

Hamming Distance: Measuring “Closeness” of Functions

The Hamming distance between two functions is the fraction of inputs on which they disagree. For example, if functions f and g disagree on 10% of inputs in some domain, their Hamming distance is 0.1.

RedShift works with “neighborhoods” of polynomials that are close to each other in terms of Hamming distance, rather than exact polynomials.

FRI Protocol: The Efficient Verifier

FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) is a protocol that efficiently tests if a function is close to a low-degree polynomial without checking every point.

Analogy: Imagine you have a black box that contains either:

1. A polynomial of degree at most 10, or
2. A function that agrees with a degree-10 polynomial on at least 90% of inputs, but disagrees on some

FRI can determine which case you have by checking only ~20 strategically chosen points, instead of the millions of possible inputs.

The RedShift Protocol: A Step-by-Step Explanation

Let’s walk through how RedShift works, with our flowchart as a guide:

RedShift Protocol Workflow

1. Replace Kate Commitments with List Polynomial Commitments

Traditional PLONK uses Kate commitments for both “setup” polynomials (describing the circuit) and “witness” polynomials (containing private inputs). RedShift replaces these with LPCs that don’t require trusted setup.

2. Distinguish Between Setup and Witness Polynomials

RedShift recognizes that different polynomials need different treatment:

• Setup polynomials define the constraint system itself and must be handled exactly
• Witness polynomials encode the prover’s secret inputs and can use the more relaxed LPC approach

3. The Mathematical Core: PLONK with Transparent Components

The RedShift protocol builds on PLONK but replaces the commitment scheme. At a high level:

1. Commitment Phase: The prover commits to witness polynomials fL,fR,fO​ using LPC .These polynomials represent the left input, right input, and output wires of the circuit
2. Challenge Generation: Random challenges β,γ are generated using the Fiat-Shamir heuristic
3. Permutation Polynomials: The prover computes special polynomials P and Q that help verify the circuit’s “copy constraints” (ensuring values are copied correctly between different parts of the circuit)
4. Constraint Polynomials: The prover constructs constraint polynomials F1,…F6​ that encode:

• Gate constraints (operations performed by each gate)
• Copy constraints (wire connections between gates)
• Boundary constraints (public inputs and outputs)

5. Quotient Polynomial: The prover computes a quotient polynomial T such that:

Where Z(X) is a fixed polynomial that is zero on the evaluation domain

6. Verification: Multiple instances of FRI verify the polynomial commitments

4. A Simplified Example

Let’s consider a tiny circuit with just one constraint: a×b=c

1. The prover knows secret values a=3,b=4,c=12
2. These values are encoded in polynomials:

3. The constraint polynomial would check:

4. Instead of using Kate commitments for these polynomials, RedShift uses LPC + FRI to verify them transparently

Real-World Performance: The Numbers

RedShift achieves impressive performance for a transparent system:

• Proof Size: Approximately 515 KB for a circuit with one million gates (at 80-bit security level)
• Proof Generation Time: Around 30 seconds for the same circuit size
• Verification Time: 3–6 milliseconds for circuits up to one million gates

While the proof size is larger than trusted setups like Groth16 (~1KB), it’s competitive with other transparent systems and offers significant advantages in terms of trust elimination.

The Mathematical Security: Johnson Bound and List Decoding

The security of RedShift relies on the Johnson bound, which limits how many codewords can exist within a certain distance of any received word.

For every rate parameter ρ>0, the list size of polynomials within distance δ of any function is bounded by:

This bound helps determine how many FRI queries are needed to achieve a specific security level.

Practical Example:

• If we use a rate ρ=1/16 (meaning polynomials of degree n/16 where n is the domain size)
• And we want 80-bit security (probability of cheating ≤ 2^{-80})
• The Johnson bound tells us we need approximately 60 FRI queries

Advanced Optimizations in RedShift

RedShift includes several optimizations that improve its practical efficiency:

1. Batching FRI

Instead of running separate FRI instances for each polynomial, RedShift can batch them:

Example:

• Instead of verifying polynomials f1,f2,f3 separately
• RedShift can verify

for random coefficients αi.

• This works because a random linear combination of low-degree polynomials is low-degree with high probability

2. Merging Oracles in Merkle Trees

When committing to function evaluations using Merkle trees:

• Traditional approach: Put evaluations of each function in separate Merkle trees
• RedShift optimization: Combine evaluations of multiple functions in the same leaf of a Merkle tree
• This reduces the number of Merkle paths needed for verification, saving significant space

3. Bit-Reversed Domain Enumeration

A technical optimization that makes FRI “folding” more efficient:

• Values that need to be accessed together in FRI are placed adjacent in the Merkle tree
• This reduces the number of Merkle paths needed and improves verification time

Comparing Zero-Knowledge Proof Systems

Let’s compare RedShift to other zero-knowledge proof systems:

Comparison of Zero-Knowledge Proof Systems

Groth16

• Proof Size: ~1KB (smallest available)
• Setup: Requires trusted setup specific to each circuit
• Verification: Extremely fast
• Strengths: Smallest proofs and fastest verification
• Weaknesses: Requires trusted setup, not quantum-resistant

PLONK

• Proof Size: Larger than Groth16 but still relatively small
• Setup: Universal trusted setup (can be used for any circuit)
• Verification: Fast
• Strengths: Flexible circuit design, universal setup
• Weaknesses: Still requires trusted setup

Aurora/Fractal

• Proof Size: ~150KB
• Setup: Transparent (no trusted setup)
• Verification: Slower than Groth16/PLONK
• Strengths: Transparency, different arithmetization
• Weaknesses: Larger proofs

RedShift

• Proof Size: ~300KB (optimized)
• Setup: Transparent (no trusted setup)
• Verification: Comparable to PLONK
• Strengths: Transparency, potential quantum resistance
• Weaknesses: Larger proofs than trusted systems

STARKs

• Proof Size: Larger than other systems
• Setup: Transparent (no trusted setup)
• Verification: Relatively efficient
• Strengths: Quantum resistance, transparency
• Weaknesses: Largest proofs, optimized for layered circuits

Extensions and Future Directions

RedShift’s approach can be extended in several promising directions:

1. Binary Fields

While the paper focuses on prime fields, RedShift can be adapted to work with binary fields (powers of 2). This makes it suitable for computations that involve a lot of bit manipulations, which are common in cryptography and other areas.

Example Application: Verifying SHA-256 hash computations efficiently

2. Recursive Proving

RedShift’s verification can be expressed as arithmetic circuits, enabling recursive proof composition — proofs that verify other proofs. This is critical for scaling zero-knowledge applications.

Example: Proving that you have verified 1000 different proofs without revealing which ones, allowing for scalable verification of large systems

3. Application to Other Proof Systems

The LPC concept can be applied to other polynomial-based proof systems beyond PLONK, such as SONIC, Marlin, and others.

Conclusion: The Significance of RedShift

RedShift represents a significant breakthrough in zero-knowledge proof technology by achieving transparency without sacrificing much efficiency. By replacing trusted Kate commitments with innovative List Polynomial Commitments based on FRI, RedShift eliminates the need for trusted setups while maintaining competitive performance.

For applications where eliminating trust is paramount — such as cryptocurrency systems, privacy-preserving voting, or anonymous credentials — RedShift provides a compelling option that doesn’t force developers to choose between security, performance, and trustlessness.

As blockchain and privacy technologies continue to evolve, innovations like RedShift take us closer to the ideal of trustless verification — where security doesn’t depend on any single party but rests purely on mathematical foundations.

This article presents a simplified explanation of the RedShift paper. For complete technical details, refer to the original publication “RedShift: Transparent SNARKs from List Polynomial Commitments” by Kattis, Panarin, and Vlasov.