Phân tích nguyên lý Binius STARKs và những suy nghĩ tối ưu hóa
1 Giới thiệu
Một trong những lý do chính khiến STARKs kém hiệu quả là hầu hết các giá trị trong chương trình thực tế đều nhỏ, nhưng để đảm bảo tính an toàn của chứng minh dựa trên cây Merkle, việc sử dụng mã Reed-Solomon để mở rộng dữ liệu sẽ tạo ra nhiều giá trị dư thừa bổ sung chiếm toàn bộ miền. Để giải quyết vấn đề này, việc giảm kích thước miền trở thành chiến lược then chốt.
Kích thước mã của STARKs thế hệ đầu tiên là 252bit, thế hệ thứ hai là 64bit, thế hệ thứ ba là 32bit, nhưng kích thước mã 32bit vẫn còn nhiều không gian lãng phí. So với điều đó, miền nhị phân cho phép thao tác trực tiếp trên các bit, mã hóa chắc gọn và hiệu quả mà không có không gian lãng phí nào, tức là STARKs thế hệ thứ tư.
Khi sử dụng miền nhỏ hơn, việc mở rộng miền trở nên càng quan trọng để đảm bảo tính an toàn. Miền nhị phân mà Binius sử dụng hoàn toàn phụ thuộc vào việc mở rộng miền để đảm bảo tính an toàn và khả năng sử dụng thực tế. Hầu hết các đa thức liên quan đến phép tính Prover không cần vào miền mở rộng, mà chỉ cần hoạt động trong miền cơ sở, từ đó đạt được hiệu suất cao trong miền nhỏ. Tuy nhiên, kiểm tra điểm ngẫu nhiên và tính toán FRI vẫn cần đi sâu vào miền mở rộng lớn hơn để đảm bảo tính an toàn cần thiết.
Khi xây dựng hệ thống chứng minh dựa trên miền nhị phân, có 2 vấn đề thực tế: Khi tính toán biểu diễn trace trong STARKs, kích thước miền sử dụng phải lớn hơn bậc của đa thức; Khi cam kết Merkle tree trong STARKs, cần thực hiện mã hóa Reed-Solomon, kích thước miền sử dụng phải lớn hơn kích thước sau khi mở rộng mã.
Binius đã đưa ra một giải pháp sáng tạo để xử lý hai vấn đề này, và thực hiện điều đó bằng cách biểu diễn cùng một dữ liệu theo hai cách khác nhau: trước tiên, sử dụng đa thức nhiều biến (cụ thể là đa thức bậc nhiều biến) thay thế cho đa thức một biến, thông qua các giá trị của nó trên "siêu khối" (hypercubes) để biểu diễn toàn bộ quỹ đạo tính toán; thứ hai, do chiều dài của mỗi chiều trong siêu khối đều là 2, nên không thể thực hiện mở rộng Reed-Solomon chuẩn như STARKs, nhưng có thể coi siêu khối như một hình vuông (square), dựa trên hình vuông đó để thực hiện mở rộng Reed-Solomon. Phương pháp này đảm bảo an toàn trong khi nâng cao đáng kể hiệu quả mã hóa và hiệu suất tính toán.
2 Phân tích nguyên lý
Hiện tại, hầu hết các hệ thống SNARKs được xây dựng thường bao gồm hai phần sau:
Chứng minh Oracle tương tác đa thức lý thuyết thông tin (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP)
Sơ đồ cam kết đa thức (Polynomial Commitment Scheme, PCS)
Binius: HyperPlonk PIOP + Brakedown PCS + miền nhị phân. Cụ thể, Binius bao gồm năm công nghệ then chốt để đạt được hiệu quả và an toàn của nó:
Toán học dựa trên miền nhị phân tháp
Phiên bản cải biên của kiểm tra tích và hoán vị HyperPlonk
Chứng minh dịch chuyển đa tuyến mới
Phiên bản cải tiến của lý thuyết tìm kiếm Lasso
Chương trình cam kết đa thức nhỏ
2.1 miền hữu hạn: toán tử hóa dựa trên tháp của các trường nhị phân
Miền nhị phân dạng tháp là chìa khóa để thực hiện tính toán có thể xác minh nhanh chóng, chủ yếu nhờ vào hai khía cạnh: tính toán hiệu quả và tính toán số học hiệu quả. Miền nhị phân về bản chất hỗ trợ các phép toán số học cực kỳ hiệu quả, khiến nó trở thành lựa chọn lý tưởng cho các ứng dụng mật mã nhạy cảm với yêu cầu về hiệu suất. Hơn nữa, cấu trúc miền nhị phân hỗ trợ quy trình số học đơn giản hóa, tức là các phép toán thực hiện trên miền nhị phân có thể được biểu diễn dưới dạng đại số ngắn gọn và dễ xác minh.
Trong trường số nguyên tố Fp, các phương pháp giảm phổ biến bao gồm giảm Barrett, giảm Montgomery, cũng như các phương pháp giảm đặc biệt cho các trường hữu hạn cụ thể như Mersenne-31 hoặc Goldilocks-64. Trong trường nhị phân F2k, các phương pháp giảm thường được sử dụng bao gồm giảm đặc biệt (như trong AES), giảm Montgomery (như trong POLYVAL) và giảm đệ quy (như Tower).
Miền nhị phân không cần phải đưa vào số mang trong các phép toán cộng và nhân, và phép toán bình phương trong miền nhị phân rất hiệu quả, vì nó tuân theo quy tắc đơn giản (X + Y )2 = X2 + Y 2.
2.2 PIOP：Phiên bản cải biên HyperPlonk Product và PermutationCheck
Thiết kế PIOP trong giao thức Binius đã tham khảo HyperPlonk, sử dụng một loạt các cơ chế kiểm tra cốt lõi để xác minh tính đúng đắn của đa thức và tập hợp đa biến. Những kiểm tra cốt lõi này bao gồm:
GateCheck
PermutationCheck
LookupCheck
MultisetCheck
ProductCheck
ZeroCheck
SumCheck
BatchCheck
Binius đã thực hiện những cải tiến sau so với HyperPlonk:
Tối ưu hóa ProductCheck
Xử lý vấn đề chia cho 0
Kiểm tra hoán vị xuyên cột
2.3 PIOP：lập luận dịch chuyển đa tuyến mới
Trong giao thức Binius, việc xây dựng và xử lý đa thức ảo là một trong những công nghệ then chốt, có khả năng tạo ra và thao tác hiệu quả các đa thức phát sinh từ tay cầm đầu vào hoặc các đa thức ảo khác. Dưới đây là hai phương pháp quan trọng:
Đóng gói
Toán tử dịch bit
2.4 PIOP：phiên bản sửa đổi lập luận tìm kiếm Lasso
Giao thức Lasso cho phép bên chứng minh cam kết một vector a ∈ Fm, và chứng minh rằng tất cả các phần tử của nó đều tồn tại trong một bảng đã được chỉ định trước t ∈ Fn. Giao thức Lasso bao gồm ba thành phần sau:
Trừu tượng đa thức ảo của bảng lớn
Tìm kiếm bảng nhỏ
Kiểm tra nhiều tập hợp
Giao thức Binius đã điều chỉnh Lasso cho các thao tác trong miền nhị phân, giới thiệu phiên bản nhân của giao thức Lasso.
2.5 PCS：bản chỉnh sửa Brakedown PCS
Ý tưởng cốt lõi để xây dựng BiniusPCS là packing. Bài báo Binius cung cấp 2 phương án cam kết đa thức Brakedown dựa trên miền nhị phân:
Sử dụng mã nối để khởi tạo
Sử dụng công nghệ mã hóa cấp khối, hỗ trợ sử dụng riêng mã Reed-Solomon.
Binius đa thức cam kết chủ yếu sử dụng các công nghệ sau:
Cam kết đa thức nhỏ và đánh giá miền mở rộng
Cấu trúc chung nhỏ
Mã khối và mã Reed-Solomon
3 Tối ưu hóa suy nghĩ
Để nâng cao hiệu suất của giao thức Binius, bài viết này đề xuất bốn điểm tối ưu chính:
PIOP dựa trên GKR: Đối với phép nhân trong miền nhị phân
Tối ưu hóa ZeroCheck PIOP: Cân nhắc chi phí tính toán giữa Prover và Verifier
Tối ưu hóa PIOP Sumcheck: Tối ưu hóa cho Sumcheck miền nhỏ
Tối ưu PCS: Tối ưu hóa bằng FRI-Binius
3.1 PIOP dựa trên GKR: Phép nhân miền nhị phân dựa trên GKR
Thuật toán nhân số nguyên dựa trên GKR, thông qua việc chuyển đổi "kiểm tra 2 số nguyên 32-bit A và B có thỏa mãn A·B =? C" thành "kiểm tra (gA)B =? gC có đúng không", nhờ giao thức GKR mà giảm đáng kể chi phí cam kết.
3.2 Tối ưu hóa ZeroCheck PIOP: Cân nhắc chi phí tính toán giữa Prover và Verifier
Bài báo "Một số cải tiến cho PIOP cho ZeroCheck" đã đề xuất nhiều phương án tối ưu để điều chỉnh phân phối khối lượng công việc giữa bên chứng minh (P) và bên xác minh (V), nhằm cân bằng chi phí. Các tối ưu chính bao gồm:
Giảm bớt việc truyền dữ liệu của bên chứng minh.
Giảm số lượng điểm đánh giá của bên chứng minh
Tối ưu hóa nội suy đại số
3.3 Tối ưu hóa PIOP Sumcheck: Giao thức Sumcheck dựa trên miền nhỏ
Ingonyama đã đề xuất một giải pháp cải tiến cho giao thức Sumcheck dựa trên miền nhỏ vào năm 2024 và mã nguồn đã được mở. Các tối ưu chính bao gồm:
Ảnh hưởng và yếu tố cải tiến của việc chuyển đổi vòng
Bài báo "Chứng minh Polylogarithmic cho Multilinears trên Tháp Nhị Phân", viết tắt là FRI-Binius, đã triển khai cơ chế gấp FRI trên trường nhị phân, mang lại 4 khía cạnh đổi mới:
Đa thức phẳng
Đa thức biến mất của không gian con
Đóng gói cơ sở đại số
Hoán đổi SumCheck
Nhờ vào FRI-Binius, có thể giảm kích thước chứng minh Binius xuống một bậc.
4 Kết luận
Binius là một giải pháp thiết kế hợp tác "sử dụng phần cứng, phần mềm và giao thức Sumcheck được tăng tốc bằng FPGA", có thể chứng minh một cách nhanh chóng với tỷ lệ sử dụng bộ nhớ rất thấp. Trong Binius, đã cơ bản loại bỏ hoàn toàn nút thắt cam kết của Prover, nút thắt mới nằm ở giao thức Sumcheck, trong đó có rất nhiều vấn đề đánh giá đa thức và phép nhân miền, có thể được giải quyết hiệu quả bằng phần cứng chuyên dụng.
Giải pháp FRI-Binius, là một biến thể của FRI, cung cấp một lựa chọn rất hấp dẫn - loại bỏ chi phí nhúng từ tầng chứng minh miền mà không gây ra sự gia tăng chi phí của tầng chứng minh tổng hợp. Hiện tại, đội ngũ Irreducible đang phát triển tầng đệ quy của họ và thông báo hợp tác với đội ngũ Polygon để xây dựng zkVM dựa trên Binius; JoltzkVM đang chuyển từ Lasso sang Binius để cải thiện hiệu suất đệ quy của nó; đội ngũ Ingonyama đang triển khai phiên bản FPGA của Binius.
Trang này có thể chứa nội dung của bên thứ ba, được cung cấp chỉ nhằm mục đích thông tin (không phải là tuyên bố/bảo đảm) và không được coi là sự chứng thực cho quan điểm của Gate hoặc là lời khuyên về tài chính hoặc chuyên môn. Xem Tuyên bố từ chối trách nhiệm để biết chi tiết.
26 thích
Phần thưởng
26
8
Đăng lại
Chia sẻ
Bình luận
0/400
AirdropF5Bro
· 8giờ trước
Ôi, bây giờ là thời điểm cho Starknet đây.
Xem bản gốcTrả lời0
¯\_(ツ)_/¯
· 08-12 16:41
Tối ưu hóa này quá mạnh mẽ từ 252 sang nhị phân
Xem bản gốcTrả lời0
SerumSquirter
· 08-10 20:16
Hiệu suất ngày càng cao, lĩnh vực ngày càng nhỏ.
Xem bản gốcTrả lời0
GateUser-afe07a92
· 08-10 09:35
Chán quá, tiếp theo
Xem bản gốcTrả lời0
ForkTongue
· 08-10 09:20
Viết thật tốt nhưng chuyên nghiệp thì không hiểu...
Xem bản gốcTrả lời0
NullWhisperer
· 08-10 09:16
hmm... tối ưu hóa trường nhị phân có vẻ lý thuyết thanh lịch nhưng hãy nói về những trường hợp biên trong các phép toán trên trường mở rộng...
Xem bản gốcTrả lời0
HalfBuddhaMoney
· 08-10 09:15
Lâu rồi không dịch lĩnh vực độ rộng bằng không, lần này làm rõ.
Xem bản gốcTrả lời0
NonFungibleDegen
· 08-10 09:08
ser, đồ này thật sự dựa vào... nhị phân = số tăng lên, cuối cùng có một chút alpha thực sự chứ không phải là cái cây merkle này.
Phân tích nguyên lý Binius STARKs: Tối ưu hóa miền nhị phân và cam kết đa thức hiệu quả
Phân tích nguyên lý Binius STARKs và những suy nghĩ tối ưu hóa
1 Giới thiệu
Một trong những lý do chính khiến STARKs kém hiệu quả là hầu hết các giá trị trong chương trình thực tế đều nhỏ, nhưng để đảm bảo tính an toàn của chứng minh dựa trên cây Merkle, việc sử dụng mã Reed-Solomon để mở rộng dữ liệu sẽ tạo ra nhiều giá trị dư thừa bổ sung chiếm toàn bộ miền. Để giải quyết vấn đề này, việc giảm kích thước miền trở thành chiến lược then chốt.
Kích thước mã của STARKs thế hệ đầu tiên là 252bit, thế hệ thứ hai là 64bit, thế hệ thứ ba là 32bit, nhưng kích thước mã 32bit vẫn còn nhiều không gian lãng phí. So với điều đó, miền nhị phân cho phép thao tác trực tiếp trên các bit, mã hóa chắc gọn và hiệu quả mà không có không gian lãng phí nào, tức là STARKs thế hệ thứ tư.
Khi sử dụng miền nhỏ hơn, việc mở rộng miền trở nên càng quan trọng để đảm bảo tính an toàn. Miền nhị phân mà Binius sử dụng hoàn toàn phụ thuộc vào việc mở rộng miền để đảm bảo tính an toàn và khả năng sử dụng thực tế. Hầu hết các đa thức liên quan đến phép tính Prover không cần vào miền mở rộng, mà chỉ cần hoạt động trong miền cơ sở, từ đó đạt được hiệu suất cao trong miền nhỏ. Tuy nhiên, kiểm tra điểm ngẫu nhiên và tính toán FRI vẫn cần đi sâu vào miền mở rộng lớn hơn để đảm bảo tính an toàn cần thiết.
Khi xây dựng hệ thống chứng minh dựa trên miền nhị phân, có 2 vấn đề thực tế: Khi tính toán biểu diễn trace trong STARKs, kích thước miền sử dụng phải lớn hơn bậc của đa thức; Khi cam kết Merkle tree trong STARKs, cần thực hiện mã hóa Reed-Solomon, kích thước miền sử dụng phải lớn hơn kích thước sau khi mở rộng mã.
Binius đã đưa ra một giải pháp sáng tạo để xử lý hai vấn đề này, và thực hiện điều đó bằng cách biểu diễn cùng một dữ liệu theo hai cách khác nhau: trước tiên, sử dụng đa thức nhiều biến (cụ thể là đa thức bậc nhiều biến) thay thế cho đa thức một biến, thông qua các giá trị của nó trên "siêu khối" (hypercubes) để biểu diễn toàn bộ quỹ đạo tính toán; thứ hai, do chiều dài của mỗi chiều trong siêu khối đều là 2, nên không thể thực hiện mở rộng Reed-Solomon chuẩn như STARKs, nhưng có thể coi siêu khối như một hình vuông (square), dựa trên hình vuông đó để thực hiện mở rộng Reed-Solomon. Phương pháp này đảm bảo an toàn trong khi nâng cao đáng kể hiệu quả mã hóa và hiệu suất tính toán.
2 Phân tích nguyên lý
Hiện tại, hầu hết các hệ thống SNARKs được xây dựng thường bao gồm hai phần sau:
Binius: HyperPlonk PIOP + Brakedown PCS + miền nhị phân. Cụ thể, Binius bao gồm năm công nghệ then chốt để đạt được hiệu quả và an toàn của nó:
2.1 miền hữu hạn: toán tử hóa dựa trên tháp của các trường nhị phân
Miền nhị phân dạng tháp là chìa khóa để thực hiện tính toán có thể xác minh nhanh chóng, chủ yếu nhờ vào hai khía cạnh: tính toán hiệu quả và tính toán số học hiệu quả. Miền nhị phân về bản chất hỗ trợ các phép toán số học cực kỳ hiệu quả, khiến nó trở thành lựa chọn lý tưởng cho các ứng dụng mật mã nhạy cảm với yêu cầu về hiệu suất. Hơn nữa, cấu trúc miền nhị phân hỗ trợ quy trình số học đơn giản hóa, tức là các phép toán thực hiện trên miền nhị phân có thể được biểu diễn dưới dạng đại số ngắn gọn và dễ xác minh.
Trong trường số nguyên tố Fp, các phương pháp giảm phổ biến bao gồm giảm Barrett, giảm Montgomery, cũng như các phương pháp giảm đặc biệt cho các trường hữu hạn cụ thể như Mersenne-31 hoặc Goldilocks-64. Trong trường nhị phân F2k, các phương pháp giảm thường được sử dụng bao gồm giảm đặc biệt (như trong AES), giảm Montgomery (như trong POLYVAL) và giảm đệ quy (như Tower).
Miền nhị phân không cần phải đưa vào số mang trong các phép toán cộng và nhân, và phép toán bình phương trong miền nhị phân rất hiệu quả, vì nó tuân theo quy tắc đơn giản (X + Y )2 = X2 + Y 2.
2.2 PIOP：Phiên bản cải biên HyperPlonk Product và PermutationCheck
Thiết kế PIOP trong giao thức Binius đã tham khảo HyperPlonk, sử dụng một loạt các cơ chế kiểm tra cốt lõi để xác minh tính đúng đắn của đa thức và tập hợp đa biến. Những kiểm tra cốt lõi này bao gồm:
Binius đã thực hiện những cải tiến sau so với HyperPlonk:
2.3 PIOP：lập luận dịch chuyển đa tuyến mới
Trong giao thức Binius, việc xây dựng và xử lý đa thức ảo là một trong những công nghệ then chốt, có khả năng tạo ra và thao tác hiệu quả các đa thức phát sinh từ tay cầm đầu vào hoặc các đa thức ảo khác. Dưới đây là hai phương pháp quan trọng:
2.4 PIOP：phiên bản sửa đổi lập luận tìm kiếm Lasso
Giao thức Lasso cho phép bên chứng minh cam kết một vector a ∈ Fm, và chứng minh rằng tất cả các phần tử của nó đều tồn tại trong một bảng đã được chỉ định trước t ∈ Fn. Giao thức Lasso bao gồm ba thành phần sau:
Giao thức Binius đã điều chỉnh Lasso cho các thao tác trong miền nhị phân, giới thiệu phiên bản nhân của giao thức Lasso.
2.5 PCS：bản chỉnh sửa Brakedown PCS
Ý tưởng cốt lõi để xây dựng BiniusPCS là packing. Bài báo Binius cung cấp 2 phương án cam kết đa thức Brakedown dựa trên miền nhị phân:
Binius đa thức cam kết chủ yếu sử dụng các công nghệ sau:
3 Tối ưu hóa suy nghĩ
Để nâng cao hiệu suất của giao thức Binius, bài viết này đề xuất bốn điểm tối ưu chính:
3.1 PIOP dựa trên GKR: Phép nhân miền nhị phân dựa trên GKR
Thuật toán nhân số nguyên dựa trên GKR, thông qua việc chuyển đổi "kiểm tra 2 số nguyên 32-bit A và B có thỏa mãn A·B =? C" thành "kiểm tra (gA)B =? gC có đúng không", nhờ giao thức GKR mà giảm đáng kể chi phí cam kết.
3.2 Tối ưu hóa ZeroCheck PIOP: Cân nhắc chi phí tính toán giữa Prover và Verifier
Bài báo "Một số cải tiến cho PIOP cho ZeroCheck" đã đề xuất nhiều phương án tối ưu để điều chỉnh phân phối khối lượng công việc giữa bên chứng minh (P) và bên xác minh (V), nhằm cân bằng chi phí. Các tối ưu chính bao gồm:
3.3 Tối ưu hóa PIOP Sumcheck: Giao thức Sumcheck dựa trên miền nhỏ
Ingonyama đã đề xuất một giải pháp cải tiến cho giao thức Sumcheck dựa trên miền nhỏ vào năm 2024 và mã nguồn đã được mở. Các tối ưu chính bao gồm:
3.4 PCS Tối ưu: FRI-Binius giảm kích thước bằng chứng Binius
Bài báo "Chứng minh Polylogarithmic cho Multilinears trên Tháp Nhị Phân", viết tắt là FRI-Binius, đã triển khai cơ chế gấp FRI trên trường nhị phân, mang lại 4 khía cạnh đổi mới:
Nhờ vào FRI-Binius, có thể giảm kích thước chứng minh Binius xuống một bậc.
4 Kết luận
Binius là một giải pháp thiết kế hợp tác "sử dụng phần cứng, phần mềm và giao thức Sumcheck được tăng tốc bằng FPGA", có thể chứng minh một cách nhanh chóng với tỷ lệ sử dụng bộ nhớ rất thấp. Trong Binius, đã cơ bản loại bỏ hoàn toàn nút thắt cam kết của Prover, nút thắt mới nằm ở giao thức Sumcheck, trong đó có rất nhiều vấn đề đánh giá đa thức và phép nhân miền, có thể được giải quyết hiệu quả bằng phần cứng chuyên dụng.
Giải pháp FRI-Binius, là một biến thể của FRI, cung cấp một lựa chọn rất hấp dẫn - loại bỏ chi phí nhúng từ tầng chứng minh miền mà không gây ra sự gia tăng chi phí của tầng chứng minh tổng hợp. Hiện tại, đội ngũ Irreducible đang phát triển tầng đệ quy của họ và thông báo hợp tác với đội ngũ Polygon để xây dựng zkVM dựa trên Binius; JoltzkVM đang chuyển từ Lasso sang Binius để cải thiện hiệu suất đệ quy của nó; đội ngũ Ingonyama đang triển khai phiên bản FPGA của Binius.