zkp update
\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\set#1{\mathcal #1} \gdef\mat#1{\mathrm #1} \gdef\vec#1{\bm #1}
Customizable Constraint System (CCS)
In STW23 a CCS is a set of sets of matrices \set S such that a witness \vec w satisfies
\sum_{\set T ∈ \set S}\ \bigodot_{M ∈ \set T}\ M ⋅ \vec w = \vec 0
where \bigodot is the Hadamard product.
A R1CS constraint is a triplet of matrices (A,B,C) such that a witness \vec w satisfies \p{A⋅\vec w} ∘ \p{B⋅\vec w} = C⋅\vec w. A R1CS becomes \ps{\ps{A,B},\ps{-C}}. For transformation of Plonkish and AIR constraints see STW23.
Note. CCS is closed under conjunction. Given two CCS constraints \set S_1 and \set S_2 with matrices of size m_1×n and m_2×n respectively. Convert all matrices to \p{m_1 + m_2} × n as \begin{bmatrix}M \\ 0\end{bmatrix} and \begin{bmatrix}0 \\ M\end{bmatrix} respectively. The conjoined CSS is now the union.
Q. The degree of the CCS is \max_{\set T ∈ \set S} \delim\vert{\set T}\vert and the rank is the number of rows in the matrices. Can we reduce the degree by increasing the rank? For example we can reduce \ps{\ps{A, B}, \ps{C}} to \ps{\ps{D, D}, \ps{E}} at doubling rank.
CCS+ extends this with a lookup argument. In addition to the above there is a set of indices \set I and a set of field elements \set T. The witness additional satisfies
\operatornamewithlimits{\large \forall}_{i∈\set I}\ w_i ∈ \set T
Q. How do we conjoin table lookup arguments?
Sum-check
Introduced in LFKN92. Given multivariate polynomial G ∈ \F[X_1,…,X_n] and domain \set B = \set B_1 × ⋯ × \set B_n, \set B_i \subseteq \F. Typically \set B = \ps{0,1}^n. We want to proof
h = \sum_{\vec x ∈ \set B} G\p{\vec x}
The prover commits to G such that the verifier has oracle access to evaluate G(\vec x) for \vec x ∈ \F^n.
Prover sends G_1 ∈ \F[X]
G_1(X) = \sum_{\vec x ∈ \set B_2×⋯×\set B_n} G\p{X, \vec x}
verifier checks
h = \sum_{x ∈ \set B_1} G_1\p{x}
verifier sends random r ∈ \F.
prover sends
G_2(X) = \sum_{\vec x ∈ \set B_3×⋯×\set B_n} G\p{r, X, \vec x}
verifier checks that degree of G_2 equals degree of X_2 in G and
G_1(r) = \sum_{x ∈ \set B_2} G_2\p{x}
repeat until prover sends
G_n(X) = G\p{\vec r, X}
. Verifier takes a random r ∈ \F and checks
G_n(r) = G(\vec r)
using any means to compute G\p{\vec r}.
See Justin Thaler's notes on Sum-Check: https://people.cs.georgetown.edu/jthaler/sumcheck.pdf
Small field optimization https://people.cs.georgetown.edu/jthaler/small-sumcheck.pdf
https://zkproof.org/2020/03/16/sum-checkprotocol/
GKR
https://people.cs.georgetown.edu/jthaler/gkrnotes.pdf https://people.cs.georgetown.edu/jthaler/GKRNote.pdf
logUp
Cached Quotients
Lasso lookups
For fixed sparse matrix \mathrm M and committed vectors \vec v and \vec a show:
\mathrm M ⋅ \vec v = \vec a
