密碼學證明的寒武紀大爆發
https://nakamoto.com/cambrian-explosion-of-crypto-proofs/ 本文經 Eli Ben-Sasson 授權，由 Taipei Ethereum Meetup 成員 Jerry Ho 與 Bill Wu 翻譯。
譯者註：本文成文於 2020 年初，已有時日；然其提供之文獻分類與回顧，時至今日對初入本領域之學習者亦相當有價值，故譯之以饗中文圈之讀者。
這篇文章的目標客群是有密碼學背景的人。本文將回顧擴張中的密碼學證明系統，以及對稱式 STARKs 在其中扮演的角色。內文由 2019 年 11 月在舊金山的演講加筆改寫而成。
一、介紹
在 35 億年前，地球上的生命還是由單細胞生物組成的原始湯。接著在對地質學而言短暫的一瞬間，是所謂寒武紀大爆發的期間，現存於世的幾乎所有的動物「門」出現了。
同樣地，我們正在經歷計算完整性（CI, Computational Integrity）密碼學證明領域的寒武紀大爆發。CI 是零知識證明的一個子集。在幾年前，每年只會出現大概一到三個新證明系統。這個速率在近年快速上升，以至於現在我們每個月，甚至是每週，都能看到相當於過去一整年的成果。在整個 2019 年，我們已經看到了許多新的證明構建方式出現，比如 Libra、Sonic、SuperSonic、PLONK、SLONK、Halo、Marlin、Fractal、Spartan、Succinct Aurora、還有實作的系統像是OpenZKP、Hodor、GenSTARK。 對了，在我寫這篇文章的墨水還沒乾之前，RedShift 和 AirAssembly 也出現了。
這些創新雖讓人感到不可思議，但我們該如何理解呢？本文的目的是找出所有已實作完成的 CI 系統的共同點，並挑出那些使其與眾不同的相異點進行討論。
請注意，要看懂這篇文章用到的技術會有點難，因為我在行文的時候會假設你有一些密碼學的背景知識！儘管如此，我還是認為本文對非密碼學家的人們來說會很有價值，即便只是簡單地囫圇吞棗，讀者們還是可以瞭解這個領域使用的專有名詞有哪些。讀者可以預期本文中的描述會儘量簡短，且行文會故意寫得在數學上不精確，以便理解。本文的另一個目的，是解釋我們的公司 StarkWare 為什麼要把科學、工程、和產品精力都放在 CI 證明系統的一個子集上 — — 我們在下文將其稱為對稱式 STARKs。
共同祖先
CI 證明系統可以協助解決分散式區塊鏈的兩個核心問題：隱私和擴展性。零知識證明（ZKPs ¹）會隱藏計算的某些輸入，在不損害計算完整性的前提下同時保障了隱私。一個可簡潔驗證（succinctly verifiable）的 CI 系統可以指數級地壓縮計算量，這樣就不必花過多的資源來驗證計算完整性，因而使系統能夠有足夠的擴展空間。
所有已經被實作的 CI 系統都有兩個共通點：他們都會使用算術化（Arithmetization）這個技巧，並且在密碼學上都確保使用者選用的多項式會是低次方（低複雜度）的多項式（LDC, Low-Degree Compliance）²。
算術化（Arithmetization）是證明演算法用來簡化計算陳述（Computational Statements）的一種方式。我們來看一個例子：
「我知道一把私鑰，可以讓我花用某筆資訊被隱藏的 Zcash 交易。」
然後把這個句子轉換成代數陳述（Algebraic Statements），其中包含了一組次方有界的（bounded-degree）多項式：
「我知道四個多項式：
每個多項式的最高次方項都小於 1000，且下列等式成立。」
LDC 此一特性，在密碼學系統建構中能確保證明者會選擇低次方的多項式³，證明者就可以在在驗證者要求的隨機點上驗算／代入（evaluate）這些多項式。 在上面的例子中（證明者／驗證者（Prover/Verifier） 的行為對比，之後我們會一直提到），一個好的 LDC 架構必須要確定證明者的行為正確：當驗證者以 x₀ 向證明者查詢的時候，證明者會正確地使用輸入 x₀ 來產生 a₀, b₀, c₀, d₀ 作為答案。 這裡麻煩的地方是：證明者可以在看到 x₀ 是多少之後才選擇對應的 A, B, C, D，甚至可以任意產生一組 a₀, b₀, c₀, d₀ 來當作答案，這些任意的答案在驗證者來看會是有效的，而且和那些預先挑好的低次方多項式沒有任何關係，證明者甚至不用跑計算。 你現在知道了，所有的密碼學構建都是為了防止這種類型的攻擊。（你可以說有 Trivial 的解，就是要求證明者送出完整的 A, B, C, D。當然這種解法沒有擴展性，也沒有隱私可言。）
考慮到這一點，我們根據以下三點來分類 CI： 一、用了哪些密碼學原語（Primitive）來達成 LDC。 二、用上述密碼學原語構建的特定 LDC 系統。 三、在以上兩點的假設下，該系統可以使用哪些算術化技巧。
二、在不同方向上比較
1. 密碼學假設
拉大尺度來看，理論上不同 CI 系統之間最大的差異，是安全性奠基在對稱性原語上還是非對稱性原語上（圖 1）。 典型的對稱性原語包含了 SHA2、Keccak(SHA3)、Blake。在系統中，我們會假設這些雜湊函數是抗碰撞的雜湊函數（CRH, Collision Resistant Hash）、是偽隨機函數，會表現得像是隨機預言機（Random oracle）。 在非對稱性原語上，我們會有的假設包含像是特定離散對數問題的難度（mod prime、RSA modulus、 或者是橢圓曲線用到的群）、計算 RSA 環乘法群大小的難度、或是同類型問題更少見的變體，像是「指數知識」假設（KEA, Knowledge of Exponent Assumption）、「可適應根」假設（Adaptive root assumption）等等。
圖 1：密碼學假設家族圖譜
CI 系統之間的這種對稱性／不對稱性差異帶來了許多後果：
A. 計算效率
對非對稱性密碼學原語而言，目前已經有實作的系統⁴必須在一個很大的代數域上解決 LDC 問題。包含了：
- 大質數域以及基於此的大橢圓曲線，這裡的大代表其中的體和群的元素都有幾百位元那麼長。
- 或者是整數環，其中的元素有幾千位元那麼長。
相比之下，基於對稱性假設的構建方法可以很好的算術化，並在任意的代數域上（環或有限體）解決 LDC 問題，這些環或有限體可以包含平滑⁵（Smooth）的子群，像是很小的二元體（Binary field）或是 2-smooth prime fields (< 64bits)。在這些環或有限體中的代數運算就很快。
懶人包：對稱性的 CI 系統可以在任何體上進行算術化，使其效率較高。
B. 後量子安全性
如果有一臺擁有足夠多量子態的量子電腦出現的話，這臺電腦可以破解目前安全性奠基於非對稱性原語的所有 CI 系統。相較之下，對稱性原語看起來很可能可以保持後量子安全（也許需要更長的種子和更高的安全級別（bits of security））。
懶人包：只有對稱性系統才有機會達成後量子安全。
圖 2：密碼學假設及承載於其上系統的經濟價值
C. 居安思危，在可見的未來是否有效
林迪效應指出：「對於一些不會自然消亡的東西，比如一種技術、一個想法，它們的預期壽命和它們目前已經存在的時間成正比。」翻譯成人話就是，舊的東西既然存在比較久，就代表他們比新的東西更有機會存活。在密碼學領域，這代表使用舊的、經過大量使用也沒有出現問題的密碼學原語系統會比較安全，更經得起時間考驗，因為他們被嘗試破解的次數一定比新的系統要多。 從這個角度來看，新的非對稱式假設的變體，像是未知階的群（GoUO, Groups of Unknown Order）、通用群模型（GGM, Generic Group Model）、或是指數知識假設，都還太新了，其上承載的經濟體量也比老的系統要來得少得多。 老的系統像是：標準的離散對數問題和 RSA 假設，被用來構建數位簽章、身份基礎加密（IBE, Identity-Based Encryption）、SSH 初始化設定等。 這些非對稱性原語比對稱性原語更禁不起時間的考驗（像是抗碰撞雜湊演算法，或是更特定的雜湊演算法），因為比起非對稱性原語，這些對稱性原語的安全假設是現在我們用來保護電腦、網路、網際網路和電子商務的基礎中的基礎。
更進一步的說，這些假設之間存在著嚴格的數學層次。抗碰撞雜湊函數在這個層次中是最基礎的。如果這個假設被打破（意味著這世界上沒有安全的密碼雜湊函數），那就代表 RSA 和離散對數問題的安全假設也會被打破，因為這兩者的安全假設，都需要這世界上存在一個安全的抗碰撞雜湊函數才會成立！ 同樣地，離散對數問題的假設是指數知識（KoE）假設的基礎。如果前者（DLP）假設不成立，那麽後者（KoE）假設也不成立。 最後，RSA 假設是未知階群（GoUO）假設的基礎。如果 RSA 安全不成立，那麽 GoUO 也不成立。
懶人包：如果要建立金融基礎建設，新的不對稱密碼學原語會帶來更大的風險。
D.陳述長度（Argument Length）
行文至此，上述三點都告訴我們對稱 CI 系統會表現得比非對稱 CI 系統更好。但，非對稱系統在某個領域其實可以表現得比對稱系統更好。在通訊複雜度上（或是陳述長度上），非對稱系統會比對稱系統短上 1~3 個數量級（因此尼爾森定律⁶不再成立）。 知名的一個例子是 Groth16 SNARK，只要花 200 bytes 的證明大小，就能達到約 128 bits 長度的安全性。今日所有的對稱性系統都需要 KB 等級的證明大小才能達成相同的安全性。應該注意的是，並非所有的非對稱系統都像 Groth16 一樣簡潔，只需要 200 bytes。 最近的建構改善了 Groth16 的一些特性：
- 不再需要可信設置（Trusted setup），達成了透明性（Transparency）
- 可以使用通用電路（Groth16 要為每個電路都跑一次可信設置） 但是這些新建構的陳述會更長，大小介於 0.5 KB（如 PLONK）到數十 KB 之間，已經快和對稱系統的陳述長度一樣長了。
懶人包：非對稱，且非通用電路系統（Groth16）的陳述是最短的，比所有的非對稱通用系統和所有的對稱系統都短。
重申以上幾點：
- 對稱性的 CI 系統可以在任何體上進行算術化，使其效率較高。
- 只有對稱性系統才有機會達成後量子安全。
- 如果要建立金融基礎建設，新的不對稱密碼學原語會帶來更大的風險。
- 非對稱，且非通用電路系統（Groth16）的陳述是最短的，比所有的非對稱通用系統和所有的對稱系統都短。
2. LDC 機制
有兩種方法能讓系統擁有 LDC 的特性：(1) 隱藏的查詢（hiding queries）、(2) 密碼學承諾（commitment scheme）（參見圖 3）。讓我們來檢視一下相異之處：
圖 3：隱藏的查詢和密碼學承諾
隱藏的查詢
這種方法（此處有正式定義）是 Zcash 風格的 SNARKs 使用的方法，比如 Pinocchio、libSNARK、Groth16，以及建立在它們之上的系統，像是 Zcash 的 Sapling、Ethereum 的 Zokrates 等等。 為了讓證明者能夠正確地回應查詢，我們使用同態加密來隱藏、加密 x₀，提供足夠的訊息，讓證明者能夠正確的在 x₀ 上驗算／代入 A, B, C, D。實際上，證明者收到的是一串 x₀ 次方項的加密序列（加密過的 x₀, x₀², …, x₀¹⁰⁰⁰)，這樣證明者可以算出任意 1000 次方多項式的值，不過最高次項超過 1000 就不行了。 粗略地說，系統是安全的，因為證明者不會知道 x₀ 是什麽，而且這個 x₀ 是隨機（預先）選擇的。如果證明者試圖造假證明，就有很高的可能性騙不過去。這種方法需要先對 x₀ 進行可信前處理採樣設置（trusted pre-processing setup phase），加密上面提到的次方項序列（還有所需的額外資訊），這代表產生出來的證明密鑰（proving key）最小的大小也會跟證明電路本身一樣大（當然驗證密鑰（verification key）會小一點）。 一旦設置完成，產生了密鑰，每個證明就可以被看作為一個簡潔（Succinct）、無需互動（Non-interactive）的知識陳述（ARgument of Knowledge），簡稱為 SNARK。請注意，這個系統確實在前處理階段的時候還是需要某種形式的互動，因為這在理論上是一定要做的程序。除此之外，還要注意這個系統不是透明的（Not Transparent），這代表你不能簡單地用大家都知道（也就是證明者也能知道）的隨機產生方式來當作熵（Entropy）用以採樣和加密 x₀ — — 因為這樣會讓任何能得知 x₀ 的人都能夠破壞本系統，並產生錯的證明騙過眾人。這代表要產生 x₀ 的次方加密序列且不洩漏 x₀ 會是安全上的一個挑戰，這個產生過程有可能成為系統的弱點，讓整個系統崩潰。
密碼學承諾
這種方法需要證明者用密碼學的方式送出承諾給驗證者，承諾的內容是一組低次方的多項式（如上文中所提到的 A, B, C, D）。 有了這個密碼學承諾，驗證者現在可以抽樣，用一個隨機選擇的 x₀ 來向證明者查詢，證明者也可以正確的傳回 a₀, b₀, c₀, d₀，以及額外的密碼學資訊給驗證者，這樣驗證者就可以確定上面四個證明者送出的值符合一開始密碼學承諾中提到的規則。 這樣的方法當然是需要互動的，而且很大一部分也有透明性（代表驗證者產生訊息的方法，使用的是大家都知道的隨機亂數產生方式）。透明性讓我們可以方便的把方法變成不需互動的，使用 Fiat-Shamir heuristic 即可達成。（把 SHA2/3 這樣的偽隨機函數當成隨機預言機（random oracle），「公開的」亂數來源就有著落了。或者用其他公開資訊當亂數來源也可以，像是區塊標頭（Block Header））。這就是大多數 STARKs 如 libSTARK、succinct Aurora，還有一些簡潔證明系統像是 ZKBoo、Ligero、Aurora、Fractal 所使用的方法（儘管這些系統不符合 STARK 系統正式上來說應有的擴展性的定義）。舉例來說，我們在 StarkWare 正在開發的技術（像是 StarkDEX alpha 和 StarkExchange）就屬於這一類。 非對稱的密碼學原語也可以被用來架構密碼學承諾方法，例如：
- 基於橢圓曲線群上離散對數問題的密碼學承諾方案（這是 BulletProofs 和 Halo 用的方法）
- 未知階群假設（DARK 和 SuperSonic 用的方法)
使用非對稱密碼學承諾方法當然是一把雙面刃，特性我們之前都提過了：證明更短，但計算時間更長、後量子時代可能不安全、安全假設太新了（沒什麼人研究過），在特定的情況下還會失去透明性。
3. 算術化
隨著系統選用不同的密碼學假設與不同的 LDC 方法，能被使用的算術化技巧也會受限。主要體現在三種明顯的影響上（見圖 4）：
圖 4：算術化的效益
A. NP（電路） vs. NEXP（程式）
大多數實作好的 CI 系統會把需要計算的問題轉化為算術電路，然後將其轉化為一組約束（Constraints，通常是 R1CS 約束，下文會詳細討論）。這種方法雖然可以針對特定電路做最佳化，但是需要驗證者（或者驗證者信任的某一方）做額外的運算，其運算量會和需要被驗證的電路一樣大。對 Zcash 的 Sapling 電路這種多用途電路，或許此法可行。然而，對透明（無需可信設置）且有擴展性的系統而言，像是 libSTARK、succinct Aurora 或是 StarkWare 正在構建的系統，必須使用簡潔的運算陳述，可以把它當成一般的電腦程式，且可被轉成比正在驗證的電腦程式還要指數級精簡的描述。 現在（2020.02）有兩種實作方法：
- libSTARK、genSTARK 和 StarkWare 系統使用的代數中繼表示形式（AIRs, Algebraic Intermediate Representations ）
- succinct Aurora 使用的簡潔 R1CS
與其說是電路，這兩種方法不如說是一般電腦程式的算術化成果。這種簡潔的表示形式能處理 NEXP 問題（nondeterministic exponential time），比算數電路描述能處理的 NP 問題（nondeterministic polynomial time）更強大。
B. 字母大小（Alphabet size）和類型
如上所述，我們所用的密碼學假設，在很大程度上決定了哪些代數域會被當作我們用來算數化的字母。如果我們使用雙線性配對（Bilinear pairing），那麽我們算術化的對象字母就是是一個橢圓曲線上的點的循環群，而且這個群的大小會是一個大質數，這就是我們需要算數化的體。再舉一個例子，SuperSonic 系統（的其中一個版本）使用的是 RSA 整數，所以我們要處理的字母就是一個大的質數體。相比之下，如果我們的密碼學假設是 Merkle tree 的話，字母大小就會是任意的，可以進行任何有限域上的算數化。這包括上面的所有例子，同時也包括任意的質數體，小質數體的延伸（像是二元體）。體的類型很重要，因為小的體才能讓證明和驗證的時間變快。
C. R1CS vs. 一般多項式約束
Zcash 風格的 SNARKs 利用橢圓曲線上的雙線性配對來算數化電路中的約束條件。這種特殊用法⁷的雙線性配對，能夠把算數化限制成 R1CS 邏輯閘的形式（Rank-1 Constraint Systems）。R1CS 的簡單性和普遍性讓很多系統都使用這種形式的算術化來處理電路，甚至可以選擇使用更一般的約束形式，像是有著任意秩的二次方程式（arbitrary rank quadratic forms），或有更高的階（degree）的約束。
三、STARK vs. SNARK
現在剛好可以來解釋 STARKs 和 SNARKs 之間的關係。這兩個術語都有具體的數學定義，某些特定的構造方式可以被做成 STARKs，可以被做成 SNARKs，或是同時屬於兩者。這兩個不同的術語強調了證明系統中的不同性質。讓我們來詳細檢視這些細節（參見圖 5）。
圖 5：STARK vs. SNARK
STARK
這裡的 S 代表可擴展，隨著要驗證的資料量 n 增加，產生證明所需的時間會準線性（quasi-linearly）地隨著 n 增加，驗證所需的時間也會多對數⁸地（poly-logarithmically）隨著 n 增加。STARK 裡面的 T 代表透明，這意味著所有驗證者的訊息都和公開的隨機數產生方式沒有兩樣（無需可信設置）。根據這個定義，如果 STARKs 中需要任何可信前處理設置，它必須是簡潔的（多對數的），且取樣方式必須只是單純的公開隨機數產生。
SNARK
這裡的 S 代表簡潔，意味著驗證時間會多對數地隨著 n 增加（但證明時間不會到準線性的程度）。N 代表無需互動，這代表在前處理階段完成之後（此階段可能是不透明的），證明系統不需要任何其他的互動。請注意，根據這個定義，可信設置是可以存在的，同時可以是不簡潔的。一般來說，這樣的系統不一定要透明，但一定要無需互動（在完成前處理階段之後就無需互動。前處理階段是必須的）。
讓我們來看目前的 CI 系統（見圖 5），我們可以注意到其中一些系統是 STARKs，一些系統是 SNARKs，有些系統同時屬於兩者，有些系統不屬於任何一者（像是那些驗證時間比隨 n 呈多對數增加還要來得慢的系統）。如果你對隱私（ZKP）應用有興趣，那不管是 ZK-SNARKs、ZK-STARKs、那些不像 STARK 一樣有擴展性的系統、還是那些比較不簡潔的 SNARK 系統，其實都可以滿足隱私應用的需求；像是 Monero 使用的 Bulletproofs 就是一個好例子。其驗證時間與電路大小成線性關係。如果你在意的是現有環境的成熟度，SNARKs 較佔優勢，因為已經有不少好的開源專案供你使用。如果你在意的是具有擴展性的應用程式（你的應用所需的證明量會不斷增加），那我們會建議你用對稱式 STARKs。在編寫本文時，STARKs 擁有最快的證明時間，並且可以確保驗證過程（或設置系統）的任何部分都不會超過多對數的處理時間。如果你想建立一個信賴／安全假設最少的系統，你還是應該使用對稱式 STARKs，因為這裡唯一的假設只包含了這世界上存在抗碰撞雜湊函數，還有一些公開可得的亂數產生來源。
四、總結
圖 6：總結
我們很幸運，能夠經歷 CI 證明系統奇妙的寒武紀大爆發，我們也相信這些系統會更加擴張，創新也會以不斷增長的速度繼續下去。此外，雖然本文試圖描述與分類不斷擴張和演化中的 CI 證明系統，這篇文章很可能在未來變得沒有價值，因為新的想法和構建會源源不絕的出現。儘管如此，在調查現在的 CI 證明系統之後，分類這些 CI 系統最明顯的幾點包含：
- 需要非對稱式假設的系統 一 雖然證明會更短，但證明所費成本更高。新出現的假設不保證後量子安全，而且許多系統是不透明的。
- 只需要對稱式假設的系統 一 它們計算效率較高、透明、後量子安全、而且可以挺過時間淬鍊（林迪效應)。
短時間之內，哪個陳述系統比較好用的討論還會持續下去。身為 StarkWare 的成員，我們會說：如果想要簡短的陳述，請使用 Groth16/PLONK SNARKs。除此之外的其他時候，用對稱式 STARKs 就對了。
Eli Ben-Sasson, StarkWare
特別感謝 Justin Drake 對文章早期草稿提出意見。
腳註
¹ ZKP 一詞經常被誤用來指所有的 CI 系統，有時候還被誤用來指那些根本不是 ZKP 的系統。為了避免這種混淆，我們用了兩個不嚴謹定義的術語來分別：「密碼學證明」、「計算完整性（CI）證明」。
² 這兩個連結可以讓你更瞭解 STARK 的算數化和 LDC：
- 算數化：StarkWare 部落格文章一、StarkWare 部落格文章二、上課投影片、還有上課錄影
- LDC：StarkWare 部落格文章（以 STARKs 為例）
³ 單變量多項式可以廣泛推廣，像是推廣到多變量多項式（multivariate polynomials）和代數幾何碼（algebraic geometry codes）。為了簡單起見，我們還是使用最簡單的單變量來講解。
⁴ 我們在討論中特別排除了網格建構（Lattice-based）的系統，因為它們還沒有被實作出來。這種建構是不對稱的，而且很有可能保持後量子安全，通常使用的是小（質數）體。
⁵ A field is k-smooth if it contains a subgroup (multiplicative or additive) of size all of whose prime divisors are at most k. For instance, all binary fields are 2-smooth, and so fields of size q such the q-1 is divisible by a large power of 2.（譯註：需要看懂本腳註的讀者不會需要中文翻譯）
⁶ 尼爾森的網際網路頻寬定律指出了使用者頻寬每年會增長 50%。這個定律在 1983 年到 2019 年間都適用。
⁷ 其他系統（如 PLONK）只是把配對拿來構建（多項式）密碼學承諾，而不是把它拿來做算術化。在這種情況下，算術化可能會導致出現低次方的約束。
⁸ 更完整地說，「對 n 呈準線性」（quasi-linear in n）指 O(n logᴼ⁽¹⁾ n)，而「對 n 呈多對數」（poly-logarithmic in n）指 logᴼ⁽¹⁾ n。
作者：Eli Ben-Sasson Starkware 的創始人之一，首席科學家，董事會主席。Zcash 的創始科學家，以色列 Technion 大學的資工系教授。ZK-STARK & SNARK 研究者。
