a16z: Lasso+Jolt triển khai hệ thống SNARK hiệu quả hơn như thế nào?
Tiêu đề gốc: Câu hỏi thường gặp về kỹ thuật về Lasso, Jolt và những tiến bộ gần đây trong thiết kế SNARK
Tác giả gốc:Justin Thaler
Bản tổng hợp gốc: Luccy, BlockBeats
Lưu ý của biên tập viên: Vào ngày 20 tháng 11, Ben Diamond và Jim Posen (DP) của Ulvetanna đã xuất bản một bài báo cải thiện IOP đa thức dựa trên kiểm tra tổng và sơ đồ cam kết Ligero/Brakedown kết hợp các chứng minh nhanh hơn và các bằng chứng lớn hơn, đồng thời tích hợp nó với dựa trên kiểm tra tổng SNARK như Lasso. Sau khi đối tác nghiên cứu của a16z Justin Thaler tiến hành phân tích chuyên sâu về công nghệ, nhiều nhà nghiên cứu đã đặt ra câu hỏi về nội dung bài báo.
Bài đọc liên quan: a16z: Lasso+Jolt, một góc nhìn mới về cam kết nhanh chóng
Câu hỏi thường gặp này tích hợp 13 câu hỏi để trả lời nhiều câu hỏi khác nhau, bao gồm hiệu suất của Jolt Prover, lý do tại sao DP chọn hàm băm Keccak và Grøstl cũng như tính bảo mật của các kế hoạch cam kết dựa trên hàm băm. Ngoài ra, câu trả lời này cũng đề cập đến mối quan hệ cơ bản giữa Lasso và Jolt, lợi thế về hiệu suất của việc sử dụng mã Reed-Solomon, lợi thế của Ligero/Brakedown so với FRI và giải thích về tính kinh tế yếu tố trong cam kết của DP với GF[2].
Trọng tâm thảo luận bao gồm việc triển khai mạch Boolean cho toàn bộ phép tính, các ưu điểm của hai trường đặc trưng cũng như các vấn đề kỹ thuật và chi phí của bằng chứng SNARK thông qua kết hợp đệ quy và kết hợp sơ đồ cam kết DP với SNARK dựa trên đường cong elip. Cuối cùng, bài viết cũng đặt ra câu hỏi liệu SNARK sử dụng sơ đồ cam kết của DP có thể được sử dụng cùng với các sơ đồ gấp như Nova hay không. Nghiên cứu chuyên sâu về những vấn đề này dự kiến sẽ thúc đẩy đổi mới công nghệ và cải tiến hơn nữa trong lĩnh vực này.
Câu hỏi 1: So với việc thực thi tự nhiên các chương trình RISC-V, bạn nghĩ trình chứng minh Jolt sẽ nhanh đến mức nào sau khi Jolt được triển khai lại để sử dụng lời hứa DP?
A：Một ước tính sơ bộ và mang tính suy đoán được cung cấp ở đây. Người chứng minh Jolt hy vọng rằng mỗi bước CPU RISC-V sẽ thực hiện khoảng 800 bit dữ liệu, sử dụng các kiểu dữ liệu 32 bit và phần mở rộng nhân. Hai điều cần lưu ý: Thứ nhất, một số lệnh RISC-V được xử lý thông qua nhiều lệnh giả. Ví dụ: hướng dẫn chia hoạt động bằng cách cho phép người chứng minh cung cấp phần còn lại và xác minh cả hai thông qua kiểm tra nhân, cộng và bất đẳng thức. Thứ hai, ước tính con số này có thể được điều chỉnh một chút sau khi chúng tôi phân tích bảng tra cứu của GF [2128].
Sử dụng sơ đồ cam kết của DP và giả định rằng đệ quy sẽ không trở thành nút cổ chai, chi phí cam kết chính trong tính toán bước T như sau.
Đầu tiên, một FFT bổ sung được áp dụng cho tổng cộng khoảng 200 Tbyte dữ liệu. Chính xác hơn, trình chuẩn Ligero/Brakedown thực hiện các FFT độc lập O(√T) có kích thước O(√T) (bao gồm tổng công việc ít hơn và có thể song song tốt hơn) so với việc thực thi các FFT độc lập O(√T) có độ dài Một FFT duy nhất có O(T)). Thứ hai, khoảng 200 terabyte được băm bằng hàm băm tiêu chuẩn như Keccak hoặc SHA 2.
Theo kinh nghiệm, DP nhận thấy rằng FFT và hàm băm gần như bằng nhau về thời gian chứng minh.
Bằng cách sử dụng hàm băm Keccak, ước tính khoảng 70 chu kỳ RISC-V trên mỗi byte cho thấy rằng các hoạt động này sẽ chậm hơn khoảng 30.000 lần so với việc chỉ chạy một chương trình RISC-V chưa được chứng minh. Nói cách khác, để chứng minh rằng bộ chuẩn Jolt đã chạy đúng chương trình RISC-V Ψ, bản thân bộ chuẩn (được triển khai trong RISC-V) sẽ yêu cầu số chu kỳ nhiều hơn ít nhất 20.000 lần so với chính Ψ.
Các chi phí cam kết này đủ nhanh để cho thấy rằng nút thắt cổ chai của người chứng minh có thể nằm ở các hoạt động miền hạn chế mà nó thực hiện trong toàn bộ giao thức kiểm tra, thậm chí cho phép tối ưu hóa trên các miền tính năng nhỏ. Vì vậy, theo ước tính sơ bộ, tôi đoán rằng bộ chuẩn Jolt (được triển khai trong RISC-V) sẽ chậm hơn khoảng 50.000 lần so với việc chỉ chạy chương trình RISC-V.
Toàn bộ phép tính này hơi vô lý: khó có khả năng chính bộ chứng minh sẽ được triển khai trong RISC-V khi Jolt được triển khai. Nhưng nó đưa ra ý tưởng chung về cách ước tính chi phí của bộ chuẩn zkVM.
Mặc dù mức giảm 50.000 lần có vẻ rất lớn nhưng nó nhanh hơn 20 lần so với mức tăng trưởng 1 triệu lần mà tôi đã lạc quan ước tính khoảng 18 tháng trước. Lý do chính cho sự cải tiến này là dữ liệu lời hứa được Lasso và Jolt mở khóa nhỏ hơn (và kích thước nhỏ hơn của mỗi giá trị lời hứa). Phần còn lại là do các sơ đồ cam kết tốt hơn (ví dụ: cải thiện khả năng sử dụng các hàm băm nhanh và khai thác kích thước nhỏ của các giá trị cam kết trong SNARK dựa trên hàm băm).
Câu 2: DP cung cấp SNARK nhanh cho Keccak và Grøstl. Tại sao các hàm băm này được chọn? Những hàm băm nào khác phù hợp với những kỹ thuật này? BlockBeats Lưu ý: Grøstl là hàm băm mật mã
A：Keccak/SHA 3 là một lựa chọn hiển nhiên vì nó là nút thắt cổ chai chính đối với tiêu chuẩn NIST, quá trình biên dịch trước Ethereum và zkEVM Loại 1. SHA 3 là tiêu chuẩn chính thức của NIST và Keccak là Ethereum được biên dịch sẵn, chúng độc lập với chi phí SNARK.
DP cân nhắc Grøstl vì nó sẽ dẫn đến việc chứng minh nhanh hơn trong khi vẫn duy trì được nhiều lợi thế của Keccak. Đặc biệt, Grøstl đã chịu được sự giám sát chặt chẽ của nhà phân tích mật mã, mặc dù cuối cùng nó không được chọn vì nó đã lọt vào vòng cuối cùng của cuộc thi SHA-3 của NIST và sử dụng hộp S AES. Nhờ hướng dẫn tăng tốc AES AES-NI, Grøstl thậm chí còn chạy nhanh hơn Keccak trên chip Intel.
Bộ chuẩn của DP phải nhanh hơn đối với Grøstl so với Keccak vì Grøstl về cơ bản được xác định nguyên gốc trên GF [28], có nghĩa là bộ chuẩn của DP có thể cam kết với ít thành phần miền hơn Keccak. (Xem Q 9 để biết chi tiết về cách điều này mang lại lợi ích cho người hoạt động.) Nhìn chung, Grøstl sẽ phù hợp hơn với SNARK (đệ quy) so với Keccak, vì nó nhanh hơn cả trên người hoạt động và trên chip.
SNARK của DP không liên quan gì đến Keccak và Grøstl. Những kỹ thuật này có thể áp dụng được cho nhiều hàm băm khác. Ví dụ, DP tin rằng SHA 2 cũng sẽ tốt như Keccak, nhưng vẫn chưa nghiên cứu chi tiết.
Câu 3: Tôi nghĩ Lasso/Jolt là một giải pháp cam kết dựa trên đường cong elip?
A：Không, Lasso và Jolt không nhắm mục tiêu cụ thể vào các chương trình cam kết dựa trên đường cong. Nhưng trong trường hợp của vài tháng trước, so với công việc trước, ưu điểm của chúng thể hiện rõ nhất khi được sử dụng kết hợp với những lời hứa dựa trên đường cong. Điều này là do các cam kết dựa trên đường cong phải trả giá đặc biệt cao khi người chứng minh phải cam kết với các phần tử miền ngẫu nhiên, do đó, khả năng mới lạ của Lasso/Jolt nhằm tránh điều này có hiệu suất hấp dẫn nhất khi các cam kết này được sử dụng Ảnh hưởng.
Nói tóm lại, mặc dù chưa có ai từng thiết kế SNARK dựa trên những lời hứa về đường cong để tận dụng các giá trị nhỏ được hứa hẹn, nhưng ở một mức độ nào đó đã có những lời hứa dựa trên hàm băm hoạt động trên các trường nhỏ tận dụng lợi thế này.
Tuy nhiên, ngay cả khi sử dụng các lời hứa dựa trên hàm băm, Lasso và Jolt vẫn cải thiện công việc trước đó ở cả hai khía cạnh. Đầu tiên, DP cho thấy các cam kết dựa trên hàm băm có thể được hưởng lợi từ việc chỉ có các yếu tố miền nhỏ được cam kết mạnh mẽ hơn các phương pháp đã biết trước đây. Ví dụ: trong khi các kế hoạch cam kết ngày nay phải chịu cùng một chi phí chứng minh cho việc cam kết giá trị 1 bit cũng như đối với giá trị 32 bit, thì kế hoạch của DP rẻ hơn gần 32 lần khi cam kết giá trị 1 bit. Thứ hai, Lasso và Jolt không chỉ đảm bảo rằng người chứng minh chỉ cam kết với các phần tử miền nhỏ mà còn đảm bảo rằng người chứng minh cam kết với ít phần tử miền hơn so với SNARK không dựa trên kiểm tra tổng. Trên thực tế, trong Jolt, chúng tôi đã tính toán cẩn thận tổng độ phức tạp bit của tất cả các phần tử miền hứa hẹn và xác nhận rằng nó nhỏ hơn nhiều so với công việc được thực hiện trong các zkVM hiện có.
Khi Lasso/Jolt được phát hành cách đây vài tháng, một trục trặc kỹ thuật khác đã khiến các cam kết dựa trên đường cong trở nên nổi bật: sơ đồ cam kết dựa trên hàm băm duy nhất có kích thước chứng minh đa thức log, FRI, dành cho đa thức một biến, Lasso/Jolt sử dụng đa thức đa tuyến tính . Một số phép biến đổi được biết là có khả năng điều chỉnh FRI theo các sơ đồ cam kết phù hợp với đa thức đa tuyến tính, nhưng những phép biến đổi này làm tăng thêm chi phí về thời gian chứng minh, kích thước chứng minh hoặc cả hai mà chúng tôi cho là rất không mong muốn. BaseFold hiện cho phép các cam kết đa tuyến tính trực tiếp với kích thước bằng chứng đa thức log, mặc dù bằng chứng thu được chậm hơn so với Brakedown và lớn hơn FRI.
Không giống như FRI, sơ đồ cam kết Ligero/Brakedown áp dụng trực tiếp cho đa thức đa tuyến tính và có bộ chứng minh rất nhanh. Nhưng trước đây, việc áp dụng đệ quy để giảm kích thước bằng chứng của nó là rất khó vì các trình xác thực đã thực hiện một số lượng lớn các phép toán băm, khiến cho việc đệ quy trở nên tốn kém. Công việc của DP sẽ giảm đáng kể chi phí của phép đệ quy này bằng cách cung cấp SNARK nhanh hơn cho hàm băm.
Câu hỏi 4: Không phải bạn đã nói rằng sơ đồ cam kết dựa trên đường cong nhanh hơn sơ đồ dựa trên hàm băm (khi chỉ hứa hẹn các giá trị nhỏ, chẳng hạn như Lasso/Jolt) phải không? Điều này có mâu thuẫn với sự chứng thực của bạn đối với SNARK của DP không?
A：Đầu tiên, như tôi đã nói trước đây, có một số tình huống ứng dụng SNARK quan trọng trong đó SNARK dựa trên hàm băm rõ ràng không phải là lựa chọn hoạt động tốt nhất, vì sẽ hợp lý khi hoạt động trên miền cơ bản của nhóm đường cong elip. Lời hứa dựa trên đường cong sẽ nhanh hơn khi sử dụng các miền này. Việc chứng minh bất kỳ tuyên bố nào về hệ thống mật mã đường cong elip (bao gồm kiến thức về chữ ký số ECDSA cho phép giao dịch blockchain) đều thuộc loại này.
Thứ hai, ngay cả trong các ứng dụng sử dụng hợp lý các miền tính năng nhỏ, việc so sánh hiệu suất của các lược đồ dựa trên hàm băm và dựa trên đường cong rất phức tạp. Ví dụ, nó phụ thuộc rất nhiều vào tốc độ của hàm băm được sử dụng trong sơ đồ dựa trên hàm băm. Ngày nay, nhiều dự án (nhưng không phải tất cả) sử dụng hàm băm chậm hơn, chẳng hạn như Poseidon, để triển khai đệ quy. Sử dụng hàm băm như vậy, các lược đồ dựa trên hàm băm chậm hơn đáng kể so với các lược đồ dựa trên đường cong khi cam kết với các giá trị nhỏ (chẳng hạn như Lasso/Jolt). Ngay cả với các hàm băm nhanh, không rõ liệu chúng có nhanh hơn hay không (như nhận xét trước đây của tôi đã nêu).
Tuy nhiên, DP tăng tốc các cam kết dựa trên hàm băm, giúp chúng hiệu quả hơn khi sử dụng các miền có đặc điểm 2 và cho phép người chứng minh khai thác tốt hơn quy mô nhỏ của các giá trị cam kết, so với các sơ đồ dựa trên hàm băm hiện có như FRI). Vì vậy, kỳ vọng hiện tại của tôi là trên các miền có đặc điểm 2, Ligero/Brakedown sẽ là con đường phía trước, trừ khi được chứng minh khác với các định nghĩa cục bộ trên các miền hữu hạn.
Tóm lại, cho đến ngày nay, lý do chính khiến các sơ đồ cam kết dựa trên hàm băm thường được coi là nhanh hơn các sơ đồ dựa trên đường cong là vì các SNARK phổ biến như Plonk yêu cầu người chứng minh cam kết với các phần tử miền ngẫu nhiên thay vì các phần tử miền nhỏ, trong khi ở Trong trường hợp này, giải pháp hứa hẹn dựa trên đường cong rất chậm. Lasso và Jolt đã chỉ ra rằng người chứng minh không cần phải cam kết với các phần tử miền ngẫu nhiên. Trong trường hợp này, sự so sánh ít nhất có nhiều sắc thái hơn. Cho đến ngày nay, các giải pháp dựa trên đường cong thực sự nhanh hơn, nhưng với những cải tiến của DP, tình hình đã đảo ngược (ngoại trừ khi được xác định cục bộ trên một miền lớn).
Câu hỏi 5: Không phải bạn đã nói rằng chương trình cam kết dựa trên hàm băm kém an toàn hơn sao?
A：Vốn dĩ không có gì là không an toàn về các chương trình cam kết dựa trên hàm băm như FRI hoặc Ligero/Brakedown. Tuy nhiên, các dự án thường ưu tiên hiệu suất hơn bảo mật bằng cách triển khai FRI trên các cấu hình mà các cuộc tấn công đã biết gần như khả thi và giả định rằng các cuộc tấn công đã biết vào FRI này là tối ưu.
Một lợi ích của sơ đồ cam kết Ligero/Brakedown là phỏng đoán chính về FRI, cụ thể là tính bảo mật của giả thuyết tại các tham số liền kề bên ngoài giới hạn Johnson, không liên quan, do đó các nhà thiết kế SNARK không có động cơ sử dụng nó để phỏng đoán dựa trên bảo mật. .
Tương tự như vậy, từ lâu tôi đã lo ngại về việc sử dụng các hàm băm có vẻ thân thiện với SNARK (chẳng hạn như Poseidon) trong quá trình triển khai SNARK. Tính bảo mật của các hàm băm này (ngay cả những hàm tồn tại lâu nhất) nhận được ít sự giám sát kỹ lưỡng hơn nhiều so với các hàm băm tiêu chuẩn như Keccak.
Trong cả hai trường hợp, tôi tin rằng dự án đã làm tổn hại đến tính bảo mật bằng cách che đậy những thiếu sót về hiệu suất SNARK ngày nay. Cách dễ nhất để loại bỏ những thực tiễn này là chỉ cần phát triển SNARK hoạt động tốt hơn.
Liên quan, tôi tin rằng thực tiễn hiện nay về thiết kế thủ công các máy ảo (VM) thân thiện với SNARK và các hệ thống ràng buộc triển khai các VM này là một vấn đề bảo mật nghiêm trọng (và tiêu tốn rất nhiều tài nguyên của nhà phát triển) vì việc thiết kế các hệ thống ràng buộc và bắt đầu từ Trình biên dịch mới phát triển ngôn ngữ cấp cao thành Máy ảo tùy chỉnh Mã hội có tính chất dễ bị lỗi. Tôi hy vọng Jolt sẽ làm cho phương pháp này trở nên lỗi thời bằng cách chỉ ra rằng các bộ hướng dẫn tiêu chuẩn thực sự thân thiện với SNARK như nhau và loại bỏ mọi nhu cầu hoặc khuyến khích đối với các hệ thống ràng buộc kỹ sư thủ công thực hiện các bộ hướng dẫn này.
Cách để loại bỏ một phương pháp có tác động tiêu cực đến bảo mật là đưa ra các SNARK hiệu suất cao hơn khiến phương pháp đó không còn phù hợp nữa.
Câu hỏi 6: DP đã sử dụng mã Reed-Solomon khi triển khai sơ đồ cam kết đa thức, nhưng Brakedown có thể sử dụng bất kỳ mã nào. Có đáng để khám phá các mã khác để có được lợi thế về hiệu suất không?
A：Đúng.
Câu 7: Ligero/Brakedown có lợi cho người chứng minh hơn FRI ở điểm nào?
A：Thời gian chứng minh được cải thiện đáng kể của DP khi cam kết với các giá trị rất nhỏ là duy nhất đối với Ligero/Brakedown, ít nhất là ở thời điểm hiện tại. Ngoài ra: DP không chỉ cải thiện thời gian của bộ chuẩn khi cam kết các giá trị nhỏ mà còn cải thiện không gian của bộ chuẩn. Đây là một nút thắt cổ chai lớn, đặc biệt đối với SNARK dựa trên hàm băm. Ví dụ: bộ chứng minh zkEVM của Polygon ngày nay yêu cầu hơn 250 GB để chứng minh một mạch xử lý một lô giao dịch khoảng 10 triệu gas.
Ligero/Brakedown mang lại sự linh hoạt cao hơn trong việc sử dụng mã sửa lỗi. Trên thực tế, nhiều cải tiến của DP trong việc cam kết các giá trị nhỏ có thể đạt được chỉ bằng cách sử dụng mã nối bên trong Ligero/Brakedown.
Khi sử dụng mã Reed-Solomon, bộ chứng minh Ligero/Brakedown thực hiện nhiều FFT nhỏ thay vì một FFT lớn. Điều này giúp tiết kiệm gấp đôi thời gian chạy FFT và phù hợp hơn cho việc song song hóa.
Ở cấp độ kỹ thuật, FRI cũng yêu cầu thực hiện cả FFT và IFFT (về mặt kỹ thuật, điều này là do FRI thực sự cần đánh giá đa thức đã cam kết ở nhiều điểm). Người chứng minh Ligero/Brakedown có thể bỏ qua IFFT (ở cấp độ kỹ thuật, bỏ qua IFFT xuất phát từ tính linh hoạt vượt trội của Ligero/Brakedown trong việc chọn mã sửa lỗi). Nếu bạn sử dụng hệ số lạm phát Reed-Solomon là 2 (là hệ số lạm phát giúp tối ưu hóa thời gian của người hoạt ngôn), điều này có thể tiết kiệm thêm 33% thời gian của người hoạt ngôn.
Bằng chứng đánh giá của Ligero/Brakedown không yêu cầu người chứng minh thực hiện băm Merkle bổ sung. Nhưng FRI yêu cầu, mặc dù hầu hết các yêu cầu của FRI đều khấu hao chi phí đánh giá bằng chứng đối với nhiều đa thức đã cam kết.
Câu hỏi 8: Bạn có thể phác thảo cách DP đảm bảo rằng các phần tử GF[2] đã cam kết rẻ hơn các phần tử GF[2^2] đã cam kết, rẻ hơn các phần tử GF[2^4] đã cam kết, v.v. không?
A：Thời gian để người chuẩn hóa cam kết với một loạt giá trị bằng cách sử dụng sơ đồ cam kết của DP gần như chỉ phụ thuộc vào tổng số bit cần thiết để chỉ định các giá trị, trong đó b bit được sử dụng để chỉ định các giá trị trong khoảng từ 0 đến 2b. Chi phí chứng minh bổ sung trong SNARK của DP sẽ tăng theo số lượng phần tử trường được sử dụng để mã hóa các bit đó (xem # 9 bên dưới để biết chi tiết). Đây là cách DP đạt được điều này.
Sơ đồ cam kết đa thức của Brakedown mã hóa một vectơ con của các giá trị được cam kết bằng cách sử dụng bất kỳ mã sửa lỗi bắt buộc nào. Giả sử nhóm giá trị được cam kết nằm trong GF[2], nhưng chúng tôi muốn bản thân mã hóa hoạt động trên miền lớn hơn GF[2^16]. Có nhiều lý do kỹ thuật khiến chúng tôi muốn làm điều này, trên thực tế nó là cần thiết nếu chúng tôi muốn áp dụng một số mã hóa cho các vectơ có độ dài lên tới 216.
Để đạt được điều này, chúng ta có thể chỉ cần sử dụng phép nối mã, bao gồm việc chia tất cả các giá trị GF[ 2 ] thành các phần có kích thước 16 và đóng gói từng đoạn gồm 16 giá trị GF[ 2 ] vào một GF[ 2 ] duy nhất ^ 16 ] phần tử trường. Điều này sẽ làm giảm số lượng phần tử trường được cam kết theo hệ số 16. Sau đó chúng ta có thể áp dụng bất kỳ mã sửa lỗi nào hoạt động trên trường GF[2^16], đây được gọi là mã nước ngoài. Sau đó, mỗi ký hiệu của từ mã thu được có thể được giải nén thành 16 phần tử GF[2] và kết quả được mã hóa bằng cách sử dụng mã bên trong được xác định trên GF[2].
Về mặt hiệu quả, phương pháp nối làm giảm độ dài của vectơ cam kết (được đo bằng số phần tử trường) theo hệ số 16, nhưng yêu cầu người chuẩn thực hiện các thao tác đóng gói và giải nén cũng như áp dụng mã bên trong.
Cách tiếp cận đơn giản này, áp dụng Brakedown bằng cách sử dụng các mã nối, đã nhận ra nhiều lợi ích của công việc DP. Nhưng DP thực hiện một cách tiếp cận khác, dẫn đến những bằng chứng nhanh hơn (với chi phí cho những bằng chứng lớn hơn một chút). Ví dụ, cách tiếp cận thực tế của DP tránh được chi phí áp dụng mã bên trong cho mỗi ký hiệu được giải nén của từ mã bên ngoài.
Câu 9: Vì sơ đồ cam kết của DP khiến cho việc cam kết các giá trị trong { 0, 1 } trở nên rất rẻ, tại sao người chứng minh không chỉ cam kết phân tách theo bit của tất cả các giá trị xuất hiện trong tính toán? Đó là, tại sao không thực hiện toàn bộ phép tính bằng mạch Boolean và để SNARK gán phần tử trường hoàn chỉnh cho từng bit đầu vào và cổng trong mạch?
A：Trong SNARK dành cho Keccak của họ, DP có cam kết của người chứng minh chỉ với các giá trị trong { 0, 1 }, nhưng đây không hẳn là một ý tưởng hay trong trường hợp chung.
Thật vậy, thời gian cam kết của DP gần như tỷ lệ thuận với tổng độ phức tạp bit của tất cả các giá trị đã cam kết, không phụ thuộc vào số lượng phần tử trường mà các giá trị đó được trải rộng (đó là lý do tại sao chỉ cam kết với các giá trị một bit là hợp lý). trong ý tưởng SNARK của Keccak).
Tuy nhiên, điều này không có nghĩa là mọi chi phí đều độc lập với số lượng phần tử trường đã cam kết. Cụ thể, quy mô của bằng chứng đánh giá của một sơ đồ cam kết tỷ lệ thuận với (căn bậc hai của) số phần tử trường cam kết.
Một chi phí khác tỷ lệ thuận với số lượng phần tử trường đã cam kết là số lượng thuật ngữ cần được tính tổng trong một số ứng dụng của giao thức kiểm tra tổng trong SNARK của DP. Nói một cách đại khái, cam kết số phần tử trường gấp x lần có nghĩa là việc kiểm tra tổng chứng minh rằng số số hạng cần được tính tổng gấp x lần. Có một số tối ưu hóa có sẵn để giảm thiểu chi phí này, nhưng việc giảm thiểu này không hoàn hảo. Nghĩa là, việc kiểm tra tổng có thể vẫn chậm hơn, ngay cả đối với các giá trị x một bit, so với việc cam kết sau khi đóng gói các giá trị vào một phần tử trường x bit duy nhất.
DP giảm thiểu chi phí sau này khi thực hiện nhiều giá trị một bit bằng cách cung cấp giao thức dựa trên kiểm tra tổng, gói nhiều giá trị một bit vào một phần tử trường duy nhất sau khi chúng được cam kết. Điều này cho phép họ về mặt kỹ thuật tránh phải trả giá bằng quá nhiều thời gian chứng minh kiểm tra tổng cho nhiều giá trị đã cam kết, trong khi vẫn có thể tận hưởng các lợi ích của mình (đặc biệt khi các cam kết phân tách bit được chứng minh bằng kiểm tra tổng, Một số hoạt động nhất định như bitwise AND làm không phải chịu thêm bất kỳ chi phí cam kết nào khi chứng minh được).
Câu hỏi 1 0: Lợi ích cụ thể của việc sử dụng các lĩnh vực DP có đặc điểm thứ hai là gì?
A：Có rất nhiều, đây là một số ví dụ.
DP đã tận dụng rộng rãi việc xây dựng hiện trường tháp. Trong bối cảnh các trường có đặc số 2, điều này đề cập đến việc xây dựng GF[22] dưới dạng mở rộng bậc hai của GF[2], sau đó xây dựng GF[24] dưới dạng mở rộng bậc hai của GF[4], rồi xây dựng GF[28 ] dưới dạng mở rộng bậc hai của GF[24], v.v. Đặc biệt đối với các lĩnh vực có đặc điểm thứ hai, người ta biết rằng đã có những công trình xây dựng tháp rất hiệu quả.
Giao thức kiểm tra tổng tính toán ∑x∈ 0, 1 ^ng(x) cho đa thức đa biến g. Kích thước của siêu khối Boolean { 0, 1 }n (và các khối con của nó) là lũy thừa của 2, do đó các trường con được căn chỉnh tốt với các khối con. DP tận dụng lợi thế này và giúp dễ dàng đóng gói nhiều phần tử trường nhỏ thành một phần tử duy nhất của trường mở rộng lớn hơn.
DP hiện sử dụng mã hóa Reed-Solomon trong sơ đồ cam kết đa thức Ligero/Brakedown. Mã hóa Reed-Solomon hiệu quả yêu cầu FFT bổ sung, rất hiệu quả trong các trường có đặc tính là hai, nhưng không tốt lắm trong các trường khác. Tuy nhiên, việc sử dụng các bảng mã khác hoàn toàn có thể tránh được nhu cầu sử dụng FFT.
Các trường có đặc điểm hai được xử lý tốt trong phần cứng thực. Máy tính trong thế giới thực dựa trên các loại dữ liệu có kích thước bằng hai. Bạn có thể điều chỉnh thông tin lớn nhất một cách hoàn hảo trong các thanh ghi, dòng bộ đệm, v.v. mà không cần đệm. Intel thậm chí còn tích hợp vào các hướng dẫn nguyên thủy của chip (Hướng dẫn mới của trường Galois [GFNI]) để thực hiện số học đặc biệt nhanh trong GF [28]. Khi sử dụng cấu trúc tháp, điều này có thể được sử dụng để thực hiện số học GF[2k] rất nhanh, ngay cả khi k > 8.
Câu hỏi 1 1: Có thể bằng cách sử dụng sơ đồ cam kết của DP để kết hợp đệ quy bằng chứng SNARK với chính nó, không có bằng chứng SNARK nào trở nên ít bị ràng buộc hơn không?
A：Có, ngưỡng đệ quy đối với SNARK sử dụng cam kết Ligero/Brakedown là tương đối cao. Ngưỡng đệ quy đề cập đến kích thước của bằng chứng sao cho không thể tạo ra bằng chứng ngắn hơn bằng cách áp dụng đệ quy SNARK dựa trên Brakedown/Ligero cho trình xác minh. Tôi hy vọng ngưỡng đệ quy sẽ ở mức vài MB.
Nếu bạn muốn có được một bằng chứng nhỏ hơn, tôi nghĩ có thể đạt được điều đó bằng cách kết hợp SNARK với các bằng chứng nhỏ hơn khác. Vui lòng tham khảo Q1 2 để biết thêm chi tiết. Nếu giả định này hóa ra là sai, thì nó không nên được coi là thất bại của Binius mà là lời buộc tội chống lại khả năng mở rộng của SNARK phổ biến ngày nay. Làm sao chúng ta có thể nói chúng có khả năng mở rộng nếu chúng không thể chứng minh rằng một vài MB dữ liệu đã được băm trong một khoảng thời gian hợp lý?
Dù sao đi nữa, bên cạnh việc giảm kích thước chứng minh, còn có những lý do quan trọng khác để kết hợp đệ quy nhanh. Quan trọng nhất, nó là công cụ chính để kiểm soát các yêu cầu về không gian chứng minh. Vì SNARK (không đệ quy) chiếm nhiều không gian cho bộ chứng minh nên mọi người sẽ chia các phép tính lớn thành các phần nhỏ, chứng minh từng phần riêng biệt và sử dụng bằng chứng đệ quy để xâu chuỗi các phần lại với nhau. SNARK nhanh của DP dành cho các hàm băm tiêu chuẩn (như Keccak) cho phép các bằng chứng đệ quy như vậy được hoàn thành nhanh chóng, ngay cả khi kích thước bằng chứng hơi lớn.
Câu 1 2: Giả sử bạn muốn kết hợp sơ đồ cam kết của DP với SNARK dựa trên đường cong elip (chẳng hạn như Plonk hoặc Groth 16) để giảm chi phí của người xác minh trước khi xuất bản bằng chứng trên chuỗi. Điều này không yêu cầu bằng chứng cho thấy có liên quan đến số học trường không cục bộ phải không? Bởi vì trình xác minh của DP hoạt động trên GF[2^128], trong khi SNARK dựa trên đường cong sử dụng các trường thứ tự nguyên tố lớn.
A：Đúng, đây là một thách thức tiềm tàng, nhưng tôi tin rằng có thể tìm ra giải pháp.
Một khả năng là trước tiên kết hợp với SNARK bằng cách sử dụng sơ đồ cam kết đa thức dựa trên hàm băm với các bằng chứng ngắn hơn (có thể là FRI, được chuyển đổi thành sơ đồ cam kết đa thức đa tuyến tính hoặc BaseFold), sau đó với SNARK dựa trên đường cong để kết hợp. Lưu ý rằng FRI có thể chạy nguyên bản trên các trường thuộc tính năng hai và trên thực tế, trường hợp này đã được xem xét trong bài báo FRI gốc. Các hạn chế SNARK phổ biến hiện nay đối với việc sử dụng các trường này xuất phát từ việc sử dụng IOP đa thức không dựa trên kiểm tra tổng, không giống như chính FRI.
Điều này không loại bỏ vấn đề về số học trường không cục bộ, nhưng nó có thể được giảm bớt ở mức độ lớn, vì đối với các đa thức đủ lớn, trình xác thực FRI thực hiện ít phép toán tổng cộng hơn, đặc biệt là ít phép toán trường hơn so với trình xác thực Ligero/Brakedown thực hiện. .
Câu hỏi 1 3: SNARK sử dụng chương trình cam kết của DP có thể được sử dụng kết hợp với các chương trình gấp như Nova không?
A：Điều này sẽ gặp phải vấn đề tương tự như Q1 2, đó là sơ đồ gấp sử dụng đường cong elip, thường được xác định trên các trường có thứ tự nguyên tố lớn, trong khi sơ đồ cam kết của DP sử dụng các trường có kích thước là lũy thừa của hai.
Tôi hy vọng sẽ đạt được tiến bộ đáng kể về phương án gấp và chúng sẽ đóng một vai trò quan trọng trong các thiết kế SNARK trong tương lai. Tuy nhiên, có thể xảy ra trường hợp chúng không kết hợp tốt với SNARK dựa trên hàm băm trên các trường có tính năng rất nhỏ.
Hiện tại, nên sử dụng các lời hứa và sơ đồ gấp dựa trên đường cong elip khi có các phát biểu liên quan đến định nghĩa cục bộ trên các trường lớn hoặc khi không gian chứng minh là quan trọng (các sơ đồ gấp như Nova vượt trội hơn nhiều trong không gian chứng minh) so với các SNARK khác, đại khái là vì chúng có thể chia các phép tính lớn thành các phần nhỏ hơn nhiều so với các SNARK khác). Trong các trường hợp khác, nên sử dụng sơ đồ dựa trên hàm băm, đặc biệt đối với các trường tính năng nhỏ.
Tương tự như vậy, việc phát triển hơn nữa các sơ đồ gấp trong tương lai có thể khiến chúng vượt xa các sơ đồ dựa trên hàm băm. Trên thực tế, Nova đã nhanh hơn SNARK dựa trên hàm băm thế hệ hiện tại ở một số điểm chuẩn (mặc dù có nhiều tuyên bố rằng SNARK dựa trên hàm băm hiện tại nhanh hơn SNARK dựa trên đường cong).
IOS
Android