이더리움 창립자 비탈릭 부테린, 비니우스를 파헤치다

Kate 작성, Mars Finance

지난 2년 동안 STARK는 매우 복잡한 문장의 쉽게 검증 가능한 암호화 증명을 효율적으로 수행할 수 있는 중요하고 대체 불가능한 기술로 부상했습니다. 이더넷 블록이 유효하다는 것을 증명).

그 주요 이유 중 하나는 필드 크기입니다. 타원 곡선 기반 SNARK는 충분한 보안을 위해 256비트 정수로 작업해야 하는 반면, STARK는 훨씬 더 작은 필드 크기로 작업할 수 있어 훨씬 효율적이라는 점입니다. 골드디락스 필드(64비트 정수), 그 다음에는 메르센31과 베이비베어(둘 다 31비트)를 사용합니다. 이러한 효율성 향상으로 인해 Goldilocks를 사용하는 Plonky2는 광범위한 계산을 증명하는 데 있어 이전 버전보다 수백 배 더 빠릅니다.

자연스러운 질문은 이러한 추세를 논리적 결론으로 가져가 0과 1을 직접 연산하여 더 빠르게 실행되는 증명 시스템을 구축할 수 있는가 하는 것입니다. 이것이 바로 비니우스가 시도한 일이며, 3년 전의 SNARK 및 STARK와는 근본적으로 다른 여러 수학적 트릭을 사용했습니다. 이 글에서는 작은 필드가 증명 생성을 더 효율적으로 만드는 이유, 이진 필드가 독특하게 강력한 이유, 그리고 이진 필드에서 증명을 효율적으로 만들기 위해 Binius가 사용하는 트릭에 대해 설명합니다.

△ Binius. 이 게시물의 마지막에. 이 다이어그램의 모든 부분을 이해할 수 있어야 합니다.

검토: 유한 필드

암호 증명 시스템의 핵심 작업 중 하나는 대량의 데이터를 조작하면서 숫자를 작게 유지하는 것입니다. 작게. 큰 프로그램에 대한 진술을 몇 개의 숫자가 포함된 수학 방정식으로 압축할 수 있지만 그 숫자가 원래 프로그램만큼 크다면 아무 것도 얻을 수 없습니다.

숫자를 작게 유지하면서 복잡한 연산을 수행하기 위해 암호학자들은 종종 모듈식 연산을 사용합니다. 소수 "모듈로" p를 선택하고, % 연산자는 15%7=1, 53%10=3 등과 같이 "나머지를 취한다"는 의미입니다. (답은 항상 음수가 아니므로 예를 들어 -1%10=9)

시간을 더하고 뺄 때 모듈로 연산을 본 적이 있을 것입니다(예: 9시에서 4시간이 지난 지금 몇 시입니까?). 하지만 여기에서는 모듈로 숫자를 더하고 빼는 것뿐만 아니라 곱하기, 나누기, 지수를 취할 수도 있습니다.

다시 정의합니다:

위의 모든 규칙은 자체적으로 일관성이 있습니다. 예를 들어, p=7이면:

5+3=1(8%7=1이므로)

1-3=5(-2%7=5이므로)

2*5=3

3/5=2

이 구조에 대한 보다 일반적인 용어는 유한 필드입니다. 유한 필드는 일반적인 산술 법칙을 따르지만 가능한 값의 수가 한정되어 있어 각 값을 고정된 크기로 나타낼 수 있는 수학적 구조입니다.

모듈형 산술(또는 소수 필드)이 가장 일반적인 유한 필드의 유형이지만 확장 필드라는 또 다른 유형이 있습니다. 확장 필드인 복수형을 이미 보셨을 수도 있습니다. 우리는 새로운 원소를 '상상'하고, i라고 라벨을 붙이고, (3i+2)*(2i+4)=6i*i+12i+4i+8=16i+2와 같은 수학적 연산을 수행합니다. 마찬가지로 소수장의 확장을 취할 수 있습니다. 더 작은 필드로 작업하기 시작하면서 보안을 유지하기 위해 소수 필드 확장이 점점 더 중요해지고 있으며, (비니우스가 사용하는 ) 이진 필드는 전적으로 확장에 의존해야 실질적인 유용성을 발휘할 수 있습니다.

검토: 산술화

SNARK와 STARK 컴퓨터 프로그램을 증명하는 방법은 산술을 통해 증명하고자 하는 프로그램에 대한 문을 가지고 를 다항식이 포함된 수학 방정식으로 변환합니다. 방정식에 대한 유효한 해는 프로그램의 유효한 실행에 해당합니다.

간단한 예로 100번째 피보나치수를 계산했는데 그 수치가 무엇인지 증명하고 싶다고 가정해 보겠습니다. 피보나치 급수를 100단계에 걸쳐 F(0)=F(1)=1, F(2)=2, F(3)=3, F(4)=5 등으로 인코딩하는 다항식 F를 만들었습니다. 제가 증명해야 하는 조건은 전체 범위 x={0,1...98}에 걸쳐 F(x+2)=F(x)+F(x+1)입니다. 몫을 제공함으로써 이를 증명할 수 있습니다.

where Z. (x) = (x-0) * (x-1) * ...(x-98)... F가 있고 H가 이 방정식을 만족시킨다면, F는 해당 범위에서 F(x+2)-F(x+1)-F(x)를 만족시켜야 합니다. 추가로 F가 F(0)=F(1)=1을 만족한다는 것을 확인한다면, F(100)은 실제로 100번째 피보나치수여야 합니다.

더 복잡한 것을 증명하려면 '간단한' 관계인 F(x+2) = F(x) + F(x+1)을 'F(x+1)은 상태 F(x)로 VM을 초기화한 결과'라는 더 복잡한 방정식으로 바꾸고 계산 단계를 실행합니다. 100이라는 숫자를 더 큰 숫자(예: 100000000)로 대체하여 더 많은 단계를 수용할 수도 있습니다.

모든 SNARK와 STARK는 다항식(때로는 벡터와 행렬)에 간단한 방정식을 사용하여 개별 값 간의 수많은 관계를 표현하는 아이디어를 기반으로 합니다. 모든 알고리즘이 위와 같이 인접한 계산 단계 간의 동등성을 확인하는 것은 아닙니다. 예를 들어, PLONK는 그렇지 않으며 R1CS도 마찬가지입니다. 그러나 동일한 검사(또는 동일한 몇 가지 검사)를 여러 번 수행하면 오버헤드를 최소화할 수 있기 때문에 가장 효율적인 검사 중 다수가 동일성 검사를 수행합니다.

Plonky2: 256비트 SNARK 및 STARK에서 64비트로 ...... 오직 STARK

5년 전의 영지식 증명의 여러 유형을 합리적으로 요약하면 다음과 같습니다. 영지식 증명에는 (타원 곡선 기반) SNARK와 (해시 기반) STARK의 두 가지 유형이 있습니다. 기술적으로는 STARK가 SNARK의 한 유형이지만, 실제로는 타원 곡선 기반 방식을 지칭할 때 'SNARK'를 사용하고 해시 기반 구조를 지칭할 때 'STARK'를 사용하는 것이 일반적입니다. SNARK는 매우 작아서 매우 빠르게 검증할 수 있습니다! STARK는 크기는 크지만 신뢰할 수 있는 설정이 필요하지 않으며 양자 내성이 있습니다.

△ STARK는 데이터를 다항식으로 취급하여 작동합니다. 다항식으로 취급하고, 해당 다항식의 계산을 계산하며, 확장된 데이터의 머클 루트를 '다항식 공약'으로 사용합니다.

여기서 중요한 역사는 타원 곡선 기반 SNARK가 처음 널리 사용되었다는 것입니다. 2018년경이 되어서야 FRI 덕분에 STARK가 충분히 효율적이 되었고, 그 무렵에는 지캐시가 1년 이상 운영된 후였다는 것입니다. 타원 곡선 기반 SNARK에는 한 가지 중요한 제한이 있습니다. 타원 곡선 기반 SNARK를 사용하려면 해당 방정식의 산술은 타원 곡선의 점 수의 계수를 사용하여 수행해야 합니다. 이는 일반적으로 2의 256제곱에 가까운 매우 큰 숫자입니다(예: bn128 곡선은 21888242871839275222246405745257275088548364400416034343698204186575808495617). 하지만 실제 계산에서는 작은 숫자를 사용합니다. '실제' 프로그램을 고려할 때 사용하는 대부분의 요소는 카운터, 루프에 대한 인덱스, 프로그램 내 위치, 참 또는 거짓을 나타내는 개별 비트 등 거의 항상 몇 자리 길이에 불과한 것들입니다.

'원시' 데이터가 '작은' 숫자로 구성되어 있더라도 증명 프로세스에서는 몫, 지수, 임의 선형 조합 및 기타 데이터 변환을 계산해야 하므로 평균적으로 필드 전체 크기와 같거나 더 큰 수의 객체가 생성됩니다. 이로 인해 중요한 비효율성이 발생하는데, 작은 값 n개에 대한 계산을 정당화하려면 훨씬 큰 값 n개에 대해 더 많은 계산을 수행해야 합니다. 처음에 STARK는 256비트 필드를 사용하는 SNARK의 습관을 그대로 물려받았기 때문에 동일한 비효율성을 겪었습니다.

△ 일부 다항식 값 리드-. 솔로몬 확장. 원래 값은 작지만 추가 값이 필드의 전체 크기로 확장됨(이 경우 2의 31번째 거듭제곱 - 1)

2022년 Plonky2가 출시되었습니다. Plonky2의 주요 혁신은 작은 소수인 산술 모듈로, 2의 64번째 거듭제곱을 2의 32번째 거듭제곱으로 확장한 것입니다. - 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를 3의 3승 = 5로 정의하고 1, y, y의 2승의 조합을 가져올 수 있습니다. 이렇게 하면 총 좌표 수가 약 2의 93제곱으로 증가합니다. 증명자가 계산하는 대부분의 다항식은 이 확장 영역에 들어가지 않고 2 - 1의 31승의 제곱을 취한 정수만 계산하므로 작은 영역을 사용함으로써 얻을 수 있는 모든 효율을 여전히 누릴 수 있습니다. 그러나 랜덤 포인트 검사 및 FRI 계산은 필요한 보안을 얻기 위해 이 더 큰 도메인을 조사합니다.

작은 소수에서 2진수까지

컴퓨터는 큰 수를 0과 1의 시퀀스로 표현하고 그 위에 '회로'를 구성하여 산술 연산을 수행합니다. 컴퓨터는 더 큰 숫자를 0과 1의 시퀀스로 표현하여 산술 연산을 수행하고, 이러한 비트 위에 "회로"를 구축하여 덧셈과 곱셈과 같은 연산을 계산합니다. 컴퓨터는 16비트, 32비트 및 64비트 정수에 최적화되어 있습니다. 예를 들어 2의 64제곱에 2 - 2의 32제곱에 +1, 2의 31제곱에 -1은 이러한 범위를 준수할 뿐만 아니라 잘 맞기 때문에 선택되었습니다. 일반적인 32비트 곱셈을 수행하고 출력을 비트별로 이동하고 몇 군데 복사하면 2의 64제곱에 2 - 2의 32제곱에 +1 곱셈을 수행할 수 있으며, 이 게시물은 몇 가지 요령을 잘 설명해줍니다.

그러나 더 나은 접근 방식은 2진법으로 직접 계산하는 것입니다. 덧셈이 '그냥' 이소이거나 1 + 1을 한 비트에서 다음 비트로 더하는 오버플로에 대한 걱정 없이 '운반'할 수 있다면 어떨까요? 곱셈도 같은 방식으로 더 평행하게 할 수 있다면 어떨까요? 이러한 장점은 모두 단일 비트로 참/거짓 값을 표현할 수 있다는 점을 기반으로 합니다.

이러한 직접 이진 계산의 이점을 활용하는 것이 바로 Binius가 추구하는 바이며, Binius 팀은 zkSummit 프레젠테이션에서 다음과 같이 효율성 향상을 입증했습니다:

32비트 이진 필드 연산은 거의 동일한 '크기'임에도 불구하고 31비트 메르센 필드 연산보다 5배 적은 연산 리소스를 필요로 합니다.

단항 다항식에서 하이퍼큐브로

이 추론을 믿고 비트(0과 1)로 모든 작업을 하고 싶다고 가정해 봅시다. 10억 비트를 어떻게 다항식으로 표현할 수 있을까요?

여기서 우리는 두 가지 실질적인 문제에 직면합니다.

1. 많은 수의 값을 나타내는 다항식의 경우, 이러한 값은 다음과 같아야 합니다. 위의 피보나치 예시에서는 F(0), F(1) ... F(100), 더 큰 계산에서는 지수가 수백만 개에 달할 수 있는 등 다항식을 평가하는 동안 액세스할 수 있어야 합니다. 우리가 사용하는 필드에는 그 크기까지의 숫자가 포함되어야 합니다.

2. 모든 스타크와 마찬가지로 머클 트리에서 제출하는 모든 값은 리드-솔로몬으로 인코딩되어야 함을 증명합니다: 예를 들어 값을 n에서 8n으로 확장하고 중복성을 사용하여 악의적인 증명자가 값을 위조하는 계산 중에 값을 위조하여 부정행위를 하는 것을 방지하기 위해 이중화를 사용합니다. 또한 백만 개의 값을 8백만 개로 확장하려면 다항식을 계산하는 데 8백만 개의 서로 다른 점이 필요합니다.

비니우스의 핵심 아이디어 중 하나는 이 두 가지 문제를 개별적으로 해결하고, 동일한 데이터를 두 가지 방식으로 표현하는 것입니다. 첫째, 다항식 자체입니다.

타원 곡선을 기반으로 하는 SNARK, 2019년형 STARK, Plonky2와 같은 시스템은 일반적으로 하나의 변수인 F(x)의 다항식을 다룹니다. 반면, 비니우스는 스파르탄 프로토콜에서 영감을 얻어 다변량 다항식인 F(x1,x2,... xk)를 사용합니다. 사실상 계산의 전체 궤적을 계산 "하이퍼큐브"로 표현하는데, 여기서 각 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) 다항식이 있습니다. 따라서 이 값 집합을 다항식의 표현으로 생각할 수 있으며 계수를 계산할 필요가 없습니다.

이 예시는 물론 설명을 위한 것입니다. 실제로 하이퍼큐브를 사용하는 이유는 개별 비트로 작업할 수 있기 때문입니다. 피보나치수를 계산하는 "비니우스 기본" 방식은 각 그룹에 16비트를 사용하여 한 자리를 저장하는 고차원 정육면체를 사용하는 것입니다. 이를 위해서는 비트 위에 정수를 추가하는 약간의 독창성이 필요하지만, 비니우스에게는 그리 어렵지 않습니다.

이제 검열을 살펴보겠습니다. 검열은 STARK가 작동하는 방식으로, n개의 값을 가져와서 리드-솔로몬이 더 많은 값(보통 8n, 보통 2n에서 32n 사이)으로 확장한 다음 확장에서 일부 머클 분기를 임의로 선택해 일종의 확인을 수행합니다. 하이퍼큐브는 각 차원의 길이가 2이므로 직접 확장하는 것은 비현실적입니다. 16개의 값에서 머클 분기를 샘플링할 '공간'이 충분하지 않기 때문입니다. 그렇다면 어떻게 해야 할까요? 하이퍼큐브가 정사각형이라고 가정해 봅시다!

간단한 비니우스 - 예제

이 프로토콜의 파이썬 구현을 보려면 다음 링크를 브라우저에 복사하세요: https://github.com/ethereum/research/blob/master/binius/simple_binius.py

예제를 살펴보겠습니다. 편의상 일반 정수 를 필드로 사용하겠습니다(실제 구현에서는 이진 필드 요소가 사용됨). 먼저 제출하려는 하이퍼큐브를 가져와 정사각형으로 인코딩합니다.

이제 리드-솔로몬으로 정사각형을 확장합니다. 즉, 각 행을 x = {0,1,2,3}의 값을 갖는 3차 다항식과 x = {4,5,6,7}의 값을 갖는 동일한 다항식으로 처리합니다:

수치가 빠르게 확장된다는 점에 유의하세요! 그렇기 때문에 실제 구현에서는 항상 일반 정수 대신 유한 필드를 사용합니다. 예를 들어 정수 모듈로 11을 사용하면 첫 번째 줄의 확장은 [3,10,0,6]이 됩니다.

확장을 직접 시도하고 숫자를 확인하려면 여기에서 간단한 리드-솔로몬 확장 코드를 사용할 수 있습니다.

다음으로 이 확장을 열로 취급하고 열의 머클 트리를 만듭니다. 머클 트리의 뿌리는 우리의 약속입니다.

자, 이제 증명자가 언젠가 이 연산에 대해 이 다항식 r={r0,r1,r2,r3}의 계산을 증명하고 싶다고 가정해 봅시다. 비니우스에는 다른 다항식 커밋 체계보다 약한 뉘앙스가 있습니다: 증명자는 머클 루트에 커밋하기 전에 s를 알거나 추측할 수 없어야 합니다(즉, r은 머클 루트에 의존하는 의사 랜덤 값이어야 합니다). 이렇게 하면 "데이터베이스 조회"(예: "좋아, 머클 루트를 주었으니 이제 P(0,0,1,0)을 증명해 주세요!")에는 이 방식이 쓸모가 없게 됩니다. !").

하지만 우리가 실제로 사용하는 영지식 증명 프로토콜은 일반적으로 "데이터베이스 조회"가 필요하지 않으며, 평가에서 임의의 지점에서 다항식을 확인하기만 하면 됩니다. 따라서 이 제한은 우리의 목적에 적합합니다.

r={1,2,3,4}(이 시점에서 다항식은 -137로 계산되며, 이 코드를 사용하여 확인할 수 있습니다)를 선택한다고 가정해 보겠습니다. 이제 증명으로 넘어가겠습니다. 첫 번째 부분 {1,2}는 행 내의 열의 선형 조합을 나타내고, 두 번째 부분 {3,4}는 행의 선형 조합을 나타내는 두 부분으로 나눕니다. 열 부분에 대해 '텐서 곱'을 계산합니다.

행 부분의 경우:

이것은 다음을 의미합니다. 값의 가능한 모든 제품 목록입니다. 행의 경우 다음과 같이 됩니다.

[(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와 무작위로 샘플링된 일부 열에 대한 머클 증명. 예시의 예시에서는 증명자가 마지막 열만 제공하도록 하겠지만, 실제로는 충분한 보안을 달성하기 위해 수십 개의 열을 제공해야 할 것입니다.

이제 리드-솔로몬 코드의 선형성을 활용합니다. 우리가 사용하는 핵심 속성은 리드-솔로몬 확장의 선형 조합을 취하면 리드-솔로몬 확장의 선형 조합과 동일한 결과를 얻을 수 있다는 것입니다. 이러한 '순차적 독립성'은 일반적으로 두 연산이 모두 선형일 때 발생합니다.

검증자는 정확히 그렇게 했습니다. 이들은 t를 계산하고 증명자가 이전에 계산한 것과 동일한 열의 선형 조합(증명자가 제공한 열만)을 계산한 다음 두 프로세스가 동일한 답을 내는지 확인합니다.

이 예제에서 동일한 열을 계산하는 것은 확장자 t입니다. 선형 조합([6,-9,-8,12], 둘 다 같은 답인 -10746을 산출합니다. 이는 머클의 근이 '선의로'(또는 적어도 '충분히 가깝게') 구성되었으며, 적어도 대부분의 열이 서로 호환된다는 것을 증명합니다.

하지만 검증자가 확인해야 할 또 다른 사항이 있습니다: 다항식 {r0...r3}의 합계를 확인해야 합니다. 지금까지 검증자의 어떤 단계도 실제로 증명자가 주장한 값에 의존하지 않았습니다. 이를 확인하는 방법은 다음과 같습니다. 계산 지점으로 레이블을 지정한 '열 부분'의 텐서 곱을 취합니다.

이 예제에서 r={1,2,3,4}(선택 열의 절반이 {1,2})인 경우, 이는 다음과 같습니다.

이제 이 선형 조합 t:

이것은 다항식을 직접 구한 것과 같은 결과입니다.

위 내용은 '간단한' 비니우스 프로토콜에 대한 완전한 설명에 가깝습니다. 예를 들어, 데이터가 행과 열로 분할되므로 크기가 절반으로 줄어든 필드만 있으면 된다는 흥미로운 장점이 있습니다. 하지만 바이너리 컴퓨팅의 모든 이점을 실현하지는 못합니다. 이를 위해서는 완전한 바이너리 프로토콜이 필요합니다. 하지만 먼저 바이너리 필드에 대해 자세히 살펴보겠습니다.

이진 필드

가장 작은 필드는 산술 모듈로 2로, 덧셈과 곱셈 테이블을 쓸 수 있을 정도로 매우 작습니다.

확장을 통해 더 큰 이진 필드를 얻을 수 있습니다: F2( 정수 모듈로 2)로 시작한 다음 x 제곱 = x+1인 x를 정의하면 다음과 같은 덧셈 및 곱셈 테이블을 얻을 수 있습니다.

이 구성을 반복하면 이진 필드를 임의로 큰 크기로 확장할 수 있다는 것이 밝혀졌습니다. 새로운 원소를 추가할 수는 있지만 더 이상 I 원소를 추가할 수 없는 실수의 복소수와 달리(쿼터니언은 존재하지만 수학적으로 이상합니다. 예를 들어 ab는 ba와 같지 않습니다), 유한 필드를 사용하면 새로운 확장을 영원히 추가할 수 있습니다. 구체적으로 요소를 다음과 같이 정의합니다:

Wait ....... 연속적으로 확장할 때마다 타워에 새로운 레이어가 추가되는 것으로 볼 수 있기 때문에 이를 타워 구조라고도 합니다. 이 방법이 임의의 크기의 바이너리 필드를 구성하는 유일한 방법은 아니지만, Binius가 활용하는 몇 가지 고유한 이점이 있습니다.

이 숫자들을 비트 목록으로 표현할 수 있습니다. 예를 들어 110010101010001111. 첫 번째 비트는 1의 배수, 두 번째 비트는 x0의 배수, 그 다음 비트는 x1, x1*x0, x2, x2*x0 등과 같은 x1 숫자의 배수를 나타냅니다. 이 인코딩은 다음과 같이 세분화할 수 있기 때문에 좋습니다.

. 이것은 비교적 흔하지 않은 표현이지만, 저는 오른쪽에 더 효율적인 비트가 있는 비트 표현을 사용하여 이진 필드 요소를 정수로 표현하는 것을 좋아합니다. 즉, 1=1, x0=01=2, 1+x0=11=3, 1+x0+x2=11001000 =19 등과 같은 식으로 표현합니다. 이 표현식에서는 61779입니다.

이진수 필드에서 덧셈은 이소 또는 (그런데 뺄셈도 마찬가지입니다.) 모든 x에 대해 x+x=0을 의미합니다. 두 요소인 x*y를 곱하려면 각 수를 반으로 나누는 매우 간단한 재귀 알고리즘이 있습니다.

그런 다음 곱셈을 나눕니다:

마지막 부분은 단순화 규칙을 적용해야 하기 때문에 약간 까다로운 유일한 부분입니다. 카라츠바 알고리즘이나 고속 푸리에 변환과 같이 곱셈을 더 효율적으로 수행하는 방법이 있지만, 관심 있는 독자들이 알아낼 수 있도록 연습 문제로 남겨두겠습니다.

2진 필드의 나눗셈은 곱셈과 반전을 결합하여 수행합니다. "단순하지만 느린" 반전 방법은 일반화된 페르마의 작은 정리를 응용한 것입니다. 더 복잡하지만 더 효율적인 반전 알고리즘도 여기에서 찾을 수 있습니다. 여기에 있는 코드를 사용하여 이진 필드의 덧셈, 곱셈, 나눗셈을 해볼 수 있습니다.

△ 왼쪽: 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제곱에 맞으므로 당황하지 않아도 됩니다. Ether의 EIP-4844에서 블롭의 개별 '블록'은 숫자 모듈로 52435875175126190479447740508185965837690552500527637822603658699938581184513 여야 하므로 이진 데이터를 인코딩하면 약간의 공간이 낭비되고 각 요소가 2의 248제곱보다 작은 값을 저장하는지 확인하기 위해 애플리케이션 계층에서 추가 검사가 필요합니다.

이것은 또한 바이너리 필드 연산이 CPU와 이론적으로 최적의 FPGA 및 ASIC 설계 모두에서 컴퓨터에서 매우 빠르다는 것을 의미합니다.

이 모든 것은 위의 예제에서 보았듯이 리드-솔로몬 인코딩이 정수 '폭발'을 완전히 피하는 방식으로, 그리고 컴퓨터가 잘하는 계산을 매우 '네이티브'한 방식으로 수행할 수 있다는 것을 의미합니다. 바이너리 필드의 '분할' 속성 - 1100101010001111=11001010+10001111*x3을 사용한 다음 필요에 따라 분할하는 방법 또한 유연성을 확보하는 데 매우 중요합니다.

비니우스 전체

프로토콜의 파이썬 구현은 아래 링크를 복사하여 브라우저에서 확인하세요:https://. github.com/ethereum/research/blob/master/binius/packed_binius.py

이제 "전체 Binius"로 이동하여 "simple Binius'는 (i) 이진 필드에서 작업하고 (ii) 단일 비트를 커밋하도록 조정합니다.이 프로토콜은 비트 행렬을 보는 여러 가지 방법을 오가기 때문에 이해하기 어렵고, 일반적으로 암호화 프로토콜을 이해하는 데 걸리는 시간보다 확실히 더 오래 걸렸습니다. 하지만 바이너리 필드를 이해하고 나면 좋은 소식은 비니어스가 사용하는 '어려운 수학'이 존재하지 않는다는 것입니다.

더 깊고 깊은 대수 기하학의 토끼 구멍이 있는 타원 곡선 페어링이 아니라 이진 필드만 있으면 됩니다.

전체 차트를 다시 살펴봅시다:

이제 대부분의 구성 요소에 익숙해졌을 것입니다. 하이퍼큐브를 격자로 '평탄화'하는 아이디어, 행-열 조합과 열-조합을 평가된 점의 텐서 곱으로 계산하는 아이디어, '리드-솔로몬 확장 후 행-열 조합 계산'과 '행-열 조합 계산 후 리드-솔로몬 확장' 간의 동등성을 테스트하는 아이디어는 모두 간단한 Binius에서 구현됩니다.

'전체 비니어스'의 새로운 기능은 무엇인가요? 기본적으로 세 가지입니다.

• 하이퍼큐브와 사각형의 개별 값은 비트(0 또는 1)여야 합니다.

• 확장 프로세스는 비트를 열로 그룹화하고 일시적으로 더 큰 필드 요소라고 가정하여 비트를 더 많은 비트로 확장합니다.

• 행 결합 단계가 끝나면 다음에 확장자를 다시 비트로 변환하는 요소별 '비트로 분해' 단계가 이어집니다.

이 두 가지 경우에 대해 차례로 설명하겠습니다. 첫째, 새로운 확장 절차 리드-솔로몬 코드에는 기본적인 한계가 있는데, n을 k*n으로 확장하려면 좌표로 사용할 수 있는 k*n의 값이 다른 필드에서 작업해야 한다는 것입니다. F2(일명 비트)를 사용하면 그렇게 할 수 없습니다. 따라서 이웃하는 F2의 요소를 함께 '패킹'하여 더 큰 값을 형성합니다. 여기 예시에서는 {0, 1, 2, 3} 요소에 한 번에 두 비트를 넣었는데, 확장에는 계산 포인트가 4개뿐이므로 이 정도면 충분합니다. '실제' 증명에서는 한 번에 16비트를 반환할 수도 있습니다. 그런 다음 이 압축된 값에 대해 리드-솔로몬 코드를 실행하고 다시 비트로 압축을 해제합니다.

자, 이제 행 조합입니다. '임의의 점에서의 값'을 암호학적으로 안전하게 확인하려면 상당히 큰 공간(하이퍼큐브 자체보다 훨씬 큰 공간)에서 점을 샘플링해야 합니다. 따라서 하이퍼큐브 내부의 점은 비트 단위이지만, 하이퍼큐브 외부에서 계산된 값은 훨씬 더 커집니다. 위의 예에서 '행 조합'은 결국 [11,4,6,1]이 됩니다.

비트를 더 큰 값으로 결합한 다음 그 위에 리드-솔로몬 확장을 수행하는 방법은 알고 있지만 더 큰 값 쌍에 대해 동일한 작업을 수행하려면 어떻게 해야 할까요?

비니우스의 비결은 각 값의 개별 비트(예: [1,1,0,1], 즉 "11"이라고 레이블을 붙인 값)를 살펴본 다음 행 단위로 확장하는 것입니다. 확장 프로세스는 객체에서 수행됩니다. 즉, 각 요소에 대해 1행에서 확장 프로세스를 수행한 다음 x0 행에서, "x1" 행에서, x0x1 행에서 확장하는 식으로 수행합니다(장난감 예제에서는 여기서 멈추지만 실제 구현에서는 128행이 됩니다(마지막 행은 x6*...*x0))

검토

하이퍼큐브의 비트를 가져와 그리드로 변환한 다음 각 행의 인접한 비트 그룹을 더 큰 필드 요소로 취급하고 산술 연산을 수행하여 다음과 같이 계산합니다. 리드-솔로몬 확장 행.

다음으로, 각 열에 있는 비트의 행 조합을 가져와 각 행의 비트 열을 출력으로 얻습니다(4x4보다 큰 사각형의 경우 훨씬 작음).

마지막으로, 출력을 행렬로, 비트를 행으로 생각하면 됩니다.

왜 그럴까요? '일반적인' 수학에서는 숫자를 비트 단위로 나누기 시작하면 (일반적으로) 어떤 순서로든 선형 연산을 수행하여 동일한 결과를 얻는 기능이 실패합니다.

하지만 3번을 한 다음 8번을 하면 다음과 같이 됩니다:

하지만 3번을 한 다음 8번을 하면 다음을 얻게 됩니다. 그리고 8번을 하면 다음과 같이 됩니다:

하지만 타워로 구성된 이진 필드에서는 구조로 이진 필드를 구축하는 경우에는 이 접근 방식이 효과적입니다. 그 이유는 분리 가능성 때문입니다. 큰 값에 작은 값을 곱하면 각 줄 세그먼트에서 일어나는 일이 각 줄 세그먼트에 그대로 유지됩니다. 1100101010001111 에 11을 곱하면, 이는 1100101010001111 의 첫 번째 분해와 동일합니다.

그런 다음 각 구성 요소에 11을 곱합니다.

함께 곱하기

일반적으로 영지식 증명 시스템은 다항식에 대한 진술을 하면서 기본 평가에 대한 진술을 표시하는 방식으로 작동하며, 이는 피보나치에서 본 것처럼 에서 피보나치 계산의 모든 단계를 확인하면서 F(X+2)-F(X+1)-F(X) = Z(X)*H(X)를 보았던 것처럼 말이죠. 임의의 지점에서 값을 증명하는 방식으로 다항식에 대한 문을 확인합니다. 다항식 방정식이 일치하지 않으면 특정 임의의 좌표에서 일치할 가능성이 매우 낮으므로 임의의 지점에서 확인하는 것은 전체 다항식에 대한 확인을 의미합니다.

실제 비효율의 주된 이유 중 하나는 실제 프로그램에서는 루프에 대한 인덱스, 참/거짓 값, 카운터 등 다루는 숫자가 대부분 작다는 것입니다. 그러나 리드-솔로몬 인코딩을 사용하여 머클 증명 기반 검사를 안전하게 만드는 데 필요한 중복성을 가지고 데이터를 '확장'하면, 원래 값이 작더라도 대부분의 '추가' 값이 필드의 전체 크기를 차지하게 됩니다.

이 문제를 해결하기 위해 필드를 최대한 작게 만들고자 Plonky2에서는 256비트 숫자에서 64비트 숫자로 줄였고, Plonky3에서는 31비트까지 더 줄였습니다. 하지만 이마저도 최적은 아닙니다. 이진 필드를 사용하면 단일 비트를 처리할 수 있습니다. 이렇게 하면 인코딩이 '고밀도'가 됩니다. 실제 기본 데이터가 n비트인 경우 인코딩은 n비트를 갖게 되고 확장자는 추가 오버헤드 없이 8 * n비트를 갖게 됩니다.

자, 이제 이 차트를 세 번째로 살펴봅시다:

비니우스에서는 다선형 다항식인 하이퍼큐브 P(x0,x1,...xk)를 사용하며, 여기서 개별 평가인 P(0,0,0,0), P(0,0,0,1)에서 P(1,1,1,1)까지 우리가 관심 있는 데이터를 보유합니다. 데이터. 특정 지점에서의 계산을 정당화하기 위해 동일한 데이터를 사각형으로 '재해석'합니다. 그런 다음 리드-솔로몬 인코딩을 사용하여 각 행을 확장하여 무작위 머클 분기 쿼리가 안전하도록 필요한 데이터 중복성을 제공합니다. 그런 다음 행의 무작위 선형 조합을 계산하여 계수를 설계하여 새로 결합된 행에 실제로 관심 있는 계산된 값이 포함되도록 합니다. 이렇게 새로 생성된 행(128행의 비트로 재해석됨)과 머클 분기가 있는 무작위로 선택된 일부 열이 검증자에게 전달됩니다.

그런 다음 검증자는 '확장 행 조합'(또는 확장 열)과 '확장 행 조합'을 수행하여 두 조합이 일치하는지 확인합니다. 그런 다음 열 조합을 계산하고 증명자가 선언한 값을 반환하는지 확인합니다. 이것이 바로 저희의 증명 시스템(더 정확하게는 증명 시스템의 핵심 구성 요소인 다항식 커미트먼트 체계)입니다.

아직 다루지 않은 내용은 무엇인가요?

• 행 확장을 위한 효과적인 알고리즘, 이는 검증자의 계산 효율성을 실제로 개선하는 데 필요합니다. 여기에 설명된 대로 이진 필드에 고속 푸리에 변환을 사용합니다(이 게시물에서는 재귀 확장을 기반으로 하지 않는 덜 효율적인 구조를 사용하므로 정확한 구현은 달라질 수 있습니다).

• 산술화. 단항식은 F(X+2)-F(X+1)-F(X) = Z(X)*H(X)와 같이 계산에서 인접한 단계를 연관시킬 수 있기 때문에 편리합니다. 하이퍼큐브에서 '다음 단계'는 'X+1'보다 훨씬 덜 해석됩니다. (k의 거듭제곱인 X+k를 할 수도 있지만, 이러한 점프 동작은 비니우스의 주요 장점을 많이 희생합니다. 비니우스 논문에서 해결책을 설명합니다. (섹션 4.3 참조) 그러나 이것은 그 자체로 "깊은 토끼굴"입니다.

• 값별 확인을 안전하게 수행하는 방법. 피보나치 예시에서는 주요 경계 조건인 F(0)=F(1)=1과 F(100)의 값을 확인해야 합니다. 하지만 '원래' 비니우스를 사용하면 알려진 계산 지점에서 확인하는 것이 안전하지 않습니다. 소위 합계 검사 프로토콜을 사용하여 알려진 계산 검사를 알려지지 않은 계산 검사로 변환하는 매우 간단한 방법이 있지만 여기서는 이에 대해 이야기하지 않습니다.

• 조회 프로토콜은 최근 매우 효율적인 증명 시스템을 만들기 위해 널리 사용되고 있는 또 다른 기술로, Binius는 많은 애플리케이션에서 조회 프로토콜과 함께 사용될 수 있습니다.

• 제곱근 검증 시간을 넘어서. 제곱근은 비용이 많이 듭니다. 비니우스 증명 2의 32제곱의 길이가 약 11MB에 달합니다. 다른 증명 시스템을 사용하여 "비니우스 증명의 증명"을 만들어 비니우스 증명의 효율성과 더 작은 증명 크기를 얻음으로써 이를 보완할 수 있습니다. 또 다른 옵션은 더 복잡한 FRI-비니우스 프로토콜로, 일반 FRI와 마찬가지로 다중 로그 크기의 증명을 생성합니다.

• 비니우스가 "SNARK 친화성"에 미치는 영향. 간단히 요약하자면, 비니어스를 사용하면 '일반' 해싱이 기존의 산술 해싱보다 더 이상 효율적이지 않고, 모듈로 2를 32제곱으로 곱하거나 모듈로 2를 256제곱으로 곱하는 것이 모듈로 곱하기보다 더 이상 골치 아프지 않는 등 계산을 '산술 친화적으로' 만드는 데 신경 쓸 필요가 없어진다는 것입니다. 하지만 이것은 복잡한 주제입니다. 모든 것이 바이너리 형식으로 이루어지면 많은 것이 달라집니다.

앞으로 몇 달 안에 이진 필드 기반 증명 기술이 더욱 개선되기를 기대합니다.