[ZK Study 05] STARK

omin·2025년 9월 4일

ZK Study

목록 보기

5/6

STARK

STARK(Scalable Transparent ARgument of Knowledge)는 trusted setup이 필요 없는 영지식 증명 기술이다. STARK는 타원 곡선이나 복잡한 암호화 가정을 사용하지 않고, 해시 함수와 정보 이론을 기반으로 하기 때문에 더 투명하다.

STARK는 Succinctness과 Transparency을 제공하지만, 증명 크기가 수백 킬로바이트로 ZK-SNARK보다 크다는 트레이드오프가 존재한다. 그러나 이는 신뢰가 중요한 블록체인 환경에서 매우 유용하다.

STARK는 크게 3단계를 통해서 이뤄진다. 해당 과정에 대해 알아보자.

1단계 : Arithmetization

우리가 증명하고자 하는 복잡한 계산의 무결성을 증명하기 위해, 계산 과정을 다항식으로 변환하는 Arithmetization 단계를 거친다.

Execution Trace를 통해서 머신에서 실행되는 모든 단계를 기록한다.

데이터 열(Data Columns): 각 클럭 주기에서 레지스터의 내부 상태를 기록(계산의 중간 결과값을 담는 곳)
제어 열(Control Columns): 초기화와 종료 지점을 표시하는 데 사용( 계산의 흐름을 제어)
누산기 열(Accumulator Columns): 전체 RISC Zero 프로토콜에서 메모리 에뮬레이션을 처리

그리고 각 단계에서 계산의 유효성을 검증하기 위한 규칙을 도입한다. 이는 계산 과정이 올바른지 확인하는 것이다. 각 규칙은 다항식으로 작성되고, 다항식이 만족되면 0으로 처리된다. 이러한 계산 규칙은 항상 사용되는 것이 아니라 특정 부분에서만 사용되므로 selector와 결합되어 사용된다. 예를 들어 $(s)(a+b-c)$ 를 살펴볼 때, 규칙이 적용되어 s가 1이라면, $(1)(a+b-c)$ 되어 $a+b-c=0$ 인지 확인한다. 반대로, 규칙이 적용되지 않아 s가 0이면 해당 규칙을 무시된다.

여기서 중간 결과들을 Algebraic Execution Trace(AET)라고 부르며 제약 조건들의 집합을 Algebraic Intermediate Representation (AIR)이라고 한다.

이후에 영지식 프로토콜을 구현하기 위해 증명 과정에서 사용자의 실제 데이터를 숨기기 위한 엔트로피를 추가한다.

Trace Polynomial은 실행 흔적의 데이터 열을 압축한 대수적 표현이다. INTT(Inverse Number Theoretic Transform)를 흔적 column 데이터에 실행하여 이 다항식의 계수를 얻는다

예시의 표는 8개의 column으로 구성되어 있으므로, 최대 차수가 7인 다항식이 나오고, 특정 지점에서의 평가값이 원래의 데이터와 정확히 일치한다.

Trace polynomial이 생성된 이후, 보안을 위해 더 넓은 도메인의 데이터를 활용해서 Reed-solomon encoding을 진행한다. 기존의 점들이 $5^{12∗i} \pmod{97}$ 로 이루어진 8개의 점이었다면, $5^{3∗i} \pmod{97}$
인 32개의 점으로 확대하는 저차 다항식 확장(Low-Degree Extension)을 실행한다. 이러한 Reed-solomon encoding은 중복성을 추가하여 작동한다.. 만약 원래 실행 흔적에 오류가 있었다면, 이 오류는 더 큰 점 집합에 걸쳐 증폭된다. 이는 검증자가 오류를 훨씬 쉽게 감지하게 하고 프로토콜의 건전성을 향상시킨다.

2단계: Commitment

이전 1단계에서 얻은 Trace Polynomial을 통해서 다항식이 바뀌지 않음을 증명하는 Commit을 진행해야한다. RS 확장이 영지식과 잘 작동하도록 하기 위해, 우리는 trace domain과 commitment domain이 겹치지 않도록 해야한다. 따라서 prover는 shift 연산을 통해서 각 trace polynomial을 평가한다.

이러한 shift 연산을 통해서 모든 trace 데이터를 변장한다.(숨긴다) 우리는 변장된 흔적에 대한 정보만 공개하며, 우리가 추가한 무작위 패딩은 공격자가 변장된 흔적과 실제 흔적 사이의 어떤 연결도 추론할 수 없다.

그리고 이 다항식을 Commit하기 위해 각 값들을 해시해서 머클 트리의 리프 노드로 만든다. 그리고 리프 노드들을 짝지어 연결하는 과젖을 통해 최종 머클 루트를 생성하고, 이 머클 루트를 제출해 commitment를 만든다. $d_1$ 의 경우 column에 있는 값들을 각각 해시하여 leaf로 만들어 $d_1$ 의 머클루트를 구하는 것이다.

우리는 다수의 제약 조건을 하나로 압축하여 계산 부담을 줄일 수 있다. 이를 위해, 우리는 하나의 새로운 열을 추가하여 우리의 제약 다항식을 단일한 혼합 제약 다항식(mixed constraint polynomial)으로 혼합한다.

Prover가 제어 다항식과 데이터 다항식에 대한 머클 루트를 커밋한 후, 이 머클 루트들은 엔트로피로 사용되어 무작위로 제약 혼합 매개변수 α1을 생성한다.

$c_i$ 를 제약 다항식이라고 하면, 우리는 $C(x)=\alpha_{1}^0*c_0(x)+\alpha_{1}^1c_1(x)+ \dots + \alpha_{1}^5c_5(x)$ 로 하나의 제약 다항식을 생성한다. $c_i$ 가 어떤 입력 $x$ 에서 0으로 평가된다면, C 또한 0으로 평가될 것이다.

모든 제약 조건을 만족하는 다항식을 넣었을 때, 제약 다항식의 값이 0이 되어야하기 때문에 Vanishing Polynomial(Z(x))을 만들어 몫 다항식(Q(x))를 만든다. 그럼 아래와 같은 식이 성립한다.

C(x) = Z(x) ⋅ Q(x)

이 과정을 통해 Prover는 여러개의 제약 다항식을 trace data가 만족한다는 걸 증명하는 것이 아니라, 하나의 혼합 제약 다항식이 몫 다항식으로 분리되고, 그 몫 다항식이 저차 다항식이다라는 것을 증명하는 것으로 바뀐다.

3단계: FRI

결국 우리의 목표는 $Q(x)$ 가 저차다항식이라는 것을 증명해야한다. 이를 위해 $Q(x)$ 를 Reed-solomon encoding으로 저차식 확장하여 머클트리를 만들고 특정점에서의 확인을 통해서 올바른지 확인한다.

이 과정은 크게 Commit과 Query 2단계로 구분된다.

Commit

Commit 단계에서는 “Split-and-Fold”라는 기법으로 차수를 재귀적으로 줄여가며 결국 상수항의 커밋을 제공한다.

Split의 경우에는 짝수항과 홀수항으로 쪼갠다.

만약 $f_0(x)=19+56x+34x^2+48x^3+43x^4+37x^5+10x^6+0x^7$ 라는 식을 Split한다고 할 때, 짝수와 홀수 차수를 가진 것들나눈다.

$f_{0,even}(x)=19+34x+43x^2+10x^3$

$f_{0,odd}(x)=56x+48x^3+37x^5+0x^7$

그리고 이후에 Fold 과정을 거친다. 이 식을 $f_{0,mid}= 19+34x^2+43x^4+10x^6 + x(56+48x^2+37x^4+0x^6)$ 으로 합친다.

그 후 어떤 x 대신에 random한 값 r을 사용해서 두 식을 하나의 식으로 합쳐서 $f_1$ 을 생성한다.

$f_1(x)=f_e(x^2)+r⋅f_o(x^2)$

$f_1(x) = 19+34x+43x^2+10x^3 + 12⋅(56+48x+37x^2+0x^3)$

$f_1(x)=12+28x+2x^2+10x^3$

최종적으로 Split-and-Fold를 거치면서 차수가 원래보다 1/2이 된 것을 확인할 수 있다.

이 과정을 결과가 상수항이 나올 때까지 진행한다.

Query

Verifier는 무작위로 지점( $g$ )를 선택하여 prover에게 각 라운드의 다항식 평가값( $f_i(g^{2^i}),f_i(−g^{2^i})$ )을 요청한다. Verifier는 locality라는 핵심 속성을 활용하여, 한 라운드의 평가값이 이전 라운드의 두 평가값과 일관적인지 확인한다. 즉, $f_i(x^2)$ 가 $f_{i-1}(x)$ 와 $f_{i-1}(-x)$ 로 계산한 값과 같은지 비교한다.

{f_i(x^2) = \frac{r_i + x}{2x} f_{i-1}(x) + \frac{r_i - x}{2(-x)} f_{i-1}(-x)}

만약 모든 지점에서 일관성이 확인되면, 검증자는 ACCEPT한다. 단 한 번이라도 불일치가 발견되면 REJECT한다.

STARK의 활용

STARKnet

STARKnet은 복잡한 계산을 이더리움 메인넷에서 분리하여 실행함으로써 이더리움의 확장성을 높이는 레이어 2 솔루션이다. 특히, STARKnet은 ZK-Rollup이라는 기술을 사용하여 이더리움의 확장성 문제를 해결한다.

ZK-Rollup은 수많은 오프체인 트랜잭션을 하나로 묶어, 그 유효성을 수학적으로 증명하는 영지식 증명(ZK-Proof)을 생성하여 온체인에 제출하는 기술이다. STARKnet은 이 영지식 증명을 생성하기 위해 STARK 기법을 사용한다.

STARKnet에서 STARK의 사용

STARKnet은 트랜잭션을 처리하고 증명을 생성하는 데 다음과 같은 방식으로 STARK 기술을 사용한다.

계산의 다항식화: STARKnet은 수십만 건의 트랜잭션과 그 실행 과정을 대수적 실행 추적(AET)이라는 데이터 목록으로 변환한다. 이 AET는 다시 하나의 거대한 추적 다항식으로 변환된다.
논리적 증명: 추적 다항식이 트랜잭션 규칙(제약 조건)을 올바르게 따랐는지 확인하기 위해, STARK는 $c(x) = Z(x) ⋅ q(x)$ 와 같은 다항식 등식으로 논리를 검증한다.
효율적인 압축: STARKnet의 핵심은 이 모든 계산을 매우 간결한 증명으로 압축하는 것이다. 여기서 Split-and-Fold와 Reed-Solomon 기법이 활용됩니다.

Reed-Solomon과 Split-and-Fold의 활용

Reed-Solomon: 오류 증폭과 확률적 검증

STARKnet은 수십만 건의 트랜잭션에 대한 추적 다항식을 생성한다. 만약 트랜잭션 중 단 하나라도 오류가 있다면, 그 오류는 다항식 전체에 걸쳐 오류 증폭을 일으킨다. Reed-Solomon의 원리는 이 증폭된 오류를 감지하는 데 사용된다.

검증자는 수십만 개의 트랜잭션이 담긴 다항식의 모든 지점을 확인할 필요 없이, 무작위로 소수의 지점(예: 16개)만 검사한다. 만약 이 지점들 중 하나라도 오류가 있다면, 전체 계산이 잘못되었음을 높은 확률로 확신할 수 있다.

Split-and-Fold: 다항식의 차수 감소

STARKnet에서 트랜잭션의 수가 늘어날수록 다항식의 차수는 기하급수적으로 커진다. Split-and-Fold는 이 거대한 다항식의 차수를 획기적으로 줄여 검증을 간결하게 만든다.

Split-and-Fold는 추적 다항식의 차수를 매 라운드마다 절반씩 줄여나갑니다. 이 과정을 반복하여 원래의 복잡한 다항식을 최종적으로는 매우 낮은 차수의 다항식으로 압축합니다. 검증자는 이 최종 다항식만 확인하면 되므로, 검증에 필요한 시간과 자원이 획기적으로 줄어듭니다.

StarkWare의 StarkEx 플랫폼을 통해 구현된 프로젝트

dYdX

dYdX는 이더리움 기반의 탈중앙화 파생상품 거래소. 거래량이 매우 많고 빠른 처리가 필수적인 서비스

STARK 활용: dYdX는 StarkEx를 이용해 오프체인에서 모든 거래를 처리하고, 그 유효성을 STARK 증명으로 묶어 이더리움에 정산한다다. 이를 통해 수십만 건의 거래를 낮은 비용으로 빠르게 처리할 수 있다.

Immutable X

Immutable X는 이더리움에서 NFT(대체 불가능 토큰) 및 웹3 게임을 위한 확장성 솔루션

STARK 활용: Immutable X는 STARK를 활용해 사용자들이 수수료(gas fee) 없이 NFT를 민팅하고 거래할 수 있도록 한다. 수많은 민팅 및 거래 데이터를 하나의 STARK 증명으로 압축하여 이더리움에 제출함으로써, 네트워크 혼잡을 피하고 대규모 게임 경제를 가능하게 한다.

Sorare

Sorare는 유명 축구선수 NFT를 기반으로 한 판타지 스포츠 게임이다.