撰文: ZKSwap 小白 (info@zks.org

在 Layer2 擴容賽道上,ZkRollup 方案以完美的數據可用性以及與 Layer1 同等級的安全性,備受青睞;以單個 Block 爲處理單元,用零知識證明算法來保證此區塊引起的世界狀態變化的有效性,大幅降低了每筆交易的上鍊成本,同時也增長了系統的吞吐效率。然而,在實際的落地過程中,研究者們發現,簡單的 ZkRollup 方案帶來的擴容效果,並不能滿足真實的場景需求;這和很多因素有關,電路參數的限制,零知識證明算法的效率等等;研究者們做了很多努力,比如對零知識證明算法進行加速,配備超高配置機器,優化電路規模等,雖帶來了一定的性能提升,但仍難以滿足需求。

研究者們當然希望,鏈上一次處理的交易越多越好。朝着這個目標出發,研究者們首先發現了聚合證明(Aggregation proof)技術,該技術已經被 ZKSwap 推出的 ZKSpeed 擴容方案採用。在前面的文章中,已經解釋了聚合證明(Aggregation proof)的原理和思想,簡單來說就是把多個區塊的證明聚合成一個證明,使得鏈上一次就可以完成多個區塊的驗證,大大的降低了交易的平均成本,其原理如下圖所示:

Layer2 擴容關鍵技術:遞歸零知識證明剖析

該方案雖然有優勢,可實現多個區塊的證明的一次驗證,但也有其一定的侷限性:

1. 一次聚合的區塊是有上限的,受限於電路參數的限制;
2. 聚合的區塊越多,電路就越大,直到其規模的上限;這種電路生成的證明時間要更長,證明密鑰和驗證密鑰也會佔用更大的存儲空間;
3. 目前可支持的最大聚合粒度是 20 個區塊,也就是湊齊 20 個區塊後,纔會開始聚合處理。如果生成證明的效率比較低,這會導致這些區塊被確認的時間拉長,尤其是最早生成的那些區塊;

受限於證明計算(Proof computation)和 CRS 生成複雜度的限制,上述的零知識證明算法是不可擴展的。因此,研究者們也在努力尋找一個可擴展的零知識證明算法,即 Scalable zk-SNARKs。

Scalable zk-SNARKs 可拓展的 zk-SNARKs

在論文《Scalable Zero Knowledge via Cycles of Elliptic Curves》中,Eli Ben-Sasson 等給出了 Scalable zk-SNARKs 的定義:

1. Key generation is cheap:即,Key 生成的時間和計算複雜度沒有關係(如果是 Scalable zk-STARKs,可能不需要);
2. Proof generation is carried out incrementally:即,證明生成過程既包含了當前執行步驟的正確性又包含了在此之前所有計算的正確性,這種 zk-SNARKs 是 incrementally computable;

爲了方便大家理解,用一張圖來表示上述思想:

Layer2 擴容關鍵技術:遞歸零知識證明剖析

上圖表示意思是:證明着證明一個遞歸計算過程,即:初始狀態爲 S0,經過 t 次函數 F 迭代計算後的結果爲 St (像極了區塊鏈裏區塊更新的過程)。

第一個計算方式,Monolithic option:證明方 P 把 t 次計算過程全部寫成電路,然後一次性證明,正如我們前面所列舉的一樣,存在相同的侷限性,很高的時間複雜度和空間複雜度;

第二個計算方式,Recursive option:遞歸計算,其過程如下:

1. 首先對於初始狀態 S0=>S1,證明方 P 對於 S1 = F(S0) 計算過程生成一個證明π1;
2. 對於 S1=>S2 的轉換,由圖中可以得知,證明方 P 證明了兩部分:{S2 = F(S1), V(S1, π1) = 1},前半部分保證了當前計算的有效性,後半部分保證了上一步計算過程的有效性;由於在 zk-SNARKs 裏,證明生成的時間比原始計算要快一些,因此,對於驗證過程進行證明是合理的;

由此可以看出, Recursive option 滿足 Scalable zk-SNARKs 了基本要求:

1. Key 的生成和循環次數沒有關係,取決於單次 F 的複雜度,如果是 general zk-SNARKs,只取決於安全參數;
2. 證明滿足 incrementally computable,每個證明都包含了在此之前所有計算的有效性;
3. 證明的大小固定,和迭遞歸次數 t 沒有關係;
由上可知,Scalable zk-SNARKs 採用了 Recursive 思想,即當前的 Prove 過程包含上一步的驗證過程電路,具體如下圖所示:

Layer2 擴容關鍵技術:遞歸零知識證明剖析

可以看到,P2 證明電路里,包含了上一步 P1 的驗證過程電路。需要注意的是,P1 對應的 V 在域 Fq 上,P2 的證明過程在 Fr 上,如何在 Fr 上表示 V 的算術電路,是一個值得探討的過程;由於 Cv 可以看作是 P 的一個子電路,因此,q 需要滿足 q = #E(Fr) 或者 q 整除 #E(Fr),即 q 整除 rk - 1,因此:

嘗試 1. 理想的情況下,如果 r = q,那麼在 Fr 上,能完美表示 Fq 上的 V 的算術電路,但是根據上述原理,r != q 恆成立;
嘗試 2. 對於 q != r,因爲需要在 Fr 上去模擬 Fq 上的計算,會導致計算複雜度的提高 log(r) 倍;
嘗試 3. 採用橢圓曲線循環(cycle of elliptic curves),可以完美實現 Recursive 過程;

具體的,選取兩個大素數,r 和 q。滿足 r = #E(Fq) 和 q = #E(Fr),即,當前羣的域等於另外一個羣的階,反之亦然。因此,域 Fq 上的證明方 P 可以完美的在 Fq 上實現 Fr 上的驗證電路,域 Fr 上的證明方 P 也可以在 Fr 上實現 Fq 上的驗證電路;因此不會出現嘗試 2 裏面的缺陷。

下面表格列舉常用的 cycle of elliptic curves (https://eprint.iacr.org/2014/595.pdf

Layer2 擴容關鍵技術:遞歸零知識證明剖析

寫在最後

通過採用遞歸證明組合密碼技術 (Recursive Proof Composition),zk-SNARKS 變成了 Scalable zk-SNARKs,實現了更高效、簡潔的零知識證明算法,並能真實的落地應用。即將發佈主網的 Mina 就採用了這種技術實現了簡潔的區塊鏈,即固定大小的鏈,保持在 22KB 左右;同時,其他的技術團隊包括 Matter Labs、starkWare 等也在計劃採用 Scalable zk-SNARKs 技術來實現 Layer2 更高的擴容。ZKSwap 團隊在 Layer2 賽道上持續發力,在 Scalable zk-SNARKs 上亦有所突破,相信不久就會應用於新的版本上。