# 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.

## 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

• SAGL18 Srinath Setty, Sebastian Angel, Trinabh Gupta, and Jonathan Lee (2018). Proving the correct execution of concurrent services in zero-knowledge.
• S19 Srinath Setty (2019). Spartan: Efficient and general-purpose zkSNARKs without trusted setup.
• STW23 Srinath Setty, Justin Thaler, Riad Wahby (2023). Unlocking the lookup singularity with Lasso.
• AST23 Arasu Arun, Srinath Setty, Justin Thaler (2023). Jolt: SNARKs for Virtual Machines via Lookups.
• ST23 Srinath Setty, Justin Thaler (2023). BabySpartan: Lasso-based SNARK for non-uniform computation.
• DP23 Benjamin E. Diamond, Jim Posen (2023). Succinct Arguments over Towers of Binary Fields.

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