3.4　libsnark開源實(shí)踐簡介

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

libsnark是用于開發(fā)zk-SNARKs應(yīng)用的C++代碼庫，由SCIPR Lab開發(fā)并維護(hù)。libsnark工程實(shí)現(xiàn)背后的理論基礎(chǔ)是近年來（尤其是2013年以來）零知識證明特別是zk-SNARKs方向的一系列重要論文。

從Github上可以看到這個(gè)項(xiàng)目的主要開發(fā)者，如：

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

他們大多都是這個(gè)領(lǐng)域內(nèi)頂尖的學(xué)者或研究牛人。扎實(shí)的理論基礎(chǔ)和工程能力，讓libsnark的作者們能夠化繁為簡，將論文中的高深理論和復(fù)雜公式逐一實(shí)現(xiàn)，高度工程化地抽象出簡潔的接口供廣大開發(fā)者方便地調(diào)用。

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

圖3-11　libsnark的模塊總覽圖

libsnark框架提供了多個(gè)通用證明系統(tǒng)的實(shí)現(xiàn)，其中使用較多的是BCTV14a和Groth16。

查看libsnark/libsnark/zk_proof_systems路徑，就能發(fā)現(xiàn)libsnark對各種證明系統(tǒng)的具體實(shí)現(xiàn)，并且均按不同類別進(jìn)行了分類，還附上了實(shí)現(xiàn)依照的具體論文。

其中，zk_proof_systems/ppzksnark/r1cs_ppzksnark對應(yīng)的是BCTV14a，zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark對應(yīng)的是Groth16。

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

基本原理與步驟

使用libsnark庫進(jìn)行開發(fā)zk-SNARKs應(yīng)用，從原理上可簡要概括為主要4個(gè)步驟：

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

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

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

（4）使用驗(yàn)證算法（V）來驗(yàn)證證明。

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

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

第二步：對應(yīng)下面的Generator函數(shù)G，lambda為隨機(jī)產(chǎn)生，也就是常說的trusted setup過程中產(chǎn)生的“toxic waste”。人們喜歡稱它為“有毒廢物”，是因?yàn)樗仨毐煌咨铺幚恚ㄈ绫仨氫N毀，不能讓任何人知道），否則會影響證明協(xié)議安全。

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

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

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

     proof = P（pk, out, x）

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

     V（vk, out, proof） ?= true

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

圖3-12　電路代碼過程圖

具體的例子，可參見如下兩個(gè)項(xiàng)目：

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

根據(jù)霍華德·吳（libsnark作者之一）的libsnark_tutorial，run_r1cs_gg_ppzksnark（）是主要部分。很容易發(fā)現(xiàn)，真正起作用的實(shí)質(zhì)代碼只有下面5行。

我們從“超長”的函數(shù)名上能直觀地看出每一步是在做什么，但是卻看不到如何構(gòu)造電路的細(xì)節(jié)。實(shí)際上這里僅僅是調(diào)用了自帶的r1cs_example，隱去了實(shí)現(xiàn)細(xì)節(jié)。

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

代碼開頭僅引用了三個(gè)頭文件：

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

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

下面需要進(jìn)行一些初始化工作，定義使用的有限域，并初始化曲線參數(shù)。這相當(dāng)于準(zhǔn)備工作。

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

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

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

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

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

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

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

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

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

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

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

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

再把public input以及witness的數(shù)值傳給prover函數(shù)進(jìn)行證明，可分別通過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函數(shù)校驗(yàn)證明。如果verified = true則說明證明驗(yàn)證成功。

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

從日志輸出中可以看出驗(yàn)證結(jié)果為true，R1CS約束數(shù)量為4，public input和private input數(shù)量分別為1和4。日志輸出符合預(yù)期。

實(shí)際應(yīng)用中，trusted setup、prove、verify會由不同角色分別開展，最終實(shí)現(xiàn)的效果就是prover給verifier一段簡短的proof和public input，verifier可以自行校驗(yàn)?zāi)趁}是否成立。對于前面的例子，就是能在不知道方程的解x具體是多少的情況下，驗(yàn)證prover知道一個(gè)秘密的x可以使得x3 + x + 5 = out成立。

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

使用它進(jìn)行實(shí)戰(zhàn)，我們可以參見安比實(shí)驗(yàn)室的開源代碼示例：https://github.com/secbit/libsnark_abc。