3,538 판독값

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

~에 의해 Sin7Y3m2024/09/13

너무 오래; 읽다

Ulvetanna(IRREDUCIBLE) 팀은 이 질문을 Succinct Arguments over Towers of Binary Fields라는 제목의 연구 논문에서 다루었습니다. 그들은 Binius: a Hardware-Optimized SNARK라는 프로젝트로 Rust에서 이를 구현했습니다. Binius에서 Binary Fields는 필드 확장 타워를 사용하여 구성됩니다.

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

계산 복잡성을 줄이는 것은 항상 블록체인 기술의 주요 목표 중 하나였습니다. 이를 달성하기 위한 효과적인 방법 중 하나는 계산 필드의 비트 폭을 줄이는 것입니다. 예를 들어, 타원 곡선을 기반으로 하는 SNARK는 256 이상의 비트 폭을 가진 필드에서 산술 연산을 수행하는 반면, STARK는 64비트 골디락스 필드에서 31비트 메르센31 및 베이비베어 필드로 발전했습니다. 모듈러 연산 중 소수의 효율성을 넘어, 비트 폭이 상당히 감소하여 Plonky2는 이전 버전인 Plonky보다 수백 배 더 빨라졌습니다. 이 궤적을 따라가다 보면 필드 폭을 1, 특히 ${\mathbb{F}}_{2}$로 설정할 수 있을까요? Ulvetanna(IRREDUCIBLE) 팀은 이 질문을 Succinct Arguments over Towers of Binary Fields라는 제목의 연구 논문에서 다루었습니다. [1] 그리고 그들의 프로젝트인 Binius: 하드웨어 최적화 SNARK를 통해 Rust로 구현했습니다. [2] [3] .

Binius는 출시 이후 ZK(Zero-Knowledge) 커뮤니티에서 상당한 주목을 받았습니다. LambdaClass 팀은 여러 가지 기술 분석[4][5][6]을 제공했으며 Vitalik Buterin은 더 접근하기 쉬운 설명을 제공했습니다. [7] . 이 글에서는 Binius의 기초를 살펴보겠습니다. 특히, 기술적 관점과 구현적 관점에서 Binary Fields의 Towers에 초점을 맞춥니다.

이진 필드

Binius의 구현은 Binary Fields에 기반합니다. Binius에서 Binary Fields는 필드 확장 타워를 사용하여 구성됩니다.

가장 간단한 이진체는 ${{\mathbb{F}}{2}}$ 로, 여기에는 두 개의 원소 ${0,1}$ 만 포함되고, 모듈로 2로 수행되는 연산이 있습니다.덧셈은 비트 단위 XOR에 해당하고 곱셈은 비트 단위 AND에 해당합니다.기약 다항식 $m(x) = x^{2} + x + 1$ over ${{\mathbb{F}}{2}}$ 선택하면, 원소가 최대 1차 다항식의 나머지인 필드 ${{\mathbb{F}}_{{2^{2}}}}$ 형성할 수 있습니다.여기서 원소는 최대 1차 다항식의 나머지입니다. $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$ 이므로 이진 확장체에서 덧셈과 곱셈을 효율적으로 구현할 수 있습니다.