零知識(shí)證明：從小白到明白

如今，知識(shí)快餐業(yè)發(fā)達(dá)，區(qū)塊鏈這么火的領(lǐng)域自然不會(huì)落下。經(jīng)過(guò)一輪輪掃盲，共識(shí)、工作量證明、閃電網(wǎng)絡(luò)等等概念對(duì)普羅大眾已不再陌生，甚至各種解構(gòu)、比喻、引申，將術(shù)語(yǔ)炒得比本義還玄乎。然而，如果不理解甚至沒聽說(shuō)過(guò)零知識(shí)證明，那你基本還屬于區(qū)塊鏈小白。

之所以這么說(shuō)，原因有二。其一， 零知識(shí)證明是代數(shù)數(shù)論、抽象代數(shù)等數(shù)學(xué)理論的綜合應(yīng)用，與閃電網(wǎng)絡(luò)一類的精巧設(shè)計(jì)不同，屬于硬技術(shù)。如果不是數(shù)學(xué)科班出生，它引入的概念、符號(hào)會(huì)讓人眼花繚亂。V神（以太坊ethreum的創(chuàng)始人。本名Vitalik Buterin，對(duì)于國(guó)人而言，這名字讀起來(lái)有點(diǎn)困難，同時(shí)考慮到這位90后小哥創(chuàng)造以太坊時(shí)才19歲，因此幣圈尊稱其“V神”）在一篇介紹零知識(shí)證明的文章中就提醒讀者看不懂也不要懷疑自己的智商，因?yàn)椤八鼘?shí)在是太難了！”因此，能堅(jiān)持搞懂的，一定是意（固）志（執(zhí)）力有異常人。呵呵，過(guò)獎(jiǎng)了o(*￣︶￣*)o！

其二，零知識(shí)證明解決了區(qū)塊鏈應(yīng)用的一個(gè)根本問(wèn)題。區(qū)塊鏈的應(yīng)用價(jià)值在于去中性化共識(shí)，無(wú)論是貨幣交易還是權(quán)益證明，所有成員都是見證人，眾目睽睽之下，一旦交易完成便無(wú)法抵賴，權(quán)益生成便不能否認(rèn)。但這也意味著，你收了誰(shuí)多少錢，名下有幾套房對(duì)于所有人都是透明的，這顯然與隱私保護(hù)的剛性需求相違背。雖然一些針對(duì)隱私保護(hù)的混淆技術(shù)被提出，例如達(dá)世幣（Dash）的PrivateSend，但終究只能在一定程度上緩解而不能根治去中心化引入的這個(gè)固有問(wèn)題。好在世上從來(lái)不缺聰明人，沒讓大家等多久，零知識(shí)證明橫空出世（嚴(yán)格說(shuō)來(lái)，零知識(shí)證明提出應(yīng)早于區(qū)塊鏈技術(shù)，但無(wú)疑是后者讓其為世人所知）。零知識(shí)證明要解決的問(wèn)題是：以不透露一個(gè)論斷（statement）的任何信息為前提，向你證明這個(gè)論斷是對(duì)的。以貨幣交易為例，就是在不告訴你付款人、收款人是誰(shuí)，也不告訴你金額多少的前提下，設(shè)法證明這筆交易是合法的。o((⊙﹏⊙))o這怎么可能呢？！

這是有可能的。圖1是一個(gè)經(jīng)常用來(lái)科普零知識(shí)證明的例子。圖中所示是一個(gè)山洞，入口處有兩條路A和B，而這兩條路在山洞深處被一道門給隔開了，只有說(shuō)出開門魔咒門才能打開。這里涉及兩個(gè)角色P（Proofer）和V（Verifier），P試圖向V證明，他知道開門魔咒；如果屬實(shí)，V就饒ta不死。P自然不能直接將魔咒告訴V，因?yàn)槿f(wàn)一ta知道后把自己干掉怎么辦；V則一定不會(huì)輕易相信P。他們可以這么做：

1. P從A、B兩條路中隨機(jī)選擇一條走進(jìn)去；這時(shí)，V在洞外等著，對(duì)P選擇了哪條路一無(wú)所知；
2. 等待足夠長(zhǎng)時(shí)間后，V進(jìn)入山洞，然后也從A、B中隨機(jī)選擇一個(gè)并且大聲喊出來(lái)，譬如，“B！”；
3. P聽到V的聲音后便從對(duì)應(yīng)的那條路走出來(lái)。如果P確實(shí)知道開門魔咒，那么無(wú)論自己和V分別選擇的是A還是B，P都能正確地從V報(bào)出的路走出來(lái)。相反，如果P不知道魔咒，那么ta只有1/2的概率會(huì)做到。而從V的角度來(lái)說(shuō)，如果ta看到P從正確的路出來(lái)了，ta便有50%的把握肯定P確實(shí)知道魔咒；
4. 將第1-3步重復(fù)N次，如果P每次都能做對(duì)，那么V便有1-(0.5)^N的把握相信P。例如，N=5，可靠性就是96.9%，已經(jīng)足夠好了。更重要的是，V對(duì)于魔咒仍然一無(wú)所知。這便是零知識(shí)證明。
   
   圖1 零知識(shí)證明示例：我知道開門咒語(yǔ)

有點(diǎn)意思，對(duì)吧？可能你會(huì)覺得這個(gè)例子不夠“嚴(yán)肅”，太喜劇化完全不像講技術(shù)。那好，再來(lái)一個(gè)例子-著名的“三色圖問(wèn)題（graph tree-coloring）”，見圖2。所謂三色圖問(wèn)題就是找到一種上色方案使得相鄰兩個(gè)節(jié)點(diǎn)的顏色不同（子圖(1)中以連線表示兩個(gè)節(jié)點(diǎn)相鄰）。三色圖是一個(gè)NP問(wèn)題（NP是啥玩意？別急，后文會(huì)詳細(xì)解釋），這意味著求解過(guò)程十分復(fù)雜。因此，當(dāng)Anna應(yīng)Carl的委托好容易找出一個(gè)三色圖問(wèn)題的答案，沒拿到報(bào)酬是絕不愿意出示答案的。那作為Prover角色的Anna如何向Carl證明她知道答案呢？步驟如下：

1. Anna把問(wèn)題圖中已經(jīng)正確上色的節(jié)點(diǎn)都遮起來(lái)，見子圖(2)；
2. Carl從中任意選相鄰的兩個(gè)節(jié)點(diǎn)，Anna便向其展示這兩個(gè)節(jié)點(diǎn)的顏色，見子圖(3)。如果這兩個(gè)節(jié)點(diǎn)的顏色不同，那么Carl便有50%的把握相信Anna確實(shí)知道答案；

3. 接著，Anna隨機(jī)選擇一種顏色映射方案將目前圖中的顏色變換成另一種顏色，例如“紫色->白色，橙色->黃色，綠色->黑色”，這樣便生成了一張新的上色圖。雖然顏色不同，但仍是原問(wèn)題的有效解。接著重復(fù)第1-3步N次，如果每次展示的兩個(gè)節(jié)點(diǎn)顏色都不相同，那么Anna知道答案的可靠性便是1-(0.5)^N。

   
   
   圖2 零知識(shí)證明示例：三色圖問(wèn)題

類似的例子還可以舉出不少，例如數(shù)獨(dú)、finding waldo（在一幅密密麻麻都是人的圖片中找到某個(gè)特定人物的游戲）。找到點(diǎn)感覺了吧？這就是零知識(shí)證明。

那zk-SNARK又是啥，和零知識(shí)證明什么關(guān)系？好，接著往下看。

zk-SNARK：到底是什么鬼？

zk-SNARK是“zero knowledge Succinct Non-interactive ARgument of Knowledge”的縮寫，這一長(zhǎng)串名字的主體是“argument of knowledge”，即“知情證明”，也就是掌握某事內(nèi)幕的證據(jù)。修飾主體名詞的定語(yǔ)由三部分組成，分別代表了此技術(shù)要解決的三個(gè)問(wèn)題，分別是：

1. zero knowledge：零知識(shí)，即在證明的過(guò)程中不透露任何內(nèi)情，如上文的例子所示；
2. succinct：簡(jiǎn)潔的，主要是指驗(yàn)證過(guò)程不涉及大量數(shù)據(jù)傳輸以及驗(yàn)證算法簡(jiǎn)單；
3. non-interactive：無(wú)交互。上文中舉的兩個(gè)例子雖然實(shí)現(xiàn)了零知識(shí)證明，但Prover和Verifier之間需要經(jīng)過(guò)多次交互才能取得滿意的可靠性，而此技術(shù)試圖徹底避免這些交互。

合起來(lái)，zk-SNARK是一種“證明我知道內(nèi)情的技術(shù)，簡(jiǎn)單、易操作，最關(guān)鍵的是你除了“我是對(duì)的”啥也不會(huì)知道”。

ZCash（大零幣，貨幣符號(hào)是ZEC。本文寫作到此處時(shí)，ZEC的單價(jià)為$223）是最早廣泛應(yīng)用zk-SNARK的數(shù)字貨幣。ZCash采用zk-SNARK技術(shù)，目的是徹底解決交易被追蹤從而暴露用戶隱私的問(wèn)題。如果上文的例子讓你覺得是toy example，那么結(jié)合ZCash便能更確切地理解zk-SNARK的應(yīng)用場(chǎng)景。

zk-SNARK的實(shí)際應(yīng)用：ZCash

ZCash的核心概念與比特幣是一脈相承的。當(dāng)然，這不奇怪，誰(shuí)讓比特幣是“初代吸金鬼”呢？（注：如果讀者對(duì)比特幣基本原理還不清楚，那基本屬于走錯(cuò)片場(chǎng)了，請(qǐng)先閱讀比特幣原理一文）。簡(jiǎn)單回顧一下比特幣交易：

1. 一個(gè)比特幣交易（Transaction）接受若干輸入（Transaction Input, TI），同時(shí)產(chǎn)生若干輸出（Transaction Output, TO）；
2. TI和TO是相對(duì)一個(gè)特定交易而言的，因?yàn)橐粋€(gè)交易的TO可能成為另一個(gè)交易的TI，這是一個(gè)將掙來(lái)的錢再花出去的過(guò)程；在還沒花出去前，這些錢就是“Unspent”的，因此此刻尚未成為下一個(gè)交易TI的TO稱為“UXTO(Unspent Transaction Output)”。UXTO是比特幣交易的基本單元；
3. 交易的付款方需證明自己有權(quán)使用這些UTXO，方法是提供私鑰進(jìn)行驗(yàn)證，因?yàn)槊總€(gè)交易TO會(huì)指定收款人的公鑰，保證只有收款人才能接著花它。

ZCash繼承了比特幣的交易模型，只不過(guò)UTXO被衍生出的新概念“note”所代替，后者是ZCash的基本交易單元。英語(yǔ)中，“note”有“鈔票”的意思。不過(guò)，翻譯成“支票”更貼切，因?yàn)槊繌坣ote上都標(biāo)注了只有誰(shuí)才能兌現(xiàn)它（即所有者）。一個(gè)交易的輸入和輸出都是若干note。為描述方便起見，將note記為“note=(PK, v, r)”，其中，PK是所有者的公鑰（地址），v是金額，而r是可以唯一區(qū)分該note的序列號(hào)。

所不同的是，ZCash交易分為兩類：透明地址和隱藏地址。透明地址交易的輸入、輸出直接是可見的note信息，一個(gè)例子如圖3所示（除了貨幣單位外，和比特幣交易一模一樣）。

圖3 ZCash交易例子：透明地址

圖4 ZCash交易例子：隱藏地址

圖5 ZCash交易例子：混用透明和隱藏地址

在隱藏地址的交易中，輸入、輸出不再是明文的note，而分別是note的廢止通知和簽發(fā)通知：

• 簽發(fā)通知（note commitment）：作為交易的輸出，表示一張新note被簽發(fā)。一個(gè)有效的commitment是一張note存在的證明，然而從它包含的信息中并不知道是哪張note，也就無(wú)法知道所有者是誰(shuí)，金額多少。為滿足這一點(diǎn)，最簡(jiǎn)單的方法是對(duì)note的描述信息取哈希，因此note對(duì)應(yīng)的commitment可以簡(jiǎn)單描述為“HASH(note)”；
• 廢止通知（note nullifier）：作為交易的輸入，表示一張老支票將作廢（因?yàn)轳R上要被兌現(xiàn)、花掉了）。同比特幣一樣，一個(gè)交易的輸入一定是另一個(gè)交易的輸出，因此nullifier對(duì)應(yīng)唯一一個(gè)commitment（結(jié)合commitment的定義，也就唯一對(duì)應(yīng)一張note)，但從它包含的信息并不能推導(dǎo)出是哪個(gè)commitment（如果可以的話，ZCash交易便可被追蹤，因而喪失隱私性了）。為構(gòu)造滿足要求的nullifier，取哈希依然是個(gè)好辦法，因此序號(hào)為r的note，對(duì)應(yīng)的nullifier可描述為“HASH(r)”。

通過(guò)引入nullifier和commitment，交易之間路人皆知的關(guān)聯(lián)變成了付款人和收款人的心照不宣，如圖6所示。

圖6 nullifier與commitment的秘密映射

表1 支付前的commitment和nullifier集合

Anna決定將金額為v1的note1轉(zhuǎn)給Carl，他的公鑰/地址是PK4，她將這么操作：

1. 隨機(jī)挑選一個(gè)序列號(hào)r4，并以此產(chǎn)生note4 = (PK4, v1, r4)；
2. 秘密地將note4發(fā)給Carl；
3. 將note1的nullifier，即nf2 = HASH(r1)，以及新產(chǎn)生的note4的commitment，即其哈希值HASH(note4)廣播給所有節(jié)點(diǎn)。

收到Anna廣播的節(jié)點(diǎn)，會(huì)檢查nf2是否已存在于nullifier集合中；若沒有，說(shuō)明對(duì)應(yīng)的支票沒有重復(fù)兌現(xiàn)，節(jié)點(diǎn)會(huì)將HASH(note4)和NF2分別加入到所維護(hù)的commitment和nullifier隊(duì)列中，如表2所示。nullifier所起的作用就是防止數(shù)字貨幣被“重復(fù)支付”的基礎(chǔ)問(wèn)題（我不喜歡將“double spend”翻譯成“雙花”，總感覺像在討論植物學(xué)）。

表2 支付后的commitment和nullifier集合

這就是ZCash的原理...咦，等等，不對(duì)吧？！怎么知道Anna給的NF2對(duì)應(yīng)的支票存在真的存在，萬(wàn)一是她精心選擇的垃圾數(shù)據(jù)怎么辦？就算NF2確實(shí)指向一張支票，那怎么知道Anna有權(quán)兌現(xiàn)它呢？Anna自然可以通過(guò)公布note1的內(nèi)容來(lái)證明，但如此一來(lái)，她的小秘密就大白于天下了。啊哈~~，我們的零知識(shí)證明這時(shí)就能排上用場(chǎng)：Anna會(huì)同時(shí)提供一份憑證 π。π足以證明提供人（這里值A(chǔ)nna）知道能滿足以下條件的PK1，sk1（PK1對(duì)應(yīng)的私鑰）和r1的值：

1. 用PK1、r1復(fù)原的note數(shù)據(jù)結(jié)構(gòu)，其哈希值存在于commitment集合中 → 用以支付的note是有效的；
2. sk1是PK1的私鑰 → Anna有權(quán)使用這張note；
3. HASH(r1) = NF2 → nullifier與commitment一致。

其他節(jié)點(diǎn)在驗(yàn)證π有效后才承認(rèn)此次交易合法。同時(shí)，它們無(wú)法從π推斷出有關(guān)PK1、sk1和r1的任何信息。

恭喜你，讀到這，你應(yīng)該基本清楚零知識(shí)證明、zk-SNARK是啥，能解決什么問(wèn)題了。但究竟如何做到的還未交待，zk-SNARK仍是謎一樣的存在。子不語(yǔ)怪力亂神。吾輩豈甘淺嘗輒止，必要一睹其中機(jī)巧為快。因此，繼續(xù)！

友情提示：前方深水區(qū)，請(qǐng)注意安全，量力前往！:)

zk-SNARK原理大起底

zk-SNARK背后的原理相當(dāng)復(fù)雜，如果沒有一張地圖，很容易在不斷涌現(xiàn)的概念中迷失。因此，為了便于理解，下文將按照如圖7所示的線索來(lái)展開。

圖7 zk-SNARK原理

1. 將計(jì)算問(wèn)題描述成一個(gè)QAP

zk-SNARK作為一種數(shù)學(xué)方法，必須有可量化的輸入，證明過(guò)程是嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)推導(dǎo)，因此在運(yùn)用zk-SNARK之前，首先得為目標(biāo)問(wèn)題建立一個(gè)數(shù)學(xué)描述模型。例如，對(duì)于ZCash，一個(gè)交易（嚴(yán)格地講，是一個(gè)交易中包含的JoinSplit描述，相當(dāng)于一個(gè)子交易）可以用以下信息來(lái)描述：

圖8 ZCash交易的描述信息

圖9 ZCash交易合法的條件

zk-SNARK只適合特定形式的計(jì)算問(wèn)題，即所謂QAP（Quadratic Arithmetic Programs）。不要糾結(jié)于這個(gè)術(shù)語(yǔ)，籠統(tǒng)地說(shuō)，就是計(jì)算方程中需要出現(xiàn)多項(xiàng)式。ZCash的例子太復(fù)雜，不適合講解，因此以一個(gè)簡(jiǎn)單的多項(xiàng)式方程x**3+x+5 = 35（這個(gè)方程的解是x=3，因?yàn)?**3+3+5 = 35）來(lái)舉例說(shuō)明將目標(biāo)計(jì)算問(wèn)題轉(zhuǎn)換為一個(gè)QAP的過(guò)程。請(qǐng)重點(diǎn)觀察：伴隨著問(wèn)題的轉(zhuǎn)化，解的形式會(huì)發(fā)生什么變化。

圖10 QAP

如圖10所示，轉(zhuǎn)換分三步完成：

1. 通過(guò)引入中間變量，將計(jì)算式x**3+x+5轉(zhuǎn)換為若干簡(jiǎn)單算式。這些簡(jiǎn)單算式要么是“x = y”或者“x = y (op) z”的形式。操作符“op”代表加（+)、減（-）、乘（*）和除（/）。這些簡(jiǎn)單算式可視為數(shù)字電路中的邏輯門，因此也被稱為“代數(shù)電路（Algebraic Circuit）”。圖10例中引入的中間變量是sym_1、sym_2和sym_3；

解的新形式：
x=3, sym_1=9, sym_2=27, sym_3=30, ~out=35（將這些變量的值代入各個(gè)簡(jiǎn)單算式，所有等式成立）

2. 定義向量s=[~one, x, ~out, sym_1, sym_2, sym_3]（~one是偽變量，表示常數(shù)1），將每個(gè)簡(jiǎn)單算式轉(zhuǎn)換為“s . c = s . a * s . b”的形式。其中，“."代表向量?jī)?nèi)積（將兩個(gè)向量對(duì)應(yīng)位置的成員相乘，結(jié)果再累加），a、b和c是其系數(shù)向量。依次完成所有簡(jiǎn)單算式的轉(zhuǎn)化，將系數(shù)向量分別順序排列，便得到A、B和C三個(gè)矩陣（例如，矩陣**C**的最后一行，就是簡(jiǎn)單算式“~out = sym_3 + 5”的系數(shù)向量c）。這個(gè)描述形式有個(gè)專門的術(shù)語(yǔ)，稱作"一階約束系統(tǒng)（L1CS）”。滿足所有約束條件的向量s就是問(wèn)題的解；

解的新形式：
s = [~one, x, ~out, sym_1, sym_2, sym_3] = [1, 3, 35, 9, 27, 30]

3. 最后一步，將每個(gè)矩陣壓縮為一個(gè)多項(xiàng)式組成的向量，例如矩陣C → C(n)=[C₁(n), C₂(n), C₃(n), C₄(n), C₅(n), C₆(n)]。方法是：對(duì)矩陣的每一列分別運(yùn)用拉格朗日插值法。譬如，矩陣C的第3列為[0,0,0,1]，現(xiàn)在要求取一個(gè)多項(xiàng)式C₃(n)，使得n分別取1、2、3、4時(shí)，C₃(n)的值為：

表3 C₃(n)在不同n的取值

按照拉格朗日插值法，C₃(n)可以分解為4個(gè)部分之和：

• C_{3_1}(n) = A(n-2)(n-3)(n-4)
• C_{3_2}(n) = B(n-1)(n-3)(n-4)
• C_{3_3}(n) = C(n-1)(n-2)(n-4)
• C_{3_4}(n) = D(n-1)(n-2)(n-3)
• C₃(n) = C_{3_1}(n) + C_{3_2}(n) + C_{3_3}(n) + C_{3_4}(n)

按照表3，已知n = 4時(shí)，C₃(n) = 1。因?yàn)椋琻 = 4時(shí)，C_{3_1}(n)、C_{3_2}(n)和C_{3_3}(n)分別為0，因此，C_{3_4}(4) = D(4-1)(4-2)(4-3) = 1，從而得到D = 1/6。同理，A = B = C = 0。于是，可知C₃(n) = 1/6*(n-1)*(n-2)*(n-3) = 0.166n**3-n**2+1.833n-1。

求得多項(xiàng)式向量A(n)、B(n)和C(n)后，計(jì)算問(wèn)題便轉(zhuǎn)換為求取解向量s，使得等式s . C(n) - s . A(n) * s . B(n) = 0 在n=1,2,3,4,5,6時(shí)成立，等價(jià)于：
s . C(n) - s . A(n) * s . B(n) = H(n) * Z(n)，其中， Z(n) = (n-1)(n-2)(n-3)(n-4)(n-5)(n-6)。各位請(qǐng)注意： 方程式中如愿以償?shù)爻霈F(xiàn)了多項(xiàng)式！

問(wèn)題算式發(fā)生變化，但解的形式未變，仍為：
s = [~one, x, ~out, sym_1, sym_2, sym_3] = [1, 3, 35, 9, 27, 30]

為啥一定要處心積慮地搞出多項(xiàng)式來(lái)呢？為了以抽樣來(lái)實(shí)現(xiàn)驗(yàn)證過(guò)程的“簡(jiǎn)潔”。這是下一節(jié)的內(nèi)容，在動(dòng)身之前先解釋一下什么叫“NP問(wèn)題”。

NP是根據(jù)計(jì)算復(fù)雜性對(duì)計(jì)算問(wèn)題劃分的一種類別：對(duì)于NP問(wèn)題，驗(yàn)證一個(gè)解是否正確的步驟可表示輸入規(guī)模的一個(gè)多項(xiàng)式。譬如，驗(yàn)證一個(gè)n次方程的解是否正確需要完成的乘法次數(shù)為O(n₂)，因此n次方程就是一個(gè)NP問(wèn)題。請(qǐng)注意，這里說(shuō)的是“驗(yàn)證”，而不是求解。如果一個(gè)問(wèn)題的解可在多項(xiàng)式步驟內(nèi)求得，這個(gè)問(wèn)題稱為P問(wèn)題。顯然，P問(wèn)題是NP問(wèn)題的一個(gè)子集?！霸诙囗?xiàng)式時(shí)間內(nèi)完成”相當(dāng)于“可行”，因此，對(duì)于NP問(wèn)題，驗(yàn)證它的解是否正確是“可行的”；而對(duì)于P問(wèn)題，更進(jìn)一步，求出它的解也是可行的。驗(yàn)證和求解的不對(duì)稱性是密碼學(xué)應(yīng)用的基礎(chǔ)。譬如，對(duì)于哈希函數(shù)，已知Hash(x) = N（常數(shù)），當(dāng)x的取值范圍很大時(shí)，求解x十分困難；而給定一個(gè)x=X，驗(yàn)證Hash(X) ?= N卻十分簡(jiǎn)單。因此，用戶密碼經(jīng)常是以哈希值來(lái)保存，防止原始密碼泄露。NP和P的劃分并不是絕對(duì)的，如果數(shù)學(xué)方法上取得突破，NP也可能變成P，即NP=P。應(yīng)該慶幸目前還沒有人做到這一點(diǎn)，否則當(dāng)今互聯(lián)網(wǎng)的安全基礎(chǔ)將徹底崩塌。

2. 抽樣實(shí)現(xiàn)簡(jiǎn)潔驗(yàn)證

上一節(jié)對(duì)問(wèn)題進(jìn)行一系列轉(zhuǎn)化，目的是向“零知識(shí)”證明靠近。假設(shè)Anna知道原始問(wèn)題“x**3+x+5 = 35”的解，如果不對(duì)問(wèn)題進(jìn)行轉(zhuǎn)化，Anna為了自證，好像除了公布解（x=3），似乎也沒有別的辦法。然而，問(wèn)題轉(zhuǎn)化為求解“s . C(n) - s . A(n) * s . B(n) = H(n) * Z(n)”后（其中，系數(shù)向量*A*(n)、*B*(n)和*C*(n)是公開的），Anna可以她知道的解s，計(jì)算多項(xiàng)式P(n)和H(n) = P(n)/Z(n)，然后將兩個(gè)多項(xiàng)式P(n)、H(n)發(fā)給驗(yàn)證者Carl；后者通過(guò)檢查P(n) ?= H(n) * Z(n)是否成立來(lái)判斷Anna是否真的知道解。 從圖11可以看出，Anna并沒有直接將解s告知Carl，也可以向Carl證明自己知道解，是不是有點(diǎn)“零知識(shí)”的感覺了？

圖11 zk-SNARK的初次嘗試：計(jì)算多項(xiàng)式

圖12 zk-SNARK的再次嘗試：抽樣驗(yàn)證

那這樣看來(lái)，抽樣點(diǎn)t不能讓Prover（Anna）知道，同時(shí)還得讓Prover能給出抽樣點(diǎn)處的值。這做得到么？答案是可以做到，通過(guò)“同態(tài)隱藏（Homomorphic Hiding）”。

3. 利用同態(tài)映射隱藏抽樣點(diǎn)

“同態(tài)隱藏”是輸入x到輸出X的某種映射（mapping）E的特性：

• 對(duì)于絕大多數(shù)的x，已知X=E(x)，無(wú)法推導(dǎo)出x；
• 如果x₁≠x₂，則E(x₁)≠E(x₂)；
• E(ax₁+bx₂) = a * E(x₁) + b * E(x₂)，即加法同態(tài)：經(jīng)過(guò)映射后，加法的計(jì)算形式仍然得以保留

假設(shè)我們找到了一個(gè)具有同態(tài)隱藏特性的映射E，便可利用它來(lái)對(duì)我們的零知識(shí)證明方法進(jìn)行改進(jìn)。如圖13所示，Carl（Verifier）不再直接將抽樣點(diǎn)告知Anna，而是提供了t的一系列指數(shù)t⁰、t¹、t²、t³...t^N的映射值E(1)、E(t¹)、E(t²)、E(t³)...E(t^N)（N是一個(gè)比任何涉及多項(xiàng)式的階數(shù)都大的整數(shù)）。由于不知道t，Anna無(wú)法直接計(jì)算P(t)和H(t)，只能根據(jù)上述映射值來(lái)計(jì)算E(P(t))和E(H(t))。多項(xiàng)式P(t)和H(t)分別是{tⁿ, n=(1,2,3...,N)}的線性組合，按照同態(tài)映射性質(zhì)，E(P(t))和E(H(t))也應(yīng)分別是{E(tⁿ), n=(1,2,3...,N)}的線性組合。Carl收到Anna的響應(yīng)后，通過(guò)檢查E(P(t)) ?= E(H(t) * Z(t))（Carl知道t的值，因此可以算出Z(t) = a，進(jìn)而求解E(aH(t))）便可判定P(t) ?= H(t)*Z(t)，進(jìn)而決定是否接受Anna的證據(jù)。Anna不知道t，也就不能找到合適的H(t)正好使“E(P(t)) = E(H(t) * Z(t))”成立，這樣第一個(gè)漏洞便堵上了。

圖13 zk-SNARK的又次嘗試：同態(tài)隱藏抽樣點(diǎn)

別灰（得）心（意），兵來(lái)將擋，水來(lái)土掩，zk-SNARK的下一招過(guò)來(lái)了。

4. KCA：除了規(guī)矩做人，你別無(wú)選擇

Verifier如何才能知道Prover計(jì)算P(n)使用的是不是規(guī)定的系數(shù)向量A(n)、B(n)和C(n)呢？這一過(guò)程便稱為KCA（Knowledge of Coefficient Test and Assumption）。原理如下。

假設(shè)有兩個(gè)東東a、b，滿足b=α * a的約束（α為整數(shù)，“α * a”相當(dāng)于α個(gè)a相加），那么這一對(duì)東東(a, b)稱為一個(gè)“α對(duì)”。如果我把(a, b)告知你，但α對(duì)你保密，現(xiàn)在要求你提供另一個(gè)α對(duì)，你該怎么辦？你可能會(huì)說(shuō)，這還不容易，先通過(guò)“b/a”求出α，然后再任意挑一個(gè)a'，并算出對(duì)應(yīng)的b'就好。如果a和b是普通數(shù)字、加法是普通加法，“b除以a”是存在的，的確如此?？扇绻癰除以a”的運(yùn)算做不了（這是可能的，后文解釋），又該如何？這時(shí)，你只有一個(gè)選擇，那就是分別將a和b乘以一個(gè)整數(shù)γ，則(a', b') = (γ*a, γ*b)也是一個(gè)α對(duì)，即b' = γ * b = α * γ * a = α * a'。

接下來(lái)，將此問(wèn)題擴(kuò)展一下：如果預(yù)先提供給你的不是一個(gè)而是N個(gè)α對(duì)(a₁, b₁)，(a₂, b₂)，...，(a_N, b_N)，還是讓你返回一個(gè)新的α對(duì)，那怎么整呢？方法是類似的，那就是返回一個(gè)由a系列和b系列值的相同線性組合組成的值對(duì)，即(c₁*a₁ + c₂*a₂+...+c_N*a_N, c₁*b₁ + c₂*b₂+...+c_N*b_N)，其中c_n是任意整數(shù)。反過(guò)來(lái)，從出題者的角度而言，ta通過(guò)檢查你提供的(a', b')是否一個(gè)α對(duì)，便可基本確信：你返回的兩個(gè)值a'和b'是ta所提供的a系列和b系列值的相同線性組合（為啥說(shuō)“基本”呢？因?yàn)檫€無(wú)法從數(shù)學(xué)上證明，只能算“good enough”）。

回到我們的zk-SNARK方案存在的漏洞二：如何才能保證Prover回答的是應(yīng)該回答的問(wèn)題呢？如上文所述，此漏洞的根源在于Anna可以選擇任意P'(n)來(lái)響應(yīng)Carl的質(zhì)詢，而P'(n)可能與目標(biāo)問(wèn)題的系數(shù)多項(xiàng)式向量A(n)、B(n)和C(n)沒有一毛錢關(guān)系。既然如此，我們可以在圖13所示方法的基礎(chǔ)上進(jìn)一步改進(jìn)：Carl可以在質(zhì)詢中只提供A(t)、B(t)和C(t)的值，Anna因而被迫只能基于它們來(lái)構(gòu)建應(yīng)答，此漏洞由此得以堵上。強(qiáng)迫的手段便是KCA。

具體描述如下。已知目標(biāo)問(wèn)題的QAP形式為s . C(n) - s . A(n) * s . B(n) = H(n) * Z(n)，其中，多項(xiàng)式系數(shù)向量A(n)、B(n)、C(n)和解向量s(n)分別為（M為QAP形式解向量s的階數(shù)）：

• A(n)=[A₁(n), A₂(n), A₃(n),..., A_M(n)]
• B(n)=[B₁(n), B₂(n), B₃(n),..., B_M(n)]
• C(n)=[C₁(n), C₂(n), C₃(n),..., C_M(n)]
• s(n)=[s₁(n),s₂(n),s₃(n),...,s_M(n)]

令：

• A(n) = s(n) . A(n) = Σs_i*A_i(n)
• B(n) = s(n) . B(n) = Σs_i*B_i(n)
• C(n) = s(n) . C(n) = Σs_i*B_i(n)

那么，QAP方程式可描述為“C(n) - A(n) * B(n) = H(n) * Z(n)”。按照?qǐng)D13所示方法，Carl要求Anna提供A(n)、B(n)、C(n)和H(n)在n=t的采樣值的同態(tài)隱藏E(A(t))、E(B(t))、E(C(t))和E((H(t))，Carl再設(shè)法檢查“E(C(t)-A(t)*B(t) ?= E(H(t)*Z(t))”，從而驗(yàn)證Anna知道的解是否正確。與圖13方法不同的是，Carl在第1步提供給Anna的不是基本粒子E(tⁿ)，而是三組、每組M個(gè)α對(duì)（α是Carl產(chǎn)生的隨機(jī)值）：

• 第一組數(shù)據(jù)
  E(A₁(t)), E(α_AA₁(t)) （注：根據(jù)同態(tài)映射的性質(zhì)，E(α_AA₁(t)) = α_AE(A₁(t))，下同。）
  E(A₂(t)), E(α_AA₂(t))
  ...
  E(A_M(t)), E(α_AA_M(t))
• 第二組數(shù)據(jù)
  E(B₁(t)), E(α_BB₁(t))
  E(B₂(t)), E(α_BB₂(t))
  ...
  E(B_M(t)), E(α_BB_M(t))
• 第三組數(shù)據(jù)
  E(C₁(t)), E(α_CC₁(t))
  E(C₂(t)), E(α_CC₂(t))
  ...
  E(C_M(t)), E(α_CC_M(t))

同時(shí)，Carl要求Anna在響應(yīng)中返回三個(gè)α對(duì)<E(A(t)), E(α_AA(t))>、<E(B(t)), E(α_BB(t))>和<E(C(t)), E(α_CC(t))>。Anna不知道這幾個(gè)α的值，因此根據(jù)KCA推斷：為了生成第一個(gè)α對(duì)，她只能以Carl提供的第一組α對(duì)的某種線性組合來(lái)合成E(A(t))和E(αA(t))：

• E(A(t)) = E(a₁*A₁(t) + a₂*A₂(t) + ... + a_M*A_M(t)) = a₁*E(A₁(t)) + a₂*E(A₂(t)) + ... + a_M*E(A_M(t))
• E(α_AA(t)) = E(a₁*α_AA₁(t) + a₂*α_AA₂(t) + ... + a_M*α_AA_M(t)) = a₁*E(α_AA₁(t)) + a₂*E(α_AA₂(t)) + ... + a_M*E(α_AA_M(t))

同理，Anna可以構(gòu)建：

• E(B(t)) = b₁*E(B₁(t)) + b₂*E(B₂(t)) + ... + b_M*E(B_M(t))
• E(α_BB(t)) = b₁*E(α_BB₁(t)) + b₂*E(α_BB₂(t)) + ... + b_M*E(α_BB_M(t))
• E(C(t)) = c₁*E(C₁(t)) + c₂*E(C₂(t)) + ... + c_M*E(C_M(t))
• E(α_CC(t)) = c₁*E(α_CC₁(t)) + c₂*E(α_CC₂(t)) + ... + c_M*E(α_CC_M(t))

其中，系數(shù)a_i、b_i和c_i如果僅為滿足α對(duì)的約束，可以是任何整數(shù)，三個(gè)序列也不用相同。但如果要進(jìn)一步強(qiáng)迫Anna使用相同的系數(shù)序列，怎么辦呢？答案是引入多項(xiàng)式序列{ L_i(n) } :

• L_i(n) = A_i(n) + B_i(n) + C_i(n)

令L(n) = Σl_iL_i(n)，那么當(dāng)“a_i=b_i=c_i=l_i(t)”時(shí)，有：
L(n) = Σl_iL_i(n) = A(n) + B(n) + C(n)
等價(jià)于：
隨機(jī)選擇一個(gè)β，對(duì)任意n=t, E(βL(t)) = E(β*(A(t) + B(t) + C(t))) = β*(E(A(t)) + E(B(t)) + E(C(t)))
另一計(jì)算E(βL(t))的方法是：E(βL(t)) = Σl_iE(βL_i(t))。如果β對(duì)Anna而言是未知的，那么有理由相信：只有當(dāng)Anna選擇相同的系數(shù)a_i、b_i、c_i和l_i，才能保證兩種方法計(jì)算的E(βL(t))對(duì)于任何采樣點(diǎn)t都是相等的。

因此，Carl發(fā)給Anna的質(zhì)詢中還應(yīng)包括第四組數(shù)據(jù)：

• 第四組數(shù)據(jù)
  E(βL₁(t))
  E(βL₂(t))
  ...
  E(βL_M(t))

而Anna的響應(yīng)中相應(yīng)增加E(βL(t)) ：

• E(βL(t)) = E(l₁*βL₁(t) + l₂*βL₂(t) + ... + l_M*βL_M(t))

Carl通過(guò)檢查Anna響應(yīng)數(shù)據(jù)的一致性，即“E(βL(t)) ?= β*(E(A(t)) + E(B(t)) + E(C(t)))”來(lái)檢驗(yàn)系數(shù)a_i、b_i和c_i是否相同。

最后，為了讓Anna能計(jì)算E(H(t))，質(zhì)詢中還應(yīng)增加第五組數(shù)據(jù)：

• 第五組數(shù)據(jù)
  E(1), E(t), E(t²), ..., E(t^N)

綜上所述，引入KCA機(jī)制后，我們的zk-SNARK方案如圖14所示。

圖14 zk-SNARK的另次嘗試：KCA

圖15 零交互驗(yàn)證

5. 雙線性映射(bilinear map）：乘法的同態(tài)隱藏

前文介紹的同態(tài)隱藏是一對(duì)一的，即將一個(gè)輸入映射到一個(gè)輸出。而雙線性映射是將分別來(lái)自兩個(gè)域的兩個(gè)元素映射到第三個(gè)域中的一個(gè)元素：e(X, Y) → Z，同時(shí)在兩個(gè)輸入上都具備線性：

• e(P+R, Q) = e(P, Q) + e(R, Q)
• e(P, Q+S) = e(P, Q) + e(P, S)

假設(shè)對(duì)于x的任意兩種因數(shù)分解(a, b)和(c, d)（即x=ab=cd），存在兩個(gè)加法同態(tài)映射E₁和E₂，以及一個(gè)雙線性映射e，使得以下等式總是成立：

• e(E₁(a), E₂(b)) = e(E₁(c), E₂(d)) = X

那么，x->X的映射也是加法同態(tài)映射，記作E。E的線性屬性證明如下：
E(ax₁+bx₂)
= e(E₁(ax₁+bx₂), E₂(1))
= e(a*E₁(x₁) + b*E₁(x₂), E₂(1))
= a*e(E₁(x₁), E₂(1)) + b*e(E₁(x₂), E₂(1))
= a*E(x₁) + b*E(x₂)

如果我們找到這種映射E，乘法的同態(tài)隱藏問(wèn)題便能迎刃而解：E(xy) = e(E₁(x), E₂(y))。于是，我們的zk-SNARK方案有了最終版本，如圖16所示。

圖16 最終的zk-SNARK方案

• CRS中包含了兩種同態(tài)映射值：E₁和E₂。同時(shí)，新增了幾個(gè)α、β的映射值，它們會(huì)在后續(xù)的驗(yàn)證過(guò)程中用到；
• 為了驗(yàn)證Anna返回的π'_A ?= α_Aπ_A，將其轉(zhuǎn)化為驗(yàn)證e(π_A, E₂(α_A)) ?= e(π'_A, E₂(1))，因?yàn)榘凑諆烧呤堑葍r(jià)的。同理，圖15中4-(2)、4-(3)步的驗(yàn)證等式也通過(guò)雙線性映射e進(jìn)行了轉(zhuǎn)化，驗(yàn)證工作變得可行。

恭喜堅(jiān)持讀到這里的同學(xué)，zk-SNARK的基本原理應(yīng)該已經(jīng)清楚了。接下來(lái)，你可能會(huì)問(wèn)：上文推導(dǎo)zk-SNARK做出了一系列假設(shè)，例如，無(wú)法通過(guò)αa和a的值推導(dǎo)出α，又例如上述雙線性映射存在，那么究竟這些看似不靠譜的假設(shè)是否成立呢？感覺不靠譜是因?yàn)槲覀兛偸钦驹谧钍煜さ钠胀〝?shù)世界思考問(wèn)題，譬如，在這個(gè)世界，有乘就有除，因此知道乘積和一個(gè)乘數(shù)，做一次除法不就知道另一個(gè)乘數(shù)了，哪來(lái)的單向性呢？為了得到想要的，我們必須跳出固有思維，進(jìn)入一個(gè)新世界，這便是橢圓曲線的世界！

7. 橢圓曲線：一個(gè)新世界

數(shù)學(xué)有一個(gè)稱為“抽象代數(shù)”的分支，主要研究對(duì)象是代數(shù)結(jié)構(gòu)，例如群、環(huán)、域。所謂“代數(shù)結(jié)構(gòu)”就是一個(gè)集合以及定義在此集合上的運(yùn)算。例如，“群（group）”就是由一個(gè)集合以及一個(gè)二元運(yùn)算符“·”組成，它具備以下性質(zhì)：

• 封閉性： 對(duì)于所有G中a, b，運(yùn)算a·b的結(jié)果也在G中。
• 結(jié)合律： 對(duì)于所有G中的a, b和c，等式 (a·b)·c = a· (b·c)成立。
• 單位元： 存在G中的一個(gè)元素e，使得對(duì)于所有G中的元素a，總有等式e·a = a·e = a 成立。
• 逆元： 對(duì)于每個(gè)G中的a，存在G中的一個(gè)元素b使得總有a·b = b·a = e，此處e為單位元。

如果進(jìn)一步滿足交換律，那么這個(gè)群稱為“阿貝群”：

• 交換律：對(duì)于所有G中的a和b和c，等式 a·b = a· b成立。

請(qǐng)注意，集合和操作是構(gòu)成群的兩個(gè)缺一不可的組成部分。以我們熟知的整數(shù)集合{...-3,-2,-1,0,1,2,3...}為例，整數(shù)集分別與加法（+）或乘法（*)結(jié)合可以構(gòu)成兩個(gè)不同的群：整數(shù)加法群和整數(shù)乘法群。這里請(qǐng)大家注意了：運(yùn)算符“·”的含義對(duì)于不同的群是不同的，有時(shí)候?yàn)榱吮阌诶斫?，操作符?huì)寫作“+”或“*”來(lái)分別類比普通數(shù)的加法或乘法。對(duì)于只有一個(gè)操作符的群而言，操作符寫成什么樣子都OK，例如雙線性映射“e(P+R, Q)=e(P,Q)+e(R,Q)”，也可表示為“e(P+R, Q)=e(P,Q)*e(R,Q)”，因?yàn)榈仁街小?”和“*”分別是兩個(gè)不同群的操作符。雖然用+更符合表達(dá)“線性”的習(xí)慣，奈何小爺我愿意呢！

令p為一個(gè)素?cái)?shù)，在集合{0,1,2,3,...,p-1}上，也可以定義加法和乘法操作，不過(guò)與普通加法、乘法不同的是：結(jié)果需要對(duì)p取模，分別稱為模加和模乘。例如，假設(shè)p=7，則：

• 模加： 4 + 5 = 2 (mod 7)
• 模乘： 3 * 6 = 4 (mod 7)

同整數(shù)集一樣，集合{0,1,2,3,...,p-1}分別與模加或模乘結(jié)合構(gòu)成了兩個(gè)群。同時(shí)，它與這兩個(gè)操作符一起還構(gòu)成了一個(gè)域，記做F_p。所謂“域”，就是一個(gè)集合及定義在其上的兩個(gè)操作：加法和乘法，這兩個(gè)操作滿足以下全部條件：

• 結(jié)合加法，構(gòu)成一個(gè)加法阿貝群。加法群的單位元記為“0”；
• 非“0”元素組成的子集，結(jié)合乘法，構(gòu)成一個(gè)乘法阿貝群；
• 乘法對(duì)加法符合交換律：對(duì)于任何a、b、c∈F_p，a * (b + c) = a * b + a * c。

那位讀者說(shuō)，你叨叨了這半天，只字未提“橢圓曲線”，是不是串線了啊？呵呵，別急，這是必要的鋪（前）墊（戲）。通過(guò)上述例子，想傳遞一個(gè)概念：如果普通數(shù)與普通加、乘構(gòu)建是我們熟悉的世界，那么通過(guò)重新定義規(guī)則，便可構(gòu)建起無(wú)數(shù)的平行世界。在舊世界看似不可能的事情，放到新世界卻有可能實(shí)現(xiàn)。基于橢圓曲線便可構(gòu)建一個(gè)這樣的新世界。

先解釋什么是橢圓曲線。假設(shè)p為大約3的素?cái)?shù)，取u,v∈F_p（敲黑板，就是上面由兩個(gè)模運(yùn)算和集合{0,1,2,3,...,p-1}構(gòu)建的域)且滿足：4u³+27v²≠0，可定義等式Y(jié)² = X³ + uX + v，那么，由座標(biāo)(x,y)滿足上述等式的點(diǎn)組成的集合就稱為橢圓曲線。

在橢圓曲線這個(gè)由點(diǎn)組成的集合上也可以定義“加法”。加法遵守的基本規(guī)則是：

• 規(guī)則1：?jiǎn)挝辉洖?strong>O；
• 規(guī)則2：任意一條直線與橢圓曲線相交的所有點(diǎn)（x的指數(shù)為3，最多3個(gè)）相加，結(jié)果為O；
• 規(guī)則3：為計(jì)算一個(gè)點(diǎn)Q的兩倍Q+Q（簡(jiǎn)寫為2Q），可畫一條經(jīng)過(guò)Q、并與橢圓曲線相切的直線，令這條直線與橢圓曲線的另一個(gè)交點(diǎn)為S，那么S = Q + Q。

基于規(guī)則2，可以有以下兩個(gè)推論：

• 推論1：經(jīng)過(guò)任意點(diǎn)P畫一條垂直x軸的線，與橢圓曲線相較于Q，則P+Q=O，因此，Q=-P，Q為P的逆元。見圖17；
• 推論2：若P、Q兩點(diǎn)的x座標(biāo)不相同（P、Q不互為逆元），連接P和Q畫一條直線，與橢圓曲線相較于R，則P+Q+R=O，即P+Q=-R。見圖18。

圖17 點(diǎn)運(yùn)算：逆元

圖18 電運(yùn)算：加法

基于上述點(diǎn)運(yùn)算的規(guī)則和推論不難看出：橢圓曲線的點(diǎn)與我們定義出來(lái)的加法也構(gòu)建出了另一個(gè)阿貝群，記作C(F_p)，一個(gè)新世界。這個(gè)新世界又給我們帶來(lái)什么可能呢？讀者是否還記得，我們?cè)谝隟CA時(shí)提到：已知α * a和a，無(wú)法求出α？如果a和b是普通數(shù)，難以想象；但如果a和b是橢圓曲線上的點(diǎn)，這便是千真萬(wàn)確的，因?yàn)樵跈E圓曲線運(yùn)算中，兩個(gè)點(diǎn)的除法不存在（或者更精確的說(shuō)，還沒有找到有效的算法）。

由此，我們可以定義映射E：x→P，其中x屬于F_p，而P是橢圓曲線上的點(diǎn)，并且滿足：P = x * G。等式中的G也是橢圓曲線的一個(gè)點(diǎn)，不過(guò)它比較特殊的是：橢圓曲線上的所有點(diǎn)都可以由它經(jīng)過(guò)若干次自加（G+G+G+...）得到，因此它被稱為創(chuàng)世點(diǎn)（generator）。映射E就是一種前面幾節(jié)透支的加法同態(tài)映射：

• 對(duì)于x、y∈F_p， E(ax+by) = (ax+by) * G = ax * G + by * G = a * E(x) + b * E(y)

當(dāng)點(diǎn)的座標(biāo)x,y∈F_p時(shí)，這些點(diǎn)組成的群是C(F_p)，它的創(chuàng)世點(diǎn)記作G₁。而當(dāng)座標(biāo)x,y屬于某個(gè)復(fù)數(shù)集合時(shí)，同樣也能使橢圓曲線方程成立，這些點(diǎn)組成的集合是C(F_p^k)，它的創(chuàng)世點(diǎn)記作G₂?；贕₁和G₂便可分別定義同態(tài)映射E₁(x) = x * G₁和E₂(x) = x * G₂，而經(jīng)過(guò)證明存在一種被稱作“Tate reduced pairing”的映射具有雙線性特性，即對(duì)于任意P、R∈C(F_p)，Q、S∈C(F_p^k)，存在：

• e(P+R, Q) = e(P, Q) + e(R, Q)
• e(P, Q+S) = e(P, Q) + e(P, S)

鑒于篇（理）幅（解）有限，Tate reduced pairing的證明過(guò)程便不再展開。由此，實(shí)現(xiàn)zk-SNARK的需要的原料找齊了。

未完待續(xù)

zk-SNARK已在ZCash中應(yīng)用，因而不再是紙上談兵。然而其實(shí)用性還有待檢驗(yàn)，畢竟產(chǎn)生零知識(shí)證明的代價(jià)是相當(dāng)高的（在ZCash，高達(dá)30~40秒），是否真能帶來(lái)足夠的安全尚不十分清楚。我接下來(lái)會(huì)對(duì)ZCash的實(shí)現(xiàn)進(jìn)行進(jìn)一步研究，將在下一篇博文中向同樣好學(xué)的你介紹其技術(shù)實(shí)現(xiàn)細(xì)節(jié)，希望到時(shí)候咱們可以動(dòng)手實(shí)踐yi'fan。

參考文獻(xiàn)

[1] ZCash protocol, https://github.com/zcash/zips/blob/master/protocol/protocol.pdf 注：ZCash的詳細(xì)技術(shù)文檔，符號(hào)漫天作雪飛，作為參考吧！
[2] “How Transactions Between Shielded Addresses Work”，https://blog.z.cash/zcash-private-transactions/。注：zcash基本原理的簡(jiǎn)單介紹，讀起來(lái)沒有壓力，推薦！
[3] “Introduction to zk-SNARKs with examples”，https://media.consensys.net/introduction-to-zksnarks-with-examples-3283b554fc3b。注：通過(guò)智能合約實(shí)現(xiàn)zk-SNARK驗(yàn)證的例子，找到一些落地的感覺。同時(shí)，清楚解釋了PK（Proof Key）和VK（Verification Key）
[4] “Explaining SNARKs series", https://z.cash/technology/zksnarks.html 注：ZCash官網(wǎng)，詳細(xì)解釋zk-SNARK的原理。循序漸進(jìn)，逐步展開，是本文的主要參考
[5] “zk-SNARKs: Under the Hood”, https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6 注：V神對(duì)zk-SNARKS的解讀，與[4]相互印證著看，更容易理解。特別是對(duì)QAP和橢圓曲線原理的解釋是[4]所沒有的
[6] “Zero Knowledge Proofs: An illustrated primer”，https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ 注：對(duì)zk-SNARK原理的零數(shù)學(xué)解讀，適合建立起基本概念。特別是對(duì)于證明“零知識(shí)”可能性的思想游戲證明很有啟發(fā)
[7] “How toxic is the waste in a zkSNARK trusted setup?”，https://medium.com/qed-it/how-toxic-is-the-waste-in-a-zksnark-trusted-setup-9b250d59bdb4 注：解釋了如何利用“核廢料”造假
[8] “群、環(huán)、域”，https://blog.csdn.net/u013281331/article/details/28233961 注：一些必要數(shù)學(xué)概念的解釋
[9] “Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture”，https://eprint.iacr.org/2013/879.pdf 注：25頁(yè)有一張圖很好地概述了zk-SNARK協(xié)議