한 문장으로 FOAKS 내의 다항식 약속 계약 Brakedown 이해하기
Brakedown은 비교적 큰 증명 크기를 가지고 있지만, 현재 가장 빠른 다항식 약속 프로토콜임에 틀림없습니다.작성자: Fox Tech CEO 강수약, Fox Tech 수석 과학자 맹현제
서론: 만약 암호학자들이 텐서 곱(Tensor Product)과 다항식 값 사이의 연관성을 발견하지 않았다면, 다항식 약속 프로토콜 Brakedown이 등장하기는 어려웠을 것이며, Brakedown을 기반으로 한 Orion 및 FOAKS와 같은 새로운 빠른 알고리즘이 탄생할 수 없었을 것입니다.
많은 다항식 약속에 의존하는 제로 지식 증명 시스템에서 다양한 약속 프로토콜이 사용됩니다. a16z의 Justin Thaler가 2022년 8월에 발표한 "Measuring SNARK performance: Frontends, backends, and the future"에서 평가한 바에 따르면, Brakedown은 Proof Size가 크지만 현재 가장 빠른 다항식 약속 프로토콜임이 분명합니다.
FRI, KZG, Bulletproof는 더 일반적인 다항식 약속 프로토콜이지만, 속도가 병목 현상입니다. zkSync에서 사용하는 Plonky, Polygon zkEVM에서 사용하는 Plonky2, Scroll에서 사용하는 Ultra-Plonk와 같은 알고리즘은 KZG 기반의 다항식 약속입니다. Prover는 다량의 FFT 계산과 MSM 연산을 통해 다항식과 약속을 생성하며, 이 두 가지는 모두 많은 계산 부담을 초래합니다. MSM은 다중 스레드 가속의 잠재력이 있지만, 많은 메모리를 필요로 하며, 고병렬에서도 느리며, 대형 FFT는 알고리즘 실행 시 데이터의 빈번한 셔플에 심각하게 의존하여 분산 가속을 통해 계산 클러스터 간 로딩이 어렵습니다.
더 빠른 다항식 약속 프로토콜 Brakedown 덕분에 이러한 계산의 복잡성이 크게 감소했습니다.
FOAKS는 Fast Objective Argument of Knowledges의 약자로, Fox Tech에서 제안한 Brakedown 기반의 제로 지식 증명 시스템 프레임워크입니다. FOAKS는 Orion을 기반으로 FFT 연산을 추가로 줄여 최종적으로 FFT를 제거하는 것을 목표로 합니다. 또한 FOAKS는 증명 크기를 줄이기 위해 매우 정교한 새로운 증명 재귀 방식을 설계했습니다. FOAKS 프레임워크의 장점은 선형 증명 시간을 구현하는 동시에 증명 크기가 작아 zkRollup 시나리오에 매우 적합하다는 점입니다.
아래에서는 FOAKS에서 사용하는 다항식 약속 프로토콜 Brakedown에 대해 자세히 설명하겠습니다.
암호학에서 약속(Commitment) 프로토콜은 증명자(Prover)가 특정 비밀 값에 대해 약속을 하고 공개 약속 값을 생성하는 것으로, 이 약속 값은 바인딩(Binding)성과 숨김(Hiding)성을 가집니다. 이후 제출자는 이 약속을 열고 메시지를 검증자에게 보내 약속과 메시지 간의 대응 관계를 검증해야 합니다. 이 점에서 약속 프로토콜과 해시 함수의 역할에는 많은 공통점이 있지만, 약속 프로토콜은 종종 공개 키 암호학 분야의 수학적 구조에 의존합니다. 다항식 약속(Polynomial Commitment)은 다항식에 대한 약속 방식으로, 즉 약속된 값이 다항식입니다. 또한 다항식 약속 프로토콜에는 주어진 점에서 값을 취하고 증명을 제공하는 알고리즘이 포함되어 있어, 다항식 약속 프로토콜 자체가 중요한 암호학 프로토콜의 일종이 되어 많은 제로 지식 증명 시스템의 핵심 부분이 됩니다.
최신 암호학 분야의 연구에서 텐서 곱(Tensor Product)과 다항식 값 사이의 연관성이 발견되면서 이와 관련된 여러 다항식 약속 프로토콜이 탄생하였으며, Brakedown은 그 대표적인 프로토콜입니다.
Brakedown의 프로토콜 세부 사항을 자세히 설명하기 전에 몇 가지 기본 지식을 이해해야 합니다. 우리는 먼저 선형 코드(Linear Code), 충돌 저항 해시 함수(Hash Function), 머클 트리(Merkle Tree), 텐서 곱(Tensor Product)의 연산 및 다항식 값의 텐서 곱 표현을 이해해야 합니다.
먼저 선형 코드(Linear Code)에 대해 설명하겠습니다. 메시지 길이가 k이고 코드워드 길이가 n인 선형 코드는 메시지에서 코드워드로의 단사 함수가 존재하는 선형 부분 공간 CFn입니다. 임의의 코드워드의 선형 조합은 여전히 코드워드입니다. 두 코드워드 u, v의 거리는 그들의 해밍 거리로, (u,v)로 표기합니다. 최단 거리는 d=minu,v(u,v)입니다. 이러한 코드는 [n,k,d] 선형 코드로 표기하며, dn으로 코드의 상대 거리를 나타냅니다.
다음으로 충돌 저항 해시 함수(Hash Function)와 머클 트리(Merkle Tree)에 대해 알아보겠습니다.
H:{0,1}2{0,1}로 해시 함수를 나타냅니다. 머클 트리는 2d개의 메시지에 대한 약속을 구현할 수 있는 특별한 데이터 구조로, 해시 값 h를 생성하며, 어떤 메시지를 열 때 d+1개의 해시 값이 필요합니다.
머클 트리는 깊이가 d인 이진 트리로 표현될 수 있으며, L개의 메시지 요소 m1,m2,…,ml은 각각 트리의 리프에 해당합니다. 트리의 각 내부 노드는 두 자식 노드의 해시 계산으로 도출됩니다. 메시지 mi를 열 때, mi에서 루트 노드까지의 경로를 공개해야 합니다.
다음 기호로 표시합니다:
hMerkle.Commit(m1,…,ml)
(mi,i)Merkle.Open(m,i)
{0,1}Merkle.Verify(i,mi,h)
그림 1: 머클 트리(Merkle Tree)
우리는 또한 텐서 곱(Tensor Product)의 연산이 어떻게 이루어지는지 알아야 합니다. 수학적으로 텐서는 벡터와 행렬을 고차원 공간으로 확장한 것으로, 중요한 연구 대상입니다. 텐서에 대한 자세한 논의는 본문의 연구 범위를 초과하므로, 여기서는 벡터와 행렬의 텐서 곱 연산만 소개합니다.
그림 2: 벡터와 행렬의 텐서 곱 연산
다음으로 다항식 값의 텐서 곱 표현을 알아보겠습니다.
[GLS+]에서는 다항식의 값이 텐서 곱 형태로 표현될 수 있다고 언급합니다. 여기서 우리는 다중 선형 다항식의 약속을 고려합니다.
구체적으로, 주어진 다항식이 벡터 x0,x1,…,xlogN-1에서의 값은 다음과 같이 쓸 수 있습니다:
(x0,x1,…,xlogN-1)=i0=01i1=01…ilogN-1=01wi0i1…ilogN-1x0i0x1i1…xlogN-1ilogN-1
다중 선형의 정의에 따르면, 각 변수의 차수는 0 또는 1이므로, 여기에는 N개의 단항식과 계수, logN개의 변수가 있습니다. i=j=0logN-12jij로 두고, i0i1…ilogN-1은 i의 이진 표현입니다. w를 다항식 계수로 두고, w[i]=wi0i1…ilogN-1로 정의합니다. 마찬가지로, Xi=x0i0x1i1…xlogN-1ilogN-1로 정의합니다. k=N, r0={X0,X1,…,Xk-1}, r1={X0k,X1k,…,Xk-1k}로 두면, X=r0r1이 됩니다.
따라서 다항식 값은 텐서 곱 형태로 표현될 수 있습니다: (x0,x1,…,xlogN-1)=\<w,r0r1>.
마지막으로 FOAKS, Orion[XZS22]에서 사용하는 Brakedown의 과정을 살펴보겠습니다.
먼저, PC.Commit는 다항식 계수 w를 kk 행렬 형태로 나누고 이를 인코딩합니다(참고: "기초 지식"의 선형 코드). 이를 C2로 표기합니다. 이후 C2의 각 열 C2[:,i]에 대해 약속을 생성하고 머클 트리를 구축한 다음, 각 열로 형성된 머클 트리의 루트를 기반으로 또 다른 머클 트리를 구축하여 최종 약속으로 합니다.
값 증명의 계산에서 두 가지를 증명해야 합니다. 첫째는 근접성(Proximity), 둘째는 일관성(Consistency)입니다. 근접성은 약속된 행렬이 인코딩된 코드워드와 충분히 가까운 것을 보장합니다. 일관성은 y=\<w,r0r1>를 보장합니다.
근접성 검증: 근접성 검증은 두 단계로 구성됩니다. 먼저, 검증자가 증명자에게 무작위 벡터 0을 보내고, 증명자는 0과 C1의 내적을 계산합니다. 즉, 0의 성분을 계수로 하여 C1의 행에 대해 선형 조합을 계산합니다. 선형 코드의 특성 덕분에 C0는 y0의 코드워드입니다. 이후 증명자는 C0가 실제로 약속된 코드워드에서 계산된 것임을 증명합니다. 이를 증명하기 위해 검증자는 t개의 열을 무작위로 선택하고, 증명자는 해당 열을 열어 머클 트리 증명을 제공합니다. 검증자는 이러한 열과 0의 내적이 C0의 해당 위치와 같음을 확인합니다.[BCG20]에서는 사용된 선형 코드의 상대 거리가 상수일 경우, 약속된 행렬이 압도적인 확률로 코드워드와 가까워진다고 증명합니다(압도적인 확률은 명제가 거짓일 확률이 무시할 수 있을 정도로 작다는 것을 의미합니다).
일관성 검증: 일관성 검증은 근접성 검증과 완전히 유사한 프로세스를 따릅니다. 다른 점은 무작위 벡터 0을 사용하지 않고 r0를 직접 사용하여 선형 조합 부분을 완료한다는 것입니다. 유사하게, c1은 메시지 y1의 선형 코드이며, (x)=\<y1,r1>입니다.[BCG20]에서는 일관성 검증을 통해 약속된 행렬이 코드워드와 가까울 경우, y=(x)가 압도적인 확률로 성립한다고 증명합니다.
의사 코드 형태로 Brakedown 프로토콜의 흐름을 제시합니다:
공개 입력: 평가 점 X, 텐서 곱으로 파싱된 X=r0r1;
비공개 입력: 다항식, 계수는 w로 표기됩니다.
C를 [n,k,d]-선형 코드로 두고, EC: FkFn을 인코딩 함수로 하며, N=kk입니다. N이 완전 제곱수가 아닐 경우, 다음 완전 제곱수로 패딩할 수 있습니다. 우리는 파이썬 스타일 표기법 mat[:,i]를 사용하여 행렬 mat의 i번째 열을 선택합니다.
함수 PC. Commit()：
w를 kk 행렬로 파싱합니다. 증명자는 로컬에서 텐서 코드 인코딩 C1, C2를 계산하며, C1은 kn 행렬이고 C2는 nn 행렬입니다.
for i [n] do
머클 트리 루트 Roott=Merkle.Commit(C2[:,i])를 계산합니다.
머클 트리 루트 R=Merkle.Commit([Root0,……Rootn-1])를 계산하고, R을 약속으로 출력합니다.
함수 PC. Prover(, X, R)
증명자는 검증자로부터 무작위 벡터 0Fk를 받습니다.
근접성: C0=i=0k-10[i]C1[:,i],y0=i=0k-10[i]w[i]
일관성: C1=i=0k-1r0[i]C1[:,i],y1=i=0k-1r0[i]w[i]
증명자는 C1,y1,C0,y0를 검증자에게 보냅니다.
검증자는 t[n]을 배열 I로 무작위 샘플링하고 이를 증명자에게 보냅니다.
for idxI do
증명자는 C1 [:,idx]와 R에 대한 C2 [:,idx]의 머클 트리 증명을 검증자에게 보냅니다.
함수 PC. VERIFY_EVAL(X,X,y=(X),R)
근접성: idxI,C0[idx]==\<0,C1[:,idx]> 및 EC(y0)==C0
일관성: idxI,C1[idx]==\<r0,C1[:,idx]> 및 EC(y1)==C1
y==\<r1, y1>
idxI, EC(C1[:,idx])는 ROOTidx와 일치하며, ROOTidx의 머클 트리 증명이 유효합니다.
모든 조건이 충족되면 accept를 출력합니다. 그렇지 않으면 reject를 출력합니다.
결론: 다항식 약속은 매우 중요한 암호학 프로토콜로, 많은 암호학 시스템에서 널리 사용되며, 특히 제로 지식 증명 시스템에서 중요합니다. 본문에서는 다항식 약속 Brakedown 프로토콜과 관련된 수학 지식을 자세히 설명하였으며, FOAKS의 중요한 하부 구성 요소로서 Brakedown은 FOAKS의 인스턴스 성능 향상에 중요한 역할을 합니다.
참고 문헌
[GLS+]:Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. Brakedown: Linear-time and post-quantum snarks for r1cs. Cryptology ePrint Archive. https://ia.cr/2021/1043.
[XZS22]:Xie T, Zhang Y, Song D. Orion: Zero knowledge proof with linear prover time[C]//Advances in Cryptology--CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15--18, 2022, Proceedings, Part IV. Cham: Springer Nature Switzerland, 2022: 299-328.https://eprint.iacr.org/2022/1010
[BCG20]:Bootle, Jonathan, Alessandro Chiesa, and Jens Groth. "Linear-time arguments with sublinear verification from tensor codes." Theory of Cryptography: 18th International Conference, TCC 2020, Durham, NC, USA, November 16--19, 2020, Proceedings, Part II 18 . Springer International Publishing, 2020.
Justin Thaler from A16zcrypto, Measuring SNARK performance: Frontends, backends, and the future
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/텐서 곱의 소개: https://blog.csdn.net/chenxy_bwave/article/details/127288938
