GKRFold：基於 SumFold 的 GKR 證明壓縮

Ethereum Research

02-19

本文為機器翻譯

展示原文

以下是文章的中文翻譯:

辻見正人 (早稻田大學) (X: grandchildrice)

免責宣告: 本文處於早期構想階段,邏輯和數學公式可能並未完全嚴謹。我們歡迎任何對於這一想法本身的評論或反饋,以及關於邏輯結構的建議。

摘要

在本文中,我們介紹了GKRFold,一種用於壓縮 n 個GKR基SNARK證明的證明大小和驗證成本的協議。GKRFold採用了最初在NeutronNova[KS24]中提出的SumFold元件來實現這種壓縮。最終,壓縮過程產生了一個Sumcheck例項和一個承諾。因此,驗證者只需執行一次Sumcheck和兩次隨機多項式評估。此外,該協議適用於GKR協議的統一和非統一例項。

1. 引言

1.1. GKR協議

GKR證明系統[GKR15,XZZ19]是一種著名的SNARK(簡潔非互動式知識論證),因其高效的證明者時間而被用於諸如Expander和Ceno等系統。它的設計基於將每個電路層表示為相應的層多項式。從輸出開始,該協議透過在隨機選擇的點上執行Sumcheck協議,將一層的宣告順序傳遞到下一層的宣告。

更準確地說,層多項式(V_i)被定義為

V_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} \Bigl\{ add_{i+1}(z,x,y)\bigl(V_{i+1}(x)+V_{i+1}(y)\bigr) + mult_{i+1}(z,x,y)\bigl(V_{i+1}(x) \cdot V_{i+1}(y)\bigr) \Bigr\},

Vi(z)=∑x,y∈{0,1}Si{addi+1(z,x,y)(Vi+1(x)+Vi+1(y))+multi+1(z,x,y)(Vi+1(x)⋅Vi+1(y))},

其中函式 add_i(z,x,y)addi(z,x,y) 和 mult_i(z,x,y)multi(z,x,y) 如果層 ii 中的門 (z,x,y)(z,x,y) 分別是加法或乘法門,則返回1,否則返回0。

GKR協議的概述如下:

證明者將電路評估 C(x,w)=yC(x,w)=y 傳送給驗證者。
對於每一層 i = 1,\dots,d-1i=1,…,d−1 (不包括輸入層),驗證者透過選擇一個隨機點 r_iri 發出挑戰,然後在 V_i(r_i)Vi(ri) 上啟動Sumcheck協議。
驗證者直接評估輸入層 V_d(r_d)Vd(rd)。

儘管證明者可以在 O(N)O(N) 時間內生成證明,而無需提交中間結果或依賴FFT,但驗證時間和證明大小的複雜度仍為 O(D\log N)O(DlogN)。因此,實現高效的證明壓縮仍然是一個重要的挑戰。

1.2. NeutronNova和SumFold

正如在NeutronNova[KS24]中介紹的,SumFold是一種技術,它可以將任意數量的Sumcheck例項摺疊成一個例項。透過將SumFold應用於GKR協議,可以壓縮GKR證明中固有的多個Sumcheck例項,從而減少整體證明大小和驗證時間。

1.3. 貢獻

在這項工作中,我們提出了GKRFold,這是一種新的方法,它將SumFold應用於有效壓縮nn個GKR證明。本研究的主要貢獻如下:

我們證明了SumFold可以有效地用於壓縮GKR例項,從而大大提高了證明大小和驗證效率。
我們表明GKRFold可以壓縮nn個GKR證明,每個證明包含dd層(總共6 \times n \times d6×n×d個Sumcheck例項),壓縮為單個Sumcheck例項。

這一結果大大減少了驗證多個GKR證明的開銷,使該協議在需要簡潔高效驗證的應用中更加實用。

2. SumFold:高層次思想

這裡省略了對MLE、Sumcheck和GKR的解釋。如果想了解詳細資訊,請參考以下文件。

假設我們希望透過Sumcheck證明一個由組合定義的函式

F(\vec{g}(x)),

F(→g(x)),

其中FF是tt個變數的多項式,\vec{g}→g是tt個ll個變數的多項式向量。例如,可以考慮以下情況

F(\vec{g}(x)) = g_0(x) \cdot g_1(x) \cdots g_{t-1}(x),

F(→g(x))=g0(x)⋅g1(x)⋯gt−1(x),

它表示\vec{g}(x)→g(x)各個分量的乘積。

SumFold的目標是將nn個Sumcheck例項

[T_i = \sum_x F(\vec{g}(x))]_{i \in [n]}

[Ti=∑xF(→g(x))]i∈[n]

壓縮為單個Sumcheck證明。

我們定義一個Sumcheck例項\mathsf{SC}SC,它包含Sumcheck證明所需的所有資訊:

Screenshot from 2025-02-16 11-17-05

SumFold將nn個\mathsf{SC}SC例項摺疊成一個。SumFold的主要思想包括以下步驟:

以下是文章內容的中文翻譯:

對於所有 i = 1,\ldots,n, 給定
T_i = \sum_x F(\vec{g}_i(x)),
透過插值構造一個多項式 Q(b), 使得對於任意輸入 b,
Q(b) = T_b.
這是透過以下方式實現的:
- (a) 透過多項式插值構造 t 個多項式 f_j(b,x), 其中每個多項式輸出對應於第 $b$ 個例項的 g_{bj}(x)。
- (b) 透過將函式 F 應用於集合 \{f_1(b,x), \dots, f_t(b,x)\} 來重構 Q(b)。
提交多項式 Q(b)。這個承諾有效地聚合了所有 n 個 Sumcheck 例項的承諾。
驗證者選擇一個隨機挑戰 r_b 並將第 $r_b$ 個 Sumcheck 例項指定為摺疊例項。

已驗證 (參見 NeutronNova 論文[KS24]附錄 B) 有

Q(r_b) = T_{r_b}.

協議 (引自[KS24]):

3. GKRFold

3.0. Linear GKR Protocol (Libra[XZZ19])

在本節中, 我們描述 GKR 協議的線性時間演算法。首先, 假定給定以下層多項式:

V_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} \Bigl\{ add_{i+1}(z,x,y)\bigl(V_{i+1}(x)+V_{i+1}(y)\bigr) + mult_{i+1}(z,x,y)\bigl(V_{i+1}(x) \cdot V_{i+1}(y)\bigr) \Bigr\}.

V_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} add_{i+1}(z,x,y)V_{i+1}(x) \;+\;

\sum_{x,y \in \{0,1\}^{S_i}} add_{i+1}(z,x,y)V_{i+1}(y) \;+\;

\sum_{x,y \in \{0,1\}^{S_i}} mult_{i+1}(z,x,y)\bigl(V_{i+1}(x) \cdot V_{i+1}(y)\bigr).

For each term, a 2-phase Sumcheck protocol is executed. For instance, consider the third term:

\sum_{x \in \{0,1\}^{S_i}} h_{i+1}(x)V_{i+1}(x),

h_{i+1}(x) = ∑_{y ∈ {0,1}^{S_i}} mult_{i+1}(z,x,y)V_{i+1}(y).

2相檢查協議如下進行:

透過Sumcheck證明h_{i+1}(x)的正確性。
透過Sumcheck證明∑_{x ∈ {0,1}^{S_i}} h_{i+1}(x)V_{i+1}(x)的正確性。

因此,對於每一層,總共執行6個Sumcheck例項。

3.1. GKRFold: 概述

假設我們有n個GKR例項,每個例項有d層。那麼總共有n × d個層多項式。對於每一層,協議需要6個Sumcheck例項,總共有

6 × n × d

個Sumcheck例項。

這六種Sumcheck例項總結如下表所示:

來源

免責聲明：以上內容僅為作者觀點，不代表Followin的任何立場，不構成與Followin相關的任何投資建議。

喜歡

評論