Introduction

In this pair of blog posts, we will review the Supersonic SNARK and attempt to demystify the technical details to a higher level description. The primary interesting contribution of the Supersonic SNARK is a new polynomial commitment scheme for any interactive oracle program (to be elaborated) which has the following notable properties:

• Possibility of no trusted setup
• In the case of trusted setup, the setup is universal (does not depend on the exact verifier circuit)
• Relatively fast and practical proof sizes. In particular, logarithmic verification time.

Given the lack of trusted setup, Supersonic is ideal for situations where a trusted setup is undesirable for assurance reasons, or if the verification circuit being compiled needs to be updated or changed sometimes.

Quick Stats

• Prover time: $O(n \log n)$ group exponentiations
• Proof size: $O(\log n)$ group elements
• Verifier time: $O(\log n)$ group exponentiations
• Reference string: $O(1)$ (the group parameters)
• Concrete measurements for 120 bit security level and $n=2^{20}$ size arithmetic circuit using the PLONK IOP:
  • Proof size: 10.1 KB
  • Verifier time: 72ms (assuming 10 microseconds per group operation)

Background

Classical computer science has shown that every language in NP has a Probabilistically Checkable Proof (PCP), where a computational resource-restricted verifier can quickly confirm membership in that language using only a few queries of a specially-constructed proof. Less formally, we can interpret this as "every true statement that has a reasonably sized proof, also has a reasonably sized proof whose correctness can be checked (with high probability) by only looking at a small number of locations of the proof."

This kind of "proof" radically revises the traditional notion of a mathematical proof. Traditional mathematical proofs, as most of us are taught in school, are "fragile": even a single incorrect or logically invalid step is enough to make the entire proof invalid. Not carefully checking every single step of a proof seemingly allows faulty "proofs" of false statements. However, PCPs show that not much has to be sacrificed: in exchange for allowing only a small probability of accepting a "proof" of a false statement, we can write robust proofs: ones whose correctness becomes almost certainly guaranteed by inspecting only a small random part.

In the cryptographic setting, SNARKs have been developed as a "succinct" version of a PCP, for a specific kind of statement: proof of knowledge. In a SNARK, a computationally-restricted prover can convince a computationally-restricted verifier that the prover knows a traditional proof of some true statement (formally, knows a witness for a member of a language in NP), using an extremely short "proof" (typically polylogarithmic in the original proof/witness, thus shrinking the traditional proof by a significant amount)

PCPs are typically constructed using local testing of low degree polynomials, and so are most SNARKs. Since low degree polynomials have good error correcting properties, only a few queries are needed to verify that the SNARK could only (plausibly) have been constructed by a prover with knowledge of a witness to the statement being proven. The connection between PCPs and low degree polynomials is incredibly subtle, but at its most abstract level, low degree polynomials are completely characterized by a small number of points; "knowing" the evaluations of a low degree polynomial at a few random points is enough to "know" the entire polynomial. This ultimately will allow the correctness of a PCP to be determined by "knowing" a small number of random parts of the PCP.

The authors of Supersonic observe that prior PCPs and SNARKs can be explained in terms of polynomial interactive oracle proofs (polynomial IOPs). In an IOP, we can think of the prover and verifier engaging in an interactive protocol where the prover sends "PCPs" (low degree polynomials) to the verifier, and the verifier makes evaluation queries of the low degree polynomials. Traditional PCPs are noninteractive, "single-round" IOPs. While it may seem counterintuitive to add interaction if our ultimate goal is a noninteractive proof, interactivity can improve efficiency of an IOP, and the interactivity can be cryptographically removed later with little penalty.

The NP-hard Quadratic Arithmetic Problem (QAP, used for the original SNARKS) can be viewed as a polynomial IOP. Other recent papers (e.g. Sonic, PLONK, Marlin) have given polynomial IOPs that are superior to QAP in efficiency; the use of additional rounds of interaction help significantly. Supersonic is a generic SNARK for any polynomial IOP, so it can use the polynomial IOPs given in Sonic to construct SNARKs.

Polynomial IOPs from NP hard Problems

Generally we are interested in computer programs that verify some fact. This is captured by the computational complexity class NP, which you may recall consists of all problems which have "proofs" of positive instances. More formally, a language \(L\) is in NP if there is a polynomial time verification program \(V(x,y)\) such that, $x \in L$ if and only if there exists a polynomial sized proof $y$ such that $V(x,y) = 1$ (that is, the verification program checks a proof $y$ that $x \in L$). Less formally, we can think of the verification program as checking the truth of some statement $x$ by considering a (space bounded) proof $y$ of the statement $x \in L$.

Expanding on this, we can think of this setup as a "prover" who knows some information, which we will call a "witness" (mathematically similar to a proof, but can be quite general) which demonstrates the truth of $x$, and a "verifier" who wants to become convinced of the truth of the statement $x$. Straightforwardly, the prover can directly reveal the witness $y$ to the verifier and the verifier can run the verification program $V(x,y)$ to check for themselves. If $V(x,y) = 1$, then the verifier becomes convinced of the truth of $x$.

The class NP contains most problems of cryptographic interest (for example, $x$ could be "given a public key $P$ and ciphertext $C$ encrypted with $P$, the 5th bit of the plaintext of $C$ is 1"; the verification program $V(x,y)$ could compute the encryption of $y$ with $P$, and compare it to $C$, and if it matches, then checks the 5th bit of $y$). More generally, the verification program might do more interesting computations, for example, verifying signatures, etc.

However, there are cases where it would be preferable for the prover to run the verification program themselves, and then "prove" to the verifier that the output of the verification program was 1. Particular reasons to do this might be if the verification program takes a long time to run, or if the witness $y$ is very long or contains sensitive information.

The idea of SNARKs is that a prover can compute the verification program on some inputs $x,y$, and produce a succinct argument that the prover knows a $y$ that causes $V(x,y) = 1$ (thus proving both that $x$ is a true statement, and that the prover actually knows such a witness proof $y$; the former implies the latter, but not necessarily the other way around). The idea is to use ideas from probabilistically checkable proofs to shrink the size of the witness, and for the prover to evaluate $V(x,y)$ for the verifier in a way that does not reveal any bits of $y$ to the verifier (zero knowledge).

We would like an arbitrary verification program to be evaluated; so if we can build a SNARK for any NP-hard problem, then we can encode any polynomial time verification program into the SNARK (by reductions). While the exact NP-hard problem is not theoretically important, for efficiency reasons an arbitrary verifier computation should be efficiently reducible to the NP-hard problem, and a witness for the verifier should be encodable in a finite field to allow PCP testing.

Therefore, generally the high-level approach taken by many modern SNARKs is to take an NP-hard problem of satisfiability of an arithmetic circuit over a finite field, which can then be converted into a polynomial IOP of evaluations of low-degree polynomials. Supersonic does not directly do any of these steps; rather, it uses the existing constructions from Sonic, PLONK, and Marlin of these polynomial IOPs. To some extent, arithmetic circuits can efficiently encode interesting computations (at least, in cases when verifiers can be optimized to have small arithmetic circuit representations) and arithmetic circuit satisfiability is efficiently reducible to polynomial IOPs.

One might ask the question: why allow interactivity if our ultimate goal (SNARKs) are by definition non-interactive? Interactivity is a powerful tool which allows a polynomial IOP to be significantly more efficient than a single non-interactive PCP of the same statement. Since, in some sense, interactivity allows the verifier to "challenge" the prover directly, it is more difficult for a fraudulent prover to prove false statements. For example, fewer queries might be necessary in a polynomial IOP than a similar PCP. Note that when discussing polynomial IOPs and PCPs by themselves, there is no cryptographic construction; even an unbounded complexity prover cannot cheat the verifier. The Fiat-Shamir heuristic will later simulate the verifier's public coins anyway, so this extra interaction does not harm the ultimate SNARK at all, except for the weakening to computational soundness (a computationally bounded prover cannot cheat the verifier).

Polynomial Commitment Schemes

PCPs, and more generally polynomial IOPs, have the nice property that only a few evaluations of some polynomials are sufficient to determine the truth of the statement to be proven. However, there is now a stumbling point: either the prover must send the entire polynomials to the verifier (resulting in long proofs, which is an undesirable property for SNARKs) or the prover must somehow perform the verifiers evaluations. SNARKs use cryptographic methods to only send short commitments of polynomials, instead of the whole polynomials. While this comes at the expense of now relying on cryptographic assumptions, this reduces the communication between the prover and verifier substantially.

The Supersonic SNARK introduces a new, efficient polynomial commitment scheme for existing polynomial IOPs such as Sonic, PLONK, or Marlin, with possibility of a universal trusted setup or no trusted setup. The next post in this series will demystify the Supersonic polynomial commitment scheme.

Written by Joseph Bebel, zero-knowledge cryptography researcher & protocol developer at Metastate.

Image credits: Porcupine by Ever Widening Circles.

Metastate has ceased its activities on the 31st of January 2021. The team members have joined a new company and working on a new project. If you're interested in zero-knowledge cryptography and cutting-edge cryptographic protocols engineering positions in Rust, check out the open positions at Heliax.

If you have any feedback or questions on this article, please do not hesitate to contact us: hello@heliax.dev.