SuperSpartan

• Protocol Explanation: Description of features and optimization techniques.

• Conclusion (Final Remarks): Benchmarks, results, or open problems.

• References: A bullet point list of reference links

• Acknowledgements:

Introduction

The SuperSpartan paper introduces customizable constraint systems (CCS), a generalization of R1CS that can simultaneously capture R1CS, Plonkish, and AIR without incurring overhead. Unlike existing formulations of Plonkish and AIR, CCS is not tied to any specific proof system. The paper shows that the linear-time polynomial IOP for R1CS from Spartan extends naturally to CCS, and that combining this with a polynomial commitment scheme yields a family of SNARKs for CCS, referred to as SuperSpartan.

SuperSpartan supports high-degree constraints without imposing cryptographic costs that scale with constraint degree; only the underlying field operations scale with degree. As in Spartan, it does not rely on superlinear-time or hard-to-distribute operations such as FFTs. While HyperPlonk (EUROCRYPT 2023) achieves similar properties for Plonkish through a different technique, the authors observe that it remains unclear how to prove CCS instances—or even R1CS instances—using HyperPlonk or Plonk itself without overhead.

In contrast, SuperSpartan can prove uniform CCS instances, including AIR, without requiring linear-time preprocessing for the verifier and offers “free” addition gates in those settings. SuperSpartan applied to AIR yields the first SNARK for AIR that features a linear-time prover, transparent and sublinear-time preprocessing, polylogarithmic proof sizes, and plausible post-quantum security. Notably, SuperSpartan provides a faster prover than existing transparent SNARKs for AIR, often referred to as STARKs.

Background

1. Multilinear Extensions

2. CCS

3. Sumcheck

4. SNARK

5. PCS

6. Polynomial IOP

Protocol Explanation

Polynomial IOP for CCS

This section describes SuperSpartan’s polynomial IOP for CCS. It is a straightforward generalization of polynomial IOP for R1CS in Spartan. As per definition of CCS, suppose we are given a CCS structure-instance tuple with size bounds:

$$((m, n, l, t, q, d), (\bm{M}_0, . . . , \bm{M}_t−1, \bm{s}_0, . . . , \bm{s}_{q−1}), \bm{x}).$$

For simplicity, we describe our protocol assuming m and n are powers of two (if this is not the case, we can pad each matrix $\bm{M}_{i}$ and the witness vector $\bm{z}$ with zeros to extend $m$ and $n$ to a power of 2 without increasing the prover or verifier’s time in the SNARKs resulting from the protocol below).

Interpret the matrices $\bm{M}_0, . . . , \bm{M}_t−1$ as functions mapping domain $\{0, 1\}^{\log m} \times\{0, 1\}^{\log n}$ to $\mathbb{F}$ in the natural way. That is, an input in $\{0, 1\}^{\log m} \times \{0, 1\}^{\log n}$ is interpreted as the binary representation of an index $(i, j) \in \{0, 1, . . . , m − 1\} \times \{0, 1, . . . , n − 1\}$, and the function outputs the $(i, j)$'th entry of the matrix.