3,593 lượt đọc

Binius Giảm Độ Phức Tạp Tính Toán Như Thế Nào Với Các Tháp Trường Nhị Phân

từ tác giả Sin7Y3m2024/09/13

dài quá đọc không nổi

Nhóm Ulvetanna (IRREDUCIBLE) đã giải quyết câu hỏi này trong bài nghiên cứu có tiêu đề Succinct Arguments over Towers of Binary Fields. Họ đã triển khai nó trong Rust với dự án Binius: một SNARK được tối ưu hóa phần cứng. Trong Binius, Binary Fields được xây dựng bằng cách sử dụng các tháp mở rộng trường.

featured image - Binius Giảm Độ Phức Tạp Tính Toán Như Thế Nào Với Các Tháp Trường Nhị Phân

Giảm độ phức tạp tính toán luôn là một trong những mục tiêu chính của công nghệ blockchain. Một cách tiếp cận hiệu quả để đạt được điều này là giảm độ rộng bit của trường tính toán. Ví dụ, SNARK dựa trên đường cong elliptic thực hiện các phép toán số học trong các trường có độ rộng bit là 256 hoặc cao hơn, trong khi STARK đã phát triển từ việc sử dụng trường Goldilocks 64 bit thành các trường Mersenne31 và BabyBear 31 bit. Ngoài hiệu quả của các số nguyên tố trong các phép toán mô-đun, việc giảm đáng kể độ rộng bit đã khiến Plonky2 nhanh hơn hàng trăm lần so với người tiền nhiệm của nó, Plonky. Theo quỹ đạo này, người ta có thể tự hỏi: liệu có thể đặt độ rộng trường thành 1, cụ thể là ${\mathbb{F}}_{2}$ không? Nhóm Ulvetanna (IRREDUCIBLE) đã giải quyết câu hỏi này trong bài báo nghiên cứu có tiêu đề Succinct Arguments over Towers of Binary Fields [1] và triển khai nó trong Rust với dự án của họ, Binius: SNARK được tối ưu hóa phần cứng [2] [3] .

Kể từ khi phát hành, Binius đã thu hút được sự chú ý đáng kể trong cộng đồng ZK (Zero-Knowledge). Nhóm LambdaClass đã cung cấp một số phân tích kỹ thuật [4][5][6] và Vitalik Buterin đã đưa ra lời giải thích dễ hiểu hơn [7] Trong bài viết này, chúng ta sẽ khám phá nền tảng của Binius, tập trung vào Towers of Binary Fields, theo cả góc độ kỹ thuật và triển khai.

Trường nhị phân

Việc triển khai Binius dựa trên Binary Fields. Trong Binius, Binary Fields được xây dựng bằng cách sử dụng các tháp mở rộng trường.

Trường nhị phân đơn giản nhất là ${{\mathbb{F}}{2}}$ , chỉ chứa hai phần tử ${0,1}$ , với các phép toán được thực hiện theo modulo 2: phép cộng tương ứng với XOR bitwise, và phép nhân tương ứng với AND bitwise. Bằng cách chọn một đa thức bất khả quy $m(x) = x^{2} + x + 1$ over ${{\mathbb{F}}{2}}$ , chúng ta có thể tạo thành trường ${{\mathbb{F}}_{{2^{2}}}}$ , trong đó các phần tử là phần dư của các đa thức có bậc không quá 1, $r(x) = ax + b$ (with $a, b \in {0, 1}$ ).

Trong khi một phương pháp để mở rộng trường liên quan đến việc lấy phần dư bằng cách sử dụng đa thức bất khả quy, Binius sử dụng một phương pháp hiệu quả hơn: sử dụng đa thức Lagrange đa tuyến tính làm cơ sở cho phần mở rộng tháp. Phương pháp này cho phép mở rộng trường đệ quy, trong đó mỗi trường mở rộng được lồng vào trường trước đó.

Triển khai cụ thể của phần mở rộng tháp như sau: Đầu tiên, ${{\tau }{0}} = {{\mathbb{F}}{2}}$ ; Sau đó, ${{\tau }{1}} = \frac{{{\mathbb{F}}{2}}[{{x}{0}}]}{(x{0}^{2} + {{x}_{0}} + 1)}$ ; Tiếp theo, ${{\tau }{k}} = \frac{{{\mathbb{F}}{2}}[{{x}{k-1}}]}{(x{k-1}^{2} + {{x}{k-1}}{{x}{k-2}} + 1)}$.

Từ quá trình xây dựng các phần mở rộng trường, rõ ràng là các phần mở rộng thỏa mãn mối quan hệ sau: ${{\tau }{0}} \subset {{\tau }{1}} \subset {{\tau }{2}} \subset \cdots \subset {{\tau }{m}}$ . Với $k \ge 0$ , phần mở rộng trường cũng có thể được biểu thị ở dạng trực tiếp của một vành như sau: ${{\tau }{k}}={{{\mathbb{F}}{2}}[{{x}{0,}}\ldots ,{{x}{k-1}}]}/{\left( x_{0}^{2}+{{x}{0}}+1,\ldots ,x{k-1}^{2}+{{x}{k-2}}{{x}{k-1}}+1 \right)}$.

Dựa trên cách triển khai này, có thể thu được các phần mở rộng khác nhau như sau:

${{\tau }_{0}}=\left{ 0,1 \right}$
${{\tau }{1}}=\left{ 0+0{{x}{0}},1+0{{x}{0}},0+1{{x}{0}},1+1{{x}{0}} \right}$, or ${{\tau }{1}}=\left{ {{\tau }{0}},0+1{{x}{0}},1+1{{x}_{0}} \right}$
$${{\tau }{2}}=\left{ \begin{align} & 0+0{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}},1+0{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}},0+1{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}}, \ & 1+1{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}},\ldots ,1+1{{x}{0}}+1{{x}{1}}+1{{x}{0}}x \ \end{align} \right}$$, Or ${{\tau }{2}}=\left{ {{\tau }{1}},0+0{{x}{0}}+1{{x}{1}}+0{{x}{0}}{{x}{1}},\ldots ,1+1{{x}{0}}+1{{x}{1}}+1{{x}{0}}{{x}{1}} \right}$

Từ các phần tử có trong trường mở rộng Rõ ràng là đối với một phần tử ${{b}{0}}{{b}{1}}{{b}{2}}\ldots {{b}{{{2}^{k}}-1}}$ bắt nguồn từ ${{\tau }{k}}$ , nó có thể được phân tích thành tổng của hai phần: ${{b}{lo}} + {{x}{k-1}}{{b}{hi}}$ (where ${{b}{lo}}, {{b}{hi}} \in {{\tau }{k-1}}$) . Ví dụ, $1100101010001111 = 11001010 + 1000111 \times {{x}{3}}$, where $11001010, 10001111 \in {{\tau }{2}}$ .

Bằng cách phân tích lặp đi lặp lại, cuối cùng chúng ta có thể biểu thị: $$1100101010001111=1+{{x}{0}}+{{x}{2}}+{{x}{2}}{{x}{1}}+{{x}{3}}+{{x}{2}}{{x}{3}}+{{x}{0}}{{x}{2}}{{x}{3}}+{{x}{1}}{{x}{2}}{{x}{3}}+{{x}{0}}{{x}{1}}{{x}{2}}{{x}{3}}$$

Ngoài ra, với $k > 0$ , vì $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$ , phép cộng và phép nhân có thể được thực hiện hiệu quả trong trường nhị phân mở rộng.

Triển khai các trường nhị phân

Irreducible cung cấp triển khai Rust nguồn mở của Binius [3]. Mã nguồn bao gồm các triển khai và hoạt động hoàn chỉnh cho Tower of Binary Fields [8,9,10].

Trong [8], như được thể hiện trong Hình 1, việc triển khai bao gồm định nghĩa đầy đủ về các phép toán cho trường nhị phân và việc xây dựng Tháp trường nhị phân. Tháp trường nhị phân, hỗ trợ trường nhị phân lên đến 128 bit, được định nghĩa như sau: