Multivariate Lookup Arguments
\gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\F{\mathbb F} \gdef\vec#1{\mathbf{#1}} \gdef\eq{\operatorname{eq}}
Most lookup protocols are based on univariate polynomials. In the multivariate sumcheck setting can use different techniques from the Lasso line of work.
Lookup arguments and indexed lookup arguments.
Grand Products
A grand product reduces a claim of the form a = \prod_{\vec x} p(\vec x) to a claim of the form p(\vec r) = h for some \vec r, h.
Tha13 Proposition 2 proposes a GKR-like protocol specialized for the grand product case.
p_{i+1}(z) = \sum_{p \in \ps{0,1}^{n_i}} \eq (z,p) \cdot p_i(p, 0) \cdot p_i(p, 1)
SL20 Lemma 5.1
To prove
p = \prod_{x \in \ps{0,1}^n} v(x)
g(\vec z) = \sum_{\vec x \in \ps{0,1}^n} \eq (\vec z, \vec x) ⋅ \p{ f(1, \vec x) - f(\vec x, 0) ⋅ f(\vec x, 1) }
- g(\vec r_0) = 0
- f(0, \vec r_1) = v(\vec r_1)
- f(\vec 1, 0) = p
Batching of grand products.
STW23 appendix E.
Multiset Equality
Offline Memory Checking
Spark / Surge
Lasso
LogUp-GKR
Generalized Lasso
References
- Tha13 Justin Thaler (2013). "Time-Optimal Interactive Proofs for Circuit Evaluation"
- Set19 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.
- PH23 Shahar Papini, Ulrich Haböck (2023). Improving logarithmic derivative lookups using GKR.
- Sou23 Lev Soukhanov (2023). Power circuits: a new arithmetization for GKR-styled sumcheck.
