原始碼在libsnark目錄下：
common - 定義和實現了一些通用的資料結構，例如默克爾樹，稀疏向量等等。
relations - relation描述了“約束”關係。除了我們通常說的R1CS外，還有很多其他約束的描述語言。
reductions - 各種不同描述語言之間的轉化。
knowledge_commit - 在multiexp的基礎上，引入pair的概念，兩個基點一個係數，計算結果稱為一個pair。
zk_proof_systems - 零知識證明中的各種證明系統（包括Groth26，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）
SAP - 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_variables_表示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係數提供擴充套件能力。Groth26計算的時候，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的多項式（透過反傅立葉變換）
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/ 計算A和B，對應FieldT::multiplicative_generator的計算結果
domain->cosetFFT(aA, FieldT::multiplicative_generator);
domain->cosetFFT(aB, FieldT::multiplicative_generator);
3/ 確定C的多項式（透過反傅立葉變換）
for (size_t i = 0; i < cs.num_constraints(); ++i)
{
aC[i] += cs.constraints[i].c.evaluate(full_variable_assignment);
}
domain->iFFT(aC);
4/ 計算C，對應FieldT::multiplicative_generator的計算結果
domain->cosetFFT(aC, FieldT::multiplicative_generator);
5/ 計算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);
6/ 計算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)
著名的Groth26演算法，屬於ppzksnark。因為Groth26在證明之前，需要預處理生成CRS。ppzksnark證明系統又可以細分成好幾種：
其中：
r1cs_gg_ppzksnark，gg代表General Group，就是Groth26演算法。
r1cs_se_ppzksnark，se代表Simulation Extractable，就是GM17演算法。
r1cs_ppzksnark，就是PGHR13演算法。
以Groth26演算法（r1cs_gg_ppzksnark）為例，梳理一下相關的邏輯。Groth26演算法的相關邏輯在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給出了Groth26演算法中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給出了Groth26演算法中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
眾所周知，Groth26的演算法的證明包括A/B/C三個結果。
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 給定一個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
總的來說，Groth26的證明生成和驗證的邏輯如下圖：
可以看出，使用ZKSNARK(Groth26)證明，需要先建立一個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>
