Phân tích nguyên lý STARKs của Binius 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 khá nhỏ, nhưng để đảm bảo tính bảo mật 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. Giảm kích thước miền trở thành chiến lược quan trọng.

Chiều rộng mã hóa STARKs thế hệ đầu tiên là 252bit, thế hệ thứ hai là 64bit, thế hệ thứ ba là 32bit, nhưng chiều rộng mã hóa 32bit vẫn tồn tại một lượng lớn không gian lãng phí. 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ẽ và hiệu quả mà không có không gian lãng phí nào, tức là STARKs thế hệ thứ tư.

Binius đã áp dụng các công nghệ cốt lõi sau:

• Dựa trên miền nhị phân dạng tháp để tính toán
• Phiên bản cải tiến của phép kiểm tra tích và hoán vị 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 lý thuyết tìm kiếm Lasso
• Phương án cam kết đa thức nhỏ

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

2.1 Tính toán dựa trên towers of binary fields

Miền nhị phân dạng tháp hỗ trợ các phép toán số học hiệu quả cao, là chìa khóa để thực hiện tính toán có thể xác minh nhanh chóng. Các lợi thế của nó bao gồm:

• Tính toán hiệu quả
• Tính toán hiệu quả
• Hỗ trợ quá trình toán học đơn giản hóa
• Có thể tận dụng đặc tính phân cấp của nó thông qua cấu trúc tháp.

2.2 Phiên bản cải biên HyperPlonk Product và PermutationCheck

Binius đã cải tiến HyperPlonk trong các lĩnh vực sau:

• Tối ưu hóa ProductCheck: Chuyên môn hóa giá trị thành 1, đơn giản hóa quá trình kiểm tra
• Xử lý vấn đề chia cho 0: ngay cả khi mẫu số là 0 cũng có thể tiếp tục xử lý
• Kiểm tra hoán vị giữa các cột: hỗ trợ kiểm tra hoán vị giữa nhiều cột

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

Binius đã giới thiệu hai phương pháp chính:

• Packing: Tối ưu hóa thao tác bằng cách đóng gói các phần tử liền kề
• Toán tử dịch: Sắp xếp lại các phần tử trong khối dựa trên độ dịch đã cho

2.4 Phiên bản chuyển thể tham số tìm kiếm Lasso

Binius đã điều chỉnh Lasso cho các thao tác trên miền nhị phân, giới thiệu phiên bản nhân của giao thức Lasso. Bên chứng minh phải cam kết một vectơ đếm đọc không bằng 0 ở mọi nơi, để đảm bảo tính an toàn của giao thức.

2.5 phiên bản sửa đổi Brakedown PCS

Binius cung cấp hai phương án cam kết đa thức Brakedown dựa trên lĩnh vực nhị phân:

• Thực hiện hóa mã ghép nối
• Sử dụng công nghệ mã hóa cấp khối, hỗ trợ sử dụng riêng các mã Reed-Solomon.

3. Tối ưu hóa suy nghĩ

3.1 PIOP dựa trên GKR

Phép nhân miền nhị phân dựa trên GKR chỉ cần một cam kết hỗ trợ, nâng cao hiệu quả bằng cách giảm chi phí của Sumchecks.

3.2 ZeroCheck PIOP tối ưu hóa

Bằng cách điều chỉnh phân bổ khối lượng công việc giữa bên chứng minh và bên xác minh, nhiều phương án tối ưu hóa đã được đưa ra:

• 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 Sumcheck PIOP tối ưu

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

• Lựa chọn chuyển đổi vòng ảnh hưởng đến hiệu suất
• Các miền cơ bản nhỏ hơn cho thấy lợi thế rõ rệt hơn.
• Thuật toán Karatsuba đã cải thiện hiệu suất
• Hiệu suất bộ nhớ được cải thiện

3.4 PCS tối ưu:FRI-Binius

FRI-Binius đã triển khai cơ chế gập FRI trong miền nhị phân, mang lại 4 đổi mới:

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

4. Tóm tắt

Binius đã loại bỏ nút thắt cam kết commit của Prover, nút thắt mới nằm ở giao thức Sumcheck. Giải pháp FRI-Binius là biến thể của FRI, có thể loại bỏ chi phí nhúng của lớp chứng minh miền. Hiện tại, nhiều đội đang phát triển các ứng dụng liên quan đến Binius.