Phân tích nguyên lý STARKs của Binius và suy nghĩ về 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à: trong các chương trình thực tế, hầu hết các giá trị đề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 sử dụng mã Reed-Solomon để mở rộng dữ liệu, nhiều giá trị dư thừa bổ sung sẽ chiếm toàn bộ miền, ngay cả khi giá trị gốc rất nhỏ. Việc giảm kích thước miền trở thành một chiến lược quan trọng.

Độ rộng bit của mã STARKs thế hệ đầu tiên là 252 bit, thế hệ thứ hai là 64 bit, thế hệ thứ ba là 32 bit, nhưng 32 bit vẫn có nhiều không gian lãng phí. Miền nhị phân cho phép thao tác trực tiếp trên bit, mã hóa chặt chẽ, hiệu quả và không lãng phí, có thể là STARKs thế hệ thứ tư.

Miền nhị phân được ứng dụng rộng rãi trong mật mã, như AES(F28), GMAC(F2128), QR mã(F28), v.v. Khi sử dụng miền nhỏ hơn, việc mở rộng miền ngày càng trở nên 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. Hầu hết các phép tính của Prover hoạt động dưới miền cơ bản, hiệu quả; kiểm tra điểm ngẫu nhiên và tính toán FRI 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.

Giải pháp đổi mới của Binius:

1. Sử dụng đa biến ( đa tuyến tính ) đa thức thay thế đa thức đơn biến, thông qua "siêu lập phương" để lấy giá trị biểu diễn quỹ đạo tính toán.
2. xem khối siêu lập phương như hình vuông, dựa trên hình vuông để mở rộng Reed-Solomon

2. Phân tích nguyên lý

Binius = HyperPlonk PIOP + Brakedown PCS + 二进制域

Năm công nghệ chính:

1. dựa trên lĩnh vực nhị phân kiểu tháp.
2. Chuyển thể kiểm tra tích và hoán vị HyperPlonk
3. Chứng minh dịch chuyển đa tuyến mới
4. Phiên bản cải tiến của Lasso tìm kiếm chứng minh
5. Chương trình cam kết đa thức nhỏ

2.1 miền hữu hạn: toán học dựa trên towers of binary fields

Lợi thế của miền nhị phân kiểu tháp:

• Tính toán hiệu quả: miền nhị phân hỗ trợ các phép toán số học hiệu quả
• Tính toán hiệu quả: Cấu trúc trường nhị phân hỗ trợ quá trình tính toán đơn giản hóa
• Tận dụng đặc tính phân cấp thông qua cấu trúc tháp

Chuỗi 128 bit có thể được giải thích linh hoạt:

• Một yếu tố độc đáo trong miền nhị phân 128 bit
• Hai phần tử miền tháp 64 bit
• Bốn phần tử miền tháp 32 bit
• 16 phần tử tháp 8 bit
• 128 phần tử miền F2

2.2 PIOP: Phiên bản cải biên của sản phẩm HyperPlonk và PermutationCheck

Cơ chế kiểm tra cốt lõi của Binius:

1. GateCheck
2. PermutationCheck
3. LookupCheck
4. MultisetCheck
5. ProductCheck
6. ZeroCheck
7. SumCheck
8. BatchCheck

Binius cải tiến HyperPlonk:

• Tối ưu hóa ProductCheck
• Xử lý đúng vấn đề chia cho không
• Hỗ trợ kiểm tra hoán vị qua các cột

2.3 PIOP: lập luận dịch chuyển đa tuyến mới

Phương pháp chính:

• Packing: Gộp các phần tử nhỏ hơn liền kề thành phần tử lớn hơn
• Toán tử dịch: Sắp xếp lại các phần tử trong khối.

2.4 PIOP: phiên bản sửa đổi đối số tìm kiếm Lasso

Ưu điểm của giao thức Lasso:

• Chứng minh hiệu suất cao: m+n phần tử miền cam kết
• Không cần cam kết bảng lớn: có thể xử lý bảng siêu lớn

Binius giới thiệu giao thức Lasso phiên bản nhân

• Tạo ra "bộ đếm bộ nhớ" gia tăng bằng cách nhân lĩnh vực nhị phân
• Bên chứng minh cam kết vector đếm đọc khác không để đảm bảo an toàn

2.5 PCS: Phiên bản cải biên Brakedown PCS

Ý tưởng cốt lõi: packing

Hai phương án:

1. Thực hiện hóa mã nối tiếp
2. Sử dụng mã hóa cấp khối, hỗ trợ sử dụng riêng mã Reed-Solomon

Cam kết đa thức nhỏ và đánh giá mở rộng miền:

• Cam kết trên K nhỏ
• Đánh giá trong miền mở rộng lớn hơn L/K

Mã khối và mã Reed-Solomon:

• Cho phép miền nhỏ ( như F2) đa thức sử dụng bảng chữ cái lớn ( như F216) mã Reed-Solomon cam kết hiệu quả

3. Tối ưu hóa tư duy

Bốn điểm tối ưu hóa chính:

3.1 PIOP dựa trên GKR: Phép nhân miền nhị phân dựa trên GKR

Chuyển "kiểm tra A·B =? C" thành "kiểm tra (gA)B =? gC"

• Chỉ cần một cam kết phụ
• Giảm chi phí Sumchecks

3.2 Tối ưu ZeroCheck PIOP: Cân bằng chi phí tính toán giữa Prover và Verifier

Phương pháp tối ưu:

• 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ỏ

Cải tiến trọng tâm:

• Chọn vòng t để chuyển đổi
• Kích thước miền cơ sở ảnh hưởng
• Tối ưu hóa thuật toán Karatsuba
• Nâng cao hiệu suất bộ nhớ

3.4 PCS tối ưu: FRI-Binius giảm kích thước proof

Bốn đổi mới:

1. Đa thức phẳng
2. Đa thức biến mất con không gian
3. Đóng gói cơ sở đại số
4. Hoán đổi SumCheck

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

Ưu điểm của Binius:

• Có thể sử dụng miền power-of-two tối thiểu cho các nhân chứng
• Chứng minh nhanh với mức sử dụng bộ nhớ thấp
• Cơ bản loại bỏ nút thắt cam kết Prover

Nút thắt mới: Giao thức Sumcheck

• Có thể sử dụng phần cứng chuyên dụng để giải quyết hiệu quả

FRI-Binius:

• Loại bỏ chi phí nhúng của lớp chứng minh miền
• Không dẫn đến sự gia tăng đột biến chi phí của lớp chứng minh tập hợp.

Tiến độ hiện tại:

• Nhóm Irreducible phát triển lớp đệ quy, hợp tác với Polygon để xây dựng zkVM dựa trên Binius
• JoltzkVM chuyển từ Lasso sang Binius
• Ingonyama thực hiện phiên bản FPGA của Binius