Jolt

\gdef\mat#1{\mathrm{#1}} \gdef\p#1{\left({#1}\right)} \gdef\ceil#1{\left\lceil{#1}\right\rceil} \gdef\forall{\mathop{\huge ∀}\limits}

Notes studying Jolt. Per Michael Zhu's suggestion I will follow the lineage from Spice SAGL18, Spartan S19, Lasso STW23, Jolt AST23, Binius DP23.

Spice

Spartan

Spartan (S19) is a transparant zkSNARK for R1CS. Recal an R1CS instance over a field 𝔽 with n-sparse m×m matrices \mat A, \mat B, \mat C such that a z=(1,\mathsf{pub},\mathsf{priv}) satisfies iff (\mat A⋅ z) ∘(\mat B ⋅ z) = \mat C ⋅ z. We convert this to a sumcheck zero testing statement \forall_{x∈\{0,1\}^s}0= \p{\sum_{y∈\{0,1\}^s}\widetilde A(x,y)⋅\widetilde z(y)}⋅ \p{\sum_{y∈\{0,1\}^s}\widetilde B(x,y)⋅\widetilde z(y)}\\- \sum_{y∈\{0,1\}^s}\widetilde C(x,y)⋅\widetilde z(y) where \widetilde\square denotes a multilinear extension and s=\ceil{\log_2 m}.Batching the inner sumchecks, it takes two sumchecks to reduce this to (r_A⋅\widetilde A(r_x, r_y) + r_B⋅\widetilde B(r_x, r_y) + r_C⋅\widetilde C(r_x, r_y)) ⋅ \widetilde z(r_y) For \widetilde z the prover provides a hiding polynomial commitment to \mathsf{priv} up front and reveals it at r_y so that the verifier can compute \widetilde z(r_y). The verifier knows \widetilde A, \widetilde B, \widetilde C and can evaluate it directly.

Evaluating the \widetilde A, \widetilde B, \widetilde C takes O(n) work. To solve this the verifier pre-computes commitments to them and the prover computes openings. To be efficient, this requires a polynomial commitements scheme that is efficient for sparse polynomials. Consider \widetilde A (the other cases are identical) we have the n term sum \widetilde A(r_x, r_y) = \sum_{\begin{subarray}{c} i,j ∈ \{0,1\}^s \\[.3em] \mat A_{ij} ≠ 0 \end{subarray}} \mat A_{ij} ⋅ \widetilde{\operatorname{eq}}(i, r_x)⋅\widetilde{\operatorname{eq}}(j, r_y) where \widetilde{\operatorname{eq}} is the multilinear equality function.

To evaluate this we create lookup tables for \widetilde{\operatorname{eq}}(i, r_x), \widetilde{\operatorname{eq}}(j, r_y) and the sequence of (i,j, \mat M_{ij}) tuples to sum over.

Create three vectors, i, j and M_{ij}.

References

Remco Bloemen
Math & Engineering
https://2π.com