零知識證明是一種可在多方交互驗證需求中實現隱私保護的密碼學方案，用於在不泄露具體數據的情況下對數據知識的掌握或相關計算的正確性進行證明，經過密碼學學術界和金融科技等產業界多年的理論研究與實踐檢驗，目前已在區塊鏈等與數據隱私相關的創新業務場景實現了落地應用。

本文介紹了零知識證明的基本概念、研究進展、實現原理等情況，並對zk-SNARK等典型的通用零知識證明算法進行了分析，最後對零知識證明技術在區塊鏈與數字貨幣、安全多方計算等領域的應用進行了梳理總結。

一、零知識證明概述

零知識證明（Zero-Knowledge Proof, ZKP）是現代密碼學中的一類經典協議，用於在不泄露關於某個命題任何信息的情況下證明該命題的正確性。近年來，隨着區塊鏈等新興技術的發展以及隱私計算需求的興起，零知識證明技術再次成爲包括金融科技、大數據等相關行業關注的焦點。

如圖1所示爲零知識證明的一個經典模型——洞穴模型[1]，該模型不涉及具體算法實現，僅用於初步說明零知識證明的原理和效果。

圖1：洞穴模型

在圖中，C點和D點之間存在一道密門，只有知道祕密口令的人才能打開。證明者（Prover）P知道祕密口令，並希望向驗證者（Verifier）V證明，但又不希望泄露祕密口令，可通過以下證明過程實現：

 ①首先，驗證者V站在A點，證明者P站在B點；
 ②證明者P隨機選擇走到C點或D點，驗證者V在A點無法看到證明者P選擇的方向；
 ③驗證者V走到B點，並要求證明者P從左通道/右通道的方向出來；
 ④證明者P根據驗證者V的要求從指定方向出來，如有必要需要用祕密口令打開密門。

如果證明者P知道祕密口令，就一定能正確地從驗證者V要求的方向出來；如果證明者P不知道祕密口令，則每次有1/2的概率能從驗證者V要求的方向出來。該證明過程可重複進行多次，直到驗證者V相信證明者P擁有打開密門的祕密口令。

通過以上證明過程，證明者P就向驗證者V完成了關於祕密口令的零知識證明，即證明過程不會泄露任何關於祕密口令的知識。

1、概念起源與發展

零知識證明的概念最早在20世紀80年代由美國麻省理工學院的Shafi Goldwasser、Silvio Micali和Charles Rackoff在論文《The Knowledge Complexity of Interactive Proof Systems（交互式證明系統中的知識複雜性）》（以下簡記爲GMR85）中提出[2]，該論文對交互式證明系統的零知識性進行了數學定義，並提出了一種關於二次剩餘（Quadratic Residue）判定問題的零知識證明協議。二次剩餘問題是數論中的經典問題，其內容是給定互素的整數a和n，判斷a是否是模n的二次剩餘。由於當n爲合數時，不存在多項式時間的算法能夠判定該問題，因此二次剩餘問題是一個等價於整數分解問題的NP問題。GMR85論文提出的二次剩餘問題證明協議可實現證明者向驗證者證明a是模n的二次剩餘，而驗證者在相信該論斷的同時無法獲知x的具體值等除“a是模n的二次剩餘”以外的任何信息。

GMR85等早期論文提出的方案大多數是專用的交互式零知識證明協議，僅能證明某一類特定的問題，且需要證明者和驗證者進行多輪交互才能完成，其功能和實際應用效果難以滿足現實應用場景的要求。爲了能夠實現針對任意問題的通用證明協議，同時避免多次交互給實際應用帶來的侷限性，非交互式通用證明協議的研究成爲了零知識證明自概念誕生以來的重要發展方向。

目前，數據安全與隱私保護成爲了區塊鏈等應用中的重要需求，零知識證明這一經典的密碼學算法有了新的應用前景。在區塊鏈應用場景中，實現多參與方的頻繁交互是不現實的，且複雜多樣的業務模式催生了通用證明協議的應用需求。因此，zk-SNARK等非交互式通用零知識證明協議在區塊鏈與數字貨幣等場景中得到了廣泛的應用。

2、經典示例

爲了能夠更加清楚地說明零知識證明的概念，本小節用數獨問題[3]和三色圖問題[4]兩個簡單的示例進行具體闡述。

（1）數獨問題

如圖2所示的數獨遊戲盤面爲由九個3×3區域（宮）組成的9×9九宮格，要求玩家在這個已經填有若干1~9數字（謎面）的9×9九宮格內繼續填滿數字（謎底），使得每一行、每一列、每一宮（3×3）內都包含不重複的1~9數字。

圖2：數獨遊戲

證明者P希望向驗證者V證明其知道某個數獨遊戲的解，但又不希望向驗證者V泄露解的具體內容，可通過以下過程實現證明：

 ①證明者P將9組1~9數字寫在81張卡片上，並在驗證者V迴避的情況下按照解的排列擺放好，謎面數字朝上，謎底數字朝下；
 ②驗證者V隨機選擇按照每一行、每一列或每一宮進行驗證；
 ③證明者P在驗證者V的見證下，按照驗證者V的要求將81張卡片以每一行/列/宮爲一組放在9個不透明的袋子中，並打亂每個袋子中的卡片順序，交給驗證者V；
 ④驗證者V打開9個袋子，如果每個袋子中均爲9個1~9不重複的數字，則本次驗證通過。

證明者P通過預先猜測驗證者V會選擇哪種驗證方式（行/列/宮）進而成功欺騙驗證者V的概率是1/3。因此，驗證者V可以每次隨機選擇不同的驗證方式將以上證明過程重複多次，直到驗證者V相信證明者P知道該數獨遊戲的解，且驗證者V在整個過程中並不能獲知任何關於解的具體信息。

（2）三色圖問題

三色圖問題即用三種顏色對一個地圖進行着色，使得任意兩個相鄰區域的顏色均不相同。三色圖問題是一個NP完全問題，不存在多項式時間內的求解算法。根據圖論原理，地圖的着色問題可以等價於連通圖的頂點着色問題。爲了便於表示，以下用連通圖的頂點着色進行問題說明，其證明過程如圖3所示。

圖3：三色問題證明過程

證明者P希望向驗證者V證明其知道某個連通圖的着色方案，但並不希望讓驗證者V獲知這一方案的內容，其證明過程如下：

 ①證明者P根據其掌握的着色方案隨機選擇三種顏色對連通圖的所有頂點進行對應着色，並將圖中的每個頂點用紙片進行覆蓋，展示給驗證者V；
 ②驗證者V可隨機挑選連通圖中的一條邊進行驗證；
 ③證明者P將這條邊連接的兩個頂點上覆蓋的紙片揭開，展示給驗證者V，如果這兩個頂點顏色不同，則本次驗證通過。

以上證明過程同樣需要重複進行足夠多次才能使驗證者V相信證明者P掌握着色方案，且證明者P每次需要重新隨機選擇三種顏色對原有着色進行替換，否則驗證者V可能根據驗證結果還原出着色方案的部分內容。經過足夠大的n次重複之後，證明者P在不掌握着色方案的情況下成功欺騙驗證者V的概率是可忽略的，即驗證者有足夠的理由相信證明者P真正掌握了對應圖的着色方案。

與本文最開始的零知識證明洞穴模型相比，以上兩個零知識證明概念演示示例雖然更具有現實性，但仍然不是實用的零知識證明協議，也都需要證明者與驗證者反覆進行多次證明過程才能以較大的概率使得驗證者信服。而在真實的零知識證明協議中，通過引入數學與密碼學手段對方案進行約束，使得證明者每次都無法僞造證明，也就無需進行反覆的證明和驗證。

二、零知識證明技術原理

本章將對零知識證明的技術原理進行進一步分析，包括零知識證明在密碼學上需要滿足的基本屬性，以及以經典的Schnorr協議爲例說明交互式零知識證明協議到非交互零知識證明協議的轉化。

1、基本屬性

零知識證明涉及的密碼學與數學理論較多，包括計算/統計不可區分性（Computationally/Statistically Indistinguishiable）、模擬器（Simulator）、隨機預言機（Random Oracle）模型等計算複雜性理論內容。爲了便於理解，我們將零知識證明協議的三個基本屬性用較爲通俗的語言描述如下：

 ①完備性（Completeness）：只要證明者P擁有相應正確知識，就能夠通過驗證者V的驗證，即P有足夠大的概率使V確信。
 ②可靠性（Soundness）：如果證明者P沒有相應正確知識，則無法通過驗證者V的驗證，即P成功欺騙V的概率可忽略。
 ③零知識性（Zero-Knowledge）：證明者P在交互的過程中僅向驗證者V揭露其是否擁有相應正確知識，而不會泄露任何關於知識的額外信息。

2、交互式零知識證明

零知識證明起源於交互式證明協議，本小節以Schnorr協議[5]爲例分析交互式零知識證明的原理和特點。Schnorr協議是一種身份認證協議，也是如今許多數字簽名方案（例如DSA算法和ECDSA算法）的基礎，其簡化的協議流程如圖4所示。

圖4：簡化Schnorr協議流程

在Schnorr協議中，證明者A通過和驗證者B進行三次交互的方式證明了其擁有公鑰pk對應的私鑰sk，而驗證者B無法在整個過程中獲取私鑰sk的信息。

3、非交互式零知識證明

交互式零知識證明協議依賴於驗證者的隨機嘗試，需要證明者和驗證者進行多次交互才能完成。非交互式零知識證明（Non-Interactive Zero-Knowledge, NIZK）[6]將交互次數減少到一次，可實現離線證明和公開驗證。例如，在區塊鏈等零知識證明應用場景中，通常需要將證明進行直接發佈，而非依賴於交互實現，且需要支持多方的公開離線驗證。因此，在實際應用中需要考慮如何實現交互式零知識證明協議的非交互化。

對於Schnorr這一具體協議而言，可通過基於隨機預言機模型的Fiat-Shamir變換[7]將其轉化爲非交互式零知識證明，即Schnorr簽名。Fiat-Shamir變換將交互式協議中驗證者的每次隨機數挑戰行爲用證明者執行隨機預言機代替，隨機預言機的輸入應包含之前的所有上下文信息。隨機預言機可以看作是一個理想化的哈希函數，能夠將輸入轉化爲具有真隨機性（滿足一致性分佈）的結果。在實際應用中，由於不存在理想化的隨機預言機，可以使用SHA-256等常用的密碼學哈希算法進行實現。

即在基於Fiat-Shamir變換的非交互式Schnorr協議證明過程中，隨機挑戰數c不再由B生成併發送給A，而是由A自己通過c=H(x||M)計算挑戰數c，其中H( ∙ )是哈希函數（隨機預言機），M是任意消息串。最後A將(c, y)作爲證明值進行發佈，同時發佈消息M。任何獲知證明值(c, y)、消息M和公鑰pk的驗證者均可在與交互式協議相同的驗證方式基礎上進一步驗證c=H(x||M)是否成立。

證明者A在沒有交互的情況下得到了隨機挑戰數c，因此省去了交互式協議中驗證者B隨機選擇c併發送給證明者A的交互過程。這一非交互式的Schnorr協議也被稱爲Schnorr簽名機制，即證明者A使用自己的私鑰sk=a對消息M進行了簽名，其他人可通過A的公鑰pk驗證這一簽名。

除了通過隨機預言機模型將交互式協議轉化爲非交互式協議外，在後來的zk-SNARK等具有通用功能的零知識證明構造中，還可採用公共參考串（Common Reference String, CRS）的形式實現協議的非交互性，即在進行非交互式證明前由可信第三方生成一個可信的隨機串，用於替代交互式證明過程中的隨機挑戰數。在Zcash等採用零知識證明技術的數字貨幣中，爲了保證過程和結果的可信性，通常會基於一種稱爲可信設置（Trusted Setup）的儀式用於產生公共參考串。

三、零知識證明典型算法分析

爲了能夠使零知識證明在更多業務場景中應用，可實現通用功能的非交互式零知識證明算法具有更強的應用普適性。因此，本章選取zk-SNARK等在區塊鏈等場景中應用較多的通用非交互式零知識證明算法進行分析。

1、zk-SNARK

zk-SNARK（Zero-Knowledge Succinct Non-interactive Arguments of Knowledge，零知識簡明非交互式知識論證）是一類應用廣泛的通用零知識證明方案，通過將任意的計算過程轉化爲若干門電路的形式，並利用多項式的一系列數學性質將門電路轉化爲多項式，進而生成非交互式的證明，可實現各類複雜的業務場景的應用。目前，zk-SNARK已在數字貨幣、區塊鏈金融等區塊鏈領域實際落地，是目前最爲成熟的通用零知識證明方案之一。

（1）基本框架

從整體上而言，zk-SNARK零知識證明協議可大致分解爲以下步驟：

①將計算轉化爲電路

首先，爲了將待證明的計算式進行統一處理，需要將其轉化爲若干個門電路的組合形式。例如，證明者A希望向驗證者B證明其知道使得計算式(c1×c2)×(c1+c3)=7成立的c1、c2、c3值，而不泄露c1、c2、c3的具體值。根據zk-SNARK協議，首先需要將計算式(c1×c2)×(c1+c3)=7轉化成如圖5所示的電路。

圖5：電路示例

在進行程序表達時，還需要引入一些中間變量，即：

 c_1 * c_2 = sym_1 
 (c_1 + c_3) * 1 = sym_2 
 sym_1 * sym_2 = out 

其中，sym1和sym2爲中間變量，out爲公開的輸出值，即7。

②將電路轉化爲R1CS

第二步是將表示計算式的電路轉化爲向量點積（內積）的形式，即一階約束系統（Rank-1 Constraint System, R1CS）。對於每個門電路，需要定義一組向量(l, r, o)，通過向量內積運算使得s∙l×s∙r-s∙o=0，其中s代表全部輸入組成的向量，即s=[one, c1, c2, c3, sym1, sym2, out]（元素排列沒有固定順序），one表示值爲1的虛擬變量，用於將加法門電路c1+c3=sym2統一表達爲(c1+c3)×1-sym2=0的形式。向量s在zk-SNARK中又被成爲證據（Witness），作爲證明者生成證明的輸入參數。

對於乘法門電路c1×c2=sym1，對應的三個向量(l, r, o)分別爲：

 l=[0,1,0,0,0,0,0]
 r=[0,0,1,0,0,0,0]
 o=[0,0,0,0,1,0,0]

將s、l、r、o代入s∙l×s∙r-s∙o=0即得c1×c2-sym1=0，與門電路c1×c2=sym1等價。同理可得加法門電路c1+c3=sym2對應的向量爲：

 l=[1,0,0,0,0,0,0]
 r=[0,1,0,1,0,0,0]
 o=[0,0,0,0,0,1,0]

即1×(c1+c3)-sym1=0。最後一個乘法門sym1×sym2=out對應的向量爲：

 l=[0,0,0,0,1,0,0]
 r=[0,0,0,0,0,1,0]
 o=[0,0,0,0,0,0,1]

即sym1×sym2-out=0。通過以上過程，就將待證明計算式對應的電路編碼成了R1CS向量的形式。

③QAP

第三步是將R1CS向量表達式轉化爲多項式的形式，即QAP（Quadratic Arithmetic Programs）。通過這一重要步驟，即可實現待證明計算式驗證和多項式驗證之間的等價轉換。

具體而言，首先在有限域上選擇三個不同的值，假設爲1、2、3（在實際應用中需要隨機選擇），然後通過拉格朗日插值公式，構造三組多項式l(x)、r(x)、o(x)，使得在x的取值分別爲之前選擇的1、2、3時，多項式向量組(l(x), r(x), o(x))的三種取值分別對應第二步中三個門電路的向量組(l, r, o)的三種不同取值。取多項式P(x)=s∙l(x)×s∙r(x)-s∙o(x)，當x取值爲1、2、3時，P(x)=0，即1、2、3爲多項式P(x)的三個根，因此多項式P(x)能夠被T(x)=(x-1)(x-2)(x-3)整除，即存在多項式H(x)使得P(x)=T(x)×H(x)。

上述QAP過程將證明原計算式轉化成了證明存在多項式H(x)使得P(x)=T(x)×H(x)。通過拉格朗日插值公式引入了大量與原計算式無關的值將向量取值轉化爲多項式約束，因此多項式與原計算式在本質上並不完全等價，但根據多項式的Schwatz-Zippel定理，驗證了轉化後的多項式即相當於驗證了原計算式。

④引入約束

以上步驟完成了計算式證明到多項式證明的轉化。爲了構造完整的零知識證明方案，需要再引入一系列約束方法構造完備的零知識證明協議。具體包括：

引入指數知識假設（Knowledge-of-Exponent Assumption, KEA）或橢圓曲線密碼體系下的係數知識假設（Knowledge-of-Coefficient Assumption, KCA）約束證明者在生成證明過程中的參數使用，防止證明者通過選擇不符合限制條件的多項式進行欺騙。

防止暴力破解：爲了保證證明的零知識性，防止驗證者在有限範圍的多項式係數組合中對證明結果進行窮舉破解，進而反推出證明者的原始多項式，需要生成一個祕密的隨機數來對證明結果進一步的加密。

使用雙線性配對實現驗證過程中需要使用到的乘法同態。

爲了實現非交互式零知識證明，需要事先由第三方生成一些祕密隨機數，並進一步生成證明密鑰（Proving Key）pk和驗證密鑰（Verification Key）vk，pk和vk將作爲公共參考串CRS分別賦予證明者和驗證者，而原始的隨機數則作爲“有害廢料”（Toxic Waste）進行銷燬。

（2）方案選擇

zk-SNARK的概念最早於2011年提出[8]，其方案基於2010年提出的Gro10論文[9]。目前，zk-SNARK已有多類不同的優化方案，主流論文包括Pinocchio協議[10]、BCTV14a[11]、Groth16[12]等等。Pinocchio協議是首個完整的zk-SNARK實用方案，後續論文方案大多基於經典的Pinocchio協議進行優化，因此具有一定的代表性。在Pinocchio協議中，初始化過程、證明過程、驗證過程分別由可信第三方、證明者、驗證者執行。在業務模式（待證明計算式形式）確定後，可通過可信第三方或多方公開生成的可信方式產生公共參考串CRS，供後續的證明和驗證使用。

由於存在着許多基於Pinocchio協議的不同優化方案，且相關學術論文仍在不斷地更新之中，因此zk-SNARK的方案選擇是一個值得考慮的問題。目前，現有的算法工具大多支持Groth16或BCTV14a方案。與BCTV14a方案相比，Groth16方案支持可證明安全，且在Zcash等數字貨幣應用中多以Groth16作爲默認方案。因此，在進行實際應用時，可優先選擇應用最爲普遍的Groth16方案作爲工程實現的基礎。

（3）功能實現

除上述的(c1×c2)×(c1+c3)=7這類簡單的計算式證明外，還可通過不同的電路構造方法，將更爲複雜的證明需求轉化爲門電路的組合形式。libsnark算法庫中的gadget工具庫包含布爾值、位組合、析取關係（或）、合取關係（與）、大小關係、向量內積、線性組合等基本約束的實現，通過包括但不限於以上基本功能的組合，可實現更爲複雜計算式的證明。除基本功能外，zk-SNARK還可實現Merkle樹、SHA256哈希、模指數運算、雙線性配對等複雜計算的驗證。在實際場景中，只要存在對隱私數據計算的可驗證性需求，理論上都可考慮嘗試採用零知識證明技術解決的可行性，但在應用的必要性方面還需考慮實際可操作性和引入的效率問題。

（4）開發工具

目前，爲了解決零知識證明技術的廣泛應用需求，產生了多個用於實現zk-SNARK零知識證明協議工程化的開源算法庫，包括libsnark、bellman、ZoKrates等等。

①libsnark

libsnark是一個基於C++語言的zk-SNARK工程開發算法庫，由SCIPR Lab開發和維護，開發者中包含參與多篇zk-SNARK學術論文的共同作者。libsnark實現了近年來多個主流的zk-SNARK論文方案，其中最爲常用的包括BCTV14a和Groth16方案。

libsnark實現了zk-SNARK算法的黑盒化，提供高度抽象的編程接口，使開發者無需掌握算法細節即可直接進行工程開發。此外，libsnark還提供了實際應用中的常見基礎功能庫，可輔助開發者進行復雜證明的組合實現。以在匿名數字貨幣Zcash中的應用爲開端，libsnark奠定了零知識證明技術從理論研究到大規模工程應用的基礎。

②bellman

在Zcash項目中，最初採用libsnark算法庫實現zk-SNARK零知識證明。在2018年升級到Sapling版本時，由於之前採用的libsnark版本較老，其中關於橢圓曲線和zk-SNARK方案的選擇都已不是當時的最優選項，Zcash改爲使用自研的bellman算法庫。bellman是Zcash團隊基於Rust語言實現的zk-SNARK算法庫，支持Groth16論文方案，目前主要在Zcash項目中應用。

③ZoKrates

ZoKrates是一個部分基於libsnark、部分採用Rust語言重寫的zk-SNARK實現工具，默認支持Groth16方案，開發者需要使用一種自建的腳本語言進行代碼編寫，目前在實際工程中僅用於在以太坊智能合約上部署支持零知識證明的應用。

2、其他算法

（1）zk-STARK

zk-STARK（Zero-Knowledge Scalable Transparent Arguments of Knowledge，零知識可擴展透明知識論證）[13]是2018年提出的一種通用非交互式零知識證明算法，通過多項式插值等方法將證明計算式轉化爲證明多項式小於某個度的問題，實現對問題的零知識證明。

zk-SNARK算法主要可分爲算術化（Arithmetization）和低度測試（Low Degree Testing, LDT）兩部分。算術化過程將待證明問題轉化爲多項式的形式，具體內容包括生成與R1CS類似的執行軌跡（Execute Trace）並構造多項式約束，然後對執行軌跡進行多項式插值，並與多項式約束進行組合變換，得到確定性的驗證多項式；而LDT過程則通過二分法驗證證明組合多項式和軌跡多項式小於某個固定的度，確保證明者給出的滿足多項式的值是基於有效的多項式計算的，用於防止證明者僞造證明，具體基於FRI（Fast Reed-Solomen Interactive Oracle Proofs of Proximity）協議實現。

zk-STARK與zk-SNARK相比主要有以下異同點：

①相同點

zk-STARK和zk-SNARK均實現了對隱私輸入的隱藏；
zk-STARK和zk-SNARK均爲基於知識的論證，即在不知道隱私輸入的情況下無法生成有效證明；
zk-STARK和zk-SNARK均可實現非交互式協議；
zk-STARK和zk-SNARK均通過將計算式轉化爲多項式實現零知識證明。

②不同點

zk-STARK具有透明性，即不需要通過由可信第三方完成的可信設置過程生成CRS；
zk-STARK具有可擴展性，即證明過程的耗時與輸入大小呈線性關係，但驗證過程的耗時僅與輸入大小呈對數關係；
zk-STARK生成的證明大小比zk-SNARK大很多。

總的來說，與zk-SNARK相比，zk-STARK不需要通過可信第三方生成CRS，且驗證耗時僅與輸入大小呈對數關係，但其生成的證明更大。面對區塊鏈等應用場景寶貴的存儲資源，zk-SNARK在證明的簡潔性方面更勝一籌。

（2）BulletProof

BulletProof[14]零知識證明算法同樣於2018年提出，主要用於實現範圍證明（Range Proof），目前已在Monero匿名數字貨幣中應用。

在BulletProof範圍證明中，證明者可向驗證者證明其擁有的祕密值v在一個確定的範圍，而不會泄露關於v的任何信息。此外，通過對範圍證明進行組合變換，還可進一步實現大小關係的證明。BulletProof算法具有生成證明小的優點，且同樣不需要通過可信設置儀式生成CRS，但其主要功能優勢在於範圍證明，因此在普遍適用性方面還有待進一步驗證。

除以上介紹的算法外，在目前的實際應用中還存在着PLONK、AZTEC等其他可用的新型零知識證明算法。作爲通用非交互式零知識證明的應用先驅，zk-SNARK算法的功能更爲全面，學術與技術資源更爲豐富，實際的工程應用場景也更加廣泛。

四、零知識證明應用場景

作爲一類經典的密碼學原語，零知識證明至今已有三十多年的歷史。但是，直至近年來基於區塊鏈的匿名數字貨幣的誕生，零知識證明技術纔開始有了較大規模的應用。目前，零知識證明在工程應用上仍處於起步階段，且在可信設置、運算效率等方面存在着一些瓶頸，依然還是一項尚未真正成熟的密碼學技術。

本章對目前零知識證明技術在區塊鏈、數字貨幣、安全多方計算等領域的應用場景進行舉例分析。

1、在區塊鏈數字貨幣中的應用

（1）Zcash

Zcash是一種基於區塊鏈的匿名數字貨幣，起源於Zerocoin協議。2014年，經過效率和匿名性等方面的改進，Zerocoin協議發展爲Zerocash協議[15]。2016年，基於Zerocash協議的Zcash數字貨幣應用項目正式向公衆開放。

Zcash採用zk-SNARK零知識證明協議實現了隱蔽交易的功能。在比特幣中，需要通過公開在區塊鏈上的交易發送方地址、交易接收方地址以及輸入和輸出金額來驗證交易。而在Zcash中，通過zk-SNARK來證明交易滿足有效條件，而不會公開任何有關地址或金額的關鍵信息。隱蔽交易的發送方通過構建一個證明，從而以足夠高的概率來證明交易滿足以下條件：

 ①交易的輸入總金額和輸出總金額相等；
 ②交易發送方擁有支配交易金額的私鑰；
 ③支配交易金額的私鑰與交易的簽名綁定，交易無法被不知道私鑰的人篡改。

在Zcash中，隱蔽交易的UTXO（Unspent Transaction Output）被稱爲Commitment（承諾），而支出一個Commitment對應的金額需要公佈一個相應的Nullifier。Zcash節點會保存包含所有已創建的Commitment組成的Merkle樹以及所有已公佈的Nullifier列表。Commitment和Nullifier通過哈希值存儲，防止泄露Commitment的信息以及Commitment和Nullfier的對應關係。

對於輸入金額的來源，每次隱蔽交易都會產生一份未使用的金額，以一個Commitment的形式進行公佈，其值爲接收方地址、交易金額、祕密的交易唯一標識和一個隨機串（Random Nounce）的哈希值。

對於輸出金額的去向，當隱蔽交易發起時，交易發送方使用支配交易金額的私鑰發佈一個Nullifier，其值是現有未使用Commitment中交易唯一標識的哈希值，並生成證明其有權使用相應金額的零知識證明。交易發送方需要將私鑰對應的公鑰和交易唯一標識通過祕密信道發送給交易接收方以完成交易。爲了防止雙花，Zcash區塊鏈節點會驗證該Nullifier不在已經公佈的列表中。

進而，隱蔽交易的零知識證明還可以驗證以下論斷的真實性：

 ①對於每一份輸入金額，都存在一個已公佈的Commitment；
 ②Nullifier和Commitment是被正確計算的；
 ③不同輸出交易的Nullifier不會發生哈希碰撞。

對於每個隱蔽交易，交易發送方通過證明密鑰生成輸入金額有效性證明，區塊鏈節點通過驗證密鑰來驗證交易發送方的證明。

Zcash通過Trusted Setup公共參數儀式生成零知識證明的證明密鑰和驗證密鑰，並與Zcash網絡中的所有參與者共享。2016年10月22日至23日，Zcash舉行了可信設置儀式生成zk-SNARK的公共參考串CRS，通過由具有競爭關係的六個參與者參與的多方計算協議，保證CRS的安全生成，除非參與參數生成的所有人共謀，否則被銷燬的隨機參數無法得到恢復。

（2）Monero

Monero（門羅幣）也是一種支持交易隱私保護的數字貨幣，創始於2014年，其通過密碼學技術手段實現了以下兩個屬性：

 ①不可鏈接性（Unlinkability）：無法判斷兩個交易的接收方是否是同一個人，即保證了交易接收方的匿名性；
 ②不可追蹤性（Untraceability）：無法知道交易的發送方是誰，即保證了交易發送方的匿名性。

Monero主要依賴於以下三種密碼學機制：

 ①一次性密鑰（One-Time Key）：每次交易生成不同密鑰以隱藏真實的交易接收方；
 ②環簽名（Ring Signature）：將交易發送方的輸入與其他人的輸入進行混淆簽名，外界無法將不同交易進行關聯；
 ③環簽名保密交易（Ring Confidential Transaction, RingCT）：隱藏交易金額。

RingCT[16]採用零知識證明技術——Pedersen承諾，可在隱藏交易金額的同時實現區塊鏈的驗證，即對交易的輸入總金額與輸出總金額（包含交易費用）之差是否爲0進行零知識證明承諾。

然而，由於基於羣代數的密碼學存在模運算，無法將小負數與對應模數的大正數進行區分，可能導致僞造幣的產生。因此，爲了在保護交易金額機密性的同時保證交易金額不爲負數，且金額不能過大至與小負數在對應模數上同餘，需要對交易的輸出金額進行範圍證明。最初的範圍證明協議基於Borromean環簽名技術，其證明大小與範圍區間的上限成線性關係，成爲了交易的主要負擔，影響了區塊鏈的整體效率。

2018年，Monero進行了一次硬分叉升級，引入了BulletProof零知識證明算法以提升交易效率。BulletProof用於取代之前基於環簽名的範圍證明協議，其產生的證明大小僅與範圍區間上限成對數關係，同時可將多個證明進行合併以實現進一步優化，最終將區塊鏈的大小以及交易費用減少70%~80%。

2、在區塊鏈其他場景中的應用——以太坊擴容

以太坊（Ethereum）是一個知名的公有區塊鏈平臺，通過在去中心化網絡節點上的以太坊虛擬機（Ethereum Virtual Machine, EVM）中運行以圖靈完備語言編寫的智能合約（Smart Contract），進而承載去中心化應用（Decentrialized Application, DApp）的部署。隨着越來越多DApp的部署，以太坊遇到了幾乎所有公有鏈平臺所共有的性能瓶頸問題，由此產生了各類針對以太坊的擴容方案。

以太坊擴容方案一般分爲第一層（Layer-1）擴容方案和第二層（Layer-2）擴容方案。Layer-1擴容方案是指直接增加鏈上的交易處理能力，即鏈上擴容，常見的技術方案有分片（Sharding）和有向無環圖（Directed Acyclic Graph, DAG）等；Layer-2擴容方案是指將鏈上的相當一部分工作量轉移到鏈下完成，常見的技術方案包括狀態通道、Plasma、Truebit等。

ZK-Rollup是一類基於zk-SNARK零知識證明的以太坊Layer-2擴容方案，其實現案例爲ZK-Sync去信任化擴容及隱私解決方案。ZK-Rollup將鏈上的賬戶狀態（包含公鑰、Nonce和餘額）壓縮存儲在一棵Merkle樹中，並將賬戶狀態變更的處理轉移到鏈下，同時通過zk-SNARK零知識證明生成每個交易的有效性證明，保證鏈下賬戶狀態變更的正確性，具體包括交易的Nonce、金額、費用以及簽名等內容的正確性，並將證明結果提交到鏈上的智能合約中。由於在鏈上直接處理賬戶狀態變更的成本較高，而僅通過鏈上的智能合約驗證零知識證明結果的成本相對低很多，因此零知識證明的應用可大大提高以太坊的交易處理效率，真正實現擴容的目的。零知識證明技術的引入預計可將以太坊的每秒交易吞吐量從目前的約15TPS提升至主流支付轉接清算網絡級別的數千TPS。

值得一提的是，以太坊的創始人Vitalik Buterin本人就是一個零知識證明技術的支持者，曾多次在不同場合公開支持zk-SNARK等零知識證明技術在以太坊等區塊鏈平臺中進行應用。

3、在安全多方計算中的應用

隱私計算是密碼學技術的另一個重要應用領域。基於密碼學的安全多方計算（Multi-Party Computation, MPC）方案通常採用混淆電路（Garbled Circuit）、不經意傳輸（Oblivious Transfer）、同態加密（Homomorphic Encryption）、同態承諾（Homomorphic Commitment）、祕密共享（Secret Sharing）以及零知識證明等技術手段，實現多個參與方之間數據共享計算過程中的隱私保護。從密碼學的本質上來說，安全多方計算的定義是在無可信第三方的情況下，若干個互相不信任的參與方使用各自的私有數據安全地計算一個約定函數而不泄露各自原始數據的問題。

在典型的安全多方計算方案中，參與方之間通常會事先約定一個計算框架，並要求雙方按照既定的框架執行計算。但是，參與方可能懷疑對方是否使用其私有數據真正進行了計算，因此可引入零知識證明技術用於解決這一計算結果的可信驗證問題。具體而言，參與方中的一方在通過混淆電路或同態加密等方法完成安全計算後，除了將計算結果提供給其他參與方外，還可將計算過程轉化爲零知識證明電路，並採用零知識證明算法生成計算過程的證明結果供其他參與方驗證。根據零知識證明協議滿足的完備性、可靠性和零知識性三個基本屬性，通過這一過程即可在不泄露具體計算數據的情況下，使其他參與方相信計算是按照正確步驟進行的。

五、總結

得益於近年來區塊鏈、數字貨幣、隱私計算等新興技術應用的發展，零知識證明這一具有30多年曆史的經典密碼學技術在最近5到10年又產生了極爲豐富的理論與應用成果。在區塊鏈應用中，對於不同參與方的數據交互驗證可採用零知識證明技術實現，避免敏感信息的相互泄露；在安全多方計算應用中，參與雙方可在通過同態加密等方法保護的隱私計算完成後要求互相提供計算過程的零知識證明結果進行驗證，防止虛假計算，同時又不會泄露計算過程中的敏感信息。

總的來說，零知識證明這一“新瓶裝舊酒”的密碼技術，在目前十分熱門的區塊鏈、數字貨幣、安全多方計算等場景中都有着一定的應用潛力。

參考文獻

[1] Quisquater J J, Quisquater M, Quisquater M, et al. How to explain zero-knowledge protocols to your children[C]//Conference on the Theory and Application of Cryptology. Springer, New York, NY, 1989: 628-631.
 [2] Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof systems[J]. SIAM Journal on computing, 1989, 18(1): 186-208.
 [3] Gradwohl R, Naor M, Pinkas B, et al. Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles[J]. Theory of Computing Systems, 2009,44(2): 245-268.
 [4] Goldreich O, Micali S, Wigderson A. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems[J]. Journal of the ACM (JACM), 1991, 38(3): 690-728.
 [5] Schnorr C P. Efficient signature generation by smart cards[J]. Journal of cryptology,1991, 4(3): 161-174.
 [6] BlumM, Feldman P, Micali S. Non-interactive zero-knowledge and its applications[C]//Proceedings of the twentieth annual ACM symposium on Theory of computing. 1988: 103-112.
 [7] Fiat A, Shamir A. How to prove yourself: Practical solutions to identification andsignature problems[C]//Conference on the theory and application of cryptographic techniques. Springer, Berlin, Heidelberg, 1986: 186-194.
 [8] Bitansky N, Canetti R, Chiesa A, et al. From extractable collision resistance tosuccinct non-interactive arguments of knowledge, and back again[C]//Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. 2012: 326-349.
 [9] Groth J. Short pairing-based non-interactive zero-knowledge arguments[C]//International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2010: 321-340.
 [10] Parno B, Howell J, Gentry C, et al. Pinocchio: Nearly practical verifiable computation[C]//2013 IEEE Symposium on Security and Privacy. IEEE, 2013: 238-252.
 [11] Ben-Sasson E, Chiesa A, Tromer E, et al. Succinct non-interactive zero knowledge for a von Neumann architecture[C]//23rd USENIX Security Symposium (USENIX Security 14). 2014: 781-796.
 [12] Groth J. On the size of pairing-basednon-interactive arguments[C]//Annual international conference on the theory andapplications of cryptographic techniques. Springer, Berlin, Heidelberg, 2016: 305-326.
 [13] Ben-Sasson E, Bentov I, Horesh Y, et al. Scalable, transparent, and post-quantum secure computational integrity[J]. IACR Cryptology ePrint Archive, 2018, 2018: 46.
 [14] Bünz B, Bootle J, Boneh D, et al. Bulletproofs: Short proofs for confidential transactions and more[C]//2018 IEEE Symposium on Security and Privacy (SP). IEEE, 2018: 315-334.
 [15] Sasson E B, Chiesa A, Garman C, et al. Zerocash: Decentralized anonymous payments from bitcoin[C]//2014 IEEE Symposiumon Security and Privacy. IEEE, 2014: 459-474.
 [16] Noether S, Mackenzie A. Ring confidential transactions[J]. Ledger, 2016, 1: 1-18.

*本文作者：狴犴安全團隊，轉載請註明來自FreeBuf.COM

相關文章