[ZK Study 06] DEEP-FRI

STARK는 “특정 다항식이 낮은 차수(low-degree)를 갖는다”를 “함수가 reed-solomon code에 가깝다”라는 수학적 증명으로 변환한다. 이러한 변환을 통해 “거리 확인”을 통해서 Accept/Reject을 구분한다. STARK는 FRI를 통해서 효율적으로 낮은 차수임을 증명하는데 이를 더 발전시킨 DEEP-FRI에 대해 알아보자.

Maximum distance vs average distance to a linear code

영지식 증명 시스템의 핵심 목표는 증명자가 거짓말을 할 때 이를 잡아내는 것이다. 증명자가 제출한 데이터가 저차항 다항식에 가깝다고 주장하지만 실제로는 멀리 떨어져 있을 수 있다. 이때 검증자는 무작위로 한 지점을 선택하여 이 주장이 사실인지 검사한다. 만약 무작위로 선택된 지점이 코드에서 멀리 떨어져 있다면, 증명자는 올바른 답변을 줄 수 없으므로 거짓말이 들통난다.

기존 방식에서는 데이터가 코드에서 멀리 떨어져 있더라도, 무작위 변형들의 평균 거리가 생각보다 가까울 수 있다. 그러면 검증자가 운 좋게 코드에 가까운 지점을 선택할 가능성이 생겨, 거짓말하는 증명자가 들통나지 않을 수 있다. 그러나 DEEP 기법은 무작위 변형들의 평균 거리($E[δ_x]$)가 최악의 경우($δ_{max}$)와 거의 같은 수준으로 멀리 떨어져 있음을 증명한다. 이로써 부적절한 식에 대해서 Verifier가 어떤 무작위 지점을 선택하든, 그 지점은 코드에서 멀리 떨어져 있을 확률이 매우 높아진다.

결론적으로, '평균 거리가 최대 거리에 가깝다'는 것은 거짓말을 잡아내는 테스트의 건전성(soundness)이 매우 높다는 것을 의미한다.

Domain Extension for Eliminating Pretenders (DEEP)

기존 영지식 증명 시스템에서 증명자는 자신이 가진 데이터가 "특정 규칙을 따르는 저차항 다항식"의 평가값이라고 주장한다. 하지만 증명자가 거짓말을 할 경우, 즉 데이터가 실제로는 저차항 다항식과 거리가 먼 경우라도 검증자가 이를 쉽게 알아채지 못할 수 있다.

검증자는 다항식의 원래 평가 도메인 $D$보다 더 큰 $\overline{D}$를 인위적으로 생성한다. 검증자는 이 확장된 도메인 $\overline{D}$에서 무작위로 점 z를 선택하고, 증명자에게 해당 지점에서의 다항식 평가값을 요청한다.

증명자가 답변을 제공하면, 검증자는 이 정보를 이용해 거짓말을 하는 증명자들이 내놓을 수 있는 '가짜' 다항식 목록을 정리(prune down)한다. 이 과정을 통해 증명자가 주장하는 다항식이 정말로 저차항 다항식에 가까운지, 아니면 거짓말인지 훨씬 더 쉽게 구별할 수 있게 된다.(가짜 다항식에 해당 prover가 보낸 다항식이 없으면 통과)

그러나 실제 증명 시스템에서는 이 "목록 정리"를 수학적으로 엄밀하게 증명해야 한다. 여기서 '거리 보존'과'가중 버전' 같은 개념이 등장한다. 이는 "목록을 정리했다"는 직관을 "거짓 다항식이 올바른 코드에서 여전히 멀리 떨어져 있음($δ_{max}$)"이라는 정량적이고 증명 가능한 사실로 변환하는 과정이다.

DEEP 기법의 핵심 논리는 다음과 같다.

DEEP 기법은 증명자가 제출한 함수($u^∗,u$)가 올바른 다항식이 아니라고 가정하는 것에서 시작된다. 이러한 경우, $u^*$와 $u$는 다항식 코드에서 멀리 떨어져 있다. 이 문제를 해결하기 위해, 검증자는 원래 도메인 밖의 점 $z$를 질의하여, 증명자의 답변과 일치하는 '가짜' 다항식들을 줄여 나간다. 이 정리 과정이 ‘거리 보존’으로 이어진다. 즉, 몫 연산과 같은 연산을 통해 얻은 새로운 함수($u_x$)는 여전히 올바른 코드에서 멀리 떨어져 있다. 여기서 이 거리가 얼마나 멀리 떨어져 있는지는 '1.5-존슨 함수'로 정량화된다.

이러한 DEEP 기법의 원리는 다양한 상황에 맞게 확장되어 실용성을 높인다. weighted version과 general linear codes이 그 방법이다. weighted version은 모든 데이터 지점이 동일한 중요도를 갖지 않는 실제 시나리오에서도 작동함을 보여준다. 또한 general linear codes은 리드-솔로몬 코드에만 국한되지 않고, 더 넓은 범위의 코드에 적용될 수 있음을 증명한다.

DEEP-FRI

DEEP-FRI에 대해 공부하기 전에 FRI를 다시 한번 짚고 넘어가 보자.

FRI

FRI는 차수를 줄이는 과정(COMMIT 단계)와 그 결과가 정확한지 확인하는 과정(QUERY 단계)으로 구성된다.

COMMIT 단계

Prover와 Verifier가 여러 라운드에 걸쳐 상호작용하며 문제를 점진적으로 축소하는 과정이다. Prover는 $f^{(0)}$라는 함수가 리드-솔로몬 코드에 가깝다고 주장하며, Verifier는 이를 검증하기 위해 무작위 값 $x^{(i)}$를 보낸다. Prover는 이 값을 이용해 $f^{(i)}$를 '대수적 해시'하여 새로운 함수 $f^{(i+1)}$을 만든다. 이 과정은 다항식의 차수와 데이터 크기를 절반으로 줄이며, 여러 라운드 반복을 통해 복잡한 문제를 상수 크기의 간단한 문제로 축소한다.

STARK에서는 이러한 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$ (mod 97)

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

QUERY 단계

COMMIT 단계에서 다항식 $f^{(0)}$를 'Split-and-Fold'를 통해 $f^{(1)}, f^{(2)}, ...$로 변환한 것이 올바른지 검증자는 확인해야 한다. 검증자는 프로토콜의 locality 속성을 사용하여 이를 수행한다

1. 무작위 지점 선택: Verifier는 $L(0)$ 도메인에서 $s(0)$라는 무작위 지점을 선택한다.
2. 폴딩 경로 추적: Verifier는 이 $s(0)$를 사용하여 COMMIT 단계에서 일어난 폴딩 과정을 역으로 추적한다.
3. 정확성 검증:
   • 검증자는 $f^{(i)}$에 대한 두 번의 질의를 통해 $H_x[f(i)](s(i+1))$ 값을 직접 계산한다.
   • 그리고 증명자가 제출한 $f(i+1)$의 값($f(i+1)(s(i+1))$)과 자신이 계산한 값이 일치하는지 비교한다.
   • 만약 단 한 번이라도 불일치가 발생하면, 검증자는 REJECT한다. 모든 라운드의 검사를 통과하면 ACCEPT한다.
     

이 과정을 통해 검증자는 매 라운드마다 증명자가 올바른 다항식 폴딩을 수행했는지를 효과적으로 확인할 수 있다.

DEEP-FRI

DEEP-FRI는 기존 FRI 프로토콜에 몫 연산(quotienting)이라는 새로운 개념을 도입하여 건전성(soundness)을 개선한 프로토콜이다.

몫 연산 (Quotienting)

몫 연산은 특정 지점에서 특정 값을 가지는 다항식에 초점을 맞추는 연산이다. 함수 f가 주어졌을 때, 몫 연산은 z에서 b 값을 갖는 새로운 함수 $g(y) = \frac{f(y)-b}{y-z}$를 정의한다.

보조정리 5.3

$L⊆F_q$이고, $z∈F_q$이며 $z∉L$이라고 하자.

$d≥1$은 정수라고 하자.

함수 $f:L→F_q$이고 $b∈F_q$라고 하자. $g = QUOTIENT(f, z, b)$라고 하자. 다음은 동치(equivalent)이다.

위의 정리는 다음과 같은 사실을 보장한다.

• $Δ(g,Q)<δ$(차수 d−1 이하의 다항식 Q가 g와 가깝다면), 차수 d 이하의 다항식 R이 존재하여 f와 가깝고 $R(z)=b$를 만족한다.
• 반대로, $Δ(f,R)<δ(R(z)=b$를 만족하는 차수 d 이하의 다항식 R이 f와 가깝다면), $Q=(R−b)/Z$로 정의된 다항식 Q는 g와 가깝다.

DEEP-FRI의 방식도 FRI와 대부분의 과정이 유사한다. 그런데 DEEP 기법을 사용하기 때문에 살짝의 차이가 있는데 어느 부분이 차이가 있는지 살펴보자.

COMMIT 단계

기존 FRI 프로토콜은 Prover가$f^{(0)}$가 리드-솔로몬 코드에 가깝다고 주장하면, Verifier가 무작위 값 $x^{(i)}$를 보내고 Prover가 이를 이용해 $f^{(i+1)}$를 만들어 문제를 점진적으로 축소한다.

하지만 DEEP-FRI는 이 과정에 다음 단계를 추가한다.

1. '도메인 밖' 질의: Verifier는 다항식의 원래 평가 도메인 밖의 무작위 지점 $z^{(i)}$를 샘플링하고, Prover에게 해당 다항식의 평가값을 요청한다.
2. 몫 연산 적용: Verifier는 검증자가 보낸 $x^{(i)}$와 $z^{(i)}$를 이용하여, 몫 연산을 적용한 새로운 함수 $f^{(i+1)}$를 작성한다. 이 함수는 $QUOTIENT(H_{x^{(i)}}[f^{(i)}], z^{(i)}, B^{(i)}_{z^{(i)}}(x))$와 같다고 추정되는 함수이다.
3. '악의적인 prover' 제거: 이 몫 연산은 가짜 다항식 목록을 걸러내는(prune down) 역할을 한다. 증명자가 거짓말을 하고 있다면, 도메인 밖의 지점 $z^{(i)}$에서 올바른 값을 제공하는 가짜 다항식은 극히 드물다.

이 과정을 통해 DEEP-FRI는 차수를 줄이기 전에 거짓 증명을 선제적으로 제거하여, FRI 프로토콜의 건전성을 획기적으로 향상시킨다.

이를 포함한 전체적인 COMMIT 과정을 정리하면 다음과 같다.

1. Split-and-Fold (대수적 해시 생성):

   Prover는 $f^{(i)}$를 짝수 차수 항과 홀수 차수 항으로 분리한다. Verifier가 보낸 무작위 값 $x^{(i)}$를 사용해 이 두 다항식을 하나로 합칩니다(Fold). 이 Split-and-Fold 과정을 거쳐 생성된 다항식이 바로 대수적 해시 함수 $H_{x^{(i)}}[f^{(i)}]$이다.

2. DEEP 기법 적용 (몫 연산):

   $H_{x^{(i)}}[f^{(i)}]$라는 단일 다항식이 생성된 후, DEEP 기법이 적용된다. Verifier는 다항식의 원래 평가 도메인 밖의 무작위 지점 $z^{(i)}$를 선택하고, 증명자에게 $H_{x^{(i)}}[f^{(i)}](z^{(i)})$의 값을 요청한다. Prover는 이 정보를 바탕으로 몫 연산(QUOTIENT)을 적용하여, 거짓 증명을 걸러낸 새로운 다항식을 만든다.

3. 다음 라운드 다항식 생성:

   몫 연산의 최종 결과물이 다음 라운드에서 사용될 다항식 $f^{(i+1)}$이 된다.

QUERY 단계

COMMIT 단계에서 제출된 함수들이 올바르게 '몫 연산'을 거쳤는지 확인하는 과정이다. 검증자는 보조정리 5.3을 기반으로 대수적 해시와 몫 연산의 관계를 검증한다.

1. 무작위 지점 선택: 검증자는 $L^{(0)}$ 도메인에서 무작위 지점 $s^{(0)}$를 선택한다.

2. 계산 경로 추적: 검증자는 각 라운드 i마다 $s^{(i+1)}$를 계산한다. 그리고 $f^{(i)}$에 대한 2번의 질의를 통해 $H_x[f^{(i)}](s^{(i+1)})$ 값을 직접 계산한다.

3. 몫 연산 검증: 검증자는 $H_x[f^{(i)}]$에 몫 연산을 역으로 적용한 값과 증명자가 제출한 $f^{(i+1)}$ 값이 일치하는지 확인한다.

   이 검증 과정은 FRI 프로토콜의 국소성(locality)과 몫 연산(quotienting)이라는 두 가지 핵심 원리에 기반을 둔다.

   $H_x[f^{(i)}](s^{(i+1)}) ? = f^{(i+1)}(s^{(i+1)}) * (s^{(i+1)}-z^{(i)}) + B^{(i)}[z^{(i)]}(x^{(i)})$
   • 우변 : 증명자가 제출한 값에 몫 연산을 역으로 적용한 결과이다.
   • 좌변 : 검증자가 직접 계산한 $H_x[f^(i)]$의 값.
   • 만약 두 값이 일치하지 않으면, 이는 증명자가 몫 연산을 올바르게 적용하지 않았음을 의미하므로, 검증자는 거부(REJECT)한다.

   이처럼 극소적 일관성만을 활용해서 전체 거리를 확인할 수 있는 이유는 극소적 확인이 전체 속성인 거리 보존을 확률적으로 보장하기에 충분하기 때문이다. 만약 Prover가 속이기 위해 나쁜 다항식을 제공했다면, COMMIT과정을 거치면서 다항식이 많이 변하기 때문에 높은 확률로 원래의 코드에서 멀리 떠러져도록 설계된다.

DEEP-FRI Analysis

• 완전성(Completeness): 증명자가 정직하게 올바른 다항식을 제출하면, 검증자는 확률 1로 수락(ACCEPT)한다.
• 효율성: DEEP-FRI는 기존 FRI의 효율성을 그대로 유지한다.
  • 증명자 복잡도: O(n) 산술 연산
  • 검증자 복잡도: O(logn) 산술 연산
• 건전성(Soundness): 만약 증명자가 거짓말을 해서 $f^{(0)}$가 리드-솔로몬 코드에서 멀리 떨어져 있다면, 검증자는 높은 확률로 이를 감지하고 거부(REJECT)한다.
  • 오류 확률: 검증자가 거짓 증명을 수락할 확률(errQUERY)은 매우 낮으며, $(1−δ^∗+(logn)⋅ϵ)ℓ$로 표현된다. 여기서 $\delta^*$는 실제 거리이고, ℓ은 반복 횟수이다.

DEEP 기법을 통해 건전성 오류(err)를 획기적으로 낮췄다는 것이 중요하다. DEEP-FRI는 one-and-a-half-Johnson Function을 활용한 ‘존슨 경계’를 사용하여, 거짓 증명에 대한 수락 확률을 $(max(1−δ(0),ρ)+o(1))^ℓ$까지 낮출 수 있다.

DEEP-ALI

DEEP 기법을 대수적 연결 IOP(ALI) 프로토콜에 적용하여 건전성을 개선하는 방법이다.

영지식 증명 시스템은 복잡한 계산 문제를 다항식의 근접성 문제로 변환한다(Arithmetization). 이러한 변환의 목표는 거짓된 입력에 대해(거짓된 prover에 대해) 다항식이 코드로부터 매우 멀리 떨어져 있음을 보장하는 것이다. 이러한 간극($γ)$이 클수록, FRI와 같은 근접성 프로토콜의 건전성이 높아진다.

그런데 기존의 ALI 프로토콜은 이 근접성 간극($γ$)이 1/8보다 작다. 이 간격이 작으면 거짓 증명을 잡아내기 어려워지므로 이를 좀 더 키우는 것이 필요하다.

DEEP-ALI는 기존의 ALI가 가지는 한계를 “몫 연산(quotienting)”을 활용하여 해결한다. 프로토콜의 전체적인 진행 과정을 다음과 같다.

1. 증명자 입력: Prover는 증인 다항식의 평가값인 함수 $f$를 제출한다.
2. 무작위 계수: Verifier는 무작위 계수 α를 증명자에게 보낸다.
3. 제약 함수 생성: Prover는 $α$와 $f$를 이용해 제약 조건들을 결합한 새로운 함수 $g_α$를 생성한다.
4. '도메인 밖' 질의: 검증자는 무작위 값 $z$를 선택하여 $f$의 평가값과 $g_α$의 추정값 $b_{\alpha,z}$를 요청한다.
5. 몫 연산: 검증자는 몫 연산을 적용하여 새로운 함수 $h_1$과 $h_2$를 만든다.
6. 근접성 테스트: 검증자는 RPT(리드-솔로몬 근접성 테스트) 프로토콜을 사용하여 $h_1$이 $RS[F_q, D, \dots]$에 가깝고, $h_2$가 $RS[F_q, D', \dots]$에 가깝다는 것을 증명한다

DEEP-ALI의 속성

DEEP-ALI는 기존 ALI 프로토콜에 비해 여러 가지 이점을 제공한다.

• 건전성: 기존 ALI 프로토콜의 근접성 간극(proximity gap)은 1/8보다 작았지만 , DEEP-ALI는 몫 연산을 통해 이 간극을 $1−ρ$까지 향상시킨다.
  
• 질의 복잡도: 검증자가 질의하는 필드 원소의 수가 $∣M∣[citestart]⋅Q$에서 $O(∣M∣+Q)$로 줄어들어 효율성이 향상된다.
• 검증자 복잡도: 검증자의 산술 복잡도가 $\Omega(Q \cdot T_{arith})$에서 $O(Q+T_{arith})$로 개선된다.

Reference

DEEP FRI