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 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ỏ, 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, 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.
Độ rộng mã hóa của STARKs thế hệ 1 là 252 bit, độ rộng mã hóa của STARKs thế hệ 2 là 64 bit, độ rộng mã hóa của STARKs thế hệ 3 là 32 bit, nhưng độ rộng mã hóa 32 bit vẫn còn 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 gọn gàng 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 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ể truy nguyên đến những năm 80 của thế kỷ trước. Hiện nay, trường nhị phân đã được áp dụng rộng rãi trong mật mã học, 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 miền F2128;
QR code, sử dụng mã hóa Reed-Solomon dựa trên F28;
Giao thức FRI nguyên thủy và zk-STARK, cùng với 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 trường 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 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 thực tế. Hầu hết các đa thức liên quan trong các phép tính của Prover không cần phải vào miền mở rộng, 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 tính 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 đã đưa ra một giải pháp đổi mới, xử lý hai vấn đề này một cách riêng biệt và thể hiện cùng một dữ liệu bằng hai cách khác nhau: đầu tiên, sử dụng đa biến (cụ thể là đa thức nhiều biến) thay thế cho đa thức một biến, thông qua các giá trị của nó trên "khối siêu" (hypercubes) để thể hiện toàn bộ quỹ đạo tính toán; thứ hai, do chiều dài của mỗi chiều trong khối siêu đều 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ể coi khối siêu như hình vuông (square), dựa trên hình vuông đó để thực hiện 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 Giải thích nguyên lý
Hiện tại, hầu hết các hệ thống SNARKs được xây dựng thường bao gồm hai phần sau:
Chứng minh Oracle tương tác đa thức lý thuyết thông tin (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP là cốt lõi của hệ thống chứng minh, 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 cho phép người chứng minh gửi dần dần các đa thức thông qua sự tương tác với người xác minh, nhờ đó người xác minh có thể xác minh tính chính xác của tính toán chỉ bằng cách truy vấn một lượng nhỏ kết quả đánh giá của các đ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 có cách xử lý các biểu thức đa thức khác nhau, từ đó ảnh hưởng đến hiệu suất và hiệu quả của 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 phương trình đa thức được sinh ra bởi PIOP có đúng hay không. PCS là một công cụ mật mã, 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 thông tin khác của đ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à tình huống áp dụng khác nhau.
Dựa trên nhu cầu cụ thể, lựa 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 elip phù hợp, có thể xây dựng 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 sự chú ý đến khả năng mở rộng, cũng như loại bỏ thiết lập đáng tin cậy trong giao thức ZCash.
• Plonky2: Kết hợp PLONK PIOP và FRI PCS, dựa trên miền Goldilocks. Plonky2 được thiết kế để đạt được tính tái diễn hiệu quả. Khi thiết kế các hệ thống này, PIOP và PCS được chọn phải tương thích với miền hữu hạn hoặc đường cong ellip đã sử dụng, nhằm đảm bảo tính chính xác, hiệu suất và độ an toàn của hệ thống. Sự lựa chọn của những kết hợp này không chỉ ảnh hưởng đến kích thước chứng minh SNARK và hiệu quả 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à liệu có thể hỗ trợ các chức năng mở rộng như chứng minh tái diễn hoặc chứng minh tổng hợp.
Binius: HyperPlonk PIOP + Brakedown PCS + lĩnh vực nhị phân. Cụ thể, Binius bao gồm năm công nghệ chủ chốt để đạt được hiệu quả và an ninh. Đầ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 HyperPlonk kiểm tra sản phẩm và hoán vị trong giao thức chứng minh Oracle tương tác của mình (PIOP), đả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à hoán vị của chúng. Thứ ba, giao thức giới thiệu một chứng minh dịch chuyển đ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 các lĩnh vực nhỏ. Thứ tư, Binius áp dụng chứng minh tìm kiếm Lasso cải tiến, cung cấp tính linh hoạt và an ninh 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ó thực hiện 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 Tập hợp hữu hạn: Toán học hóa dựa trên tháp của các trường nhị phân
Miền nhị phân tháp là yếu tố then chốt để thực hiện tính toán xác minh nhanh chóng, chủ yếu nhờ vào hai khía cạnh: tính toán hiệu quả và thuật toán hóa hiệu quả. Miền nhị phân về bản chất hỗ trợ các phép toán số học cực kỳ 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 thuật toán hóa đơn giản, 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. Những đặc điểm này, cộng với khả năng tận dụng tốt các đặc tính phân cấp thông qua cấu trúc tháp, làm cho miền 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" ám chỉ cách biểu diễn duy nhất và trực tiếp của các phần tử trong miền nhị phân. Ví dụ, trong miền nhị phân cơ bản F2, bất kỳ chuỗi k bit nào đều có thể được ánh xạ trực tiếp đến một phần tử miền nhị phân k bit. Điều này khác với miền số nguyên tố, nơi mà miền số nguyên tố không thể cung cấp cách biểu diễn chuẩn này trong một số bit đã cho. Mặc dù miền số nguyên tố 32 bit có thể nằm trong 32 bit, 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ử miền, trong khi miền nhị phân lại có thuận lợi cho việc ánh xạ một-một như vậy. Trong miền số nguyên tố Fp, các phương pháp giảm thiểu phổ biến bao gồm giảm thiểu Barrett, giảm thiểu Montgomery, cũng như các phương pháp giảm thiểu đặc biệt cho các miền hữu hạn cụ thể như Mersenne-31 hoặc Goldilocks-64. Trong miền nhị phân F2k, các phương pháp giảm thiểu thường dùng bao gồm giảm thiểu đặc biệt (như được sử dụng trong AES), giảm thiểu Montgomery (như được sử dụng trong POLYVAL) và giảm thiểu đệ quy (như Tower). Bài báo "Khám Phá Không Gian Thiết Kế của Các Triển Khai Phần Cứng ECC- Miền Số Nguyên Tố So Với Miền Nhị Phân" chỉ ra rằng miền nhị phân không cần phải đưa vào các ký hiệu khi thực hiện phép cộng và phép nhân, và phép bình phương trong miền nhị phân rất hiệu quả, vì nó tuân theo quy tắc rút gọn (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 bối cảnh miền nhị phân. Nó có thể được coi là một phần tử độc 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, 16 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à một chuyển đổi kiểu (typecast) cho chuỗi bit, là một thuộc tính 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 chi phí tính toán bổ sung. Giao thức Binius đã tận dụng đặc điểm này để nâng cao hiệu quả tính toán. Thêm vào đó, tài liệu "On Efficient Inversion in Tower Fields of Characteristic Two" đã khám phá độ phức tạp tính toán của phép nhân, phép bình phương và phép nghịch đảo trong miền nhị phân tháp n bit (có thể phân tách thành miền con m bit).
2.2 PIOP：Phiên bản cải biên HyperPlonk Product 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ác cơ chế kiểm tra cốt lõi để xác thực tính chính xác của các đa thức và tập hợp đa biến. Các kiểm tra cốt lõi này bao gồm:
GateCheck: Xác minh chứng nhận bảo mật ω và đầu vào công khai x có thỏa mãn mối quan hệ tính toán của mạch C(x,ω)=0, để đảm bảo mạch hoạt động chính xác.
PermutationCheck: Xác minh kết quả đánh giá của hai đa thức nhiều biến f và g trên siêu lập phương 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 sự sắp xếp giữ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 một số giá trị nằm trong khoảng đã chỉ định.
MultisetCheck: Kiểm tra xem 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 lập phương Boolean có bằng 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 minh xem một đa biến đa thức tại bất kỳ điểm nào trên hypercube Boolean có phải bằng không ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, để đảm bảo phân bố đ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ị được tuyên bố hay không ∑x∈Hµ f(x) = s. Bằng cách chuyển đổi vấn đề đánh giá đa thức nhiều biến thành đánh giá đa thức một 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ý theo lô, thông qua việc giới thiệu số ngẫu nhiên, xây dựng tổ hợp tuyến tính để thực hiện việc xử lý theo lô cho nhiều trường hợp kiểm tra tổng.
BatchCheck: Dựa trên SumCheck, xác minh tính chính xác của nhiều giá trị đa biến đa thức để 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 mọi điểm của hypercube, và tích phải bằng một giá trị cụ thể; Binius đã đơn giản hóa quá 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 0: HyperPlonk không xử lý đầy đủ trường hợp chia cho 0, dẫn đến không thể khẳng định vấn đề khác 0 của U trên siêu khối; Binius đã xử lý đúng vấn đề này, 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 PermutationCross: HyperPlonk không có chức năng này; Binius hỗ trợ kiểm tra Permutation 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.
Do đó, 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 là khi xử lý xác thực đa thức nhiều biến phức tạp, 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 những 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 lĩnh vực nhị phân trong tương lai.
2.3 PIOP：tham số dịch multi-linear mới------áp dụng cho 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 công nghệ quan trọng, có thể tạo ra và thao tác hiệu quả các đa thức được sinh từ các tay cầm đầu vào hoặc các đa thức ảo khác. Dưới đây là hai phương pháp chính:
Đóng gói：Phương pháp này thông qua việc đưa các phần tử nhỏ hơn ở vị trí liền kề trong thứ tự từ điển.
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.
13 thích
Phần thưởng
13
8
Chia sẻ
Bình luận
0/400
FlashLoanKing
· 07-15 19:54
Ba thế hệ sau vẫn cảm thấy lãng phí không gian à?
Xem bản gốcTrả lời0
GasWaster
· 07-14 17:00
Tối ưu hóa này cứng quá nhỉ? Tôi như não cá vàng nhìn mà choáng.
Xem bản gốcTrả lời0
screenshot_gains
· 07-14 05:52
Hiệu suất gọn nhẹ cuối cùng đã được đưa vào chương trình.
Binius: Tối ưu hóa đổi mới STARKs dựa trên lĩnh vực 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 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ỏ, 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, 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.
Độ rộng mã hóa của STARKs thế hệ 1 là 252 bit, độ rộng mã hóa của STARKs thế hệ 2 là 64 bit, độ rộng mã hóa của STARKs thế hệ 3 là 32 bit, nhưng độ rộng mã hóa 32 bit vẫn còn 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 gọn gàng 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 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ể truy nguyên đến những năm 80 của thế kỷ trước. Hiện nay, trường nhị phân đã được áp dụng rộng rãi trong mật mã học, 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 miền F2128;
QR code, sử dụng mã hóa Reed-Solomon dựa trên F28;
Giao thức FRI nguyên thủy và zk-STARK, cùng với 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 trường 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 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 thực tế. Hầu hết các đa thức liên quan trong các phép tính của Prover không cần phải vào miền mở rộng, 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 tính 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 đã đưa ra một giải pháp đổi mới, xử lý hai vấn đề này một cách riêng biệt và thể hiện cùng một dữ liệu bằng hai cách khác nhau: đầu tiên, sử dụng đa biến (cụ thể là đa thức nhiều biến) thay thế cho đa thức một biến, thông qua các giá trị của nó trên "khối siêu" (hypercubes) để thể hiện toàn bộ quỹ đạo tính toán; thứ hai, do chiều dài của mỗi chiều trong khối siêu đều 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ể coi khối siêu như hình vuông (square), dựa trên hình vuông đó để thực hiện 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 Giải thích nguyên lý
Hiện tại, hầu hết các hệ thống SNARKs được xây dựng thường bao gồm hai phần sau:
Chứng minh Oracle tương tác đa thức lý thuyết thông tin (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP là cốt lõi của hệ thống chứng minh, 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 cho phép người chứng minh gửi dần dần các đa thức thông qua sự tương tác với người xác minh, nhờ đó người xác minh có thể xác minh tính chính xác của tính toán chỉ bằng cách truy vấn một lượng nhỏ kết quả đánh giá của các đ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 có cách xử lý các biểu thức đa thức khác nhau, từ đó ảnh hưởng đến hiệu suất và hiệu quả của 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 phương trình đa thức được sinh ra bởi PIOP có đúng hay không. PCS là một công cụ mật mã, 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 thông tin khác của đ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à tình huống áp dụng khác nhau.
Dựa trên nhu cầu cụ thể, lựa 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 elip phù hợp, có thể xây dựng 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 sự chú ý đến khả năng mở rộng, cũng như loại bỏ thiết lập đáng tin cậy trong giao thức ZCash.
• Plonky2: Kết hợp PLONK PIOP và FRI PCS, dựa trên miền Goldilocks. Plonky2 được thiết kế để đạt được tính tái diễn hiệu quả. Khi thiết kế các hệ thống này, PIOP và PCS được chọn phải tương thích với miền hữu hạn hoặc đường cong ellip đã sử dụng, nhằm đảm bảo tính chính xác, hiệu suất và độ an toàn của hệ thống. Sự lựa chọn của những kết hợp này không chỉ ảnh hưởng đến kích thước chứng minh SNARK và hiệu quả 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à liệu có thể hỗ trợ các chức năng mở rộng như chứng minh tái diễn hoặc chứng minh tổng hợp.
Binius: HyperPlonk PIOP + Brakedown PCS + lĩnh vực nhị phân. Cụ thể, Binius bao gồm năm công nghệ chủ chốt để đạt được hiệu quả và an ninh. Đầ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 HyperPlonk kiểm tra sản phẩm và hoán vị trong giao thức chứng minh Oracle tương tác của mình (PIOP), đả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à hoán vị của chúng. Thứ ba, giao thức giới thiệu một chứng minh dịch chuyển đ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 các lĩnh vực nhỏ. Thứ tư, Binius áp dụng chứng minh tìm kiếm Lasso cải tiến, cung cấp tính linh hoạt và an ninh 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ó thực hiện 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 Tập hợp hữu hạn: Toán học hóa dựa trên tháp của các trường nhị phân
Miền nhị phân tháp là yếu tố then chốt để thực hiện tính toán xác minh nhanh chóng, chủ yếu nhờ vào hai khía cạnh: tính toán hiệu quả và thuật toán hóa hiệu quả. Miền nhị phân về bản chất hỗ trợ các phép toán số học cực kỳ 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 thuật toán hóa đơn giản, 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. Những đặc điểm này, cộng với khả năng tận dụng tốt các đặc tính phân cấp thông qua cấu trúc tháp, làm cho miền 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" ám chỉ cách biểu diễn duy nhất và trực tiếp của các phần tử trong miền nhị phân. Ví dụ, trong miền nhị phân cơ bản F2, bất kỳ chuỗi k bit nào đều có thể được ánh xạ trực tiếp đến một phần tử miền nhị phân k bit. Điều này khác với miền số nguyên tố, nơi mà miền số nguyên tố không thể cung cấp cách biểu diễn chuẩn này trong một số bit đã cho. Mặc dù miền số nguyên tố 32 bit có thể nằm trong 32 bit, 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ử miền, trong khi miền nhị phân lại có thuận lợi cho việc ánh xạ một-một như vậy. Trong miền số nguyên tố Fp, các phương pháp giảm thiểu phổ biến bao gồm giảm thiểu Barrett, giảm thiểu Montgomery, cũng như các phương pháp giảm thiểu đặc biệt cho các miền hữu hạn cụ thể như Mersenne-31 hoặc Goldilocks-64. Trong miền nhị phân F2k, các phương pháp giảm thiểu thường dùng bao gồm giảm thiểu đặc biệt (như được sử dụng trong AES), giảm thiểu Montgomery (như được sử dụng trong POLYVAL) và giảm thiểu đệ quy (như Tower). Bài báo "Khám Phá Không Gian Thiết Kế của Các Triển Khai Phần Cứng ECC- Miền Số Nguyên Tố So Với Miền Nhị Phân" chỉ ra rằng miền nhị phân không cần phải đưa vào các ký hiệu khi thực hiện phép cộng và phép nhân, và phép bình phương trong miền nhị phân rất hiệu quả, vì nó tuân theo quy tắc rút gọn (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 bối cảnh miền nhị phân. Nó có thể được coi là một phần tử độc 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, 16 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à một chuyển đổi kiểu (typecast) cho chuỗi bit, là một thuộc tính 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 chi phí tính toán bổ sung. Giao thức Binius đã tận dụng đặc điểm này để nâng cao hiệu quả tính toán. Thêm vào đó, tài liệu "On Efficient Inversion in Tower Fields of Characteristic Two" đã khám phá độ phức tạp tính toán của phép nhân, phép bình phương và phép nghịch đảo trong miền nhị phân tháp n bit (có thể phân tách thành miền con m bit).
2.2 PIOP：Phiên bản cải biên HyperPlonk Product 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ác cơ chế kiểm tra cốt lõi để xác thực tính chính xác của các đa thức và tập hợp đa biến. Các kiểm tra cốt lõi này bao gồm:
GateCheck: Xác minh chứng nhận bảo mật ω và đầu vào công khai x có thỏa mãn mối quan hệ tính toán của mạch C(x,ω)=0, để đảm bảo mạch hoạt động chính xác.
PermutationCheck: Xác minh kết quả đánh giá của hai đa thức nhiều biến f và g trên siêu lập phương 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 sự sắp xếp giữ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 một số giá trị nằm trong khoảng đã chỉ định.
MultisetCheck: Kiểm tra xem 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 lập phương Boolean có bằng 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 minh xem một đa biến đa thức tại bất kỳ điểm nào trên hypercube Boolean có phải bằng không ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, để đảm bảo phân bố đ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ị được tuyên bố hay không ∑x∈Hµ f(x) = s. Bằng cách chuyển đổi vấn đề đánh giá đa thức nhiều biến thành đánh giá đa thức một 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ý theo lô, thông qua việc giới thiệu số ngẫu nhiên, xây dựng tổ hợp tuyến tính để thực hiện việc xử lý theo lô cho nhiều trường hợp kiểm tra tổng.
BatchCheck: Dựa trên SumCheck, xác minh tính chính xác của nhiều giá trị đa biến đa thức để 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 mọi điểm của hypercube, và tích phải bằng một giá trị cụ thể; Binius đã đơn giản hóa quá 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 0: HyperPlonk không xử lý đầy đủ trường hợp chia cho 0, dẫn đến không thể khẳng định vấn đề khác 0 của U trên siêu khối; Binius đã xử lý đúng vấn đề này, 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 PermutationCross: HyperPlonk không có chức năng này; Binius hỗ trợ kiểm tra Permutation 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.
Do đó, 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 là khi xử lý xác thực đa thức nhiều biến phức tạp, 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 những 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 lĩnh vực nhị phân trong tương lai.
2.3 PIOP：tham số dịch multi-linear mới------áp dụng cho 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 công nghệ quan trọng, có thể tạo ra và thao tác hiệu quả các đa thức được sinh từ các tay cầm đầu vào hoặc các đa thức ảo khác. Dưới đây là hai phương pháp chính: