GKRFold: Nén bằng chứng GKR dựa trên SumFold

avatar
Ethereum Research
02-19
Bài viết này được dịch máy
Xem bản gốc

Masato Tsutsumi (Đại học Waseda) ( X: cháu )

phiên bản mới nhất: https://hackmd.io/@grandchildrice/SkXoyK1qkl

Tuyên bố miễn trừ trách nhiệm : Bài đăng này đang trong giai đoạn ý tưởng ban đầu và logic cũng như công thức toán học có thể chưa hoàn toàn chặt chẽ. Chúng tôi hoan nghênh mọi bình luận hoặc phản hồi về ý tưởng cũng như các đề xuất liên quan đến cấu trúc logic.

Tóm tắt

Trong bài báo này, chúng tôi giới thiệu GKRFold, một giao thức để nén cả kích thước bằng chứng và chi phí xác minh của n bằng chứng SNARK dựa trên GKR. GKRFold kết hợp SumFold—một thành phần ban đầu được đề xuất trong NeutronNova[KS24]—để đạt được sự nén này. Cuối cùng, quá trình nén tạo ra một thể hiện Sumcheck duy nhất cùng với một cam kết. Do đó, trình xác minh chỉ cần thực hiện một Sumcheck và hai đánh giá đa thức ngẫu nhiên. Hơn nữa, giao thức này có thể áp dụng cho cả thể hiện đồng nhất và không đồng nhất của giao thức GKR.

1. Giới thiệu

1.1. Giao thức GKR

Hệ thống chứng minh GKR[GKR15,XZZ19], một SNARK (Lập luận phi tương tác ngắn gọn về kiến thức) nổi bật do thời gian chứng minh hiệu quả của nó, đã được sử dụng trong các hệ thống như Expander và Ceno . Thiết kế của nó dựa trên việc biểu diễn mỗi lớp mạch như một đa thức lớp tương ứng. Bắt đầu từ đầu ra, giao thức tuần tự chuyển tiếp một yêu cầu về một lớp đến một yêu cầu về lớp tiếp theo bằng cách thực hiện giao thức Sumcheck khi đánh giá đa thức lớp tại một điểm được chọn ngẫu nhiên.

hình ảnh

Chính xác hơn, đa thức lớp ( V_i ) được định nghĩa là

V_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} \Bigl\{ cộng_{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 ) = ∑ x , y ∈ { 0 , 1 } S i { cộng d i + 1 ( z , x , y ) ( V i + 1 ( x ) + V i + 1 ( y ) ) + bội số i + 1 ( z , x , y ) ( V i + 1 ( x ) ⋅ V i + 1 ( y ) ) } ,​​​

trong đó các hàm add_i(z,x,y) a d i ( z , x , y ) và mult_i(z,x,y) m u l t i ( z , x , y ) trả về 1 nếu cổng (z,x,y) ( z , x , y ) trong lớp i i là cổng cộng hoặc nhân, và trả về 0 nếu không.

Tổng quan về giao thức GKR như sau:

  1. Người chứng minh gửi đánh giá mạch C(x,w)=y C ( x , w ) = y tới người xác minh.
  2. Đối với mỗi lớp i = 1,\dots,d-1 i = 1 , … , d − 1 (không bao gồm lớp đầu vào), trình xác minh đưa ra thử thách bằng cách chọn một điểm ngẫu nhiên r_i r i rồi khởi tạo giao thức Sumcheck trên V_i(r_i) V i ( r i ) .
  3. Bộ xác minh trực tiếp đánh giá lớp đầu vào V_d(r_d) V d ( r d ) .

Mặc dù người chứng minh có thể tạo ra các bằng chứng trong thời gian O(N) O ( N ) mà không cần cam kết các kết quả trung gian hoặc dựa vào FFT, thời gian xác minh và quy mô bằng chứng thể hiện độ phức tạp là O(D\log N) O ( D log N ) . Do đó, việc đạt được khả năng nén hiệu quả vẫn là một thách thức quan trọng.

1.2. NeutronNova và SumFold

SumFold, như đã giới thiệu trong NeutronNova[KS24], là một kỹ thuật gấp một số lượng tùy ý các thể hiện Sumcheck thành một thể hiện duy nhất. Bằng cách áp dụng SumFold vào giao thức GKR, có thể nén nhiều thể hiện Sumcheck vốn có trong các bằng chứng GKR, do đó giảm cả kích thước bằng chứng tổng thể và thời gian xác minh.

1.3. Đóng góp

Trong công trình này, chúng tôi đề xuất GKRFold, một phương pháp mới áp dụng SumFold để nén hiệu quả n n trường hợp của bằng chứng GKR. Những đóng góp chính của nghiên cứu này như sau:

  1. Chúng tôi chứng minh rằng SumFold có thể được sử dụng hiệu quả để nén các phiên bản GKR, dẫn đến những cải tiến đáng kể về kích thước bằng chứng và hiệu quả xác minh.
  2. Chúng tôi chứng minh rằng GKRFold có thể nén n n bằng chứng GKR, mỗi bằng chứng bao gồm d d lớp (tổng cộng là 6 \times n \times d 6 × n × d thể hiện Sumcheck) thành một thể hiện Sumcheck duy nhất.

Kết quả này làm giảm đáng kể chi phí liên quan đến việc xác minh nhiều bằng chứng GKR, khiến giao thức trở nên thiết thực hơn cho các ứng dụng yêu cầu xác minh ngắn gọn và hiệu quả.

2. SumFold: Ý tưởng cấp cao

Giải thích về MLE, Sumcheck và GKR được lược bỏ ở đây. Những ai muốn tìm hiểu chi tiết nên tham khảo các tài liệu sau.

Giả sử chúng ta muốn chứng minh, thông qua Sumcheck, một hàm được xác định bởi một thành phần

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

trong đó F F là một đa thức trong t biến t và \vec{g} → g là một vectơ của t đa thức trong l l biến. Ví dụ, người ta có thể xem xét trường hợp

F(\vec{g}(x)) = g_0(x) \cdot g_1(x) \cdots g_{t-1}(x),
F ( → g ( x ) ) = g 0 ( x ) ⋅ g 1 ( x ) ⋯ g t − 1 ( x ) ,

biểu diễn tích các thành phần của \vec{g}(x) → g ( x ) .

Mục tiêu của SumFold là giảm các bằng chứng của n n trường hợp Sumcheck

[T_i = \sum_x F(\vec{g}(x))]_{i \trong [n]}
[ T i = ∑ x F ( → g ( x ) ) ] i ∈ [ n ]

với một bằng chứng Sumcheck duy nhất.

hình ảnh

Chúng tôi định nghĩa một thể hiện Sumcheck \mathsf{SC} S C chứa tất cả thông tin cần thiết cho một bằng chứng Sumcheck như sau:

Ảnh chụp màn hình từ 2025-02-16 11-17-05

SumFold gấp n n trường hợp của \mathsf{SC} S C thành một. Ý tưởng chính đằng sau SumFold bao gồm các bước sau:

  1. Với mọi i = 1,\ldots,n i = 1 , … , n , cho
    T_i = \sum_x F(\vec{g}_i(x)),
    T i = ∑ x F ( → g i ( x ) ) ,
    xây dựng một đa thức Q(b) Q ( b ) bằng cách nội suy sao cho, đối với bất kỳ đầu vào b b nào ,
    Q(b) = T_b.
    Q ( b ) = Tb .​
    Điều này được thực hiện như sau:
    • (a) Xây dựng t đa thức f_j (b,x) f j ( b , x ) thông qua nội suy đa thức, trong đó mỗi đa thức đưa ra g_{bj}(x) g b j ( x ) tương ứng với trường hợp thứ $b$.
    • (b) Xây dựng lại Q(b) Q ( b ) bằng cách áp dụng hàm F F vào tập hợp \{f_1(b,x), \dots, f_t(b,x)\} { f 1 ( b , x ) , … , f t ( b , x ) } .
  2. Cam kết với đa thức Q(b) Q ( b ) . Cam kết này thực sự tổng hợp các cam kết cho tất cả n n trường hợp Sumcheck.
  3. Bộ xác minh chọn một thử thách ngẫu nhiên r_b r b và chỉ định phiên bản Sumcheck thứ $r_b$ là phiên bản đã gấp lại.

hình ảnh

Người ta đã xác minh (xem Phụ lục B của bài báo NeutronNova[KS24]) rằng

Q(r_b) = T_{r_b}.
Q ( r b ) = T r b .

Giao thức (trích dẫn từ [KS24]):
Ảnh chụp màn hình từ 2025-02-16 11-15-57

3. GKRFold

3.0. Giao thức GKR tuyến tính (Libra[XZZ19])

Trong phần này, chúng tôi mô tả thuật toán thời gian tuyến tính cho giao thức GKR. Trước tiên, giả sử rằng đa thức lớp sau được đưa ra:

V_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} \Bigl\{ cộng_{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 ) = ∑ x , y ∈ { 0 , 1 } S i { cộng d i + 1 ( z , x , y ) ( V i + 1 ( x ) + V i + 1 ( y ) ) + bội số i + 1 ( z , x , y ) ( V i + 1 ( x ) ⋅ V i + 1 ( y ) ) } .​​​

Chúng ta phân chia biểu thức này thành ba hạng tử:

V_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} cộng_{i+1}(z,x,y)V_{i+1}(x) \;+\;
V i ( z ) = ∑ x , y ∈ { 0 , 1 } S i cộng d i + 1 ( z , x , y ) V i + 1 ( x )​ +
\sum_{x,y \in \{0,1\}^{S_i}} cộng_{i+1}(z,x,y)V_{i+1}(y) \;+\;
∑ x , y ∈ { 0 , 1 } S i a d i + 1 ( z , x , y ) V i + 1 ( y )​ +
\sum_{x,y \in \{0,1\}^{S_i}} nhân_{i+1}(z,x,y)\bigl(V_{i+1}(x) \cdot V_{i+1}(y)\bigr).
∑ x , y ∈ { 0 , 1 } Đồng dạng i + 1 ( z , x , y ) ( V i + 1 ( x ) ⋅ V i + 1 ( y ) ) .​​​​

Đối với mỗi thuật ngữ, một giao thức Sumcheck 2 pha được thực hiện. Ví dụ, hãy xem xét thuật ngữ thứ ba:

\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)=\sum_{x \in \{0,1\}^{S_i}} h_{i+1}(x)V_{i+1}(x),
∑ x , y ∈ { 0 , 1 } Đồng dạng i + 1 ( z , x , y ) ( V i + 1 ( x ) ⋅ V i + 1 ( y ) ) = ∑ x ∈ { 0 , 1 } Si h i + 1 ( x ) V i + 1 ( x ) ,​​​​​

Ở đâu

h_{i+1}(x) = \sum_{y \in \{0,1\}^{S_i}} nhân_{i+1}(z,x,y)V_{i+1}(y).
h i + 1 ( x ) = ∑ y ∈ { 0 , 1 } Đồng dạng i + 1 ( z , x , y ) V i + 1 ( y ) .​​​​

Sau đó, giao thức Sumcheck 2 giai đoạn được thực hiện như sau:

  1. Chứng minh tính đúng đắn của h_{i+1}(x) h i + 1 ( x ) thông qua Sumcheck.
  2. Chứng minh tính đúng đắn của biểu thức \sum_{x \in \{0,1\}^{S_i}} h_{i+1}(x)V_{i+1}(x) ∑ x ∈ { 0 , 1 } S i h i + 1 ( x ) V i + 1 ( x ) thông qua Sumcheck.

Vì vậy, đối với mỗi lớp, tổng cộng có 2 \times 3 = 6 2 × 3 = 6 phiên bản Sumcheck được thực thi song song.

3.1. GKRFold: Tổng quan

Giả sử chúng ta được cung cấp n n trường hợp GKR và mỗi trường hợp bao gồm d d lớp. Khi đó tồn tại tổng cộng n \times d n × d đa thức lớp. Đối với mỗi lớp, giao thức yêu cầu 6 trường hợp Sumcheck (như mô tả ở trên), dẫn đến tổng cộng

6 \lần n \lần d
6 × n × d

Các trường hợp Sumcheck.

Sáu loại phiên bản Sumcheck này được tóm tắt trong bảng sau:

Kiểm tra tổng 1 (h_{1,i+1}(x)) ( h 1 , i + 1 ( x ) ) Kiểm tra tổng 2 (h_{2,i+1}(y)) ( h 2 , i + 1 ( y ) ) Kiểm tra tổng 3 (h_{3,i+1}(x)) ( h 3 , i + 1 ( x ) ) Tổng kiểm tra 4 (học kỳ 1) Tổng kiểm tra 5 (học kỳ 2) Tổng kiểm tra 6 (học kỳ 3)
Sự biểu lộ \sum_{y \in \{0,1\}^{S_i}} cộng_{i+1}(z,x,y ) ∑ y ∈ { 0 , 1 } S i cộng d i + 1 ( z , x , y ) \sum_{x \in \{0,1\}^{S_i}} cộng_{i+1}(z,x,y ) ∑ x ∈ { 0 , 1 } S i cộng d i + 1 ( z , x , y ) \sum_{y \in \{0,1\}^{S_i}} mult_{i+1}(z,x,y)V_{i+1 } ( y ) ∑ y ∈ { 0 , 1 } Đồng dạng i + 1 ( z , x , y ) V i + 1 ( y ) \sum_{x \in \{0,1\}^{S_i}} h_{1,i+1}(x)V_{i+1}(x) ∑ x ∈ { 0 , 1 } S i h 1 , i + 1 ( x ) V i + 1 ( x ) \sum_{y \in \{0,1\}^{S_i}} h_{2,i+1}(y)V_{i+1}(y) ∑ y ∈ { 0 , 1 } S i h 2 , i + 1 ( y ) V i + 1 ( y ) \sum_{x \in \{0,1\}^{S_i}} h_{3,i+1}(x)V_{i+1}(x) ∑ x ∈ { 0 , 1 } S i h 3 , i + 1 ( x ) V i + 1 ( x )
Hình thức của F F F(g_1(x),g_2(x)) = g_1(x) \cdot g_2(x) F ( g 1 ( x ) , g 2 ( x ) ) = g 1 ( x ) ⋅ g 2 ( x ) như nhau như nhau như nhau như nhau như nhau
Vectơ \vec{g} → g \{ cộng_{i+1}(z,x,y),\, g_e(x,y,z) \ } { cộng d i + 1 ( z , x , y ) , g e ( x , y , z ) } \{ cộng_{i+1}(z,x,y),\, g_e(x,y,z) \ } { cộng d i + 1 ( z , x , y ) , g e ( x , y , z ) } \{ nhân_{i+1}(z,x,y),\, V_{i+1}(y ) \ } { nhân i + 1 ( z , x , y ) , V i + 1 ( y ) } \{ h_{1,i+1}(x),\, V_{i+1}(x) \} { h 1 , i + 1 ( x ) , V i + 1 ( x ) } \{ h_{2,i+1}(y),\, V_{i+1}(y) \} { h 2 , i + 1 ( y ) , V i + 1 ( y ) } \{ h_{3,i+1}(x),\, V_{i+1}(x) \} { h 3 , i + 1 ( x ) , V i + 1 ( x ) }

Lưu ý rằng Sumcheck 1 và Sumcheck 2 tự nhiên có dạng

F(g_1(x)) = g_1(x).
F ( g1 ( x ) ) = g1 ( x ) .​​

Tuy nhiên, bằng cách giới thiệu hàm đồng nhất hằng số g_e(x) = 1 g e ( x ) = 1 (luôn trả về 1), chúng có thể được biểu thị tương đương như

F(g_1(x), g_e(x)) = g_1(x) \cdot g_e(x).
F ( g 1 ( x ) , g e ( x ) ) = g 1 ( x ) ⋅ g e ( x ) .

Vì vậy, tất cả các trường hợp Sumcheck đều chia sẻ cùng một dạng chức năng

F(g_1(x), g_2(x)) = g_1(x) \cdot g_2(x).
F ( g 1 ( x ) , g 2 ( x ) ) = g 1 ( x ) ⋅ g 2 ( x ) .

Sự tương ứng giữa các thể hiện Sumcheck này và khung SumFold được đưa ra trong bảng trên.

Do đó, bằng cách áp dụng SumFold, tổng số

6 \lần n \lần d
6 × n × d

Các phiên bản Sumcheck có thể được gộp lại thành một phiên bản Sumcheck duy nhất.

3.2. GKRFold: Giao thức

Đầu vào:
n n Các trường hợp GKR, được biểu diễn dưới dạng

\Bigl\{\{SC_{i1}, SC_{i2}, SC_{i3}, SC_{i4}, SC_{i5}, SC_{i6}\}_{i \in [n \times d]},\, (\vec{x}_i, \vec{w}_i)_{i \in [n \times d]},\, (\vec{u}_i)_{i \in [n \times d]}\Bigr\} \in GKR^{n},
{ { S C i 1 , S C i 2 , S C i 3 , S C i 4 , S C i 5 , S C i 6 } i ∈ [ n × d ] , ( → x i , → w i ) i ∈ [ n × d ] , ( → u i ) i ∈ [ n × d ] } ∈ G K R n ,

Đầu ra:
(SC,\, r_b,\, \bar{Q}(r_b),(\vec{x}_i, \vec{w}_i), (\vec{u}_i)) ( S C , r b , ¯ Q ( r b ) , ( → x i , → w i ) , ( → u i ) )

Nguồn
Tuyên bố từ chối trách nhiệm: Nội dung trên chỉ là ý kiến của tác giả, không đại diện cho bất kỳ lập trường nào của Followin, không nhằm mục đích và sẽ không được hiểu hay hiểu là lời khuyên đầu tư từ Followin.
Thích
Thêm vào Yêu thích
Bình luận
Nội dung liên quan