GKRFold: SumFold 기반 GKR 증명 압축

02-19

이 기사는 기계로 번역되었습니다

원문 표시

츠츠미 마사토(와세다 대학교) (X: grandchildrice)

면책 조항: 이 게시물은 초기 아이디어 단계이며, 논리와 수학적 공식화가 완전히 엄격하지 않을 수 있습니다. 아이디어 자체와 논리 구조에 대한 제안에 대한 의견이나 피드백을 환영합니다.

요약

이 논문에서는 GKR 기반 SNARK 증명 n개의 증명 크기와 검증 비용을 압축하는 프로토콜인 GKRFold를 소개합니다. GKRFold는 NeutronNova[KS24]에서 처음 제안된 SumFold 구성 요소를 활용하여 이러한 압축을 달성합니다. 최종적으로 압축 과정은 하나의 Sumcheck 인스턴스와 하나의 커밋먼트를 생성합니다. 그 결과 검증자는 단 하나의 Sumcheck와 두 개의 랜덤 다항식 평가만 수행하면 됩니다. 또한 이 프로토콜은 GKR 프로토콜의 균일 및 비균일 인스턴스 모두에 적용할 수 있습니다.

1. 소개

1.1. GKR 프로토콜

GKR 증명 시스템[GKR15,XZZ19]은 프루버 시간이 효율적이라는 장점으로 Expander와 Ceno와 같은 시스템에서 사용되는 대표적인 SNARK(Succinct Non-interactive ARgument of Knowledge)입니다. 이 설계는 각 회로 레이어를 해당 레이어 다항식으로 표현하는 것을 기반으로 합니다. 출력부터 시작하여 프로토콜은 순차적으로 레이어 다항식의 임의로 선택된 지점에서의 평가에 대한 주장을 실행하는 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\},

여기서 함수 add_i(z,x,y)와 mult_i(z,x,y)는 각각 레이어 i의 (z,x,y) 게이트가 덧셈 게이트 또는 곱셈 게이트인 경우 1을, 그렇지 않은 경우 0을 반환합니다.

GKR 프로토콜의 개요는 다음과 같습니다:

프루버가 회로 평가 C(x,w)=y를 검증자에게 보냅니다.
모든 레이어 i = 1,...,d-1(입력 레이어 제외)에 대해, 검증자는 임의의 지점 r_i를 선택하고 V_i(r_i)에 대한 Sumcheck 프로토콜을 시작합니다.
검증자는 직접 입력 레이어 V_d(r_d)를 평가합니다.

프루버는 중간 결과를 커밋하거나 FFT에 의존하지 않고도 O(N) 시간에 증명을 생성할 수 있지만, 검증 시간과 증명 크기는 O(D log N) 복잡도를 갖습니다. 따라서 효율적인 증명 압축을 달성하는 것이 중요한 과제로 남아 있습니다.

1.2. 뉴트론노바와 섬폴드

뉴트론노바[KS24]에서 소개된 섬폴드는 임의의 수의 섬체크 인스턴스를 단일 인스턴스로 접는 기술입니다. GKR 프로토콜에 섬폴드를 적용하면 GKR 증명에 내재된 다중 섬체크 인스턴스를 압축할 수 있어 전체 증명 크기와 검증 시간을 줄일 수 있습니다.

1.3. 기여

이 연구에서는 섬폴드를 적용하여 nn개의 GKR 증명을 효율적으로 압축하는 GKRFold라는 새로운 방법을 제안합니다. 이 연구의 주요 기여는 다음과 같습니다:

섬폴드를 활용하여 GKR 인스턴스를 압축할 수 있음을 보여주며, 이를 통해 증명 크기와 검증 효율성이 크게 향상됩니다.
nn개의 GKR 증명을 각각 dd개의 레이어로 구성된 것(총 6 \times n \times d6×n×d개의 섬체크 인스턴스)을 단일 섬체크 인스턴스로 압축할 수 있음을 보여줍니다.

이 결과는 다중 GKR 증명 검증에 수반되는 오버헤드를 크게 줄여 간단하고 효율적인 검증이 필요한 애플리케이션에 프로토콜을 더욱 실용적으로 만듭니다.

2. 섬폴드: 높은 수준의 아이디어

MLE, 섬체크, GKR에 대한 설명은 생략되어 있습니다. 자세한 내용을 알고 싶으신 분은 다음 문서를 참조하시기 바랍니다.

다음과 같은 합성 함수의 섬체크 증명을 하고자 한다고 가정합시다.

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)의 구성 요소들의 곱을 나타냅니다.

섬폴드의 목표는 nn개의 섬체크 인스턴스

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

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

의 증명을 단일 섬체크 증명으로 줄이는 것입니다.

섬체크 증명에 필요한 모든 정보를 포함하는 섬체크 인스턴스 \mathsf{SC}SC를 다음과 같이 정의합니다:

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

섬폴드는 nn개의 \mathsf{SC}SC 인스턴스를 하나로 접습니다. 섬폴드의 주요 아이디어는 다음과 같은 단계로 구성됩니다:

以下是韩语翻译结果:

对于所有 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. 线性 GKR 协议 (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\}.

에이프(Ape)_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} 추가_i+1(z,x,y)에이프_{i+1}(x) \;+\;

에이프i(z)=∑x,y∈{0,1}Si추가_i+1(z,x,y)에이프_i+1(x)+

\sum_{x,y \in \{0,1\}^{S_i}} 추가_i+1(z,x,y)에이프_{i+1}(y) \;+\;

∑x,y∈{0,1}Si추가_i+1(z,x,y)에이프_i+1(y)+

\sum_{x,y \in \{0,1\}^{S_i}} 곱_i+1(z,x,y)\bigl(에이프_{i+1}(x) \cdot 에이프_{i+1}(y)\bigr).

∑x,y∈{0,1}Si곱_i+1(z,x,y)(에이프_i+1(x)⋅에이프_i+1(y)).

각 항목에 대해 2단계 Sumcheck 프로토콜이 실행됩니다. 예를 들어, 세 번째 항목을 고려해 보겠습니다:

\sum_{x,y \in \{0,1\}^{S_i}} 곱_i+1(z,x,y)\bigl(에이프_{i+1}(x) \cdot 에이프_{i+1}(y)\bigr)=\sum_{x \in \{0,1\}^{S_i}} h_{i+1}(x)에이프_{i+1}(x),

∑x,y∈{0,1}Si곱_i+1(z,x,y)(에이프_i+1(x)⋅에이프_i+1(y))=∑x∈{0,1}Sih_i+1(x)에이프_i+1(x),

여기서

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

hi+1(x)=∑y∈{0,1}Simulti+1(z,x,y)Vi+1(y).

The 2-phase Sumcheck protocol is then carried out as follows:

Prove the correctness of h_{i+1}(x)hi+1(x) via Sumcheck.
Prove the correctness of the term ∑_{x ∈ {0,1}^{S_i}} h_{i+1}(x)V_{i+1}(x)∑x∈{0,1}Sihi+1(x)Vi+1(x) via Sumcheck.

Thus, for each layer, a total of 2 × 3 = 62×3=6 Sumcheck instances are executed in parallel.

3.1. GKRFold: Overview

Assume that we are given nn GKR instances, and that each instance comprises dd layers. Then there exist a total of n × dn×d layer polynomials. For each layer, the protocol requires 6 Sumcheck instances (as described above), resulting in a total of

6 × n × d

6×n×d

Sumcheck instances.

These six types of Sumcheck instances are summarized in the following table:

출처

면책조항: 상기 내용은 작자의 개인적인 의견입니다. 따라서 이는 Followin의 입장과 무관하며 Followin과 관련된 어떠한 투자 제안도 구성하지 않습니다.

라이크

즐겨찾기에 추가

코멘트