簡潔非交互零知識證明綜述

朱旭東， 張心軒， 鄧 燚*

(1.中國科學院 信息工程研究所/信息安全國家重點實驗室， 北京 100093； 2.中國科學院大學 網絡空間安全學院， 北京 100049)

1 研究背景

Goldwasser等[1]給出了零知識證明(Zero-Knowledge Proofs, ZKP)的概念，零知識證明的出現在密碼學上有著重要的意義，它給人們的現實生活也帶來了巨大的沖擊。零知識證明是一個強大的密碼學工具，能讓證明者向某個驗證者證明某個斷言是正確的而不透露其它任何信息，它需要滿足3個性質：①完整性：如果證明者做出正確的證明，那么驗證者一定會通過驗證；②可靠性：如果證明者偽造一個虛假的證明，那么驗證者除了可忽略的概率外會拒絕；③零知識性：驗證者只能知道斷言是正確的而不知道任何其他知識。

隨著對零知識協議研究的深入,以及對其應用要求的增加，大家并不滿足于需要雙方進行交互的零知識證明系統。Blum等[2]在公共參考串模型下(Common Reference String model，CRS model)將零知識的概念延伸至非交互零知識證明的概念(Non-interactive Zero-knowledge proofs, NIZK proofs)，在這個系統里，證明者可以只發一條消息給驗證者，然后驗證者驗證即可。NIZK在包括數字簽名、選擇密文攻擊(Chosen-ciphertext Attack， CCA)和安全的公鑰加密等非交互密碼學方案中都十分有用。

在大數據時代的今天，互聯網上的數據量日益增大，零知識證明作為一個被廣泛應用的工具，大家對其通信復雜度和效率的要求也越發嚴格。于是簡潔非交互零知識的知識論證(Zero-knowledge Succinct Non-interactive Arguments of Knowledge, zk-SNARKs)概念也被提出并被廣泛研究，事實上zk-SNARKs是如今區塊鏈等密碼學應用領域上重要的一環。

早期的zk-SNARKs都是在CRS模型下討論的，雖然目前已經可以在這種模型下構造十分高效的zk-SNARKs方案，但該模型需要依賴受信任的初始設置(Setup)。從現實的角度來看，實現可信的初始設置是很困難的，因為實現過程中往往會產生有害信息(toxic waste)，萬一被泄漏，敵手則可以利用這些有害信息生成能夠通過驗證的偽造證明。此外，這些zk-SNARK的初始設置是特定電路的一次性受信任的初始設置，即由該初始設置產生的CRS只能針對特定電路，而不能針對任意的電路。為了避開這些問題出現了以下一系列的解決方法和新的研究路線。

1.1 通用可更新(Universal updatable)的zk-SNARKs

在這個模型下CRS可以被任意更新參與方非交互的更新，這個更新是可驗證的，并且只要在所有參與方中至少有一個是誠實做的，那么模擬的陷門就不會被泄露，從而達到了取代可信第三方的目的。另外，這種可更新的CRS一般都是通用的(Universal)，也就是說它們的生成不依賴于具體電路，而是直接被用于針對任意電路的零知識證明之中。

1.2 透明的(Transparent)zk-SNARKs

這個模型主要研究CRS生成時無需可信第三方的SNARK協議。絕大多數透明的zk-SNARKs協議，其CRS是無結構的均勻隨機串，有時候，也稱這種使用無結構的均勻隨機串的CRS模型為均勻隨機串模型(Uniform Random String model, URS)。透明的zk-SNARKs的安全性通常是在隨機預言機模型(Random Oracle Model)下證明的。

1.3 純公鑰模型(Bare Public Key model，BPK)下的zk-SNARKs

在該模型下的zk-SNARKs協議分為2個階段，第一個階段不同于CRS模型下由可信第三方來生成CRS，該模型下是由驗證者生成CRS；第二個階段再由證明者與驗證者在這個CRS下執行零知識證明協議(當然為了保證零知識性質，目前的方案都需要證明者先對這個CRS進行一些驗證)，因此，該模型不需要可信第三方，要比CRS模型更弱。

1.4 模擬多方安全計算(MPC-in-the-head)的zk-SNARKs

在該模型下，證明者在一些(至少3個)虛擬的服務器之間模擬一個MPC協議，然后將他們所看見的副本和每個服務器的中間狀態承諾起來。此后，驗證者可以讓證明者打開這些承諾的一個子集來高效驗證是否一致。由MPC的私密性可以保證證明者打開給驗證者看的內容不會泄露額外信息，由MPC的正確性也可以保證證明者無法欺騙驗證者。

2 公共參考串模型下的zk-SNARKs

零知識證明[1]，特別是非交互零知識證明[2]在密碼學理論和實際密碼學應用中都扮演著重要的角色。而在諸如文獻[3-7]等大量的研究下，基于pairing的簡潔非交互零知識的論證(Zero-knowledge Succinct Non-interactive Arguments of Knowledge, zk-SNARKs)出現在人們的視野中，并被不斷發展。相比于非交互的零知識證明，zk-SNARKs最大的特點就是簡潔性，事實上它甚至可以讓證明者在證明長度僅為常數個群元素的情況下證明任意大小電路的可滿足性。此外，為了滿足不斷提高的應用需求，如今許多的zk-SNARKs方案在計算效率方面也被設計得十分高效。

關于為什么CRS模型會被提出的背景，Goldreich等[8]提出在標準模型下，對于足夠困難的語言想要構造一輪的協議來抵抗帶輔助輸入的證明者的攻擊是不可能的，因此，需要考慮一個更強的模型——CRS模型。

另外，知識的論證(Argument of Knowledge/ Knowledge Soundness)是對合理性(Soundness)的強化定義，在該定義下，一個高效證明者爭對某個斷言生成的證明通過驗證，不僅能說明該斷言對應的證據的存在性，并且這個證據還能被高效地抽取出來。許多證明系統都滿足這個性質，這個性質對于簡潔論證系統的應用也有重要的影響。

概率可檢驗證明(Probabilistically Checkable Proofs, PCP)定理[9-12]為NP語言提供了一個新的、對證明系統產生深遠影響的特征，它說明了NP斷言擁有能在正常證明尺寸和對數多項式時間內被驗證的概率可檢驗證明。Kilian[3]將這種新的NP特征應用于密碼場景，證明可以對NP語言用PCP去構造交互論證。而通信量大小是零知識證明的一個重要表現參數，Klilian給出了第一個亞線性通信規模和驗證時間的零知識證明，該方案需要發送的比特數少于需要被證明的斷言，這樣的論證系統被稱為簡潔的(Succinct)論證系統。

需要注意的是Klilian的協議需要4輪交互，而對于應用而言非交互顯然更加有意義。因此，朝著這個方向嘗試，Micali[4]通過讓證明者在這些論證中使用密碼學函數計算驗證者的挑戰，而在RO模型下構造出了一個公開可驗證的簡潔非交互論證方案。正如Kilian[13]所述，這種Fiat-Shamir啟發式[14]可以把公開擲幣(Public Coin)的零知識論證變成亞線性規模的NIZK方案。此外，還有一些早期工作，如文獻[15-18]研究了怎么利用可抽取的抗碰撞哈希(Extractable Collision-resistant Hashing)[19-21]來去除Kilian的基于PCP的協議的交互，或者利用有一個可抽取同態性質的全同態加密(Fully-homomorphic Encryption with An Extractable Homomorphism Property)[22]去構造基于MIP(Multi-prover Interactive Proofs)的SNARKs。

經典的構造簡潔論證的方法是首先給出一個信息論構造，然后在對證明者有某種約束的模型下利用一些概率檢查(Probabilistic Checking)去驗證計算(例如前面提到過的PCP模型[3-4,18-21,23]，或者其它的概率檢查的模型[22,24-29])，最后再利用密碼學工具將信息論構造編譯成論證系統(此時對于證明者，除了要求其算法為高效的，并無其它約束)。然而如今的構造都偏離了這個方法而基于新的方法，新的方法有很多吸引人的好處，例如，公開可驗證與證明只包含常數個群元素等。

Groth等[30-33]提出了基于pairing的NIZK證明，這也導致了標準假設下的第一個線性通信規模的證明誕生。Groth[5]結合這些技術和他此前提出的交互零知識論證的想法[34],在指數知識假設(Knowledge of Exponent Assumptions， KEA)[35-37]和雙線性群下給出了第一個證明只包含常數個群元素的NIZK論證。Groth的常數規模的NIZK論證基于一系列多項式等式，并采用pairing的方式去高效地驗證這些等式。Lipmaa[38]在同樣的群和假設下使用了一個基于進展集合(progression sets)的新構造進一步壓縮CRS的長度。文獻[5, 38]都用到了不可證偽的假設，事實上Gentry等[39]給出了一個負面的結論——不可證偽的假設(包括知識假設和一些強的模型)是證明SNARK的知識的論證所必須的。

不同于基于之前所提到的概率檢查的方法，Gennaro等[6]首先通過電路的編碼和拉格朗日插值將電路可滿足性問題規約到了更容易處理的代數可滿足問題上，從而跳過了經典方法中的概率檢查的步驟而直接構造具體的密碼學工具來驗證代數可滿足問題，這種方式是對信息論材料和密碼學材料的進一步區分。他們給出了2種新的代數可滿足問題，一個是與證明布爾電路可滿足性相對應的QSP(Quadratic Span Programs)，另一個是與證明算術電路可滿足性相對應的QAP(Quadratic Arithmetic Programs)，并給出了一個CRS長度與斷言和證據大小呈比例的基于pairing的zk-SNARK，這樣構造出的SNARK擁有更加高效的驗證時間和更短的證明長度。Lipmma[40]結合糾錯碼提出了更加高效的QSP。Danezis等[41]將 quadratic span programs 重新定義為了square span programs，并給出了一個針對布爾電路的包含4個群元素的zk-SNARK。 Bitansky等[42]給出了基于對域元素做線性編碼的SNARKs的抽象模型——LIPs(Linear-interactive Proofs)，這個模型抓住了證明者被限制為只能使用線性操作計算消息的特征,此外,該文章給出了一個一般的轉化——從2輪LIP結合基于pairing的技術轉化為公開可驗證的SNARK或者結合同態加密技術得到指定驗證者的SNARK。在LIP的框架下，Groth[7]提出了迄今為止在驗證時間和證明長度(證明只包含3個群元素)上表現最優的zk-SNARKs，也因此已被廣泛用于電子貨幣等互聯網領域中。

這些傳統的zk-SNARKs方案雖然已經在通信量和效率上有了不錯的結果，但是其還有2個比較大的缺陷：①其CRS生成都需要依賴可信第三方，因而在中心化系統中難以實現；②其大部分只能針對特定線路，即對每個不同線路的證明都需要重新生成一次CRS，這使得其在應用上受到限制。

當然，也存在CRS模型下的針對通用電路的zk-SNARKs。例如Libra[43]也需要CRS，但是其CRS是通用的，與具體電路邏輯無關而只與電路的輸入長度有關。該方案也是第一個擁有最優證明者時間(證明時間為O(C)且與電路類型無關)和簡潔證明長度/驗證時間的零知識證明系統。特別地，如果令C是電路大小，d是電路深度，那么Libra的證明時間為O(C)，證明長度和驗證時間都是O(dlogC)。該方案的核心技術有2個，一個是線性證明者時間的GKR協議(Goldwasser, Kalai和Rothblum的交互證明協議)；另一個是高效的將GKR協議轉化為零知識協議的方法。

3 通用可更新的zk-SNARKs

為了取代CRS模型，Groth等[44]定義了可更新模型(Updatable Model)，這個模型是完全的CRS模型和完全的BPK模型的折衷模型，在這個模型下，CRS可以被任意更新參與方非交互地更新，這個更新是可驗證的，并且只要在所有參與方中至少有一個是誠實的，那么模擬的陷門(Trapdoor)就不會被泄露，從而達到了取代可信第三方的目的。另外，一般這種可更新的CRS都是通用的(universal)，也就是說它們的生成不依賴于具體電路，因此，可以被用于對任意電路的零知識證明。

算術電路的可滿足性問題可以被歸約到一系列有限域上的二次和仿射約束問題。二次約束是通用的，并且很容易在pairing場景下通過Hadamard乘積論證(Hadamard product argument)來對其進行證明。關于二次約束的證明，大部分zk-SNARKs構造的基礎核心來源于文獻[6]。而仿射約束是依賴電路的，因此，如何在通用CRS下高效地證明仿射關系是一個充滿挑戰的問題。

Groth等[44]給出的構造盡管只需要常數個群元素的證明長度和常數的驗證時間，但需要用到花銷很大的子空間論證(Subspace Argument)，它要求CRS和預處理的長度分別為電路大小的平方和立方。另外，更新CRS要求平方多個群指數運算，而驗證更新的正確性則需要線性多個pairing計算。而Sonic[45]是第一個高效的、通用的、可更新的SNARK，它的證明長度為常數個群元素而且CRS規模僅與電路大小呈線性關系。Sonic的技術目標是去對一個代表NP-hard語言的約束系統的可滿足性做零知識論證，而這個約束系統與Bulletproofs[46]中的約束系統類似，也表達為二元多項式等式。為了給多項式做承諾，該文章還用到了Kate等[47]提出的多項式承諾方案的一個變體，并證明這個承諾方案在代數群模型(Algebraic Group Model, AGM)下是安全的。對于正確賦值的證明，Sonic也給出了一個新的置換論證和一個Grand-product論證。Sonic的驗證需要檢查一個稀疏二元多項式的賦值，該文章提出了一個簡潔地檢查這個賦值的方法。總的來說，Sonic給出了2種不同的方式去證明仿射約束，一個方式是完全簡潔的但并不是十分高效，另一個方式通過引入一個不受信任的第三方，在批驗證場景下(Batch Verification Context)可以做得十分高效。由于Sonic的整個協議是公開擲幣的，而其用到的子部件是Kate的承諾方案的一個變形，該承諾方案是可更新的且其安全性可以在代數群模型下被證明，因此，在RO模型、AGM下，Sonic是通用可更新的zk-SNARK。

Marlin[48]是Sonic的改進版，其擁有與電路規模呈線性的CRS長度和常數個群元素的證明長度且都比Sonic要短，Marlin的證明時間比Sonic快10倍，而驗證者時間比Sonic快3倍。Marlin可以在標準假設下實現，也可以在代數群模型(Sonic也用到了這個模型)下實現以追求最大的效率。Marlin的技術核心是一個高效的爭對R1CS(Rank-1 Constraint Satisfiability)的代數全息證明(Algebraic Holographic Proof， AHP)，它能在線性的證明長度和常數的問詢復雜度(Query Complexity)下實現。事實上，構造一個“全息證明(holographic proofs)”[49]與在線下階段對一個線路做預處理的能力息息相關。這意味著驗證者可以不以電路的描述作為輸入而是對其的編碼做少量的問詢。該文章中對電路描述的編碼包括一些低次多項式，與此同時，證明本身也是一些低次數的多項式，這可以視為要求證明者是代數的，而這就構成了AHP。該文章擴展了Kate的多項式承諾方案[47]，設計了一個高效的AHP，并指出利用公開擲幣的AHP和多項式承諾就可以得到簡潔的交互論證系統，最后利用Fiat-Shamir轉化，可以得到通用可更新的zk-SNARKs。

Plonk[50], 也是Sonic的改進，其相比于Sonic而言，Plonk提高了證明時間(群指數運算少7.5～20倍)。與Sonic[45]類似，Plonk也依賴于Bayer和Groth的置換論證[51]。然而Plonk關注的是子群上的賦值而非單項式的系數，因此，同時簡化了這個置換論證和算術步驟。Plonk的構造思路是首先將電路的約束分為2種——門約束和置換約束，用一元多項式表達門約束，然后和之前的方案類似同樣用了Kate多項式承諾[47]的變形來打開多項式在一個點的值進行證明，而用置換論證來證明置換約束(也要用到多項式承諾)。由于整個過程是公開擲幣的，而Kate的承諾方案的變形是可更新的且與Sonic類似可以在代數群模型下證明安全性，使得在RO模型、AGM下，Plonk是通用可更新的。

Lunar[52]與前面這些方案相比則有著更好的證明長度和證明者驗證時間，而代價是其在驗證密鑰的長度和驗證時間上有更高的限制。其技術貢獻主要有如下2點：①提出了一種新的代數型IOPs(Interactive Oracle Proofs)變體——多項式全息IOPs(Polynomial Holographic IOPs, PHPs);②提出了一個新的編譯器，它利用這個PHPs結合針對被承諾多項式的CP-SNARKs (Commit-and-Prove zkSNARKs)來構造通用的zk-SNARKs。其它的貢獻包括對這些CP-SNARKs在pairing場景下實現、對R1CS和其新變體的PHPs構造的實現。另外，前面所說的編譯器稍做改變可以變成第一個從IOPs到Commit-and-Prove的通用zk-SNARKs的編譯器。

4 透明的zk-SNARKs

隨著諸如區塊鏈等去中心化的系統的發展與應用，類似文獻[7]的傳統CRS模型下的SNARK協議的需要可信第三方的特性成為了其在去中心化系統應用中的障礙。為了避免可信第三方的需求，一方面，正如前面所描述的，各種可更新CRS的zk-SNARK系統作為一種去中心化的解決方法被提出并得到廣泛應用；另一方面，正如本節中將要介紹的，各種透明的zk-SNARK方案被構造提出并發展以實現去中心化。

與通用可更新的zk-SNARKs的CRS可更新并且只要更新用戶中有一個用戶是誠實可信的CRS就是安全的不同，透明的zk-SNARKs的CRS的生成不需要任何可信第三方。盡管透明的零知識協議的概念很早就被提出了，但是可實用的、透明的zk-SNARKs直到最近幾年才出現。2018年Ben-Sasson等[53]提出了STARK方案。在STARK中，首先需要將待證明的線路或者約束條件轉化成代數中間表示(algebraic intermediate representation, AIR)。簡單來說，AIR將一個線路的執行表示成線路的中間狀態(包括輸入狀態與輸出狀態)的轉換，線路則可以表示成這些相鄰狀態的轉換/約束。之后使用代數的布局與布線(Algebraic Placement and Routing，APR)技術優化線路的約束，并將線路的可滿足性轉化成2組Reed-Solomon有效性檢測問題(Reed-Solomon Proximity Testing (RPT) Problem)。之后使用代數鏈接(Algebraic Linking)將上述2組RPT問題聚合成2個RPT問題，最后使用快速Reed-Solomon 有效性IOP協議(FRI)實現證明。大致來說，對于結構較好(擁有較多重復子線路)的線路而言，STARK可以實現O(nlog2n)的證明者時間與O(log2n)的驗證者時間與通信量，其中n是線路的大小。

2019年由Chiesa等[56]提出的Fractal也是一種針對R1CS斷言的SNARK。該方案通過對R1CS斷言構造一種新的全息證明，并給出一種從全息IOP到透明的帶預處理的SNARK的轉化方式，從而實現了對R1CS類的透明的帶預處理的SNARK構造。這個構造實現了O(nlogn)時間的預處理時間，O(nlogn)的證明者時間，O(|x|+log2n)的驗證者時間與O(log2m)的證明長度。

同年，Setty[57]提出了另一種針對R1CS斷言的SNARK——Spartan。該方案將一個R1CS實例x=(F,A,B,C,io,m,n)編碼成3次的logm變量多項式G使得該實例是可滿足的，當且僅當∑x∈{0,1}logm(x)=0。之后將上述等式轉換成線性多變量多項式的Sum-Check，從而實現NIZK的構造。在預處理的情形下，這個NIZK是一個SNARK，并根據使用的多項式承諾不同，其效率表現也不同。其可以在證明者時間O(n)或者O(nlogn)的情形下，分別實現O(log2n)或者的驗證者時間和證明長度。另外，文章中也提出了用SPARK等技術來提升方案的表現，使方案在實際運行中取得良好的表現。

在2016年，Bootle等[58]為Pedesen承諾設計了一種新的內積求值的遞推論證技術，并使用這個技術為代數線路的可滿足性設計了一種對數的通信復雜度的交互式零知識論證協議。在其基礎上，Bünz等[46]于2018年提出了一種新的透明的短證明SNARK協議，名為Bulletproof。Bulletproof優化了先前的內積求值的遞推論證技術，實現了證明者驗證者時間為O(n)，證明大小為O(logn)的透明的SNARK協議。

某種程度上，Bulletproof蘊含著一個無需可信第三方的具備內積求值功能的多項式承諾方案，事實上許多CRS可更新的SNARK協議，如sonic和plonk等，都可以視作是通過多項式承諾與多項式IOP的結合。其之所以是可更新的而不是透明的，原因在于其使用的多項式承諾不是透明的。最近Bünz等[59]在未知階群上使用Diophantine Argument of Knowledge (DARK)技術構造了新的多項式承諾。未知階群可以使用RSA群或者類群，當使用類群時，多項式承諾不需要任何可信方。DARK多項式承諾(1)需要特別說明的是，在Crypto 2021的文獻[60]中，Block等指出在DARK多項式承諾方案的安全性證明中存在著一處錯誤。目前尚不知這個錯誤能否在方案不變的情況下被修復。擁有常數的參數與承諾大小，當承諾μ個變量的d次多項式時，其多項式上點的打開需要O(dμμlogd)EXP的證明時間，O(μlogd)EXP的驗證時間與2μlogdU的證明長度，其中EXP指的是類群上的一次λ-bit指數操作(所需的時間),U指的是未知階群上的元素(長度)。Bünz等利用DARK承諾方案改進了Sonic方案，得到了Supersonic方案，后者是透明的SNARK，證明者時間為O(nlogn)EXP，驗證者時間為3log (n)EXP，證明長度為2lognU。當證明n=220規模的線路時，Supersonic僅需要10.1 KB的證明大小。

5 純公鑰模型下的zk-SNARKs

不同于通用可更新和透明的zk-SNARKs構造思想，還有一些值得考慮的可實現去中心化的比CRS模型更弱的模型，例如在由文獻[61]中提出的參數篡改(Parameter Subversion)模型下，考慮生成公共參數的一方有可能被敵手控制進而生成有利于敵手的參數，并最終導致協議喪失可靠性或零知識性。構造該模式下安全的zk-SNARKs協議將避免傳統協議下對于可信第三方的依賴。另外，為了在更強的零知識概念下(如并發零知識、可重置零知識)進一步降低協議的輪復雜性，Canetti等[62]提出了一個比CRS模型更弱的純公鑰(BPK, Bare Public Key)模型。與參數篡改模型類似，BPK模型也不需要可信第三方來生成CRS，而是驗證者在與證明者執行協議之前在公共文件夾里放上自己的公鑰，顯然該模型下也存在參數篡改所帶來的威脅。事實上BPK模型下的驗證者就是參數篡改模型下的參數篡改敵手，正如文獻[63]所證，這2個模型幾乎可以被認為是等價的。文獻[61]第一個研究了在非交互零知識證明(NIZK，Non-interactive Zero Knowledge Proofs)的可信參數被篡改時所保持的安全性定義：防篡改可靠性與防篡改零知識性，并揭示了2者無法同時滿足；此外，他們證明了同時滿足防篡改零知識性和可靠性的協議是存在的，并構造了一個滿足這些性質的NIZK協議，但該NIZK協議只有理論意義，實用價值不高。文獻[64]基于提出新的知識假設，給出了比文獻[61]更強的抗參數篡改的安全性定義，在文獻[7]的方案下通過在CRS中添加部分信息并讓證明者執行一個高效的CRS驗證算法，以確保CRS的良好結構，使得其同時具備防篡改零知識性和知識可靠性(Knowledge Soundness)。文獻[65]同樣提出了新的知識假設以及新的模擬技術，在不擴大CRS尺寸的情況下，遵循文獻[61]的安全性定義并展示了包括文獻[7]提出的方案在內的大多數基于QAP的zk-SNARK方案都可以同時實現防篡改零知識性和知識可靠性。文獻[66]通過改進文獻[64]的方案，總結了構造抗參數篡改zk-SNARK的一般方法，并將文獻[65]中的模擬技術應用于文獻[64]的方案之中。

文獻[63]認為CRS模型下的防篡改零知識性等價于BPK模型下的沒有輔助輸入的非黑盒的零知識。文獻[67]提出了個體化規約技術并利用這個技術構造了2輪延遲輸入的零知識協議等應用，事實上也提供了一個構造BPK模型下的NIZK的構造框架。這個框架目前只能被用來構造BPK模型下的NIZK方案而不是BPK模型下的zk-SNARK。盡管如文獻[7]中的十分高效的zk-SNARKs已經有辦法被改造成抗參數篡改的版本，但是這些改造都需要引入不可證偽的知識假設并且它們的零知識性只能滿足防篡改零知識，換句話說，在BPK模型下只能實現沒有輔助輸入的非黑盒零知識。除此之外，文獻[68]還研究了如何在零知識方面保證防篡改零知識性的同時在可靠性方面保證模擬可抽取(Simulation-Extractable)。

6 模擬多方安全計算的zk-SNARKs

姚期智先生在1982年提出了著名的百萬富翁問題，進而誕生了安全多方計算(Secure Muti-part Computation, MPC)這一概念[69]。MPC技術能使彼此互不信任的多方協同計算任何函數并輸出計算結果，并保證任何一方均無法得到除應得的計算結果之外的其他任何信息。2007年， Ishai等[70]首次提出MPC-in-the-head的概念，這個概念是指證明者先在“頭腦中”執行MPC協議然后再對“頭腦中”各個參與方的看到的副本進行承諾并發送給驗證者，隨后驗證者V再與P交互，來判斷是否相信P的斷言。基于這個框架做的zk-SNARKs的優點是不需要可信的設置、證明時間高效而且抗量子攻擊。基于這個范式， Giacomelli等[71]發表了ZKBoo方案，該方案相比方案[70]取消了交互，且驗證時間和在此之前的zk-SNARKs差不多的情況下，證明時間幾乎快了1 000倍，缺點是其通信復雜度與電路大小呈線性關系。ZKBoo主要是通過用一個電路分解的方法來取代MPC協議從而擴展了方案[70]的想法，這意味著該證明者不需要完全遵循MPC協議的性質從而獲得更高的效率。Chase等[72]對方案[71]進行了改進，在不增加計算成本的前提下將證明長度減少了一半以上。Ames等[73]將高效的安全多方計算和Ishai等[70]提出的將MPC協議轉化為零知識交互PCPs(ZKIPCP)的一般轉換的變形相結合，從而將通信復雜度幾乎降低到了驗證電路大小的根號級別，其證明長度大約比方案[72]短4倍。

7 總 結

零知識證明理論在密碼學中處于極其重要的基礎地位。從應用上來說，零知識證明所具有的強大的隱私保護特性使得它被廣泛應用于身份認證、群簽名、安全多方計算、密碼貨幣、電子投票等領域之中。從零知識證明到非交互零知識證明再到zk-SNARKs，目前的零知識證明在功能性、簡潔性和效率上都已經做得很好但仍有很多提升空間。盡管目前文獻[7]提出的CRS模型下的方案在證明長度和驗證效率上達到了最優，但在是現實上依然存在中心化的問題。而通用可更新的zk-SNARKs的研究目前比較熱門，出現了很多各有優劣的新方案，未來主要是研究如何在效率和通信量上做到更優。透明的zk-SNARKs相比較存在可信第三方的SNARKs，其通信量與驗證者時間仍有較大差距，這也是其實用化的最大障礙，因此，其研究重點在于如何進一步減少驗證者計算量與通信量。而BPK模型下的zk-SNARK主要依靠添加額外CRS驗證算法來解決CRS模型下的中心化問題，但目前這個驗證算法的的運行時間并不理想，未來如何提出更高效的解決方式是一個待研究的課題。模擬多方安全計算的zk-SNARKs相比于其它SNARKs的缺點主要在于通信量，因此其研究重點在于如何在保證效率的同時設計通信量更小的方案。