零知识证明 - libsnark源代码分析 | 深入浅出区块链 | 技术博客 - JOYK Joy of Geek, Geek News, Link all geek

libsnark 源代码，建议想深入零知识证明的小伙伴都读一读。Bellman 库主要围绕 Groth16 算法，libsnark 给出了 SNARK 相关算法的全貌，各种 Relation，Language，Proof System。为了更好的生成 R1CS 电路，libsnark 抽象出 protoboard 和 gadget，方便开发者快速搭建电路。

本文中使用的 libsnark 源代码的最后一个 commit 如下：

commit 477c9dfd07b280e42369f82f89c08416319e24ae
Author: Madars Virza <[email protected]>
Date:   Tue Jun 18 18:43:12 2019 -0400

    Document that we also implement the Groth16 proof system.

1. 源代码目录

源代码在 libsnark 目录下：

common - 定义和实现了一些通用的数据结构，例如默克尔树，稀疏向量等等。

relations - relation 描述了“约束”关系。除了我们通常说的 R1CS 外，还有很多其他约束的描述语言。

reductions - 各种不同描述语言之间的转化。

knowledge_commit - 在 multiexp 的基础上，引入 pair 的概念，两个基点一个系数，计算结果称为一个 pair。

zk_proof_systems - 零知识证明中的各种证明系统（包括 Groth16，GM17 等等）。

gadgetlib1/gadgetlib2 - 为了更方便的构建 R1CS，libsnark 抽象出一层 gadget。已有的 gadget，可以方便地整合搭建出新的电路。

2. Relation

需要零知识证明的问题都是 NP 问题。NP 问题中有一类问题 NPC（NP-complete）问题。所有的 NP 问题都可以转化为一个 NPC 问题。只要有一个 NPC 问题能多项式时间内解决，所有的 NP 问题都能多项式时间内解决。描述一个 NPC 问题，有多种方式。描述 NPC 问题的方式，称为“language”。Relation 指的是一个 NPC 问题和该问题的解的关系。

libsnark 库总结了几种描述语言：

constraint satisfaction problem 类
- R1CS - Rank-1 Constraint System
- USCS - Unitary-Square Constraint System
circuit satisfaction problem 类
- BACS - Bilinear Arithmetic Circuit Satisfiability
- TBCS - Two-input Boolean Circuit Satisfiability
ram computation 类

RAM 是 Random Access Machine 的缩写。libsnark 总结了两种 RAM 计算框架：
- tinyRAM
- fooRAM
arithmetic program 类
- QAP - Quadratic Arithmetic Program（GGPR13）
- SQP - Square Arithmetic Program（GM17）
- SSP - Square Span Program (DFGK14)

先介绍实现各种语言中需要的“variable” （variable.hpp/variable.tcc)，再详细介绍 R1CS 以及 QAP 语言。

2.1 variable

 template <typename FieldT>

 class variable {
     public:
        var_index_t index;
        ...
 };

varible 的定义非常简单，描述一个 variable，只需要记录一个 varible 对应的标号就行了。比如对应编号为 index 的 variable，表示的是 x_{index}变量。

2.2 linear_term

linear_term 描述了一个线性组合中的一项。线性组合中的一项由变量以及对应的系数组成：

template <typename FieldT>
class linear_term {
 public:
     var_index_t index;
     FieldT coeff;
     ...
 };

2.3 linear_combination

linear_combination 描述了一个完整的线性组合。一个 linear combination 由多个 linear term 组成：

 template <typename FieldT>
 class linear_combination {
     public:
        std::vector<linear_term<FieldT> > terms;
 ...
 };

2.4 R1CS

R1CS 定义在 constraint_satisfaction_problems/r1cs/r1cs.hpp。R1CS 约束就是满足以下形式的一个表达式：

< A , X > * < B , X > = < C , X >

X 是所有变量组合的向量，A/B/C 是和 X 等长的向量。<,> 代表的是点乘。一个 R1CS 系统由多个 R1CS 约束组成。

R1CS 约束定义为：

 template <typename FieldT>
 class r1cs_constraint {
     public:
         linear_combination<FieldT> a, b, c;
 ...
 };

一个 R1CS 约束，可以由 a/b/c 三个 linear_combination 表示。一个 R1CS 系统中的所有变量的赋值，又分成两部分：primary input 和 auxiliary input。primary 就是"statement", auxiliary 就是“witness”。

 template<typename FieldT>
 using r1cs_primary_input = std::vector<FieldT>;
 template<typename FieldT>
 using r1cs_auxiliary_input = std::vector<FieldT>;

一个 R1CS 系统，包括多个 R1CS 约束。当然，每个约束的向量的长度是固定的（primary input size + auxiliary input size + 1）。

 template<typename FieldT>
 class r1cs_constraint_system {
 public:
     size_t primary_input_size;
     size_t auxiliary_input_size;
     std::vector<r1cs_constraint<FieldT> > constraints;
     ...
}

2.5 QAP

QAP 定义在 arithmetic_programs/qap/qap.hpp。libsnark 采用的 QAP 的公式是：A*B-C=H*Z。

 template<typename FieldT>
 class qap_instance {
 private:
     size_t num_variables_;
     size_t degree_;
     size_t num_inputs_;
 public:
     std::shared_ptr<libfqfft::evaluation_domain<FieldT> > domain;
     std::vector<std::map<size_t, FieldT> > A_in_Lagrange_basis;
     std::vector<std::map<size_t, FieldT> > B_in_Lagrange_basis;
     std::vector<std::map<size_t, FieldT> > C_in_Lagrange_basis;
}

num_bariables_表示 QAP 电路的变量的个数。num_inputs_表示 QAP 电路的"statement"对应变量的个数。degree_表示 A/B/C 中每个多项式的阶的个数（和电路的门的个数相关）。

domain 是计算傅立叶变换/反傅立叶变换的引擎，由 libfqfft 库实现。

何为 Lagrange basis？

给定一系列的 x 和 y 的对应关系，通过拉格朗日插值的方式，可以确定多项式： p(x) = y_0l_0(x) + y_1l_1(x) + ... + y_nl_n(x) 其中 l_0(x), l_1(x), ... l_n(x)就称为拉格朗日 basis。

A_in_Lagrange_basis/B_in_Lagrange_basis/C_in_Lagrange_basis 把一个电路中每个变量不同门的值整理在一起。举个例子，如下是 x^3+x+5 的电路对应的 R1CS 的约束：

该电路对应的 A_in_Lagrange_basis/B_in_Lagrange_basis/C_in_Lagrange_basis 为：

qap_instance 描述的是一个 QAP 电路，A/B/C 对应的多项式表达式（虽然是用 Lagrange basis 表示）。A/B/C 多项式在一个点上的结果，用 qap_instance_evaluation 表示：

 template<typename FieldT>
 class qap_instance_evaluation {
 private:
     size_t num_variables_;
     size_t degree_;
     size_t num_inputs_;
 public:
     std::shared_ptr<libfqfft::evaluation_domain<FieldT> > domain;
     FieldT t;
     std::vector<FieldT> At, Bt, Ct, Ht;
     FieldT Zt;
     ...
}

qap_instance_evaluation，记录了在 t 点上，A/B/C/H 以及 Z 对应的值。

一个 QAP 电路，对应的 primary/auxiliary，称为 witness，定义为：

template<typename FieldT>
 class qap_witness {
 private:
     size_t num_variables_;
     size_t degree_;
     size_t num_inputs_;
 public:
     FieldT d1, d2, d3;
     std::vector<FieldT> coefficients_for_ABCs;
     std::vector<FieldT> coefficients_for_H;
     ...
}

coefficients_for_ABCs 就是 witness。为了计算的方便，同时给出了对应的 H 多项式的系数。在给定一个 qap_instance_evaluation 和一个 qap_witness 的前提下，可以通过 is_satisfied 函数确定，是否 witness 合理：

 template<typename FieldT>
 bool qap_instance_evaluation<FieldT>::is_satisfied(const qap_witness<FieldT> &witness) const
 {
 ...
      ans_A = ans_A + libff::inner_product<FieldT>(this->At.begin()+1,
                                                  this->At.begin()+1+this->num_variables(),witness.coefficients_for_ABCs.begin(),witness.coefficients_for_ABCs.begin()+this->num_variables());
     ans_B = ans_B + libff::inner_product<FieldT>(this->Bt.begin()+1,
                                                  this->Bt.begin()+1+this->num_variables(),witness.coefficients_for_ABCs.begin(),witness.coefficients_for_ABCs.begin()+this->num_variables());
     ans_C = ans_C + libff::inner_product<FieldT>(this->Ct.begin()+1,
                                                  this->Ct.begin()+1+this->num_variables(),witness.coefficients_for_ABCs.begin(),witness.coefficients_for_ABCs.begin()+this->num_variables());
     ans_H = ans_H + libff::inner_product<FieldT>(this->Ht.begin(),
                                                  this->Ht.begin()+this->degree()+1,
                                                  witness.coefficients_for_H.begin(),
                                                  witness.coefficients_for_H.begin()+this->degree()+1);

     if (ans_A * ans_B - ans_C != ans_H * this->Zt)
     {
         return false;
     }
...
}

检查一个 witness 是否正确，就是计算 wA*wB-w*C = HZ 是否相等。

3. Reduction

Reduction 实现了不同描述语言之间的转化。libsnark 给出了如下一系列的转化实现：

bacs -> r1cs
r1cs -> qap
r1cs -> sap
ram -> r1cs
tbcs -> uscs
uscs -> ssp

以 r1cs->qap 为例，梳理一下 Reduction 的逻辑。从 R1CS 到 QAP 的转化逻辑在 reductions/r1cs_to_qap/目录中，定义了三个函数：

3.1 r1cs_to_qap_instance_map

r1cs_to_qap_instance_map 函数实现了从一个 R1CS 实例到 QAP instance 的转化。转化过程比较简单，就是将系数重新整理的过程（可以查看 2.5 中的 QAP 的描述）。

3.2 r1cs_to_qap_instance_map_with_evaluation

r1cs_to_qap_instance_map_with_evaluation 函数实现了从一个 R1CS 实例到 qap_instance_evaluation 的转化。给定 t，计算 A/B/C 以及 H/Z。

3.3 r1cs_to_qap_witness_map

r1cs_to_qap_witness_map 函数实现了从一个 R1CS 实例到 qap_witness 的转化。

 template<typename FieldT>
 qap_witness<FieldT> r1cs_to_qap_witness_map(const r1cs_constraint_system<FieldT> &cs,
                                             const r1cs_primary_input<FieldT> &primary_input,
                                             const r1cs_auxiliary_input<FieldT> &auxiliary_input,
                                             const FieldT &d1,
                                             const FieldT &d2,
                                             const FieldT &d3)

在给定 primary/auxiliary input 的基础上，计算出 witness（A/B/C 以及 H 的系数）。d1/d2/d3 在计算 H 系数提供扩展能力。Groth16 计算的时候，d1/d2/d3 取值都为 0。给定 primary/auxiliary input，A/B/C 的系数比较简单，就是 primary/auxiliary input 的简单拼接后的结果。

r1cs_variable_assignment<FieldT> full_variable_assignment = primary_input;
     full_variable_assignment.insert(full_variable_assignment.end(), auxiliary_input.begin(), auxiliary_input.end());```

H多项式系数的计算相对复杂一些，涉及到傅立叶变换/反傅立叶变换。H多项式的计算公式计算如下： `H(z) := (A(z)*B(z)-C(z))/Z(z)`

其中，`A(z) := A_0(z) + w_1 A_1(z) + ... + w_m A_m(z) + d1 * Z(z)，B(z) := B_0(z) + w_1 B_1(z) + ... + w_m B_m(z) + d2 * Z(z)，C(z) := C_0(z) + w_1 C_1(z) + ... + w_m C_m(z) + d3 * Z(z), Z(z) = (z-sigma_1)(z-sigma_2)...(z-sigma_n)`（m是QAP电路中变量的个数，n是QAP电路门的个数）。特别强调的是，`A(z)/B(z)/C(z)` 是多个多项式的和，并不是每个变量对应的多项式。

1. 确定A和B的多项式（通过反傅立叶变换）

```cpp
     for (size_t i = 0; i < cs.num_constraints(); ++i)
     {
         aA[i] += cs.constraints[i].a.evaluate(full_variable_assignment);
         aB[i] += cs.constraints[i].b.evaluate(full_variable_assignment);
     }
     domain->iFFT(aA);
     domain->iFFT(aB);

计算 A 和 B，对应 FieldT::multiplicative_generator 的计算结果

domain->cosetFFT(aA, FieldT::multiplicative_generator);
domain->cosetFFT(aB, FieldT::multiplicative_generator);

确定 C 的多项式（通过反傅立叶变换）

     for (size_t i = 0; i < cs.num_constraints(); ++i)
     {
         aC[i] += cs.constraints[i].c.evaluate(full_variable_assignment);
     }
     domain->iFFT(aC);

计算 C，对应 FieldT::multiplicative_generator 的计算结果

domain->cosetFFT(aC, FieldT::multiplicative_generator);

计算 H，对应 FieldT::multiplicative_generator 的计算结果

 for (size_t i = 0; i < domain->m; ++i)
 {
     H_tmp[i] = aA[i]*aB[i];
 }
 for (size_t i = 0; i < domain->m; ++i)
 {
     H_tmp[i] = (H_tmp[i]-aC[i]);
 }
 domain->divide_by_Z_on_coset(H_tmp);

计算 H 多项式的系数（反傅立叶变换）

domain->icosetFFT(H_tmp, FieldT::multiplicative_generator);

4. ZK Proof System

libsnark 提供了四种证明系统：

pcd (Proof-Carrying Data)
ppzkadsnark (PreProcessing Zero-Knowledge Succinct Non-interactive ARgument of Knowledge Over Authenticated Data)
ppzksnark (PreProcessing Zero-Knowledge Succinct Non-interactive ARgument of Knowledge)
zksnark (Zero-Knowledge Succinct Non-interactive ARgument of Knowledge)

著名的 Groth16 算法，属于 ppzksnark。因为 Groth16 在证明之前，需要预处理生成 CRS。ppzksnark 证明系统又可以细分成好几种：

r1cs_gg_ppzksnark，gg 代表 General Group，就是 Groth16 算法。

r1cs_se_ppzksnark，se 代表 Simulation Extractable，就是 GM17 算法。

r1cs_ppzksnark，就是 PGHR13 算法。

以 Groth16 算法（r1cs_gg_ppzksnark）为例，梳理一下相关的逻辑。Groth16 算法的相关逻辑在 zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark 目录中。

4.1 r1cs_gg_ppzksnark_proving_key

r1cs_gg_ppzksnark_proving_key 记录了 CRS 中在 prove 过程需要的信息。

template<typename ppT>
 class r1cs_gg_ppzksnark_proving_key {
 public:
     libff::G1<ppT> alpha_g1;
     libff::G1<ppT> beta_g1;
     libff::G2<ppT> beta_g2;
     libff::G1<ppT> delta_g1;
     libff::G2<ppT> delta_g2;

     libff::G1_vector<ppT> A_query;
     knowledge_commitment_vector<libff::G2<ppT>, libff::G1<ppT> > B_query;
     libff::G1_vector<ppT> H_query;
     libff::G1_vector<ppT> L_query;

     r1cs_gg_ppzksnark_constraint_system<ppT> constraint_system;
     ...
}

A_query 是 A(t)以 G1 生成元的 multiexp 的计算结果。

B_query 是 B(t)以 G1/G2 生成元的 multiexp 的计算结果。

H_query 是如下的计算以 G1 位生成元的 multiexp 的计算结果：

H(t)*Z(t)/delta

L_query 是如下的计算在 G1 位生成元的 multiexp 的计算结果：

(beta*A(t)+alpha*B(t)+C(t))/delta

也就是说，r1cs_gg_ppzksnark_proving_key 给出了 Groth16 算法中 CRS 的如下信息（用蓝色圈出）

r1cs_gg_ppzksnark_constraint_system<ppT> 定义在 zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark/r1cs_gg_ppzksnark_params.hpp 文件中。

template<typename ppT>
 using r1cs_gg_ppzksnark_constraint_system = r1cs_constraint_system<libff::Fr<ppT> >;

也就是说，r1cs_gg_ppzksnark_constraint_system 就是 r1cs_constraint_system。

4.2 r1cs_gg_ppzksnark_verification_key

r1cs_gg_ppzksnark_verification_key 记录了 CRS 中在 verify 过程需要的信息。

 template<typename ppT>
 class r1cs_gg_ppzksnark_verification_key {
 public:
     libff::GT<ppT> alpha_g1_beta_g2;
     libff::G2<ppT> gamma_g2;
     libff::G2<ppT> delta_g2;

     accumulation_vector<libff::G1<ppT> > gamma_ABC_g1;
     ...
}

也就是说，r1cs_gg_ppzksnark_verification_key 给出了 Groth16 算法中 CRS 的如下信息（用蓝色圈出）

4.3 r1cs_gg_ppzksnark_processed_verification_key

r1cs_gg_ppzksnark_processed_verification_key 和 r1cs_gg_ppzksnark_verification_key 类似。“processed"意味着 verification key 会做进一步处理，验证的过程会更快。

template<typename ppT>
 class r1cs_gg_ppzksnark_processed_verification_key {
 public:
     libff::GT<ppT> vk_alpha_g1_beta_g2;
     libff::G2_precomp<ppT> vk_gamma_g2_precomp;
     libff::G2_precomp<ppT> vk_delta_g2_precomp;

     accumulation_vector<libff::G1<ppT> > gamma_ABC_g1;
     ...
}

4.4 r1cs_gg_ppzksnark_keypair

r1cs_gg_ppzksnark_keypair 包括两部分：r1cs_gg_ppzksnark_proving_key 和 r1cs_gg_ppzksnark_verification_key。

 template<typename ppT>
 class r1cs_gg_ppzksnark_keypair {
 public:
     r1cs_gg_ppzksnark_proving_key<ppT> pk;
     r1cs_gg_ppzksnark_verification_key<ppT> vk;
     ...
}

4.5 r1cs_gg_ppzksnark_proof

众所周知，Groth16 的算法的证明包括 A/B/C 三个结果。

 template
 class r1cs_gg_ppzksnark_proof {
 public:
 libff::G1 g_A;
 libff::G2 g_B;
 libff::G1 g_C;
 ...
}

4.6 r1cs_gg_ppzksnark_generator

r1cs_gg_ppzksnark_generator 给定一个 r1cs_constraint_system 的基础上，r1cs_gg_ppzksnark_generator 能生成 r1cs_gg_ppzksnark_keypair，也就是生成 CRS 信息。

template<typename ppT>
 r1cs_gg_ppzksnark_keypair<ppT> r1cs_gg_ppzksnark_generator(const r1cs_gg_ppzksnark_constraint_system<ppT> &cs);

4.7 r1cs_gg_ppzksnark_prover

给定了 proving key 以及 primary/auxiliary input，计算证明的 A/B/C 结果。

template<typename ppT>
 r1cs_gg_ppzksnark_proof<ppT> r1cs_gg_ppzksnark_prover(const r1cs_gg_ppzksnark_proving_key<ppT> &pk,
                                                       const r1cs_gg_ppzksnark_primary_input<ppT> &primary_input,
                                                       const r1cs_gg_ppzksnark_auxiliary_input<ppT> &auxiliary_input);

已知 proving key 的情况下，计算 A/B/C 的结果，相当简单：

/* A = alpha + sum_i(a_i*A_i(t)) + r*delta */
libff::G1<ppT> g1_A = pk.alpha_g1 + evaluation_At + r * pk.delta_g1;
/* B = beta + sum_i(a_i*B_i(t)) + s*delta */
libff::G1<ppT> g1_B = pk.beta_g1 + evaluation_Bt.h + s * pk.delta_g1;
libff::G2<ppT> g2_B = pk.beta_g2 + evaluation_Bt.g + s * pk.delta_g2;
/* C = sum_i(a_i*((beta*A_i(t) + alpha*B_i(t) + C_i(t)) + H(t)*Z(t))/delta) + A*s + r*b - r*s*delta */
libff::G1<ppT> g1_C = evaluation_Ht + evaluation_Lt + s *  g1_A + r * g1_B - (r * s) * pk.delta_g1;

4.8 r1cs_gg_ppzksnark_verifier

总共提供了四种验证函数，分成两类：processed/non-processed 和 weak/strong IC。processed/non-processed 是指验证的 key 是否 processed？weak/strong IC 指的是，是否 input consistency？Primary Input 的大小和 QAP 的 statement 的大小相等，称为 strong IC。Primary Input 的大小小于 QAP 的 statement 的大小，称为 weak IC。

以 r1cs_gg_ppzksnark_verifier_strong_IC 为例，在给定 verification key/primary input 的基础上，可以验证 proof 是否正确。

template<typename ppT>
bool r1cs_gg_ppzksnark_verifier_strong_IC(const r1cs_gg_ppzksnark_verification_key<ppT> &vk,const r1cs_gg_ppzksnark_primary_input<ppT> &primary_input,const r1cs_gg_ppzksnark_proof<ppT> &proof);

总的来说，Groth16 的证明生成和验证的逻辑如下图：

可以看出，使用 ZKSNARK(Groth16)证明，需要先创建一个 r1cs_constraint_system。libsnark 设计了 Gadget 的框架，方便搭建 r1cs_constraint_system。

5 Gadget

libsnark 提供了两套 Gadget 库：gadgetlib1 和 gadgetlib2。libsnark 中很多示例是基于 gadgetlib1 搭建。gadgetlib1 也提供了更丰富的 gadget。本文也主要讲解 gadgetlib1 的逻辑。gadgetlib1 的相关代码在 libsnark/gadgetlib1 目录中。

5.1 protoboard

protoboard 是 r1cs_constraint_system 之上的一层封装。通过一个个的 Gadget，向 r1cs_constraint_system 添加约束。为了让不同的 Gadget 之间采用统一的 Variable 以及 Lc，protoboard 通过”next_free_var"以及"next_free_lc“维护所有 Gadget 创建的 Variable 以及 Lc。

 template<typename FieldT>
 class protoboard {
   ...
     FieldT constant_term;
     r1cs_variable_assignment<FieldT> values;
     var_index_t next_free_var;
     lc_index_t next_free_lc;
     std::vector<FieldT> lc_values;
     r1cs_constraint_system<FieldT> constraint_system;
     ...
 }

5.2 pb_variable

libsnark 提供了在 pb_variable，pb_variable_array，pb_linear_combination 和 pb_linear_combination_array 四个类。这四个类都是 variable, linear_combination 的封装，为了支持 protoboard 的管理。

5.3 gadget

gadget 的定义非常的简单：

 template<typename FieldT>
 class gadget {
 protected:
     protoboard<FieldT> &pb;
     const std::string annotation_prefix;
 public:
     gadget(protoboard<FieldT> &pb, const std::string &annotation_prefix="");
 };

每一个具体的 Gadget 逻辑上需要做如下一些事情：

申请 Variable 或者 Lc （allocate）
添加 Gadget 逻辑相关的约束（generate_r1cs_constraints）
生成相关的 Witness（generate_r1cs_witness）

5.4 example

在 gadgetlib1/gadgets 目录下有很多 Gadget 的实现：椭圆曲线计算，各种 hash 算法，merkle 树的计算，配对函数等等。本文以 basic gagdet 中的两数比较（comparison gadget）为例，说明 Gadget 的基本逻辑。

comparison_gadget 的定义在 gadgetlib1/gadgets/basic_gadgets.hpp：

comparison_gadget(protoboard<FieldT>& pb,
                       const size_t n,
                       const pb_linear_combination<FieldT> &A,
                       const pb_linear_combination<FieldT> &B,
                       const pb_variable<FieldT> &less,
                       const pb_variable<FieldT> &less_or_eq,
                       const std::string &annotation_prefix="") :
         gadget<FieldT>(pb, annotation_prefix), n(n), A(A), B(B), less(less), less_or_eq(less_or_eq)
     {
         alpha.allocate(pb, n, FMT(this->annotation_prefix, " alpha"));
         alpha.emplace_back(less_or_eq); // alpha[n] is less_or_eq
         alpha_packed.allocate(pb, FMT(this->annotation_prefix, " alpha_packed"));
         not_all_zeros.allocate(pb, FMT(this->annotation_prefix, " not_all_zeros"));
         pack_alpha.reset(new packing_gadget<FieldT>(pb, alpha, alpha_packed,                           FMT(this->annotation_prefix, " pack_alpha")));
         all_zeros_test.reset(new disjunction_gadget<FieldT>(pb,                                    pb_variable_array<FieldT>(alpha.begin(), alpha.begin() + n),not_all_zeros, FMT(this->annotation_prefix, " all_zeros_test")));
     };

comparison_gadget 的构造函数比较清晰：在给定两个 n 位的数 A 和 B，输出两个变量：less 和 less_or_eq（A 是否小于 B？）。

构造函数，主要是创建其他变量以及 Gadget。 alpha 是长度为 n+1 的变量数组，其中 alpha[n]是 less or eq。

alpha 是 2^n+B-A 的结果的位的表示。alpha_packed 是一个变量，alpha 对应的值。也就是，alpha_packed 等于 2^n+B-A。

not_all_zeros 是一个变量，表示 B-A 的结果是否全是 0。

pack_alpha 是 packing_gadget，将 n+1 位的 alpha 打包，计算结果存储在 alpha_packed 变量中。packing_gadget 就是将位表示的数据，变成数值表示。

all_zeros_test 是 disjunction_gadget，确定 alpha 的 n 个变量中是否全 0。

comparison_gadget 的 generate_r1cs_constraints 函数负责添加约束。

template<typename FieldT>
 void comparison_gadget<FieldT>::generate_r1cs_constraints()
 {
     generate_boolean_r1cs_constraint<FieldT>(this->pb, not_all_zeros, FMT(this->annotation_prefix, " not_all_zeros"));
     pack_alpha->generate_r1cs_constraints(true);
     this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(1, (FieldT(2)^n) + B - A, alpha_packed), FMT(this->annotation_prefix, " main_constraint"));
     all_zeros_test->generate_r1cs_constraints();
     this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(less_or_eq, not_all_zeros, less),     FMT(this->annotation_prefix, " less"));
 }

a. 对 not_all_zeros，添加 boolean 约束（该变量只能是 0 或者 1）

b. pack_alpha->generate_r1cs_constraints(true) 约束 alpha 对应的数值等于 alpha_packed。

c. 1*(2^n+B-A) = alpah_packed

d. 确定 not_all_zeros 变量的值和 alpha 中 n 个变量中是否为 0 的结果一致

e. less_or_eq * not_all_zeros = less

整个 comparison_gadget 的电路逻辑如下图所示：

comparison_gadget 的设计思想是：

如果 B - A > 0, 则 2^n + B - A > 2^n, less_or_eq = 1， not_all_zeros = 1

如果 B - A = 0, 则 2^n + B - A = 2^n, less_or_eq = 1，not_all_zeros = 0 如果 B - A 也就是说，less_or_eq * not_all_zeros = less。

简单的说，两个数的“大小“比较，是通过 2^n + B - A 的计算结果的相应的一些”符号“位相乘确定。

comparison_gadget 的 generate_r1cs_witness 函数生成电路的 witness。comparison_gadget 的 test_comparison_gadget 函数是 comparison gadget 的测试函数，相对比较容易理解，小伙伴可以自行查看源码。

总结： libsnark 库代码层次非常清晰。最重要的是，libsnark 给出了 SNARK 相关算法的全貌，各种 Relation，Language，Proof System。为了更好的生成 R1CS 电路，libsnark 抽象出 protoboard 和 gadget，方便开发者快速搭建电路。

最近一个月发生好多事情。原有的合作关系的结束，新的合作关系的开始。创业变化就是快。期间，我也自己问自己，自己该何去何从？彷徨，犹豫，对未知的未来，我也不确定。但是，内心有种强烈的感觉，告诉自己，有想法，就去干，保持好奇。也许，内心深处，总有一丝侥幸，万一能走出一条路呢。也许，真的就成了呢？

本文作者为深入浅出区块链共建者：Star Li，他的公众号星想法有很多原创高质量文章，欢迎大家扫码关注。

学习中如遇问题，欢迎到区块链技术问答提问，这里有专家为你解惑。深入浅出区块链 - 高质量的区块链技术博客 + 问答社区，为区块链学习双重助力

零知识证明 - libsnark源代码分析 | 深入浅出区块链 | 技术博客

1. 源代码目录

2. Relation

2.1 variable

2.2 linear_term

2.3 linear_combination

2.4 R1CS

2.5 QAP

3. Reduction

3.1 r1cs_to_qap_instance_map

3.2 r1cs_to_qap_instance_map_with_evaluation

3.3 r1cs_to_qap_witness_map

4. ZK Proof System

4.1 r1cs_gg_ppzksnark_proving_key

4.2 r1cs_gg_ppzksnark_verification_key

4.3 r1cs_gg_ppzksnark_processed_verification_key

4.4 r1cs_gg_ppzksnark_keypair

4.5 r1cs_gg_ppzksnark_proof

4.6 r1cs_gg_ppzksnark_generator

4.7 r1cs_gg_ppzksnark_prover

4.8 r1cs_gg_ppzksnark_verifier

5 Gadget

5.1 protoboard

5.2 pb_variable

5.3 gadget

5.4 example

Recommend

[译]JavaScript中的development模式怎么实现 - 知乎

实现一个简单的Webpack - 知乎

使用Sauce Labs进行页面性能测试与监控 - 简书

产品级敏捷: 高效, 使命必达的产品开发生态系统 - Cloud-Native 产品级敏捷

JMM 内存模型 | 极客之光

Android系统上的进程管理：进程的调度

简单几招提速 Kotlin kapt编译 - 技术小黑屋

聊一聊字符串内部化 - poslua | ms2008 Blog

使用FindBugs对Java代码进行静态分析 - 简书

Spring Cloud Alibaba基础教程：与Dubbo的完美融合 | 程序猿DD

About Joyk

零知识证明 - libsnark源代码分析 | 深入浅出区块链 | 技术博客

1. 源代码目录

2. Relation

2.1 variable

2.2 linear_term

2.3 linear_combination

2.4 R1CS

2.5 QAP

3. Reduction

3.1 r1cs_to_qap_instance_map

3.2 r1cs_to_qap_instance_map_with_evaluation

3.3 r1cs_to_qap_witness_map

4. ZK Proof System

4.1 r1cs_gg_ppzksnark_proving_key

4.2 r1cs_gg_ppzksnark_verification_key

4.3 r1cs_gg_ppzksnark_processed_verification_key

4.4 r1cs_gg_ppzksnark_keypair

4.5 r1cs_gg_ppzksnark_proof

**4.6 ** r1cs_gg_ppzksnark_generator

4.7 r1cs_gg_ppzksnark_prover

4.8 r1cs_gg_ppzksnark_verifier

5 Gadget

5.1 protoboard

5.2 pb_variable

5.3 gadget

5.4 example

Recommend

About Joyk

4.6 r1cs_gg_ppzksnark_generator