Learning new things!
following this post
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} \)
the multi-linear polynomial for …
let \(\mathcal{G}\) be a function in binary field:
$$\mathcal{G}(x), x \in \{0,1\}^m$$
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 }$$
Or another equivalent expression:
$$\mathcal{G}(r_1,…,r_m)=\sum\limits_{x\in\{0,1\}^m}\mathcal{G}(x)eq(x,r)$$
emphasize:
\(r_i \in \mathbb{F}\)…
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.
Justin Thaler’s descritpion of sum-check protocol
Following the definition from Justin Thaler (you can find why the multilinear extension of a indexed table is unique)
Let \(\mathbb{F}\) be any finite field, and let \( f : \{0,1\}^v \rightarrow \mathbb{F} \) be any function mapping the \( v \)-dimensional …