paper-Spartan efficient and general purpose zkSnarks without trusted setup.md

paper-Spartan efficient and general purpose zkSnarks without trusted setup.md

$$ \newcommand{\t}[1]{\widetilde{#1}} $$

paper-Spartan: efficient and general purpose zkSnarks without trusted setup

abstract

This paper introduces Spartan, a new family of zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) for the rank-1 constraint satisfiability (R1CS), an NP-complete language that generalizes arithmetic circuit satisfiability. A distinctive feature of Spartan is that it offers the first zkSNARKs without trusted setup (i.e., transparent zkSNARKs) for NP where verifying a proof incurs sub-linear costs—without requiring uniformity in the NP statement’s structure. Furthermore, Spartan offers zkSNARKs with a time-optimal prover, a property that has remained elusive for nearly all zkSNARKs in the literature.

evaluation

The goal is the following pipeline:

• R1CS encoding => low degree (degree 3) multilinear extension polynomial (thm 4.1) $Q$ to be proven via sumcheck: $$Q_{io}(t) = \sum_{x \in {0,1}^s} \widetilde{F}_{io}(x) \cdot \widetilde{e}q(t, x)$$
• section 5: Apply sumcheck to to obtain a (non-succinct NIZK) Prove the evaluations of $Q_{io}$ transform the above polynomial constraints to a set of constraints to be checked via via the sumcheck polynomial
• section 6: theoretically obtain a zkSNARK via a applying a polynomial commitment scheme to the prior NIZK
• section 7: design SPARK, a PCS designed to compile the sumcheck instance based on Hyrax

Jump forward to my section "understanding..." to speedrun this paper.

4 An encoding of R1CS instances as low-degree polynomials

main theorem: For any R1CS instance x = (F, A, B, C, io, m, n), there exists a degree-3 log m-variate polynomial G such that $\sum_{x \in {0,1}^{\log m}} G(x) = 0$ i.e. sumcheck is satisfied iff R1CS is satisfied.

Start with R1CS instance $x = (F, A, B, C, io, m, n)$. Let $s = \lceil\log m\rceil$. Matrices $A, B, C$ are viewed as functions: ${0,1}^s \times {0,1}^s \rightarrow \mathbb F$. Let $Z = (io, 1, w)$ viewed as function: ${0,1}^s \rightarrow \mathbb F$.

The function $F_{io}$ encoding R1CS constraints is:

$$F_{io}(x) = \left(\sum_{y \in {0,1}^s} A(x,y) \cdot Z(y)\right) \cdot \left(\sum_{y \in {0,1}^s} B(x,y) \cdot Z(y)\right) - \sum_{y \in {0,1}^s} C(x,y) \cdot Z(y)$$

This is just a statement of R1CS as a product of polynomials. The result is not a polynomial itself; amended by taking a polynomial extension $\tilde{F}_{io}: F^s \rightarrow F$:

$$\tilde{F}_{io}(x) = \left(\sum_{y \in {0,1}^s} \tilde{A}(x,y) \cdot \tilde{Z}(y)\right) \cdot \left(\sum_{y \in {0,1}^s} \tilde{B}(x,y) \cdot \tilde{Z}(y)\right) - \sum_{y \in {0,1}^s} \tilde{C}(x,y) \cdot \tilde{Z}(y)$$

This matches $F_{io}$ on boolean inputs and is a low-degree extension. Sidebar on extension, this just means that we need to blow up the range of $F$ to get nice properties about proving its correct evaluation, but that F is fundamentally the same poly over the previously described boolean hypercube.

Simply computing the sumcheck of $\t F$ over the hypercube, insufficient, and could allow a cheating prover to permute the values of $F$, exploiting cancellations. To that end we construct polynomial $Q_{io}$:

$$Q_{io}(t) = \sum_{x \in {0,1}^s} \tilde{F}_{io}(x) \cdot \tilde{eq}(t,x)$$

where recall the deg-1 ML poly outputs 1 if t=x:

$$\tilde{eq}(t,x) = \prod_{i=1}^s (t_i \cdot x_i + (1-t_i)\cdot(1-x_i))$$

$Q_{io}(t) = \tilde{F}{io}(t)$ for all $t \in {0,1}^s$, and $Q{io}$ is the zero polynomial if and only if $\tilde{F}{io}$ is zero on the boolean hypercube. Testing $Q{io}(\tau) = 0$ for random $\tau$ provides soundness (recall, that we needed to blow up F to $\t F$ to obtain this soundness; now we have it).

The final polynomial $G$ (defined largely for convenience) used in the theorem is:

$$G_{io,\tau}(x) = \tilde{F}_{io}(x) \cdot \tilde{eq}(\tau,x)$$

This polynomial is degree-3 in $s = \log m$ variables, its sum over the boolean hypercube equals $Q_{io}(\tau)$, and it is suitable for the sum-check protocol while preserving R1CS satisfiability with high probability.

C/S proofs follow from definitions of sumcheck, R1CS, and the schwarz zippel lemma.

5 A family of NIZKs with succinct proofs for R1CS

Main theorem: Given an extractable polynomial commitment scheme for multilinear polynomials, there exists a public-coin succinct interactive argument of knowledge (NIZK) with security under the commitment scheme's assumptions and $|\mathbb F|$ exponential in $\lambda$.

To verify R1CS instance $x = (F, A, B, C, io, m, n)$ is satisfiable, verifier $V$ checks if $\sum_{x \in {0,1}^s} G_{io,\tau}(x) = 0$. Using sumcheck reduces this to evaluating $G_{io,\tau}(r_x)$ at random point $r_x \in \mathbb F^s$.

Sidebar on verifier costs for sumcheck evaluation

To evaluate $G_{io,\tau}(r_x)$, verifier must compute:

1. $\tilde{eq}(\tau, r_x)$ - costs $O(\log m)$ operations in $\mathbb F$
2. $\tilde{F}_{io}(r_x)$ which requires:
   • Evaluating $\tilde{A}(r_x,y)$, $\tilde{B}(r_x,y)$, $\tilde{C}(r_x,y)$ for all $y \in {0,1}^s$
   • Each matrix evaluation costs $O(n)$ operations as matrices have $n$ non-zero entries
   • Total cost $O(n)$ operations in $\mathbb F$
3. Total verifier cost: $O(n + \log m)$ = $O(n)$ operations in $\mathbb F$

An $O(n)$ cost for the verifier fails to be succinct, and would render approach game-over, prior to the application of the PCS.

continued

Recall $G_{io,\tau}(x) = \tilde{F}{io}(x) \cdot \tilde{eq}(\tau, x)$, so $V$ needs $\tilde{F}{io}(r_x)$ and $\tilde{eq}(\tau, r_x)$. The latter is fast $O(\log m)$, but $\tilde{F}_{io}(r_x)$ expands as:

$$\tilde{F}_{io}(r_x) = \mathcal{A}(r_x) \cdot \mathcal{B}(r_x) - \mathcal{C}(r_x)$$

where: $$\mathcal{A}(r_x) = \sum_{y \in {0,1}^s} \tilde{A}(r_x,y) \cdot \tilde{Z}(y)$$ $$\mathcal{B}(r_x) = \sum_{y \in {0,1}^s} \tilde{B}(r_x,y) \cdot \tilde{Z}(y)$$ $$\mathcal{C}(r_x) = \sum_{y \in {0,1}^s} \tilde{C}(r_x,y) \cdot \tilde{Z}(y)$$

naive

Naively, the prover could make three separate claims to verifier $\mathcal{V}$ and run sumcheck 3 times:

1. $\mathcal{A}(r_x) = v_A$
2. $\mathcal{B}(r_x) = v_B$
3. $\mathcal{C}(r_x) = v_C$

Given these claimed values, $\mathcal{V}$ can evaluate:

$$G_{io,\tau}(r_x) = (v_A \cdot v_B - v_C) \cdot \tilde{eq}(r_x, \tau)$$

The verifier can compute $\tilde{eq}(r_x, \tau)$ efficiently in $O(\log m)$ operations, and the arithmetic to combine the claimed values costs $O(1)$. This transforms the $O(n)$ evaluation of $G_{io,\tau}(r_x)$ into the task of verifying three separate claims about polynomial evaluations.

Recall that $\tau$ is a random challenge point chosen by the verifier to test if $Q_{io}$ is the zero polynomial. The verifier must compute $\tilde{eq}(r_x, \tau)$, which is a degree-1 multilinear polynomial evaluation:

$$\tilde{eq}(r_x, \tau) = \prod_{i=1}^s (r_x[i] \cdot \tau[i] + (1-r_x[i])\cdot(1-\tau[i]))$$

This computation takes $O(\log m)$ operations in $\mathbb{F}$ since $s = \log m$ and each term in the product requires a constant number of field operations.

better: just one claim via linearization technique

Key insight: Prover claims values $(v_A, v_B, v_C)$ for these sums. $V$ combines them into single claim using random challenge values $r_A, r_B, r_C \in_R \mathbb F$:

$$r_A \cdot \mathcal{A}(r_x) + r_B \cdot \mathcal{B}(r_x) + r_C \cdot \mathcal{C}(r_x) \stackrel{?}{=} r_A v_A + r_B v_B + r_C v_C$$

This reduces to a more convenient second sumcheck instance over:

$$M_{r_x}(y) = r_A \cdot \tilde{A}(r_x,y) \cdot \tilde{Z}(y) + r_B \cdot \tilde{B}(r_x,y) \cdot \tilde{Z}(y) + r_C \cdot \tilde{C}(r_x,y) \cdot \tilde{Z}(y)$$

At end, $V$ needs $\tilde{Z}(r_y)$ for random challenge $r_y$. Verifier must still evaluate $M$ for the challenge $r_y$. The only term in $M$ that depends on the witness $w$ is $\t Z(r_y)$.

evaluating $\t Z$

We want to evaluate $\t Z$ without incurring $O(|W|)$ communication. To that end $P$ sends a commitment to $\t w(\cdot)$ to $V$ before the first sumcheck. $V$ evaluates $\t Z(r_y)$ by the closed form of multilinear poly evaluations:

$$\tilde{Z}(r_y) = (1-r_y[0]) \cdot \tilde{w}(r_y[1..]) + r_y[0] \cdot \widehat{(io,1)}(r_y[1..])$$

This means that the prover will commit to a poly $\t w$ that will be opened at $r_y$, in addition to the prior commitments.

Protocol makes black-box use of polynomial commitment scheme, inheriting its security properties. Adding zero-knowledge and Fiat-Shamir transform yields NIZK family.

The proofs follow from commitment scheme properties and sumcheck protocol soundness.

brief reminder: $\t Z$

$\tilde{Z}$ is the multilinear extension of $Z$, where $Z = (io, 1, w)$ combines the public inputs/outputs $(io)$, a constant $1$, and the witness $w$ into a single vector which is viewed as a function from ${0,1}^s \rightarrow \mathbb F$. That is, Z is the column of circuit private and public circuit inputs to the R1CS circuit.

understanding the protocol in section 5

Zooming in on the protocol described in detail now in a box in section 5:

• $\mathcal{P}$: $(C, S) \leftarrow \text{PC.Commit}(pp, \tilde{w})$ and send $C$ to $\mathcal{V}$
  • The prover uses the the public parameters to commit to the witness. We commit to the witness so as to be able to open the witness at a challenge point $r_y$ in step 11.
• $\mathcal{V}$: $\tau \in_R \mathbb{F}^{\log m}$ and send $\tau$ to $\mathcal{P}$
  • Verifier returns the challenge to $P$. This will be compiled to NI by Fiat Shamir.
• Let $T_1 = 0, \mu_1 = \log m, \ell_1 = 3$
  • Note the sumcheck parameters. $T_1=0$ is the claimed sum (we want polynomial to sum to 0), $\mu_1$ is dimension of the hypercube, $\ell_1=3$ is the degree bound from Section 4's polynomial encoding.
• $\mathcal{V}$: Sample $r_x \in_R \mathbb{F}^{\mu_1}$
  • verifier choses a random challenge value. To be fiat shamir'd.
• First sumcheck: $e_x \leftarrow \langle\mathcal{P}{SC}(G{io,\tau}), \mathcal{V}_{SC}(r_x)\rangle(\mu_1, \ell_1, T_1)$
  • recall: $$G_{io,\tau}(x) = \tilde{F}_{io}(x) \cdot \tilde{eq}(\tau,x)$$
  • prover computes sumcheck output $e_x$ claimed to equal $G_{io, \tau}(r_x)$. That is, the prover claims that the R1CS instance is satisfied. Verifier defers opening the sumcheck just yet, to avoid computing $G(r_x)$, a polynomial linear in the size of witness $w$. Note that opening $G$ is equivalent to opening some component polynomials, which we now do, in after a compressing linearization step.
• $\mathcal{P}$: Compute $v_A = \mathcal{A}(r_x), v_B = \mathcal{B}(r_x), v_C = \mathcal{C}(r_x)$; send $(v_A, v_B, v_C)$ to $\mathcal{V}$
  • Linearization (next 3 steps). The prover sends claimed evaluations of component polynomials to V, to be used to succinctly check the the above poly. The $v$'s represent random samplings of the multilinearization of the R1CS instance at $r_x$. The verifier now will check that the sampling. That is, the claimed evaluations of the three key terms from $\tilde{F}{io}(r_x)$ at the sumcheck challenge point $r_x$. These will be used to verify $G{io,\tau}(r_x) = e_x$
• $\mathcal{V}$: Abort with $b = 0$ if $e_x \neq (v_A \cdot v_B - v_C) \cdot \tilde{eq}(r_x, \tau)$
  • Deny prover cheat: the sampled point of the multilinearized R1CS $[v]$ must check out, forcing the claim to match poly $G_{io,\tau}(r_x)$
• $\mathcal{V}$: Sample $r_A, r_B, r_C \in_R \mathbb{F}$ and send $(r_A, r_B, r_C)$ to $\mathcal{P}$
  • These are random coefficients for linearizing the three polynomial evaluation claims into a single claim. They define the random linear combination used to compress three checks into one
• Let $T_2 = r_A \cdot v_A + r_B \cdot v_B + r_C \cdot v_C, \mu_2 = \log m, \ell_2 = 2$
  • $T_2$ is the claimed value for the linear combination. $\mu_2$ is still dimension of hypercube, but $\ell_2=2$ is degree bound for $M_{r_x}$ polynomial (lower than first sumcheck!)
• $\mathcal{V}$: Sample $r_y \in_R \mathbb{F}^{\mu_2}$. Second sumcheck: $e_y \leftarrow \langle\mathcal{P}{SC}(M{r_x}), \mathcal{V}_{SC}(r_y)\rangle(\mu_2, \ell_2, T_2)$
  • recall: $$M_{r_x}(y) = r_A \cdot \tilde{A}(r_x,y) \cdot \tilde{Z}(y) + r_B \cdot \tilde{B}(r_x,y) \cdot \tilde{Z}(y) + r_C \cdot \tilde{C}(r_x,y) \cdot \tilde{Z}(y)$$
  • the verifier now executes sumcheck over the polynomial $M$, where the $\t A, \t B, \t C$ terms are compressed by the verifier challenges $r_A, r_B, r_C$. All that remains is to avoid having the verifier compute $\t Z$ which is depends on witness $\t w$. We construct a component polynomial describing $\t Z$ in the next step.
• $\mathcal{P}$: $v \leftarrow \tilde{w}(r_y[1..])$ and send $v$ to $\mathcal{V}$
  • recall: $$\tilde{Z}(r_y) = (1-r_y[0]) \cdot \tilde{w}(r_y[1..]) + r_y[0] \cdot \widehat{(io,1)}(r_y[1..])$$
  • then $v$ is an evaluation of the witness ml poly at the challenged $r_y$ values. The rest of the expression may be computed directly by $v$ from the R1CS values.
• $b_e \leftarrow \langle\mathcal{P}{\text{PC.Eval}}(\tilde{w}, S), \mathcal{V}{\text{PC.Eval}}(r)\rangle(pp, C, r_y, v, \mu_2)$ ; $\mathcal{V}$: Abort with $b = 0$ if $b_e == 0$
  • The verifier may now use the opening of $\t w$ at $r_y$ to compute an opening to the second sumcheck at $r_y$ to compute the opening of the first sumcheck at $r_x$, all underneath the PCS (denoted PC) This step verifies the claimed witness evaluation using the commitment from step 1. The PC.Eval protocol proves $v$ is correct evaluation.
• $\mathcal{V}$: $v_Z \leftarrow (1-r_y[0]) \cdot \tilde{w}(r_y[1..]) + r_y[0] \cdot \widehat{(io,1)}(r_y[1..])$
  • verifier computes the evaluation $\t Z(r_y)$
• $\mathcal{V}$: $v_1 \leftarrow \tilde{A}(r_x, r_y), v_2 \leftarrow \tilde{B}(r_x, r_y), v_3 \leftarrow \tilde{C}(r_x, r_y)$
  • Verifier evaluates R1CS matrices at challenge points - this is efficient as matrices are public. This step is not succinct, but can be rendered succinct via a PCS transformation, described in latter sections.
• $\mathcal{V}$: Abort with $b = 0$ if $e_y \neq (r_A \cdot v_1 + r_B \cdot v_2 + r_C \cdot v_3) \cdot v_Z$
  • Verifier checks if claimed $M_{r_x}(r_y)$ matches actual evaluation using all components.
• $\mathcal{V}$: Output $b = 1$

The remainder of the paper describes an efficient PCS for compressing the MLE opening for the prover, requiring a transformation from a dense MLE to a sparse MLE for efficiency.

That is, we now have an NIZK which we will render succinct via a constructed PCS, allowing the verifier to evaluate $\t A, \t B, \t C$ efficiently.

The approach can be rendered ZK via commit and prove techniques ("Everything provable is provable in zero knowledge").

6 - PCS abstractly

This step was SLOW

• $\mathcal{V}$: $v_1 \leftarrow \tilde{A}(r_x, r_y), v_2 \leftarrow \tilde{B}(r_x, r_y), v_3 \leftarrow \tilde{C}(r_x, r_y)$

but it's okay. We adjust with a PCS, including a pre-processing step committing to the R1CS instance as follows:

Encode Algorithm: Encode($pp_{cc}$, $(A, B, C)$): • $(C_A, S_A) \leftarrow \text{PC.Commit}(pp_{cc}, \tilde{A})$ • $(C_B, S_B) \leftarrow \text{PC.Commit}(pp_{cc}, \tilde{B})$ • $(C_C, S_C) \leftarrow \text{PC.Commit}(pp_{cc}, \tilde{C})$ • Output $(C_A, C_B, C_C)$

$\mathcal{V}$ retains commitments output by Encode (which need not hide the underlying polynomials, so in practice $S_A = S_B = S_C = \perp$). The interactive argument proceeds as in the prior section except that at step 16, instead of $\mathcal{V}$ evaluating $\tilde{A}, \tilde{B}, \tilde{C}$, we have:

Prover's Step: $\mathcal{P}$: $v_1 \leftarrow \tilde{A}(r_x, r_y)$, $v_2 \leftarrow \tilde{B}(r_x, r_y)$, $v_3 \leftarrow \tilde{C}(r_x, r_y)$. Send $(v_1, v_2, v_3)$ to $\mathcal{V}$.

Verification Protocol: • $b_1 \leftarrow \langle\mathcal{P}{\text{PC.Eval}}(\tilde{A}, \perp), \mathcal{V}{\text{PC.Eval}}(r)\rangle(pp_{cc}, C_A, (r_x, r_y), v_1, 2\log m)$ • $b_2 \leftarrow \langle\mathcal{P}{\text{PC.Eval}}(\tilde{B}, \perp), \mathcal{V}{\text{PC.Eval}}(r)\rangle(pp_{cc}, C_B, (r_x, r_y), v_2, 2\log m)$ • $b_3 \leftarrow \langle\mathcal{P}{\text{PC.Eval}}(\tilde{C}, \perp), \mathcal{V}{\text{PC.Eval}}(r)\rangle(pp_{cc}, C_C, (r_x, r_y), v_3, 2\log m)$ • $\mathcal{V}$: Abort with $b = 0$ if $b_1 = 0 \vee b_2 = 0 \vee b_3 = 0$

The authors design SPARK to only incur subquadratic prover costs to compute eval in $m$ (the size), without (ambiguous) asymptotic overhead for verifier

7 SPARK pcs

highlevel

Section 7 introduces SPARK, a PCS based in Hyrax.

Reader warning. The background fon this section is significant, and thorough understanding of Hyrax and "memory checking techniques" seems basically assumed. The section is described below at a high level, but a more precise, lower level description is beyond me at this moment.

Problem: For matrices $A, B, C \in \mathbb{F}^{m \times m}$ with $n$ non-zero entries, need to efficiently commit to and prove evaluations of $\tilde{A}, \tilde{B}, \tilde{C}$ at $(r_x, r_y) \in \mathbb{F}^{\log m} \times \mathbb{F}^{\log m}$.

Naive Solution (SPARK-naive):

• Use existing commitment scheme (hyrax)
• For evaluation at $r \in \mathbb{F}^{2\log m}$, recall the defn of multilinear polynomial evaluation at $r$: $$\tilde{M}(r) = \sum_{i \in {0,1}^{2\log m} : M(i)\neq 0} M(i) \cdot \tilde{eq}(i, r)$$
• Build $O(\log m)$-depth circuit with $O(n \cdot \log m)$ gates
• Use Hyrax for verification
• Problem: $O(n \log n)$ prover time

Better Solution (SPARK):

• Key insight: For $M \in {A,B,C}$, evaluation at $(r_x, r_y)$ can be rewritten: $$\tilde{M}(r_x, r_y) = \sum_{(i,j) \in ({0,1}^{\log m}, {0,1}^{\log m}) : M(i,j)\neq 0} M(i,j) \cdot \tilde{eq}(i, r_x) \cdot \tilde{eq}(j, r_y)$$
• Use offline memory checking to build $O(n)$-sized circuit
• Employ multiset hash functions: $$h_\gamma(a,v,t) = a\gamma^2 + v\gamma + t$$ $$H_\gamma(M) = \prod_{e \in M}(e - \gamma)$$
• Results in linear-time prover when combined with efficient commitment schemes; Sub-linear verification for sparse polynomials!

in more detail

TODO

terms

• Hyrax, a zkSNARK that achieves sub-linear verification costs for uniform circuits, specifically data-parallel circuits. The prover’s costs in Hyrax can be made linear in the circuit size using subsequent ideas. Furthermore, the verifier’s costs are O(d log n + e) where d is the depth of the circuit and e is the cost to the verifier to participate in PC.Eval to evaluate a log |w|-variate multilinear polynomial where w is a witness to the circuit.

)

related:

• topic:: [[topic-Interactive Oracle Proofs (IOP)]]