零知識證明技術綜述及其在區塊鏈領域的應用

摘要

零知識證明(ZKP)技術被普遍認爲是區塊鏈領域最重要的創新之一,也是近年來風險投資的重點關注領域。本文對ZKP技術近40年的發展歷程和最新研究進行了系統性綜述。

首先,介紹了ZKP的基本概念和歷史背景。接着重點分析了基於電路的ZKP技術,包括zkSNARK、Ben-Sasson、Pinocchio、Bulletproofs和Ligero等模型的設計、應用和優化方法。在計算環境方面,本文介紹了ZKVM和ZKEVM,探討了它們如何提升交易處理能力、保護隱私和提高驗證效率。文章還闡述了零知識Rollup(ZK Rollup)作爲Layer擴展方案的工作機制和優化方法,以及硬件加速、混合解決方案和專用ZK EVM的最新進展。

最後,本文展望了ZKCoprocessor、ZKML、ZKThreads、ZK Sharding和ZK StateChannels等新興概念,並探討了它們在區塊鏈擴展性、互操作性和隱私保護方面的潛力。

通過分析這些最新技術和發展趨勢,本文爲理解和應用ZKP技術提供了全面視角,展示了其在提升區塊鏈系統效率和安全性方面的巨大潛力,爲未來的投資決策提供了重要參考。

目錄

前言

一、零知識證明基礎知識

1. 概述
2. 零知識證明示例

二、非交互零知識證明

1. 背景
2. NIZK的提出
3. Fiat-Shamir變換
4. Jens Groth及其研究
5. 其他研究

三、基於電路的零知識證明

1. 背景
2. 電路模型的基本概念與特點
3. 零知識證明中的電路設計與應用
4. 潛在的缺陷和挑戰

四、零知識證明模型

1. 背景
2. 常見算法模型
3. 基於線性PCP和離散對數問題的方案
4. 基於普通人證明的方案
5. 基於概率可檢驗證明(PCP)的零知識
6. 基於CPC(通用證明構造)的設置階段進行分類

五、零知識虛擬機的概述和發展

1. 背景
2. 現有的ZKVM的分類
3. 前端與後端範式
4. ZKVM範式的優缺點

六、零知識以太坊虛擬機的概述和發展

1. 背景
2. ZKEVM的工作原理
3. ZKEVM的實現流程
4. ZKEVM的特點

七、零知識二層網路方案概述與發展

1. 背景
2. ZK Rollup的工作機制
3. ZK Rollup的缺點與優化

八、零知識證明的未來發展方向

1. 加速計算環境的發展
2. ZKML的提出和發展
3. ZKP擴容技術相關發展
4. ZKP互操作性的發展

九、結論

參考文獻

前言

互聯網正在進入Web3時代,區塊鏈應用(DApps)發展迅速。近年來,區塊鏈平台每天承載着數百萬用戶的活動,處理數十億筆交易。這些交易產生了大量涉及用戶身分、交易金額、帳戶地址和餘額等敏感個人信息的數據。由於區塊鏈的開放性和透明性,這些存儲的數據對所有人都是開放的,因此引發了多種安全與隱私問題。

目前有幾種加密技術可以應對這些挑戰,包括同態加密、環籤名、安全多方計算和零知識證明。同態加密允許在不解密密文的情況下執行運算,有助於保護帳戶餘額和交易金額的安全,但無法保護帳戶地址的安全。環籤名提供了一種特殊的數字籤名形式,能夠隱藏籤名者的身分,從而保護帳戶地址的安全,但對帳戶餘額和交易金額的保護則無能爲力。安全多方計算允許在多個參與者之間分配計算任務,而無需任何參與者知曉其他參與者的數據,有效保護了帳戶餘額和交易金額的安全,但同樣不能保護帳戶地址的安全。此外,這些技術無法在不泄露交易金額、帳戶地址和帳戶餘額的情況下用於驗證區塊鏈環境中證明者是否擁有足夠的交易金額。

零知識證明是一種更全面的解決方案,這種驗證協議允許在不透露任何中介數據的情況下驗證某些命題的正確性。該協議不需要復雜的公鑰設施,其重復實施也不會爲惡意用戶提供獲取額外有用信息的機會。通過ZKP,驗證者能夠在不泄露任何私人交易數據的情況下,驗證證明者是否具有足夠的交易金額。驗證過程包括生成包含證明者聲稱的交易金額的證明,然後將該證明傳遞給驗證者,驗證者對證明進行預定義的計算,並產出最終的計算結果,從而得出是否接受證明者聲明的結論。如果證明者的聲明被接受,意味着他們擁有足夠的交易金額。上述驗證過程可以記錄在區塊鏈上,沒有任何僞造。

ZKP這一特性使其在區塊鏈交易和加密貨幣應用中扮演核心角色,特別是在隱私保護和網路擴容方面,使得其不僅成爲了學術研究的焦點,被廣泛認爲是自分布式帳本技術成功實施以來最重要的技術創新之一,同時也是行業應用和風險投資的重點賽道。

由此,諸多基於ZKP的網路項目相繼湧現,如ZkSync、StarkNet、Mina、FIL和Aleo等。隨着這些項目的發展,關於ZKP的算法創新層出不窮,據報道幾乎每週都有新算法問世。此外,與ZKP技術相關的硬件開發也在迅速進展,包括專爲ZKP優化的芯片。例如,一些項目已經完成了大規模的資金募集,這些發展不僅展示了ZKP技術的快速進步,也反映了從通用硬件向專用硬件如GPU、FPGA和ASIC的轉變。

這些進展表明,零知識證明技術不僅是密碼學領域的一個重要突破,也是實現更廣泛區塊鏈技術應用的關鍵推動力,尤其是在提高隱私保護和處理能力方面。

因此,我們決定系統地整理零知識證明(ZKP)的相關知識,以更好地輔助我們做出未來的投資決策。爲此,我們綜合審閱了關於ZKP相關的核心學術論文(依據相關性和引用次數進行排序);同時,我們也詳細分析了該領域內領先的項目的資料和白皮書(根據其融資規模進行排序)。這些綜合性的資料搜集和分析爲本文的撰寫提供了堅實的基礎。

一、零知識證明基礎知識

1.概述

1985年,學者Goldwasser、Micali和Rackoff在論文《The Knowledge Complexity of Interactive Proof-Systems》中首次提出了零知識證明(Zero-Knowledge Proof,ZKP)和交互式知識證(Interactive Zero-Knowledge,IZK)。該論文是零知識證明的奠基之作,定義了許多影響後續學術研究的概念。例如,知識的定義是"不可行計算的輸出",即知識必須是一個輸出,且是一個不可行計算,意味着它不能是簡單的函數,而需是復雜的函數。不可行計算通常可以理解爲是一個NP問題,即可以在多項式時間內驗證其解正確性的問題,多項式時間指的是算法運行時間可以用輸入大小的多項式函數來表示。這是計算機科學中衡量算法效率和可行性的重要標準。由於NP問題的求解過程復雜,因此被認爲是不可行計算;但其驗證過程相對簡單,所以非常適合用於零知識證明驗證。

NP問題的一個經典例子是旅行商問題,其中要找到訪問一系列城市並返回起點的最短路徑。雖然找到最短路徑可能很困難,但給定一個路徑,驗證這條路徑是否是最短的相對容易。因爲驗證一個具體路徑的總距離可以在多項式時間內完成。

Goldwasser等人在其論文中引入了"知識復雜度"這一概念,用以量化在交互式證明系統中,證明者向驗證者泄露的知識量。他們還提出了交互式證明系統(Interactive Proof Systems,IPS),其中證明者(Prover)和驗證者(Verifier)通過多輪互動來證明某個語句的真實性。

綜上,Goldwasser等人總結的零知識證明的定義,是一種特殊的交互式證明,其中驗證者在驗證過程中不會獲得除語句真值外的任何額外信息;並且提出了三個基本特性包括:

1.完備性:如果論證是真實的,誠實的證明者可以說服誠實的驗證者這一事實;

2.可靠性:如果證明者不知道聲明內容,他只能以微不足道的概率欺騙驗證者;

3.零知識性:在證明過程完成後,驗證者只獲得"證明者擁有此知識"的信息,而無法獲得任何額外內容。

2.零知識證明示例

爲更好理解零知識證明及其屬性,以下是一個驗證證明者是否擁有某些私密信息的示例,該示例分爲三個階段:設置、挑戰和響應。

第一步:設置(Setup)

在這一步,證明者的目標是創建一個證據,證明他知道某個祕密數字 s,但又不直接顯示 s。設祕密數字;

選擇兩個大的質數 p 和 q,計算它們的乘積 。設質數 和 ,計算得到的;

計算,這裏,v 作爲證明的一部分被發送給驗證者,但它不足以讓驗證者或任何旁觀者推斷出 s。;

隨機選擇一個整數 r,計算 並發送給驗證者。這個值 x 用於後續的驗證過程,但同樣不暴露 s。設隨機整數,計算得到的 。

第二步:挑戰(Challenge)

驗證者隨機選擇一個位 a(可以是0或1),然後發送給證明者。這個"挑戰"決定了證明者接下來需要採取的步驟。

第三步:響應(Response)

根據驗證者發出的 a 值,證明者進行響應:

如果,證明者發送 (這裏 r 是他之前隨機選擇的數)。

如果 ,證明者計算 並發送。設驗證者發送的隨機位,根據 a 的值,證明者計算 ;

最後,驗證者根據收到的 g 來驗證 是否等於 。如果等式成立,驗證者接受這個證明。當 時,驗證者計算驗證者計算 ,右側驗證 ; 當 時,驗證者計算驗證者計算 ,右側驗證 。

這裏,我們看到驗證者計算得到的 說明證明者成功地通過了驗證過程,同時沒有泄露他的祕密數字 s。在這裏,由於a只可以取0或1,僅有兩種可能性,證明者依靠運氣通過驗證的概率(當a取0時)。但驗證者隨後再挑戰證明者次,證明者不斷更換相關數字,提交給驗證者,且總能成功地通過驗證過程,這樣一來證明者依靠運氣通過驗證的概率(無限趨近於0),證明者確實知道某個祕密數字 s的結論便得到證明。這一例子證明了零知識證明系統的完整性、可靠性和零知識性。

二、非交互零知識證明

1.背景

零知識證明(ZKP)在傳統概念中通常是交互式和在線的協議形式;例如,Sigma協議通常需要三到五輪交互才能完成認證。然而,在諸如即時交易或投票等場景中,往往沒有機會進行多輪交互,特別是在區塊鏈技術應用中,線下驗證功能顯得尤爲重要。

2.NIZK的提出

1988年,Blum、Feldman和Micali首次提出了非交互式零知識(NIZK)證明的概念,證明了在無需多輪交互的情況下,證明者(Prover)與驗證者(Verifier)仍可完成認證過程的可能性。這一突破使得即時交易、投票以及區塊鏈應用的實現變得可行。

他們提出非交互式零知識證明(NIZK)可以