1. 引言

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

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

2. 零知識證明分類

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

2.1 ZK-Snark

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

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

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

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

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

2.2 ZK-Stark

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

2.3 Bulletproof

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

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

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

圖片

3. 零知識證明的應用

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

3.1 擴容

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

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

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

3.2 跨鏈

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

圖2 ZK Bridge原理

ZK Bridge作為使用零知識證明技術(shù)的跨鏈橋梁，其最大特點是不需要引入額外的信任假設就可以適應多種不同類型的區(qū)塊鏈。在這個解決方案當中，零知識證明是在區(qū)塊鏈之外生成的，實際的驗證則是在區(qū)塊鏈上進行的。這樣的做法大幅降低了區(qū)塊鏈上的計算和存儲成本，是當今市場上一種相當前沿且有潛力的跨鏈技術(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橋接，標志著將Cosmos連接到Ethereum的實現(xiàn)。Polyhedra Network的zkBridge利用其獨創(chuàng)的deVirgo協(xié)議，一種高效的分布式零知識證明協(xié)議，實現(xiàn)了令人印象深刻的性能優(yōu)化和線性可擴展性。deVirgo協(xié)議的核心優(yōu)勢在于它幾乎完美的線性可擴展性—在一個分布式計算網(wǎng)絡中，隨著計算資源的線性增加，證明的生成時間將成倍減少。deVirgo協(xié)議的這一特性特別適合處理大量數(shù)據(jù)或高頻交易，使得zkBridge在處理跨鏈交易時，不僅保持了零知識證明的隱私和安全性優(yōu)勢，同時也確保了極高的吞吐量和低延遲，這對于金融交易和復雜的去中心化應用（dApps）來說至關重要。

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

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

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

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

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

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

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

參考文獻

[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.