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

Ghi chú của người biên tập:

Vào ngày 20 tháng 11, Ben Diamond và Jim Posen (D&P) của Ulvetanna đã xuất bản một bài báo cải thiện IOP đa thức và liên minh dựa trên kiểm tra tổng. Người chứng minh nhanh hơn, cam kết chứng minh lớn hơn lược đồ Ligero/Brakedown và tích hợp nó với SNARK dựa trên kiểm tra tổng (chẳng hạn như Lasso). Sau khi đối tác nghiên cứu của a16z Justin Thaler đưa ra 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 triển vọng 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 và câu trả lời bao gồm hiệu suất của Jolt Prover, Lý do tại sao D&P 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 và các vấn đề khác. Ngoài ra, câu trả lời còn bao gồm 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ế của cam kết của D&P đối với các yếu tố GF[2].

Các vấn đề về kỹ thuật và chi phí của SNARK của đường cong. 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 D&P có thể được sử dụng kết hợp 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.

Q1: Bạn nghĩ Jolt sẽ nhanh như thế nào sau khi Jolt được triển khai lại để sử dụng lời hứa D&P, so với việc thực thi nguyên gốc các chương trình RISC-V?

Đ: 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 yêu cầu người chứng minh cung cấp nhà cung cấp và số dư, đồng thời xác minh cả hai thông qua phép nhân, phép cộng và kiểm tra 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 giải quyết việc phân tách bảng tra cứu của GF[2128].

Sử dụng sơ đồ cam kết của D&P 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, FFT bổ sung được áp dụng cho tổng số ~200T byte 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 200T byte được băm bằng hàm băm tiêu chuẩn như Keccak hoặc SHA2.

Theo kinh nghiệm, D&P 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.

Sử dụng phương pháp băm Keccak, ước tính khoảng 70 chu kỳ RISC-V trên mỗi byte cho thấy các thao tác này sẽ nhanh hơn việc chỉ chạy một chương trình RISC-V chưa được chứng minh Khoảng 30.000 lần Chậm hơn. 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ữu hạn mà nó thực hiện trong toàn bộ giao thức kiểm tra, ngay cả khi xem xét tính năng nhỏ Tối ưu hóa tên miền. Vì vậy, theo ước tính sơ bộ, tôi đoán rằng trình 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ộ tính toán 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 cam kết được Lasso và Jolt mở khóa nhỏ hơn (và kích thước nhỏ hơn của mỗi giá trị cam kết). 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).

Q2: D&P 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ã

Đáp:

D&P 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 ưu điểm 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. Grøstl thậm chí còn chạy nhanh hơn Keccak trên chip Intel nhờ hướng dẫn tăng tốc AES AES-NI.

Chứng minh của D&P sẽ 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 bản trên GF[28], có nghĩa là chứng minh của D&P có thể cam kết với ít thành phần miền hơn Keccak. (Xem Q9 để biết chi tiết về lợi ích của điều này đối với bộ chuẩn.) 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 bộ chuẩn và trên chip.

SARK của D&P 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ụ: D&P tin rằng SHA2 cũng tốt như Keccak, nhưng vẫn chưa nghiên cứu chi tiết.

Q3: Tôi nghĩ Lasso/Jolt là một giải pháp cam kết dựa trên đường cong elip?

Đ: Không, Lasso và Jolt không nhắm mục tiêu cụ thể đến 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, ưu điểm của chúng so với công việc trước đó thể hiện rõ nhất khi 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.

Tóm lại, mặc dù chưa có ai thiết kế SNARK dựa trên đường cong hứa hẹn tận dụng các giá trị nhỏđược cam kết, nhưng ở một mức độ nào đó, đã có Những lời hứa dựa trên Hash hoạt động trên các lĩnh vực nhỏ sẽ 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, D&P 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 phần tử miền nhỏ được cam kết mạnh mẽ hơn các phương tiện đã 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 các giá trị 1 bit như đối với các giá trị 32 bit, thì kế hoạch của D&P rẻ hơn gần 32 lần khi cam kết các 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 thành phần 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 chúng tôi phải nêu bật lời hứa về tính năng dựa trên đường cong: tính năng duy nhất có kích thước bằng chứng đa thức logarit Sơ đồ cam kết dựa trên hàm băm, FRI, dành cho đa thức một biến, trong khi 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 log-đa thức, 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 D&P 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.

Q4: Không phải bạn đã nói rằng các sơ đồ cam kết dựa trên đường cong nhanh hơn các sơ đồ dựa trên hàm băm (khi chỉ các giá trị nhỏ được cam kết, 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 D&P không?

Đáp: Trước hết, như tôi đã nói trước đây, có một số kịch bản ứng dụng SNARK quan trọng và rõ ràng là SNARK dựa trên hàm băm không thân thiện với hiệu suất Sự lựa chọn tốt nhất vì nó hợp lý khi làm việc trên miền cơ sở của nhóm đường cong elip. Khi sử dụng các miền này, lời hứa dựa trên đường cong sẽ nhanh hơn. 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 sơ đồ dựa trên hàm băm và sơ đồ dựa trên đường cong vẫn 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. Với 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ỏ (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, D&P tăng tốc các cam kết dựa trên hàm băm, khiến 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 tốt hơn. giá trị cam kết so với các chương trình 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ỏ và sơ đồ cam kết dựa trên đường cong rất chậm trong trường hợp này. 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 D&P thì điều ngược lại là đúng (ngoại trừ khi được xác định cục bộ trên một miền lớn).

Câu 5: Không phải bạn đã nói rằng kế hoạch cam kết dựa trên hàm băm kém an toàn hơn sao?

Đ: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à độ an toàn của phỏng đoán theo các tham số liền kề bên ngoài giới hạn Johnson, không phải là có liên quan , vì vậy các nhà thiết kế SNARK đã không suy đoán về các biện pháp khuyến khích 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ẻ là "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 các dự án đã làm tổn hại đến tính bảo mật bằng cách che đậy các lỗi về hiệu suất trong 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 máy ảo này là một bước tiến quan trọng vấn đề bảo mật (và tiêu tốn rất nhiều tài nguyên của nhà phát triển) do tính chất dễ xảy ra lỗi khi thiết kế các hệ thống bị hạn chế và phát triển trình biên dịch mới từ ngôn ngữ cấp cao đến mã hợp ngữ cho máy ảo tùy chỉnh. Tôi hy vọng rằ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.

Q6: D&P đã 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?

Đáp: Có.

Q7: Ligero/Brakedown có lợi hơn cho người chứng minh so với FRI về mặt nào?

Đáp: D&P đã cải thiện đáng kể thời gian chứng minh 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 bây giờ. Ngoài ra: D&P 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 đến 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 D&P 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 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.

Về mặt kỹ thuật, FRI cũng yêu cầu cả FFT và IFFT (về mặt kỹ thuật, điều này là do FRI thực sự cần đánh giá các cam kết ở nhiều điểm đa thức). Những người ủng hộ 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 chuẩn), điều này có thể tiết kiệm thêm 33% thời gian chuẩn.

Bằng chứng đánh giá của Ligero/Brakedown không yêu cầu người chứng thực thực hiện các phép 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.

Q8: Bạn có thể phác thảo cách D&P đảm bảo rằng việc cam kết các phần tử GF[2] rẻ hơn so với việc cam kết các phần tử GF[2^2], rẻ hơn so với việc cam kết các phần tử GF[2] cam kết các phần tử GF[2^4] rẻ hơn, v.v.?

A: Thời gian cần thiết để người chứng minh cam kết một loạt giá trị bằng cách sử dụng sơ đồ cam kết của D&P gần như chỉ phụ thuộc vào chỉ định các giá trị này Tổng số bit được yêu cầu, trong đó b bit được sử dụng để chỉ định giá trị trong khoảng từ 0 đến 2b. Chi phí chứng minh bổ sung trong SNARK của D&P 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 D&P thực hiện được điều này.

Lược đồ cam kết đa thức của Brakedown mã hóa các 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 và 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 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 khối có kích thước 16 và đặt mỗi khối 16 GF[2] giá trị "được đóng gói" vào một phần tử trường GF[2^16] duy nhất. Đ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], đượ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].

Một cách 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 chứng minh để thực hiện các thao tác đóng gói và giải nén và áp dụng mã bên trong cho từng ký hiệu (đã giải nén) của từ mã bên ngoài.

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 D&P. Nhưng D&P 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 D&P 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.

Q9: Vì kế hoạch cam kết của D&P khiến việc hứa hẹn các giá trị trong {0,1} trở nên rất rẻ, tại sao không để người chứng minh chỉ hứa với xuất hiện trong phép tính Còn việc phân tách theo bit của tất cả các giá trị thì sao? Đó 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?

Đ: Trong SNARK dành cho Keccak, D&P chỉ cho phép người chứng minh cam kết giá trị {0,1}, nhưng đây không hẳn là một ý tưởng hay nói chung.

Thật vậy, thời gian cam kết của D&P 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ị này được dàn trải (Đây là lý do tại sao cam kết chỉ một bit trong SNARK của Keccak là một ý tưởng hợp lý).

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 biệt, 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à tổng được yêu cầu trong một số ứng dụng của giao thức kiểm tra tổng trong SNARK của D&P Số lượng mục. 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.

D&P giảm bớt vấn đề cam kết 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 các giá trị đó đã được cam kết Chi phí sau. Đ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).

Q10: Lợi ích cụ thể của D&P khi sử dụng các trường có đặc điểm thứ hai là gì?

Đ: Có rất nhiều, đây là một số ví dụ.

D&P đã tận dụng rộng rãi việc xây dựng hiện trường tháp. Trong ngữ cảnh của một 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], sau đó 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^n g(x) cho đa thức g nhiều biến. 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. D&P 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ỏ vào một phần tử duy nhất của trường mở rộng lớn hơn.

D&P hiện đang 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 hiệu quả 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 thứ 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 sức mạnh của 2 loại dữ liệu có kích thước. 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 có các hướng dẫn cơ bản (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] được tích hợp trong chip. 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ả đối với k >

Q11: Bằng cách kết hợp đệ quy một bằng chứng SNARK với chính nó bằng cách sử dụng sơ đồ cam kết của D&P, liệu có có giới hạn nào về mức độ nhỏ của bằng chứng SNARK không?

Đáp:Có, "ngưỡng đệ quy" đối với SNARK sử dụng lời hứa 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 nhận. Tôi hy vọng ngưỡng đệ quy sẽ ở mức vài MB.

Nếu bạn muốn có được 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 Q12 để 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à bản cáo trạng về 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, 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 để soạn thảo đệ 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 D&P 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.

Q12: Giả sử bạn muốn kết hợp sơ đồ cam kết của D&P với SNARK dựa trên đường cong elip (chẳng hạn như Plonk hoặc Groth16) để giảm số lượng người xác minh phát hành Chi phí chứng nhận trước 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 D&P 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.

Đ: Đúng, đây là một thách thức tiềm ẩn, nhưng tôi tin rằng có thể tìm ra giải pháp.

Một khả năng trước tiên là 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, sơ đồ cam kết đa thức đa tuyến tính chuyển đổi hoặc BaseFold), và sau đó kết hợp với SNARK dựa trên đường cong. 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. 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, trái ngược với chính FRI.

Điều này không loại bỏ được 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ổng số phép tính ít hơn, Đặc biệt, nó thực hiện ít thao tác hiện trường hơn trình xác thực Ligero/Brakedown.

Q13: SNARK sử dụng chương trình cam kết của D&P có thể được sử dụng cùng 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ư Q12, đó là sơ đồ gấp sử dụng đường cong elip, thường được xác định trong các trường thứ tự nguyên tố lớn, trong khi sơ đồ cam kết của D&P sử dụng các trường có kích thước là lũy thừa của hai.

Tôi kỳ 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 hứa hẹn dựa trên đường cong elip khi có liên quan đến 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 và các sơ đồ gấp (. các sơ đồ gấp như Nova vượt trội hơn nhiều so với các SNARK khác về mặt không gian chứng minh, đạ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 qua 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 thế hệ hiện tại nhanh hơn SNARK dựa trên đường cong).

「Liên kết gốc‖

Chào mừng bạn tham gia cộng đồng chính thức của BlockBeats:

Nhóm Telegram đăng ký: https://t.me/theblockbeats

Nhóm Telegram thảo luận: https://t.me/BlockBeats_App

Tài khoản Twitter chính thức: https://twitter.com/BlockBeatsAsia