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

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

零知識(shí)證明分類

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

ZK-Snark

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

完備性：對(duì)于關(guān)系 R 的一個(gè)真實(shí)陳述，一個(gè)誠(chéng)實(shí)的證明者 P 擁有一個(gè)能夠說(shuō)服驗(yàn)證者V有效的證據(jù)。

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

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

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

ZK-Stark

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

Bulletproof

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

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

零知識(shí)證明的應(yīng)用

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

擴(kuò)容

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

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

跨鏈

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

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

挑戰(zhàn)與未來(lái)展望

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

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

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

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

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

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