零知識證明：從小白到明白

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

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

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

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

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

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

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

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

   
   
   圖2 零知識證明示例：三色圖問題

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

那zk-SNARK又是啥，和零知識證明什么關系？好，接著往下看。

zk-SNARK：到底是什么鬼？

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

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

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

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

zk-SNARK的實際應用：ZCash

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

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

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

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

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

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

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

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

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

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

圖6 nullifier與commitment的秘密映射

表1 支付前的commitment和nullifier集合

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

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

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

表2 支付后的commitment和nullifier集合

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

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

其他節(jié)點在驗證π有效后才承認此次交易合法。同時，它們無法從π推斷出有關PK1、sk1和r1的任何信息。

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

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

zk-SNARK原理大起底

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

圖7 zk-SNARK原理

1. 將計算問題描述成一個QAP

zk-SNARK作為一種數(shù)學方法，必須有可量化的輸入，證明過程是嚴謹?shù)臄?shù)學推導，因此在運用zk-SNARK之前，首先得為目標問題建立一個數(shù)學描述模型。例如，對于ZCash，一個交易（嚴格地講，是一個交易中包含的JoinSplit描述，相當于一個子交易）可以用以下信息來描述：

圖8 ZCash交易的描述信息

圖9 ZCash交易合法的條件

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

圖10 QAP

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

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

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

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

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

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

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

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

• 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時，C₃(n) = 1。因為，n = 4時，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。

求得多項式向量A(n)、B(n)和C(n)后，計算問題便轉(zhuǎn)換為求取解向量s，使得等式s . C(n) - s . A(n) * s . B(n) = 0 在n=1,2,3,4,5,6時成立，等價于：
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)。各位請注意： 方程式中如愿以償?shù)爻霈F(xiàn)了多項式！

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

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

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

2. 抽樣實現(xiàn)簡潔驗證

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

圖11 zk-SNARK的初次嘗試：計算多項式

圖12 zk-SNARK的再次嘗試：抽樣驗證

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

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

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

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

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

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

別灰（得）心（意），兵來將擋，水來土掩，zk-SNARK的下一招過來了。

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

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

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

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

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

具體描述如下。已知目標問題的QAP形式為s . C(n) - s . A(n) * s . B(n) = H(n) * Z(n)，其中，多項式系數(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)”。按照圖13所示方法，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再設法檢查“E(C(t)-A(t)*B(t) ?= E(H(t)*Z(t))”，從而驗證Anna知道的解是否正確。與圖13方法不同的是，Carl在第1步提供給Anna的不是基本粒子E(tⁿ)，而是三組、每組M個α對（α是Carl產(chǎn)生的隨機值）：

• 第一組數(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))

同時，Carl要求Anna在響應中返回三個α對<E(A(t)), E(α_AA(t))>、<E(B(t)), E(α_BB(t))>和<E(C(t)), E(α_CC(t))>。Anna不知道這幾個α的值，因此根據(jù)KCA推斷：為了生成第一個α對，她只能以Carl提供的第一組α對的某種線性組合來合成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如果僅為滿足α對的約束，可以是任何整數(shù)，三個序列也不用相同。但如果要進一步強迫Anna使用相同的系數(shù)序列，怎么辦呢？答案是引入多項式序列{ L_i(n) } :

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

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

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

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

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

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

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

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

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

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

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

圖15 零交互驗證

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

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

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

假設對于x的任意兩種因數(shù)分解(a, b)和(c, d)（即x=ab=cd），存在兩個加法同態(tài)映射E₁和E₂，以及一個雙線性映射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)隱藏問題便能迎刃而解：E(xy) = e(E₁(x), E₂(y))。于是，我們的zk-SNARK方案有了最終版本，如圖16所示。

圖16 最終的zk-SNARK方案

• CRS中包含了兩種同態(tài)映射值：E₁和E₂。同時，新增了幾個α、β的映射值，它們會在后續(xù)的驗證過程中用到；
• 為了驗證Anna返回的π'_A ?= α_Aπ_A，將其轉(zhuǎn)化為驗證e(π_A, E₂(α_A)) ?= e(π'_A, E₂(1))，因為按照兩者是等價的。同理，圖15中4-(2)、4-(3)步的驗證等式也通過雙線性映射e進行了轉(zhuǎn)化，驗證工作變得可行。

恭喜堅持讀到這里的同學，zk-SNARK的基本原理應該已經(jīng)清楚了。接下來，你可能會問：上文推導zk-SNARK做出了一系列假設，例如，無法通過αa和a的值推導出α，又例如上述雙線性映射存在，那么究竟這些看似不靠譜的假設是否成立呢？感覺不靠譜是因為我們總是站在最熟悉的普通數(shù)世界思考問題，譬如，在這個世界，有乘就有除，因此知道乘積和一個乘數(shù)，做一次除法不就知道另一個乘數(shù)了，哪來的單向性呢？為了得到想要的，我們必須跳出固有思維，進入一個新世界，這便是橢圓曲線的世界！

7. 橢圓曲線：一個新世界

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

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

如果進一步滿足交換律，那么這個群稱為“阿貝群”：

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

請注意，集合和操作是構(gòu)成群的兩個缺一不可的組成部分。以我們熟知的整數(shù)集合{...-3,-2,-1,0,1,2,3...}為例，整數(shù)集分別與加法（+）或乘法（*)結(jié)合可以構(gòu)成兩個不同的群：整數(shù)加法群和整數(shù)乘法群。這里請大家注意了：運算符“·”的含義對于不同的群是不同的，有時候為了便于理解，操作符會寫作“+”或“*”來分別類比普通數(shù)的加法或乘法。對于只有一個操作符的群而言，操作符寫成什么樣子都OK，例如雙線性映射“e(P+R, Q)=e(P,Q)+e(R,Q)”，也可表示為“e(P+R, Q)=e(P,Q)*e(R,Q)”，因為等式中“+”和“*”分別是兩個不同群的操作符。雖然用+更符合表達“線性”的習慣，奈何小爺我愿意呢！

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

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

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

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

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

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

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

• 規(guī)則1：單位元記為O；
• 規(guī)則2：任意一條直線與橢圓曲線相交的所有點（x的指數(shù)為3，最多3個）相加，結(jié)果為O；
• 規(guī)則3：為計算一個點Q的兩倍Q+Q（簡寫為2Q），可畫一條經(jīng)過Q、并與橢圓曲線相切的直線，令這條直線與橢圓曲線的另一個交點為S，那么S = Q + Q。

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

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

圖17 點運算：逆元

圖18 電運算：加法

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

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

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

當點的座標x,y∈F_p時，這些點組成的群是C(F_p)，它的創(chuàng)世點記作G₁。而當座標x,y屬于某個復數(shù)集合時，同樣也能使橢圓曲線方程成立，這些點組成的集合是C(F_p^k)，它的創(chuàng)世點記作G₂?；贕₁和G₂便可分別定義同態(tài)映射E₁(x) = x * G₁和E₂(x) = x * G₂，而經(jīng)過證明存在一種被稱作“Tate reduced pairing”的映射具有雙線性特性，即對于任意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的證明過程便不再展開。由此，實現(xiàn)zk-SNARK的需要的原料找齊了。

未完待續(xù)

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

參考文獻

[1] ZCash protocol, https://github.com/zcash/zips/blob/master/protocol/protocol.pdf 注：ZCash的詳細技術(shù)文檔，符號漫天作雪飛，作為參考吧！
[2] “How Transactions Between Shielded Addresses Work”，https://blog.z.cash/zcash-private-transactions/。注：zcash基本原理的簡單介紹，讀起來沒有壓力，推薦！
[3] “Introduction to zk-SNARKs with examples”，https://media.consensys.net/introduction-to-zksnarks-with-examples-3283b554fc3b。注：通過智能合約實現(xiàn)zk-SNARK驗證的例子，找到一些落地的感覺。同時，清楚解釋了PK（Proof Key）和VK（Verification Key）
[4] “Explaining SNARKs series", https://z.cash/technology/zksnarks.html 注：ZCash官網(wǎng)，詳細解釋zk-SNARK的原理。循序漸進，逐步展開，是本文的主要參考
[5] “zk-SNARKs: Under the Hood”, https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6 注：V神對zk-SNARKS的解讀，與[4]相互印證著看，更容易理解。特別是對QAP和橢圓曲線原理的解釋是[4]所沒有的
[6] “Zero Knowledge Proofs: An illustrated primer”，https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ 注：對zk-SNARK原理的零數(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ù)學概念的解釋
[9] “Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture”，https://eprint.iacr.org/2013/879.pdf 注：25頁有一張圖很好地概述了zk-SNARK協(xié)議