zk based on Multilinear polynomials - Shuang's Crypto Notes

Logup GKR – 3: Air constraint for STARK

Committed Traces

The traces that will be interpreted as multilinear polynomial evaluations from STARK:

talking about a single lookup relation, for multiple lookup, it means the

Extra traces that dedicated for Logup-GKR and need to be built additionally

Circuit Example:

using a simple example to describe the GKR circuit

bus …

Input Layer Encoding (witness encoding)

trace columns are interpreted as functions, the inputs of the function are bits, enough number of bits that can present $n$ number of witness in this column.

for trace $i$, with $n$ number of rows (trace degree, trace length)

$f_i(b_0,b_1,b_2,…,b_n)=a_{b_n,…,b_2,b_1,b_0} $

at …

Witness encoding:

trace columns are interpreted as functions, the inputs of the function are bits, enough number of bits that can present $n$ number of witness in this column.

for trace $i$, with $n$ number of rows (trace degree, trace length)

$f_i(b_0,b_1,b_2,…,b_n)=a_{b_n,…,b_2,b_1,b_0} $

Circuit for computing the

…

Commonly used tricks in Multilinear polynomials

Equation function

Turn a function in binary field to its multilinear extension.

let $\mathcal{G}$ be a function in binary field, its multi-linear extension can be presented as:

$$\mathcal{G}(r_1,…,r_m)=\sum\limits_{x\in\{0,1\}^m}\mathcal{G}(x)\prod\limits^{m}_{i=1}\underbrace{(r_i\cdot x_i + (1-r_i)(1-x_i))}_{x_i=0 \rightarrow 1-r_i, x=1 \rightarrow r_i }$$

emphasize:

$r_i \in \mathbb{F}$

$x \in \{0,1\}^m$

$x_i $ is 0 or 1…

GKR Part 2 -example

Using the following example to go through GKR protocol

this blogs follows the example in Spartan 预备知识：GKR with ZK Argument

zero knowledge version of GKR, Hyrax approach.

…

Multi-linear extension

Following the definition from Justin Thaler

Let $\mathbb{F}$ be any finite field, and let $ f : \{0,1\}^v \rightarrow \mathbb{F} $ be any function mapping the $ v $-dimensional Boolean hypercube to $\mathbb{F}$. A $ v $-variate polynomial $ g $ over $\mathbb{F}$ is said to be an …

Category: zk based on Multilinear polynomials