1. 引言

零知識證明（ZKP）是由Goldwasser等人[1]首先提出的，在密碼學(xué)領(lǐng)域有著重要的應(yīng)用。它能夠保證證明者在不提供任何有用的相關(guān)信息的情況下，使驗證者相信一個語句是真實的。零知識證明允許證明者產(chǎn)生一個簡短的證明π，可以說服任何驗證者相信證明者的公共輸入x和秘密輸入w上的公共函數(shù)f的結(jié)果是y = f（x,w）。w通常被稱為見證輸入或輔助輸入。零知識證明保證了如果證明者在計算結(jié)果時作弊，驗證者以壓倒性的概率拒絕，而證明過程不會透露關(guān)于秘密w的額外信息，包括證明者的數(shù)據(jù)、證明者的身份和驗證者的身份等。在區(qū)塊鏈應(yīng)用中，驗證者可以使用ZKP來驗證證明者在區(qū)塊鏈環(huán)境中是否有足夠的交易量，而不會泄露任何私有交易數(shù)據(jù)。

零知識證明作為一項重要的密碼學(xué)技術(shù)，在許多領(lǐng)域有著廣泛應(yīng)用，例如隱私保護(hù)、區(qū)塊鏈智能合約的驗證等。為了更深入地理解零知識證明的多樣性和適用性，接下來本文將進(jìn)一步探討零知識證明的不同類型，包括Snark（Succinct Non-Interactive Arguments of Knowledge）、Stark（Scalable Transparent ARguments of Knowledge）以及Bulletproof等。每種類型都在特定情境下具有獨(dú)特的優(yōu)勢和應(yīng)用。

2. 零知識證明分類

在當(dāng)前的密碼學(xué)研究和實踐中，零知識證明（ZKP）技術(shù)已成為確保數(shù)據(jù)隱私和完整性的關(guān)鍵工具。零知識證明允許一方（證明者）向另一方（驗證者）證明某個陳述的正確性，而無需透露除該陳述正確性之外的任何信息。由于零知識證明底層的構(gòu)造繁雜，本文更強(qiáng)調(diào)零知識證明在區(qū)塊鏈上的應(yīng)用，故本節(jié)將深入探討區(qū)塊鏈上三種代表性以及使用范圍最廣的零知識證明構(gòu)造：ZK-Snark、ZK-Stark和Bulletproof。這三種構(gòu)造方法體現(xiàn)了零知識證明技術(shù)在安全性、效率和實用性方面的不同技術(shù)特點(diǎn)及發(fā)展趨勢。ZK-Snark是一種高度壓縮且非交互式的零知識證明，適用于區(qū)塊鏈和隱私保護(hù)應(yīng)用。其主要優(yōu)點(diǎn)是極高的驗證效率和低通信開銷，但這種優(yōu)勢的代價是需要一個可信的設(shè)置階段，這可能引入了中心化的風(fēng)險和潛在的安全漏洞。相比之下，ZK-Stark提供了一種無需可信設(shè)置的零知識證明方法，能夠在不犧牲透明度和安全性的前提下提供可擴(kuò)展性。它利用了密碼學(xué)中的哈希函數(shù)和其他非對稱技術(shù)，因此理論上在對抗量子計算攻擊方面具有更強(qiáng)的韌性。然而，這種方法通常會帶來更大的證明尺寸和計算開銷。最后，Bulletproof是一種新型的非交互式零知識證明技術(shù)，不需要可信的設(shè)置過程，適用于范圍證明。

2.1 ZK-Snark

ZK-Snark：一個非交互式論證系統(tǒng)R的ZK-Snark是指滿足以下條件的（G, P, Ver, Sim）：

完備性：對于關(guān)系 R 的一個真實陳述，一個誠實的證明者 P 擁有一個能夠說服驗證者V有效的證據(jù)。

知識可靠性：存在一個提取器，每當(dāng)P生成一個有效的論證時，就能計算出一個證據(jù)。提取器可以完全訪問P的狀態(tài)，包括任何隨機(jī)的硬幣，以確保對手不能通過作弊或不真實的證明欺騙系統(tǒng)。

簡潔性：一個非交互式論證，其中驗證者在 λ + |u| 的多項式時間內(nèi)運(yùn)行，并且證明大小是 λ 的多項式，稱為預(yù)處理 Snark。如果公共參考字符串是 λ 的多項式，則非交互式論證是一個完全簡潔的 Snark。

統(tǒng)計零知識：統(tǒng)計零知識是一種強(qiáng)零知識證明，在這種證明中，對于任何可能的輸入，驗證者從證明者那里獲得的信息與他在不進(jìn)行任何交互時可以模擬的信息在統(tǒng)計上是無法區(qū)分的。具體來說，這意味著存在一個模擬器，該模擬器在不與證明者交互的情況下，能夠生成一個與實際交互記錄在統(tǒng)計上無法區(qū)分的記錄。

2.2 ZK-Stark

Eli Ben-Sasson于2018年提出了一種稱為ZK-Stark的新型零知識證明[2]。ZK-Stark是ZK-Snark協(xié)議的改進(jìn)版本?！癝tark” 這個縮寫代表 “Scalable Transparent Argument of Knowledge”－即可擴(kuò)展透明知識論證?！翱蓴U(kuò)展” 指的是證明者的運(yùn)行時間最多是計算大小的準(zhǔn)線性級別、驗證時間是計算大小的對數(shù)級別。也就是說，ZK-Stark是一種針對可用對數(shù)空間，使用可計算電路表示陳述的非交互零知識論證。“透明”指的是所有驗證者信息只是公開抽樣的隨機(jī)硬幣。ZK-Stark不需要可信設(shè)置程序來實例化證明系統(tǒng)，而是依賴于基于哈希沖突的對稱加密算法，這種特性使其更加高效，并且完全擺脫了ZK-Snark中可信階段產(chǎn)生的參數(shù)，能夠有效抗擊量子計算機(jī)對算法的威脅。ZK-Stark通過AIR（algebraic intermediate representation，代數(shù)中間表示）進(jìn)行約束的表示，Stark證明系統(tǒng)將在任何時間計算的狀態(tài)都包含在從有限域取值的寄存器元組中，在每個周期更新狀態(tài)。而代數(shù)執(zhí)行軌跡（AET）則是按時間順序排列的所有狀態(tài)元組的列表。ZK-Stark可以有一個非?？斓淖C明時間和驗證時間，但證明大小過大。因此，它在投票系統(tǒng)、在線系統(tǒng)和其他一些需要識別步驟才能訪問的服務(wù)中有著光明的前景。

2.3 Bulletproof

Bulletproof的構(gòu)造思路如下：首先將電路中的乘法門約束和乘法門之間的線性約束利用 Schwartz-Zippel 引理[3]歸約為一個多項式的某一特定項系數(shù)為零的問題，然后將該問題轉(zhuǎn)化為內(nèi)積論證（IPA）[4]的陳述表示形式，最后調(diào)用內(nèi)積論證實現(xiàn)零知識證明。

Bulletproof提供了一種更有效的機(jī)密交易（CT）范圍證明，主要應(yīng)用于在加密貨幣領(lǐng)域如Zcash中。防彈技術(shù)建立在實現(xiàn)通信高效的零知識證明的技術(shù)之上，它們可以用來擴(kuò)展多方協(xié)議，如多重簽名或零知識緊急支付等，事實上，Bulletproof可以認(rèn)為是基于IPA的Snark構(gòu)造的一種。

表1 經(jīng)典零知識證明協(xié)議對比

圖片

3. 零知識證明的應(yīng)用

對于區(qū)塊鏈的擴(kuò)容問題，已成為增強(qiáng)區(qū)塊鏈網(wǎng)絡(luò)可擴(kuò)展性的關(guān)鍵方案。Rollups通過在二層協(xié)議上處理交易并將結(jié)果傳回主鏈，能夠在提高性能和降低交易費(fèi)用的同時，保持去中心化和安全性。在這一過程中，零知識證明尤為關(guān)鍵，因為它們允許在主鏈上對多筆交易的真實性進(jìn)行一次性驗證，而無需逐個驗證每筆交易的細(xì)節(jié)。而在跨鏈技術(shù)方面，ZK Bridge展示了零知識證明技術(shù)在實現(xiàn)不同區(qū)塊鏈之間資產(chǎn)與信息傳遞的潛力。與傳統(tǒng)的跨鏈橋相比，ZK Bridge的優(yōu)勢在于它不需要引入額外的信任假設(shè)，并且可以實現(xiàn)高效率的交易驗證，從而降低了計算和存儲成本。

3.1 擴(kuò)容

隨著以太坊生態(tài)的日漸繁榮，以太坊主鏈無法承受龐大的生態(tài)，導(dǎo)致整個以太坊網(wǎng)絡(luò)擁堵。Rollup 是為了緩解 Layer1 擴(kuò)容問題所提出的可擴(kuò)展性的方案，通常被稱為鏈下解決方案。它擴(kuò)展了以太坊并繼承了以太坊的安全保證。它的主要目的是在提高以太坊的性能并且降低 Gas費(fèi)用的同時，保留分布式協(xié)議的去中心化和安全性特點(diǎn)。Rollup通過將Layer1的部分?jǐn)?shù)據(jù)轉(zhuǎn)移到二層協(xié)議上進(jìn)行處理，然后將處理結(jié)果返送到Layer1上，從而增強(qiáng)區(qū)塊鏈網(wǎng)絡(luò)的可擴(kuò)展性。Rollups 會在其上的網(wǎng)絡(luò)中將交易打包在一起并進(jìn)行壓縮，然后將打包后的交易發(fā)送到Layer1主網(wǎng)進(jìn)行驗證，通過一次性驗證多筆交易，使得網(wǎng)絡(luò)效率得到提高，同時增加了可被執(zhí)行的交易數(shù)量，實現(xiàn)了網(wǎng)絡(luò)擴(kuò)容。但在這個過程中，需要保證L1的節(jié)點(diǎn)沒有作弊上傳虛假交易。

圖1 Rollup(圖源以太坊官網(wǎng))

根據(jù)證明方法，Rollup 可以大致分為兩類：樂觀（optimistic）—Rollup 和ZK（零知識）-Rollup。Optimistic-Rollup的前提是所有交易均有效，除非另有證明。如果交易的有效性受到質(zhì)疑，驗證者需要提供欺詐證明，然后將其發(fā)送到主網(wǎng)絡(luò)進(jìn)行驗證。如果發(fā)現(xiàn)無效，交易將被恢復(fù)。這種方法依賴于網(wǎng)絡(luò)參與者彼此保持誠實，從而建立信任和警惕的平衡。但是當(dāng)用戶提供欺詐證據(jù)時，主網(wǎng)上的解決方案不會立即得到解決。這可能會導(dǎo)致從Optimistic-Rollup鏈中提取資產(chǎn)時出現(xiàn)延遲，等待時間從幾天到甚至幾周不等。而零知識證明可以很好地完成上述需求，在L1打包多筆交易后同時為這個過程生成零知識證明，驗證者在Layer1上通過驗證該證明后打包生成共識，完成擴(kuò)容功能。ZK-Rollup則確保所有交易都經(jīng)過驗證，同時保持交易詳細(xì)信息完全私密。這不僅增強(qiáng)了安全性，而且提供了所有用戶都非常贊賞的更高程度的隱私。ZK-rollups的落地應(yīng)用包括基于Snark的Scroll[551]，基于Starknet的Starknet[6]，混合Snark與Stark證明機(jī)制的Taiko[7]等項目。

3.2 跨鏈

跨鏈技術(shù)是一種使得加密資產(chǎn)在不同的區(qū)塊鏈之間移動和儲存的技術(shù)。當(dāng)前市場上存在眾多獨(dú)立運(yùn)作的區(qū)塊鏈，例如比特幣和以太坊，但它們之間缺乏直接的互通機(jī)制。若無跨鏈技術(shù)，資產(chǎn)將無法在不同鏈間轉(zhuǎn)移。

圖2 ZK Bridge原理

ZK Bridge作為使用零知識證明技術(shù)的跨鏈橋梁，其最大特點(diǎn)是不需要引入額外的信任假設(shè)就可以適應(yīng)多種不同類型的區(qū)塊鏈。在這個解決方案當(dāng)中，零知識證明是在區(qū)塊鏈之外生成的，實際的驗證則是在區(qū)塊鏈上進(jìn)行的。這樣的做法大幅降低了區(qū)塊鏈上的計算和存儲成本，是當(dāng)今市場上一種相當(dāng)前沿且有潛力的跨鏈技術(shù)。目前，有幾個項目正在發(fā)展 ZK Bridge 的生態(tài)系統(tǒng)，也就是開發(fā)基于零知識證明技術(shù)的跨鏈橋解決方案，但皆處于開發(fā)階段。例如，Succinct Labs[8]、Electron Labs[9]、zkIBC[10]、Polyhedra Network[11]的 zkBridge[12] 等。Succinct Labs推出了Tendermint X，這是第一個開源的、高性能的Tendermint ZK輕客戶端，它為Cosmos和Ethereum之間提供了一個無需信任的ZK橋接，標(biāo)志著將Cosmos連接到Ethereum的實現(xiàn)。Polyhedra Network的zkBridge利用其獨(dú)創(chuàng)的deVirgo協(xié)議，一種高效的分布式零知識證明協(xié)議，實現(xiàn)了令人印象深刻的性能優(yōu)化和線性可擴(kuò)展性。deVirgo協(xié)議的核心優(yōu)勢在于它幾乎完美的線性可擴(kuò)展性—在一個分布式計算網(wǎng)絡(luò)中，隨著計算資源的線性增加，證明的生成時間將成倍減少。deVirgo協(xié)議的這一特性特別適合處理大量數(shù)據(jù)或高頻交易，使得zkBridge在處理跨鏈交易時，不僅保持了零知識證明的隱私和安全性優(yōu)勢，同時也確保了極高的吞吐量和低延遲，這對于金融交易和復(fù)雜的去中心化應(yīng)用（dApps）來說至關(guān)重要。

4. 挑戰(zhàn)與未來展望

零知識證明技術(shù)仍然面臨許多挑戰(zhàn)，同時也衍生出眾多研究方向。

較弱假設(shè)的挑戰(zhàn)。ZKP的一個挑戰(zhàn)是，是否可以在一些較弱假設(shè)下有效實施。例如，Zerocash中使用了ZK-Snark，但它需要一個受信任的第三方來進(jìn)行設(shè)置和系統(tǒng)初始化。ZKP可以在沒有受信任第三方的情況下實施，但這會影響ZKP的效率。因此，研究在沒有受信任第三方的情況下有效實施ZKP是值得的。Spartan是一個引人注目的成果[13]，它提供了一種無需可信設(shè)置的ZK-Snark，特別適用于解決算術(shù)電路滿足性問題（R1CS）。它的特點(diǎn)在于，它能夠在驗證證明時產(chǎn)生低于線性的成本，而且不要求NP陳述的結(jié)構(gòu)具有一致性。此外，Spartan實現(xiàn)了時間最優(yōu)化的證明者，這在先前的ZK-Snark文獻(xiàn)中幾乎未被實現(xiàn)。Spartan應(yīng)用了新技術(shù)，如計算承諾和一個加密編譯器Spark，用于將現(xiàn)有的可提取多項式承諾方案轉(zhuǎn)換為有效處理稀疏多項式的方案，這對于實現(xiàn)時間最優(yōu)化的證明者至關(guān)重要。Spartan作為Rust庫實現(xiàn)，并與最新ZK-Snark進(jìn)行了實驗比較，表現(xiàn)出多方面的優(yōu)勢，包括在無可信設(shè)置方案中具有較快的證明者速度，生成更短的證明，驗證時間低，綜合效率優(yōu)秀。

零知識證明的硬件加速。零知識證明技術(shù)雖然被廣泛認(rèn)為是解決區(qū)塊鏈主要問題的關(guān)鍵方案，但長期受制于其本身的高計算密集性導(dǎo)致的計算效率問題。正是基于這種背景，ZKP硬件加速成為解決 ZKP 效率問題的一個重要創(chuàng)新方向。ZKP 硬件加速涉及在專用硬件（如 GPU、 FPGA 和 ASIC）上實現(xiàn) ZKP 算法的優(yōu)化，使其能夠更快地處理復(fù)雜計算，從而大幅提高 ZKP 的生成和驗證速度。在 ZKP 的不同證明系統(tǒng)及其相關(guān)實現(xiàn)中，計算需求與資源開銷各不相同。在眾多證明系統(tǒng)中，有兩種計算操作尤為耗時與昂貴，分別是多標(biāo)量乘法（Multiscalar Multiplication-MSM）和快速傅里葉變換（Fast Fourier Transform-FFT）。CUZK[14]中提出MSM 算法占據(jù)了證明生成總運(yùn)行時間的70%以上。隨著新的 ZKP 框架 STARK 的發(fā)展，也有更多的證明是基于 FTT 算法為主。

多標(biāo)量乘法（MSM）優(yōu)化。MSM是一種在橢圓曲線密碼學(xué)中常見的操作，它涉及對多個標(biāo)量和橢圓曲線點(diǎn)的乘法與求和運(yùn)算。雖然MSM 可以通過并行處理來加速，但即使在多核心的系統(tǒng)上，對于復(fù)雜的應(yīng)用MSM 的運(yùn)算仍然需要消耗大量的資源與時間。MSM 算法需要處理大量的元素與重復(fù)執(zhí)行相同的操作。

快速傅里葉變換（FFT）優(yōu)化。以STARK為代表的零知識證明系統(tǒng)大量用到了快速傅里葉變換（FFT）。這個算法用于高效計算序列的離散傅里葉變換（DFT）及其逆變換。FFT 的運(yùn)行過程嚴(yán)重依賴于數(shù)據(jù)的頻繁交換，數(shù)據(jù)交換過程中需要從大數(shù)據(jù)集中“隨機(jī)”地傳輸元素，這在硬件內(nèi)存有限的情況下尤為困難。盡管硬件操作本身非?？?，但傳輸數(shù)據(jù)的時間卻顯著降低了整體操作速度。除此之外，F(xiàn)FT 算法通常需要將輸入數(shù)據(jù)重新排列成特定順序以執(zhí)行變換，這可能需要大量的數(shù)據(jù)移動，對于大型FFT算法規(guī)模來說，這可能成為性能瓶頸。FFT 雖然是一種強(qiáng)大且廣泛應(yīng)用的算法，但在大型數(shù)據(jù)處理和分布式計算環(huán)境中，其性能和效率受到數(shù)據(jù)交換、帶寬限制的顯著影響。

基于 SNARK 的證明系統(tǒng)主要依賴于 MSM 算法，而 STARK 類證明則主要使用 FFT 算法。因此，目前的硬件加速主要是面向這兩種加密算法的需求進(jìn)行優(yōu)化。MSM 對硬件的需求包括強(qiáng)大的并行處理能力、較大的內(nèi)存容量。相比之下，F(xiàn)FT 對硬件的需求則包括高帶寬、大內(nèi)存容量、高效的數(shù)據(jù)訪問模式。

參考文獻(xiàn)

[1] Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof-systems[M]//Providing sound foundations for cryptography: On the work of shafi goldwasser and silvio micali. 2019: 203-225.

[2] Ben-Sasson E, Bentov I, Horesh Y, et al. Scalable zero knowledge with no trusted setup[C]//Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part III 39. Springer International Publishing, 2019: 701-732

[3] Schwartz J T. Fast probabilistic algorithms for verification of polynomial identities[J]. Journal of the ACM (JACM), 1980, 27(4): 701-717.

[4] Bootle J, Cerulli A, Chaidos P, et al. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting[C]//Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35. Springer Berlin Heidelberg, 2016: 327-357.

[5] https://github.com/scroll-tech

[6] https://github.com/starknet-io

[7] https://github.com/taikoxyz

[8] https://github.com/succinctlabs

[9] https://github.com/Electron-Labs

[10] https://www.zkibc.com/

[11] https://github.com/topics/polyhedra

[12] https://zkbridge.com/

[13] Setty S. Spartan: Efficient and general-purpose zkSNARKs without trusted setup[C]//Annual International Cryptology Conference. Cham: Springer International Publishing, 2020: 704-737.

[14] [63]Lu T, Wei C, Yu R, et al. Cuzk: Accelerating zero-knowledge proof with a faster parallel multi-scalar multiplication algorithm on gpus[J]. Cryptology ePrint Archive, 2022.