Phân tích nguyên lý của Binius STARKs và tư duy tối ưu hóa của nó
1 Giới thiệu
Không giống như SNARK dựa trên đường cong elip, STARK có thể được coi là SNARK dựa trên băm. Một trong những lý do chính dẫn đến sự kém hiệu quả hiện tại của STARK là hầu hết các giá trị trong chương trình thực tế đều nhỏ, chẳng hạn như các chỉ mục trong vòng lặp for, giá trị đúng và sai, bộ đếm, v.v. Tuy nhiên, để đảm bảo tính bảo mật của các bằng chứng dựa trên cây Merkle, khi dữ liệu được mở rộng bằng mã hóa Reed-Solomon, nhiều giá trị dư thừa bổ sung chiếm toàn bộ miền, mặc dù bản thân các giá trị ban đầu rất nhỏ. Để giải quyết vấn đề này, việc giảm kích thước của tên miền trở thành một chiến lược quan trọng.
Như thể hiện trong Bảng 1, STARK thế hệ đầu tiên là 252 bit, STARK thế hệ thứ hai là 64 bit và STARK thế hệ thứ ba là 32 bit. Ngược lại, miền nhị phân cho phép các hoạt động căn chỉnh bit trực tiếp và nhỏ gọn và hiệu quả trong việc mã hóa mà không lãng phí không gian, tức là STARK thế hệ thứ 4.
Bảng 1: Con đường tiến hóa của STARK
| Tính năng | STARK thế hệ thứ 1 | STARK thế hệ thứ 2 | STARK thế hệ thứ 3 | Thế hệ thứ 4 STARKs(Binius) |
|------|-------------|-------------|-------------|---------------------|
| Độ rộng bit mã | 252 bit | 64 bit | 32 bit | 1 bit |
| Hệ thống đại diện | StarkWare | Plonky2 | BabyBear | Binius |
So với các miền hữu hạn được phát hiện trong những năm gần đây, chẳng hạn như Goldilocks, BabyBear và Mersenne31, nghiên cứu về các miền nhị phân có thể bắt nguồn từ những năm 80 của thế kỷ trước. Hiện nay, các miền nhị phân đã được sử dụng rộng rãi trong mật mã, cá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 tên miền F28;
Mã xác thực tin nhắn Galois (GMAC), dựa trên tên miền F2128;
Mã QR, sử dụng mã hóa Reed-Solomon dựa trên F28;
Các giao thức FRI và zk-STARK ban đầu, cũng như hàm băm Grøstl đã lọt vào vòng chung kết SHA-3, dựa trên miền F28 và là một thuật toán băm phù hợp để đệ quy.
Khi sử dụng các tên miền nhỏ hơn, việc mở rộng hoạt động tên miền ngày càng trở nên quan trọng để đảm bảo tính bảo mật. Mặt khác, tên miền nhị phân được sử dụng bởi Binius cần dựa hoàn toàn vào việc mở rộng tên miền để đảm bảo tính bảo mật và tính khả dụng thực tế của nó. Hầu hết các đa thức liên quan đến các phép tính Prover không cần phải nhập miền mở rộng mà chỉ cần hoạt động dưới miền cơ sở, do đó đạt được hiệu quả cao trong các 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 được khoan vào một khu vực mở rộng lớn hơn để đảm bảo an ninh cần thiết.
Khi xây dựng một hệ thống chứng minh dựa trên các miền nhị phân, có hai vấn đề thực tế: khi tính toán biểu diễn dấu vết trong STARK, kích thước miền được sử dụng phải lớn hơn thứ tự của đa thức; Khi cây Merkle được hứa hẹn trong STARK, nó cần được mã hóa bằng Reed-Solomon và kích thước của miền được sử dụng phải lớn hơn kích thước của phần mở rộng mã hóa.
Binius đề xuất một giải pháp sáng tạo giải quyết hai vấn đề này một cách riêng biệt và làm như vậy bằng cách biểu diễn cùng một dữ liệu theo hai cách khác nhau: thứ nhất, sử dụng đa thức đa biến (cụ thể là đa tuyến) thay vì đa thức đơn biến và biểu diễn toàn bộ quỹ đạo tính toán bằng giá trị của nó trên "siêu lập phương"; Thứ hai, vì độ dài của mỗi chiều của siêu lập phương là 2, nên không thể thực hiện phần mở rộng Reed-Solomon tiêu chuẩn như STARK, nhưng siêu lập phương có thể được coi là một hình vuông dựa trên phần mở rộng Reed-Solomon. Phương pháp này cải thiện đáng kể hiệu quả mã hóa và hiệu suất tính toán trong khi vẫn đảm bảo tính bảo mật.
2 Phân tích nguyên tắc
Hiện tại, hầu hết các hệ thống SNARKs thường bao gồm hai phần sau:
Bằng chứng Oracle tương tác đa thức lý thuyết thông tin (PIOP) :P IOP làm cốt lõi của hệ thống chứng minh, chuyển đổi các mối quan hệ tính toán của đầu vào thành các phương trình đa thức có thể kiểm chứng được. Các giao thức PIOP khác nhau cho phép người chứng minh gửi đa thức từng bước bằng cách tương tác với trình xác thực, cho phép trình xác thực xác minh rằng phép tính là chính xác bằng cách truy vấn kết quả đánh giá của một số lượng nhỏ đa thức. Các giao thức PIOP hiện có bao gồm PLONK PIOP, Spartan PIOP và HyperPlonk PIOP, tất cả đều xử lý các biểu thức đa thức khác nhau, điều này ảnh hưởng đến hiệu suất và hiệu quả của toàn bộ hệ thống SNARK.
Sơ đồ cam kết đa thức (PCS): Sơ đồ cam kết đa thức được sử dụng để chứng minh liệu phương trình đa thức do PIOP tạo ra có đúng hay không. PCS là một công cụ mật mã mà qua đó người chứng minh có thể cam kết với một đa thức nhất định và sau đó xác minh kết quả đánh giá của đa thức đó, đồng thời ẩn các thông tin khác về đa thức đó. Các sơ đồ 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ó các kịch bản hiệu suất, bảo mật và ứng dụng khác nhau.
Theo yêu cầu cụ thể, có thể chọn PIOP và PCS khác nhau và kết hợp với các trường hữu hạn hoặc đường cong elip phù hợp, có thể xây dựng các hệ thống chứng minh với các đặc tính khác nhau. Chẳng hạn:
• Halo2: Được cung cấp bởi PLONK PIOP kết hợp với PCS chống đạn và dựa trên đường cong Pasta. Halo2 được thiết kế với khả năng mở rộng, cũng như loại bỏ thiết lập đáng tin cậy khỏi giao thức ZCash.
• Plonky2: Kết hợp PLONK PIOP với FRI PCS và dựa trên miền Goldilocks. Plonky2 là để đệ quy hiệu quả. 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 bằng chứng và hiệu quả xác minh của SNARK mà còn xác định liệu hệ thống có thể đạt được tính minh bạch mà không cần cài đặt đáng tin cậy hay không và liệu nó có thể hỗ trợ các chức năng mở rộng như bằng chứng đệ quy hoặc bằng chứng tổng hợp hay không.
Binius: HyperPlonk PIOP + Brakedown PCS + Miền nhị phân. Cụ thể, Binius bao gồm năm công nghệ chính để đạt được hiệu quả và an toàn. Trước hết, số học dựa trên các tháp của trường nhị phân tạo thành cơ sở cho các tính toán của nó, có thể thực hiện các phép toán đơn giản hóa trong các trường nhị phân. Thứ hai, trong Giao thức chứng minh Oracle (PIOP) tương tác, Binius đã điều chỉnh sản phẩm HyperPlonk và kiểm tra hoán vị để đả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 đối số dịch chuyển đa tuyến mới để tối ưu hóa hiệu quả của việc xác minh mối quan hệ đa tuyến trên một miền nhỏ. Thứ tư, Binius áp dụng một phiên bản cải tiến của đối số tra cứu Lasso, cung cấp tính linh hoạt và bảo mật mạnh mẽ cho cơ chế tra cứu. Cuối cùng, giao thức sử dụng sơ đồ cam kết đa thức trường nhỏ (PCS trường nhỏ), cho phép nó triển khai một hệ thống chứng minh hiệu quả trên miền nhị phân và giảm chi phí thường liên quan đến các miền lớn.
2.1 Trường hữu hạn: Số học dựa trên tháp trường nhị phân
Miền nhị phân tháp là chìa khóa để tính toán có thể xác minh nhanh, chủ yếu là do hai khía cạnh: tính toán hiệu quả và số học hóa hiệu quả. Các miền nhị phân vốn hỗ trợ các phép toán số học hiệu quả cao, khiến chúng trở nên lý tưởng cho các ứng dụng mật mã nhạy cảm với các yêu cầu về hiệu suất. Ngoài ra, cấu trúc miền nhị phân hỗ trợ một quá trình số học đơn giản hóa, tức là các phép toán được thực hiện trên miền nhị phân có thể được biểu diễn dưới dạng đại số nhỏ gọn và dễ dàng kiểm chứng. Những tính năng này, kết hợp với khả năng tận dụng tối đa bản chất phân cấp của nó thông qua các cấu trúc tháp, làm cho miền nhị phân đặc biệt thích hợp cho các hệ thống chứng minh có thể mở rộng như Binius
trong đó "canonical" đề cập đến một biểu diễn duy nhất và trực tiếp của một phần tử trong miền nhị phân. Ví dụ: trong miền nhị phân cơ bản nhất F2, bất kỳ chuỗi k-bit nào cũng có thể được ánh xạ trực tiếp đến phần tử miền nhị phân k-bit. Điều này trái ngược với trường số nguyên tố, không thể cung cấp một biểu diễn kinh điển như vậy trong vị trí nhất định. Mặc dù trường số nguyên tố 32 bit có thể được chứa trong hệ thống 32 bit, nhưng không phải mọi chuỗi 32 bit đều tương ứng duy nhất với một phần tử miền và các trường nhị phân có sự tiện lợi của ánh xạ một-một này. Trong miền nguyên tố Fp, các phương pháp rút ngắn phổ biến bao gồm suy Barrett, rút Montgomery và các phương pháp rút ngắn đặc biệt cho các trường 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 rút gọn thường được sử dụng bao gồm giảm đặc biệt (ví dụ: được sử dụng trong AES), rút gọn Montgomery (ví dụ: được sử dụng trong POLYVAL) và giảm đệ quy (ví dụ: Tower). Bài báo "Khám phá không gian thiết kế của trường nguyên tố so với trường nhị phân ECC-phần cứng triển khai" chỉ ra rằng miền nhị phân không cần phải giới thiệu carry trong cả phép cộng và nhân, và hoạt động bình phương của miền nhị phân rất hiệu quả vì nó tuân theo (X + Y )2 = X2 + Y 2.
Như thể hiện trong Hình 1, một chuỗi 128 bit: chuỗi này có thể được giải thích theo nhiều cách khác nhau trong bối 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 nó có thể được phân giải thành hai phần tử tháp 64 bit, bốn phần tử tháp 32 bit, 16 phần tử tháp 8 bit hoặc 128 phần tử miền F2. Tính linh hoạt của biểu diễn này không yêu cầu bất kỳ chi phí tính toán nào, chỉ cần một kiểu của các chuỗi bitwise, đây 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 thêm chi phí tính toán. Giao thức Binius tận dụng tính năng này để cải thiện hiệu quả tính toán. Ngoài ra, bài báo "Về sự đảo ngược hiệu quả trong các trường tháp của đặc điểm hai" khám phá độ phức tạp tính toán của các phép toán nhân, bình phương và đảo ngược trong miền nhị phân tháp n-bit có thể được phân tách thành các tên miền phụ m-bit.
2.2 PIOP: Sản phẩm HyperPlonk thích ứng và PermutationCheck ------ cho miền nhị phân
Thiết kế PIOP trong giao thức Binius vay mượn từ HyperPlonk và sử dụng một loạt các cơ chế kiểm tra lõi để xác minh tính đúng đắn của đa thức và tập đa biến. Các bài kiểm tra cốt lõi này bao gồm:
Kiểm tra cổng: Xác minh xem nhân chứng bí mật ω và đầu vào công khai x có đáp ứng mối quan hệ hoạt động mạch C(x, ω) = 0 để đảm bảo hoạt động chính xác của mạch hay không.
Kiểm tra hoán vị: Xác minh rằng kết quả đánh giá của hai đa thức đa biến f và g trên siêu khối Boolean là mối quan hệ hoán vị f(x) = f(π(x)) để đảm bảo tính nhất quán trong sự sắp xếp giữa các biến đa thức.
LookupCheck: Xác minh rằng đa thức đánh giá trong một bảng tra cứu nhất định, tức là f(Bμ) ⊆ T(Bμ), đảm bảo rằng một số giá trị nhất định nằm trong phạm vi được chỉ định.
MultisetCheck: Kiểm tra xem hai tậ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 bộ.
Kiểm tra sản phẩm: Kiểm tra xem việc đánh giá một đa thức hữu tỉ trên một siêu lập phương Boolean có bằng giá trị khai báo ∏x∈Hμ f(x) = s để đảm bảo tính đúng đắn của sản phẩm đa thức hay không.
ZeroCheck: Xác minh rằng một đa thức đa biến bằng không tại bất kỳ điểm nào trên hypercube∏x∈Hμ Boolean f(x) = 0,∀x ∈ Bμ để đảm bảo phân bố bằng không của đa thức.
Kiểm tra tổng: Kiểm tra xem giá trị tổng của đa thức đa biến có phải là giá trị đã khai báo ∑x∈Hμ f(x) = s hay không. Bằng cách chuyển đổi bài toán đánh giá của đa thức đa biến thành đánh giá đa thức đơn biến, độ phức tạp tính toán của trình xác minh được giảm bớt. Ngoài ra, SumCheck cũng cho phép xử lý hàng loạt, bằng cách giới thiệu các số ngẫu nhiên, xây dựng các tổ hợp tuyến tính để đạt được xử lý hàng loạt của nhiều trường hợp kiểm tra tổng.
Kiểm tra hàng loạt: Dựa trên SumCheck, xác minh tính đúng đắn của nhiều đánh giá đa thức đa biến để cải thiện hiệu quả giao thức.
Mặc dù có nhiều điểm tương đồng giữa Binius và HyperPlonk về thiết kế giao thức, Binius đã thực hiện những cải tiến ở ba khía cạnh sau:
Tối ưu hóa ProductCheck: Trong HyperPlonk, ProductCheck yêu cầu mẫu số U không được bằng 0 ở mọi vị trí trên siêu khối, 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 chuyên biệt hóa giá trị đó thành 1, từ đó giảm độ phức tạp tính toán.
Xử lý bài toán chia không: HyperPlonk không xử lý đầy đủ trường hợp chia không, dẫn đến không có khả năng khẳng định bài toán không phải là không của U trên hypercube; Binius xử lý điều này một cách chính xác và ProductCheck của Binius tiếp tục xử lý ngay cả khi mẫu số bằng không, cho phép khái quát hóa các giá trị sản phẩm tùy ý.
Kiểm tra hoán vị: Tính năng này không khả dụng trong HyperPlonk; Binius hỗ trợ PermutationCheck giữa nhiều cột, cho phép Binius xử lý hoán vị đa thức phức tạp hơn.
Do đó, thông qua việc cải tiến cơ chế PIOPSumCheck hiện có, Binius cải thiện tính linh hoạt và hiệu quả của giao thức, đặc biệt là khi xử lý xác minh đa thức đa biến phức tạp hơn và 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 cung cấp một nền tảng dựa trên nhị phân cho tương lai
Xem bản gốc
Nội dung chỉ mang tính chất tham khảo, không phải là lời chào mời hay đề nghị. Không cung cấp tư vấn về đầu tư, thuế hoặc pháp lý. Xem Tuyên bố miễn trừ trách nhiệm để biết thêm thông tin về rủi ro.
Phân tích Binius STARKs: Hệ thống chứng minh không biết hiệu quả dựa trên trường nhị phân
Phân tích nguyên lý của Binius STARKs và tư duy tối ưu hóa của nó
1 Giới thiệu
Không giống như SNARK dựa trên đường cong elip, STARK có thể được coi là SNARK dựa trên băm. Một trong những lý do chính dẫn đến sự kém hiệu quả hiện tại của STARK là hầu hết các giá trị trong chương trình thực tế đều nhỏ, chẳng hạn như các chỉ mục trong vòng lặp for, giá trị đúng và sai, bộ đếm, v.v. Tuy nhiên, để đảm bảo tính bảo mật của các bằng chứng dựa trên cây Merkle, khi dữ liệu được mở rộng bằng mã hóa Reed-Solomon, nhiều giá trị dư thừa bổ sung chiếm toàn bộ miền, mặc dù bản thân các giá trị ban đầu rất nhỏ. Để giải quyết vấn đề này, việc giảm kích thước của tên miền trở thành một chiến lược quan trọng.
Như thể hiện trong Bảng 1, STARK thế hệ đầu tiên là 252 bit, STARK thế hệ thứ hai là 64 bit và STARK thế hệ thứ ba là 32 bit. Ngược lại, miền nhị phân cho phép các hoạt động căn chỉnh bit trực tiếp và nhỏ gọn và hiệu quả trong việc mã hóa mà không lãng phí không gian, tức là STARK thế hệ thứ 4.
Bảng 1: Con đường tiến hóa của STARK
| Tính năng | STARK thế hệ thứ 1 | STARK thế hệ thứ 2 | STARK thế hệ thứ 3 | Thế hệ thứ 4 STARKs(Binius) | |------|-------------|-------------|-------------|---------------------| | Độ rộng bit mã | 252 bit | 64 bit | 32 bit | 1 bit | | Hệ thống đại diện | StarkWare | Plonky2 | BabyBear | Binius |
So với các miền hữu hạn được phát hiện trong những năm gần đây, chẳng hạn như Goldilocks, BabyBear và Mersenne31, nghiên cứu về các miền nhị phân có thể bắt nguồn từ những năm 80 của thế kỷ trước. Hiện nay, các miền nhị phân đã được sử dụng rộng rãi trong mật mã, cá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 tên miền F28;
Mã xác thực tin nhắn Galois (GMAC), dựa trên tên miền F2128;
Mã QR, sử dụng mã hóa Reed-Solomon dựa trên F28;
Các giao thức FRI và zk-STARK ban đầu, cũng như hàm băm Grøstl đã lọt vào vòng chung kết SHA-3, dựa trên miền F28 và là một thuật toán băm phù hợp để đệ quy.
Khi sử dụng các tên miền nhỏ hơn, việc mở rộng hoạt động tên miền ngày càng trở nên quan trọng để đảm bảo tính bảo mật. Mặt khác, tên miền nhị phân được sử dụng bởi Binius cần dựa hoàn toàn vào việc mở rộng tên miền để đảm bảo tính bảo mật và tính khả dụng thực tế của nó. Hầu hết các đa thức liên quan đến các phép tính Prover không cần phải nhập miền mở rộng mà chỉ cần hoạt động dưới miền cơ sở, do đó đạt được hiệu quả cao trong các 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 được khoan vào một khu vực mở rộng lớn hơn để đảm bảo an ninh cần thiết.
Khi xây dựng một hệ thống chứng minh dựa trên các miền nhị phân, có hai vấn đề thực tế: khi tính toán biểu diễn dấu vết trong STARK, kích thước miền được sử dụng phải lớn hơn thứ tự của đa thức; Khi cây Merkle được hứa hẹn trong STARK, nó cần được mã hóa bằng Reed-Solomon và kích thước của miền được sử dụng phải lớn hơn kích thước của phần mở rộng mã hóa.
Binius đề xuất một giải pháp sáng tạo giải quyết hai vấn đề này một cách riêng biệt và làm như vậy bằng cách biểu diễn cùng một dữ liệu theo hai cách khác nhau: thứ nhất, sử dụng đa thức đa biến (cụ thể là đa tuyến) thay vì đa thức đơn biến và biểu diễn toàn bộ quỹ đạo tính toán bằng giá trị của nó trên "siêu lập phương"; Thứ hai, vì độ dài của mỗi chiều của siêu lập phương là 2, nên không thể thực hiện phần mở rộng Reed-Solomon tiêu chuẩn như STARK, nhưng siêu lập phương có thể được coi là một hình vuông dựa trên phần mở rộng Reed-Solomon. Phương pháp này cải thiện đáng kể hiệu quả mã hóa và hiệu suất tính toán trong khi vẫn đảm bảo tính bảo mật.
2 Phân tích nguyên tắc
Hiện tại, hầu hết các hệ thống SNARKs thường bao gồm hai phần sau:
Bằng chứng Oracle tương tác đa thức lý thuyết thông tin (PIOP) :P IOP làm cốt lõi của hệ thống chứng minh, chuyển đổi các mối quan hệ tính toán của đầu vào thành các phương trình đa thức có thể kiểm chứng được. Các giao thức PIOP khác nhau cho phép người chứng minh gửi đa thức từng bước bằng cách tương tác với trình xác thực, cho phép trình xác thực xác minh rằng phép tính là chính xác bằng cách truy vấn kết quả đánh giá của một số lượng nhỏ đa thức. Các giao thức PIOP hiện có bao gồm PLONK PIOP, Spartan PIOP và HyperPlonk PIOP, tất cả đều xử lý các biểu thức đa thức khác nhau, điều này ảnh hưởng đến hiệu suất và hiệu quả của toàn bộ hệ thống SNARK.
Sơ đồ cam kết đa thức (PCS): Sơ đồ cam kết đa thức được sử dụng để chứng minh liệu phương trình đa thức do PIOP tạo ra có đúng hay không. PCS là một công cụ mật mã mà qua đó người chứng minh có thể cam kết với một đa thức nhất định và sau đó xác minh kết quả đánh giá của đa thức đó, đồng thời ẩn các thông tin khác về đa thức đó. Các sơ đồ 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ó các kịch bản hiệu suất, bảo mật và ứng dụng khác nhau.
Theo yêu cầu cụ thể, có thể chọn PIOP và PCS khác nhau và kết hợp với các trường hữu hạn hoặc đường cong elip phù hợp, có thể xây dựng các hệ thống chứng minh với các đặc tính khác nhau. Chẳng hạn:
• Halo2: Được cung cấp bởi PLONK PIOP kết hợp với PCS chống đạn và dựa trên đường cong Pasta. Halo2 được thiết kế với khả năng mở rộng, cũng như loại bỏ thiết lập đáng tin cậy khỏi giao thức ZCash.
• Plonky2: Kết hợp PLONK PIOP với FRI PCS và dựa trên miền Goldilocks. Plonky2 là để đệ quy hiệu quả. 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 bằng chứng và hiệu quả xác minh của SNARK mà còn xác định liệu hệ thống có thể đạt được tính minh bạch mà không cần cài đặt đáng tin cậy hay không và liệu nó có thể hỗ trợ các chức năng mở rộng như bằng chứng đệ quy hoặc bằng chứng tổng hợp hay không.
Binius: HyperPlonk PIOP + Brakedown PCS + Miền nhị phân. Cụ thể, Binius bao gồm năm công nghệ chính để đạt được hiệu quả và an toàn. Trước hết, số học dựa trên các tháp của trường nhị phân tạo thành cơ sở cho các tính toán của nó, có thể thực hiện các phép toán đơn giản hóa trong các trường nhị phân. Thứ hai, trong Giao thức chứng minh Oracle (PIOP) tương tác, Binius đã điều chỉnh sản phẩm HyperPlonk và kiểm tra hoán vị để đả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 đối số dịch chuyển đa tuyến mới để tối ưu hóa hiệu quả của việc xác minh mối quan hệ đa tuyến trên một miền nhỏ. Thứ tư, Binius áp dụng một phiên bản cải tiến của đối số tra cứu Lasso, cung cấp tính linh hoạt và bảo mật mạnh mẽ cho cơ chế tra cứu. Cuối cùng, giao thức sử dụng sơ đồ cam kết đa thức trường nhỏ (PCS trường nhỏ), cho phép nó triển khai một hệ thống chứng minh hiệu quả trên miền nhị phân và giảm chi phí thường liên quan đến các miền lớn.
2.1 Trường hữu hạn: Số học dựa trên tháp trường nhị phân
Miền nhị phân tháp là chìa khóa để tính toán có thể xác minh nhanh, chủ yếu là do hai khía cạnh: tính toán hiệu quả và số học hóa hiệu quả. Các miền nhị phân vốn hỗ trợ các phép toán số học hiệu quả cao, khiến chúng trở nên lý tưởng cho các ứng dụng mật mã nhạy cảm với các yêu cầu về hiệu suất. Ngoài ra, cấu trúc miền nhị phân hỗ trợ một quá trình số học đơn giản hóa, tức là các phép toán được thực hiện trên miền nhị phân có thể được biểu diễn dưới dạng đại số nhỏ gọn và dễ dàng kiểm chứng. Những tính năng này, kết hợp với khả năng tận dụng tối đa bản chất phân cấp của nó thông qua các cấu trúc tháp, làm cho miền nhị phân đặc biệt thích hợp cho các hệ thống chứng minh có thể mở rộng như Binius
trong đó "canonical" đề cập đến một biểu diễn duy nhất và trực tiếp của một phần tử trong miền nhị phân. Ví dụ: trong miền nhị phân cơ bản nhất F2, bất kỳ chuỗi k-bit nào cũng có thể được ánh xạ trực tiếp đến phần tử miền nhị phân k-bit. Điều này trái ngược với trường số nguyên tố, không thể cung cấp một biểu diễn kinh điển như vậy trong vị trí nhất định. Mặc dù trường số nguyên tố 32 bit có thể được chứa trong hệ thống 32 bit, nhưng không phải mọi chuỗi 32 bit đều tương ứng duy nhất với một phần tử miền và các trường nhị phân có sự tiện lợi của ánh xạ một-một này. Trong miền nguyên tố Fp, các phương pháp rút ngắn phổ biến bao gồm suy Barrett, rút Montgomery và các phương pháp rút ngắn đặc biệt cho các trường 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 rút gọn thường được sử dụng bao gồm giảm đặc biệt (ví dụ: được sử dụng trong AES), rút gọn Montgomery (ví dụ: được sử dụng trong POLYVAL) và giảm đệ quy (ví dụ: Tower). Bài báo "Khám phá không gian thiết kế của trường nguyên tố so với trường nhị phân ECC-phần cứng triển khai" chỉ ra rằng miền nhị phân không cần phải giới thiệu carry trong cả phép cộng và nhân, và hoạt động bình phương của miền nhị phân rất hiệu quả vì nó tuân theo (X + Y )2 = X2 + Y 2.
! Nghiên cứu Bitlayer: Phân tích nguyên tắc Binius STARKs và tư duy tối ưu hóa
Như thể hiện trong Hình 1, một chuỗi 128 bit: chuỗi này có thể được giải thích theo nhiều cách khác nhau trong bối 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 nó có thể được phân giải thành hai phần tử tháp 64 bit, bốn phần tử tháp 32 bit, 16 phần tử tháp 8 bit hoặc 128 phần tử miền F2. Tính linh hoạt của biểu diễn này không yêu cầu bất kỳ chi phí tính toán nào, chỉ cần một kiểu của các chuỗi bitwise, đây 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 thêm chi phí tính toán. Giao thức Binius tận dụng tính năng này để cải thiện hiệu quả tính toán. Ngoài ra, bài báo "Về sự đảo ngược hiệu quả trong các trường tháp của đặc điểm hai" khám phá độ phức tạp tính toán của các phép toán nhân, bình phương và đảo ngược trong miền nhị phân tháp n-bit có thể được phân tách thành các tên miền phụ m-bit.
2.2 PIOP: Sản phẩm HyperPlonk thích ứng và PermutationCheck ------ cho miền nhị phân
Thiết kế PIOP trong giao thức Binius vay mượn từ HyperPlonk và sử dụng một loạt các cơ chế kiểm tra lõi để xác minh tính đúng đắn của đa thức và tập đa biến. Các bài kiểm tra cốt lõi này bao gồm:
Kiểm tra cổng: Xác minh xem nhân chứng bí mật ω và đầu vào công khai x có đáp ứng mối quan hệ hoạt động mạch C(x, ω) = 0 để đảm bảo hoạt động chính xác của mạch hay không.
Kiểm tra hoán vị: Xác minh rằng kết quả đánh giá của hai đa thức đa biến f và g trên siêu khối Boolean là mối quan hệ hoán vị f(x) = f(π(x)) để đảm bảo tính nhất quán trong sự sắp xếp giữa các biến đa thức.
LookupCheck: Xác minh rằng đa thức đánh giá trong một bảng tra cứu nhất định, tức là f(Bμ) ⊆ T(Bμ), đảm bảo rằng một số giá trị nhất định nằm trong phạm vi được chỉ định.
MultisetCheck: Kiểm tra xem hai tậ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 bộ.
Kiểm tra sản phẩm: Kiểm tra xem việc đánh giá một đa thức hữu tỉ trên một siêu lập phương Boolean có bằng giá trị khai báo ∏x∈Hμ f(x) = s để đảm bảo tính đúng đắn của sản phẩm đa thức hay không.
ZeroCheck: Xác minh rằng một đa thức đa biến bằng không tại bất kỳ điểm nào trên hypercube∏x∈Hμ Boolean f(x) = 0,∀x ∈ Bμ để đảm bảo phân bố bằng không của đa thức.
Kiểm tra tổng: Kiểm tra xem giá trị tổng của đa thức đa biến có phải là giá trị đã khai báo ∑x∈Hμ f(x) = s hay không. Bằng cách chuyển đổi bài toán đánh giá của đa thức đa biến thành đánh giá đa thức đơn biến, độ phức tạp tính toán của trình xác minh được giảm bớt. Ngoài ra, SumCheck cũng cho phép xử lý hàng loạt, bằng cách giới thiệu các số ngẫu nhiên, xây dựng các tổ hợp tuyến tính để đạt được xử lý hàng loạt của nhiều trường hợp kiểm tra tổng.
Kiểm tra hàng loạt: Dựa trên SumCheck, xác minh tính đúng đắn của nhiều đánh giá đa thức đa biến để cải thiện hiệu quả giao thức.
Mặc dù có nhiều điểm tương đồng giữa Binius và HyperPlonk về thiết kế giao thức, Binius đã thực hiện những cải tiến ở ba khía cạnh sau:
Tối ưu hóa ProductCheck: Trong HyperPlonk, ProductCheck yêu cầu mẫu số U không được bằng 0 ở mọi vị trí trên siêu khối, 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 chuyên biệt hóa giá trị đó thành 1, từ đó giảm độ phức tạp tính toán.
Xử lý bài toán chia không: HyperPlonk không xử lý đầy đủ trường hợp chia không, dẫn đến không có khả năng khẳng định bài toán không phải là không của U trên hypercube; Binius xử lý điều này một cách chính xác và ProductCheck của Binius tiếp tục xử lý ngay cả khi mẫu số bằng không, cho phép khái quát hóa các giá trị sản phẩm tùy ý.
Kiểm tra hoán vị: Tính năng này không khả dụng trong HyperPlonk; Binius hỗ trợ PermutationCheck giữa nhiều cột, cho phép Binius xử lý hoán vị đa thức phức tạp hơn.
Do đó, thông qua việc cải tiến cơ chế PIOPSumCheck hiện có, Binius cải thiện tính linh hoạt và hiệu quả của giao thức, đặc biệt là khi xử lý xác minh đa thức đa biến phức tạp hơn và 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 cung cấp một nền tảng dựa trên nhị phân cho tương lai