官术网_书友最值得收藏!

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 可使等式滿足。因此將xout還有pk 作為輸入一起傳給P,最終生成證明proof。

     proof = P(pk, out, x)

第四步:對應(yīng)使用Verify函數(shù)(V)驗(yàn)證證明,將proofout還有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。

主站蜘蛛池模板: 沧源| 伽师县| 霍邱县| 两当县| 锡林郭勒盟| 东兰县| 麦盖提县| 伽师县| 六盘水市| 江津市| 大足县| 桦甸市| 大化| 梧州市| 广昌县| 花莲县| 吴川市| 江山市| 镇沅| 利辛县| 三河市| 旬阳县| 桐梓县| 大冶市| 拜泉县| 剑阁县| 会同县| 左权县| 道真| 临安市| 沾益县| 科尔| 准格尔旗| 厦门市| 蓬莱市| 东莞市| 和静县| 宽甸| 嘉定区| 宁乡县| 南川市|