Phân tích nguyên lý Binius STARKs và những suy nghĩ tối ưu hóa của nó
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ế khá 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 chiếm toàn bộ miền. Để giải quyết vấn đề này, 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 STARKs thế hệ thứ 1 là 252 bit, thế hệ thứ 2 là 64 bit, thế hệ thứ 3 là 32 bit, nhưng độ rộng mã hóa 32 bit vẫn còn có nhiều không gian lãng phí. So với đó, miền nhị phân cho phép thao tác trực tiếp trên các bit, mã hóa chặt chẽ, hiệu quả mà không có không gian lãng phí nào, tức là STARKs thế hệ thứ 4.
Khi sử dụng miền nhỏ hơn, việc mở rộng miền trở nên ngày càng quan trọng để đảm bảo an toàn. Miền nhị phân mà Binius sử dụng hoàn toàn dựa vào việc mở rộng miền để đảm bảo 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 trong tính toán Prover không cần phải vào mở rộng miền, 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, việc 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 an toàn cần thiết.
Binius đã đề xuất một giải pháp đổi mới để xử lý hai vấn đề này, và thực hiện điều này bằng cách biểu diễn cùng một dữ liệu theo hai cách khác nhau: đầu tiên, sử dụng đa biến (cụ thể là đa thức đa tuyến tính) thay thế cho đa thức đơn biến, thông qua 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, vì chiều dài của mỗi chiều của 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 này để thực hiện mở rộng Reed-Solomon. Phương pháp này đảm bảo tính an toàn trong khi nâng cao hiệu quả mã hóa và hiệu suất tính toán một cách đáng kể.
2 Phân tích nguyên lý
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à tính an toàn của nó:
Toán học dựa trên miền nhị phân dạng tháp (towers of binary fields)
Đã điều chỉnh kiểm tra tích và hoán vị của HyperPlonk
Chứng minh dịch chuyển đa tuyến tính mới
Phiên bản cải tiến của chứng minh tìm kiếm Lasso
Phương án cam kết đa thức trường nhỏ (Small-Field PCS)
2.1 miền hữu hạn: toán học dựa trên tháp của các trường nhị phân
Miền nhị phân kiểu 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 do hai khía cạnh: tính toán hiệu quả và 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 rất 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ố gọn gàng và dễ xác minh.
2.2 PIOP: Phiên bản cải biên của Sản phẩm HyperPlonk và Kiểm tra Permutation
Thiết kế PIOP trong giao thức Binius đã tham khảo HyperPlonk, áp dụng một loạt các cơ chế kiểm tra cốt lõi để xác minh tính chính xác 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 đã cải tiến ở 3 lĩnh vực 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：tham số dịch nhiều tuyến tính 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ệ quan trọng, chủ yếu bao gồm hai phương pháp:
Đóng gói
Toán tử dịch bit
2.4 PIOP: phiên bản sửa đổi của tham số tra cứu Lasso
Giao thức Lasso được cấu thành từ ba thành phần sau:
Trừu tượng đa thức ảo lớn
Tìm kiếm bảng nhỏ
Kiểm tra đa tập hợp
Giao thức Binius đã điều chỉnh Lasso cho các hoạt động 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：Phiên bản cải biên Brakedown PCS
Ý tưởng cốt lõi để xây dựng BiniusPCS là packing. Cam kết đa thức Binius chủ yếu sử dụng:
Cam kết đa thức nhỏ và đánh giá mở rộng miền
Cấu trúc chung nhỏ
Mã khối và mã Reed-Solomon
3 Tối ưu hóa tư duy
Để 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 trong miền nhỏ
Tối ưu hóa PCS: Giảm kích thước proof thông qua 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 xem (gA)B =? gC có hợp lệ 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
Chủ yếu bao gồm các hướng tối ưu hóa sau:
Giảm thiểu 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ỏ
Các điểm tối ưu hóa 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
FRI-Binius đã triển khai cơ chế gập FRI trong miền 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 trong không gian con
Gói cơ sở đại số
Hoán đổi SumCheck
4 Tóm tắt
Giá trị cốt lõi của Binius là có thể sử dụng các miền power-of-two tối thiểu cho các nhân chứng, do đó chỉ cần chọn kích thước miền dựa trên yêu cầu. Binius là giải pháp thiết kế phối hợp của "sử dụng phần cứng, phần mềm, và giao thức Sumcheck tăng tốc bằng FPGA", có thể chứng minh nhanh chóng với mức sử dụng bộ nhớ rất thấp.
Binius đã cơ bản hoàn toàn loại bỏ nút thắt cam kết Prover, nút thắt mới nằm ở giao thức Sumcheck, và nhiều vấn đề như đánh giá đa thức và phép nhân miền trong giao thức Sumcheck có thể được giải quyết hiệu quả nhờ phần cứng chuyên dụng. Giải pháp FRI-Binius là một biến thể của FRI, có thể cung cấp một lựa chọn rất hấp dẫn - loại bỏ chi phí nhúng từ lớp chứng minh miền mà không làm tăng chi phí của lớp chứng minh tổng hợp.
Hiện tại, đội ngũ Irreducible đang phát triển lớp đệ quy của mình và công bố 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 mình; độ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.
12 thích
Phần thưởng
12
6
Chia sẻ
Bình luận
0/400
SilentObserver
· 07-16 18:11
Sao hiệu suất lại tăng nhiều như vậy
Xem bản gốcTrả lời0
StakeOrRegret
· 07-16 11:52
Đây chính là điều tôi luôn nói, phải lãng phí bao nhiêu tài nguyên mới có thể tiến hóa đến thế hệ thứ 4 thật sự.
Xem bản gốcTrả lời0
Ser_This_Is_A_Casino
· 07-16 06:56
Đã nhanh chóng tiến vào thế hệ thứ tư ở đây rồi.
Xem bản gốcTrả lời0
AirdropHunterXiao
· 07-15 16:49
Airdrop nội chiến rồi, cả ngày nghiên cứu cái này thật sâu sắc.
Xem bản gốcTrả lời0
CodeSmellHunter
· 07-15 16:44
stark dịu dàng 666
Xem bản gốcTrả lời0
RektRecorder
· 07-15 16:41
Thà nhìn tiền tệ ngoài sàn giao dịch cũng không muốn nhìn đống huyền học này.
Giải pháp tối ưu Binius STARKs: Tăng cường hiệu suất của phép toán số nhị phân và đa thức nhiều biến.
Phân tích nguyên lý Binius STARKs và những suy nghĩ tối ưu hóa của nó
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ế khá 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 chiếm toàn bộ miền. Để giải quyết vấn đề này, 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 STARKs thế hệ thứ 1 là 252 bit, thế hệ thứ 2 là 64 bit, thế hệ thứ 3 là 32 bit, nhưng độ rộng mã hóa 32 bit vẫn còn có nhiều không gian lãng phí. So với đó, miền nhị phân cho phép thao tác trực tiếp trên các bit, mã hóa chặt chẽ, hiệu quả mà không có không gian lãng phí nào, tức là STARKs thế hệ thứ 4.
Khi sử dụng miền nhỏ hơn, việc mở rộng miền trở nên ngày càng quan trọng để đảm bảo an toàn. Miền nhị phân mà Binius sử dụng hoàn toàn dựa vào việc mở rộng miền để đảm bảo 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 trong tính toán Prover không cần phải vào mở rộng miền, 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, việc 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 an toàn cần thiết.
Binius đã đề xuất một giải pháp đổi mới để xử lý hai vấn đề này, và thực hiện điều này bằng cách biểu diễn cùng một dữ liệu theo hai cách khác nhau: đầu tiên, sử dụng đa biến (cụ thể là đa thức đa tuyến tính) thay thế cho đa thức đơn biến, thông qua 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, vì chiều dài của mỗi chiều của 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 này để thực hiện mở rộng Reed-Solomon. Phương pháp này đảm bảo tính an toàn trong khi nâng cao hiệu quả mã hóa và hiệu suất tính toán một cách đáng kể.
2 Phân tích nguyên lý
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à tính an toàn của nó:
2.1 miền hữu hạn: toán học dựa trên tháp của các trường nhị phân
Miền nhị phân kiểu 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 do hai khía cạnh: tính toán hiệu quả và 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 rất 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ố gọn gàng và dễ xác minh.
2.2 PIOP: Phiên bản cải biên của Sản phẩm HyperPlonk và Kiểm tra Permutation
Thiết kế PIOP trong giao thức Binius đã tham khảo HyperPlonk, áp dụng một loạt các cơ chế kiểm tra cốt lõi để xác minh tính chính xác 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 đã cải tiến ở 3 lĩnh vực sau:
2.3 PIOP：tham số dịch nhiều tuyến tính 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ệ quan trọng, chủ yếu bao gồm hai phương pháp:
2.4 PIOP: phiên bản sửa đổi của tham số tra cứu Lasso
Giao thức Lasso được cấu thành từ ba thành phần sau:
Giao thức Binius đã điều chỉnh Lasso cho các hoạt động 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：Phiên bản cải biên Brakedown PCS
Ý tưởng cốt lõi để xây dựng BiniusPCS là packing. Cam kết đa thức Binius chủ yếu sử dụng:
3 Tối ưu hóa tư duy
Để 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 xem (gA)B =? gC có hợp lệ 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
Chủ yếu bao gồm các hướng tối ưu hóa sau:
3.3 Tối ưu hóa PIOP Sumcheck: Giao thức Sumcheck dựa trên miền nhỏ
Các điểm tối ưu hóa chính bao gồm:
3.4 PCS Tối ưu: FRI-Binius giảm kích thước bằng chứng Binius
FRI-Binius đã triển khai cơ chế gập FRI trong miền nhị phân, mang lại 4 khía cạnh đổi mới:
4 Tóm tắt
Giá trị cốt lõi của Binius là có thể sử dụng các miền power-of-two tối thiểu cho các nhân chứng, do đó chỉ cần chọn kích thước miền dựa trên yêu cầu. Binius là giải pháp thiết kế phối hợp của "sử dụng phần cứng, phần mềm, và giao thức Sumcheck tăng tốc bằng FPGA", có thể chứng minh nhanh chóng với mức sử dụng bộ nhớ rất thấp.
Binius đã cơ bản hoàn toàn loại bỏ nút thắt cam kết Prover, nút thắt mới nằm ở giao thức Sumcheck, và nhiều vấn đề như đánh giá đa thức và phép nhân miền trong giao thức Sumcheck có thể được giải quyết hiệu quả nhờ phần cứng chuyên dụng. Giải pháp FRI-Binius là một biến thể của FRI, có thể cung cấp một lựa chọn rất hấp dẫn - loại bỏ chi phí nhúng từ lớp chứng minh miền mà không làm tăng chi phí của lớp chứng minh tổng hợp.
Hiện tại, đội ngũ Irreducible đang phát triển lớp đệ quy của mình và công bố 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 mình; đội ngũ Ingonyama đang thực hiện phiên bản FPGA của Binius.