Phân tích nguyên lý STARKs 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 nhỏ, chẳng hạn như chỉ số trong vòng lặp for, giá trị đúng/sai, bộ đếm, v.v. Tuy nhiên, để đả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ã hóa 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, ngay cả khi giá trị gốc rất nhỏ. Để 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ệ 1 là 252 bit, kích thước mã của STARKs thế hệ 2 là 64 bit, kích thước mã của STARKs thế hệ 3 là 32 bit, nhưng kích thước mã 32 bit vẫn còn tồn tại 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 bit, mã hóa chặt chẽ và hiệu quả mà không có bất kỳ không gian lãng phí nào, tức là STARKs thế hệ 4.
So với Goldilocks, BabyBear, Mersenne31 và các phát hiện nghiên cứu mới trong những năm gần đây về trường hữu hạn, nghiên cứu về trường nhị phân có thể được truy nguyên đến những năm 80 của thế kỷ trước. Hiện tại, trường nhị phân đã được ứng dụng rộng rãi trong lĩnh vực mật mã, ví dụ điển hình bao gồm:
Tiêu chuẩn mã hóa nâng cao ( AES ), dựa trên miền F28;
Mã xác thực tin nhắn Galois ( GMAC ), dựa trên trường F2128;
Mã QR, sử dụng mã Reed-Solomon dựa trên F28;
Giao thức FRI gốc và zk-STARK, cũng như hàm băm Grøstl đã vào vòng chung kết SHA-3, hàm băm này dựa trên miền F28, là một thuật toán băm rất phù hợp cho đệ quy.
Khi sử dụng miền nhỏ hơn, thao tác mở rộng miền trở nên ngày càng quan trọng để đảm bảo an toàn. Và miền nhị phân mà Binius sử dụng hoàn toàn phụ thuộc vào thao tác mở rộng miền để đảm bảo an toàn và tính khả dụng thực tế. Hầu hết các đa thức liên quan trong các phép toán Prover không cần phải vào miền mở rộng, mà chỉ cần thực hiện trong miền cơ sở, do đó đạ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 vào miền mở rộng lớn hơn để đảm bảo 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 đã đề xuất một giải pháp đổi mới, xử lý riêng biệt hai vấn đề này và thể hiện dữ liệu giống nhau theo hai cách khác nhau: đầu tiên, sử dụng đa thức đa biến (cụ thể là đa thức đa tuyến) thay vì đa thức đơn biến, để thể hiện toàn bộ quỹ đạo tính toán thông qua giá trị của nó trên "siêu lập phương" (hypercubes); thứ hai, do mỗi chiều của siêu lập phương đều có độ dài là 2, nên không thể thực hiện mở rộng Reed-Solomon tiêu chuẩn như STARKs, nhưng có thể xem siêu lập phương như một hình vuông (square) và thực hiện mở rộng Reed-Solomon dựa trên hình vuông đó. Phương pháp này, trong khi đảm bảo tính an toàn, đã 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 thường bao gồm hai phần sau:
Chứng minh Oracle Tương tác Đa thức Dựa trên Thông tin (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP như một hệ thống chứng minh cốt lõi, chuyển đổi mối quan hệ tính toán đầu vào thành các phương trình đa thức có thể xác minh. Các giao thức PIOP khác nhau thông qua sự tương tác với người xác minh, cho phép người chứng minh gửi từng bước các đa thức, để người xác minh có thể xác minh tính chính xác của phép tính thông qua việc truy vấn một lượng nhỏ kết quả đánh giá đa thức. Các giao thức PIOP hiện có bao gồm: PLONK PIOP, Spartan PIOP và HyperPlonk PIOP, mỗi giao thức xử lý các biểu thức đa thức theo cách khác nhau, từ đó ảnh hưởng đến hiệu suất và hiệu quả toàn bộ hệ thống SNARK.
Chương trình cam kết đa thức (Polynomial Commitment Scheme, PCS): Chương trình cam kết đa thức được sử dụng để chứng minh xem các phương trình đa thức được tạo ra bởi PIOP có đúng hay không. PCS là một công cụ mật mã, thông qua đó, người chứng minh có thể cam kết một đa thức và sau đó xác minh kết quả đánh giá của đa thức đó, đồng thời ẩn đi các thông tin khác về đa thức. Các chương trình cam kết đa thức phổ biến bao gồm KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) và Brakedown. Các PCS khác nhau có hiệu suất, độ an toàn và ứng dụng khác nhau.
Dựa trên nhu cầu cụ thể, chọn các PIOP và PCS khác nhau, và kết hợp với miền hữu hạn hoặc đường cong elliptic phù hợp, có thể xây dựng các hệ thống chứng minh với các thuộc tính khác nhau. Ví dụ:
• Halo2: Kết hợp giữa PLONK PIOP và Bulletproofs PCS, dựa trên đường cong Pasta. Halo2 được thiết kế với trọng tâm vào khả năng mở rộng và loại bỏ thiết lập tin cậy trong giao thức ZCash.
• Plonky2: Sử dụng PLONK PIOP kết hợp với FRI PCS và dựa trên miền Goldilocks. Plonky2 được thiết kế để đạt được hiệu suất đệ quy. Khi thiết kế các hệ thống này, PIOP và PCS được chọn phải phù hợp với miền hữu hạn hoặc đường cong elip được sử dụng, để đảm bảo tính chính xác, hiệu suất và an toàn của hệ thống. Việc lựa chọn các kết hợp này không chỉ ảnh hưởng đến kích thước chứng minh của SNARK và hiệu suất xác minh, mà còn quyết định xem hệ thống có thể đạt được tính minh bạch mà không cần thiết lập đáng tin cậy hay không, và có thể hỗ trợ các chức năng mở rộng như chứng minh đệ quy hoặc chứng minh tổng hợp hay không.
Binius: HyperPlonk PIOP + Brakedown PCS + lĩnh vực 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. Đầu tiên, cấu trúc số học dựa trên các tháp lĩnh vực nhị phân (towers of binary fields) tạo thành nền tảng cho tính toán của nó, cho phép thực hiện các phép toán đơn giản trong lĩnh vực nhị phân. Thứ hai, Binius đã điều chỉnh kiểm tra tích và hoán vị HyperPlonk trong giao thức chứng minh Oracle tương tác (PIOP) của nó, đảm bảo kiểm tra tính nhất quán an toàn và hiệu quả giữa các biến và các hoán vị của chúng. Thứ ba, giao thức giới thiệu một chứng minh chuyển vị đa tuyến mới, tối ưu hóa hiệu quả xác minh các mối quan hệ đa tuyến trên lĩnh vực nhỏ. Thứ tư, Binius sử dụng chứng minh tìm kiếm Lasso cải tiến, cung cấp tính linh hoạt và độ an toàn mạnh mẽ cho cơ chế tìm kiếm. Cuối cùng, giao thức sử dụng kế hoạch cam kết đa thức lĩnh vực nhỏ (Small-Field PCS), cho phép nó thiết lập hệ thống chứng minh hiệu quả trên lĩnh vực nhị phân và giảm thiểu chi phí thường liên quan đến lĩnh vực lớn.
2.1 trường hữu hạn: số học dựa trên tháp của các trường nhị phân
Trường nhị phân tháp là yếu tố then chốt để thực hiện tính toán có thể xác minh nhanh chóng, chủ yếu do hai lý do: tính toán hiệu quả và tính toán hóa hiệu quả. Trường nhị phân về bản chất hỗ trợ các phép toán số học hiệu quả cao, 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 năng. Hơn nữa, cấu trúc trường nhị phân hỗ trợ quy trình tính toán hóa đơn giản hóa, tức là các phép toán thực hiện trên trường 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. Những đặc tính này, cộng với khả năng tận dụng triệt để các đặc điểm phân cấp của nó thông qua cấu trúc tháp, khiến trường nhị phân đặc biệt phù hợp với các hệ thống chứng minh có thể mở rộng như Binius.
Trong đó, "canonical" đề cập đến cách biểu diễn duy nhất và trực tiếp của các phần tử trong trường nhị phân. Ví dụ, trong trường nhị phân cơ bản F2, bất kỳ chuỗi k bit nào cũng có thể được ánh xạ trực tiếp đến một phần tử trường nhị phân k bit. Điều này khác với trường nguyên tố, nơi không thể cung cấp cách biểu diễn quy chuẩn như vậy trong một số bit nhất định. Mặc dù trường nguyên tố 32 bit có thể chứa trong 32 bit, nhưng không phải mọi chuỗi 32 bit đều có thể tương ứng duy nhất với một phần tử trường, trong khi trường nhị phân lại có sự tiện lợi của ánh xạ một-một này. Trong trường nguyên tố Fp, các phương pháp giảm phổ biến bao gồm giảm Barrett, giảm Montgomery, và 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). Bài báo "Khám Phá Không Gian Thiết Kế của Các Triển Khai ECC-Hardware Trường Nguyên Tố So với Trường Nhị Phân" chỉ ra rằng trường nhị phân không cần phải đưa vào việc mang trong các phép toán cộng và nhân, và phép toán bình phương của trường nhị phân rất hiệu quả, vì nó tuân theo quy tắc đơn giản hóa (X + Y )2 = X2 + Y2.
Như hình 1 cho thấy, một chuỗi 128 bit: chuỗi này có thể được giải thích theo nhiều cách trong ngữ cảnh của miền nhị phân. Nó có thể được coi là một phần tử duy nhất trong miền nhị phân 128 bit, hoặc được phân tích thành hai phần tử miền tháp 64 bit, bốn phần tử miền tháp 32 bit, mười sáu phần tử miền tháp 8 bit, hoặc 128 phần tử miền F2. Tính linh hoạt của cách biểu diễn này không yêu cầu bất kỳ chi phí tính toán nào, chỉ là việc chuyển đổi kiểu (typecast) của chuỗi bit, đây là một đặc điểm rất thú vị và hữu ích. Đồng thời, các phần tử miền nhỏ có thể được đóng gói thành các phần tử miền lớn hơn mà không cần thêm chi phí tính toán. Giao thức Binius đã tận dụng đặc điểm này để cải thiện hiệu quả tính toán. Hơn nữa, bài báo "On Efficient Inversion in Tower Fields of Characteristic Two" đã khám phá độ phức tạp tính toán của các phép nhân, bình phương và phép đảo ngược trong miền nhị phân tháp n bit (có thể phân rã thành miền con m bit).
2.2 PIOP: Phiên bản cải biên sản phẩm HyperPlonk và PermutationCheck------Áp dụng cho miền nhị phân
Thiết kế PIOP trong giao thức Binius đã tham khảo HyperPlonk, sử dụng một loạt 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: Xác minh chứng thực bảo mật ω và đầu vào công khai x có thỏa mãn quan hệ tính toán mạch C(x,ω)=0, để đảm bảo mạch hoạt động chính xác.
PermutationCheck: Xác thực xem kết quả đánh giá của hai đa thức đa biến f và g trên hypercube Boolean có phải là quan hệ hoán vị hay không f(x) = f(π(x)), để đảm bảo tính nhất quán của các biến đa thức.
LookupCheck: Xác minh xem giá trị của đa thức có nằm trong bảng tra cứu đã cho hay không, tức là f(Bµ) ⊆ T(Bµ), đảm bảo rằng một số giá trị nằm trong khoảng đã chỉ định.
MultisetCheck: Kiểm tra hai tập hợp đa biến có bằng nhau hay không, tức là {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, đảm bảo tính nhất quán giữa nhiều tập hợp.
ProductCheck：Kiểm tra xem giá trị của đa thức hợp lý trên siêu khối Boolean có bằng với một giá trị đã tuyên bố nào đó ∏x∈Hµ f(x) = s, để đảm bảo tính chính xác của tích đa thức.
ZeroCheck: Xác thực một đa biến đa thức tại bất kỳ điểm nào trên siêu lập phương Bool có phải là không ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, để đảm bảo phân bố của các điểm không của đa thức.
SumCheck: Kiểm tra xem tổng của đa thức nhiều biến có bằng giá trị đã tuyên bố hay không ∑x∈Hµ f(x) = s. Bằng cách chuyển đổi bài toán đánh giá đa thức nhiều biến thành bài toán đánh giá đa thức đơn biến, giảm độ phức tạp tính toán của bên xác minh. Ngoài ra, SumCheck còn cho phép xử lý hàng loạt bằng cách đưa vào số ngẫu nhiên, xây dựng tổ hợp tuyến tính để thực hiện xử lý hàng loạt cho nhiều trường hợp kiểm tra tổng.
BatchCheck: Dựa trên SumCheck, xác thực tính chính xác của nhiều giá trị đa thức đa biến để nâng cao hiệu quả của giao thức.
Mặc dù Binius và HyperPlonk có nhiều điểm tương đồng trong thiết kế giao thức, nhưng Binius đã cải tiến ở 3 khía cạnh sau:
Tối ưu hóa ProductCheck: Trong HyperPlonk, ProductCheck yêu cầu mẫu số U phải khác không trên siêu lập phương, và tích phải bằng một giá trị cụ thể; Binius đã đơn giản hóa quy trình kiểm tra này bằng cách đặc trưng hóa giá trị đó thành 1, từ đó giảm độ phức tạp tính toán.
Xử lý vấn đề chia cho không: HyperPlonk không xử lý đầy đủ trường hợp chia cho không, dẫn đến không thể khẳng định rằng U không bằng 0 trên siêu khối; Binius đã xử lý vấn đề này một cách chính xác, ngay cả khi mẫu số bằng 0, ProductCheck của Binius vẫn có thể tiếp tục xử lý, cho phép mở rộng đến bất kỳ giá trị tích nào.
Kiểm tra hoán vị giữa các cột: HyperPlonk không có chức năng này; Binius hỗ trợ kiểm tra hoán vị giữa nhiều cột, điều này cho phép Binius xử lý các trường hợp sắp xếp đa thức phức tạp hơn.
Vì vậy, Binius đã cải tiến cơ chế PIOPSumCheck hiện có, nâng cao tính linh hoạt và hiệu quả của giao thức, đặc biệt trong việc xử lý các xác minh đa biến đa thức phức tạp hơn, cung cấp hỗ trợ chức năng mạnh mẽ hơn. Những cải tiến này không chỉ giải quyết các hạn chế trong HyperPlonk mà còn đặt nền tảng cho các hệ thống chứng minh dựa trên miền nhị phân trong tương lai.
2.3 PIOP：tham số dịch đa tuyến mới------phù hợp với hypercube boolean
Trong giao thức Binius, việc xây dựng và xử lý đa thức ảo là một trong những kỹ thuật then chốt, có khả năng tạo ra và thao tác hiệu quả các đa thức được dẫn xuất từ tay cầm đầu vào hoặc từ các đa thức ảo khác. Dưới đây là hai phương pháp chính:
Packing：Phương pháp này tối ưu hóa hoạt động bằng cách đóng gói các phần tử nhỏ hơn ở các vị trí liền kề trong thứ tự từ điển thành các phần tử lớn hơn. Toán tử Pack nhắm vào các khối có kích thước 2κ và sẽ thực hiện chúng
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.
Phân tích nguyên lý Binius STARKs: Xây dựng hệ thống chứng minh hiệu quả trong miền nhị phân
Phân tích nguyên lý STARKs 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 nhỏ, chẳng hạn như chỉ số trong vòng lặp for, giá trị đúng/sai, bộ đếm, v.v. Tuy nhiên, để đả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ã hóa 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, ngay cả khi giá trị gốc rất nhỏ. Để 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ệ 1 là 252 bit, kích thước mã của STARKs thế hệ 2 là 64 bit, kích thước mã của STARKs thế hệ 3 là 32 bit, nhưng kích thước mã 32 bit vẫn còn tồn tại 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 bit, mã hóa chặt chẽ và hiệu quả mà không có bất kỳ không gian lãng phí nào, tức là STARKs thế hệ 4.
So với Goldilocks, BabyBear, Mersenne31 và các phát hiện nghiên cứu mới trong những năm gần đây về trường hữu hạn, nghiên cứu về trường nhị phân có thể được truy nguyên đến những năm 80 của thế kỷ trước. Hiện tại, trường nhị phân đã được ứng dụng rộng rãi trong lĩnh vực mật mã, ví dụ điển hình bao gồm:
Tiêu chuẩn mã hóa nâng cao ( AES ), dựa trên miền F28;
Mã xác thực tin nhắn Galois ( GMAC ), dựa trên trường F2128;
Mã QR, sử dụng mã Reed-Solomon dựa trên F28;
Giao thức FRI gốc và zk-STARK, cũng như hàm băm Grøstl đã vào vòng chung kết SHA-3, hàm băm này dựa trên miền F28, là một thuật toán băm rất phù hợp cho đệ quy.
Khi sử dụng miền nhỏ hơn, thao tác mở rộng miền trở nên ngày càng quan trọng để đảm bảo an toàn. Và miền nhị phân mà Binius sử dụng hoàn toàn phụ thuộc vào thao tác mở rộng miền để đảm bảo an toàn và tính khả dụng thực tế. Hầu hết các đa thức liên quan trong các phép toán Prover không cần phải vào miền mở rộng, mà chỉ cần thực hiện trong miền cơ sở, do đó đạ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 vào miền mở rộng lớn hơn để đảm bảo 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 đã đề xuất một giải pháp đổi mới, xử lý riêng biệt hai vấn đề này và thể hiện dữ liệu giống nhau theo hai cách khác nhau: đầu tiên, sử dụng đa thức đa biến (cụ thể là đa thức đa tuyến) thay vì đa thức đơn biến, để thể hiện toàn bộ quỹ đạo tính toán thông qua giá trị của nó trên "siêu lập phương" (hypercubes); thứ hai, do mỗi chiều của siêu lập phương đều có độ dài là 2, nên không thể thực hiện mở rộng Reed-Solomon tiêu chuẩn như STARKs, nhưng có thể xem siêu lập phương như một hình vuông (square) và thực hiện mở rộng Reed-Solomon dựa trên hình vuông đó. Phương pháp này, trong khi đảm bảo tính an toàn, đã 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 thường bao gồm hai phần sau:
Chứng minh Oracle Tương tác Đa thức Dựa trên Thông tin (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP như một hệ thống chứng minh cốt lõi, chuyển đổi mối quan hệ tính toán đầu vào thành các phương trình đa thức có thể xác minh. Các giao thức PIOP khác nhau thông qua sự tương tác với người xác minh, cho phép người chứng minh gửi từng bước các đa thức, để người xác minh có thể xác minh tính chính xác của phép tính thông qua việc truy vấn một lượng nhỏ kết quả đánh giá đa thức. Các giao thức PIOP hiện có bao gồm: PLONK PIOP, Spartan PIOP và HyperPlonk PIOP, mỗi giao thức xử lý các biểu thức đa thức theo cách khác nhau, từ đó ảnh hưởng đến hiệu suất và hiệu quả toàn bộ hệ thống SNARK.
Chương trình cam kết đa thức (Polynomial Commitment Scheme, PCS): Chương trình cam kết đa thức được sử dụng để chứng minh xem các phương trình đa thức được tạo ra bởi PIOP có đúng hay không. PCS là một công cụ mật mã, thông qua đó, người chứng minh có thể cam kết một đa thức và sau đó xác minh kết quả đánh giá của đa thức đó, đồng thời ẩn đi các thông tin khác về đa thức. Các chương trình cam kết đa thức phổ biến bao gồm KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) và Brakedown. Các PCS khác nhau có hiệu suất, độ an toàn và ứng dụng khác nhau.
Dựa trên nhu cầu cụ thể, chọn các PIOP và PCS khác nhau, và kết hợp với miền hữu hạn hoặc đường cong elliptic phù hợp, có thể xây dựng các hệ thống chứng minh với các thuộc tính khác nhau. Ví dụ:
• Halo2: Kết hợp giữa PLONK PIOP và Bulletproofs PCS, dựa trên đường cong Pasta. Halo2 được thiết kế với trọng tâm vào khả năng mở rộng và loại bỏ thiết lập tin cậy trong giao thức ZCash.
• Plonky2: Sử dụng PLONK PIOP kết hợp với FRI PCS và dựa trên miền Goldilocks. Plonky2 được thiết kế để đạt được hiệu suất đệ quy. Khi thiết kế các hệ thống này, PIOP và PCS được chọn phải phù hợp với miền hữu hạn hoặc đường cong elip được sử dụng, để đảm bảo tính chính xác, hiệu suất và an toàn của hệ thống. Việc lựa chọn các kết hợp này không chỉ ảnh hưởng đến kích thước chứng minh của SNARK và hiệu suất xác minh, mà còn quyết định xem hệ thống có thể đạt được tính minh bạch mà không cần thiết lập đáng tin cậy hay không, và có thể hỗ trợ các chức năng mở rộng như chứng minh đệ quy hoặc chứng minh tổng hợp hay không.
Binius: HyperPlonk PIOP + Brakedown PCS + lĩnh vực 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. Đầu tiên, cấu trúc số học dựa trên các tháp lĩnh vực nhị phân (towers of binary fields) tạo thành nền tảng cho tính toán của nó, cho phép thực hiện các phép toán đơn giản trong lĩnh vực nhị phân. Thứ hai, Binius đã điều chỉnh kiểm tra tích và hoán vị HyperPlonk trong giao thức chứng minh Oracle tương tác (PIOP) của nó, đảm bảo kiểm tra tính nhất quán an toàn và hiệu quả giữa các biến và các hoán vị của chúng. Thứ ba, giao thức giới thiệu một chứng minh chuyển vị đa tuyến mới, tối ưu hóa hiệu quả xác minh các mối quan hệ đa tuyến trên lĩnh vực nhỏ. Thứ tư, Binius sử dụng chứng minh tìm kiếm Lasso cải tiến, cung cấp tính linh hoạt và độ an toàn mạnh mẽ cho cơ chế tìm kiếm. Cuối cùng, giao thức sử dụng kế hoạch cam kết đa thức lĩnh vực nhỏ (Small-Field PCS), cho phép nó thiết lập hệ thống chứng minh hiệu quả trên lĩnh vực nhị phân và giảm thiểu chi phí thường liên quan đến lĩnh vực lớn.
2.1 trường hữu hạn: số học dựa trên tháp của các trường nhị phân
Trường nhị phân tháp là yếu tố then chốt để thực hiện tính toán có thể xác minh nhanh chóng, chủ yếu do hai lý do: tính toán hiệu quả và tính toán hóa hiệu quả. Trường nhị phân về bản chất hỗ trợ các phép toán số học hiệu quả cao, 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 năng. Hơn nữa, cấu trúc trường nhị phân hỗ trợ quy trình tính toán hóa đơn giản hóa, tức là các phép toán thực hiện trên trường 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. Những đặc tính này, cộng với khả năng tận dụng triệt để các đặc điểm phân cấp của nó thông qua cấu trúc tháp, khiến trường nhị phân đặc biệt phù hợp với các hệ thống chứng minh có thể mở rộng như Binius.
Trong đó, "canonical" đề cập đến cách biểu diễn duy nhất và trực tiếp của các phần tử trong trường nhị phân. Ví dụ, trong trường nhị phân cơ bản F2, bất kỳ chuỗi k bit nào cũng có thể được ánh xạ trực tiếp đến một phần tử trường nhị phân k bit. Điều này khác với trường nguyên tố, nơi không thể cung cấp cách biểu diễn quy chuẩn như vậy trong một số bit nhất định. Mặc dù trường nguyên tố 32 bit có thể chứa trong 32 bit, nhưng không phải mọi chuỗi 32 bit đều có thể tương ứng duy nhất với một phần tử trường, trong khi trường nhị phân lại có sự tiện lợi của ánh xạ một-một này. Trong trường nguyên tố Fp, các phương pháp giảm phổ biến bao gồm giảm Barrett, giảm Montgomery, và 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). Bài báo "Khám Phá Không Gian Thiết Kế của Các Triển Khai ECC-Hardware Trường Nguyên Tố So với Trường Nhị Phân" chỉ ra rằng trường nhị phân không cần phải đưa vào việc mang trong các phép toán cộng và nhân, và phép toán bình phương của trường nhị phân rất hiệu quả, vì nó tuân theo quy tắc đơn giản hóa (X + Y )2 = X2 + Y2.
Như hình 1 cho thấy, một chuỗi 128 bit: chuỗi này có thể được giải thích theo nhiều cách trong ngữ cảnh của miền nhị phân. Nó có thể được coi là một phần tử duy nhất trong miền nhị phân 128 bit, hoặc được phân tích thành hai phần tử miền tháp 64 bit, bốn phần tử miền tháp 32 bit, mười sáu phần tử miền tháp 8 bit, hoặc 128 phần tử miền F2. Tính linh hoạt của cách biểu diễn này không yêu cầu bất kỳ chi phí tính toán nào, chỉ là việc chuyển đổi kiểu (typecast) của chuỗi bit, đây là một đặc điểm rất thú vị và hữu ích. Đồng thời, các phần tử miền nhỏ có thể được đóng gói thành các phần tử miền lớn hơn mà không cần thêm chi phí tính toán. Giao thức Binius đã tận dụng đặc điểm này để cải thiện hiệu quả tính toán. Hơn nữa, bài báo "On Efficient Inversion in Tower Fields of Characteristic Two" đã khám phá độ phức tạp tính toán của các phép nhân, bình phương và phép đảo ngược trong miền nhị phân tháp n bit (có thể phân rã thành miền con m bit).
2.2 PIOP: Phiên bản cải biên sản phẩm HyperPlonk và PermutationCheck------Áp dụng cho miền nhị phân
Thiết kế PIOP trong giao thức Binius đã tham khảo HyperPlonk, sử dụng một loạt 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: Xác minh chứng thực bảo mật ω và đầu vào công khai x có thỏa mãn quan hệ tính toán mạch C(x,ω)=0, để đảm bảo mạch hoạt động chính xác.
PermutationCheck: Xác thực xem kết quả đánh giá của hai đa thức đa biến f và g trên hypercube Boolean có phải là quan hệ hoán vị hay không f(x) = f(π(x)), để đảm bảo tính nhất quán của các biến đa thức.
LookupCheck: Xác minh xem giá trị của đa thức có nằm trong bảng tra cứu đã cho hay không, tức là f(Bµ) ⊆ T(Bµ), đảm bảo rằng một số giá trị nằm trong khoảng đã chỉ định.
MultisetCheck: Kiểm tra hai tập hợp đa biến có bằng nhau hay không, tức là {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, đảm bảo tính nhất quán giữa nhiều tập hợp.
ProductCheck：Kiểm tra xem giá trị của đa thức hợp lý trên siêu khối Boolean có bằng với một giá trị đã tuyên bố nào đó ∏x∈Hµ f(x) = s, để đảm bảo tính chính xác của tích đa thức.
ZeroCheck: Xác thực một đa biến đa thức tại bất kỳ điểm nào trên siêu lập phương Bool có phải là không ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, để đảm bảo phân bố của các điểm không của đa thức.
SumCheck: Kiểm tra xem tổng của đa thức nhiều biến có bằng giá trị đã tuyên bố hay không ∑x∈Hµ f(x) = s. Bằng cách chuyển đổi bài toán đánh giá đa thức nhiều biến thành bài toán đánh giá đa thức đơn biến, giảm độ phức tạp tính toán của bên xác minh. Ngoài ra, SumCheck còn cho phép xử lý hàng loạt bằng cách đưa vào số ngẫu nhiên, xây dựng tổ hợp tuyến tính để thực hiện xử lý hàng loạt cho nhiều trường hợp kiểm tra tổng.
BatchCheck: Dựa trên SumCheck, xác thực tính chính xác của nhiều giá trị đa thức đa biến để nâng cao hiệu quả của giao thức.
Mặc dù Binius và HyperPlonk có nhiều điểm tương đồng trong thiết kế giao thức, nhưng Binius đã cải tiến ở 3 khía cạnh sau:
Tối ưu hóa ProductCheck: Trong HyperPlonk, ProductCheck yêu cầu mẫu số U phải khác không trên siêu lập phương, và tích phải bằng một giá trị cụ thể; Binius đã đơn giản hóa quy trình kiểm tra này bằng cách đặc trưng hóa giá trị đó thành 1, từ đó giảm độ phức tạp tính toán.
Xử lý vấn đề chia cho không: HyperPlonk không xử lý đầy đủ trường hợp chia cho không, dẫn đến không thể khẳng định rằng U không bằng 0 trên siêu khối; Binius đã xử lý vấn đề này một cách chính xác, ngay cả khi mẫu số bằng 0, ProductCheck của Binius vẫn có thể tiếp tục xử lý, cho phép mở rộng đến bất kỳ giá trị tích nào.
Kiểm tra hoán vị giữa các cột: HyperPlonk không có chức năng này; Binius hỗ trợ kiểm tra hoán vị giữa nhiều cột, điều này cho phép Binius xử lý các trường hợp sắp xếp đa thức phức tạp hơn.
Vì vậy, Binius đã cải tiến cơ chế PIOPSumCheck hiện có, nâng cao tính linh hoạt và hiệu quả của giao thức, đặc biệt trong việc xử lý các xác minh đa biến đa thức phức tạp hơn, cung cấp hỗ trợ chức năng mạnh mẽ hơn. Những cải tiến này không chỉ giải quyết các hạn chế trong HyperPlonk mà còn đặt nền tảng cho các hệ thống chứng minh dựa trên miền nhị phân trong tương lai.
2.3 PIOP：tham số dịch đa tuyến mới------phù hợp với hypercube boolean
Trong giao thức Binius, việc xây dựng và xử lý đa thức ảo là một trong những kỹ thuật then chốt, có khả năng tạo ra và thao tác hiệu quả các đa thức được dẫn xuất từ tay cầm đầu vào hoặc từ các đa thức ảo khác. Dưới đây là hai phương pháp chính: