Mina Kimchi

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

Kimchi 协议主要有三种证明：

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

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

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

Roots-check

对于一个多项式 ，次数为 ， 然后验证 , 其中 为某个集合。

若对每个 分别验证，会比较麻烦。因此 集合通过 vanishing polynomial 定义，即：

此时只需要验证 可以整除 即可，即存在次数为 的 quotient polynomial：

若证明者提供一个商多项式，并验证 ， 根据Schwartz-Zippel定理，在 集合上成立。

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

Aggregation

上面只介绍 一个多项式在某个集合等式关系成立，可以采用聚合，验证多个多项式在某个集合上成立，采用powers-of-alpha 技术，即选取随机的 , 验证：

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 通用电路：

1. l r o l r

CompleteAdd 椭圆曲线加法电路:

1. x21_inv x2 x1 same_x
2. same_x x2 x1
3. same_x s y1 x1 same_x x2 x1 s y2 + y1
4. x1 x2 x3 s
5. s x1 x3 y1 y3
6. y2 y1 same_x inf
7. y2 y1 inf_z inf

ExamplePairs 元素对示例电路:

1. a e
2. i o
3. u y

ExampleTriples 三元组示例电路:

1. a b c

2. d e f

3. g h i

4. j k l

5. m n o

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

Generic:

1. w0 w1 w2 w0 w1

CompleteAdd:

1. w10 w2 w0 w7
2. w7 w2 w0
3. w7 w8 w1 w0 w7 w2 w0 w8 w3 + w1
4. w0 w2 w4 w8
5. w8 w0 w4 w1 w4
6. w3 w1 w7 w6
7. w3 w1 w9 w6

ExamplePairs:

1. w0 w1
2. w2 w3
3. w4 w5

ExampleTriples:

1. w0 w1 w2
2. w3 w4 w5
3. w6 w7 w8
4. w9 w10 w11
5. w12 w13 w14

对于每一列的元素进行Lagrange 插值，得到多项式： ，

可以得到：

Generic:

1. 

CompleteAdd:

1. 
2. 
3. 
4. 
5. 
6. 
7. 

ExamplePairs:

1. 
2. 
3. 

ExampleTriples:

1. 
2. 
3. 
4. 
5. 

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

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

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

然后验证，随机值 \ ，则可以使验证者确信：

证明者知道多项式 , 在 值皆为0.

Permutation

对于两个长度为 的序列和, 证明者要证明, , 为某个置换，协议过程如下：

1. 验证者发送随机值 给证明者；

2. 证明者构造两个新的序列： 和, 其中
   

3. 证明者计算新的序列, 其中
   
   即
   
   即为所谓的grand product。

   证明者将 序列发给验证者。

4. 验证者检查以下方程：
   
   其中表示单位元的根，表示对序列的多项式插值。

若验证通过， 则验证者确信成立， 。

Lookup

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

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

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

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

• 
• 

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

• 
• 
• 
• 

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

• init:

• Final:

• 对于

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

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

Kimchi 使用4位的查找表，有 行。

例如，对于下面的查询，可以验证

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

其对应的 grand product argument 为：

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

row	query selector
0	1
1	0

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

采用如下方式构造，若某一行没有表查询，用假的查询 表示：

s 排序

向量 的长度为：

若向量 的长度大于定义域大小 ， 可以将 划分为多个长度为 的向量，此时对 排序为两种方式：

• Zig-zag 技术： 将 划分为多个列，例如 , ， 此时分子可以写为：

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

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

此时分子表示为：

蛇形的 U 型约束为：

若存在 , 其表示为：

并且需要添加一个U 型约束：

Polynomials commitment

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

<img src="https://o1-labs.github.io/proof-systems/img/polycom.png" alt="img" style="zoom: 33%;" />

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

给定两个已经承诺（hash值）的向量 和 ， 长度为，证明其内积

可以将多项式的计算转化为内积形式，例如对于多项式 ,

定义 , 则

IPA 协议描述

若证明知道一个私有的向量：

公开的参数有：

• , 用于Pedersen hashing 基；
• , 为 的承诺；
• 为 的幂，
• 内积的结果为：

证明的流程如下图：

1. 证明者发送多项式 的承诺；
2. 验证者发送点 ， 要求证明计算 , 为了让证明者生成证明，验证者需要发送一个随机挑战 ;
3. 证明者发送计算的结果 和 证明，给验证者。

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

• 
• 
• 

证明问题约减为： ， 大小变为原先的一半。

此时

为了计算新的承诺，验证者需要：

• 前一个承诺 ;
• ;
• 两个曲线上点的点 和

新的内积变为：

和 类似，验证者需要利用先前的 重新计算 ，

最终，证明变成：

• 向量 ， 大小是 的一半；
• 椭圆曲线点
• 标量

HALO 优化

Zcash HALO 对IPA 进行了优化，转化为如下形式：

类似地，

具体的约减方式为：

进一步可以写为：

此时验证验证者除了 ， 只需要两个点：

• 
• 

以此递归，经过 轮后，得到最后的承诺 ,

验证者检查：

验证者需要重新计算 和 ，

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

**zero-knowledge **

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

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

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

• 
• 

最终打开的承诺为：

使用 和最终盲化的值 ， 和重构的 和 ， 打开承诺：

其中 为 。

此时证明构成为：

• 每一轮有2个椭圆曲线点 和 ；
• 一个标量 ；
• 一个盲化因子标量 .

最后，还需要证明者隐藏 ， 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

令 为PLONK多项式的行数，列的 witness 值为： ， 为最接近 的二次幂，.

随机选择 个元素: ， 将其添加到 witness 列后，再填充 个 0， 再将其插值为 witness 多项式， 以此保证零知识性。

Permutation polynomials

对于置换多项式 ， 最后的 个值选取 中随机的值 ， 此时需要修改验证方程。

修改后的置换多项式 为：

上述 可以得到零知识证明属性，当 个值被显示时。

由于最后 不再满足置换约束，需要修改协议，即：

修改后的置换检查条件变为：

• For all ,

• For all ,

  

• For all ,

多项式 保护置换多项式检查排除最后 行。

Final check

最终需要检查 ， 实现PLONK 的验证。

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

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

对于置换，现有的是：

作为对照，需要用的有：

1. 等式两边分别为：

   
   其中

2. 并且

3. 初始化时条件：

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

4. 累加器最后的验证条件：

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

通过对照比较，可以看出置换中缺少部分为：

所以最终我们需要检查恒等式： ， 即如下所示(带颜色的表示缺失的部分)：

在代码实现的时候进公式进行了调整，如下：

根据Lagrange的计算公式，可以将其调整为：

最终的计算公式变为：

其中 。

Maller optimization

Maller optimization

由验证者构造如下的承诺：

的承诺为：

由于 已知道，可以产生 ， 所以仅需要 , 所以协议流程为：

Chunked polynomial

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

验证者需要生产 分块的承诺， 并通过 结合起来，可以定义 为：

其中每个 次数为 ， 即：

可以得到：

对于证明者，可以生成以下的线性多项式：

其和 在 的估值相同。

**Evaluation of L **

由于证明没有完整发送 的承诺，验证者需要计算 , 它的值并不等于0， 应该等于：

此时可以采用IPA 承诺，还需要：

的值也要作为生成证明的一部分。

Kimchi protocol

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

1. 多项式承诺；
2. 多项式估值；
3. IPA 证明。

Source code

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

系数表

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

构建的系数表为：

	0	1	2	3	4	5	6	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	7	8	9	10	11	12	13	14	15
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