1. 原始碼結構
contracts - 實現了groth26的驗證智慧合約（Verifier.sol），橢圓曲線的計算，MerkleTree以及MiMC Hash計算的智慧合約。這些智慧合約可以透過truffle進行部署測試。部署相關的指令碼在migrations目錄下。
ethsnarks - python實現的相關功能，包括pedersen/mimc/poseidon等hash函式，groth26驗證，以及橢圓曲線的計算。
test - 以上兩個功能的測試程式碼，採用python語言實現。
depends - 依賴庫，包括libsnark，libfqfft等等。
src - 基於libsnark的gadget1庫實現的更多的gadget。本文著重介紹這些gadget的實現。
2. gadget實現
src目錄下的原始碼結構如下：
2.1 ethsnarks.hpp
libsnark的gadget1庫主要圍繞sha256（基於bit的hash函式）實現各種gadgets。ethsnarks在alt_bn128這條橢圓曲線上實現了基於Field的hash函式（mimc，pedersen，poseidon等）。
libsnark的電路中各種定義都非常長。libsnark定義一個變數陣列型別：pb_variable_array<FieldT>。
ethsnarks.hpp精簡了在alt_bn128這條橢圓曲線相關的型別宣告：
namespace ethsnarks {
typedef libff::bigint<libff::alt_bn128_r_limbs> LimbT;
typedef libff::alt_bn128_G1 G1T;
typedef libff::alt_bn128_G2 G2T;
typedef libff::alt_bn128_pp ppT;
typedef libff::Fq<ppT> FqT;
typedef libff::Fr<ppT> FieldT;
typedef libsnark::r1cs_constraint<FieldT> ConstraintT;
typedef libsnark::protoboard<FieldT> ProtoboardT;
typedef libsnark::pb_variable<ethsnarks::FieldT> VariableT;
typedef libsnark::pb_variable_array<FieldT> VariableArrayT;
typedef libsnark::pb_linear_combination<FieldT> LinearCombinationT;
typedef libsnark::pb_linear_combination_array<FieldT> LinearCombinationArrayT;
typedef libsnark::linear_term<FieldT> LinearTermT;
typedef libsnark::gadget<ethsnarks::FieldT> GadgetT;
typedef libsnark::r1cs_gg_ppzksnark_zok_proof<ppT> ProofT;
typedef libsnark::r1cs_gg_ppzksnark_zok_proving_key<ppT> ProvingKeyT;
typedef libsnark::r1cs_gg_ppzksnark_zok_verification_key<ppT> VerificationKeyT;
typedef libsnark::r1cs_gg_ppzksnark_zok_primary_input<ppT> PrimaryInputT;
typedef libsnark::r1cs_gg_ppzksnark_zok_auxiliary_input<ppT> AuxiliaryInputT;
}
其中，FieldT特指在alt_bn128線上的點的個數。
2.2 utils.hpp/utils.cpp
utils實現了電路實現中常用的功能性函式。
inline const VariableT make_variable( ProtoboardT &in_pb, const std::string &annotation )
{
VariableT x;
x.allocate(in_pb, annotation);
return x;
}
make_variable建立一個VariableT。
const VariableArrayT flatten( const std::vector<VariableArrayT> &in_scalars )
{
size_t total_sz = 0;
for( const auto& scalar : in_scalars )
total_sz += scalar.size();
VariableArrayT result;
result.resize(total_sz);
size_t offset = 0;
for( const auto& scalar : in_scalars )
{
for( size_t i = 0; i < scalar.size(); i++ )
{
result[offset++].index = scalar[i].index;
}
}
return result;
}
flatten函式將多個VariableArrayT合併成一個VariableArray。其實也很簡單，就是把VariableArray中的index都合併到一個VariableArray中。
2.3 r1cs_gg_ppzksnark_zok
在libsnark的r1cs_gg_ppzksnark的基礎上，稍做改動，讓以太坊的預編譯智慧合約能驗證groth26的演算法。r1cs_gg_ppzksnark_zok目錄中的README.md很清晰的解釋了改動的原因。
從以太坊的拜占庭硬分叉之後，以太坊引入了基於ALT_BN128的配對函式計算的預編譯合約，合約實現的功能如下：
給定ALT_BN128上兩個基點（G1/G2）一系列的點(a1, b1, a2, b2, ..., ak, bk)，預編譯合約能檢查：
e(a1, b1) * ... * e(ak, bk) 是否等於1？
Groth26原有的驗證係數為：vk.alpha_beta，vk.gamma以及vk.delta。Groth26的驗證等式為：
vk.alpha_beta = e(A, B) * e(-x, vk.gamma) * e(-C, vk.delta)
其中vk.alpha_beta為e(alpha, beta)。
如果直接用之前的驗證等式，以太坊上的預編譯合約沒法實現。在不影響Groth26的安全性的情況下，將Groth26的驗證係數變為：vk.alpha，vk.beta，vk.gamma以及vk.delta。Groth26的驗證等式也變為：
e(A, B) * e(-x, vk.gamma) * e(-C, vk.delta) * e(-alpha, beta) = 1
r1cs_gg_ppzksnark_zok目錄就是實現如上的改動。同時提供了stubs.hpp/stubs.cpp，從json檔案中讀取相應的驗證引數進行驗證。
2.4 poseidon
poseidon演算法的實現在gadgets/poseidon.hpp檔案中。
template<unsigned nInputs, unsigned nOutputs, bool constrainOutputs=true>
using Poseidon128 = Poseidon_gadget_T<6, 1, 8, 57, nInputs, nOutputs, constrainOutputs>;
Poseidon128是Poseidon_gadget_T的一個例項。前面四個引數是poseidon演算法的引數，後續會寫文章詳細介紹poseidon演算法以及這些引數的含義（6，1，8，57是預設的配置）。nInputs指定演算法的輸入的個數，nOutputs指定輸出的個數，contrainOutputs指定是否對輸出進行約束。
Poseidon_gadget_T的建構函式如下：
Poseidon_gadget_T(
ProtoboardT &pb,
const VariableArrayT& in_inputs,
const std::string& annotation_prefix
) :
GadgetT(pb, annotation_prefix),
inputs(in_inputs),
constants(poseidon_params<param_t, param_F, param_P>()),
first_round(pb, constants.C[0], constants.M, in_inputs, FMT(annotation_prefix, ".round[0]")),
prefix_full_rounds(
make_rounds<FullRoundT>(
1, partial_begin, pb,
first_round.outputs, constants, annotation_prefix)),
partial_rounds(
make_rounds<PartialRoundT>(
partial_begin, partial_end, pb,
prefix_full_rounds.back().outputs, constants, annotation_prefix)),
suffix_full_rounds(
make_rounds<FullRoundT>(
partial_end, total_rounds-1, pb,
partial_rounds.back().outputs, constants, annotation_prefix)),
last_round(pb, constants.C.back(), constants.M, suffix_full_rounds.back().outputs, FMT(annotation_prefix, ".round[%u]", total_rounds-1)),
_output_vars(constrainOutputs ? make_var_array(pb, nOutputs, ".output") : VariableArrayT())
{
}
poseidon演算法的計算由好幾輪組成：first_round（第一輪），prefix_full_rounds（預處理，完整輪），partial_rounds(中間，不完整輪)，suffix_full_rounds（後處理，完整輪）以及last_round（最後一輪）。
_output_vars是輸出的變數。這些輪都是透過make_rounds函式實現。
template<typename T>
static const std::vector<T> make_rounds(
unsigned n_begin, unsigned n_end,
ProtoboardT& pb,
const std::vector<libsnark::linear_combination<FieldT> >& inputs,
const PoseidonConstants& constants,
const std::string& annotation_prefix)
{
std::vector<T> result;
result.reserve(n_end - n_begin);
for( unsigned i = n_begin; i < n_end; i++ )
{
const auto& state = (i == n_begin) ? inputs : result.back().outputs;
result.emplace_back(pb, constants.C[i], constants.M, state, FMT(annotation_prefix, ".round[%u]", i));
}
return result;
}
make_rounds就是為每一輪準備合適的引數。每一輪的具體實現透過Poseidon_Round實現。
在Poseidon_Round的封裝下，Poseidon_gadget_T的generate_r1cs_constraints以及generate_r1cs_witness相對簡單，小夥伴們可以自行檢視原始碼。
3. 示例程式碼
在ethsnarks的基礎上，實現Poseidon函式的電路就非常簡單了。構造一個簡單的電路，給大家參考一下。
電路的需求：實現Poseidon計算，輸入為兩個FieldT，輸出為一個FieldT。輸出作為電路的public input。
#include "ethsnarks.hpp"
#include "gadgets/poseidon.hpp"
using namespace ethsnarks;
namespace testproject {
using TestHash = Poseidon128<2, 1>;
class test_gadget : public GadgetT {
public:
VariableT output;
VariableT input0;
VariableT input1;
TestHash tHash;
test_gadget(
ProtoboardT& pb,
const std::string& prefix
) : GadgetT(pb, prefix),
output(make_variable(pb, FMT(prefix, ".output"))),
input0(make_variable(pb, FMT(prefix, ".input0"))),
input1(make_variable(pb, FMT(prefix, ".input1"))),
tHash(pb, create_var_array({input0, input1}), FMT(prefix, ".testhash"))
{
}
void generate_r1cs_witness(
ethsnarks::FieldT w_input0,
ethsnarks::FieldT w_input1,
ethsnarks::FieldT w_output)
{
pb.val(input0) = w_input0;
pb.val(input1) = w_input1;
pb.val(output) = w_output;
tHash.generate_r1cs_witness();
}
void generate_r1cs_constraints()
{
pb.set_input_sizes(1);
tHash.generate_r1cs_constraints();
pb.add_r1cs_constraint(ConstraintT(output, 1, tHash.result()),
FMT(annotation_prefix, " output == Poseidon(input0 || input1)"));
}
};
};
總結：
ethsnarks在libsnark的基礎上，實現了以太坊上與zkSNARK相關的智慧合約和電路。ethsnarks本身也是libsnark應用很好的學習示例。libsnark的gadget1庫主要圍繞sha256（基於bit的hash函式）實現各種gadgets。ethsnarks在alt_bn128這條橢圓曲線上實現了基於Field的hash函式（mimc，pedersen，poseidon等）。
