계산 복잡성을 줄이는 것은 항상 블록체인 기술의 주요 목표 중 하나였습니다. 이를 달성하기 위한 효과적인 방법 중 하나는 계산 필드의 비트 폭을 줄이는 것입니다. 예를 들어, 타원 곡선을 기반으로 하는 SNARK는 256 이상의 비트 폭을 가진 필드에서 산술 연산을 수행하는 반면, STARK는 64비트 골디락스 필드에서 31비트 메르센31 및 베이비베어 필드로 발전했습니다. 모듈러 연산 중 소수의 효율성을 넘어, 비트 폭이 상당히 감소하여 Plonky2는 이전 버전인 Plonky보다 수백 배 더 빨라졌습니다. 이 궤적을 따라가다 보면 필드 폭을 1, 특히 ${\mathbb{F}}_{2}$로 설정할 수 있을까요? Ulvetanna(IRREDUCIBLE) 팀은 이 질문을 Succinct Arguments over Towers of Binary Fields라는 제목의 연구 논문에서 다루었습니다.  그리고 그들의 프로젝트인 Binius: 하드웨어 최적화 SNARK를 통해 Rust로 구현했습니다.  .   [1]     [2] [3]  Binius는 출시 이후 ZK(Zero-Knowledge) 커뮤니티에서 상당한 주목을 받았습니다. LambdaClass 팀은 여러 가지 기술 분석[4][5][6]을 제공했으며 Vitalik Buterin은 더 접근하기 쉬운 설명을 제공했습니다.  . 이 글에서는 Binius의 기초를 살펴보겠습니다. 특히, 기술적 관점과 구현적 관점에서 Binary Fields의 Towers에 초점을 맞춥니다.   [7]   이진 필드  Binius의 구현은 Binary Fields에 기반합니다. Binius에서 Binary Fields는 필드 확장 타워를 사용하여 구성됩니다.  가장 간단한 이진체는   로, 여기에는 두 개의 원소   만 포함되고, 모듈로 2로 수행되는 연산이 있습니다.덧셈은 비트 단위 XOR에 해당하고 곱셈은 비트 단위 AND에 해당합니다.기약 다항식   선택하면, 원소가 최대 1차 다항식의 나머지인 필드   형성할 수 있습니다.여기서 원소는 최대 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}$  필드를 확장하는 한 가지 방법은 기약 다항식을 사용하여 나머지를 취하는 것인 반면, Binius는 더 효율적인 접근 방식을 사용합니다. 타워 확장을 위한 기초로 다중선형 라그랑주 다항식을 사용합니다. 이 방법은 각 확장 필드가 이전 확장 필드 내에 중첩되는 재귀적 필드 확장을 허용합니다.  타워 확장의 구체적인 구현은 다음과 같습니다. 먼저,   ; 그런 다음,   ; 다음으로,  ${{\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)}$.  필드 확장의 구성 과정으로부터 확장이 다음 관계를 만족한다는 것이 분명합니다.   .   의 경우, 필드 확장은 다음과 같이 링의 직접 형식으로도 표현될 수 있습니다.  ${{\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)}$.   이 구현을 기반으로 다음과 같이 다양한 확장을 얻을 수 있습니다.   ${{\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}$  확장된 필드에 포함된 원소에서     에서 유도된 경우 두 부분의 합으로 분해될 수 있음이 분명합니다.   . 예를 들어,    ${{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}}$ .  반복적으로 분해하면 마침내 다음과 같이 표현할 수 있습니다.  $$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}}$$  또한,   의 경우   이므로 이진 확장체에서 덧셈과 곱셈을 효율적으로 구현할 수 있습니다. $k > 0$ $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$   이진 필드 구현  Irreducible은 Binius의 오픈 소스 Rust 구현을 제공합니다[3]. 소스 코드에는 Tower of Binary Fields[8,9,10]에 대한 완전한 구현 및 작업이 포함되어 있습니다.   [8]에서 그림 1에 표시된 것처럼 구현에는 이진 필드에 대한 연산의 완전한 정의와 이진 필드 타워의 구성이 포함됩니다. 최대 128비트 이진 필드를 지원하는 이진 필드 타워는 다음과 같이 정의됩니다.   또한 [8]은 Tower of Binary Fields 및 관련 작업에 대한 테스트 및 검증 코드를 제공합니다.   참고문헌  [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: Binius - 1부(lambdaclass.com)  [5] 이진 필드에 대한 SNARK: Binius - 2부(lambdaclass.com)  [6] Binius가 ZK 산업을 발전시키는 데 어떻게 도움을 주고 있는가 (lambdaclass.com)  [7]   https://vitalik.eth.limo/general/2024/04/29/binius.html  [8] binius/crates/field/src/binary_field.rs at main · IrreducibleOSS/binius · GitHub  [9] binius/crates/field/src/binary_field_arithmetic.rs at main · IrreducibleOSS/binius · GitHub  [10] binius/crates/field/src/extension.rs at 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

이 오디오는 이야기의 원래 언어로 제작되었습니다!

너무 오래; 읽다

Binius가 이진 필드 타워로 계산 복잡성을 줄이는 방법

Binius가 이진 필드 타워로 계산 복잡성을 줄이는 방법

About Author

코멘트

태그 걸기

이 기사는 다음에서 발표되었습니다.

Related Stories

바다 항해: 데이터 레이크를 사용하여 프로덕션 등급 RAG 애플리케이션 개발

성공적인 클라우드 마이그레이션을 위한 전체 가이드: 전략 및 모범 사례

이 18가지 개발자 도구로 생산성을 높이세요 🚀🔥

볼츠만 뇌 이론에 대한 간략한 소개

바다 항해: 데이터 레이크를 사용하여 프로덕션 등급 RAG 애플리케이션 개발

성공적인 클라우드 마이그레이션을 위한 전체 가이드: 전략 및 모범 사례

이 18가지 개발자 도구로 생산성을 높이세요 🚀🔥

볼츠만 뇌 이론에 대한 간략한 소개

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps