Phân tích nguyên lý Binius STARKs và suy nghĩ về tối ưu hóa
1. Giới thiệu
Một 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, khi mở rộng dữ liệu bằng mã Reed-Solomon, nhiều giá trị dư thừa bổ sung sẽ chiếm lĩnh toàn bộ miền. Giảm kích thước miền trở thành một chiến lược then chốt.
Độ rộng mã hóa của STARKs thế hệ đầu tiên là 252bit, thế hệ thứ hai là 64bit, thế hệ thứ ba là 32bit, nhưng độ rộng mã hóa 32bit vẫn có 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 bit, mã hóa gọn gàng và hiệu quả mà không có không gian lãng phí tùy ý, tức là STARKs thế hệ thứ tư.
Binius sử dụng miền nhị phân, cần 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 tính toán Prover không cần phải vào miền mở rộng, mà chỉ cần thao tác 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 phải đ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.
Binius đã đưa ra một giải pháp sáng tạo: trước tiên, sử dụng đa biến (cụ thể là đa thức đa tuyến) thay thế cho đa thức đơn biến, thông qua giá trị của nó trên "siêu lập phương" để biểu diễn toàn bộ quỹ đạo tính toán; thứ hai, coi siêu lập phương như một hình vuông, dựa trên hình vuông đó để 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ý
Binius bao gồm năm công nghệ chính:
Căn cứ vào miền nhị phân tháp được số hóa
Phiên bản sửa đổi kiểm tra tích và hoán vị HyperPlonk
Bằng chứng dịch chuyển đa tuyến mới
Phiên bản cải tiến của Lasso tìm kiếm chứng minh
Kế hoạch cam kết đa thức nhỏ
2.1 Tập hợp hữu hạn: Toán tử dựa trên tháp của các trường nhị phân
Miền nhị phân dạng tháp hỗ trợ các phép toán số học hiệu quả cao, hỗ trợ quá trình số học đơn giản hóa. Các phần tử của miền nhị phân có cách biểu diễn duy nhất và trực tiếp, có thể linh hoạt chuyển đổi và đóng gói giữa các miền có kích thước khác nhau.
2.2 PIOP: Phiên bản cải biên HyperPlonk Product và PermutationCheck
Binius đã áp dụng một loạt cơ chế kiểm tra cốt lõi, bao gồm GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck và BatchCheck.
So với HyperPlonk, Binius đã cải tiến ở các khía cạnh sau:
Tối ưu hóa ProductCheck
Xử lý vấn đề chia cho 0
Kiểm tra hoán vị giữa các cột
2.3 PIOP: lập luận dịch chuyển đa tuyến mới
Binius sử dụng hai phương pháp chính là Packing và toán tử dịch để xử lý đa thức ảo.
2.4 PIOP: Phiên bản cải biên tham số tìm kiếm Lasso
Giao thức Lasso được cấu thành từ ba thành phần:
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
Binius đã giới thiệu phiên bản nhân của giao thức Lasso, yêu cầu bên chứng minh và bên xác minh hợp tác tăng cường hoạt động "đếm bộ nhớ" của giao thức, không phải bằng cách tăng đơn giản 1, mà là bằng cách tăng cường thông qua các phần tử sinh trong miền nhị phân.
2.5 PCS: Phiên bản cải biên Brakedown PCS
Binius đa thức cam kết chủ yếu sử dụng:
Cam kết đa thức nhỏ và đánh giá miền mở rộng
Cấu trúc chung nhỏ
Mã hóa khối và công nghệ mã Reed-Solomon
3. Tối ưu hóa tư duy
3.1 PIOP dựa trên GKR: Nhân trường 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ó hợp lệ hay không", nhờ vào giao thức GKR đã 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
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ỏ
Ảnh hưởng và yếu tố cải tiến của việc chuyển đổi vòng
Ảnh hưởng của kích thước miền cơ bản đến hiệu suất
FRI-Binius đã thực hiện cơ chế gập FRI trong miền nhị phân, mang lại 4 phương diện đổi mới:
Đa thức phẳng
Đa thức biến mất trong không gian con
Gói cơ sở đại số
Hoán đổi SumCheck
4. Tóm tắt
Binius基本完全移除了Prover的commit承诺瓶颈,新的瓶颈在于Sumcheck协议。FRI-Binius方案为FRI变体,可从域证明层中消除嵌入开销。Hiện tại, đội ngũ Irreducible đang phát triển lớp đệ quy của mình và 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; đội ngũ Ingonyama đang thực hiện phiên bản FPGA của Binius.
Xem bản gốc
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.
14 thích
Phần thưởng
14
5
Chia sẻ
Bình luận
0/400
WalletDivorcer
· 07-27 05:08
Chỉ nói về an toàn là bạn đã thua...thở dài
Xem bản gốcTrả lời0
Anon4461
· 07-24 16:08
Đề tài luận văn này dọa ai vậy vài
Xem bản gốcTrả lời0
ProofOfNothing
· 07-24 16:06
Độ rộng vị trí từ 252 đến 32, vẫn chưa đủ thấp nhỉ.
Xem bản gốcTrả lời0
RugPullAlertBot
· 07-24 16:00
Nghe nói kiến thức không biết lại tốn tiền rồi.
Xem bản gốcTrả lời0
StakeOrRegret
· 07-24 15:55
Tôi đã xem bài luận ba lần, nhưng không hiểu gì cả.
Binius STARKs: Đổi mới chứng minh không kiến thức hiệu quả cao dựa trên miền nhị phân
Phân tích nguyên lý Binius STARKs và suy nghĩ về tối ưu hóa
1. Giới thiệu
Một 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, khi mở rộng dữ liệu bằng mã Reed-Solomon, nhiều giá trị dư thừa bổ sung sẽ chiếm lĩnh toàn bộ miền. Giảm kích thước miền trở thành một chiến lược then chốt.
Độ rộng mã hóa của STARKs thế hệ đầu tiên là 252bit, thế hệ thứ hai là 64bit, thế hệ thứ ba là 32bit, nhưng độ rộng mã hóa 32bit vẫn có 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 bit, mã hóa gọn gàng và hiệu quả mà không có không gian lãng phí tùy ý, tức là STARKs thế hệ thứ tư.
Binius sử dụng miền nhị phân, cần 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 tính toán Prover không cần phải vào miền mở rộng, mà chỉ cần thao tác 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 phải đ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.
Binius đã đưa ra một giải pháp sáng tạo: trước tiên, sử dụng đa biến (cụ thể là đa thức đa tuyến) thay thế cho đa thức đơn biến, thông qua giá trị của nó trên "siêu lập phương" để biểu diễn toàn bộ quỹ đạo tính toán; thứ hai, coi siêu lập phương như một hình vuông, dựa trên hình vuông đó để 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ý
Binius bao gồm năm công nghệ chính:
2.1 Tập hợp hữu hạn: Toán tử dựa trên tháp của các trường nhị phân
Miền nhị phân dạng tháp hỗ trợ các phép toán số học hiệu quả cao, hỗ trợ quá trình số học đơn giản hóa. Các phần tử của miền nhị phân có cách biểu diễn duy nhất và trực tiếp, có thể linh hoạt chuyển đổi và đóng gói giữa các miền có kích thước khác nhau.
2.2 PIOP: Phiên bản cải biên HyperPlonk Product và PermutationCheck
Binius đã áp dụng một loạt cơ chế kiểm tra cốt lõi, bao gồm GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck và BatchCheck.
So với HyperPlonk, Binius đã cải tiến ở các khía cạnh sau:
2.3 PIOP: lập luận dịch chuyển đa tuyến mới
Binius sử dụng hai phương pháp chính là Packing và toán tử dịch để xử lý đa thức ảo.
2.4 PIOP: Phiên bản cải biên tham số tìm kiếm Lasso
Giao thức Lasso được cấu thành từ ba thành phần:
Binius đã giới thiệu phiên bản nhân của giao thức Lasso, yêu cầu bên chứng minh và bên xác minh hợp tác tăng cường hoạt động "đếm bộ nhớ" của giao thức, không phải bằng cách tăng đơn giản 1, mà là bằng cách tăng cường thông qua các phần tử sinh trong miền nhị phân.
2.5 PCS: Phiên bản cải biên Brakedown PCS
Binius đa thức cam kết chủ yếu sử dụng:
3. Tối ưu hóa tư duy
3.1 PIOP dựa trên GKR: Nhân trường 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ó hợp lệ hay không", nhờ vào giao thức GKR đã 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
3.3 Tối ưu hóa PIOP Sumcheck: Giao thức Sumcheck dựa trên miền nhỏ
3.4 PCS Tối ưu: FRI-Binius giảm kích thước bằng chứng Binius
FRI-Binius đã thực hiện cơ chế gập FRI trong miền nhị phân, mang lại 4 phương diện đổi mới:
4. Tóm tắt
Binius基本完全移除了Prover的commit承诺瓶颈,新的瓶颈在于Sumcheck协议。FRI-Binius方案为FRI变体,可从域证明层中消除嵌入开销。Hiện tại, đội ngũ Irreducible đang phát triển lớp đệ quy của mình và 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; đội ngũ Ingonyama đang thực hiện phiên bản FPGA của Binius.