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?


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://people.cs.georgetown.edu/jthaler/gkrnotes.pdf https://people.cs.georgetown.edu/jthaler/GKRNote.pdf


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

Remco Bloemen
Math & Engineering