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  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  .   [1]     [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  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.   [7]   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à   , chỉ chứa hai phần tử   , 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   , chúng ta có thể tạo thành trường   , trong đó các phần tử là phần dư của các đa thức có bậc không quá 1,   ). ${{\mathbb{F}}{2}}$ ${0,1}$ $m(x) = x^{2} + x + 1$ over ${{\mathbb{F}}{2}}$ ${{\mathbb{F}}_{{2^{2}}}}$ $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,   ; Sau đó,   ; Tiếp theo,  ${{\tau }{0}} = {{\mathbb{F}}{2}}$ ${{\tau }{1}} = \frac{{{\mathbb{F}}{2}}[{{x}{0}}]}{(x{0}^{2} + {{x}_{0}} + 1)}$ ${{\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:   . Với   , 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 }{0}} \subset {{\tau }{1}} \subset {{\tau }{2}} \subset \cdots \subset {{\tau }{m}}$ $k \ge 0$ ${{\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ắt nguồn từ   , nó có thể được phân tích thành tổng của hai phần:   . Ví dụ,    ${{b}{0}}{{b}{1}}{{b}{2}}\ldots {{b}{{{2}^{k}}-1}}$ ${{\tau }{k}}$ ${{b}{lo}} + {{x}{k-1}}{{b}{hi}}$ (where ${{b}{lo}}, {{b}{hi}} \in {{\tau }{k-1}}$) $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   , vì   , 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. $k > 0$ $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$   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:   Ngoài ra, [8] cung cấp mã kiểm tra và xác minh cho Tháp trường nhị phân và các hoạt động liên quan.   Tài liệu tham khảo  [1]   https://eprint.iacr.org/2023/1784  [2]   https://www.irreducible.com/posts/binius-hardware-optimized-snark  [3]   https://gitlab.com/IrreducibleOSS/binius  [4] SNARK trên các trường nhị phân: Binius - Phần 1 (lambdaclass.com)  [5] SNARK trên các trường nhị phân: Binius - Phần 2 (lambdaclass.com)  [6] Binius đang giúp thúc đẩy ngành công nghiệp ZK phát triển như thế nào (lambdaclass.com)  [7]   https://vitalik.eth.limo/general/2024/04/29/binius.html  [8] binius/crates/field/src/binary_field.rs tại main · IrreducibleOSS/binius · GitHub  [9] binius/crates/field/src/binary_field_arithmetic.rs tại main · IrreducibleOSS/binius · GitHub  [10] binius/crates/field/src/extension.rs tại main · IrreducibleOSS/binius · GitHub

This story will praise and/or roast a product, company, service, game, or anything else people like to review on the Internet.

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Architecture

2022 - HackerNoon Contributor of the Year - Blockchain

2022 - HackerNoon Contributor of the Year - Optimization

2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Nghe bài viết này bằng Tiếng Anh, đọc bởi robot thông minh của HackerNoon

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

Download free Tech Leaders Productivity Report!

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

About Author

BÌNH LUẬN

chuyên mục

BÀI VIẾT NÀY CŨNG CÓ MẶT TẠI

Related Stories

309 Stories To Learn About Smart Contracts

179 Stories To Learn About Reading

184 Stories To Learn About Psychology

128 Stories To Learn About Charles Dickens

309 Stories To Learn About Smart Contracts

179 Stories To Learn About Reading

184 Stories To Learn About Psychology

128 Stories To Learn About Charles Dickens

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps