Giải thích chi tiết về hai công cụ SNARK mới được ra mắt bởi a16z crypto

Bài viết này đến từ 16 z, tác giả gốc: Justin Thaler, biên dịch bởi dịch giả Nhật báo Odaily Planet Daily Jessica.

Vào ngày 10 tháng 8, một loại tiền điện tử 16 z đã ra mắt các công cụ mới dựa trên SNARK là Lasso và Jolt, cùng nhau đại diện cho một cách tiếp cận mới đối với thiết kế SNARK có thể cải thiện hiệu suất của các chuỗi công cụ được triển khai rộng rãi theo mức độ lớn hoặc hơn; cung cấp tốt hơn, thuận tiện hơn kinh nghiệm của nhà phát triển và làm cho việc kiểm tra dễ dàng hơn.

SNARK (Lập luận kiến thức không tương tác ngắn gọn) là một giao thức mã hóa, theo đó bất kỳ ai cũng có thể chứng minh với một người xác minh không đáng tin cậy rằng họ biết một "nhân chứng" thỏa mãn các thuộc tính nhất định.

• Một trường hợp sử dụng nổi bật trong Web 3 là để L2 chứng minh với L1 rằng họ biết chữ ký số cho phép một loạt giao dịch, do đó bản thân chữ ký không cần phải được lưu trữ và xác minh bởi mạng L1, cải thiện khả năng mở rộng.
• Các ứng dụng bên ngoài chuỗi khối bao gồm: nhanh chóng chứng minh tính hợp lệ của tất cả các đầu ra được tạo bởi các thiết bị phần cứng không đáng tin cậy, đảm bảo rằng người dùng có thể tin tưởng chúng. Các cá nhân có thể chứng minh một cách không cần biết rằng một cơ quan đáng tin cậy đã cấp cho họ thông tin đăng nhập chứng minh rằng họ đủ tuổi để truy cập nội dung bị giới hạn độ tuổi mà không tiết lộ ngày sinh của họ. Bất kỳ ai gửi dữ liệu được mã hóa qua mạng đều có thể chứng minh với quản trị viên rằng dữ liệu tuân thủ chính sách mạng mà không tiết lộ thêm chi tiết.

Mặc dù nhiều SNARK vẫn là một chi phí hấp dẫn đối với trình xác minh, nhưng SNARK thường vẫn đưa ra khoảng sáu bậc độ lớn của chi phí trong tính toán chứng minh. Công việc bổ sung do người châm ngôn đảm nhận được thực hiện song song cao, nhưng chi phí hoạt động hàng triệu lần đã hạn chế nghiêm trọng phạm vi ứng dụng của SNARK.

**SNARK với nhiều lợi thế hơn về hiệu suất sẽ tăng tốc L 2 và cũng cho phép các nhà phát triển mở khóa các ứng dụng chưa được hình dung. **Đây là lý do tại sao chúng tôi giới thiệu hai công nghệ mới có liên quan: Lasso, một tham số tra cứu mới có thể làm tăng đáng kể chi phí chứng minh; Jolt, sử dụng Lasso để cung cấp một khuôn khổ mới cho cái gọi là zkVM Và một thiết kế giao diện người dùng rộng hơn để thiết kế SNARK. Họ cùng nhau cải thiện hiệu suất, trải nghiệm của nhà phát triển và khả năng kiểm tra của các thiết kế SNARK, từ đó cải thiện các bản dựng trong web 3.

Việc triển khai Lasso ban đầu của chúng tôi đã chứng minh tốc độ tăng hơn 10 lần so với các tham số tra cứu trong chuỗi công cụ SNARK phổ biến halo 2. Khi cơ sở mã Lasso được tối ưu hóa hoàn toàn, chúng tôi mong đợi tốc độ tăng ~40 lần. Jolt bao gồm các cải tiến khác trên Lasso và chúng tôi hy vọng nó sẽ đạt được tốc độ tương tự hoặc tốt hơn so với zkVM hiện có.

Tìm tham số, Lasso và Jolt

Giao diện người dùng SNARK là trình biên dịch chuyển đổi chương trình máy tính thành mạch mà giao diện người dùng SNARK có thể nhập. (Lưu ý: Mạch điện là một mô hình tính toán cực kỳ hạn chế trong đó "các phép toán nguyên thủy" duy nhất khả dụng là phép cộng và phép nhân.)

Một công cụ quan trọng trong các thiết kế SNARK hiện đại là một giao thức được gọi là tham số tra cứu, cho phép một trình chứng minh không đáng tin cậy gửi một vectơ lớn bằng mật mã và sau đó chứng minh rằng mỗi mục nhập của vectơ đó được chứa trong một số bảng được xác định trước. Tham số tra cứu có thể giúp giữ cho các mạch nhỏ bằng cách xử lý hiệu quả các hoạt động không được tính toán một cách tự nhiên bằng các phép cộng và phép nhân nhỏ.

Tuy nhiên, như Barry Whitehat của Ethereum Foundation đã nói vào năm ngoái, "nếu chúng ta có thể xác định hiệu quả các mạch chỉ sử dụng các tham số tra cứu, nó sẽ dẫn đến các công cụ và mạch đơn giản hơn". Mạch chúng tôi thiết kế chỉ thực hiện tra cứu. Theo thời gian, các tham số tra cứu "sẽ trở nên hiệu quả hơn so với các ràng buộc đa thức đối với hầu hết mọi thứ".

Tầm nhìn này hoàn toàn trái ngược với cách mọi thứ hoạt động ngày nay, nơi các nhà phát triển triển khai SNARK bằng cách viết chương trình bằng các ngôn ngữ dành riêng cho miền đặc biệt để biên dịch chương trình thành các ràng buộc đa thức hoặc trực tiếp mã hóa các ràng buộc bằng tay. Chuỗi công cụ này có rất nhiều công việc và cung cấp nhiều diện tích bề mặt cho các lỗi nghiêm trọng về an toàn xâm nhập. Ngay cả với các công cụ và mạch phức tạp, hiệu suất của SNARK vẫn chậm, điều này hạn chế khả năng ứng dụng của chúng.

Lasso và Jolt giải quyết cả ba vấn đề chính: hiệu suất, trải nghiệm của nhà phát triển và khả năng kiểm tra, và họ cùng nhau hiện thực hóa tầm nhìn tìm kiếm điểm kỳ dị. Lasso và Jolt cũng buộc phải suy nghĩ lại về phần lớn sự khôn ngoan đã được chấp nhận trong thiết kế SNARK.

Sau khi cung cấp thông tin cơ bản cần thiết, phần sau đây sẽ xem xét lại một số ý tưởng chung về hiệu suất của SNARK và giải thích cách chúng có thể được tối ưu hóa dựa trên những đổi mới như Lasso và Jolt.

Nền thiết kế SNARK: sao chậm thế?

Hầu hết các chương trình phụ trợ SNARK đều có cam kết mã hóa chứng minh đối với giá trị của từng cổng trong mạch bằng cách sử dụng sơ đồ cam kết đa thức. Sau đó, người chứng minh chứng minh rằng giá trị được gửi thực sự tương ứng với việc thực hiện đúng của người kiểm tra nhân chứng.

Tôi đề cập đến công việc chứng minh từ sơ đồ cam kết đa thức là chi phí cam kết. **SNARK có thêm chi phí bằng chứng từ các chương trình cam kết đa thức. Nhưng chi phí cam kết thường là nút cổ chai. ** Lasso và Jolt cũng vậy. Nếu SNARK được thiết kế trong đó chi phí cam kết không phải là chi phí chứng minh chính, điều đó không có nghĩa là sơ đồ cam kết đa thức là rẻ. Thay vào đó, nó có nghĩa là các chi phí khác cao hơn mức cần thiết.

Theo trực giác, mục đích của các cam kết là tăng cường tính đơn giản của các hệ thống chứng minh bằng mật mã một cách an toàn. Khi một người minh chứng gửi một véc-tơ giá trị lớn, gần như thể người đó đang gửi toàn bộ véc-tơ đó đến người xác minh, giống như các hệ thống bằng chứng thông thường gửi toàn bộ nhân chứng đến người xác minh. Các kế hoạch cam kết có thể đạt được điều này mà không buộc người xác thực phải thực sự nhận toàn bộ nhân chứng—có nghĩa là mục đích của kế hoạch cam kết trong thiết kế SNARK là để kiểm soát chi phí của người xác nhận.

Nhưng các phương pháp mật mã này rất tốn kém đối với người chứng minh, đặc biệt là so với các phương pháp lý thuyết thông tin mà SNARK sử dụng bên ngoài các sơ đồ cam kết đa thức. Các phương pháp lý thuyết thông tin chỉ dựa vào các hoạt động của trường hữu hạn. Và một hoạt động trường nhanh hơn nhiều so với thời gian cần thiết để gửi một phần tử trường tùy ý.

Cam kết điện toán liên quan đến nhiều phép lũy thừa (còn được gọi là phép nhân vô hướng hoặc MSM) hoặc FFT và hàm băm Merkle, tùy thuộc vào lược đồ cam kết đa thức được sử dụng. Lasso và Jolt có thể sử dụng bất kỳ sơ đồ cam kết đa thức nào, nhưng có chi phí đặc biệt hấp dẫn khi khởi tạo bằng cách sử dụng các sơ đồ dựa trên MSM, chẳng hạn như IPA/Bulletproofs, KZG/PST, Hyrax, Dory hoặc Zeromorph.

Tại sao Lasso và Jolt lại quan trọng

Lasso là một tham số tra cứu mới trong đó người tục ngữ hứa hẹn các giá trị ít hơn và nhỏ hơn so với công việc trước đó. Đây có thể là tốc độ tăng tốc gấp 20 lần trở lên, trong đó tốc độ tăng tốc từ 2 đến 4 lần đến từ ít giá trị cam kết hơn và một tốc độ tăng tốc 10 lần khác đến từ thực tế là tất cả các giá trị cam kết trong Lasso đều nhỏ . Không giống như nhiều tham số tra cứu trước đây, Lasso (và Jolt) cũng tránh các FFT chiếm nhiều dung lượng và có thể là nút cổ chai đối với các phiên bản lớn.

Hơn nữa, Lasso hoạt động ngay cả với các bảng lớn, miễn là các bảng đó được "cấu trúc" (theo nghĩa kỹ thuật chính xác). Các bảng này quá lớn để bất kỳ ai cũng có thể triển khai một cách rõ ràng, nhưng Lasso chỉ trả tiền cho các thành phần bảng mà nó thực sự truy cập. Cụ thể—so với các tham số tra cứu trước đó—nếu bảng được cấu trúc, thì không bên nào cần cam kết tất cả các giá trị trong bảng ở dạng mã hóa.

Lasso sử dụng hai khái niệm cấu trúc khác nhau: khả năng phân hủy và cấu trúc LDE. (LDE là từ viết tắt của một khái niệm kỹ thuật có tên là Đa thức mở rộng mức độ thấp.) Khả năng phân tách đại khái có nghĩa là một lần tra cứu bảng có thể được trả lời bằng cách thực hiện một số lượng tra cứu nhỏ hơn trên một bảng nhỏ hơn. Đây là một yêu cầu khắt khe hơn so với cấu trúc LDE, nhưng Lasso đặc biệt hiệu quả khi áp dụng cho các bảng có thể phân tách.

Giật mình

Jolt (Just One Lookup Table) là một giao diện người dùng mới được mở khóa nhờ khả năng sử dụng các bảng tra cứu khổng lồ của Lasso. Jolt nhắm mục tiêu trừu tượng hóa máy ảo/CPU, còn được gọi là Kiến trúc tập lệnh (ISA). SNARK hỗ trợ sự trừu tượng hóa này được gọi là zkVM. Ví dụ, hãy xem xét tập lệnh RISC-V (bao gồm cả phần mở rộng bội số) mà dự án RISC-Zero cũng hướng tới. Đây là một ISA mã nguồn mở phổ biến được phát triển bởi cộng đồng kiến trúc máy tính mà không cần lưu ý đến SNARK.

Đối với mỗi lệnh RISC-V fi, ý tưởng chính của Jolt là tạo một bảng tra cứu chứa toàn bộ bảng đánh giá của fi. Về cơ bản, đối với mọi lệnh RISC-V, bảng tra cứu kết quả có thể phân tách được và áp dụng lasso.

Xem xét lại sự khôn ngoan đã được chấp nhận trong thiết kế SNARK

Lasso và Jolt cũng phá vỡ một số sự khôn ngoan được chấp nhận trong thiết kế SNARK.

** # 1. SNARK diện tích lớn là một sự lãng phí. Mọi người nên sử dụng FRI, Ligero, Brakedown hoặc các biến thể, vì chúng tránh các kỹ thuật đường cong elip thường áp dụng cho quy mô lớn. **

Kích thước trường ở đây gần tương ứng với kích thước của các số xuất hiện trong bằng chứng SNARK. Vì phép cộng và nhân các số rất lớn rất tốn kém nên ý tưởng cho rằng SNARK trên các trường lớn là lãng phí có nghĩa là chúng ta nên cố gắng thiết kế các giao thức không bao giờ có số lớn. Các cam kết dựa trên MSM sử dụng các đường cong elip, thường được xác định trên các trường lớn (có kích thước ~2 256), vì vậy những cam kết này có tiếng là kém hiệu quả.

Việc sử dụng các trường nhỏ có hợp lý hay không (ngay cả khi chúng là một tùy chọn) phần lớn phụ thuộc vào ứng dụng. Lasso và Jolt còn đi xa hơn nữa. Chúng chỉ ra rằng ngay cả với một kế hoạch cam kết dựa trên MSM, công việc của người chứng minh có thể gần như độc lập với quy mô trường. Điều này là do, đối với các cam kết dựa trên MSM, kích thước của các giá trị đã cam kết quan trọng hơn kích thước của các trường chứa các giá trị đó.

SNARK hiện có làm cho người tục ngữ cam kết với nhiều yếu tố trường ngẫu nhiên. Ví dụ: trình chuẩn trong phần phụ trợ SNARK phổ biến có tên là Plonk cam kết khoảng 7 phần tử trường ngẫu nhiên (và các phần tử trường không ngẫu nhiên khác) trên mỗi cổng mạch. Các yếu tố trường ngẫu nhiên này có thể lớn ngay cả khi tất cả các giá trị xuất hiện trong phép tính đã được chứng minh là nhỏ.

Ngược lại, Lasso và Jolt chỉ yêu cầu người chứng minh gửi một giá trị nhỏ (người chứng minh của Lasso cũng gửi ít giá trị hơn tham số tra cứu trước đó). Điều này cải thiện đáng kể hiệu suất của các chương trình dựa trên MSM. Ở mức tối thiểu, Lasso và Jolt nên loại bỏ quan niệm rằng cộng đồng nên từ bỏ các cam kết dựa trên MSM trong trường hợp hiệu suất của người chứng minh có vấn đề.

**#2 Tập lệnh đơn giản hơn dẫn đến zkVM nhanh hơn. **

Độ phức tạp (mỗi lệnh) của Jolt chỉ phụ thuộc vào kích thước đầu vào của lệnh, miễn là bảng đánh giá cho mỗi lệnh có thể phân tách được. Jolt đã chứng minh rằng các lệnh phức tạp đáng ngạc nhiên có thể phân tách được, đặc biệt là tất cả RISC-V.

Điều này trái ngược với niềm tin phổ biến rằng các máy ảo đơn giản hơn (zkVM) nhất thiết phải dẫn đến các mạch nhỏ hơn và các bộ chứng minh nhanh hơn (mỗi bước của VM). Đây là động lực hướng dẫn đằng sau các zkVM đặc biệt đơn giản như Cairo VM, được thiết kế đặc biệt để thân thiện với SNARK.

Trên thực tế, đối với các máy ảo đơn giản hơn, Jolt đạt được chi phí cam kết thấp hơn so với các SNARK trước đó. Ví dụ: để thực thi VM ở Cairo, trình chuẩn SNARK gửi 51 phần tử trường ở mỗi bước của VM. Các SNARK do Cairo triển khai hiện đang hoạt động trên các trường 251 bit (63 bit là giới hạn dưới cứng đối với kích thước trường mà SNARK có thể sử dụng). Prover của Jolt hoạt động trên ~60 phần tử trường mỗi bước (xác định nhiều loại dữ liệu hơn 64 bit) cho CPU RISC-V. Sau khi tính đến thực tế là các phần tử trường đã gửi là nhỏ, chi phí của bộ kiểm chứng Jolt gần tương đương với chi phí gửi 6 phần tử trường 256 bit ngẫu nhiên.

**#3 Không có hình phạt về hiệu năng đối với việc chia các phép tính lớn thành các phần nhỏ. **

Dựa trên quan điểm này, các dự án ngày nay phân tách bất kỳ mạch lớn nào thành các khối nhỏ, chứng minh từng khối riêng biệt và tổng hợp đệ quy các kết quả thông qua SNARK. Những triển khai này sử dụng phương pháp này để giảm bớt tắc nghẽn hiệu suất trong các SNARK phổ biến. Ví dụ: SNARK dựa trên FRI yêu cầu gần 100 GB dung lượng bằng chứng, ngay cả đối với các mạch nhỏ. Chúng cũng yêu cầu FFT, một hoạt động siêu tuyến tính có thể trở thành nút cổ chai nếu SNARK được áp dụng "đồng thời" cho các mạch lớn.

Thực tế là một số SNARK (chẳng hạn như Lasso và Jolt) thể hiện tính kinh tế theo quy mô (chứ không phải tính kinh tế không theo quy mô được tìm thấy trong các SNARK hiện đang được triển khai). Điều này có nghĩa là tuyên bố được chứng minh càng lớn thì chi phí chứng minh càng nhỏ so với việc kiểm tra nhân chứng trực tiếp (nghĩa là công việc cần thiết để đánh giá mạch nhân chứng mà không đảm bảo tính chính xác). Ở cấp độ kỹ thuật, tính kinh tế theo quy mô đến từ hai nơi.

Tăng tốc Pippenger cho các MSM có quy mô n: cải thiện hệ số log(n) so với thuật toán ngây thơ. N càng lớn, cải tiến càng lớn.

Trong các tham số tra cứu chẳng hạn như Lasso, người chứng thực trả chi phí "một lần" phụ thuộc vào kích thước của bảng tra cứu nhưng không liên quan gì đến số lượng giá trị được tra cứu. Chi phí kiểm chứng một lần được khấu hao trong tất cả các lần tra cứu bảng. Khối lớn hơn có nghĩa là tra cứu nhiều hơn, có nghĩa là khấu hao tốt hơn.

Cách phổ biến để xử lý các mạch lớn ngày nay là chia nhỏ mọi thứ thành những phần nhỏ nhất có thể. Ràng buộc chính về kích thước của mỗi phần là chúng không thể nhỏ đến mức chứng minh tập hợp đệ quy trở thành nút cổ chai đối với chứng minh.

Lasso và Jolt đề xuất một cách tiếp cận hoàn toàn ngược lại. Mọi người nên sử dụng SNARK có quy mô kinh tế. Sau đó, chia phép tính lớn thành nhiều phần lớn nhất có thể và lặp lại kết quả. Hạn chế chính về kích thước của mỗi mảnh là không gian bằng chứng, không gian này tăng lên khi mảnh trở nên lớn hơn.

**#4 Các ràng buộc về chiều cao là cần thiết để SNARK hiệu quả. **

Jolt sử dụng R 1 CS làm đại diện trung gian của nó. Không có lợi ích gì khi sử dụng các ràng buộc về Chiều cao hoặc Tùy chỉnh trong Jolt. Hầu hết chi phí của người chứng minh trong Jolt nằm ở việc tra cứu tham số Lasso, thay vì chứng minh tính thỏa đáng của hệ thống ràng buộc kết quả mà việc tra cứu là đương nhiên.

Jolt là phổ quát, vì vậy nó không mất đi tính linh hoạt của nó. Do đó, nó phản ánh sự tập trung cao độ của các nhà phát triển vào các giới hạn chiều cao thiết kế (thường được chỉ định thủ công) nhằm nỗ lực giảm hiệu suất được cải thiện khỏi các SNARK phổ biến hiện nay.

Tất nhiên, một số bối cảnh vẫn có thể được hưởng lợi từ các ràng buộc về chiều cao hoặc tùy chỉnh. Một ví dụ quan trọng là Minroot VDF, có ràng buộc 5 độ có thể giảm chi phí cam kết xuống khoảng 3 lần.

**#5 Các chương trình cam kết đa thức thưa thớt rất tốn kém và nên tránh bất cứ khi nào có thể. **

Đây là lời chỉ trích chính đối với hệ thống kiềm chế được giới thiệu gần đây có tên là CCS và các SNARK hỗ trợ nó - Spartan và Marlin, CCS là sự khái quát rõ ràng của tất cả các hệ thống kiềm chế phổ biến trong thực tế ngày nay.

Lời chỉ trích này là vô căn cứ. Trên thực tế, cốt lõi kỹ thuật của Lasso và Jolt là sơ đồ cam kết đa thức thưa thớt trong Spartan - Spark. Bản thân Spark là một chuyển đổi chung của bất kỳ sơ đồ cam kết đa thức (không thưa thớt) nào sang sơ đồ hỗ trợ đa thức thưa thớt.

Lasso tối ưu hóa và mở rộng Spark để đảm bảo rằng người chuẩn chỉ cam kết với các giá trị "nhỏ", nhưng ngay cả khi không có những tối ưu hóa này thì lời chỉ trích là không chính đáng. Trên thực tế, câu tục ngữ của Spartan cam kết ít phần tử trường (ngẫu nhiên) hơn SNARK (chẳng hạn như Plonk tránh các cam kết đa thức thưa thớt).

Phương pháp của Spartan có thêm các lợi thế về hiệu suất, đặc biệt là đối với các mạch có cấu trúc lặp đi lặp lại. Đối với các mạch này, các cổng bổ sung không thêm vào công việc mã hóa của câu tục ngữ Spartan. Công việc này chỉ phát triển với số lượng biến trong một hệ thống ràng buộc nhất định, không phải với số lượng ràng buộc. Không giống như Plonk, người chứng minh Spartan không cần gửi nhiều "bản sao" khác nhau của cùng một biến.

Chúng tôi lạc quan rằng Lasso và Jolt sẽ thay đổi đáng kể cách thiết kế SNARK, cải thiện hiệu suất và khả năng kiểm tra. Đây là một công cụ quan trọng với khả năng phi thường để giảm thiểu chi phí cam kết của chứng minh.