Nguyên văn tác giả: Fox Tech CEO Kang Shuiyue, Fox Tech trưởng khoa học gia Meng Xuanji

Lời nói đầu: Nếu các nhà mật mã học không phát hiện ra mối liên hệ giữa Sản phẩm Tensor và các giá trị đa thức, thì giao thức cam kết đa thức sẽ khó có thể xuất hiện Brakedown và sẽ không thể tạo ra các giao thức mới như thuật toán Orion và FOAKS dựa trên Brakedown.

Trong nhiều hệ thống bằng chứng không kiến ​​thức dựa trên các cam kết đa thức, các giao thức cam kết khác nhau được sử dụng. Theo đánh giá của Justin Thaler về a16z trong bài viết "Đo lường hiệu suất SNARK: Giao diện người dùng, phụ trợ và tương lai" vào tháng 8 năm 2022, mặc dù Brakedown có Kích thước bằng chứng lớn hơn nhưng chắc chắn đây là giao thức cam kết đa thức nhanh nhất hiện nay.

FRI, KZG, Bulletproof là các giao thức cam kết đa thức phổ biến hơn, nhưng tốc độ là điểm nghẽn của chúng. Các thuật toán như Plonky được sử dụng bởi zkSync, Plonky 2 được sử dụng bởi Polygon zkEVM và Ultra-Plonk được sử dụng bởi Scroll đều là các cam kết đa thức dựa trên KZG. Prover liên quan đến một số lượng lớn các phép tính FFT và hoạt động MSM tạo ra các đa thức và cam kết, cả hai đều gây ra gánh nặng tính toán lớn. Mặc dù MSM có khả năng chạy tăng tốc đa luồng, nhưng nó đòi hỏi nhiều bộ nhớ và chậm ngay cả khi có tính song song cao, trong khi FFT quy mô lớn phụ thuộc rất nhiều vào việc xáo trộn dữ liệu thường xuyên khi thuật toán đang chạy, gây khó khăn cho việc tải trên các cụm máy tính thông qua khả năng tăng tốc phân tán.

Chính vì giao thức cam kết đa thức nhanh hơn Phanh lại mà độ phức tạp của các hoạt động như vậy được giảm đi rất nhiều.

FOAKS, hay Lập luận khách quan nhanh về kiến ​​thức, là một khung hệ thống bằng chứng không kiến ​​thức dựa trên Brakedown do Fox Tech đề xuất. FOAKS tiếp tục giảm hoạt động FFT trên cơ sở Orion và mục tiêu cuối cùng là loại bỏ FFT. Ngoài ra, FOAKS cũng thiết kế một phương pháp đệ quy bằng chứng mới và rất thanh lịch để giảm kích thước bằng chứng. Ưu điểm của khung FOAKS là nó có kích thước bằng chứng nhỏ dựa trên việc thực hiện thời gian bằng chứng tuyến tính, rất phù hợp với các kịch bản zkRollup.

Dưới đây chúng tôi sẽ giới thiệu chi tiết về giao thức cam kết đa thức Brakedown được sử dụng bởi FOAKS.

Trong mật mã, giao thức cam kết (Commitment) bao gồm người chứng minh (Prover) cam kết một giá trị bí mật nhất định, tạo ra một giá trị cam kết công khai, có ràng buộc và ẩn (Hiding), sau đó trình xác minh cần mở lời hứa này và gửi đi. tin nhắn cho người xác minh để xác minh sự tương ứng giữa lời hứa và tin nhắn. Điều này làm cho các giao thức cam kết và hàm băm có nhiều điểm chung, nhưng các giao thức cam kết thường dựa trên các cấu trúc toán học trong lĩnh vực mật mã khóa công khai. Cam kết đa thức (Cam kết đa thức) là một loại sơ đồ cam kết cho đa thức, nghĩa là giá trị hứa hẹn là một đa thức. Đồng thời, giao thức cam kết đa thức cũng bao gồm một thuật toán để thu được giá trị tại một điểm nhất định và đưa ra bằng chứng, điều này khiến bản thân giao thức cam kết đa thức trở thành một loại giao thức mật mã quan trọng và là phần cốt lõi của nhiều hệ thống bằng chứng không có kiến ​​thức. .

Trong nghiên cứu mới nhất về lĩnh vực mật mã, do phát hiện ra mối liên hệ giữa tích tensor (Tensor Product) và giá trị của đa thức, hàng loạt các giao thức cam kết đa thức liên quan đã ra đời, và Brakedown là một trong những giao thức tiêu biểu. . .

Trước khi giới thiệu chi tiết về giao thức Brakedown, một số điều cơ bản cần được hiểu. Chúng ta cần hiểu hoạt động của Mã tuyến tính, Hàm băm chống xung đột, Cây Merkle, Tích tenxơ và biểu diễn tích tenxơ của các giá trị đa thức.

Đầu tiên là mã tuyến tính (Linear Code). Một mã tuyến tính với độ dài bản tin k và độ dài từ mã n là một không gian con tuyến tính

C ∈ Fn, sao cho có một phép tiêm từ thông báo vào từ mã, được gọi là mã hóa, ký hiệu là EC: Fk→C. Mọi tổ hợp tuyến tính của các từ mã vẫn là một từ mã. Khoảng cách giữa hai từ mã u và v là khoảng cách Hamming của chúng, ký hiệu là △(u, v).

Khoảng cách ngắn nhất là d=minu, v△(u, v). Các mã như vậy được ký hiệu là mã tuyến tính [n, k, d] và d /n biểu thị khoảng cách tương đối của các mã.

Tiếp theo là hàm băm chống va chạm (Hash Function) và cây Merkle (Merkle Tree).

Sử dụng H: { 0, 1 } 2 λ → { 0, 1 } λ để biểu diễn hàm băm. Cây Merkle là một cấu trúc dữ liệu đặc biệt có thể nhận ra lời hứa của 2 tin nhắn d, tạo ra giá trị băm h và cần giá trị băm d+1 khi mở bất kỳ tin nhắn nào.

Cây Merkle có thể được biểu diễn dưới dạng cây nhị phân có độ sâu d, trong đó L phần tử thông báo m1 , m2 ,..., ml tương ứng với các lá của cây. Mỗi nút bên trong của cây được băm từ hai nút con của nó. Khi mở một tin nhắn mi, đường dẫn từ mi đến nút gốc cần được hiển thị.

Mô tả hình ảnh

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

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

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

Hình 1: Cây Merkle

Mô tả hình ảnh

Hình 2: Phép toán tích tenxơ của vectơ và ma trận

Tiếp theo, chúng ta cần biết biểu diễn tích tensor của các giá trị đa thức.

Như đã đề cập trong [GLS+], giá trị của đa thức có thể được biểu diễn dưới dạng tích tensor. Ở đây chúng tôi xem xét các cam kết đa thức đa tuyến.

Cụ thể, cho một đa thức, giá trị của nó trong các vectơ x0 , x1 ,..., xlogN-1 có thể được viết là:

Theo định nghĩa của đa tuyến, bậc của mỗi biến là 0 hoặc 1 nên tồn tại N đơn thức và hệ số, logN biến. làm

, trong đó i0 i1 ...ilogN-1 là biểu diễn nhị phân của i. Đặt w biểu thị các hệ số đa thức,

Tương tự, xác định

làm

. Vậy X=r0 ⊗r1.

Như vậy, giá trị đa thức có thể biểu diễn dưới dạng tích tensor: ϕ(x0 , x1 ,..., xlogN-1 )=。

Cuối cùng, hãy xem quy trình Phanh lại được sử dụng trong FOAKS và Orion [XZS 22 ].

Đầu tiên, PC.Commit chia hệ số đa thức w thành dạng ma trận k×k và mã hóa nó (tham khảo mã tuyến tính trong "Kiến thức sơ bộ"), ký hiệu là C2. Sau đó, thực hiện cam kết với từng cột C2 [:, i] của C2 để xây dựng cây Merkle, sau đó xây dựng một cây Merkle khác cho gốc của cây Merkle được hình thành bởi mỗi cột làm cam kết cuối cùng.

Trong tính toán chứng minh giá trị, cần chứng minh hai điểm, một là tính gần nhau (Proximity), hai là tính nhất quán (Consistency). Xấp xỉ đảm bảo rằng ma trận cam kết thực sự đủ gần với một từ mã được mã hóa. Đảm bảo nhất quán y=。

Kiểm tra độ gần: Kiểm tra độ gần bao gồm hai bước. Đầu tiên, trình xác minh gửi một vectơ ngẫu nhiên 0 đến trình chứng minh và trình chứng minh tính toán sản phẩm bên trong của Y0 và C1, nghĩa là tính toán tổ hợp tuyến tính của các hàng của C1 với thành phần của Y0 làm hệ số. Do thuộc tính của mã tuyến tính, Cy 0 là từ mã của Yy 0 . Sau đó, người chứng minh rằng Cy 0 thực sự được tính toán từ từ mã đã cam kết. Để chứng minh điều này, người xác minh chọn ngẫu nhiên t cột và người xác minh mở cột tương ứng và cung cấp bằng chứng cây Merkle. Trình xác minh kiểm tra xem tích bên trong của các cột này và Y0 có bằng với vị trí tương ứng trong Cy 0 hay không. [BCG 20] chứng minh rằng nếu mã tuyến tính được sử dụng có khoảng cách tương đối không đổi, thì ma trận cam kết gần với một từ mã có xác suất vượt trội (xác suất áp đảo đề cập đến xác suất mà mệnh đề phủ định của mệnh đề là đúng. Bị bỏ qua) .

Kiểm tra tính nhất quán: Quá trình kiểm tra tính nhất quán và kiểm tra độ gần là hoàn toàn giống nhau. Sự khác biệt là vectơ ngẫu nhiên Y0 không được sử dụng nhưng r0 được sử dụng trực tiếp để hoàn thành phần kết hợp tuyến tính. Tương tự, c1 cũng là một mã tuyến tính cho thông điệp y1, và có

ϕ(x)=. Nó được chỉ ra trong [BCG 20 ] rằng, bằng cách kiểm tra tính nhất quán, y=ϕ(x) đúng với xác suất vượt trội nếu ma trận đã cam kết gần với một từ mã.

Ở dạng mã giả, chúng tôi đưa ra quy trình của giao thức 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.

người giới thiệu

người giới thiệu

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. Giới thiệu về sản phẩm tensor: https://blog.csdn.net/chenxy_bwave/article/details/127288938