一文了解 FOAKS 當中的多項式承諾協議 Brakedown

撰文：Fox Tech CEO 康水躍，Fox Tech 首席科學家 孟鉉濟

前言：如果密碼學家沒有發現張量積（Tensor Product）和多項式取值之間的聯繫，那就很難出現多項式承諾協議 Brakedown，也就不可能誕生基於 Brakedown 的 Orion、以及 FOAKS 這類全新的快速算法。

在許多依賴多項式承諾的零知識證明系統當中，使用了不同的承諾協議。根據 a16z 的 Justin Thaler 在 2022 年 8 月文章“Measuring SNARK performance: Frontends, backends, and the future”的評估，Brakedown 雖然有較大的 Proof Size，但是無疑是當下最快的多項式承諾協議。

FRI、KZG、Bulletproof 是更為常見的多項式承諾協議，但速度是它們的瓶頸。zkSync 採用的 Plonky、Polygon zkEVM 採用的 Plonky 2、Scroll 採用的 Ultra-Plonk 等算法都是基於 KZG 的多項式承諾。Prover 涉及到大量的 FFT 計算和 MSM 運算生成多項式和承諾，這兩者都會帶來大量的計算負擔。 雖然 MSM 有運行多線程加速的潛力，但需要大量內存，即使在高並行下也很慢，而大型 FFT 則嚴重依賴算法運行時數據的頻繁洗牌，難以通過分佈式加速跨計算集群加載。

正是由於有了更為快速的多項式承諾協議 Brakedown，才使這類運算的複雜度大幅降低。

FOAKS 即 Fast Objective Argument of Knowledges，是由 Fox Tech 提出的一種基於 Brakedown 的零知識證明系統框架。FOAKS 在 Orion 的基礎上進一步減少 FFT 運算，目標是最終消除 FFT。此外，FOAKS 還設計出一種全新的非常精妙的證明遞歸方式來減少證明大小。FOAKS 框架的優勢在於在實現線性證明時間的基礎上有著較小的證明大小，非常適合應用於 zkRollup 場景當中。

下文我們將詳細介紹 FOAKS 所使用的多項式承諾協議 Brakedown。

在密碼學當中，承諾（Commitment）協議由證明者（Prover）對某一個秘密值進行承諾，生成一個公開的承諾值，這個承諾值具有綁定性（Binding）和隱藏性（Hiding），之後提交者需要打開此承諾並將消息發送到驗證者，以驗證承諾與消息之間的對應關係。這一點，使得承諾協議和哈希函數的作用有許多共通之處，但是承諾協議往往依賴於公鑰密碼學領域的數學結構。而多項式承諾（Polynomial Commitment）是一類對於多項式的承諾方案，也就是說被承諾值是多項式。而同時多項式承諾協議當中還包含了在給定的點取值並給出證明的算法，這就使得多項式承諾協議本身成為一類重要的密碼學協議，是許多零知識證明系統的核心部分。

而在最新的密碼學領域的研究當中，由於發現了張量積（Tensor Product）和多項式取值之間的聯繫，所以誕生了一系列與此相關的多項式承諾協議，Brakedown 是其中的代表性協議。

在詳細介紹 Brakedown 的協議細節之前，需要先了解一些基礎知識。我們需要先了解線性碼（Linear Code）、抗碰撞哈希函數（Hash Function）、默克爾樹（Merkle Tree）、張量積（Tensor Product）的運算以及多項式取值的張量積表示。

首先是線性碼（Linear Code）。一個消息長度為 k，碼字長度為 n 的線性碼是一個線性子空間

C∈Fn，使得存在一個從消息到碼字的單射，稱為編碼，記作 EC：Fk→C。任意的對於碼字的線性組合仍然是一個碼字。兩個碼字 u，v 的距離即他們的漢明距離，記作△(u, v)。

最短距離為 d=minu, v△(u, v)。這樣的碼記作[n, k, d]線性碼，用 d /n 表示碼的相對距離。

其次是抗碰撞哈希函數（Hash Function）與默克爾樹（Merkle Tree）。

使用 H:{ 0, 1 }2 λ→{ 0, 1 }λ表示一個哈希函數。默克爾樹是一種特殊的數據結構，可以實現對於 2 d個消息的承諾，生成一個哈希值 h，在打開任何消息時候需要 d+ 1 個哈希值。

默克爾樹可以被表示為一個深度為 d 的二叉樹，其中 L 個消息元素 m1 , m2 ,..., ml分別對應樹的葉子。樹的每一個內部節點都由它的兩個子節點進行哈希計算得出。打開消息 mi時，需要公開從 mi到根節點的路徑。

用以下記號來表示：

1. h←Merkle.Commit(m1 ,..., ml)

2. (mi,πi)←Merkle.Open(m, i)

3. { 0, 1 }←Merkle.Verify(πi, mi, h)

圖 1 ：默克爾樹（Merkle Tree）

我們還需要了解張量積（Tensor Product）的運算是怎麼做的。數學上，張量是向量和矩陣向高維空間的擴展，是很重要的研究對象，詳細的討論張量超出本文的研究範疇，這裡只介紹向量和矩陣的張量積運算。

圖 2  ：向量和矩陣的張量積運算

緊接著，我們需要知道多項式取值的張量積表示。

[GLS+]當中提到，多項式的取值可以被表示成張量積的形式。在這裡我們考慮多線性多項式的承諾。

具體來講，給定一個多項式，他在向量 x0 , x1 ,..., xlogN-1 的取值可以寫成：

根據多線性的定義，每一個變量的次數是 0 或 1 ，因此，這裡有 N 個單項式和係數，以及 logN 個變量。令

，其中 i0 i1 ...ilogN-1 是 i 的二進制表示。令 w 表示多項式係數，

 

同樣的，定義

令

。於是有 X=r0 ⊗r1 。

從而，多項式取值可以被表示成張量積的形式：ϕ(x0 , x1 ,..., xlogN-1 )=<w, r0 ⊗r1 >。

最後，我們來看 FOAKS、Orion[XZS 22 ]當中使用的 Brakedown 的過程。

首先，PC.Commit 將多項式係數 w 劃分成 k×k 的矩陣形式，並將其編碼（參考“預備知識”中的線性碼），記作 C2 。之後對於 C2 的每一列 C2 [:, i]進行承諾建立一個默克爾樹，然後再對於每一個列形成的默克爾樹樹根建立另一個默克爾樹，作為最終的承諾。

在取值證明的計算中，需要證明兩點，一是近似性（Proximity），二是一致性（Consistency）。近似性保證了承諾的矩陣確實和編碼後的一個碼字足夠接近。一致性保證 y=<w, r0 ⊗r1 >。

近似性檢驗：近似性檢驗由兩步組成。首先，驗證者發送一個隨機向量 0 給證明者，證明者計算 Y0 與 C1 的內積，也就是以 Y0 的分量為係數對 C1 的行計算線性組合。由於線性碼的性質，Cy 0 是 Yy 0 的碼字。之後，證明者證明 Cy 0 確實是從被承諾的碼字計算出的。為了證明這一點，驗證者隨機選取 t 列，證明者打開對應的列並提供默克爾樹證明。驗證者檢查這些列和 Y0 的內積和 Cy 0 當中對應位置相等。[BCG 20 ]當中證明如果使用的線性碼有常數的相對距離，那麼被承諾的矩陣就以壓倒性的概率與一個碼字接近（壓倒性的概率是指，命題的否命題成立的概率是可忽略的）。

一致性檢驗：一致性檢驗和近似性檢驗的流程完全類似。不同之處在於，不使用隨機向量 Y0 而是直接使用 r0 來完成線性組合的部分。類似的，c1 也是消息 y1 的一個線性碼，並且有

ϕ(x)=<y1 , r1 >。[BCG 20 ]當中證明，通過一致性檢驗，如果被承諾的矩陣與一個碼字接近，則以壓倒性概率成立 y=ϕ(x)。

以偽代碼形式，我們給出 Brakedown 協議的流程：

Public input：The evaluation point X，parsed as a tensor product X=r0 ⊗r1 ;

Private input：The polynomial ϕ ，the coefficient of is denoted by w.

Let C be the [n, k, d]-limear code，EC：FkFn be the encoding function，N=k×k. If N is not a perfect square，we can pad it to the next perfect square. We use a python style notationmat[:, i] to select the i-th column of a matrix mat。

1. function PC. Commit(ϕ)：

2. Parse w as a k×k matrix. The prover locally computes the tensor code encoding C1 ，C2  ，C1 is a k×n matrix，C2 is a n×n matrix.

3. for i∈ [n] do

4. Compute the Merkle tree root Roott=Merkle.Commit(C2 [:, i])

5. Compute a Merkle tree root R=Merkle.Commit([Root0 ,......Rootn-1 ]), and output R as the commitment.

6. function PC. Prover(ϕ, X, R)

7. The prover receives a random vector Y0 ∈Fk from the verifier

8. Proximity 

   

9. Consistency  

   

10. Prover sends C1 , y1 , C0 , y0  to the verifier.

11. Verifier randomly samples t[n] as an array Î and send it to prover

12. for idx∈Πdo

13. Prover sends C1  [:, idx] and the Merkle tree proof of Rootidx for C2  [:, idx] under R to verifier

14. function PC. VERIFY_EVAL(πX, X, y=ϕ(X), R)

15. Proximity: ∀idx∈Î, CY 0 [idx]==<Y0 , C1 [:, idx]>and EC(Yy 0 )==CY 0 

16. Consistency:∀idx∈Î, C1 [idx]==<Y0 , C1 [:, idx]>and EC(Y1 )==C1 

17. y==<r1 , y1>

18. ∀idx∈Î, EC(C1 [:, idx]) is consistent with ROOTidx, and ROOTidx’s Merkle tree proof is valid.

19. Output accept if all conditions above holds. Otherwise output reject.

結語：多項式承諾是一類非常重要的密碼學協議，被廣泛的應用在許多密碼學系統當中，尤其是零知識證明系統。本文詳細介紹了多項式承諾 Brakedown 協議以及和其相關的數學知識，作為 FOAKS 很重要的底層組件，Brakedown 對 FOAKS 的實例化性能的提升起到了重要作用。

參考文獻

1. [GLS+]:Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. Brakedown: Linear-time and post-quantum snarks for r 1 cs. Cryptology ePrint Archive. https://ia.cr/2021/1043.

2. [XZS 22 ]:Xie T, Zhang Y, Song D. Orion: Zero knowledge proof with linear prover time[C]//Advances in Cryptology–CRYPTO 2022: 42 nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15 – 18, 2022, Proceedings, Part IV. Cham: Springer Nature Switzerland, 2022: 299-328.https://eprint.iacr.org/2022/1010 

3. [BCG 20 ]:Bootle, Jonathan, Alessandro Chiesa, and Jens Groth. "Linear-time arguments with sublinear verification from tensor codes." Theory of Cryptography: 18 th International Conference, TCC 2020, Durham, NC, USA, November 16 – 19, 2020, Proceedings, Part II 18. Springer International Publishing, 2020.

4. Justin Thaler from A16z crypto, Measuring SNARK performance: Frontends, backends, and the future https://a16z crypto.com/measuring-snark-performance-frontends-backends-and-the-future/

5. 張量積的介紹：https://blog.csdn.net/chenxy_bwave/article/details/127288938