零知識(shí)證明中的libsnark源代碼全面分析

時(shí)間：2020-05-26 13:33:01

關(guān)鍵字：源代碼 INPUT WITNESS PEN

手機(jī)看文章

掃描二維碼
隨時(shí)隨地手機(jī)看文章

[導(dǎo)讀] 最近一個(gè)月發(fā)生好多事情。原有的合作關(guān)系的結(jié)束，新的合作關(guān)系的開始。創(chuàng)業(yè)變化就是快。期間，我也自己?jiǎn)栕约?，自己該何去何從？彷徨，猶豫，對(duì)未知的未來，我也不確定。但是，內(nèi)心有種強(qiáng)烈的感覺，告訴自己，

最近一個(gè)月發(fā)生好多事情。原有的合作關(guān)系的結(jié)束，新的合作關(guān)系的開始。創(chuàng)業(yè)變化就是快。期間，我也自己?jiǎn)栕约?，自己該何去何從？彷徨，猶豫，對(duì)未知的未來，我也不確定。但是，內(nèi)心有種強(qiáng)烈的感覺，告訴自己，有想法，就去干，保持好奇。也許，內(nèi)心深處，總有一絲僥幸，萬一能走出一條路呢。也許，真的就成了呢？

libsnark源代碼，建議想深入零知識(shí)證明的小伙伴都讀一讀。Bellman庫(kù)主要圍繞Groth16算法，libsnark給出了SNARK相關(guān)算法的全貌，各種Relation，Language，Proof System。為了更好的生成R1CS電路，libsnark抽象出protoboard和gadget，方便開發(fā)者快速搭建電路。

本文中使用的libsnark源代碼的最后一個(gè)commit如下：

commit 477c9dfd07b280e42369f82f89c08416319e24ae

Author： Madars Virza 《madars@mit.edu》

Date： Tue Jun 18 18:43:12 2019 -0400

Document that we also implement the Groth16 proof system.

1. 源代碼目錄

源代碼在libsnark目錄下：

common - 定義和實(shí)現(xiàn)了一些通用的數(shù)據(jù)結(jié)構(gòu)，例如默克爾樹，稀疏向量等等。

relaTIons - relaTIon描述了“約束”關(guān)系。除了我們通常說的R1CS外，還有很多其他約束的描述語言。

reducTIons - 各種不同描述語言之間的轉(zhuǎn)化。

knowledge_commit - 在mulTIexp的基礎(chǔ)上，引入pair的概念，兩個(gè)基點(diǎn)一個(gè)系數(shù)，計(jì)算結(jié)果稱為一個(gè)pair。

zk_proof_systems - 零知識(shí)證明中的各種證明系統(tǒng)（包括Groth16，GM17等等）。

gadgetlib1/gadgetlib2 - 為了更方便的構(gòu)建R1CS，libsnark抽象出一層gadget。已有的gadget，可以方便地整合搭建出新的電路。

2. Relation

需要零知識(shí)證明的問題都是NP問題。NP問題中有一類問題NPC（NP-complete）問題。所有的NP問題都可以轉(zhuǎn)化為一個(gè)NPC問題。只要有一個(gè)NPC問題能多項(xiàng)式時(shí)間內(nèi)解決，所有的NP問題都能多項(xiàng)式時(shí)間內(nèi)解決。描述一個(gè)NPC問題，有多種方式。描述NPC問題的方式，稱為“l(fā)anguage”。Relation指的是一個(gè)NPC問題和該問題的解的關(guān)系。

libsnark庫(kù)總結(jié)了幾種描述語言：

·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總結(jié)了兩種RAM計(jì)算框架：

tinyRAM

fooRAM

· arithmetic program類

QAP - Quadratic Arithmetic Program（GGPR13）

SAP - Square Arithmetic Program（GM17）

SSP - Square Span Program （DFGK14）

先介紹實(shí)現(xiàn)各種語言中需要的“variable” （variable.hpp/variable.tcc），再詳細(xì)介紹R1CS以及QAP語言。

2.1 variable

template《typename FieldT》

class variable {

public：

var_index_t index;

。..

};

varible的定義非常簡(jiǎn)單，描述一個(gè)variable，只需要記錄一個(gè)varible對(duì)應(yīng)的標(biāo)號(hào)就行了。比如對(duì)應(yīng)編號(hào)為index的variable，表示的是x_{index}變量。

2.2 linear_term

linear_term描述了一個(gè)線性組合中的一項(xiàng)。線性組合中的一項(xiàng)由變量以及對(duì)應(yīng)的系數(shù)組成：

template《typename FieldT》

class linear_term {

public：

var_index_t index;

FieldT coeff;

。..

};

2.3 linear_combination

linear_combination描述了一個(gè)完整的線性組合。一個(gè)linear combination由多個(gè)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約束就是滿足以下形式的一個(gè)表達(dá)式：

《 A ， X 》 * 《 B ， X 》 = 《 C ， X 》

X是所有變量組合的向量，A/B/C是和X等長(zhǎng)的向量。《，》代表的是點(diǎn)乘。一個(gè)R1CS系統(tǒng)由多個(gè)R1CS約束組成。

R1CS約束定義為：

template《typename FieldT》

class r1cs_constraint {

public：

linear_combination《FieldT》 a， b， c;

。..

};

一個(gè)R1CS約束，可以由a/b/c三個(gè)linear_combination表示。一個(gè)R1CS系統(tǒng)中的所有變量的賦值，又分成兩部分：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》;

一個(gè)R1CS系統(tǒng)，包括多個(gè)R1CS約束。當(dāng)然，每個(gè)約束的向量的長(zhǎng)度是固定的（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_variables_表示QAP電路的變量的個(gè)數(shù)。num_inputs_表示QAP電路的“statement”對(duì)應(yīng)變量的個(gè)數(shù)。degree_表示A/B/C中每個(gè)多項(xiàng)式的階的個(gè)數(shù)（和電路的門的個(gè)數(shù)相關(guān)）。

domain是計(jì)算傅立葉變換/反傅立葉變換的引擎，由libfqfft庫(kù)實(shí)現(xiàn)。

何為L(zhǎng)agrange basis？

給定一系列的x和y的對(duì)應(yīng)關(guān)系，通過拉格朗日插值的方式，可以確定多項(xiàng)式： p（x） = y_0l_0（x） + y_1l_1（x） + 。.. + y_nl_n（x）其中l(wèi)_0（x）， l_1（x），。.. l_n（x）就稱為拉格朗日basis。

A_in_Lagrange_basis/B_in_Lagrange_basis/C_in_Lagrange_basis把一個(gè)電路中每個(gè)變量不同門的值整理在一起。舉個(gè)例子，如下是x^3+x+5的電路對(duì)應(yīng)的R1CS的約束：

該電路對(duì)應(yīng)的A_in_Lagrange_basis/B_in_Lagrange_basis/C_in_Lagrange_basis為：

qap_instance描述的是一個(gè)QAP電路，A/B/C對(duì)應(yīng)的多項(xiàng)式表達(dá)式（雖然是用Lagrange basis表示）。A/B/C多項(xiàng)式在一個(gè)點(diǎn)上的結(jié)果，用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點(diǎn)上，A/B/C/H以及Z對(duì)應(yīng)的值。

一個(gè)QAP電路，對(duì)應(yīng)的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。為了計(jì)算的方便，同時(shí)給出了對(duì)應(yīng)的H多項(xiàng)式的系數(shù)。在給定一個(gè)qap_instance_evaluation和一個(gè)qap_witness的前提下，可以通過is_satisfied函數(shù)確定，是否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;

}

。..

}

檢查一個(gè)witness是否正確，就是計(jì)算wA*wB-w*C = HZ是否相等。

3.Reduction

Reduction實(shí)現(xiàn)了不同描述語言之間的轉(zhuǎn)化。libsnark給出了如下一系列的轉(zhuǎn)化實(shí)現(xiàn)：

bacs -》 r1cs

r1cs -》 qap

r1cs -》 sap

ram -》 r1cs

tbcs -》 uscs

uscs -》 ssp

以r1cs-》qap為例，梳理一下Reduction的邏輯。從R1CS到QAP的轉(zhuǎn)化邏輯在reductions/r1cs_to_qap/目錄中，定義了三個(gè)函數(shù)：

3.1 r1cs_to_qap_instance_map

r1cs_to_qap_instance_map函數(shù)實(shí)現(xiàn)了從一個(gè)R1CS實(shí)例到QAP instance的轉(zhuǎn)化。轉(zhuǎn)化過程比較簡(jiǎn)單，就是將系數(shù)重新整理的過程（可以查看2.5中的QAP的描述）。

3.2 r1cs_to_qap_instance_map_with_evaluation

r1cs_to_qap_instance_map_with_evaluation函數(shù)實(shí)現(xiàn)了從一個(gè)R1CS實(shí)例到qap_instance_evaluation的轉(zhuǎn)化。給定t，計(jì)算A/B/C以及H/Z。

3.3 r1cs_to_qap_witness_map

r1cs_to_qap_witness_map函數(shù)實(shí)現(xiàn)了從一個(gè)R1CS實(shí)例到qap_witness的轉(zhuǎn)化。

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的基礎(chǔ)上，計(jì)算出witness（A/B/C以及H的系數(shù)）。d1/d2/d3在計(jì)算H系數(shù)提供擴(kuò)展能力。Groth16計(jì)算的時(shí)候，d1/d2/d3取值都為0。給定primary/auxiliary input，A/B/C的系數(shù)比較簡(jiǎn)單，就是primary/auxiliary input的簡(jiǎn)單拼接后的結(jié)果。

r1cs_variable_assignment《FieldT》 full_variable_assignment = primary_input;

full_variable_assignment.insert（full_variable_assignment.end（）， auxiliary_input.begin（）， auxiliary_input.end（））;

H多項(xiàng)式系數(shù)的計(jì)算相對(duì)復(fù)雜一些，涉及到傅立葉變換/反傅立葉變換。H多項(xiàng)式的計(jì)算公式計(jì)算如下： 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電路中變量的個(gè)數(shù)，n是QAP電路門的個(gè)數(shù)）。特別強(qiáng)調(diào)的是，A（z）/B（z）/C（z）是多個(gè)多項(xiàng)式的和，并不是每個(gè)變量對(duì)應(yīng)的多項(xiàng)式。

1/ 確定A和B的多項(xiàng)式（通過反傅立葉變換）

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）;

2/ 計(jì)算A和B，對(duì)應(yīng)FieldT：：multiplicative_generator的計(jì)算結(jié)果

domain-》cosetFFT（aA， FieldT：：multiplicative_generator）;

domain-》cosetFFT（aB， FieldT：：multiplicative_generator）;

3/ 確定C的多項(xiàng)式（通過反傅立葉變換）

for （size_t i = 0; i 《 cs.num_constraints（）; ++i）

{

aC［i］ += cs.constraints［i］.c.evaluate（full_variable_assignment）;

}

domain-》iFFT（aC）;

4/ 計(jì)算C，對(duì)應(yīng)FieldT：：multiplicative_generator的計(jì)算結(jié)果

domain-》cosetFFT（aC， FieldT：：multiplicative_generator）;

5/ 計(jì)算H，對(duì)應(yīng)FieldT：：multiplicative_generator的計(jì)算結(jié)果

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）;

6/ 計(jì)算H多項(xiàng)式的系數(shù)（反傅立葉變換）

domain-》icosetFFT（H_tmp， FieldT：：multiplicative_generator）;

4. ZK Proof System

libsnark提供了四種證明系統(tǒng)：

·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。因?yàn)镚roth16在證明之前，需要預(yù)處理生成CRS。ppzksnark證明系統(tǒng)又可以細(xì)分成好幾種：

其中：

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

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

r1cs_ppzksnark，就是PGHR13算法。

以Groth16算法（r1cs_gg_ppzksnark）為例，梳理一下相關(guān)的邏輯。Groth16算法的相關(guān)邏輯在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的計(jì)算結(jié)果。

B_query是B（t）以G1/G2生成元的multiexp的計(jì)算結(jié)果。

H_query是如下的計(jì)算以G1位生成元的multiexp的計(jì)算結(jié)果：

H（t）*Z（t）/delta

L_query是如下的計(jì)算在G1位生成元的multiexp的計(jì)算結(jié)果：

（beta*A（t）+alpha*B（t）+C（t））/delta

也就是說，r1cs_gg_ppzksnark_proving_key給出了Groth16算法中CRS的如下信息（用藍(lán)色圈出）

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的如下信息（用藍(lán)色圈出）

4.3 r1cs_gg_ppzksnark_processed_verification_key

r1cs_gg_ppzksnark_processed_verification_key和r1cs_gg_ppzksnark_verification_key類似?！皃rocessed“意味著verification key會(huì)做進(jìn)一步處理，驗(yàn)證的過程會(huì)更快。

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三個(gè)結(jié)果。

template《typename ppT》

class r1cs_gg_ppzksnark_proof {

public：

libff：：G1《ppT》 g_A;

libff：：G2《ppT》 g_B;

libff：：G1《ppT》 g_C;

。..

}

4.6 r1cs_gg_ppzksnark_generator 給定一個(gè)r1cs_constraint_system的基礎(chǔ)上，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，計(jì)算證明的A/B/C結(jié)果。

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的情況下，計(jì)算A/B/C的結(jié)果，相當(dāng)簡(jiǎn)單：

/* 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

總共提供了四種驗(yàn)證函數(shù)，分成兩類：processed/non-processed 和 weak/strong IC。processed/non-processed是指驗(yàn)證的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的基礎(chǔ)上，可以驗(yàn)證proof是否正確。

template《typename ppT》

bool r1cs_gg_ppzksnark_verifier_strong_IC（const r1cs_gg_ppzksnark_verification_key《ppT》 &vk

總的來說，Groth16的證明生成和驗(yàn)證的邏輯如下圖：

可以看出，使用ZKSNARK（Groth16）證明，需要先創(chuàng)建一個(gè)r1cs_constraint_system。libsnark設(shè)計(jì)了Gadget的框架，方便搭建r1cs_constraint_system。

5. Gadget

libsnark提供了兩套Gadget庫(kù)：gadgetlib1和gadgetlib2。libsnark中很多示例是基于gadgetlib1搭建。gadgetlib1也提供了更豐富的gadget。本文也主要講解gadgetlib1的邏輯。gadgetlib1的相關(guān)代碼在libsnark/gadgetlib1目錄中。

5.1 protoboard

protoboard是r1cs_constraint_system之上的一層封裝。通過一個(gè)個(gè)的Gadget，向r1cs_constraint_system添加約束。為了讓不同的Gadget之間采用統(tǒng)一的Variable以及Lc，protoboard通過”next_free_var”以及“next_free_lc“維護(hù)所有Gadget創(chuàng)建的Variable以及Lc。