密碼學證明(CI)領域經歷了「寒武紀爆炸」式發展,僅 2019 年就有 Libra、Sonic、SuperSonic、PLONK 等零知識證明系統出現。

原文標題:《寒武紀密碼學證明大爆發,數十個零知識證明系統該如何選?》(A Cambrian Explosion of Crypto Proofs)
撰文:Eli Ben-Sasson,StarkWare 公司的聯合創始人兼首席科學家
翻譯:灑脫喜

一、介紹

35 億年之前,地球上的生命還都是原始單細胞生物。然後,在經歷被稱爲寒武紀生命大爆發的時期中,我們今天認識的幾乎所有動物種系都出現了。

通過類比,我們目前在計算完整性的密碼學證明(CI)領域也經歷了「寒武紀爆炸」,其中一個子集就包括零知識證明。幾年之前,一年的時間裏大約會出現 1-3 個新的零知識證明系統,而現在已發展到每個月(甚至有時會是周爲單位)就能看到近似數量新系統的出現。在 2019 年,我們瞭解到的新零知識證明結構,例如有 Libra、Sonic、SuperSonic、PLONK、SLONK、Halo、Marlin、Fractal、Spartan、簡潔 Aurora,以及 OpenZKP、Hodor 和 GenSTARK 等實現。哦,好吧,在差不多寫完這篇文章的時候,RedShift 以及 AirAssembly 也已經出現。

如何理解這些奇妙的創新呢?這篇文章的目的是確定代碼中實現的所有 CI 系統的共同點,並討論一些不同的因素。

請注意,這篇文章將有些技術性,因爲它假設讀者掌握了一些密碼學背景!不過,對於感興趣的非密碼學讀者來說,它可能也是值得粗略一覽的,你可以憑此瞭解該領域所使用的一些行話。

儘管如此,我們的描述將是簡短的,並且故意避開數學方面的東西。這篇文章的另一個主要目的,是解釋爲什麼我們 StarkWare 公司會把科學、工程學及產品方面的所有核心都放到 CI 領域的一個特定子家族上,從此之後,我們會稱之爲對稱 STARKs (symmetric STARKs)。

計算完整性證明系統,有助於解決困擾去中心化區塊鏈的兩大基本問題:隱私及可擴展性。零知識證明(ZKP)1 通過屏蔽計算的某些輸入而不損害完整性來提供隱私。而簡潔可驗證 CI 系統,通過指數級壓縮驗證大批量交易完整性所需的計算量,以此提供可擴展性。
所有在代碼中實現的 CI 系統,都具有兩個共同點:它們都使用被稱爲 Arithmetization 的東西,並且所有的密碼都強制使用一個稱爲「低階順應性」(LDC)2 的概念。

Arithmetization 是指通過證明算法來減少計算語句。你可以從這樣的概念性陳述開始:

「I know the keys that allow me to spend a shielded Zcash transaction」(我知道允許我花費一筆屏蔽 Zcash 交易的密鑰)

然後將它轉換爲包含一組有界次多項式的代數陳述,如:

「「I know four polynomials A(X), B(X), C(X), D(X), each of degree less than 1,000, such that this equality holds: A(X)B²(X)-C(X) = (X¹⁰⁰⁰–1)D(X)」」 (我知道四個多項式 A (X),B (X),C (X),D (X),它們每個階數都小於 1000,所以這個等式成立:A(X)B²(X)-C(X) = (X¹⁰⁰⁰–1)D(X))

低階順應性(LDC)是指使用密碼學來確保 prover 實際選擇低階多項式 3,並在 verifier 請求的隨機選擇點上評估這些多項式。在上面的例子中(本文會持續提及),一個好的 LDC 解決方案向我們保證,當詢問有關 x₀的問題時,它將使用 a₀、b₀、c₀、d₀的值來回答輸入 x₀上的 A、B、C 和 D 的正確值。棘手的部分是,prover 可能在看到查詢 x₀後選擇 A、B、C 和 D,或者可能決定用任意的 a₀、B₀、C₀、D₀來回答,而它們會安撫 verifier,並且與預先選擇的低階多項式的任何求值都不對應。所以,所有的密碼學都是爲了防止這種攻擊向量。(需要 prover 發送完整 A、B、C 和 D 的簡單解決方案,既不提供可擴展性,也不提供隱私性。)

有鑑於此,CI 宇宙可根據以下三種方式繪製出來:(i)用於強制 LDC 的密碼學原語,(ii)用這些原語構建的特定 LDC 解決方案以及(iii)這些選擇所允許的 Arithmetization。

二、 比較維度(Dimensions of Comparison)

2.1 密碼學假設

從 30000 英尺的高空來看,不同 CI 系統之間最大的理論區別因素,就在於它們的安全性需要對稱密碼學原語還是非對稱密碼學原語(見圖 1)。典型的對稱原語有 SHA2、Keccak (SHA3)或 Blake,我們假設它們是抗碰撞哈希(CRH)函數,它們是僞隨機的,行爲類似於隨機預言機。非對稱假設包括求解模素數、RSA 模或橢圓曲線羣的離散對數問題的困難性(hardness),RSA ring 乘法羣大小的計算困難,以及類似於「指數知識」假設,「自適應根」假設這樣的奇異變體問題。

多維度比較寒武紀爆炸式發展的零知識證明系統圖 1:密碼學假設家族樹

CI 系統之間的這種對稱 / 不對稱劃分,會帶來很多結果,其中包括:

A. 計算效率

今天在代碼 [4] 中實現的非對稱密碼學原語的安全性,要求在大型代數域上對 LDC 問題進行運算與求解:大型素數域和它們上面的大型橢圓曲線,其中每個域 / 組元素都有數百(bit)位長,或整數環中每個元素都有數千(bit)位長。

相比之下,僅依賴對稱假設的構造對包含 smooth[5] 子組的任何代數域(環域或有限域)進行算術運算並執行 LDC,包括非常小的二進制域和 2 個 smooth 素數域(64 位或更少),其中算術運算速度是很快的。

結論:對稱 CI 系統可以對任何字段進行算術運算,從而提高效率。

B. 後量子安全性

當一臺具有足夠大狀態(以量子位測量)的量子計算機出現時,當前在 CI-verse 中使用的所有非對稱密碼學原語將被有效地破壞。另一方面,對稱密碼學原語似乎是後量子安全的。

結論:只有對稱系統纔是合理的後量子安全系統。

多維度比較寒武紀爆炸式發展的零知識證明系統圖 2:密碼學假設及由它們支撐的經濟價值

C. 經得起考驗

Lindy 效應理論提出:

「一些不易腐爛的東西,比如一項技術或一個想法,其未來預期壽命與其當前年齡成正比。」

或者用通俗的話來說,舊東西要比新東西存活的時間要更長。在密碼學領域,這可以被翻譯成這樣一種說法,即依賴於較老的、經實戰測試的原語系統,要比那些輪胎被踢得較少的較新假設要更安全,也更容易存活下來(見圖 2)。從這個角度來看,非對稱密碼學假設的新變體,如未知階羣、一般羣模型和指數假設的知識,要比較舊的假設(如用於數字簽名、基於身份的加密和 SSH 初始化的更標準的 DLP 和 RSA 假設)更年輕。這些假設,相較於對稱假設(如存在抗碰撞的哈希算法)要更經不起未來的考驗,因爲後一種假設(甚至是特定的哈希函數)是用來保護計算機、網絡、互聯網和電子商務而存在的。

此外,這些假設之間有嚴格的數學層次。CRH 假設在這個層次中是主宰的,因爲如果這個假設被破壞(意味着沒有安全的密碼哈希函數被發現),那麼,特別是 RSA 和 DLP 假設也會被破壞,這些假設的前提是存在一個好的 CRH!

同樣,DLP 假設支配着指數知識(KoE)假設,因爲如果前者(DLP)假設不能成立,那麼後者(KoE)也不能成立。類似地,RSA 假設支配着未知階羣(GoUO)假設,因爲如果 RSA 被破壞,那麼 GoUO 也會被破壞。

結論:新的不對稱密碼學假設,對於金融基礎設施而言,會是具有更高風險的基礎;

D. 論證長度

以上各點都有利於對稱 CI 結構而不是非對稱 CI 結構。但在一個方面,非對稱結構會表現得更好。與之相關聯的通信複雜性(或論證長度)會小 1-3 個數量級(尼爾森定律 [6] )。知名的是, Groth16 SNARK 在 128 位安全級別的估計 level 上小於 200 字節,而今天存在的所有對稱結構需要幾十 KB 纔能有相同的安全級別。需要注意的是,並不是所有的非對稱結構都會有 200 字節那麼簡潔。Groth16 結構通過(i)消除了對可信設置的需求(透明性)和(ii)處理通用電路(Groth16 要求每個電路有一個可信設置)已經得到了改進。但這些較新的結構有更長的參數,其大小在半 KB (如 PLONK)到兩位數 KB 之間,接近對稱結構的論證長度。

結論:非對稱電路專用系統(Groth16)最短,它要比所有非對稱通用系統和所有對稱系統都要短。

然後重申下上面的要點:

  1. 對稱 CI 系統可以對任何字段進行算術運算,從而提高效率;
  2. 只有對稱系統纔是合理的後量子安全系統;
  3. 新的不對稱假設,對於金融基礎設施而言,會是具有更高風險的基礎;
  4. 非對稱電路專用系統(Groth16)最短,它要比所有非對稱通用系統和所有對稱系統都要短。

2.2 低階順應性(LDC)方案

實現低階順應性的主要方法有兩種:(i)隱藏查詢,(ii)承諾方案(見圖 3)。讓我們來討論一下差異。

多維度比較寒武紀爆炸式發展的零知識證明系統圖 3: 隱藏查詢 & 承諾方案

隱藏查詢(Hiding Queries)

這種方法是 Zcash 式 SNARKs,如 Pinocchio、libSNARK、Groth16 和建立在它們之上的系統,例如 Zcash 的 Sapling,以太坊的 Zokrates 等所使用的方法。爲了讓 prover 正確回答,我們使用同態加密隱藏或加密 x₀,並提供足夠的信息,以便 prover 能夠在 x₀上計算 A、B、C 和 D。

實際上,給 prover 的是一個 x₀冪的加密序列(即,x₀¹ , x₀², … x₀¹⁰⁰⁰的加密),這樣 prover 就可以計算任意階-1000 多項式,但最多隻能計算 1000 階多項式。粗略地說,系統是安全的,因爲 prover 不知道 x₀是什麼,而這個 x₀是隨機(預先)選擇的,因此如果 prover 試圖欺騙,那麼它們很有可能會暴露出來。這裏需要一個可信的預處理設置階段來採樣 x₀,並加密上面的冪序列(以及附加信息),從而得到至少與被證明的計算電路一樣大的證明密鑰(還有一個更短的驗證密鑰)。一旦設置完成並釋放了密鑰,每個證明都是一個單一的、簡潔的、非交互的知識論證(簡稱 SNARK)。請注意,這個系統確實需要某種形式的交互,以預處理階段的形式,因爲理論上的原因這是不可避免的。還請注意,該系統是不透明的,這意味着用於對 x₀進行採樣和加密的熵,不能僅僅是公開的隨機 coin,因爲任何知道 x₀的一方,都可以破壞該系統並證明其錯誤性。因此,在不暴露 x₀的情況下生成 x₀及其冪的加密,是構成潛在單點故障的一個安全問題。

承諾方案(Commitment Scheme)

這種方法要求 prover 通過向 verifier 發送一些加密構造的承諾消息來提交一組低階多項式(在上面的示例中是 A、B、C 和 D)。有了這個承諾,verifier 現在對隨機選擇的 x₀取樣並詢問 prover,現在 prover 用 a₀、b₀、c₀和 d₀,以及使 verifier 確信由 prover 揭示的四個值符合先前發送給 verifier 的承諾的附加密碼信息來回答。

這種方案是自然交互的,而且許多方案都是透明的(verifier 生成的所有消息都只是公開的隨機 coin)。透明性允許人們通過 Fiat-Shamir 啓發式(它將 SHA 2/3 這樣的僞隨機函數視爲提供「公共」隨機性的隨機預言機)將協議壓縮爲非交互式協議,或者使用其他隨機性公共源(如區塊頭)。最流行的透明承諾方案是通過 Merkle 樹,這種方法看似是後量子安全的,但會導致在許多對稱系統中出現較大的論證長度(因爲所有認證路徑都需要被揭示並附上每個 prover 的答案)。這是大多數 STARK (如 libSTARK 和簡潔 Aurora)以及簡潔證明系統(如 ZKBoo、Ligero、Aurora 和 Fractal)使用的方法(即使這些系統不滿足 STARK 的正式可擴展性定義)。

特別是,我們在 StarkWare 建造的 STARKs (比如我們即將部署的 StarkDEX alpha 版本和 StarkExchange)就屬於這一類。人們也可以使用非對稱密碼學原語來構造承諾方案,例如基於橢圓曲線組上離散對數問題的難度(這是 BulletProof 和 Halo 所採用的方法)以及未知階假設組(如 DARK 和 SuperSonic 採用的)。使用非對稱承諾方案具有前面提到的優點和缺點:證明較短,但計算時間較長,易受量子計算影響,具有較新(且較少研究)的假設,以及在某些情況下會有透明度的損失。

2.3 Arithmetization

密碼學假設和 LDC 方法的選擇,也以三種明顯的方式影響 arithmetization 可能性的範圍(見圖 4):

多維度比較寒武紀爆炸式發展的零知識證明系統圖 4:Arithmetization 效應

A. NP (電路) vs. NEXP (程序)

大多數已實現的 CI 系統將計算問題簡化爲算術電路,然後將其轉換爲一組約束(一般是下面我們將討論的 R1CS 約束)。此方法允許特定於電路的優化,但要求 verifier 或其信任的某個實體執行與正在驗證的計算(電路)一樣大的計算。對於 Zcash 的 Sapling 電路這樣的多用途電路來說,這種算法就足夠了。但是,像 libSTARK、簡潔 Aurora 和 StarkWare 正在構建的可擴展且透明(沒有可信設置)的系統而言,必須要使用簡潔的計算表示,這種表示類似於一般的計算機程序,並且其描述要比被驗證的計算要小指數級。現有的兩種實現:(i) libSTARK、genSTARK 以及 StaskWS 系統所使用代數中間表示(AIR)方法,以及(ii)簡潔 Aurora 的簡潔 R1CS,最好被描述爲通用計算機程序(與電路相反)的 arithmetization。這些簡潔表示足以捕捉非確定性指數時間(NEXP)的複雜類,它比由電路描述的非確定性多項式時間(NP)類更具有指數表現力,也更強大。

B. Alphabet 大小和類型

如上所述,所使用的密碼學假設在很大程度上也決定了哪些代數域可用作我們進行算術運算的 alphabet。例如,如果我們使用雙線性配對,那麼我們將用於 arithmetization 的 alphabet 是一個橢圓曲線點的循環組,這個組必須是大素數大小,這意味着我們需要對這個域進行算術運算。再舉一個例子,SuperSonic 系統(在其某個版本中)使用了 RSA 整數,在這種情況下,Alphabet 將是一個大的素數字段。相比之下,當使用 Merkle 樹時,Alphabet 的大小可以是任意的,允許在任何有限域上進行算術運算。這包括上面的例子,也包括任意素數域,小素數域的擴展,如二進制域。字段類型是很重要的,因爲字段越小,證明和驗證時間就越快。

C. R1CS vs. 一般多項式約束

Zcash 型 SNARKs 利用橢圓曲線上的雙線性配對來計算約束。雙線性配對的這種特殊使用 [7],限制了二次秩 1 約束系統(R1CS)的門運算。R1CS 的簡單性和普遍性使得許多其他系統對電路使用這種算術形式,儘管可以使用更普遍的約束形式,如任意秩二次型( arbitrary rank quadratic form)或更高階的約束。

三、 STARK vs. SNARK

下面我們來澄清一下 STARKs 和 SNARKs 之間的差異。這兩個術語都有具體的數學定義,某些結構可以實例化爲 STARKs 或 SNARKs,或者兩者兼而有之。不同的術語強調證明系統的不同性質。讓我們更詳細地檢查一下(參見圖 5)。

多維度比較寒武紀爆炸式發展的零知識證明系統圖 5:STARK vs. SNARK

STARK

這裏的 S 代表可擴展性,這意味着隨着批處理大小 n 的增加,證明時間大小與 n 是呈准線性關係的,同時驗證時間大小與 n 是呈多對數 [8] 關係的。

STARK 中的 T 代表透明性,這意味着所有 verifier 消息都是公共隨機 coin(沒有可信設置)。根據這個定義,如果有任何預處理設置,它必須簡潔(多對數),並且必須僅包括抽樣公共隨機 coin。

SNARK

這裏的 S 代表簡潔性,這意味着在 n (不要求準線性證明時間)中驗證時間大小是對數的,而 N 表示非交互,這意味着在預處理階段(可能是非透明的)之後,證明系統不能允許任何進一步的交互。注意,根據這個定義,允許非簡潔的可信設置階段,一般來說,系統不需要透明,但必須是非交互的(在完成預處理階段之後,這是不可避免的)。

縱觀 CI-verse (見圖 5),有人注意到它的一些成員是 STARKs,其它一些成員則是 SNARKs,有些則是兩者都是,而其它成員則都不是(例如,驗證時間大小與 n 的關係要比多對數要差的方案)。如果你對隱私(ZKP)應用是感興趣的,那麼 ZK-SNARKs 和 ZK-STARKs,甚至是那些不具備 STARK 可擴展性也沒有 SNARK 的的(弱)簡潔性的系統,都可以很好地工作,例如 Monero (門羅幣)使用的 Bulletproofs (防彈證明)就是這樣一個顯著的例子,其中驗證時間與電路大小成線性關係。而當談到代碼成熟度時, SNARKs 會擁有優勢,因爲有很多好的開源庫可供構建。但是,如果你對可擴展性應用感興趣,那麼我們會建議使用對稱 STARKs,因爲在編寫本文時,它們有最快的證明時間,並且保證驗證過程(或建立系統)的任何部分都不需要超過多對數處理時間。如果你想建立具有最小信任假設的系統,那麼,同樣,你也會想要使用對稱 STARK,因爲唯一需要的成分是一些 CRH 和公共隨機性的來源。

四、總結

多維度比較寒武紀爆炸式發展的零知識證明系統圖 6: 總結

我們很幸運地經歷了計算完整性密碼學證明系統宇宙的驚人寒武紀爆發,我們認爲系統和創新的擴散,將繼續以越來越快的速度進行。

此外,隨着未來新的見解及結構的出現,以上描述 CI 宇宙擴展及變化的嘗試很可能會過時。話雖如此,縱觀當今的 CI 領域,我們所看到的最大分界線是 (i) 需要非對稱密碼假設的系統,它們會導致證明時間更短,但證明成本更高,它們具有較新的假設,這些假設是易受量子計算影響的,其中有很多是不透明的,以及(ii)只依賴對稱假設的系統,這使得它們在計算上是高效、透明,且可能是後量子安全的,而根據 Lindy 效應來看,它們也可能是最經得起未來考驗的。

關於使用哪個證明系統的爭論遠未結束,但在 StarkWare 看來,我們會說:對於簡短論證,可以使用 Groth16/PLONK SNARKs,而對於其它的情況,則使用對稱 STARKs。

腳註

1. 術語 ZKP 經常被誤用來指代所有的 CI 系統,甚至是一些非正式 ZKP 系統。爲了避免這種混淆,我們使用了定義鬆散的術語「密碼學證明」和「計算完整性(CI)證明」;
2. 你可以在這裏讀到 STARK 算術化和低階順應性:
Arithmetization:博客 [1, 2];
3. 一元多項式的使用可以被廣泛地推廣到多元多項式和代數幾何碼,但是爲了簡單起見,我們堅持使用最簡單的一元情況;
[4]. 我們特別將基於格的構造排除在討論之外,因爲它們還沒有代碼基礎。這種結構是非對稱的,而且似乎也是後量子安全的,並且通常使用小(素數)域。
[5]. 如果一個域包含一個子羣(乘法或加法),且其所有素因子都不超過 k,則該域是 k-smooth 的。例如,所有的二元域都是 2-smooth,因此 q 大小的域 q-1 可以被 2 的大冪(power)除;
[6]. 尼爾森的互聯網帶寬定律指出,用戶帶寬每年會增長 50%,該定律適用於 1983 年至 2019 年的數據;
[7]. 其他系統(如 PLONK)僅使用配對來獲得(多項式)承諾方案案,而不用於算術化 arithmetization。在這種情況下,算術化可能導致任何低階約束;
[8]. 形式上,「n 中的準線性」表示 O(n logᴼ⁽¹⁾ n) ,「n 中的多對數」表示爲 logᴼ⁽¹⁾ n。

來源鏈接:nakamoto.com