Mina Kimchi

作者: 雪落无留痕 | 来源:发表于2022-07-01 12:35 被阅读0次

Kimchi是Mina新提出的零知识证明方案，基于Plonk和Halo2设计，用于实现递归证明方案。

Kimchi 协议主要有三种证明：

Custom gates: 定制电路，用于实现具体的电路功能；
Permutation: 主要用于复制约束的证明，保证电路中一些值的相等；
Lookup tables: 进行查找表约束；

上述所有的证明都需要转化为方程等式验证，主要需要处理两个关键问题：

Roots-check: 验证方程在一些值上等于0；
Aggregation: 验证等式关系对于所有的方程都成立。

Roots-check

对于一个多项式 $p(X)$ ，次数为 $d$ ，然后验证 $p(x)=0, x\in S$ , 其中 $S$ 为某个集合。

若对每个 $x$ 分别验证，会比较麻烦。因此 $S$ 集合通过 vanishing polynomial $v_S(X)$ 定义，即：
$v_S(X)=\prod_{x\in S}(X-s)$
此时只需要验证 $p(X)$ 可以整除 $v_S(X)$ 即可，即存在次数为 $d-|s|$ 的 quotient polynomial：
$q(X):=\frac{p(X)}{v_S(X)}$
若证明者提供一个商多项式，并验证 $q(a)=p(a)/v_S(a), a\in \mathbb{F}\setminus S$ ，根据Schwartz-Zippel定理， $p(X)$ 在 $S$ 集合上成立。

Schwartz-Zipple定理
对于两个多项式 f(X)和 g(X)，次数皆为d, 则 f(x)和g(x) 最多相交 d 个点，对于h(x) = f(x)-g(x)， 最多有 d 个根。

Aggregation

上面只介绍一个多项式在某个集合等式关系成立，可以采用聚合，验证多个多项式在某个集合上成立，采用powers-of-alpha 技术，即选取随机的 $\alpha$ , 验证：
$\bigwedge_{i_n} p_i(X) =_? 0 \iff_{w.h.p.} \sum_{i=0}^{n} \alpha^i \cdot p_i(X) =_? 0$

Custom gates

Kimchi 可以灵活定制各种定制电路，满足各种约束条件，以下表中为例，定义了四种电路：

row	`GateType::`	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	`Generic`	`l`	`r`	`o`
1	`CompleteAdd`	`x1`	`y1`	`x2`	`y2`	`x3`	`y3`	`inf`	`same_x`	`s`	`inf_z`	`x21_inv`
2	`ExamplePairs`	`a`	`e`	`i`	`o`	`u`	`y`
3	`ExampleTriples`	`a`	`b`	`c`	`d`	`e`	`f`	`g`	`h`	`i`	`j`	`k`	`l`	`m`	`n`	`o`

每种门电路需要满足一种约束，例如：

Generic 通用电路：

l $\cdot c_l +$ r $\cdot c_r +$ o $\cdot c_o +$ l $\cdot$ r $\cdot c_m + c_c = 0$

CompleteAdd 椭圆曲线加法电路:

x21_inv $\cdot ($ x2 $-$ x1 $) - ( 1 -$ same_x $) = 0$
same_x $\cdot ($ x2 $-$ x1 $) = 0$
same_x $\cdot ( 2 \cdot$ s $\cdot$ y1 $- 3 \cdot$ x1 $^2) + ( 1 -$ same_x $) \cdot \big(($ x2 $-$ x1 $) \cdot$ s $-$ y2 + y1 $\big) = 0$
x1 $+$ x2 $+$ x3 $-$ s $^2 = 0$
s $\cdot ($ x1 $-$ x3 $) -$ y1 $-$ y3 $= 0$
$($ y2 $-$ y1 $) \cdot ($ same_x $-$ inf $) = 0$
$($ y2 $-$ y1 $) \cdot$ inf_z $-$ inf $= 0$

ExamplePairs 元素对示例电路:

a $-$ e $= 0$
i $-$ o $= 0$
u $-$ y $= 0$

ExampleTriples 三元组示例电路:

a $\cdot$ b $\cdot$ c $= 0$
d $\cdot$ e $\cdot$ f $= 0$
g $\cdot$ h $\cdot$ i $= 0$
j $\cdot$ k $\cdot$ l $= 0$
m $\cdot$ n $\cdot$ o $= 0$

对于每列的元素，可以用w0..w14 表示，上述约束条件变为：

Generic:

w0 $\cdot c_l +$ w1 $\cdot c_r +$ w2 $\cdot c_o +$ w0 $\cdot$ w1 $\cdot c_m + c_c = 0$

CompleteAdd:

w10 $\cdot ($ w2 $-$ w0 $) - ( 1 -$ w7 $) = 0$
w7 $\cdot ($ w2 $-$ w0 $) = 0$
w7 $\cdot ( 2 \cdot$ w8 $\cdot$ w1 $- 3 \cdot$ w0 $^2) + ( 1 -$ w7 $) \cdot \big(($ w2 $-$ w0 $) \cdot$ w8 $-$ w3 + w1 $\big) = 0$
w0 $+$ w2 $+$ w4 $-$ w8 $^2 = 0$
w8 $\cdot ($ w0 $-$ w4 $) -$ w1 $-$ w4 $= 0$
$($ w3 $-$ w1 $) \cdot ($ w7 $-$ w6 $) = 0$
$($ w3 $-$ w1 $) \cdot$ w9 $-$ w6 $= 0$

ExamplePairs:

w0 $-$ w1 $= 0$
w2 $-$ w3 $= 0$
w4 $-$ w5 $= 0$

ExampleTriples:

w0 $\cdot$ w1 $\cdot$ w2 $= 0$
w3 $\cdot$ w4 $\cdot$ w5 $= 0$
w6 $\cdot$ w7 $\cdot$ w8 $= 0$
w9 $\cdot$ w10 $\cdot$ w11 $= 0$
w12 $\cdot$ w13 $\cdot$ w14 $= 0$

对于每一列的元素进行Lagrange 插值，得到多项式： $w_0(X),\cdots,w_{14}(X)$ ，
$\mathbb{G}=<g>: w_j(g^i)=trace[i,j]$
可以得到：

Generic:

$w_0(X)\cdot c_l + w_1(X) \cdot c_r + w_2(X) \cdot c_o + w_0(X) \cdot w_1(X) \cdot c_m + c_c = 0$

CompleteAdd:

$w_{10}(X) \cdot \big( w_2(X) - w_0(X)\big) - \big( 1 - w_7(X)\big) = 0$
$w_7(X) \cdot ( w_2(X) - w_0(X) ) = 0$
$w_7(X) \cdot \big( 2 \cdot w_8(X) \cdot w_1(X) - 3 \cdot w_0(X)^2 \big) + \big( 1 - w_7(X) \big) \cdot \big((w_2(X) - w_0(X) \big) \cdot w_8(X) - w_3(X) + w_1(X) \big) = 0$
$w_0(X) + w_2(X) + w_4(X) - w_8(X)^2 = 0$
$w_8(X) \cdot \big( w_0(X) - w_4(X)\big) - w_1(X) - w_4(X) = 0$
$\big( w_3(X) - w_1(X) \big) \cdot \big( w_7(X) - w_6(X) \big) = 0$
$( w_3(X) - w_1(X) ) \cdot w_9(X) - w_6(X) = 0$

ExamplePairs:

$w_0(X) - w_1(X) = 0$
$w_2(X) - w_3(X) = 0$
$w_4(X) - w_5(X) = 0$

ExampleTriples:

$w_0(X) \cdot w_1(X) \cdot w_2(X) = 0$
$w_3(X) \cdot w_4(X) \cdot w_5(X) = 0$
$w_6(X) \cdot w_7(X) \cdot w_8(X) = 0$
$w_9(X) \cdot w_{10}(X) \cdot w_{11}(X) = 0$
$w_{12}(X) \cdot w_{13}(X) \cdot w_{14}(X) = 0$

对于每个定制电路，需要定义一个GateType 的选择子，其值在为1或0，以表示定制电路是否在某一行上成立。

例于对于Generic的选择子generic(X)，值在 $X=g^0$ (表示第一行)为 1，其余皆为0.

可以各个定制电路的约束聚合成为一个多项式：

$\text{gates}(X) =$

$\quad \text{generic}(X) \cdot$

$\qquad \alpha^0 \cdot \Big( w_0(X)\cdot c_l + w_1(X) \cdot c_r + w_2(X) \cdot c_o + w_0(X) \cdot w_1(X) \cdot c_m + c_c \Big)$

$\quad + \text{add}(X) \cdot \huge($

$\qquad \alpha^0 \cdot \Big( w_{10}(X) \cdot \big( w_2(X) - w_0(X)\big) - \big( 1 - w_7(X)\big) \Big )$

$\qquad + \alpha^1 \cdot \Big( w_7(X) \cdot ( w_2(X) - w_0(X) ) \Big)$

$\qquad + \alpha^2 \cdot \Big( w_7(X) \cdot \big( 2 \cdot w_8(X) \cdot w_1(X) - 3 \cdot w_0(X)^2 \big) + \big( 1 - w_7(X) \big) \cdot \big((w_2(X) - w_0(X) \big) \cdot w_8(X) - w_3(X) + w_1(X) \big) \Big)$

$\qquad + \alpha^3 \cdot \Big( w_0(X) + w_2(X) + w_4(X) - w_8(X)^2 \Big)$

$\qquad + \alpha^4 \cdot \Big ( w_8(X) \cdot \big( w_0(X) - w_4(X)\big) - w_1(X) - w_4(X) \Big)$

$\qquad + \alpha^5 \cdot \Big ( \big( w_3(X) - w_1(X) \big) \cdot \big( w_7(X) - w_6(X) \big) \Big)$

$\qquad + \alpha^6 \cdot \Big( ( w_3(X) - w_1(X) ) \cdot w_9(X) - w_6(X) \Big) \huge)$

$\quad + \text{pairs}(X) \cdot \Big($

$\qquad \alpha^0 \cdot \big( w_0(X) - w_1(X) \big)$

$\qquad + \alpha^1 \cdot \big( w_2(X) - w_3(X) \big)$

$\qquad + \alpha^2 \cdot \big( w_4(X) - w_5(X) \big) \Big)$

$\quad + \text{triples}(X) \cdot \Big($

$\qquad \alpha^0 \cdot \big( w_0(X) \cdot w_1(X) \cdot w_2(X) \big)$

$\qquad + \alpha^1 \cdot \big( w_3(X) \cdot w_4(X) \cdot w_5(X) \big)$

$\qquad + \alpha^2 \cdot \big( w_6(X) \cdot w_7(X) \cdot w_8(X) \big)$

$\qquad + \alpha^3 \cdot \big( w_9(X) \cdot w_{10}(X) \cdot w_{11}(X) \big)$

$\qquad + \alpha^4 \cdot \big( w_{12}(X) \cdot w_{13}(X) \cdot w_{14}(X) \big) \Big)$

然后验证 $q(X)=gates(X)/v_{\mathbb{G}}(X)$ ，随机值 $X\in\mathbb{F}$ \ $\mathbb{G}$ ，则可以使验证者确信：

证明者知道多项式 $gates(X)$ , 在 $x \in \{1,g,g^2,g^3\}$ 值皆为0.

Permutation

对于两个长度为 $n$ 的序列 $(f_1, f_2, \cdots, f_n)$ 和 $(g_1, g_2, \cdots, g_n)$ , 证明者要证明 $g_i = f_{\sigma(i)}$ , $1\leq i \leq n$ , $\sigma$ 为某个置换，协议过程如下：

验证者发送随机值 $\beta, \gamma \in \mathbb{F}$ 给证明者；
证明者构造两个新的序列： $(f_1, f_2, \cdots, f_n)$ 和 $(g_1, g_2, \cdots, g_n)$ , 其中
$f_i = f_i + \beta\cdot i + \gamma \\ g_i = g_i + \beta \cdot \sigma(i) + \gamma$
证明者计算新的序列 $s_i$ , 其中
$s_0=1, s_i= s_{i-1}\cdot \frac{f_i}{g_i}$
即
$s_i = \frac{\prod_{1\leq j\leq i}f_j}{\prod_{1\leq j \leq i}g_j}$
$s_i$ 即为所谓的grand product。

证明者将 ${s_i}$ 序列发给验证者。
验证者检查以下方程：
$\hat{s}(w^n) = s_0 = 1 \\ \hat{s}(w^i)\cdot g_i=\hat{s}(w^{i-1})\cdot f_i$
其中 $w^i$ 表示单位元的根， $\hat{s}$ 表示对序列 $s_i$ 的多项式插值。

若验证通过，则验证者确信 $g_i= f_{\sigma(i)}$ 成立， $1\leq i \leq n$ 。

Lookup

查找表主要用来验证witness 值在某个查找表中，主要用于对一些位操作减少约束条件的个数。

在Plookup的论文中，证明者需要计算三个向量：

$f$ , 查询向量，包含 witness 值，证明者想要证明其在查找表中；
$t$ , 查找表；
$s$ , 将 $f || t$ 并接起来，并根据 $t$ 进行排序。

plookup需要证明 $f$ 中的元素都在查找表 $t$ 中，当且仅当以下集合相等，即：

$\{(1+ \beta)f, diff(t)\}$
$diff(sorted(f,t))$

其中diff 是一种新的集合，通过随机差分由连续的两个元素构成：

$f=\{5,4,1,5\}$
$t=\{1,4,5\}$
$\{(1+\beta)f, diff(t)\}=\{(1+\beta)5, (1+\beta)4, (1+ \beta)1, (1+\beta)5, 1+\beta 4, 4+ \beta 5\}$
$diff(sorted(f,t))=\{1+\beta 1, 1+\beta 4, 4+ \beta 4, 4+ \beta 5, 5 + \beta 5, 5+ \beta 5\}$

可以采用Permutation 证明的形式，约束下面的累加器：

init: $acc_0=1$
Final: $acc_n=1$
对于 $0 < i \leq n$

$acc_i = acc_{i-1} \cdot \frac{(1+\beta)(\gamma + f_{i-1})(\gamma(1 + \beta) + t_{i-1} + \beta t_i)}{(\gamma(1+\beta) + s_{i-1} + \beta s_{i})}$

Kimchi 主要使用了 XOR 查找表，对于1 位的查找表如下所示：

l	r	o
1	0	1
0	1	1
1	1	0
0	0	0

Kimchi 使用4位的查找表，有 $2^8$ 行。

例如，对于下面的查询，可以验证 $r_0 \oplus r_2=2r_1$

l	r	0
1, r0	1, r2	2, r1

其对应的 grand product argument 为：

$acc_i = acc_{i-1} \cdot \frac{\color{green}{(1+\beta)(\gamma + w_0(g^i) + j \cdot w_2(g^i) + j^2 \cdot 2 \cdot w_1(g^i))}(\gamma(1 + \beta) + t_{i-1} + \beta t_i)}{(\gamma(1+\beta) + s_{i-1} + \beta s_{i})}$

Query selector 用于表示 XOR 查找表所存在行。

row	query selector
0	1
1	0

加上查询选择子的查找约束条件如下：

$acc_i = acc_{i-1} \cdot \frac{\color{green}{(1+\beta) \cdot query} \cdot (\gamma(1 + \beta) + t_{i-1} + \beta t_i)}{(\gamma(1+\beta) + s_{i-1} + \beta s_{i})}$

$\color{green}query$ 采用如下方式构造，若某一行没有表查询，用假的查询 $(0\oplus0=0)$ 表示：
$\begin{align} query = &\ selector \cdot (\gamma + w_0(g^i) + j \cdot w_2(g^i) + j^2 \cdot 2 \cdot w_1(g^i)) + \\ &\ (1- selector) \cdot (\gamma + 0 + j \cdot 0 + j^2 \cdot 0) \end{align}$
s 排序

向量 $s$ 的长度为：
$n \cdot |\text{queries}| + |\text{lookup\_table}|$
若向量 $s$ 的长度大于定义域大小 $n$ ，可以将 $s$ 划分为多个长度为 $n$ 的向量，此时对 $s$ 排序为两种方式：

Zig-zag 技术：将 $s$ 划分为多个列，例如 $h_1 = (s_0, s_2, s_4,\cdots)$ , $h_2=(s_1, s_3, s_5,\cdots)$ ，此时分子可以写为：

$(\gamma(1+\beta)+ h_1(x)+\beta h_2(x))(\gamma (1+\beta)+ h_2(x) + \beta h_1(x\cdot g))$

Snake 技术：将 $s$ 重排为如下形式：

    _   _
 | | | | |
 | | | | |
 |_| |_| |

此时分子表示为：
$(\gamma(1+\beta) + h_1(x) + \beta h_1(x \cdot g))(\gamma(1+\beta)+ h_2(x \cdot g) + \beta h_2(x))$
蛇形的 U 型约束为：
$L_{n-1}\cdot (h_1(x)-h_2(x))=0$
若存在 $h_3$ , 其表示为：
$(\gamma(1+\beta) + h_1(x) + \beta h_1(x \cdot g))(\gamma(1+\beta)+ h_2(x \cdot g) + \beta h_2(x))\color{green}{(\gamma(1+\beta)+ h_3(x) + \beta h_3(x \cdot g))}$
并且需要添加一个U 型约束：
$L_0\cdot (h_2(x)-h_3(x))=0$

Polynomials commitment

多项式承诺允许先对多项式进行承诺，然后由证明者给出多项式在某个点的值，并通过证明验证值的正确性。

PLonk 采用KZG 多项式承诺方案，Kimchi 采用 IPA（Inner product argument）承诺， IPA 通过对向量内积实现：

给定两个已经承诺（hash值）的向量 $\vec{a}$ 和 $\vec{b}$ ，长度为 $n$ ，证明其内积 $\langle \vec{a}, \vec{b} \rangle = z$

可以将多项式的计算转化为内积形式，例如对于多项式 $f(x)=f_0 + f_1x+f_2x^2+\cdots + f_nx^n$ ,

定义 $\vec{f} = (f_0,\cdots, f_n)$ , 则
$f(s)=\langle \vec{f}, (1,s, s^2, \cdots, s^n)$
IPA 协议描述

若证明知道一个私有的向量：
$\vec{a}=(a_1, a_2, a_3, a_4)$
公开的参数有：

$\vec{G}=(G_1, G_2,G_3, G_4)$ , 用于Pedersen hashing 基；
$A=\langle \vec{a}, \vec{G} \rangle$ , 为 $\vec{a}$ 的承诺；
$\vec{b}=(b_1,b_2, b_3, b_4)$ 为 $s$ 的幂， $\vec{b}=(1,s,s^2,s^3)$
内积的结果为： $z=\langle \vec{a}, \vec{b} \rangle$

证明的流程如下图：

证明者发送多项式 $f$ 的承诺；
验证者发送点 $s$ ，要求证明计算 $f(s)$ , 为了让证明者生成证明，验证者需要发送一个随机挑战 $x$ ;
证明者发送计算的结果 $z$ 和证明，给验证者。

首先证明约减证明的大小：

$\vec{a'} = x^{-1} \begin{pmatrix}a_1 \\ a_2\end{pmatrix} + x \begin{pmatrix}a_3 \\ a_4\end{pmatrix}$
$\vec{b'} = x \begin{pmatrix}b_1 \\ b_2\end{pmatrix} + x^{-1} \begin{pmatrix}b_3 \\ b_4\end{pmatrix}$
$\vec{G'} = x \begin{pmatrix}G_1 \\ G_2\end{pmatrix} + x^{-1} \begin{pmatrix}G_3 \\ G_4\end{pmatrix}$

证明问题约减为： $\langle \vec{a'}, \vec{b'} \rangle = z'$ ， $a', b', G'$ 大小变为原先的一半。

此时
$\begin{align} \vec{A'} =& \langle \vec{a'}, \vec{G'} \rangle \\ =& (x^{-1} a_1 + x a_3)(x G_1 + x^{-1} G_3) + (x^{-1} a_2 + x a_4)(x G_2 + x^{-1}G_4) \\ =& A + x^{-2} (a_1 G_3 + a_2 G_4) + x^2 (a_3 G_1 + a_4 G_2) \\ =& A + x^{-2} L_a + x^{2} R_a \end{align}$
为了计算新的承诺，验证者需要：

前一个承诺 $A$ ;
$x^2, x^{-2}$ ;
两个曲线上点的点 $L_a$ 和 $R_a$

新的内积变为：
$\begin{align} \vec{z'} =& \langle \vec{a'}, \vec{b'} \rangle \\ =& \langle \begin{pmatrix}x^{-1} a_1 + x a_3 \\ x^{-1} a_2 + x a_4 \end{pmatrix}, \begin{pmatrix}x b_1 + x^{-1} b_3 \\ x b_2 + x^{-1} b_4 \end{pmatrix} \rangle \\ =& (a_1b_1 + a_2b_2 + a_3b_3 + a_4b_4) + x^{-2} (a_1b_3 + a_2b_4) + x^2 (a_3b_1 + a_4b_2) \\ =& z + x^{-2} (L_z) + x^2 (R_z) \end{align}$
和 $A'$ 类似，验证者需要利用先前的 $z, L_z, R_z$ 重新计算 $z'$ ，

最终，证明变成：

向量 $\vec{a'}$ ，大小是 $\vec{a}$ 的一半；
椭圆曲线点 $L_a, R_a$
标量 $L_z, R_z$

HALO 优化

Zcash HALO 对IPA 进行了优化，转化为如下形式：
$C= A+ zU=\langle \vec{a}, \vec{G} \rangle + \langle \vec{a}, \vec{b}\rangle U$
类似地，
$C'= A'+ zU'=\langle \vec{a'}, \vec{G'} \rangle + \langle \vec{a'}, \vec{b'}\rangle U$
具体的约减方式为：
$\begin{align} C' =& \langle \vec{a'}, \vec{G'} \rangle + \langle \vec{a'}, \vec{b'} \rangle U \\ =& [A + x^{-2} L_a + x^{2} R_a] + [z + x^{-2} (L_z) + x^2 (R_z)] U \end{align}$
进一步可以写为：
$C' = C + x^{-2} (L_a + L_z U) + x^{2} (R_a + R_z U)$
此时验证验证者除了 $\vec{a'}$ ，只需要两个点：

$L = L_a +L_zU$
$R= R_a + R_zU$

以此递归，经过 $log_2\ n$ 轮后，得到最后的承诺 $C'$ ,

$C' = C + x^{-2}L + x^2 R$

验证者检查：
$C'= \langle \vec{a'}, \vec{G'} \rangle + \langle \vec{a'}, \vec{b'} \rangle U$
验证者需要重新计算 $\vec{G'}$ 和 $\vec{b'}$ ，

[图片上传失败...(image-84b0dc-1656650076375)]

**zero-knowledge **

上述协议中，需要明文发送 $a'$ ，会泄露原始向量 $a$ 的值，为了实现零知识证明，调整pedersen 承诺，使其满足hiding 属性，即

$C = A + zU + rH = \langle \vec{a}, \vec{G} \rangle + \langle \vec{a}, \vec{b} \rangle U +rH$

其中 $H$ 是一个椭圆曲线上的生成元， $r$ 为随机数。

$L$ 和 $R$ 也可能泄露一些信息，将其调整为：

$L = L_a + L_z U + r_L H$
$R = R_a + R_z U + r_R H$

最终打开的承诺为：
$C' = C + x^{-2}L + x^2 R$
使用 $\vec{a'}$ 和最终盲化的值 $r'$ ，和重构的 $\vec{G'}$ 和 $\vec{b'}$ ，打开承诺：
$\langle \vec{a'}, \vec{G'} \rangle + \langle \vec{a'}, \vec{b'} \rangle U + r'H$
其中 $r'$ 为 $r + \sum_i (r_{Li} + r_{Ri})$ 。

此时证明构成为：

每一轮有2个椭圆曲线点 $L$ 和 $R$ ；
一个标量 $a'$ ；
一个盲化因子标量 $r'$ .

最后，还需要证明者隐藏 $\vec{a'}$ ， Halo 证文中采用 Schnorr 协议，如下所示：

更多参考：

Split accumulation for Pedersen polynomial commitments

参考：https://eprint.iacr.org/2020/1618.pdf Appendix A.

DLog Pedersen polynomial commitments

参考： https://eprint.iacr.org/2020/499.pdf Appendix A

Zero knowledge

为了实现零知识证明，PLONK 将多项式乘以一个随机的低度多项式，但这会增加多项式的次数， Kimchi 对此进行了优化。

Columm polynomials

令 $w$ 为PLONK多项式的行数，列的 witness 值为： $s_1, s_2, \cdots, s_w$ ， $n$ 为最接近 $w$ 的二次幂， $n \geq w$ .

随机选择 $k$ 个元素: $\mathbb{F}: r_{w+1},\cdots, r_{w+k}$ ，将其添加到 witness 列后，再填充 $n-(w+k)$ 个 0，再将其插值为 witness 多项式，以此保证零知识性。

Permutation polynomials

对于置换多项式 $z$ ，最后的 $k$ 个值选取 $\mathbb{F}$ 中随机的值 $t_1, \cdots, t_k$ ，此时需要修改验证方程。

修改后的置换多项式 $z(X)$ 为：

$z(X) = L_1(X) + \sum_{i = 1}^{\color{blue}{n-k-2}} \left(L_{i+1} \prod_{j=1}^i \mathsf{frac}_{i,j} \right) + \color{blue}{t_1 L_{n-k}(X) + \ldots + t_k L_{n}(X) }$

上述 $z(X)$ 可以得到零知识证明属性，当 $k$ 个值被显示时。

由于最后 $k$ 不再满足置换约束，需要修改协议，即：
$\begin{aligned} & t(X) = \\ & (a(X)b(X)q_M(X) + a(X)q_L(X) + b(X)q_R(X) + c(X)q_O(X) + PI(X) + q_C(X)) \frac{1}{z_H(X)} \\ &+ ((a(X) + \beta X + \gamma)(b(X) + \beta k_1 X + \gamma)(c(X) + \beta k_2X + \gamma)z(X) \color{blue}{(X-h_{n-k}) \ldots (X-h_{n-1})(X-h_n)} ) \frac{\alpha}{z_{H}(X)} \\ & - ((a(X) + \beta S_{\sigma1}(X) + \gamma)(b(X) + \beta S_{\sigma2}(X) + \gamma)(c(X) + \beta S_{\sigma3}(X) + \gamma)z(X\omega) \color{blue}{(X-h_{n-k}) \ldots (X-h_{n-1})(X-h_n)}) \frac{\alpha}{z_{H}(X)} \\ & + (z(X)-1)L_1(X) \frac{\alpha^2}{z_H(X)} \\ & + \color{blue}{(z(X)-1)L_{n-k}(X) \frac{\alpha^3}{z_H(X)} } \end{aligned}$
修改后的置换检查条件变为：

For all $h \in H$ , $L_1(h)(Z(h) - 1) = 0$
For all $h \in \color{blue}{H\setminus \{h_{n-k}, \ldots, h_n\}}$ ,

$\begin{aligned} & Z(h)[(a(h) + \beta h + \gamma)(b(h) + \beta k_1 h + \gamma)(c(h) + \beta k_2 h + \gamma)] \\ &= Z(\omega h)[(a(h) + \beta S_{\sigma1}(h) + \gamma)(b(h) + \beta S_{\sigma2}(h) + \gamma)(c(h) + \beta S_{\sigma3}(h) + \gamma)] \end{aligned}$
For all $h \in H$ , $L_{n-k}(h)(Z(h) - 1) = 0$

多项式 $(X-h_{n-k})\cdots(X-h_{n-1})(X-h_n)$ 保护置换多项式检查排除最后 $k$ 行。

Final check

最终需要检查 $f(\zeta)=Z_{H}(\zeta)t(\zeta)$ ，实现PLONK 的验证。

若观察证明者在计算 $f(z)$ 的时候，会看到 $f$ 缺少两部分：

公开输入部分；
置换中的一些东西

对于置换，现有的是：
$\begin{align} -1 \cdot z(\zeta \omega) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot \\ (w[0](\zeta) + \beta \cdot \sigma[0](\zeta) + \gamma) \cdot \\ (w[1](\zeta) + \beta \cdot \sigma[1](\zeta) + \gamma) \cdot \\ (w[2](\zeta) + \beta \cdot \sigma[2](\zeta) + \gamma) \cdot \\ (w[3](\zeta) + \beta \cdot \sigma[3](\zeta) + \gamma) \cdot \\ (w[4](\zeta) + \beta \cdot \sigma[4](\zeta) + \gamma) \cdot \\ (w[5](\zeta) + \beta \cdot \sigma[5](\zeta) + \gamma) \cdot \\ \beta \cdot \sigma[6](x) \end{align}$

作为对照，需要用的有：

等式两边分别为：

$\begin{align} & z(\zeta) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot \\ & (w[0](\zeta) + \beta \cdot \text{shift}[0] \zeta + \gamma) \cdot \\ & (w[1](\zeta) + \beta \cdot \text{shift}[1] \zeta + \gamma) \cdot \\ & (w[2](\zeta) + \beta \cdot \text{shift}[2] \zeta + \gamma) \cdot \\ & (w[3](\zeta) + \beta \cdot \text{shift}[3] \zeta + \gamma) \cdot \\ & (w[4](\zeta) + \beta \cdot \text{shift}[4] \zeta + \gamma) \cdot \\ & (w[5](\zeta) + \beta \cdot \text{shift}[5] \zeta + \gamma) \cdot \\ & (w[6](\zeta) + \beta \cdot \text{shift}[6] \zeta + \gamma) \end{align}$
其中 $shift[0]=1$
并且

$\begin{align} & -1 \cdot z(\zeta \omega) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot \\ & (w[0](\zeta) + \beta \cdot \sigma[0](\zeta) + \gamma) \cdot \\ & (w[1](\zeta) + \beta \cdot \sigma[1](\zeta) + \gamma) \cdot \\ & (w[2](\zeta) + \beta \cdot \sigma[2](\zeta) + \gamma) \cdot \\ & (w[3](\zeta) + \beta \cdot \sigma[3](\zeta) + \gamma) \cdot \\ & (w[4](\zeta) + \beta \cdot \sigma[4](\zeta) + \gamma) \cdot \\ & (w[5](\zeta) + \beta \cdot \sigma[5](\zeta) + \gamma) \cdot \\ & (w[6](\zeta) + \beta \cdot \sigma[6](\zeta) + \gamma) \cdot \end{align}$

初始化时条件：

$$(z(\zeta) - 1) L_1(\zeta) \alpha^{PERM1}$$

累加器最后的验证条件：

   $$(z(\zeta) - 1) L_{n-k}(\zeta) \alpha^{PERM2}$$

通过对照比较，可以看出置换中缺少部分为：
$\begin{align} & -1 \cdot z(\zeta \omega) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot \\ & (w[0](\zeta) + \beta \cdot \sigma[0](\zeta) + \gamma) \cdot \\ & (w[1](\zeta) + \beta \cdot \sigma[1](\zeta) + \gamma) \cdot \\ & (w[2](\zeta) + \beta \cdot \sigma[2](\zeta) + \gamma) \cdot \\ & (w[3](\zeta) + \beta \cdot \sigma[3](\zeta) + \gamma) \cdot \\ & (w[4](\zeta) + \beta \cdot \sigma[4](\zeta) + \gamma) \cdot \\ & (w[5](\zeta) + \beta \cdot \sigma[5](\zeta) + \gamma) \cdot \\ & (w[6](\zeta) + \gamma) \end{align}$

所以最终我们需要检查恒等式： $f(\zeta) = Z_H(\zeta)t(\zeta)$ ，即如下所示(带颜色的表示缺失的部分)：
$\begin{align} & f(\zeta) + \color{darkgreen}{pub(\zeta)} + \\ & \color{darkred}{z(\zeta) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot} \\ & \color{darkred}{(w[0](\zeta) + \beta \zeta + \gamma) \cdot} \\ & \color{darkred}{(w[1](\zeta) + \beta \cdot \text{shift}[0] \zeta + \gamma) \cdot} \\ & \color{darkred}{(w[2](\zeta) + \beta \cdot \text{shift}[1] \zeta + \gamma) \cdot} \\ & \color{darkred}{(w[3](\zeta) + \beta \cdot \text{shift}[2] \zeta + \gamma) \cdot} \\ & \color{darkred}{(w[4](\zeta) + \beta \cdot \text{shift}[3] \zeta + \gamma) \cdot} \\ & \color{darkred}{(w[5](\zeta) + \beta \cdot \text{shift}[4] \zeta + \gamma) \cdot} \\ & \color{darkred}{(w[6](\zeta) + \beta \cdot \text{shift}[5] \zeta + \gamma) +} \\ & \color{blue}{- z(\zeta \omega) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot} \\ & \color{blue}{(w[0](\zeta) + \beta \cdot \sigma[0](\zeta) + \gamma) \cdot} \\ & \color{blue}{(w[1](\zeta) + \beta \cdot \sigma[1](\zeta) + \gamma) \cdot} \\ & \color{blue}{(w[2](\zeta) + \beta \cdot \sigma[2](\zeta) + \gamma) \cdot} \\ & \color{blue}{(w[3](\zeta) + \beta \cdot \sigma[3](\zeta) + \gamma) \cdot} \\ & \color{blue}{(w[4](\zeta) + \beta \cdot \sigma[4](\zeta) + \gamma) \cdot} \\ & \color{blue}{(w[5](\zeta) + \beta \cdot \sigma[5](\zeta) + \gamma) \cdot} \\ & \color{blue}{(w[6](\zeta) + \gamma) +} \\ & \color{purple}{(z(\zeta) - 1) L_1(\zeta) \alpha^{PERM1} +} \\ & \color{darkblue}{(z(\zeta) - 1) L_{n-k}(\zeta) \alpha^{PERM2}} \\ & = t(\zeta)(\zeta^n - 1) \end{align}$
在代码实现的时候进公式进行了调整，如下：
$\begin{align} & f(\zeta) + pub(\zeta) + \\ & z(\zeta) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot \\ & (w[0](\zeta) + \beta \cdot \text{shift}[0] \zeta + \gamma) \cdot \\ & (w[1](\zeta) + \beta \cdot \text{shift}[1] \zeta + \gamma) \cdot \\ & (w[2](\zeta) + \beta \cdot \text{shift}[2] \zeta + \gamma) \cdot \\ & (w[3](\zeta) + \beta \cdot \text{shift}[3] \zeta + \gamma) \cdot \\ & (w[4](\zeta) + \beta \cdot \text{shift}[4] \zeta + \gamma) \cdot \\ & (w[5](\zeta) + \beta \cdot \text{shift}[5] \zeta + \gamma) \cdot \\ & (w[6](\zeta) + \beta \cdot \text{shift}[6] \zeta + \gamma) + \\ & - z(\zeta \omega) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot \\ & (w[0](\zeta) + \beta \cdot \sigma[0](\zeta) + \gamma) \cdot \\ & (w[1](\zeta) + \beta \cdot \sigma[1](\zeta) + \gamma) \cdot \\ & (w[2](\zeta) + \beta \cdot \sigma[2](\zeta) + \gamma) \cdot \\ & (w[3](\zeta) + \beta \cdot \sigma[3](\zeta) + \gamma) \cdot \\ & (w[4](\zeta) + \beta \cdot \sigma[4](\zeta) + \gamma) \cdot \\ & (w[5](\zeta) + \beta \cdot \sigma[5](\zeta) + \gamma) \cdot \\ & (w[6](\zeta) + \gamma) + \\ & \color{darkred}{- t(\zeta)(\zeta^n - 1)} \\ & = \color{darkred}{(1 - z(\zeta)) L_1(\zeta) \alpha^{PERM1} +} \\ & \color{darkred}{(1 - z(\zeta)) L_{n-k}(\zeta) \alpha^{PERM2}} \\ \end{align}$
根据Lagrange的计算公式，可以将其调整为：
$\begin{align} & f(\zeta) + pub(\zeta) + \\ & z(\zeta) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot \\ & (w[0](\zeta) + \beta \cdot \text{shift}[0] \zeta + \gamma) \cdot \\ & (w[1](\zeta) + \beta \cdot \text{shift}[1] \zeta + \gamma) \cdot \\ & (w[2](\zeta) + \beta \cdot \text{shift}[2] \zeta + \gamma) \cdot \\ & (w[3](\zeta) + \beta \cdot \text{shift}[3] \zeta + \gamma) \cdot \\ & (w[4](\zeta) + \beta \cdot \text{shift}[4] \zeta + \gamma) \cdot \\ & (w[5](\zeta) + \beta \cdot \text{shift}[5] \zeta + \gamma) \cdot \\ & (w[6](\zeta) + \beta \cdot \text{shift}[6] \zeta + \gamma) + \\ & - z(\zeta \omega) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot \\ & (w[0](\zeta) + \beta \cdot \sigma[0](\zeta) + \gamma) \cdot \\ & (w[1](\zeta) + \beta \cdot \sigma[1](\zeta) + \gamma) \cdot \\ & (w[2](\zeta) + \beta \cdot \sigma[2](\zeta) + \gamma) \cdot \\ & (w[3](\zeta) + \beta \cdot \sigma[3](\zeta) + \gamma) \cdot \\ & (w[4](\zeta) + \beta \cdot \sigma[4](\zeta) + \gamma) \cdot \\ & (w[5](\zeta) + \beta \cdot \sigma[5](\zeta) + \gamma) \cdot \\ & (w[6](\zeta) + \gamma) + \\ & - t(\zeta)(\zeta^n - 1) \\ & = \color{darkred}{(1 - z(\zeta))[\frac{(\zeta^n - 1)}{n(\zeta - 1)} \alpha^{PERM1} + \frac{\omega^{n-k}(\zeta^n - 1)}{n(\zeta - \omega^{n-k})} \alpha^{PERM2}]} \end{align}$
最终的计算公式变为：
$\begin{align} & \color{darkred}{[} \\ & \; f(\zeta) + pub(\zeta) + \\ & \; z(\zeta) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot \\ & \; (w[0](\zeta) + \beta \cdot \text{shift}[0] \zeta + \gamma) \cdot \\ & \; (w[1](\zeta) + \beta \cdot \text{shift}[1] \zeta + \gamma) \cdot \\ & \; (w[2](\zeta) + \beta \cdot \text{shift}[2] \zeta + \gamma) \cdot \\ & \; (w[3](\zeta) + \beta \cdot \text{shift}[3] \zeta + \gamma) \cdot \\ & \; (w[4](\zeta) + \beta \cdot \text{shift}[4] \zeta + \gamma) \cdot \\ & \; (w[5](\zeta) + \beta \cdot \text{shift}[5] \zeta + \gamma) \cdot \\ & \; (w[6](\zeta) + \beta \cdot \text{shift}[6] \zeta + \gamma) + \\ & \; - z(\zeta \omega) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot \\ & \; (w[0](\zeta) + \beta \cdot \sigma[0](\zeta) + \gamma) \cdot \\ & \; (w[1](\zeta) + \beta \cdot \sigma[1](\zeta) + \gamma) \cdot \\ & \; (w[2](\zeta) + \beta \cdot \sigma[2](\zeta) + \gamma) \cdot \\ & \; (w[3](\zeta) + \beta \cdot \sigma[3](\zeta) + \gamma) \cdot \\ & \; (w[4](\zeta) + \beta \cdot \sigma[4](\zeta) + \gamma) \cdot \\ & \; (w[5](\zeta) + \beta \cdot \sigma[5](\zeta) + \gamma) \cdot \\ & \; (w[6](\zeta) + \gamma) + \\ & \; - t(\zeta)(\zeta^n - 1) \\ & \color{darkred}{] \cdot (\zeta - 1)(\zeta - \omega^{n-k})} & \\ & = \color{darkred}{(1 - z(\zeta))[\frac{(\zeta^n - 1)(\zeta - \omega^{n-k})}{n} \alpha^{PERM1} + \frac{\omega^{n-k}(\zeta^n - 1)(\zeta - 1)}{n} \alpha^{PERM2}]} \end{align}$
其中 $\alpha^{PERM0} = \alpha^{17}, \alpha^{PERM1} = \alpha^{18}, \alpha^{PERM2} = \alpha^{19}$ 。

Maller optimization

Maller optimization

由验证者构造如下的承诺：
$L(x) = f(x)-Z_H(\zeta)\cdot t(x)$
$L(x)$ 的承诺为：
$com(L) = com(f)-Z_H(\zeta)\cdot com(t)$
由于 $f$ 已知道，可以产生 $com(f)$ ，所以仅需要 $com(t)$ , 所以协议流程为：

Chunked polynomial

由于 $t$ 是一个非常大的多项式，会超出 $SRS$ 的大小，因此需要对其进行分块。

验证者需要生产 $L$ 分块的承诺，并通过 $\zeta^n$ 结合起来，可以定义 $L$ 为：
$L = L_0+x^nL_1+x^{2n}L_1+\cdots$
其中每个 $L_i$ 次数为 $n-1$ ，即：
$com(L) = com(L_0) + com(x^n \cdot L_1) + com(x^{2n} \cdot L_2) + \cdots$
可以得到：
$com(\tilde L) = com(L_0) + \zeta^n \cdot com(L_1) + \zeta^{2n} \cdot com(L_2) + \cdots$
对于证明者，可以生成以下的线性多项式：
$\tilde L(x) = 1 \cdot L_0(x) + \zeta^n \cdot L_1(x) + \zeta^{2n} \cdot L_2(x) + \cdots$
其和 $L(x)$ 在 $\zeta$ 的估值相同。

**Evaluation of L **

由于证明没有完整发送 $f$ 的承诺，验证者需要计算 $\tilde{L}(\zeta)$ , 它的值并不等于0，应该等于：
$\begin{align} & \tilde f(\zeta) - \tilde t(\zeta)(\zeta^n - 1) = \\ & \frac{1 - z(\zeta)}{(\zeta - 1)(\zeta - \omega^{n-k})}\left[ \frac{(\zeta^n - 1)(\zeta - \omega^{n-k})}{n} \alpha^{PERM1} + \frac{\omega^{n-k}(\zeta^n - 1)(\zeta - 1)}{n} \alpha^{PERM2} \right] \\ & - pub(\zeta) \\ & \; - z(\zeta) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot \\ & \; (w[0](\zeta) + \beta \cdot \text{shift}[0] \zeta + \gamma) \cdot \\ & \; (w[1](\zeta) + \beta \cdot \text{shift}[1] \zeta + \gamma) \cdot \\ & \; (w[2](\zeta) + \beta \cdot \text{shift}[2] \zeta + \gamma) \cdot \\ & \; (w[3](\zeta) + \beta \cdot \text{shift}[3] \zeta + \gamma) \cdot \\ & \; (w[4](\zeta) + \beta \cdot \text{shift}[4] \zeta + \gamma) \cdot \\ & \; (w[5](\zeta) + \beta \cdot \text{shift}[5] \zeta + \gamma) \cdot \\ & \; (w[6](\zeta) + \beta \cdot \text{shift}[6] \zeta + \gamma) + \\ & \; + z(\zeta \omega) \cdot zkpm(\zeta) \cdot \alpha^{PERM0} \cdot \\ & \; (w[0](\zeta) + \beta \cdot \sigma[0](\zeta) + \gamma) \cdot \\ & \; (w[1](\zeta) + \beta \cdot \sigma[1](\zeta) + \gamma) \cdot \\ & \; (w[2](\zeta) + \beta \cdot \sigma[2](\zeta) + \gamma) \cdot \\ & \; (w[3](\zeta) + \beta \cdot \sigma[3](\zeta) + \gamma) \cdot \\ & \; (w[4](\zeta) + \beta \cdot \sigma[4](\zeta) + \gamma) \cdot \\ & \; (w[5](\zeta) + \beta \cdot \sigma[5](\zeta) + \gamma) \cdot \\ & \; (w[6](\zeta) + \gamma) \\ \end{align}$
此时可以采用IPA 承诺，还需要：
$\tilde L(\zeta \omega) = \tilde f(\zeta \omega) - Z_H(\zeta) \cdot \tilde t(\zeta \omega)$
$\tilde L(\zeta \omega)$ 的值也要作为生成证明的一部分。

Kimchi protocol

整个Kimchi 协议的流程如下，主要分为三个过程：

多项式承诺；
多项式估值；
IPA 证明。

Source code

以 Generic test 为例，分析Kimchi 的开发实现过程。

系数表

let public = vec![Fp::from(3u8); 5];
let gates = create_circuit(0, public.len());

构建的系数表为：

	0	1	2	4	5	7	8	9
0	1
1	1
2	1
3	1
4	1
5	1	3	-1			-1	2
6	1	3	-1			-1	2
7	1	3	-1			-1	2
8	1	3	-1			-1	2
9	1	3	-1			-1	2
10	1	3	-1			-1	2
11	1	3	-1			-1	2
12	1	3	-1			-1	2
13	1	3	-1			-1	2
14	1	3	-1			-1	2
15	1			-3	1			-5
16	1			-3	1			-5
17	1			-3	1			-5
18	1			-3	1			-5
19	1			-3	1			-5
20	1			-3	1			-5
22	1			-3	1			-5
23	1			-3	1			-5
24	1			-3	1			-5
25	1			-3	1			-5

witness

// create witness
let mut witness: [Vec<Fp>; COLUMNS] = array_init(|_| vec![Fp::zero(); gates.len()]);
fill_in_witness(0, &mut witness, &public);

生成的witness为：

	0	1	2	3	4	6
0	3
1	3
2	3
3	3
4	3
5	11	23	80	11	23	506
6	11	23	80	11	23	506
7	11	23	80	11	23	506
8	11	23	80	11	23	506
9	11	23	80	11	23	506
10	11	23	80	11	23	506
11	11	23	80	11	23	506
12	11	23	80	11	23	506
13	11	23	80	11	23	506
14	3			5
15	3			5
16	3			5
17	3			5
18	3			5
19	3			5
20	3			5
21	3			5
22	3			5
24	3			5
24	3			5

ConstraintSystem

 let cs =ConstraintSystem::<Fp>::create(gates, lookup_tables, fp_sponge_params, public).unwrap();

生成的约束系统为：

pub struct ConstraintSystem<F: FftField> {
    // Basics
    // ------
    /// number of public inputs
    pub public: usize,               // 公开输入个数
    /// evaluation domains
    #[serde(bound = "EvaluationDomains<F>: Serialize + DeserializeOwned")]
    pub domain: EvaluationDomains<F>,    // 计算的定义域： d1 || d2
    /// circuit gates
    #[serde(bound = "CircuitGate<F>: Serialize + DeserializeOwned")]
    pub gates: Vec<CircuitGate<F>>,       // 所有的门电路

    // Polynomials over the monomial base
    // ----------------------------------
    /// permutation polynomial array
    #[serde_as(as = "[o1_utils::serialization::SerdeAs; PERMUTS]")]
    pub sigmam: [DP<F>; PERMUTS],       // sigma置换的多项式  

    // Coefficient polynomials. These define constant that gates can use as they like.
    // ---------------------------------------
    /// coefficients polynomials in evaluation form
    #[serde_as(as = "[o1_utils::serialization::SerdeAs; COLUMNS]")]
    pub coefficients8: [E<F, D<F>>; COLUMNS],  // 系统多项式

    // Generic constraint selector polynomials
    // ---------------------------------------
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub genericm: DP<F>,                       // 通用电路门选择多项式

    // Poseidon selector polynomials
    // -----------------------------
    /// poseidon constraint selector polynomial
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub psm: DP<F>,                            // Poseidon 约束选择多项式

    // Generic constraint selector polynomials
    // ---------------------------------------
    /// multiplication evaluations over domain.d4
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub generic4: E<F, D<F>>,                      //  通用门电路选择多项式

    // permutation polynomials
    // -----------------------
    /// permutation polynomial array evaluations over domain d1
    #[serde_as(as = "[o1_utils::serialization::SerdeAs; PERMUTS]")]
    pub sigmal1: [E<F, D<F>>; PERMUTS],                          // 置换多项式
    /// permutation polynomial array evaluations over domain d8
    #[serde_as(as = "[o1_utils::serialization::SerdeAs; PERMUTS]")]
    pub sigmal8: [E<F, D<F>>; PERMUTS],                        // 置换多项式
    /// SID polynomial
    #[serde_as(as = "Vec<o1_utils::serialization::SerdeAs>")]
    pub sid: Vec<F>,                                 // SID 多项式

    // Poseidon selector polynomials
    // -----------------------------
    /// poseidon selector over domain.d8
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub ps8: E<F, D<F>>,                        // poseidon 选择多项式

    // ECC arithmetic selector polynomials
    // -----------------------------------
    /// EC point addition selector evaluations w over domain.d4
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub complete_addl4: E<F, D<F>>,                        // EC 点加选择多项式
    /// scalar multiplication selector evaluations over domain.d8
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub mull8: E<F, D<F>>,                                   // 标量乘选择多项式 
    /// endoscalar multiplication selector evaluations over domain.d8
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub emull: E<F, D<F>>,                       // 自同态标量乘法选择多项式
    /// ChaCha indexes
    #[serde_as(as = "Option<[o1_utils::serialization::SerdeAs; 4]>")]
    pub chacha8: Option<[E<F, D<F>>; 4]>,                  // chacha选择多项式  
    /// EC point addition selector evaluations w over domain.d8
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub endomul_scalar8: E<F, D<F>>,                    // EC 点加选择多项式    

    /// wire coordinate shifts
    #[serde_as(as = "[o1_utils::serialization::SerdeAs; PERMUTS]")]
    pub shift: [F; PERMUTS],                         // Shift 参数
    /// coefficient for the group endomorphism
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub endo: F,

    /// random oracle argument parameters
    #[serde(skip)]
    pub fr_sponge_params: ArithmeticSpongeParams<F>,

    /// lookup constraint system
    #[serde(bound = "LookupConstraintSystem<F>: Serialize + DeserializeOwned")]
    pub lookup_constraint_system: Option<LookupConstraintSystem<F>>,

    /// precomputes
    #[serde(skip)]
    precomputations: OnceCell<Arc<DomainConstantEvaluations<F>>>,
}

预计算的结构体为：

pub struct DomainConstantEvaluations<F: FftField> {
    /// 1-st Lagrange evaluated over domain.d8
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub poly_x_d1: E<F, D<F>>,          // x 多项式
    /// 0-th Lagrange evaluated over domain.d4
    // TODO(mimoo): be consistent with the paper/spec, call it L1 here or call it L0 there
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub constant_1_d4: E<F, D<F>>,                  // 常量 1 多项式
    /// 0-th Lagrange evaluated over domain.d8
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub constant_1_d8: E<F, D<F>>,                      // 常量 1 多项式
    /// the polynomial that vanishes on the last four rows
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub vanishes_on_last_4_rows: E<F, D<F>>,            // vanishing 多项式
    /// zero-knowledge polynomial over domain.d8
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub zkpl: E<F, D<F>>,                                 // zk 多项式
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub zkpm: DP<F>,                                      // zk 多项式    
}

SRS

let mut srs = SRS::<Affine>::create(cs.domain.d1.size as usize);
srs.add_lagrange_basis(cs.domain.d1);
let srs = Arc::new(srs);

SRS 结构体为：

pub struct SRS<G: CommitmentCurve> {
    /// The vector of group elements for committing to polynomials in coefficient form
    #[serde_as(as = "Vec<o1_utils::serialization::SerdeAs>")]
    pub g: Vec<G>,                               // 多项式承诺的基
    /// A group element used for blinding commitments
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub h: G,               // 盲化因子基

    // TODO: the following field should be separated, as they are optimization values
    /// Commitments to Lagrange bases, per domain size
    #[serde(skip)]
    pub lagrange_bases: HashMap<usize, Vec<G>>,         // Lagrange 基
    /// Coefficient for the curve endomorphism
    #[serde(skip)]
    pub endo_r: G::ScalarField,                 // 自同态标量        
    /// Coefficient for the curve endomorphism
    #[serde(skip)]
    pub endo_q: G::BaseField,
}

ProverIndex

pub struct ProverIndex<G: CommitmentCurve> {
    /// constraints system polynomials
    #[serde(bound = "ConstraintSystem<ScalarField<G>>: Serialize + DeserializeOwned")]
    pub cs: ConstraintSystem<ScalarField<G>>,   // 约束系统

    /// The symbolic linearization of our circuit, which can compile to concrete types once certain values are learned in the protocol.
    #[serde(skip)]
    pub linearization: Linearization<Vec<PolishToken<ScalarField<G>>>>,  // 线性化的符号表示

    /// The mapping between powers of alpha and constraints
    #[serde(skip)]
    pub powers_of_alpha: Alphas<ScalarField<G>>,  // 用于组合各个多项式的 alpha 参数 

    /// polynomial commitment keys
    #[serde(skip)]
    pub srs: Arc<SRS<G>>,   // structed Reference String

    /// maximal size of polynomial section
    pub max_poly_size: usize,            

    /// maximal size of the quotient polynomial according to the supported constraints
    pub max_quot_size: usize,

    /// random oracle argument parameters
    #[serde(skip)]
    pub fq_sponge_params: ArithmeticSpongeParams<BaseField<G>>,  // sponge 参数
}

Lookup

/// Describes the desired lookup configuration.
#[derive(Clone, Serialize, Deserialize)]
pub struct LookupInfo<F> {
    /// A single lookup constraint is a vector of lookup constraints to be applied at a row.
    /// This is a vector of all the kinds of lookup constraints in this configuration.
    pub kinds: Vec<Vec<JointLookupSpec<F>>>,   
    //kinds是指三类：ChaCha0, ChaCha1, Chacha2； ChaChaFinal; Lookup;
    // Vec<JointLookupSpec<F>> 是一类Lookup的lookup的个数
    // 每个JointLookupSpec<F> 是指一个Lookup
  
    /// A map from the kind of gate (and whether it is the current row or next row) to the lookup
    /// constraint (given as an index into `kinds`) that should be applied there, if any.
    pub kinds_map: HashMap<(GateType, CurrOrNext), usize>,
    //主要映射到kinds的索引位置，上述三类分别对应0，1， 2 
  
    /// A map from the kind of gate (and whether it is the current row or next row) to the lookup
    /// table that is used by the gate, if any.
    pub kinds_tables: HashMap<(GateType, CurrOrNext), GateLookupTable>,
    // GateLookupTable 为 Xor 或者 None.
  
  
    /// The maximum length of an element of `kinds`. This can be computed from `kinds`.
    pub max_per_row: usize,
    // 主要指一行中lookup的最大个数， 对应 Vec<JointLookupSpec<F>>
  
    /// The maximum joint size of any joint lookup in a constraint in `kinds`. This can be computed from `kinds`.
    pub max_joint_size: u32,
    // 所有 lookup中 entry最多的数量，对应 JoinLookupSpec 的entry个数
    /// An empty vector.
    empty: Vec<JointLookupSpec<F>>,
}

ProverProof

/// The proof that the prover creates from a [ProverIndex] and a `witness`.
#[derive(Clone)]
pub struct ProverProof<G: AffineCurve> {
    /// All the polynomial commitments required in the proof
    pub commitments: ProverCommitments<G>,   //多项式承诺

    /// batched commitment opening proof
    pub proof: OpeningProof<G>,   //IPA 打开证明

    /// Two evaluations over a number of committed polynomials
    // TODO(mimoo): that really should be a type Evals { z: PE, zw: PE }
    pub evals: [ProofEvaluations<Vec<ScalarField<G>>>; 2],   // 多项式分别在\zeta 和 \zeta\omega 的值 

    /// Required evaluation for [Maller's optimization](https://o1-labs.github.io/mina-book/crypto/plonk/maller_15.html#the-evaluation-of-l)
    pub ft_eval1: ScalarField<G>,  // \tilde{L}(\zeta \omega) 的值

    /// The public input
    pub public: Vec<ScalarField<G>>,   // 公开输入的值

    /// The challenges underlying the optional polynomials folded into the proof
    pub prev_challenges: Vec<(Vec<ScalarField<G>>, PolyComm<G>)>,
}

其中 ProverCommitment 为：

#[derive(Clone)]
pub struct ProverCommitments<G: AffineCurve> {
    /// The commitments to the witness (execution trace)
    pub w_comm: [PolyComm<G>; COLUMNS],    // witness 多项式承诺
    /// The commitment to the permutation polynomial
    pub z_comm: PolyComm<G>,               // 置换多项式z(x) 的承诺
    /// The commitment to the quotient polynomial
    pub t_comm: PolyComm<G>,                 // 商多项式 t(x) 的承诺
    /// Commitments related to the lookup argument
    pub lookup: Option<LookupCommitments<G>>,  // 查找多项式的承诺
}

Verifier Index

#[serde_as]
#[derive(Serialize, Deserialize)]
pub struct VerifierIndex<G: CommitmentCurve> {
    /// evaluation domain
    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
    pub domain: D<ScalarField<G>>,      //定义域
    /// maximal size of polynomial section
    pub max_poly_size: usize,            //多项式最大的次数
    /// maximal size of the quotient polynomial according to the supported constraints
    pub max_quot_size: usize,  // 商多项式最大的次数
    /// polynomial commitment keys
    #[serde(skip)]
    pub srs: Arc<SRS<G>>,  // Structed Reference Strinng

    // index polynomial commitments
    /// permutation commitment array
    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
    pub sigma_comm: [PolyComm<G>; PERMUTS],    // 置换的\sigma 多项式承诺     
    /// coefficient commitment array
    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
    pub coefficients_comm: [PolyComm<G>; COLUMNS],   // 系数多项式承诺
    /// coefficient commitment array
    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
    pub generic_comm: PolyComm<G>,             //通用电路选择子多项式承诺

    // poseidon polynomial commitments
    /// poseidon constraint selector polynomial commitment
    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
    pub psm_comm: PolyComm<G>,                     // poseidon 选择子多项式承诺

    // ECC arithmetic polynomial commitments
    /// EC addition selector polynomial commitment
    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
    pub complete_add_comm: PolyComm<G>,      // EC 点加电门选择子多项式承诺
    /// EC variable base scalar multiplication selector polynomial commitment
    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
    pub mul_comm: PolyComm<G>,                 // EC 变基 标量乘选择子多项式承诺
    /// endoscalar multiplication selector polynomial commitment
    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
    pub emul_comm: PolyComm<G>,               // 自同态标量乘 选择子多项式承诺
    /// endoscalar multiplication scalar computation selector polynomial commitment
    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
    pub endomul_scalar_comm: PolyComm<G>,

    /// Chacha polynomial commitments
    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
    pub chacha_comm: Option<[PolyComm<G>; 4]>,   // chach 多项式承诺

    /// wire coordinate shifts
    #[serde_as(as = "[o1_utils::serialization::SerdeAs; PERMUTS]")]
    pub shift: [ScalarField<G>; PERMUTS],                  // 置换偏移量
    /// zero-knowledge polynomial
    #[serde(skip)]
    pub zkpm: DensePolynomial<ScalarField<G>>,      // 置换多项式实现zk的多项式
    // TODO(mimoo): isn't this redundant with domain.d1.group_gen ?
    /// domain offset for zero-knowledge
    #[serde(skip)]
    pub w: ScalarField<G>,     // 基域生成元
    /// endoscalar coefficient
    #[serde(skip)]
    pub endo: ScalarField<G>,

    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
    pub lookup_index: Option<LookupVerifierIndex<G>>,        // Lookup 相关的承诺

    #[serde(skip)]
    pub linearization: Linearization<Vec<PolishToken<ScalarField<G>>>>,  // 线性化的符号化表示
    /// The mapping between powers of alpha and constraints
    #[serde(skip)]
    pub powers_of_alpha: Alphas<ScalarField<G>>, //alpha 常量

    // random oracle argument parameters
    #[serde(skip)]
    pub fr_sponge_params: ArithmeticSpongeParams<ScalarField<G>>,  // sponge 参数
    #[serde(skip)]
    pub fq_sponge_params: ArithmeticSpongeParams<BaseField<G>>,
}

参考

https://minaprotocol.com/zh-hans

https://docs.minaprotocol.com/static/pdf/technicalWhitepaper.pdf

https://docs.minaprotocol.com/en

https://minaexplorer.com/

https://github.com/o1-labs/proof-systems

https://o1-labs.github.io/proof-systems/

https://github.com/MinaProtocol/mina

https://docs.minaprotocol.com/en/developers/sandbox-node

https://github.com/ChainSafe/mina-rs

https://mp.weixin.qq.com/s/sYe7fQSSy6Ix9xIYWMNWfw

https://mp.weixin.qq.com/s/mvh4gHaVDvdwIe157UTLZw

https://eprint.iacr.org/2022/086

Mina Kimchi

Roots-check

Aggregation

Custom gates

Permutation

Lookup

Polynomials commitment

Zero knowledge

Final check

Maller optimization

Kimchi protocol

Source code

Lookup

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

	0	1	2	4	5	7	8	9
0	1
1	1
2	1
3	1
4	1
5	1	3	-1			-1	2
6	1	3	-1			-1	2
7	1	3	-1			-1	2
8	1	3	-1			-1	2
9	1	3	-1			-1	2
10	1	3	-1			-1	2
11	1	3	-1			-1	2
12	1	3	-1			-1	2
13	1	3	-1			-1	2
14	1	3	-1			-1	2
15	1			-3	1			-5
16	1			-3	1			-5
17	1			-3	1			-5
18	1			-3	1			-5
19	1			-3	1			-5
20	1			-3	1			-5
22	1			-3	1			-5
23	1			-3	1			-5
24	1			-3	1			-5
25	1			-3	1			-5

	0	1	2	3	4	6
0	3
1	3
2	3
3	3
4	3
5	11	23	80	11	23	506
6	11	23	80	11	23	506
7	11	23	80	11	23	506
8	11	23	80	11	23	506
9	11	23	80	11	23	506
10	11	23	80	11	23	506
11	11	23	80	11	23	506
12	11	23	80	11	23	506
13	11	23	80	11	23	506
14	3			5
15	3			5
16	3			5
17	3			5
18	3			5
19	3			5
20	3			5
21	3			5
22	3			5
24	3			5
24	3			5

	0	1	2	4	5	7	8	9
0	1
1	1
2	1
3	1
4	1
5	1	3	-1			-1	2
6	1	3	-1			-1	2
7	1	3	-1			-1	2
8	1	3	-1			-1	2
9	1	3	-1			-1	2
10	1	3	-1			-1	2
11	1	3	-1			-1	2
12	1	3	-1			-1	2
13	1	3	-1			-1	2
14	1	3	-1			-1	2
15	1			-3	1			-5
16	1			-3	1			-5
17	1			-3	1			-5
18	1			-3	1			-5
19	1			-3	1			-5
20	1			-3	1			-5
22	1			-3	1			-5
23	1			-3	1			-5
24	1			-3	1			-5
25	1			-3	1			-5

	0	1	2	3	4	6
0	3
1	3
2	3
3	3
4	3
5	11	23	80	11	23	506
6	11	23	80	11	23	506
7	11	23	80	11	23	506
8	11	23	80	11	23	506
9	11	23	80	11	23	506
10	11	23	80	11	23	506
11	11	23	80	11	23	506
12	11	23	80	11	23	506
13	11	23	80	11	23	506
14	3			5
15	3			5
16	3			5
17	3			5
18	3			5
19	3			5
20	3			5
21	3			5
22	3			5
24	3			5
24	3			5

	0	1	2	4	5	7	8	9
0	1
1	1
2	1
3	1
4	1
5	1	3	-1			-1	2
6	1	3	-1			-1	2
7	1	3	-1			-1	2
8	1	3	-1			-1	2
9	1	3	-1			-1	2
10	1	3	-1			-1	2
11	1	3	-1			-1	2
12	1	3	-1			-1	2
13	1	3	-1			-1	2
14	1	3	-1			-1	2
15	1			-3	1			-5
16	1			-3	1			-5
17	1			-3	1			-5
18	1			-3	1			-5
19	1			-3	1			-5
20	1			-3	1			-5
22	1			-3	1			-5
23	1			-3	1			-5
24	1			-3	1			-5
25	1			-3	1			-5

	0	1	2	3	4	6
0	3
1	3
2	3
3	3
4	3
5	11	23	80	11	23	506
6	11	23	80	11	23	506
7	11	23	80	11	23	506
8	11	23	80	11	23	506
9	11	23	80	11	23	506
10	11	23	80	11	23	506
11	11	23	80	11	23	506
12	11	23	80	11	23	506
13	11	23	80	11	23	506
14	3			5
15	3			5
16	3			5
17	3			5
18	3			5
19	3			5
20	3			5
21	3			5
22	3			5
24	3			5
24	3			5