建议和反馈

请填写你的反馈内容

零知识证明 – libsnark 源代码分析

2020-05-19 ·2609次阅读 ·读完需要13分钟

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

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

commit 477c9dfd07b280e42369f82f89c08416319e24ae
Author: Madars Virza 
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

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

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

2.2 linear_term

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

1234567
template class linear_term { public:     var_index_t index;     FieldT coeff;     ... };

2.3 linear_combination

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

123456
template class linear_combination {    public:       std::vector > 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 约束定义为:

123456
template class r1cs_constraint {    public:        linear_combination a, b, c;...};

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

1234
templateusing r1cs_primary_input = std::vector;templateusing r1cs_auxiliary_input = std::vector;

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

12345678
 template class r1cs_constraint_system { public:     size_t primary_input_size;     size_t auxiliary_input_size;     std::vector > constraints;     ...}

2.5 QAP

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

123456789101112
 template class qap_instance { private:     size_t num_variables_;     size_t degree_;     size_t num_inputs_; public:     std::shared_ptr > domain;     std::vector > A_in_Lagrange_basis;     std::vector > B_in_Lagrange_basis;     std::vector > C_in_Lagrange_basis;}

numbariables 表示 QAP 电路的变量的个数。numinputs 表示 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 表示:

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

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

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

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

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

123456789101112131415161718192021
 template bool qap_instance_evaluation::is_satisfied(const qap_witness &witness) const { ...      ans_A = ans_A + libff::inner_product(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(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(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(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 的转化。

1234567
templateqap_witness r1cs_to_qap_witness_map(const r1cs_constraint_system &cs,                                            const r1cs_primary_input &primary_input,                                            const r1cs_auxiliary_input &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 的简单拼接后的结果。

12
r1cs_variable_assignment 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 的多项式(通过反傅立叶变换)

1234567
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);
  1. 计算 A 和 B,对应 FieldT::multiplicative_generator 的计算结果

    12
    domain->cosetFFT(aA, FieldT::multiplicative_generator);domain->cosetFFT(aB, FieldT::multiplicative_generator);
  2. 确定 C 的多项式(通过反傅立叶变换)

    12345
    for (size_t i = 0; i < cs.num_constraints(); ++i){    aC[i] += cs.constraints[i].c.evaluate(full_variable_assignment);}domain->iFFT(aC);
  3. 计算 C,对应 FieldT::multiplicative_generator 的计算结果

1
domain->cosetFFT(aC, FieldT::multiplicative_generator);
  1. 计算 H,对应 FieldT::multiplicative_generator 的计算结果

    123456789
    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);
  2. 计算 H 多项式的系数(反傅立叶变换)

    1
    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 过程需要的信息。

1234567891011121314151617
template class r1cs_gg_ppzksnark_proving_key { public:     libff::G1 alpha_g1;     libff::G1 beta_g1;     libff::G2 beta_g2;     libff::G1 delta_g1;     libff::G2 delta_g2;
      libff::G1_vector A_query;     knowledge_commitment_vector, libff::G1 > B_query;     libff::G1_vector H_query;     libff::G1_vector L_query;
      r1cs_gg_ppzksnark_constraint_system 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 定义在 zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark/r1cs_gg_ppzksnark_params.hpp 文件中。

12
template using r1cs_gg_ppzksnark_constraint_system = r1cs_constraint_system >;

也就是说,r1cs_gg_ppzksnark_constraint_system 就是 r1cs_constraint_system。

4.2 r1cs_gg_ppzksnark_verification_key

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

12345678910
 template class r1cs_gg_ppzksnark_verification_key { public:     libff::GT alpha_g1_beta_g2;     libff::G2 gamma_g2;     libff::G2 delta_g2;
      accumulation_vector > 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 会做进一步处理,验证的过程会更快。

12345678910
template class r1cs_gg_ppzksnark_processed_verification_key { public:     libff::GT vk_alpha_g1_beta_g2;     libff::G2_precomp vk_gamma_g2_precomp;     libff::G2_precomp vk_delta_g2_precomp;
      accumulation_vector > gamma_ABC_g1;     ...}

4.4 r1cs_gg_ppzksnark_keypair

r1cs_gg_ppzksnark_keypair 包括两部分:r1cs_gg_ppzksnark_proving_key 和 r1cs_gg_ppzksnark_verification_key。

1234567
 template class r1cs_gg_ppzksnark_keypair { public:     r1cs_gg_ppzksnark_proving_key pk;     r1cs_gg_ppzksnark_verification_key vk;     ...}

4.5 r1cs_gg_ppzksnark_proof

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

12345678
 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 信息。

12
template r1cs_gg_ppzksnark_keypair r1cs_gg_ppzksnark_generator(const r1cs_gg_ppzksnark_constraint_system &cs);

4.7 r1cs_gg_ppzksnark_prover

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

1234
template r1cs_gg_ppzksnark_proof r1cs_gg_ppzksnark_prover(const r1cs_gg_ppzksnark_proving_key &pk,                                                       const r1cs_gg_ppzksnark_primary_input &primary_input,                                                       const r1cs_gg_ppzksnark_auxiliary_input &auxiliary_input);

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

1234567
/* A = alpha + sum_i(a_i*A_i(t)) + r*delta */libff::G1 g1_A = pk.alpha_g1 + evaluation_At + r * pk.delta_g1;/* B = beta + sum_i(a_i*B_i(t)) + s*delta */libff::G1 g1_B = pk.beta_g1 + evaluation_Bt.h + s * pk.delta_g1;libff::G2 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 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 是否正确。

12
templatebool r1cs_gg_ppzksnark_verifier_strong_IC(const r1cs_gg_ppzksnark_verification_key &vk,const r1cs_gg_ppzksnark_primary_input &primary_input,const r1cs_gg_ppzksnark_proof &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。

1234567891011
template                                                                          class protoboard {                                                                                    ...                                                                                            FieldT constant_term;                                                                                      r1cs_variable_assignment values;    var_index_t next_free_var;    lc_index_t next_free_lc;    std::vector lc_values;                                                                      r1cs_constraint_system 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 的定义非常的简单:

12345678
templateclass gadget {protected:    protoboard &pb;    const std::string annotation_prefix;public:    gadget(protoboard &pb, const std::string &annotation_prefix="");};

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

  1. 申请 Variable 或者 Lc (allocate)

  2. 添加 Gadget 逻辑相关的约束(generate_r1cs_constraints)

  3. 生成相关的 Witness(generate_r1cs_witness)

5.4 example

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

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

12345678910111213141516
comparison_gadget(protoboard& pb,                                                                             const size_t n,                                                                                     const pb_linear_combination &A,                                                             const pb_linear_combination &B,                                                             const pb_variable &less,                                                                     const pb_variable &less_or_eq,                                                               const std::string &annotation_prefix="") :                                             gadget(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(pb, alpha, alpha_packed,                           FMT(this->annotation_prefix, " pack_alpha")));           all_zeros_test.reset(new disjunction_gadget(pb,                                    pb_variable_array(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 函数负责添加约束。

123456789
template void comparison_gadget::generate_r1cs_constraints() {     generate_boolean_r1cs_constraint(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(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(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,方便开发者快速搭建电路。

题外

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


评论(0)问答(0)
请先登录或注册

请先登陆或注册

相关推荐

区块链技术指南 | ODIN协议初窥

本文主要介绍了ODIN协议是什么、如何使用、格式等内容。1 IntroductionODIN是用来对标传统互联网中的DNS的。ODIN(Open Data Index Name) - 开放数据索引命名......
呼近乎出 · 2020-06-01
1081阅读 · 0赞赏 · 0问答

密码学原语如何应用?解析单向哈希的妙用

隐私数据如何验明真伪?区块链数据何以可信?如何快速检验海量数据是否被篡改?单向哈希在其中起到了什么作用?隐私数据的价值很大程度上源自其真实性,如何防止数据被恶意篡改,是隐私保护方案设计中不可忽视的关键......
区块链网 · 2020-05-29
1362阅读 · 0赞赏 · 0问答

了解下不用助记词的 ZenGo 钱包及门限签名技术

区块链钱包作为数字货币世界的入口,它糟糕的体验把大部分人挡在门外,说的就是你:助记词备份(或私钥备份)。现在一个激动人心的签名方案让体验提升一大步,也是博客的主角:门限签名技术及 ZenGo......
年少 · 2020-05-25
1042阅读 · 0赞赏 · 0问答

Zcash – 各种密钥和签名,你懂吗?

Zcash 的发展大体经过了 OverWinter (过冬) -> Sprout (发芽) -> Sapling (树苗) 这几个阶段,随着业务和功能的逐渐丰富,密钥系统也越来越复杂,刚开始......
爵士J · 2020-05-25
1153阅读 · 0赞赏 · 0问答

零知识证明 – zkSNARK 应用的 Nullifier Hash 攻击

早上很多朋友 @我,安比实验室发表了一篇文章 zkSNARK 的 “输入假名” 的攻击。迅速看了看,很赞。这个攻击原理其实比较简单,但是,不深入理解 zkSNARK 以及使用场景的朋友确实很......
Watch · 2020-05-21
1693阅读 · 0赞赏 · 0问答

探索零知识证明系列 2:从“模拟”理解零知识证明

相信很多人都听说过零知识证明,但是只有极少数人听说过模拟,然而模拟是理解零知识的关键。我们在第一篇文章『初识「零知识」与「证明」』中介绍了一个简单的零知识交互系统:地图三染色问题。那么这个系统真的是零......
calculator · 2020-05-21
2085阅读 · 0赞赏 · 0问答

wind

4099

LK币

23

粉丝

34

笔记

感谢"wind"

这篇精彩的笔记,目前已经帮助

  • 0
  • 2
  • 6
  • 0
  • 9
喜欢0
链客社群 加入

微博进入

商务合作>

广告投放>

公司名称:北京链客行科技有限公司

联系方式:010-67707199

ICP备案号:京ICP备18032136号

Copyright:链客区块链技术问答社区 版权所有

感谢您的提问,问题被社区永久收入以便新人查看。一定要记得采纳最佳答案哦!加油!

感谢您的善举,每一次解答会成为新人的灯塔,回答被采纳后获得20算力和相应的LK币奖励

您将赞赏给对方2LK币的奖励哦!感谢您的赞赏!

您将赞赏给对方2LK币的奖励哦!感谢您的赞赏!