[ZK] Stark - Split-and-Fold

STARK (Scalable Transparent ARguments of Knowledge)의 핵심기법 중 하나는 Split-and-Fold입니다. Split-and-Fold를 간단한 예제와 함께 찍먹해봅시다.

---

1. 왜 "저차수 다항식"인지 확인해야 하나?

STARK에서 Prover는 어떤 계산이 정확하다는 것을 Verifier에게 증명합니다. 이때 핵심 아이디어는:

"이 계산의 결과들을 저차수 다항식으로 표현할 수 있다면, 계산이 맞았다고 믿을 수 있다."

즉, Prover는 다항식 $f(x)$를 직접 보내는 대신, 다항식의 평가값만을 보냅니다. Verifier는 이 값들이 정말로 degree ≤ d 인 다항식에서 유도된 것인지 확인해야 합니다.

---

2. Split-and-Fold (FRI) 기법이란?

이 검증을 위해 STARK에서는 **FRI (Fast Reed-Solomon IOP of Proximity)**라는 프로토콜을 사용하고, 그 핵심이 바로 Split-and-Fold입니다.

아이디어:

다항식을 평가한 벡터를 반복적으로 반으로 줄이며, 차수를 절반씩 감소시켜 마지막에는 상수 하나만 남게 한다. 그러면 원래 다항식도 저차수였음을 확인할 수 있다.

과정:

1. Prover는 다항식 $f(x)$의 평가값을 도메인 $D = \{x_0, ..., x_{n-1}\}$에서 계산한다.
2. 평가값 벡터를 절반으로 나누고, Verifier가 고른 무작위 숫자 $\alpha$로 다음을 계산한다:
   $\text{folded}[i] = f[i] + \alpha \cdot f[i + n/2]$
3. 이 과정을 반복하면 벡터 길이는 N → N/2 → N/4 → ... → 1 로 줄어들고, 결과적으로 상수 하나가 남는다.
4. 이 모든 과정에서 Merkle Tree로 커밋(commit)하며 Verifier는 일부 위치만 무작위로 열어 확인한다.

---

3. 예제 (간단한 수치로 설명)

다항식: $f(x) = x^2$

도메인: $x = 0, 1, 2, 3$

평가값: $f(0)=0, f(1)=1, f(2)=4, f(3)=9$

무작위 $\alpha = 2$ 선택 시:

$\text{folded}[0] = 0 + 2\times4 = 8$
$\text{folded}[1] = 1 + 2\times9 = 19$

→ 새로운 벡터: [8, 19]

이 벡터가 1차 다항식의 평가값처럼 보이면 OK!
다시 한 번 Fold → 상수 → 검증 완료!

---

4. 다항식 커밋 과정

Prover가 다항식을 Verifier에게 증명하려면 다음을 합니다:

Step-by-step:

1. 다항식을 도메인 D에 평가: $[f(x_0), ..., f(x_{n-1})]$
2. 이 벡터를 Merkle Tree에 넣고 루트만 Verifier에 전달
3. Verifier는 무작위로 몇 개의 위치를 지정하고 "이 값이 진짜냐"를 확인
4. Prover는 해당 값과 Merkle proof(경로)를 제공

왜 Merkle Tree?

• 투명성: trusted setup 필요 없음
• 효율성: proof는 로그 크기
• 보안성: 일부만 확인해도 전체 위조를 걸러낼 수 있음

---

5. 검증 과정의 효율성은 어떻게 개선되었는가?

STARK는 대규모 계산도 짧은 증명과 빠른 검증으로 처리할 수 있게 설계되었습니다.
이 효율성은 다음과 같은 핵심 기법에서 나옵니다:

① FRI 기반 서브선형 검증

Verifier는 전체 다항식이 아닌 일부 무작위 위치만 검증함으로써
$O(n)$ 대신 $O(\log n)$ 수준의 계산만으로도 정당성을 확인할 수 있습니다.

② Merkle Tree 커밋

모든 평가값 대신, Merkle Tree 루트 하나만으로 전체를 커밋할 수 있어
통신량과 저장공간을 획기적으로 줄일 수 있습니다.

정리

• STARK의 핵심은 "계산 결과가 저차수 다항식 평가값"이라는 것
• 이를 위해 Split-and-Fold(FRI)를 이용해 반복적으로 다항식을 줄여나감
• Merkle Tree를 통해 평가값을 감추면서도 검증 가능하게 커밋

이 과정을 통해 Verifier는 일부 정보만 확인해도 전체 계산의 정당성을 확신할 수 있습니다.

Low Degree Testing
Cryptography 101: STARKs