Phân tích nguyên lý Binius STARKs và suy nghĩ tối ưu hóa
1 Giới thiệu
Một trong những lý do chính dẫn đến hiệu suất thấp của STARKs 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ã Reed-Solomon để mở rộng dữ liệu sẽ tạo ra nhiều giá trị dư thừa chiếm giữ toàn bộ miền, ngay cả khi giá trị ban đầu 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.
Như bảng 1 đã chỉ ra, bề rộng mã hóa của STARKs thế hệ đầu tiên là 252bit, bề rộng mã hóa của STARKs thế hệ thứ hai là 64bit, và bề rộng mã hóa của STARKs thế hệ thứ ba là 32bit, nhưng bề rộng mã hóa 32bit vẫn còn rất nhiều không gian lãng phí. So với điều đó, 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ó bất kỳ không gian lãng phí nào, tức là STARKs thế hệ thứ tư.
Bảng 1: Đường dẫn biến thể STARKs
| Đại số | Bề rộng mã hóa | Ví dụ |
|------|----------|------|
| Thế hệ 1 | 252bit | Ethereum STARKs |
| Thế hệ thứ 2 | 64bit | Plonky2 |
| Thế hệ thứ 3 | 32bit | BabyBear |
| Thế hệ thứ 4 | 1bit | Binius |
So với Goldilocks, BabyBear, Mersenne31 và các nghiên cứu mới về miền hữu hạn trong những năm gần đây, nghiên cứu về miền nhị phân có thể được truy nguyên đến thập niên 80 của thế kỷ trước. Hiện nay, miền nhị phân đã được ứng dụng rộng rãi trong 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
Galois mã xác thực tin nhắn ( GMAC ), dựa trên trường F2128
Mã QR, sử dụng mã hóa Reed-Solomon dựa trên F28
Giao thức FRI gốc và zk-STARK, cùng với hàm băm Grøstl lọt 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, việ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 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 đã đề xuất 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à đạt được điều đó bằng cách biểu diễn cùng một dữ liệu theo hai cách khác nhau: đầu tiên, sử dụng đa biến ( thay thế cho đa thức đơn biến, thông qua giá trị của nó trên các "hyper-cube" ) để biểu diễn toàn bộ quỹ đạo tính toán; thứ hai, do chiều dài của mỗi chiều trong hyper-cube đề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 hyper-cube như một hình vuông ( và thực hiện mở rộng Reed-Solomon dựa trên hình vuông đó. Phương pháp này không chỉ đảm bảo tính an toàn mà cò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 đượ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 như là cốt lõi của hệ thống chứng minh, biến đổi các 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 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 tính toán thông qua việc truy vấn một số 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 đều có cách xử lý khác nhau đối với các biểu thức đa thức, từ đó ảnh hưởng đến hiệu suất và hiệu quả của toàn bộ hệ thống SNARK.
Phương án cam kết đa thức ) Polynomial Commitment Scheme, PCS (: Phương án cam kết đa thức được sử dụng để chứng minh xem các 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ã, 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 của đa thức. Các phương án 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à các tình huống áp 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: được kết hợp từ PLONK PIOP và Bulletproofs PCS, và 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: 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 đệ quy 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 elip được 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 các tổ hợp này không chỉ ảnh hưởng đến kích thước chứng minh 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à liệu có thể hỗ trợ các tính 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 + 二进制域。Cụ thể, Binius bao gồm năm công nghệ chính để đạt được hiệu quả và độ an toàn của nó. Đầu tiên, dựa trên cấu trúc số học của các tháp trường nhị phân )towers of binary fields( đã tạo thành nền tảng cho các phép tính của nó, có khả năng thực hiện các phép toán đơn giản trong trường nhị phân. Thứ hai, Binius trong giao thức chứng minh Oracle tương tác của nó )PIOP(, đã điều chỉnh kiểm tra sản phẩm và hoán vị HyperPlonk, đảm bảo kiểm tra 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 suất xác minh các mối quan hệ đa tuyến trên các trường nhỏ. Thứ tư, Binius sử dụng một phiên bản cải tiến của chứng minh tìm kiếm Lasso, 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 một kế hoạch cam kết đa thức trên trường nhỏ )Small-Field PCS(, cho phép nó thực hiện hệ thống chứng minh hiệu quả trên trường nhị phân và giảm thiểu chi phí thường liên quan đến các trường lớn.
) 2.1 Miền hữu hạn: Toán tử hóa dựa trên towers of binary fields
Trường nhị phân tháp là chìa khóa để thực hiện tính toán có thể 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à số học 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, làm cho 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 hiệu suất. Ngoài ra, cấu trúc trường nhị phân hỗ trợ quá trình số học đơ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 đầy đủ các đặc điểm phân cấp thông qua cấu trúc tháp, làm cho trường nhị phân đặc biệt phù hợp cho 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 k bit. Điều này khác với trường số nguyên tố, nơi mà trường số nguyên tố không thể cung cấp cách biểu diễn tiêu chuẩn trong một số bit nhất định. Mặc dù trường số nguyên tố 32 bit có thể được chứa trong 32 bit, nhưng không phải mọi chuỗi 32 bit đều có thể tương ứng một cách duy nhất với một phần tử trường, trong khi trường nhị phân lại có sự thuận lợi của ánh xạ một-một này. Trong trường số 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 nhất định như Mersenne-31 hoặc Goldilocks-64. Trong trường nhị phân F2k, các phương pháp giảm thường dùng bao gồm giảm đặc biệt ( như được sử dụng trong AES ), giảm Montgomery ### như được sử dụng trong POLYVAL ( và giảm đệ quy ) như Tower (. Bài báo "Khám Phá Không Gian Thiết Kế của ECC-Hardware Triển Khai Trường Số 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 giới thiệu các chữ số mang trong các phép toán cộng và nhân, và phép toán bình phương trong trường nhị phân rất hiệu quả, vì nó tuân theo quy tắc đơn giả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 diễn giải 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ử độc đáo trong miền nhị phân 128 bit, hoặc được giải thích là 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. Sự 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 phép chuyển đổi kiểu chuỗi bit )typecast(, đâ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 đặc điểm này để cải thiện hiệu quả tính toán. Hơn nữa, 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, bình phương và phép đảo ngược trong miền tháp nhị phân n bit ) có thể phân rã thành miền con m bit (.
![Bitlayer Research：Phân tích nguyên lý của Binius STARKs và những suy nghĩ tối ưu hóa])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: Phiên bản sửa đổi HyperPlonk Product và PermutationCheck------Áp dụng cho trường 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 chính xác của đa thức và tập hợp nhiều biến. Những 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 đúng.
PermutationCheck: Xác minh kết quả đánh giá của hai đa thức nhiều 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 sự sắp xếp giữa các biến đa thức.
LookupCheck: Xác minh rằng giá trị của đa thức có trong bảng tra cứu đã cho, tức là f(Bµ) ⊆ T)Bµ(, đảm bảo rằng một số giá trị nằm trong khoảng được 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 việc đánh giá đa thức hữu tỷ trên khối siêu Boolean có bằng một giá trị được 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 một đa thức nhiều biến trên hypercube boolean có phải là zero tại bất kỳ điểm nào ∏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 giá trị 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 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ô, bằng cách đưa ra số ngẫu nhiên, xây dựng tổ hợp tuyến tính để thực hiện 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 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ó những cải tiến trong 3 lĩnh vực sau:
Tối ưu hóa ProductCheck: Trong HyperPlonk, ProductCheck yêu cầu mẫu số U không được bằng không ở mọi nơi 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 đủ tình huống chia cho không, dẫn đến không thể khẳng định vấn đề không bằng không của U trên siêu khối; Binius đã xử lý đúng vấn đề này, ngay cả trong trường hợp mẫu số bằng không, 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ó tính 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.
Do đó, Binius đã cải tiến cơ chế PIOPSumCheck hiện tại, nâng cao tính linh hoạt và hiệu quả của giao thức, đặc biệt là trong việc xử lý các xác thực đ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 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 miền nhị phân trong tương lai.
) 2.3 PIOP: lập luận dịch chuyển đa tuyến mới ------ áp dụng cho hypercube boolean
Trong giao thức Binius, đa dạng ảo
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.
6 thích
Phần thưởng
6
3
Chia sẻ
Bình luận
0/400
ETHReserveBank
· 16giờ trước
on-chain chi phí giảm xuống ai mà không vui chứ
Xem bản gốcTrả lời0
ChainChef
· 23giờ trước
đang nấu một ít thông tin mới ở đây... binius trông giống như một loại sốt hoàn hảo được giảm thiểu so với những công thức 252-bit phình to đó thật lòng mà nói
Binius: Tối ưu hóa đột phá của miền nhị phân STARKs
Phân tích nguyên lý Binius STARKs và suy nghĩ tối ưu hóa
1 Giới thiệu
Một trong những lý do chính dẫn đến hiệu suất thấp của STARKs 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ã Reed-Solomon để mở rộng dữ liệu sẽ tạo ra nhiều giá trị dư thừa chiếm giữ toàn bộ miền, ngay cả khi giá trị ban đầu 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.
Như bảng 1 đã chỉ ra, bề rộng mã hóa của STARKs thế hệ đầu tiên là 252bit, bề rộng mã hóa của STARKs thế hệ thứ hai là 64bit, và bề rộng mã hóa của STARKs thế hệ thứ ba là 32bit, nhưng bề rộng mã hóa 32bit vẫn còn rất nhiều không gian lãng phí. So với điều đó, 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ó bất kỳ không gian lãng phí nào, tức là STARKs thế hệ thứ tư.
Bảng 1: Đường dẫn biến thể STARKs
| Đại số | Bề rộng mã hóa | Ví dụ | |------|----------|------| | Thế hệ 1 | 252bit | Ethereum STARKs |
| Thế hệ thứ 2 | 64bit | Plonky2 | | Thế hệ thứ 3 | 32bit | BabyBear | | Thế hệ thứ 4 | 1bit | Binius |
So với Goldilocks, BabyBear, Mersenne31 và các nghiên cứu mới về miền hữu hạn trong những năm gần đây, nghiên cứu về miền nhị phân có thể được truy nguyên đến thập niên 80 của thế kỷ trước. Hiện nay, miền nhị phân đã được ứng dụng rộng rãi trong mật mã, ví dụ điển hình bao gồm:
Khi sử dụng miền nhỏ hơn, việ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 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 đã đề xuất 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à đạt được điều đó bằng cách biểu diễn cùng một dữ liệu theo hai cách khác nhau: đầu tiên, sử dụng đa biến ( thay thế cho đa thức đơn biến, thông qua giá trị của nó trên các "hyper-cube" ) để biểu diễn toàn bộ quỹ đạo tính toán; thứ hai, do chiều dài của mỗi chiều trong hyper-cube đề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 hyper-cube như một hình vuông ( và thực hiện mở rộng Reed-Solomon dựa trên hình vuông đó. Phương pháp này không chỉ đảm bảo tính an toàn mà cò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 đượ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 như là cốt lõi của hệ thống chứng minh, biến đổi các 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 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 tính toán thông qua việc truy vấn một số 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 đều có cách xử lý khác nhau đối với các biểu thức đa thức, từ đó ảnh hưởng đến hiệu suất và hiệu quả của toàn bộ hệ thống SNARK.
Phương án cam kết đa thức ) Polynomial Commitment Scheme, PCS (: Phương án cam kết đa thức được sử dụng để chứng minh xem các 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ã, 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 của đa thức. Các phương án 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à các tình huống áp 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: được kết hợp từ PLONK PIOP và Bulletproofs PCS, và 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: 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 đệ quy 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 elip được 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 các tổ hợp này không chỉ ảnh hưởng đến kích thước chứng minh 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à liệu có thể hỗ trợ các tính 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 + 二进制域。Cụ thể, Binius bao gồm năm công nghệ chính để đạt được hiệu quả và độ an toàn của nó. Đầu tiên, dựa trên cấu trúc số học của các tháp trường nhị phân )towers of binary fields( đã tạo thành nền tảng cho các phép tính của nó, có khả năng thực hiện các phép toán đơn giản trong trường nhị phân. Thứ hai, Binius trong giao thức chứng minh Oracle tương tác của nó )PIOP(, đã điều chỉnh kiểm tra sản phẩm và hoán vị HyperPlonk, đảm bảo kiểm tra 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 suất xác minh các mối quan hệ đa tuyến trên các trường nhỏ. Thứ tư, Binius sử dụng một phiên bản cải tiến của chứng minh tìm kiếm Lasso, 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 một kế hoạch cam kết đa thức trên trường nhỏ )Small-Field PCS(, cho phép nó thực hiện hệ thống chứng minh hiệu quả trên trường nhị phân và giảm thiểu chi phí thường liên quan đến các trường lớn.
) 2.1 Miền hữu hạn: Toán tử hóa dựa trên towers of binary fields
Trường nhị phân tháp là chìa khóa để thực hiện tính toán có thể 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à số học 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, làm cho 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 hiệu suất. Ngoài ra, cấu trúc trường nhị phân hỗ trợ quá trình số học đơ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 đầy đủ các đặc điểm phân cấp thông qua cấu trúc tháp, làm cho trường nhị phân đặc biệt phù hợp cho 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 k bit. Điều này khác với trường số nguyên tố, nơi mà trường số nguyên tố không thể cung cấp cách biểu diễn tiêu chuẩn trong một số bit nhất định. Mặc dù trường số nguyên tố 32 bit có thể được chứa trong 32 bit, nhưng không phải mọi chuỗi 32 bit đều có thể tương ứng một cách duy nhất với một phần tử trường, trong khi trường nhị phân lại có sự thuận lợi của ánh xạ một-một này. Trong trường số 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 nhất định như Mersenne-31 hoặc Goldilocks-64. Trong trường nhị phân F2k, các phương pháp giảm thường dùng bao gồm giảm đặc biệt ( như được sử dụng trong AES ), giảm Montgomery ### như được sử dụng trong POLYVAL ( và giảm đệ quy ) như Tower (. Bài báo "Khám Phá Không Gian Thiết Kế của ECC-Hardware Triển Khai Trường Số 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 giới thiệu các chữ số mang trong các phép toán cộng và nhân, và phép toán bình phương trong trường nhị phân rất hiệu quả, vì nó tuân theo quy tắc đơn giả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 diễn giải 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ử độc đáo trong miền nhị phân 128 bit, hoặc được giải thích là 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. Sự 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 phép chuyển đổi kiểu chuỗi bit )typecast(, đâ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 đặc điểm này để cải thiện hiệu quả tính toán. Hơn nữa, 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, bình phương và phép đảo ngược trong miền tháp nhị phân n bit ) có thể phân rã thành miền con m bit (.
![Bitlayer Research：Phân tích nguyên lý của Binius STARKs và những suy nghĩ tối ưu hóa])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: Phiên bản sửa đổi HyperPlonk Product và PermutationCheck------Áp dụng cho trường 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 chính xác của đa thức và tập hợp nhiều biến. Những 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 đúng.
PermutationCheck: Xác minh kết quả đánh giá của hai đa thức nhiều 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 sự sắp xếp giữa các biến đa thức.
LookupCheck: Xác minh rằng giá trị của đa thức có trong bảng tra cứu đã cho, tức là f(Bµ) ⊆ T)Bµ(, đảm bảo rằng một số giá trị nằm trong khoảng được 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 việc đánh giá đa thức hữu tỷ trên khối siêu Boolean có bằng một giá trị được 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 một đa thức nhiều biến trên hypercube boolean có phải là zero tại bất kỳ điểm nào ∏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 giá trị 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 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ô, bằng cách đưa ra số ngẫu nhiên, xây dựng tổ hợp tuyến tính để thực hiện 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 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ó những cải tiến trong 3 lĩnh vực sau:
Tối ưu hóa ProductCheck: Trong HyperPlonk, ProductCheck yêu cầu mẫu số U không được bằng không ở mọi nơi 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 đủ tình huống chia cho không, dẫn đến không thể khẳng định vấn đề không bằng không của U trên siêu khối; Binius đã xử lý đúng vấn đề này, ngay cả trong trường hợp mẫu số bằng không, 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ó tính 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.
Do đó, Binius đã cải tiến cơ chế PIOPSumCheck hiện tại, nâng cao tính linh hoạt và hiệu quả của giao thức, đặc biệt là trong việc xử lý các xác thực đ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 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 miền nhị phân trong tương lai.
) 2.3 PIOP: lập luận dịch chuyển đa tuyến mới ------ áp dụng cho hypercube boolean
Trong giao thức Binius, đa dạng ảo