3.4　libsnark開源實踐簡介

libsnark是目前實現zk-SNARKs電路最重要的框架，在眾多私密交易或隱私計算相關項目間廣泛應用，其中最著名當然要數Zcash。Zcash在Sapling版本升級前一直使用libsnark來實現電路（之后才替換為bellman）。毫不夸張地說，libsnark支撐并促進了zk-SNARKs技術的首次大規模應用，填補了零知識證明技術從最新理論到工程實現間的空缺。

libsnark是用于開發zk-SNARKs應用的C++代碼庫，由SCIPR Lab開發并維護。libsnark工程實現背后的理論基礎是近年來（尤其是2013年以來）零知識證明特別是zk-SNARKs方向的一系列重要論文。

從Github上可以看到這個項目的主要開發者，如：

• 馬達斯·維嘉（Madars Virza）
• 霍華德·吳（Howard Wu）
• 伊蘭·特魯莫（Eran Tromer）

他們大多都是這個領域內頂尖的學者或研究牛人。扎實的理論基礎和工程能力，讓libsnark的作者們能夠化繁為簡，將論文中的高深理論和復雜公式逐一實現，高度工程化地抽象出簡潔的接口供廣大開發者方便地調用。

libsnark的模塊總覽如圖3-11所示，摘自libsnark代碼貢獻量第一作者馬達斯·維嘉在MIT的博士論文。

圖3-11　libsnark的模塊總覽圖

libsnark框架提供了多個通用證明系統的實現，其中使用較多的是BCTV14a和Groth16。

查看libsnark/libsnark/zk_proof_systems路徑，就能發現libsnark對各種證明系統的具體實現，并且均按不同類別進行了分類，還附上了實現依照的具體論文。

其中，zk_proof_systems/ppzksnark/r1cs_ppzksnark對應的是BCTV14a，zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark對應的是Groth16。

ppzksnark是指preprocessing zkSNARK。這里的pp/preprocessing其實就是指我們常說的trusted setup，即在證明生成和驗證之前，需要通過一個生成算法來創建相關的公共參數（proving key和verification key）。我們也把這個提前生成的參數稱為“公共參考串“（Common Reference String），或簡稱為CRS。

基本原理與步驟

使用libsnark庫進行開發zk-SNARKs應用，從原理上可簡要概括為主要4個步驟：

（1）將待證明的命題表達為R1CS（Rank One Constraint System）；

（2）使用生成算法（G）為該命題生成公共參數；

（3）使用證明算法（P）生成R1CS可滿足性的證明；

（4）使用驗證算法（V）來驗證證明。

R1CS是一種表示計算的方法，使其能夠滿足零知識證明。基本上任何計算都可以簡化（或平鋪）為一個R1CS。例如向量w上的一個秩為1的約束被定義為

第一步：我們需要將函數C（x, out）在libsnark中進行表達。此處先省略，后面介紹詳細過程。

第二步：對應下面的Generator函數G，lambda為隨機產生，也就是常說的trusted setup過程中產生的“toxic waste”。人們喜歡稱它為“有毒廢物”，是因為它必須被妥善處理（如必須銷毀，不能讓任何人知道），否則會影響證明協議安全。

     lambda <- random（）
（pk, vk） = G（C, lambda）

最終生成proving key（pk）和verification key（vk）。

第三步：對應使用Prove函數（P）生成證明。這里想證明的是prover知道一個秘密值x和計算結果out 可使等式滿足。因此將x、out還有pk 作為輸入一起傳給P，最終生成證明proof。

     proof = P（pk, out, x）

第四步：對應使用Verify函數（V）驗證證明，將proof、out還有vk 傳給G，即可在不暴露秘密的情況下證明存在一個秘密值可使等式滿足。

     V（vk, out, proof） ?= true

而開發者主要工作量就集中在第一步，需要按照libsnark的接口規則手寫C++電路代碼來描述命題，由代碼構造R1CS約束。整個過程也就對應圖3-12的計算（Computation）→算法電路（Arithmetic Circuit）→R1CS。

圖3-12　電路代碼過程圖

具體的例子，可參見如下兩個項目：

• https://github.com/howardwu/libsnark-tutorial
• https://github.com/christianlundkvist/libsnark-tutorial

根據霍華德·吳（libsnark作者之一）的libsnark_tutorial，run_r1cs_gg_ppzksnark（）是主要部分。很容易發現，真正起作用的實質代碼只有下面5行。

我們從“超長”的函數名上能直觀地看出每一步是在做什么，但是卻看不到如何構造電路的細節。實際上這里僅僅是調用了自帶的r1cs_example，隱去了實現細節。

下面通過一個更直觀的例子來學習電路細節。研究src/test.cpp，這個例子改編自克里斯汀·倫德偉（Christian Lundkvist）的libsnark-tutorial。

代碼開頭僅引用了三個頭文件：

前面提到r1cs_gg_ppzksnark對應的是Groth16方案。這里加了gg是為了區別r1cs_ppzksnark（也就是BCTV14a方案），表示Generic Group Model（通用群模型）。Groth16安全性證明依賴Generic Group Model，以更強的安全假設換得了更好的性能和更短的證明。

第一個頭文件是為了引入default_r1cs_gg_ppzksnark_pp類型，第二個則為了引入證明相關的各個接口。pb_variable 則是用來定義電路相關的變量。

下面需要進行一些初始化工作，定義使用的有限域，并初始化曲線參數。這相當于準備工作。

     typedef libff::Fr<default_r1cs_gg_ppzksnark_pp> FieldT;
default_r1cs_gg_ppzksnark_pp::init_public_params（）;

接下來就需要明確“待證命題“是什么。這里不妨沿用之前的例子，證明秘密x滿足等式x3 + x + 5 == out。這實際也是維塔利（Vitalik）博客文章 Quadratic Arithmetic Programs: from Zero to Hero中用的例子。如果對下面的變化陌生，可嘗試閱讀該文章。

通過引入中間變量sym_1、y、sym_2將x3 + x + 5 = out扁平化為若干個二次方程式，幾個只涉及簡單乘法或加法的式子，對應到算術電路中就是乘法門和加法門。你可以很容易地在紙上畫出對應的電路。

     x * x = sym_1
sym_1 * x = y
y + x = sym_2
sym_2 + 5 = out

通常文章到這里便會順著介紹如何按照R1CS的形式編排上面幾個等式，并一步步推導出具體對應的向量。這對理解如何把Gate轉換為R1CS有幫助，然而卻不是本書的核心目的。所以此處省略這些內容。

下面定義與命題相關的變量。首先創建的protoboard是libsnark中的一個重要概念，顧名思義就是“原型板”或者“面包板”，用來快速搭建電路，在zk-SNARKs電路中則是用來關聯所有變量、組件和約束。接下來的代碼定義了所有需要外部輸入的變量以及中間變量。

下面將各個變量與protoboard連接，相當于把各個元器件插到“面包板”上。allocate（）函數的第二個string類型變量僅是用來方便DEBUG時的注釋，方便DEBUG時查看日志。

     out.allocate（pb, "out"）;
x.allocate（pb, "x"）;
sym_1.allocate（pb, "sym_1"）;
y.allocate（pb, "y"）;
sym_2.allocate（pb, "sym_2"）;
pb.set_input_sizes（1）;

注意，此處第一個與pb連接的是out變量。我們知道zk-SNARKs中有public input和private witness的概念，分別對應libsnark中的primary和auxiliary變量。那么如何在代碼中進行區分呢？我們需要借助set_input_sizes（n）來聲明與protoboard連接的public/primary變量的個數n。在這里n = 1，表明與pb連接的前n = 1個變量屬性是public，其余變量的屬性都是private。

至此，所有變量都已經順利與protoboard相連，下面需要確定的是這些變量間的約束關系。這個也很好理解，類似元器件插至面包板后，需要根據電路需求確定它們之間的關系再連線焊接。如下調用protoboard的add_r1cs_constraint（）函數，為pb添加形如a * b = c的r1cs_constraint，即r1cs_constraint（a, b, c）中參數應該滿足a * b = c。根據注釋，不難理解每個等式和約束之間的關系。

至此，變量間的約束添加完成，針對命題的電路構建完畢。下面進入前文提到的“4個步驟”中的第二步：使用生成算法（G）為該命題生成公共參數（pk和vk），即trusted setup。生成出來的proving key和verification key分別可以通過keypair.pk和keypair.vk獲得。

進入第三步，生成證明。先為public input以及witness提供具體數值。不難發現，x = 3, out = 35是原始方程的一個解，則依次為x、out以及各個中間變量賦值。

再把public input以及witness的數值傳給prover函數進行證明，可分別通過pb.primary_input（）和pb.auxiliary_input（）訪問。生成的證明用proof變量保存。

    const r1cs_gg_ppzksnark_proof<default_r1cs_gg_ppzksnark_pp> proof
= r1cs_gg_ppzksnark_prover<default_r1cs_gg_ppzksnark_pp>(keypair.pk,
pb.primary_input(), pb.auxiliary_input());

最后我們使用verifier函數校驗證明。如果verified = true則說明證明驗證成功。

    bool verified = r1cs_gg_ppzksnark_verifier_strong_IC<default_r1cs_gg_
ppzksnark_pp>（keypair.vk, pb.primary_input（）, proof）;

從日志輸出中可以看出驗證結果為true，R1CS約束數量為4，public input和private input數量分別為1和4。日志輸出符合預期。

實際應用中，trusted setup、prove、verify會由不同角色分別開展，最終實現的效果就是prover給verifier一段簡短的proof和public input，verifier可以自行校驗某命題是否成立。對于前面的例子，就是能在不知道方程的解x具體是多少的情況下，驗證prover知道一個秘密的x可以使得x3 + x + 5 = out成立。

通過上面短短的幾十行代碼，就已經使用了zk-SNARKs。

使用它進行實戰，我們可以參見安比實驗室的開源代碼示例：https://github.com/secbit/libsnark_abc。