비탈릭: 비니우스, 이진 체를 위한 효율적인 증명
글: Vitalik Buterin
번역: Kate, 화성경제
이 글은 2019년대 암호학에 대해 대략적으로 익숙한 독자를 대상으로 하며, 특히 SNARK와 STARK를 다룬다. 만약 그렇지 않다면, 먼저 해당 글들을 읽어보는 것을 추천한다. Justin Drake, Jim Posen, Benjamin Diamond, Radi Cojbasic의 피드백과 의견에 특별히 감사한다.
지난 2년간 STARK는 매우 복잡한 진술에 대해 쉽게 검증 가능한 암호화 증명을 효율적으로 생성하는 데 핵심적이고 대체 불가능한 기술로 자리 잡았다(예: 이더리움 블록의 유효성을 증명). 그 핵심 이유 중 하나는 필드 크기가 작다는 점이다: 타원 곡선 기반 SNARK는 충분한 보안을 위해 256비트 정수에서 작업해야 하지만, STARK는 더 작은 필드 크기를 사용할 수 있어 효율성이 높아진다. 처음에는 Goldilocks 필드(64비트 정수), 그 후 Mersenne31과 BabyBear(모두 31비트)였다. 이러한 효율성 향상 덕분에 Goldilocks를 사용하는 Plonky2는 다양한 계산에 대한 증명 생성 속도가 이전 세대보다 수백 배 빠르다.
자연스러운 질문은 바로 여기서 시작된다: 논리적인 결론까지 나아가 0과 1 위에서 직접 연산함으로써 더 빠른 증명 시스템을 구축할 수 있을까? 이것이 바로 Binius가 시도하는 바이며, 이를 위해 3년 전의 SNARK와 STARK와는 근본적으로 다른 많은 수학적 기법을 사용한다. 이 글에서는 왜 작은 필드가 증명 생성을 더욱 효율적으로 만드는지, 왜 이진 필드(binary field)가 고유하게 강력한지를 설명하고, Binius가 이진 필드 위의 증명을 효과적으로 만드는 방법을 소개한다.
Binius. 이 글의 마지막에는 위 이미지의 각 부분을 모두 이해할 수 있게 될 것이다.
복습: 유한체(Finite Fields)
암호화 증명 시스템의 핵심 과제 중 하나는 많은 데이터를 처리하면서도 숫자를 작게 유지하는 것이다. 큰 프로그램에 대한 진술을 몇 개의 숫자만 포함하는 수학 방정식으로 압축할 수 있지만, 그 숫자들이 원래 프로그램만큼 크다면 아무런 이득도 없다.
숫자를 작게 유지하면서도 복잡한 산술을 수행하기 위해 암호학자들은 일반적으로 모듈러 연산(modular arithmetic)을 사용한다. 우리는 소수인 "모듈러스(modulus)" p를 선택한다. % 연산자는 "나머지를 취한다"는 의미이다: 15%7=1, 53%10=3 등.(답변은 항상 음이 아닌 수임에 주의하라. 예를 들어 -1%10=9)
시간 계산 맥락에서 모듈러 연산을 본 적이 있을지도 모른다(예: 9시에서 4시간 후는 몇 시인가?). 하지만 여기서는 단순히 어떤 수에 대해 덧셈과 뺄셈만 하는 것이 아니라 곱셈, 나눗셈, 거듭제곱도 할 수 있다.
다시 정의하자면:
위 규칙들은 모두 자기 일관적(self-consistent)이다. 예를 들어 p=7이라면:
5+3=1 (8%7=1이기 때문)
1-3=5 (-2%7=5이기 때문)
2*5=3
3/5=2
이 구조의 보다 일반적인 용어는 유한체(finite field)이다. 유한체란 일반적인 산술 법칙을 따르지만, 가능한 값의 수가 제한되어 있어 각 값을 고정된 크기로 표현할 수 있는 수학적 구조이다.
모듈러 연산(또는 소수체)은 유한체의 가장 일반적인 형태이지만, 또 다른 형태도 존재한다: 확장체(extension field). 아마 이미 한 번쯤 본 적 있을 것이다: 복소수. 우리는 새로운 요소를 "생각해내고", 그것에 i라는 라벨을 붙여 수학 연산을 한다: (3i+2)*(2i+4)=6i*i+12i+4i+8=16i+2. 마찬가지로 소수체를 확장할 수도 있다. 우리가 더 작은 필드를 다룰수록, 보안을 유지하기 위해 소수체의 확장은 점점 더 중요해지고, 이진 필드(Binius가 사용)는 실질적인 유용성을 가지기 위해 완전히 확장에 의존한다.
복습: 산술화(Arithmetization)
SNARK와 STARK는 컴퓨터 프로그램을 증명하는 방법을 산술화(arithmetic)를 통해 수행한다: 당신이 증명하고자 하는 프로그램에 대한 진술을, 다항식을 포함하는 수학 방정식으로 변환한다. 방정식의 유효한 해는 프로그램의 유효한 실행에 대응한다.
간단한 예를 들어보자. 내가 100번째 피보나치 수를 계산했고 그것을 증명하고 싶다고 하자. 나는 피보나치 수열을 인코딩하는 다항식 F를 만들 것이다: 따라서 F(0)=F(1)=1, F(2)=2, F(3)=3, F(4)=5 등, 총 100단계이다. 내가 증명해야 할 조건은 x={0,1…98} 범위 전체에서 F(x+2)=F(x)+F(x+1)가 성립한다는 것이다. 나는 다음의 몫(quotiont)을 제공함으로써 당신을 설득할 수 있다:
여기서 Z(x) = (x-0) * (x-1) * …(x-98)이다. 만약 F와 H가 이 등식을 만족하는 다항식을 제공할 수 있다면, F는 반드시 해당 범위에서 F(x+2)-F(x+1)-F(x)를 만족해야 한다. 또한 F(0)=F(1)=1임을 추가로 검증한다면, F(100)은 실제로 100번째 피보나치 수여야 한다.
더 복잡한 것을 증명하고 싶다면, "간단한" 관계 F(x+2) = F(x) + F(x+1)를 더 복잡한 방정식으로 교체하면 된다. 이것은 기본적으로 "F(x+1)는 상태 F(x)로 초기화된 가상 머신의 출력이며, 계산 단계를 한 번 실행한 것"이라고 말하는 것이다. 또한 100 대신 1억과 같은 더 큰 숫자를 사용하여 더 많은 단계를 수용할 수 있다.
모든 SNARK와 STARK는 다항식(때로는 벡터와 행렬) 위의 간단한 방정식을 사용하여 단일 값들 사이의 많은 관계를 표현한다는 아이디어를 기반으로 한다. 모든 알고리즘이 위 예시처럼 인접한 계산 단계 간의 동등성을 확인하는 것은 아니다: 예를 들어 PLONK도 R1CS도 아니다. 그러나 가장 효율적인 많은 검사들이 그렇게 하는데, 그 이유는 동일한 검사를 여러 번 수행하거나 동일한 소수의 검사를 반복함으로써 오버헤드를 최소화하기가 더 쉽기 때문이다.
Plonky2: 256비트 SNARK 및 STARK에서 64비트로... 이제는 STARK만
5년 전만 해도 다양한 유형의 제로지식 증명에 대한 합리적인 요약은 다음과 같았다. 두 가지 유형의 증명이 있었다: (타원 곡선 기반) SNARK와 (해시 기반) STARK. 기술적으로 보면, STARK는 SNARK의 일종이지만, 실제로는 일반적으로 "SNARK"라고 하면 타원 곡선 기반 변형을 의미하고, "STARK"라고 하면 해시 기반 구조를 의미한다. SNARK는 작아서 매우 빠르게 검증할 수 있고 체인 상에 쉽게 설치할 수 있다. STARK는 크지만 신뢰할 수 있는 설정이 필요 없으며 양자 저항성이 있다.
STARK는 데이터를 다항식으로 간주하고 그 다항식의 평가를 계산하며, 확장된 데이터의 메르클 루트를 "다항식 커밋먼트(polynomial commitment)"로 사용한다.
여기서 중요한 역사적 사실은, 타원 곡선 기반 SNARK가 먼저 널리 사용되었다는 것이다: 약 2018년까지는 FRI 덕분에 STARK가 충분히 효율적이 되었고, 그때쯤이면 Zcash가 이미 1년 이상 운영되고 있었다. 타원 곡선 기반 SNARK는 핵심적인 제한점을 가지고 있다: 타원 곡선 기반 SNARK를 사용하려면, 그 방정식 내 산술 연산을 타원 곡선 위의 점 수를 모듈러스로 해야 한다는 것이다. 이는 매우 큰 수이며, 일반적으로 2의 256승에 가깝다: 예를 들어 bn128 곡선은 21888242871839275222246405745257275088548364400416034343698204186575808495617이다. 하지만 실제 계산은 작은 숫자를 사용한다: 좋아하는 언어로 "실제" 프로그램을 생각해보면 대부분 카운터, for 루프 내 인덱스, 프로그램 내 위치, 참 또는 거짓을 나타내는 비트 하나, 그리고 거의 항상 몇 비트 길이밖에 안 되는 기타 사물들로 이루어져 있다.
당신의 "원시(raw)" 데이터가 "작은" 숫자들로 구성되어 있다고 해도, 증명 과정은 몫, 확장, 무작위 선형 조합 및 기타 데이터 변환을 계산해야 하며, 이는 동일하거나 더 많은 수의 객체를 만들어내고, 그 평균 크기는 필드의 전체 크기와 같다. 이는 핵심적인 비효율을 초래한다: n개의 작은 값에 대한 계산을 증명하기 위해, 훨씬 더 큰 n개의 값에 대한 더 많은 계산을 해야 한다. 처음에는 STARK도 SNARK처럼 256비트 필드를 사용하는 습관을 물려받아 같은 비효율을 겪었다.
일부 다항식 평가의 리드-솔로몬 확장. 원래 값은 작지만, 추가된 값들은 필드의 전체 크기(이 경우 2의 31승-1)로 확장된다.
2022년, Plonky2가 발표되었다. Plonky2의 주요 혁신은 더 작은 소수에 대해 산술 연산을 하는 것이었다: 2의 64승 – 2의 32승 + 1 = 18446744067414584321. 이제 덧셈이나 곱셈마다 CPU에서 몇 개의 명령어로 항상 완료할 수 있으며, 모든 데이터를 함께 해싱하는 속도가 이전보다 4배 빨라졌다. 하지만 문제점이 하나 있다: 이 방법은 STARK에만 적용된다. SNARK에 사용하려고 하면, 너무 작은 타원 곡선으로 인해 타원 곡선 자체가 안전하지 않게 된다.
보안을 보장하기 위해 Plonky2는 또한 확장체를 도입해야 했다. 산술 방정식을 검사하는 핵심 기술 중 하나는 "무작위 점 샘플링"이다: H(x) * Z(x)가 F(x+2)-F(x+1)-F(x)와 같은지 확인하고 싶다면, 무작위로 좌표 r을 선택하고 다항식 커밋먼트를 통해 H(r), Z(r), F(r), F(r+1), F(r+2)를 증명한 후, H(r) * Z(r)가 F(r+2)-F(r+1)-F(r)과 같은지 검증한다. 공격자가 좌표를 미리 추측할 수 있다면, 증명 시스템을 속일 수 있다—그래서 증명 시스템은 무작위여야 한다. 하지만 이는 공격자가 무작위로 추측할 수 없도록 충분히 큰 집합에서 좌표를 샘플링해야 한다는 의미이기도 하다. 모듈러스가 2의 256승에 가까우면 당연히 그렇다. 그러나 모듈러스가 2의 64승-2의 32승+1이라면 아직 그런 수준은 아니며, 2의 31승-1로 낮추면 분명히 아니다. 증명을 20억 번 위조해보다가 운 좋게 성공하는 것은 공격자의 능력 범위 내에 있다.
이것을 방지하기 위해 우리는 확장체에서 r을 샘플링한다. 예를 들어 y³=5인 y를 정의하고 1, y, y²의 조합을 사용할 수 있다. 이렇게 하면 좌표의 총 수가 약 2의 93승으로 증가한다. 증명자가 계산하는 다항식의 대부분은 이 확장체로 들어가지 않는다; 단지 2의 31승-1을 모듈러스로 한 정수를 사용하므로, 여전히 작은 필드를 사용함으로써 모든 효율성을 얻을 수 있다. 하지만 무작위 점 검사와 FRI 계산은 필요한 보안을 얻기 위해 이 더 큰 영역으로 깊이 들어간다.
작은 소수에서 이진수로
컴퓨터는 큰 숫자를 0과 1의 수열로 표현하고, 덧셈과 곱셈 등의 연산을 계산하기 위해 그 비트 위에 "회로(circuit)"를 구축함으로써 산술 연산을 수행한다. 컴퓨터는 특히 16비트, 32비트, 64비트 정수에 대해 최적화되어 있다. 예를 들어 2의 64승-2의 32승+1과 2의 31승-1은 단지 그 경계에 맞기 때문에 선택된 것이 아니라, 그 경계와 매우 잘 맞기 때문이다: 일반적인 32비트 곱셈을 수행하여 2의 64승-2의 32승+1에 대한 모듈러스 곱셈을 실행하고, 출력을 몇 군데에서 비트 시프트하고 복사하면 된다; 이 글은 일부 기술을 잘 설명하고 있다.
그러나 더 나은 방법은 직접 이진수로 계산하는 것이다. 덧셈이 "단순히" XOR이고, 1+1에서 다음 비트로의 "자리올림(carry)" 오버플로우를 걱정할 필요가 없다면 어떨까? 곱셈도 마찬가지로 더 병렬화될 수 있다면? 이러한 장점들은 참/거짓 값을 비트 하나로 표현할 수 있다는 가능성에 기반한다.
이러한 직접적인 이진 계산의 장점을 활용하는 것이 바로 Binius가 시도하는 바이다. Binius 팀은 zkSummit에서 효율성 향상을 시연했다:
비록 "크기"가 대략 같지만, 32비트 이진 필드 연산은 31비트 메르센 필드 연산보다 5배 적은 컴퓨팅 자원이 필요하다.
일원 다항식에서 초입방체(Hypercube)로
이 논리를 믿고 비트(0과 1)로 모든 것을 하고 싶다고 가정하자. 어떻게 10억 비트를 다항식으로 표현할 수 있을까?
여기서 우리는 두 가지 실제적인 문제에 직면한다:
1. 많은 값을 표현하는 다항식의 경우, 그 값들은 다항식 평가 시 접근 가능해야 한다: 위의 피보나치 예에서 F(0), F(1) ... F(100), 더 큰 계산에서는 지수가 수백만에 이를 수 있다. 우리가 사용하는 필드는 이 크기까지의 숫자를 포함해야 한다.
2. 우리가 메르클 트리에 커밋하는 모든 값(모든 STARK처럼)은 리드-솔로몬 코드로 인코딩되어야 한다: 예를 들어, 값을 n에서 8n으로 확장하여 계산 중에 값을 하나 위조함으로써 악의적인 증명자가 속이는 것을 방지하기 위한 중복성을 제공한다. 이것 역시 충분히 큰 필드가 필요하다: 백만 개의 값을 800만 개로 확장하려면, 다항식을 평가할 800만 개의 서로 다른 점이 필요하다.
Binius의 핵심 아이디어 중 하나는 이 두 가지 문제를 별도로 해결하고 동일한 데이터를 두 가지 다른 방식으로 표현함으로써 달성하는 것이다. 먼저 다항식 자체부터. 타원 곡선 기반 SNARK, 2019년대 STARK, Plonky2 등은 일반적으로 하나의 변수 위의 다항식을 다룬다: F(x). 반면 Binius는 Spartan 프로토콜에서 영감을 받아 다변량 다항식을 사용한다: F(x1,x2,… xk). 실제로 우리는 계산의 "초입방체(hypercube)" 위에 전체 계산 궤적을 표현하며, 각 xi는 0이거나 1이다. 예를 들어 피보나치 수열을 표현하고자 하며, 여전히 충분히 큰 필드로 표현한다고 하자. 그러면 앞의 16개 숫자를 다음과 같이 상상할 수 있다:
즉, F(0,0,0,0)는 1이어야 하고, F(1,0,0,0)도 1, F(0,1,0,0)는 2, ..., F(1,1,1,1)=987까지 계속된다. 이러한 계산 초입방체가 주어지면, 이러한 계산을 생성하는 다변량 선형(각 변수의 차수는 1) 다항식이 존재한다. 따라서 우리는 이 값들의 집합을 다항식의 표현으로 볼 수 있다; 계수를 계산할 필요는 없다.
이 예시는 물론 설명을 위한 것이다: 실제로 입방체에 들어가는 전체 의미는 단일 비트를 처리하게 해주는 것이다. 피보나치 수를 계산하는 "Binius 원생(native)" 방법은 높은 차원의 입방체를 사용하고, 예를 들어 각 16비트 그룹으로 하나의 숫자를 저장하는 것이다. 이것은 비트 기반에서 정수 덧셈을 구현하기 위해 다소 영리한 방법이 필요하지만, Binius에게는 그리 어렵지 않다.
이제 오류 정정 코드(코드)를 살펴보자. STARK의 작동 방식은: n개의 값을 취하고, 리드-솔로몬 코드로 더 많은 값으로 확장(일반적으로 8n, 일반적으로 2n과 32n 사이)한 후, 확장에서 무작위로 일부 메르클 브랜치를 선택하고, 그에 대해 어떤 검사를 수행한다. 초입방체는 각 차원에서 길이가 2이다. 따라서 직접 확장하는 것은 비실용적이다: 16개의 값에서 메르클 브랜치를 샘플링할 충분한 "공간"이 없다. 그렇다면 어떻게 해야 할까? 우리는 초입방체를 정사각형으로 간주하자!
간단한 Binius - 예제
이 프로토콜의 파이썬 구현은 여기를 참조하라.
편의상 필드로 정규 정수를 사용하는 예제를 살펴보자(실제 구현에서는 이진 필드 요소를 사용한다). 먼저 커밋하고자 하는 초입방체를 정사각형으로 인코딩한다:
이제 이 정사각형을 리드-솔로몬 코드로 확장한다. 즉, 각 행을 x ={0,1,2,3}에서 평가된 3차 다항식으로 간주하고, x ={4,5,6,7}에서 동일한 다항식을 평가한다:
숫자가 빠르게 팽창한다는 점에 주목하라! 그래서 실제 구현에서는 정규 정수가 아니라 항상 유한체를 사용한다: 예를 들어 모듈러스 11을 사용하면, 첫 번째 행의 확장은 단지 [3,10,0,6]이 된다.
확장을 직접 시도하고 여기의 숫자를 검증하고 싶다면, 내 간단한 리드-솔로몬 확장 코드를 사용할 수 있다.
다음으로, 이 확장을 열로 간주하고 열의 메르클 트리를 생성한다. 메르클 트리의 루트가 우리의 커밋이다.
이제 증명자가 어딘가에서 다항식의 계산 r={r0,r1,r2,r3}을 증명하고 싶다고 가정하자. Binius에는 다른 다항식 커밋 방식보다 약한 점이 하나 있다: 증명자는 메르클 루트에 커밋하기 전에 s를 알거나 추측해서는 안 된다(즉, r은 메르클 루트에 의존하는 의사 무작위 값이어야 한다). 이는 해당 방식을 "데이터베이스 조회(database lookup)"에 무용하게 만든다(예: "좋아, 너가 메르클 루트를 줬으니 이제 P(0,0,1,0)을 보여줘!"). 하지만 우리가 실제로 사용하는 제로지식 증명 프로토콜은 일반적으로 "데이터베이스 조회"를 필요로 하지 않는다; 그저 무작위 평가 지점에서 다항식을 검사하면 된다. 따라서 이 제한은 우리의 목적에 부합한다.
r={1,2,3,4}를 선택했다고 가정하자(이 시점에서 다항식의 계산 결과는 -137; 이 코드로 확인 가능). 이제 증명 과정에 들어간다. 우리는 r을 두 부분으로 나눈다: 첫 번째 {1,2}는 행 내 열의 선형 조합을 나타내고, 두 번째 {3,4}는 행의 선형 조합을 나타낸다. 우리는 "텐서 곱(tensor product)"을 계산한다, 열 부분에 대해서:
행 부분에 대해서:
이것의 의미는: 각 집합에서 하나씩 선택한 모든 가능한 곱의 목록이다. 행의 경우, 우리는 다음을 얻는다:
[(1-r2)*(1-r3), (1-r3), (1-r2)*r3, r2*r3]
r={1,2,3,4} (따라서 r2=3 및 r3=4)를 사용하면:
[(1-3)*(1-4), 3*(1-4),(1-3)*4,3*4] = [6, -9 -8 -12]
이제 기존 행의 선형 조합을 통해 새로운 "행" t를 계산한다. 즉, 다음을 취한다:
여기서 발생하는 일을 부분 평가로 볼 수 있다. 우리가 전체 텐서 곱을 전체 값의 벡터와 곱하면 P(1,2,3,4) = -137을 계산하게 된다. 여기서 우리는 평가 좌표의 절반만 사용하는 부분 텐서 곱을 곱하고, N값 그리드를 √N값의 한 행으로 단순화한다. 당신이 이 행을 다른 사람에게 제공하면, 그 사람은 나머지 절반의 평가 좌표의 텐서 곱으로 나머지 계산을 완료할 수 있다.
증명자는 검증자에게 다음의 새로운 행: t와 일부 무작위 샘플링된 열의 메르클 증명을 제공한다. 우리의 설명 예제에서는 증명자가 마지막 열만 제공하도록 하겠다; 현실에서는 충분한 보안을 위해 수십 개의 열을 제공해야 한다.
이제 리드-솔로몬 코드의 선형성을 활용한다. 우리가 사용하는 핵심 속성은: 리드-솔로몬 확장의 선형 조합을 취하면 선형 조합의 리드-솔로몬 확장과 동일한 결과를 얻는다는 것이다. 이러한 "순서 독립성(order independence)"은 두 연산이 모두 선형일 때 일반적으로 발생한다.
검증자가 바로 그 일을 한다. 그들은 t를 계산하고, 증명자가 이전에 계산한 것과 동일한 열의 선형 조합을 계산한다(하지만 증명자가 제공한 열만 계산하고), 두 과정이 동일한 답을 주는지 검증한다.
이 예에서는, t를 확장하고 동일한 선형 조합([6,-9,-8,12])을 계산하면, 두 가지 모두 동일한 답: -10746을 준다. 이는 메르클 루트가 "선의" 방식으로 구축되었음을(또는 적어도 "충분히 가깝게") 증명하며, t와 일치함을 의미한다: 대부분의 열이 서로 호환됨을 의미한다.
하지만 검증자는 또 다른 것을 검사해야 한다: 다항식 {r0…r3}의 평가를 검사해야 한다. 지금까지 검증자의 모든 단계는 실제로 증명자가 주장하는 값에 의존하지 않았다. 우리는 다음과 같이 검사한다. 우리가 계산 지점으로 표시한 "열 부분"의 텐서 곱을 취한다:
우리 예에서 r={1,2,3,4}이므로 열을 선택하는 절반은 {1,2})이고, 이는 다음과 같다:
이제 이 선형 조합 t를 취한다:
이것은 다항식을 직접 평가한 결과와 같다.
위 내용은 "간단한" Binius 프로토콜에 대한 완전한 설명에 매우 가깝다. 이는 이미 몇 가지 흥미로운 장점을 가지고 있다: 예를 들어 데이터가 행과 열로 분할되므로 필드 크기를 절반으로 줄이기만 하면 된다. 하지만 이는 이진수로 계산하는 모든 장점을 실현하지는 못한다. 이를 위해서는 완전한 Binius 프로토콜이 필요하다. 그러나 먼저 이진 필드에 대해 더 깊이 살펴보자.
이진 필드(Binary Fields)
가능한 가장 작은 필드는 모듈러스 2의 산술이며, 매우 작아서 덧셈과 곱셈 표를 작성할 수 있다:
확장함으로써 더 큰 이진 필드를 얻을 수 있다: F2(모듈러스 2 정수)에서 시작하여 x²=x+1인 x를 정의하면, 다음의 덧셈과 곱셈 표를 얻는다:
사실 우리는 이 구조를 반복함으로써 이진 필드를 임의로 큰 크기까지 확장할 수 있다. 실수 위의 복소수와는 달리, 실수에서는 새 요소 I를 추가할 수 있지만 더 이상 추가할 수 없다(사원수는 존재하지만 수학적으로 이상하다, 예: ab≠ba), 유한체에서는 새로운 확장을 무한히 추가할 수 있다. 구체적으로 요소를 다음과 같이 정의한다:
등등... 이것은 일반적으로 타워 구조(tower structure)라고 불리는데, 각 연속적인 확장을 탑에 새 층을 추가하는 것으로 볼 수 있기 때문이다. 이는 임의 크기의 이진 필드를 구성하는 유일한 방법은 아니지만, Binius가 활용하는 독특한 장점을 가지고 있다.
우리는 이 숫자들을 비트의 목록으로 표현할 수 있다. 예를 들어, 1100101010001111. 첫 번째 비트는 1의 배수를, 두 번째 비트는 x0의 배수를, 이후 비트는 다음 x1 숫자의 배수를 나타낸다: x1, x1*x0, x2, x2*x0, 등등. 이 인코딩은 다음과 같이 분해할 수 있기 때문에 좋다:
이것은 비교적 드문 표기법이지만, 나는 이진 필드 요소를 오른쪽에 더 높은 비트가 있는 비트 표현으로 정수로 표현하는 것을 좋아한다. 즉, 1=1, x0=01=2, 1+x0=11=3, 1+x0+x2=11001000=19 등. 이 표현에서, 그것은 61779이다.
이진 필드에서의 덧셈은 단순한 XOR이다(덧셈과 마찬가지로 뺄셈도 그렇다); 즉, 모든 x에 대해 x+x=0임에 주의하라. 두 요소 x*y를 곱하는 데는 매우 간단한 재귀 알고리즘이 있다: 각 숫자를 두 조각으로 나눈다:
그리고 곱셈을 분할한다:
마지막 부분만이 약간 까다로운데, 간소화 규칙을 적용해야 하기 때문이다. Karatsuba 알고리즘과 빠른 푸리에 변환과 유사한 더 효율적인 곱셈 방법이 있지만, 흥미 있는 독자가 스스로 알아내는 연습으로 남겨두겠다.
이진 필드에서의 나눗셈은 곱셈과 역수 계산을 결합하여 수행한다. "간단하지만 느린" 역수 계산 방법은 일반화된 페르마 소정리를 응용하는 것이다. 더 복잡하지만 더 효율적인 역수 계산 알고리즘도 있으며, 여기서 찾을 수 있다. 여기의 코드를 사용하여 이진 필드의 덧셈, 곱셈, 나눗셈을 실험할 수 있다.
왼쪽: 4비트 이진 필드 요소(즉, 1, x0, x1, x0x1로만 구성)의 덧셈 표. 오른쪽: 4비트 이진 필드 요소의 곱셈 표.
이러한 유형의 이진 필드의 아름다움은 "정규" 정수와 모듈러 연산의 최고의 점들을 결합한다는 데 있다. 정규 정수처럼, 이진 필드 요소는 무한하다: 마음대로 확장할 수 있다. 하지만 모듈러 연산처럼, 특정 크기 제한 내에서 값을 연산하면 모든 결과도 동일한 범위 내에 유지된다. 예를 들어 42의 연속된 거듭제곱을 취하면 다음과 같다:
255단계 후에 42의 255승=1로 돌아오며, 정규 정수와 모듈러 연산처럼 일반적인 수학 법칙을 따른다: a*b=b*a, a*(b+c)=a*b+a*c, 심지어는 약간 이상한 새로운 법칙들도 있다.
마지막으로, 이진 필드는 비트를 편리하게 처리할 수 있다: 2의 k승에 맞는 숫자로 수학 연산을 하면, 모든 출력도 2의 k승 비트에 맞게 된다. 이것은 어색함을 피하게 해준다. 이더리움의 EIP-4844에서, blob의 각 "블록"은 모듈러스 52435875175126190479447740508185965837690552500527637822603658699938581184513의 숫자여야 하므로, 이진 데이터를 인코딩하려면 공간을 일부 버려야 하고, 각 요소가 2의 248승보다 작은 값을 저장하고 있음을 보장하기 위해 애플리케이션 계층에서 추가 검사를 해야 한다. 또한 이진 필드 연산은 CPU뿐만 아니라 이론적으로 최적의 FPGA 및 ASIC 설계에서도 컴퓨터에서 매우 빠르게 수행된다.
이 모든 것은 우리가 위에서 설명한 리드-솔로몬 인코딩을 할 수 있음을 의미하며, 우리의 예에서 본 것처럼 정수 "폭발(explosion)"을 완전히 피할 수 있으며, 컴퓨터가 잘하는 계산 방식으로 매우 "자연스럽게" 수행할 수 있다. 이진 필드의 "분할(splitting)" 속성—우리가 1100101010001111=11001010+10001111*x3로 어떻게 분할했는지, 그리고 필요에 따라 분할할 수 있는 능력—은 큰 유연성을 실현하는 데 매우 중요하다.
완전한 Binius
이제 "완전한 Binius"로 넘어갈 수 있다. 이는 "간단한 Binius"를 (i) 이진 필드에서 작동하도록 조정하고, (ii) 단일 비트를 커밋할 수 있도록 한다. 이 프로토콜은 비트 매트릭스를 보는 다양한 방식 사이를 오가기 때문에 이해하기 어렵다; 물론 나는 이를 이해하는 데 더 오랜 시간이 걸렸으며, 이는 내가 일반적으로 암호화 프로토콜을 이해하는 데 걸리는 시간보다 더 길다. 하지만 일단 이진 필드를 이해하면, 좋은 소식은 Binius가 의존하는 "더 어려운 수학"이 없다는 것이다. 타원 곡선 페어링처럼 점점 더 깊은 대수기하학의 토끼굴을 파야 하는 것이 아니라, 여기서는 이진 필드만 있으면 된다.
다시 전체 다이어그램을 살펴보자:
지금까지 대부분의 구성 요소에 익숙해졌을 것이다. 초입방체를 격자로 "압축(flattening)"하는 아이디어, 평가 지점의 텐서 곱으로 행 조합과 열 조합을 계산하는 아이디어, "리드-솔로몬 확장 후 행 조합 계산"과 "행 조합 계산 후 리드-솔로몬 확장" 사이의 등가성을 검사하는 아이디어는 모두 간단한 Binius에서 구현된다.
"완전한 Binius"에는 무엇이 새로 추가되는가? 기본적으로 세 가지가 있다:
• 초입방체와 정사각형의 개별 값은 비트(0 또는 1)여야 한다.
• 확장 과정은 비트를 열로 그룹화하고 일시적으로 더 큰 필드 요소로 간주함으로써 비트를 더 많은 비트로 확장한다.
• 행 조합 단계 후에, 확장을 다시 비트로 변환하는 "비트로 분해(decomposition into bits)" 단계가 있다.
이 두 가지 경우를 차례로 살펴보겠다. 먼저 새로운 연기(prolongation) 절차부터. 리드-솔로몬 코드는 기본적인 제한이 있는데, n을 k*n으로 확장하려면 k*n개의 서로 다른 값을 가진 필드에서 작업해야 하며, 이는 좌표로 사용할 수 있어야 한다. F2(다시 말해 비트)를 사용하면 이를 할 수 없다. 따라서 우리가 하는 일은 인접한 F2 요소를 "묶어(pack)" 더 큰 값을 형성하는 것이다. 여기 예시에서는 두 비트를 한 번에 {0,1,2,3} 요소로 묶는다. 확장이 단지 네 개의 계산 지점을 가지므로, 우리에게는 충분하다. "실제" 증명에서는 아마 16비트씩 묶을 것이다. 그런 다음 이 묶인 값에 대해 리드-솔로몬 코드를 수행하고 다시 비트로 풀어낸다.
이제 행 조합이다. "무작위 지점에서 평가" 검사를 암호학적으로 안전하게 만들기 위해, 우리는 초입방체 자체보다 훨씬 더 큰 공간에서 그 지점을 샘플링해야 한다. 따라서 초입방체 내의 지점은 비트이지만, 초입방체 외부의 계산 값은 훨씬 더 커질 것이다. 위의 예에서 "행 조합"은 결국 [11,4,6,1]이 된다.
여기서 문제가 발생한다: 우리는 비트를 더 큰 값으로 조합하고, 그 위에서 리드-솔로몬 확장을 수행하는 방법을 알고 있지만, 더 큰 값의 조합에 대해서는 어떻게 같은 일을 할 수 있을까?
Binius의 요령은 비트 단위로 처리하는 것이다: 우리는 각 값의 개별 비트를 살펴본다(예: 우리가 "11"이라고 표시한 것은 [1,1,0,1]). 그런 다음 행 단위로 확장을 수행한다. 즉, 각 요소의 1행에 대해 확장 과정을 수행한 후, x0행, "x1"행, x0x1행 등등 순서로 진행한다(음, 우리의 완구 예제에서는 여기서 멈추지만, 실제 구현에서는 128행(마지막은 x6*…*x0)까지 갈 것이다).
요약하자면:
• 우리는 초입방체의 비트를 격자로 변환한다.
• 그런 다음 각 행의 인접한 비트 그룹을 더 큰 필드 요소로 간주하고, 리드-솔로몬 확장을 위해 산술 연산을 수행한다.
• 그런 다음 각 열 비트의 행 조합을 취하고, 출력으로 각 행의 비트 열을 얻는다(4x4보다 큰 정사각형의 경우 훨씬 작아짐).
• 그런 다음 출력을 행렬로 보고, 그 비트를 다시 행으로 간주한다.
왜 이렇게 할까? "일반적인" 수학에서는 숫자를 비트로 자르고, 선형 연산을 임의의 순서로 수행하여 동일한 결과를 얻는 능력이 (보통) 사라진다. 예를 들어 345에서 시작하여 8을 곱한 후 3을 곱하면 8280이 되고, 연산 순서를 바꿔도 8280이 된다. 하지만 두 단계 사이에 "비트로 분할" 작업을 삽입하면 무너진다: 8배를 하고 3배를 하면 다음과 같다:
하지만 3배를 하고 8배를 하면 다음과 같다:
하지만 타워 구조로 구성된 이진 체에서는 이 방법이 실제로 작동한다. 그 이유는 분리 가능성(separability)에 있다: 큰 값에 작은 값을 곱하면, 각 세그먼트에서 일어나는 일은 각 세그먼트에 머무른다. 만약 1100101010001111에 11을 곱하면, 이것은 먼저 1100101010001111을 다음과 같이 분해하는 것과 같다:
TechFlow 공식 커뮤니티에 오신 것을 환영합니다 Telegram 구독 그룹:https://t.me/TechFlowDaily 트위터 공식 계정:https://x.com/TechFlowPost 트위터 영어 계정:https://x.com/BlockFlow_News
@VitalikButerin
