[ZK] STARK FRI 검증에서 Verifier는 어떻게 위조를 잡아내는가?

Zero-Knowledge 시스템인 STARK에서 핵심 기법 중 하나는 FRI (Fast Reed-Solomon IOP of Proximity)입니다. 이 과정에서 Prover는 다항식이 "저차수"라는 것을 주장하고, Verifier는 일부 정보만 확인해서 그 주장이 맞는지를 검증합니다.

하지만 저차수임을 확인하는 것이 어떻게 검증의 핵심이 될 수 있을까요? 그리고 Verifier는 다항식 전체를 알지 못하는데도, 위조된 다항식이라는 것을 어떻게 탐지할 수 있을까요?

---

핵심 개념 요약

• Verifier는 다항식 자체를 모름
• 하지만 Prover가 보낸 Merkle Tree로 커밋된 값들과
• FRI의 fold 수식 구조를 이용해 검증 가능함
• 무작위로 z를 고른 뒤, 해당 위치의 값을 확인하면 위조를 높은 확률로 탐지할 수 있음

---

사전지식

FRI에서의 folding: f₀(x)와 f₁(x)의 관계

FRI는 다항식을 반복적으로 접는(folding) 방식으로 차수를 줄여나가며 검증합니다. Prover는 다항식 $f_0(x)$를 평가하고, 이를 바탕으로 다음 단계의 다항식 $f_1(x)$를 생성합니다.

접는 방식은 다음과 같습니다:

여기서:

• $g(x)$는 $f_0(x)$의 짝수 차수 항 (even terms)으로 구성됨
• $h(x)$는 $f_0(x)$의 홀수 차수 항 (odd terms)으로 구성됨

즉, $f_0(x)$는 다음과 같이 분리될 수 있습니다:

따라서 다음의 관계가 성립합니다:

---

고정 상수 $\alpha$는 어떻게 정해지나?

$\alpha$는 각 folding 단계에서 사용되는 무작위 상수로, 보안의 핵심입니다. 이 값은 Prover가 임의로 정할 수 없고, 다음과 같은 방식으로 정해집니다:

• Verifier가 Merkle root 등의 데이터를 기반으로 해시하여 결정
• 보통 Fiat-Shamir 변환을 사용하여 다음처럼 계산:

α := hash(Merkle root of f₀)

이로써 $\alpha$는 공개되지만 Prover가 조작할 수 없는 고정값이 됩니다.

---

수식 기반 설명: Fold 구조의 검증

Prover는 다음과 같은 형태의 folding을 통해 다항식을 줄여나갑니다:

그런데 Prover가 실제로 보낸 것은 원래 다항식 $f_0(x)$의 평가값이므로, Verifier는 다음의 관계를 사용하여 $g(x^2), h(x^2)$를 계산할 수 있습니다.

검증자가 하는 일 (무작위 z 선택)

Verifier는 $z$와 $-z$ 두 점에 대해 $f_0$의 값을 요청합니다:

이제 Verifier는 다음을 계산합니다:

• $g(z^2) = \frac{f_0(z) + f_0(-z)}{2}$
• $h(z^2) = \frac{f_0(z) - f_0(-z)}{2z}$

검증

이제 Verifier는 다음을 계산합니다:

그리고 Prover가 Merkle Tree로 커밋한 $f_1(z^2)$의 값과 비교합니다.

• 값이 같으면: 통과 (그 점에서는 fold가 정당)
• 값이 다르면: Prover가 위조한 것 → 검증 실패

---

왜 이게 위조를 잡아내는가?

• Prover가 $f_0$의 값을 조작하면,
• 그 흔적이 $g, h$, 그리고 결국 $f_1$의 계산된 값에서 일관성 깨짐
• Merkle로 커밋한 값과 불일치 → 바로 탐지됨

또한 이 과정을 여러 번 반복하거나, 여러 $z$를 무작위로 선택하면:

• 위조가 들킬 확률은 지수적으로 상승
• $10%$ 정도만 조작해도, 30번만 확인하면 들킬 확률 ≈ $> 95$

---

정리

요소	Verifier가 아는가?	역할
원래 다항식 $f(x)$	모름	몰라도 됨
Merkle 루트 (커밋된 평가값들)	받음	변경 불가능한 약속
Fold 수식의 구조	알고 있음	Split-and-Fold 고정 알고리즘
무작위 $z$	Verifier가 직접 선택	검증을 랜덤화해 위조 차단
특정 $f(z), f(-z)$	요청하여 받음	Fold 검증에 사용

---

이 구조 덕분에 Verifier는 전체 다항식은 몰라도, 몇 개의 무작위 점만 확인하여 위조를 잡아낼 수 있습니다.