libsnark庫代碼層次非常清晰。libsnark也給出了SNARK相關算法的全貌，各種Relation，Language，Proof System。爲了更好的生成R1CS電路，libsnark抽象出protoboard和gadget，方便開發者快速搭建電路。在閱讀該示例代碼前，請仔細閱讀libsnark的源代碼分析： 零知識證明 - libsnark源代碼分析

唯一有點遺憾的，libsnark沒有給個完整的電路構造實例，入門者想搭建自己的電路，剛開始有點摸不着頭腦。

爲了方便入門者編寫自己的電路，同事寫了個基於libsnark構造電路，並生成並驗證電路的實例：

https://github.com/StarLI-Trapdoor/libsnark_sample

入門者，可以基於這個示例開發自己的電路。選擇默克爾樹作爲電路的示例，因爲在零知識證明的應用中，大量的使用默克爾樹數據結構。

1 代碼結構

該示例構造了一條merkle路徑的驗證電路，生成並驗證證明。merkle樹的深度爲3，並且merkle樹的計算採用sha256散列函數。代碼結構比較清晰，merkle目錄中的main.cpp是主函數。circuit目錄下的merklecircuit.h是電路的實現。整個項目用cmake進行編譯。

2 電路實現

電路名爲MerkleCircuit，主要依賴兩個gadget：merkle_authentication_path_variable和merkle_tree_check_read_gadget。merkle_authentication_path_variable提供了merkle樹的一條路徑。merkle_tree_check_read_gadget檢查給定一個葉子節點，是否能計算出正確的root。

實現一個電路，主要實現兩個接口函數：

generate_r1cs_constraints - 生成R1CS，該電路比較簡單，只要讓依賴的兩個gadget，生成R1CS即可。

generate_r1cs_witness - 給所有的變量進行賦值。該電路，需要賦值的變量有root，leaf（葉子節點），和葉子節點配套的默克爾路徑，以及默克爾路徑對應的地址信息（也就是每一層的節點的位置，左邊還是右邊）。

整個電路最複雜的就是電路的構造函數，申請變量，創建gadget。其中重點講一講，set_input_sizes函數。libsnark的框架中，使用簡單的區分public和private變量的模型。通過set_input_sizes函數，設置前幾個變量爲public變量。

pb.set_input_sizes(root_digest->digest_size);

也就是說，該電路的公開變量爲root的bit個數。

3 生成和驗證證明

確定了電路的實現，看看main函數，如何生成和驗證證明。

在main函數中定義了merkle樹計算需要的一些類型：

typedef libff::default_ec_pp ppzksnark_ppT;
typedef libff::Fr<ppzksnark_ppT> FieldT;
typedef sha256_two_to_one_hash_gadget<FieldT> HashT;

FieldT默認是bn256橢圓曲線的的Fr，默克爾樹計算採用是sha256算法。

3.1 setup

實現了generate_read_keypair函數，生成pk/vk。仔細看一下generate_read_keypair函數，邏輯簡單清晰：構造MerkleCircuit，在生成R1CS後，調用r1cs_gg_ppzksnark_generator生成pk/vk。

    protoboard<FieldT> pb;
    sample::MerkleCircuit<FieldT, HashT> mc(pb, tree_depth);
    mc.generate_r1cs_constraints();
    r1cs_constraint_system<FieldT> cs = pb.get_constraint_system();
    return r1cs_gg_ppzksnark_generator<ppzksnark_ppT>(cs);

pk存放在merkle_pk.raw文件中，vk存放在merkle_vk.raw中。

3.2 prove

prove邏輯，首先從輸入參數構造一個完整的merkle樹，並根據輸入選定了默克爾路徑。通過generate_read_proof函數生成證明。該函數邏輯也比較清晰：

    protoboard<FieldT> pb;
    sample::MerkleCircuit<FieldT, HashT> mc(pb, tree_depth);
    mc.generate_r1cs_constraints();
    mc.generate_r1cs_witness(pb, leaf, root, path, address, address_bits);
    return r1cs_gg_ppzksnark_prover<ppzksnark_ppT>(proving_key, pb.primary_input(), pb.auxiliary_input());

構造MerkleCircuit，在生成R1CS後，設置各個變量的值。接着通過r1cs_gg_ppzksnark_prover生成證明。

3.3 verify

在獲知vk，證明以及公開信息（root）的基礎上，調用r1cs_gg_ppzksnark_verifier_strong_IC的接口完成驗證。這也就是verify_read_proof函數的邏輯。

4 編譯和運行

在編譯之前，同步該項目依賴的libsnark庫：

git submodule update --init --recursive

4.1 編譯

mkdir build; cd build; cmake ..

編譯完成，merkle目錄下會生成merkle的可執行文件。

4.2 可信設置（trusted setup）

./merkle setup

4.3 生成證明

./merkle prove [data1] [data2] [data3] [data4] [data5] [data6] [data7] [data8] [index]

prove命令，需要提供原始的3層merkle樹的8個葉子節點，並指定需要證明的第幾個葉子節點對應的路徑（index指明）。

4.4 驗證

./merkle verify [root]

其中，root信息是在prove中生成過程中打印出來的root信息（也是公開信息）。如果驗證通過，就說明存在一條能生成root的merkle路徑，雖然沒有公開路徑的具體信息。

總結：

libsnark庫代碼層次非常清晰，並抽象出protoboard和gadget，方便開發者快速搭建電路。本文給出了一個基於libsnark庫開發的完整電路示例。示例實現了3層默克爾樹的一條默克爾路徑的驗證。其中默克爾樹採用sha256的散列函數。

相關文章