Mina Kimchi SNARK 代码解析

1. 引言

Mina系列博客有：

• Mina概览
• Mina的支付流程
• Mina的zkApp
• Mina中的Pasta（Pallas和Vesta）曲线
• Mina中的Schnorr signature
• Mina中的Pickles SNARK
• Mina中的Kimchi SNARK
• Mina中的Poseidon hash

Kimchi SNARK 代码实现见：

• https://github.com/o1-labs/proof-systems（Rust语言）

在该代码库中，主要包括的模块有：

• 1）Cairo模块：为提供proofs of computation的StarkWare 框架。可使用Cairo语言来编写程序，然后将编译的字节码传给Stark Prover。最初的 Cairo实现 采用Python编写。而在此，提供了Rust版本编写的Cairo，可使用Kimchi zk-SNARK来证明statements。将基于Cairo的证明系统称为Turshi。在代码中包含了一系列的测试用例来对比 [Rust版本的Cairo——Turshi] 与 [Cairo playground] 二者的一致性。同时，也会检查实际运行程序的constraints。
• 2）Curves模块：为当前使用的pasta曲线。
• 3）Groupmap模块：用于将elliptic curve element转换为field element。
• 4）Oracle模块：实现了Poseidon hash函数。详细可参看博客Mina中的Poseidon hash。
• 5）Hasher模块：为针对Oracle模块封装的Mina hash接口。在Oracle模块中实现了2个版本的Poseidon hash函数，分别为legacy版本和kimchi experimental版本。提供的ScalarChallenge供zk-SNARK中生成非交互式challenge使用。
• 6）OCaml模块：提供了ocaml-gen工具来将Rust代码编译为OCaml bindings。
• 7）Poly-commitment模块：实现了多项式承诺。
• 8）Signer模块：实现了 Mina针对Pallas Pasta曲线的 Schnorr签名算法 接口。由于Poseidon hash函数实现了legacy版本和kimchi experimental版本，因此相应的签名机制也分为了legacy 和 experimental kimchi版本。
• 9）Tools模块：包含了Kimchi-visu可视化工具，可帮助以HTML table的形式来展示circuit。
• 10）Utils模块：包含了一些有用的函数和traits。
• 11）Kimchi模块：为可证明程序正确执行的基于Plonk的通用zk-SNARK证明系统。

2. Cairo模块

Cairo模块内代码会：

• 运行a bytecode compiled Cairo program
• 生成相应的memory instantiation

Cairo中：

• 用某些代码来表示Cairo指令及其分解
• 以构成整个程序的计算步骤来表示相应的逻辑

Cairo模块中包含多个子模块：

• 1）flags：定义了使步骤更易读的一些常量。当指向单个bit标志时，仅需要1个常量。
• 2）helper：包含了对Cairo有用的协议field helper。
• 3）memory：表示Cairo memory，包含了占据前几个entries的compiled Cairo program。
• 4）runner：表示以一系列连续的执行步骤来运行一个Cairo程序，每个步骤定义了Cairo指令的运行逻辑。
• 5）word：Cairo语言原生支持模为 0 x 800000000001100000000000000000000000000000000001 = 2 251 + 17 ∗ 2 192 + 1 0x800000000001100000000000000000000000000000000001=2^{251}+17*2^{192}+1 0x800000000001100000000000000000000000000000000001=2251+17∗2192+1的有限域内的field element。Pallas曲线有255位，因此Cairo原生指令将适用。这意味着Rust版本的Cairo实现 比 Python版本实现 可为immediate value提供更大的域。

3. Groupmap模块

其实质为针对椭圆曲线 E : y 2 = x 3 + a x + b E:y^2=x^3+ax+b E:y2=x3+ax+b over filed F q \mathbb{F}_q Fq​，将某 t ∈ F q t\in \mathbb{F}_q t∈Fq​映射为曲线 E E E上有效点 ( x , y ) (x,y) (x,y)，其中 x , y ∈ F q x,y\in\mathbb{F}_q x,y∈Fq​。

Groupmap对应的OCaml实现见：

• https://github.com/o1-labs/snarky/blob/2e9013159ad0d1df0af681735b89518befc4be11/group_map/group_map.ml#L4

实际算法实现参考的论文有：

• SvdW06：Shallue和van de Woestijne 2006年论文《Construction of rational points on elliptic curves over finite fields》。
• WB19：Wahby和Dan Boneh 2019年论文《Fast and simple constant-time hashing to the BLS12-381 elliptic curve》

4. Poly-commitment模块

Poly-commitment模块中包含以下子模块：

• 1）chunked子模块。其实是根据Horner rule将 p ( x ) = a 0 + a 1 ∗ x + a 2 ∗ x 2 + a 3 ∗ x 3 + a 4 ∗ x 4 + . . . + a n x n p(x) = a_0 + a_1*x + a_2*x^2 + a_3*x^3 + a_4*x^4 + ...+a_nx^n p(x)=a0​+a1​∗x+a2​∗x2+a3​∗x3+a4​∗x4+...+an​xn 优化为 p ( x ) = a 0 + x ∗ ( a 1 + x ∗ ( a 2 + x ∗ ( a 3 + x ∗ ( a 4 + . . . x ∗ ( a n − 1 + x ∗ ( a n + x ∗ 0 ) ) ) ) ) p(x) = a_0 + x*(a_1 + x*(a_2 + x*(a_3 + x*(a_4 + ... x*(a_{n-1} + x*(a_n+x*0))))) p(x)=a0​+x∗(a1​+x∗(a2​+x∗(a3​+x∗(a4​+...x∗(an−1​+x∗(an​+x∗0)))))，关键代码为：【要比https://github.com/lovesh/amcl_rust_wrapper中的实现优美。】

	/// Multiplies each commitment chunk of f with powers of zeta^n
    /// Note that it ignores the shifted part.
    // TODO(mimoo): better name for this function
    pub fn chunk_commitment(&self, zeta_n: C::ScalarField) -> Self {
        let mut res = C::Projective::zero();
        // use Horner's to compute chunk[0] + z^n chunk[1] + z^2n chunk[2] + ...
        // as ( chunk[-1] * z^n + chunk[-2] ) * z^n + chunk[-3]
        // (https://en.wikipedia.org/wiki/Horner%27s_method)
        for chunk in self.unshifted.iter().rev() {
            res *= zeta_n;
            res.add_assign_mixed(chunk);
        }

        PolyComm {
            unshifted: vec![res.into_affine()],
            shifted: self.shifted,
        }
    }

• 2）combine子模块：实现了一些批量曲线运算，如batch_add_assign_in_place等运算，支持并行曲线运算且避免了在每个算法中重新分配临时数组。借助batch inversion 算法，可将计算数组内所有元素的倒数的运算开销降为 每个元素仅需3次乘法运算。
• 3）srs子模块：实现了Marlin structured reference string原语。其实就是non trusted setup方式来生成随机的generators G ⃗ , h \vec{G},h G ,h以及lagrange_bases， endo_r和endo_q值。
• 4）evaluation_proof子模块：针对srs实现相应的open和challenge函数。
• 5）commitment子模块：实现了基于Dlog的多项式承诺机制，支持：
  • 5.1）以多项式的最大degree进行commit。
  • 5.2）在指定点进行批量open，生成batched opening proof。
  • 5.3）批量验证batched opening proofs。【即支持批量open多个不同的点。】

Mina的polynomial commitment为类似Bulletproofs类型的，结合了以下论文的算法做的实现：

• （1）2020年 PCD论文 附录A.1中描述的多项式承诺机制。
• （2）2019年 Halo论文 第3.1节中描述的zero-knowledge opening。

相关博客有：

• proof-carrying data from accumulation schemes学习笔记
• Bulletproofs: Short Proofs for Confidential Transactions and More学习笔记
• Bulletproofs 代码解析
• Halo: Recursive Proof Composition without a Trusted Setup 学习笔记
• Halo代码解析

5. Kimchi-visu可视化工具

调用方法为：

kimchi_visu::visu(&index, Some(witness));

也可直接复用tools/kimchi-visu/src/main.rs中的实现，然后运行：

$ cargo run --bin kimchi-visu

Kimchi-visu可视化工具会将circuit和constraints信息以HTML的形式展示：

6. Utils模块

Utils模块中包含了一些有用的函数和traits：

• 1）dense_polynomial：为arkworks的DensePolynomial增加了一些有用的函数。
• 2）evaluations：为arkworks的Evaluations增加了一些有用的函数。
• 3）field_helpers：基于field扩展出的一些函数。
• 4）hasher：提供了CryptoDigest trait，为hash运算提供了通用接口。
• 5）serialization：为arkworks中实现了[CanonicalSerialize] 和 [CanonicalDeserialize] 的一些类型实现了序列化和反序列化函数。
• 6）types：定义了一些通用类型。

7. Kimchi模块

Kimchi为可证明程序正确执行的基于Plonk的通用zk-SNARK证明系统。 采用cargo criterion进行bench：

$ cargo criterion -p kimchi --bench proof_criterion