原文著者：Fox Tech CEO Kang Shuiyue、Fox Tech主任研究員Meng Xuanji

前書き: 暗号学者が Tensor Product と多項式値の間の関係を発見しない場合、多項式コミットメント プロトコル Brakedown の出現は困難になり、Brakedown ベースの Orion や FOAKS などの新しいプロトコルを作成することは不可能になります。

多項式コミットメントに依存する多くのゼロ知識証明システムでは、さまざまなコミットメント プロトコルが使用されます。 2022 年 8 月の記事「SNARK パフォーマンスの測定: フロントエンド、バックエンド、そして将来」における a16z の Justin Thaler の評価によれば、Brakedown はより大きなプルーフ サイズを持っていますが、間違いなく現時点で最速の多項式コミットメント プロトコルです。

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 シナリオに非常に適しています。

以下では、FOA​​KS で使用される多項式コミットメント プロトコル Brakedown について詳しく紹介します。

暗号化におけるコミットメント (Commitment) プロトコルは、証明者 (Prover) が特定の秘密値をコミットし、結合と隠蔽 (Hiding) を持つ公開コミットメント値を生成して送信することで構成されます。検証者はこのプロミスを開いて送信する必要があります。メッセージを検証者に送信して、Promise とメッセージの対応を検証します。このため、コミットメント プロトコルとハッシュ関数には多くの共通点がありますが、コミットメント プロトコルは公開キー暗号化の分野で数学的構造に依存することがよくあります。多項式コミットメント (Polynomial Commitment) は、多項式のコミットメント スキームの一種です。つまり、約束された値は多項式です。同時に、多項式コミットメント プロトコルには、特定の点で値を取得して証明を行うアルゴリズムも含まれているため、多項式コミットメント プロトコル自体が暗号プロトコルの重要なクラスとなり、多くのゼロ知識証明システムの中核部分となります。 。

暗号分野における最新の研究では、テンソル積（Tensor Product）と多項式の値との関係の発見により、関連する一連の多項式コミットメントプロトコルが誕生し、Brakedown は代表的なプロトコルの 1 つとなっています。 . .

Brakedown プロトコルの詳細を詳しく紹介する前に、いくつかの基本を理解する必要があります。線形コード、衝突防止ハッシュ関数、マークル ツリー、テンソル積、および多項式値のテンソル積表現の操作を理解する必要があります。

1つ目はリニアコード（Linear Code）です。メッセージ長 k とコードワード長 n の線形コードは線形部分空間です

C ∈ Fn であるため、エンコーディングと呼ばれるメッセージからコードワードへの注入があり、EC: Fk→C として示されます。コードワードの線形結合はすべてコードワードです。 2 つのコードワード 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 がそれぞれツリーの葉に対応します。ツリーの各内部ノードは、その 2 つの子ノードからハッシュされます。メッセージ mi を開くときは、mi からルート ノードまでのパスを公開する必要があります。

画像の説明

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

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

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

図 1: マークル ツリー

画像の説明

図 2: ベクトルと行列のテンソル積演算

次に、多項式値のテンソル積表現を知る必要があります。

[GLS+] で述べたように、多項式の値はテンソル積の形式で表現できます。ここでは、多線形多項式コミットメントを考慮します。

具体的には、多項式が与えられた場合、ベクトル x0 、 x1 、...、 xlogN-1 の値は次のように記述できます。

多重線形性の定義によれば、各変数の次数は 0 または 1 であるため、N 個の単項式と係数、および logN 個の変数が存在します。作る

ここで、i0 i1 ...ilogN-1 は i のバイナリ表現です。 w を多項式係数とします。

同様に、定義します

作る

。したがって、X=r0 ⊗r1 となります。

したがって、多項式の値はテンソル積の形式で表現できます: ϕ(x0 , x1 ,..., xlogN-1 )=。

最後に、FOAKS と Orion [XZS 22] で使用されるブレーキダウン プロセスを見てみましょう。

まず、PC.Commit は、多項式係数 w を k×k 行列形式に分割し、C2 として符号化します (「予備知識」の線形コードを参照)。次に、C2 の各列 C2 [:, i] にコミットしてマークル ツリーを構築し、最終コミットメントとして各列によって形成されるマークル ツリーのルートに対して別のマークル ツリーを構築します。

価値証明の計算では、近接性(Proximity)と一貫性(Consistency)の2点を証明する必要があります。近似により、コミットされた行列が実際にエンコードされたコードワードに十分に近いことが保証されます。一貫性保証 y=。

近接テスト: 近接テストは 2 つのステップで構成されます。まず、検証者はランダムベクトル0を証明者に送り、証明者はY0とC1の内積、つまりY0の成分を係数としたC1の行の線形結合を計算します。線形符号の特性により、Cy 0 は Yy 0 の符号語です。その後、証明者は Cy 0 が確かにコミットされたコードワードから計算されたことを証明します。これを証明するために、検証者はランダムに t 列を選択し、証明者は対応する列を開いてマークル ツリー証明を提供します。検証者は、これらの列と Y0 の内積が Cy 0 内の対応する位置に等しいことをチェックします。 [BCG 20]は、使用される線形符号が一定の相対距離を持っている場合、コミットされた行列は圧倒的な確率で符号語に近づくことを証明します(圧倒的な確率とは、命題の否定的な命題が真である確率を指します。無視されます) 。

整合性チェック: 整合性チェックと近接性チェックのプロセスは完全に似ています。違いは、ランダム ベクトル Y0 が使用されず、線形結合部分を完了するために r0 が直接使用されることです。同様に、c1 もメッセージ y1 の線形コードであり、次のようになります。

ϕ(x)=。 [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]==and EC(Yy 0 )==CY 0 

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

17. y==

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.

参考文献

参考文献

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