Binary GKR：刷新Keccak證明速度記錄的全新零知識證明系統

BTCC / BTCC Square / Odaily /

Author:

Odaily

Published:

2025-05-23 12:50:11

原文作者：Weikeng Chen

在以太坊虛擬機（EVM）中，Keccak 雜湊函數廣泛用於狀態樹（Merkle Patricia Trees）的建構與驗證，佔據了零知識證明中的主要計算開銷。如何有效率地對Keccak 進行證明，是零知識證明領域長期未解的技術難題。

為因應這項挑戰，POLyhedra 團隊推出了Binary GKR——專為Keccak 及其他二進位作業設計的高效能證明系統。

核心進展：對Keccak 的證明速度提升5.7 倍

BinARy GKR 實現了迄今為止最快的Keccak 零知識證明性能，相比現有二進制證明系統最優解FRI-Binius 提速約5.7 倍。這項突破不僅在理論上具有重要意義，也為實際應用開啟了新的可能性。

應用前景：zkEVM 的“通用加速側車”

我們認為，Binary GKR 可作為多種zkEVM 架構中的“通用加速側車”，高效處理Ethereum 狀態樹中大量的Keccak 運算，從而顯著降低證明成本、提升系統吞吐與響應速度。

Polyhedra 將持續推動Binary GKR 的產品化與開源進程，賦能以太坊及更廣泛生態中的zk 架構升級。

Keccak：零知識以太坊的“聖杯”

以太坊正逐步向零知識證明原生的LAYER-1 演進。由21 個團隊參與、涵蓋22 種ZK(E)VM 實現的Ethproofs計劃，正在嘗試對以太坊歷史區塊進行完整證明，邁出關鍵一步。

在ETHproofs 官網上可以即時查看多個團隊的進度：ZkCloud、Succinct、Snarkify 和ZKM 等項目，已開始持續提交最新區塊的ZK 證明。這趨勢的最終目標，是將以太坊打造為以零知識證明驅動的執行層，而共識層僅需完成交易清單的提案等輕量任務。

zkEVM 架構面臨的最大挑戰：Keccak 的證明效率瓶頸

目前已有多個以太坊相容zkRollup 專案（如Polygon、Taiko、Scroll）嘗試實現zkEVM。然而，傳統EVM 中一些在CPU 上有效率的操作，在零知識證明系統中卻代價高昂。其中最主要的效能瓶頸，正是Keccak 雜湊函數。

Keccak 被廣泛用於建構以太坊的Merkle Patricia Tree，以哈希形式記錄全鏈狀態。然而Keccak 的底層運算是基於位元運算（bit-level oPErations），這與大多數ZK 系統使用的素數域（prime field）運算模型並不相容，導致效能顯著下降。

為了幫助理解Keccak 雜湊函數為何本質上是「位元運算」的集合，我們在此簡要展示其中的五個核心操作：θ（THETA）、ρ（rho）、π（pi）、χ（chi）和ι（iota）。這些運算應用於一個5 × 5 的矩陣結構，每個單元格為一個64 位元整數，我們稱之為「字」（word）。整個矩陣共包含5 行5 列。

θ（Theta）：先計算每一列的奇偶校驗值（ parity ），然後將該奇偶值與左側相鄰列進行異或運算（exclusive-or）；同時，對右側相鄰列執行一次左旋轉（rotate-left）後，再進行異或。這個過程涉及基本的二進位操作，如“異或”與“左旋”。
ρ（Rho）：對矩陣中的每一個字按位左旋轉，每個字的旋轉距離不同，但均為預設的固定值。此步驟完全由「左旋」操作構成。
π（Pi）：依照固定模式重新排列矩陣中的字。由於該過程僅為位置置換，在零知識證明中通常被視為「零成本操作」。
χ（Chi）：沿著每一行進行位元組合操作，每個字會與該行中其左右相鄰的兩個字進行組合。此操作包括「異或」、「取反」（negation）與「與」（and）。
ι（Iota）：將矩陣中第一個字與一個固定常數進行異或操作，僅涉及「異或」運算。

在零知識證明中實現Keccak 的主要挑戰，正是如何有效表示這些位元級操作，尤其是在每個操作都作用於64 位元整數的前提下。這也是我們稱之為Keccak-1600 的原因──因為每一輪的狀態空間為5 × 5 × 64 = 1600 位元。而這樣的操作過程需重複24 輪。

接下來，我們將簡要回顧一些先前實現Keccak 的嘗試。

嘗試一：基於Groth 16 或其他R 1 CS 的證明系統

目前最流行且最直接的方式，是使用Groth 16 或其他R 1 CS（Rank-1 Constraint System）證明系統來實現Keccak。為了在Groth 16 中表達位元運算，我們將每個位元表示為0 或1 ，並透過算術關係來模擬下列邏輯運算：

異或（exclusive-or）：使用表達式a + b − 2 ab
取反（negation）：使用表達式1 − a（通常可無成本地整合進其他限制中）
與（and）：使用表達式a × b

而像是「左旋」（rotate-left）和其他置換操作在ZK 環境中通常被視為無成本操作，不需要額外約束。

根據計算，Keccak 每一輪的約束數量如下：

θ 操作約產生4480 個約束
ρ 與π 操作為“零成本”
χ 操作約產生3200 個約束
ι 操作約產生64 個約束

因此完整的Keccak-1600 （共24 輪）將在Groth 16 中產生185, 856 個約束。

參考Ingonyama 的ICICLE 庫中的數據，在一塊Nvidia 4090 GPU 上產生一個Keccak 的ZK 證明大約需要30-40 毫秒，在CPU 上則約為450 毫秒。如果需要證明8192 次Keccak 運算，GPU 至少需要250 至300 秒，而CPU 可能需要接近一小時。

嘗試二：基於查找表的證明系統（Lookup-based Proof Systems）

一種更現代的最佳化方案是對資料進行批次處理（例如每4 位元或8 位元一組），並透過尋找表來執行所有的位元運算。換句話說，將每個64 位元整數切分成若干小塊（例如8 個8 位元chunk），再使用查找表完成邏輯運算。

具體包括以下幾種查找表：

異或操作查找表（XOR）：一個大小為2 ⁸ × 2 ⁸ 的查找表，用於計算兩個8 位元chunk 的異或值。這樣可以用一個約束完成8 位元異或，而不是傳統的8 個限制。

與操作查找表（AND）：同樣是一個2 ⁸ × 2 ⁸ 的查找表，用於兩個8 位元chunk 的位元與操作，節省限制的效果與XOR 類似。

左旋操作查找表（Rotate-left）：為了處理Keccak 中頻繁出現的rotate-left 操作，引入了多個查找表。具體為：七個大小為2 ⁸ 的查找表，分別對應旋轉距離為8 k+ 1、 8 k+ 2 等（其中k 為非負整數）。相較於嘗試一（Attempt 1）完全不處理旋轉操作，這種方式會引入額外開銷－每輪大約增加192 個約束。不過與其他部分相比，這個開銷仍然相對較小。

為了實現這種系統，我們不再使用Groth 16 ，而是更適合採用Stwo、Plonky 3 等小域證明系統，這類系統對查找表支援更加完善。在這個方案下，每次完整的Keccak 運算大約需要27, 264 個約束，並結合查找表的調用，可大幅減少整體約束數，相較Groth 16 顯著優化。

然而，這種優化在性能上並非絕對佔優勢。因為查找表本身的呼叫和管理也會帶來開銷，若處理不當，可能會抵銷約束數量減少所帶來的優勢。因此，其實際運行效率在某些場景下可能不如基於Groth 16 的實作。

試試三：Binius

鑑於查找表（lookup）或定制閘電路（custOMized gates）所帶來的加速在實際中可能不如預期，原因在於查找本身的開銷可能抵消其帶來的約束優化效果，因此我們需探索其他路徑來進一步提升Keccak 的證明效率。

這正是Keccak 被譽為「零知識聖杯」的原因所在。與之相比，早期的雜湊函數如SHA-256 和Blake 2/3 ，雖然也依賴異或（XOR）、與（AND）等位元運算，但其最大效能瓶頸源自於整數加法。而整數加法在證明系統中通常會透過將其拆解為多個4-bit 區塊來優化，從而大幅提升效能。但Keccak 並不涉及任何整數加法，因此這些最佳化策略在此失效。

目前最前沿的解決方案是Binius。此系統的核心思想是：既然Keccak 完全由位元運算組成，我們便可以使用以位為基本單位的證明系統來實現。這便是Binius 的突破之處。

在Binius 中，Keccak 被表示為在有限域𝐹₂（即二元域）上的運算。由於XOR 本質上就是𝐹₂ 中的加法，因此其相關開銷幾乎完全消除。整體過程被建構為一系列多項式運算，位元旋轉操作也可在位元處理模型中輕鬆實現。證明成本主要集中於χ 步中出現的AND 閘。

Binius 的基準測試顯示，在證明8192 次Keccak 運算時，僅需約12.35 秒，遠優於Groth 16 （嘗試一）和查找表方法（嘗試二）。

Binius 是終點嗎？其實並非如此。我們發現通過去除Keccak 證明中的某些冗餘部分，還有可能進一步提升約五倍的性能，超過目前的Binius 實現。

Polyhedra 推出Binary GKR：專為Keccak 優化的二進位證明系統

Polyhedra 團隊正在建立全新的證明系統－ Binary GKR（詳見： ePrint 2025/717 ），這是一個專門針對二元操作高效證明的框架，特別適用於像Keccak 這樣以位元運算為核心的函數。 Binary GKR 的核心優勢來自以下三個關鍵技術創新：

1. 基於GKR 協議，優化重複計算

我們在Binary GKR 的設計中選擇以GKR 協定（Goldwasser–Kalai–Rothblum）為基礎，原因在於它能夠有效降低處理重複性計算所帶來的冗餘開銷。

在典型的zkevm 場景中，Keccak 往往以"外掛證明器（sidecar prover）" 的角色出現，用於批量處理zkEVM 所委託的大量Keccak 運算任務。因此，我們面向的電路結構天然具有大量的重複模式，例如： 8192 次Keccak 調用是一種常見規模。

更重要的是，Keccak 演算法本身就極具重複性：

它在5 × 5 的狀態矩陣上反覆執行相似的布林運算；
整個過程包含24 輪幾乎一致的步驟；
各輪之間結構相同，僅輸入狀態不同。

這樣的特性，使得Keccak 成為GKR 協議的「天然適配對象」：

Verifier 成本較低，適合高頻驗證場景；
Prover 可充分利用結構重複性，重複使用運算路徑，大幅簡化證明開銷；
相較於傳統通用證明系統，在批量Keccak 場景中具備顯著效能優勢。

2. 基於二進位域的多項式承諾

我們採用了一種基於線性碼的多項式承諾方案，該方案直接在二進位域上運行。正如我們之前提到的，使用原生的二進位表示，使我們能夠「免費」獲得諸如異或（XOR）這樣的操作。此外，與Binius 的方法類似，基於二進位域的多項式承諾避免了使用更大數域所帶來的冗餘，這使得系統在效能和效率上都得到了顯著提升。

3. 用於二進位操作的預計算表

Binary GKR 論文中的關鍵創新在於：透過充分利用電路結構的高稀疏性，顯著提升了GKR 協議的證明效率。即使在同時處理多個位元的情況下，這種稀疏性仍得以保留。們的做法是將多個位元「打包」進GKR 協議中的多項式中（注意：這些是中間多項式，無需進行承諾），然後直接在這些打包的資料上執行GKR 協議的運算。

由於稀疏性仍然很高，我們可以利用預計算表，讓證明者以遠低於傳統GKR 協定的計算開銷來產生證明。這項優化顯著提升了GKR 在處理二進位關係時的效率。

本文將重點放在上述第三項技術最佳化：用於二進位操作的預計算表。