---
layout: post

title: "STIR: Reed-Solomon Proximity Testing with Fewer Queries"

date: 2024-07-26

author: rkm0959
---

# 소개

이 글은 https://eprint.iacr.org/2024/390.pdf에 대해서 설명합니다.

STIR의 목표는, Reed-Solomon Code와의 Proximity Testing을 최소한의 query로 하는 것입니다. 동일한 문제를 푸는 알고리즘 중 가장 잘 알려진 FRI는, degree $d$ 문제를 $\lambda$-bit security를 갖게 해결하기 위하여 query를 $\mathcal{O}(\lambda \log d)$개 사용합니다. STIR는, 그에 비해 $\mathcal{O}(\log d + \lambda \cdot \log \log d)$만큼의 query를 사용하여, 더 적은 query를 사용하게 됩니다. query의 개수는 STARK proof의 크기와 연결되어 있기 때문에, FRI를 STIR로 대체하여 STARK의 proof size 및 verifier time을 줄일 수 있습니다. STIR의 argument size는 FRI에 비해 (파라미터에 따라서) 대략 1.25x에서 2.46x 정도의 개선을 보인다고 합니다. STARK의 proof size를 줄일 수 있다는 점은, 다르게 말하면 Recursive STARKs의 overhead 역시 감소한다는 의미를 갖습니다. 이런 점에서 STIR는 FRI의 direct replacement로 작동할 수 있을 것으로 예상됩니다. 이 논문은 2024년 CRYPTO에서 Best Paper Award를 받기도 했으며, 현재 FRI를 사용하고 있는 ZKP 팀들은 대부분 STIR에 큰 관심을 보이고 있습니다.

STIR 논문은 Polynomial IOP를 Reed-Solomon Proximity Test를 통해서 IOP로 compile 하는 새로운 방법에 대해서도 다루지만, 이에 대해서는 생략하도록 하겠습니다. 간단하게 소개하자면, round-by-round knowledge soundness를 높게 가져가는 새로운 compiler를 만들고, R1CS를 위한 IOP를 compile 하는 방법을 소개합니다.

STIR 논문의 또다른 중요한 기여는 batch degree correction입니다.

이는, $f_1, f_2, \cdots, f_m: \mathcal{L} \rightarrow \mathbb{F}$와 $d_1, d_2, \cdots, d_m, d^\star$가 있어 $d^\star \ge d_i$이라 합시다.

batch degree correction은 적당한 $f^\star: \mathcal{L} \rightarrow \mathbb{F}$를 찾아 다음이 성립하도록 하는 것입니다.
- 만약 $f_i \in \text{RS}[\mathbb{F}, \mathcal{L}, d_i]$가 전부 성립한다면, $f^\star \in \text{RS}[\mathbb{F}, \mathcal{L}, d^\star]$.
- 만약 하나의 $f_i$라도 $\text{RS}[\mathbb{F}, \mathcal{L}, d_i]$와 $\delta$-far 하다면, $f^\star$도 $\text{RS}[\mathbb{F}, \mathcal{L}, d^\star]$와 $\delta$-far.

즉, batch testing을 하되, 각 함수의 목표 degree가 다른 경우를 다룹니다. $d_i$들이 전부 동일한 경우는 일반적인 batch test와 같고, 이는 correlated agreement에 대한 여러 논문에서 이미 다루었습니다. 예를 들어, $\delta \in (0, 1 - \sqrt{\rho})$에 대해서 풀림이 이미 알려져 있습니다. 이 논문은 $\delta \in (0, \min (1 - \sqrt{\rho}, 1 - (1 + 1/d^\star) \cdot \rho))$에 대하여 $f^\star$를 잡는 법을 다루며, 특히 $f^\star$의 evaluation은 $f_i$들의 evaluation을 알 때 $\mathcal{O}(m \log d^\star)$에 계산할 수 있음을 증명합니다. 최종 error term도 [BCIKS20]의 그것과 비슷합니다.

degree batching은 경우에 따라 매우 유용하게 쓰일 수 있으니, 이 역시 매우 중요한 기여라고 볼 수 있습니다.

이제부터 $\text{err}(d, \rho, \delta, l)$을 [BCIKS20]의 (Theorem 1.2, Johnson Bound) error term으로 정의하겠습니다.

# STIR: Overview

먼저 folding parameter $k \ge 4$ (power of 2) 를 잡고, 각 round에 대한 repetition parameter $t$를 잡습니다. 각 round는 domain $\mathcal{L}$의 크기를 절반으로 줄이고, degree $d$를 $d/k$로 줄입니다. 기존 FRI의 경우에는 $d/2$로 줄이는 것에 비해, 여기서는 $d / k$로 줄입니다. 이 말은 code의 rate가 $2/k$배 씩 감소한다는 말이고, 즉 가면 갈수록 Proximity Testing이 쉬워짐을 의미합니다. STIR는 $d$를 $\mathcal{O}(1)$로 줄이기 위해 $M = \mathcal{O}(\log_k d)$개의 round를 사용하고, 각 round 마다 repetition parameter $t_i$가 있다면 $t_0 \ge t_1 \ge \cdots \ge t_M$이 성립하게 됩니다. 이는 rate가 점점 감소하게 되어 repetition이 적게 필요함을 의미합니다. 마지막 단계에서는 $d = \mathcal{O}(1)$이 되므로, 전체 polynomial을 아예 보낸 후 $t_M$개의 점에서 evaluation을 받아 polynomial과 그 값을 비교하여 Proximity Testing을 할 수 있게 됩니다. STIR는 distance amplification 성질도 갖는데, 시작 시점에서 $\delta$-far 하다면, $(1 - \delta)^t$ 확률을 제외하고 새 함수는 $1 - \sqrt{\rho'}$-far 하게 됩니다. 여기서 rate 감소 성질에 따라 $\rho' = (2/k)\rho$가 성립합니다.

$\rho_i$가 $\text{RS}[\mathbb{F}, \mathcal{L}_i, d/k^i]$의 rate라고 하면, 각 round의 round-by-round soundness error는 최대

$$\epsilon = \max \left\{ (1 - \delta)^{t_0}, \rho_1^{t_1/2}, \rho_2^{t_2/2}, \cdots, \rho_M^{t_M / 2} \right\}$$

입니다. 이를 감안하여, $2^{-\lambda}$ round-by-round soundness error를 원한다면,

$$t_0 = \frac{\lambda}{-\log(1 - \delta)}, \quad t_i = \frac{\lambda}{-\log \sqrt{\rho_i}}$$

가 되어, $\rho_i = (2/k)^i \rho$임을 감안하여 계산하면

$$t_i = \frac{2 \cdot \lambda}{i \log (k/2) - 2 \log \sqrt{\rho}}$$

를 얻어, 전체 query complexity는

$$\sum_{i=0}^M t_i = \mathcal{O}_k \left(\log d + \lambda \cdot \log \left( \frac{\log d}{\log 1/\rho} \right) \right)$$

가 됩니다. STIR의 강점 중 하나는, 분석하는 과정에 있어서 각 round를 독립적으로 봐도 된다는 사실입니다.

이제 각 round의 각 iteration을 생각해봅시다. 결국, $\text{RS}[\mathbb{F}, \mathcal{L}, d]$에서 $\text{RS}[\mathbb{F}, \mathcal{L}', d/k]$로 가는 것이 목표입니다.

일단, $\mathcal{L} = \langle \omega \rangle$, $\mathcal{L}' = \omega \cdot \langle \omega^2 \rangle$인 경우를 생각합시다. 목표를 위해 두 가지 테크닉이 필요합니다.

**Folding Codewords**: $f: \langle \omega \rangle \rightarrow \mathbb{F}$를 $r \in \mathbb{F}$에서 fold 한다는 것은, $f_r = \text{Fold}(f, r) : \langle \omega^k \rangle \rightarrow \mathbb{F}$를 정의하는 것입니다. $x \in \langle \omega^k \rangle$에 대해서 $p$를 $p(y) = f(y)$가 $y^k = x$를 만족하는 모든 $y \in \langle \omega \rangle$에 대해서 성립하는 $\deg p < k$인 다항식일 때, $f_r(x) = p(r)$입니다. 이는 FRI에서부터 사용되어온 전형적인 기술입니다.

다음이 성립함을 증명할 수 있습니다.
- $f \in \text{RS}[\mathbb{F}, \langle \omega \rangle, d]$면 $f_r \in \text{RS}[\mathbb{F}, \langle \omega^k \rangle, d/k]$
- $f$가 $\text{RS}[\mathbb{F}, \langle \omega \rangle, d]$에서 $\delta$-far면 매우 높은 확률로 $f_r$ 역시 $\text{RS}[\mathbb{F}, \langle \omega^k \rangle, d/k]$에서 $\delta$-far. 단, $\delta \in (0, 1 - \sqrt{\rho})$.
- $f_r(x)$의 계산을 위해서, $f$의 evaluation access는 $k$번 필요함. 다만, 이 $k$개는 하나의 "묶음"으로 볼 수 있으니, 사실상 merkle proof 하나로 $k$개의 evaluation access를 동시에 할 수 있음.

이를 증명해봅시다. FRI의 그것과 매우 비슷하지만, 완전성을 위해 증명해보겠습니다. 세 번째 사실은 자명합니다.

첫 번째 사실은, $f$를 degree $k$짜리 block으로 쪼개서

$$f(y) = \sum_{i=0}^{d/k - 1} f_i(y) \cdot (y^k)^i$$

라고 쓰면 자명해집니다. $y^k = x$인 $y$들만 모았다면, 결국

$$f(y) = \sum_{i=0}^{d/k - 1} f_i(y) \cdot x^i$$

이고 후자는 $y$로 봤을 때 degree $k$ 미만이므로, 이는

$$p(r) = \sum_{i=0}^{d/k - 1} f_i(r) \cdot x^i$$

를 의미하며, 결국

$$f_r(x) = \sum_{i=0}^{d/k - 1} f_i(r) \cdot x^i$$

가 되어 $f_r$는 degree $d/k$ 미만의 다항식이 됨을 알 수 있습니다.

이제 두 번째 사실을 증명해봅시다. 각 $x$에 대해서, $p_x$의 계수를 $c_0(x), c_1(x), \cdots, c_{k-1}(x)$라 합시다. 즉,

$$p_x(X) = \sum_{i=0}^{k-1} c_i(x) X^i$$

이며, $y^k = x$이면 $p_x(y) = f(y)$가 성립합니다. 또한, $f_r(x)$를 계산하려면

$$f_r(x) = p_x(r) = \sum_{i=0}^{k-1} r^i \cdot c_i(x)$$

임을 알 수 있습니다. 그런데 이 식이 $\text{RS}[\mathbb{F}, \langle \omega^k \rangle, d/k]$와 $\delta$-close 하다는 것은, correlated agreement에 의해서 적당한 $S$가 있고 $\lvert S \rvert \ge (1 - \delta) \cdot \lvert \langle \omega^k \rangle \rvert$를 만족하며, $c_i(x) = u_i(x)$가 $S$ 위에서 성립하도록 하는 codeword $u_i$가 있습니다. 이제, $S' \subset S$가 $\lvert S' \rvert = \min (\lvert S \rvert, d/k)$를 만족하도록 하고, $x \in S'$에 대해서 $I_{x, S'}$를 $x$에서 $1$이고 다른 $S'$의 점에서는 $0$으로 evaluate 되는 indicator polynomial 이라고 합시다. 이제 bivariate polynomial

$$Q(X, Y) = \sum_{x \in S'} I_{x, S'}(X) \cdot p_x(Y)$$

그러면 $r \in \mathbb{F}$와 $x \in S'$에 대하여

$$Q(x, r) = p_x(r) = \sum_{i=0}^{k-1} r^i \cdot c_i(x) = \sum_{i=0}^{k-1} r^i \cdot u_i(x) $$

이제, degree의 논리에 의해 이는 $x \in S$에 대해서 아예 성립합니다. 그러므로, $y^k \in S$라면,

$$Q(y^k, y) = \sum_{i=0}^{k-1} y^i \cdot u_i(y^k) = \sum_{i=0}^{k-1} y^i \cdot c_i(y^k) = p_{y^k}(y) = f(y)$$

가 성립하는데 $Q(y^k, y)$는 degree $d$ 미만의 다항식이므로, $f$가 $k \cdot \lvert S \rvert \ge (1 - \delta) \lvert \langle \omega \rangle \rvert$ 짜리 크기의 집합에서 codeword와 agree 함을 알 수 있습니다. 그러므로 증명 끝.

이 논리를 잘 생각해보면, 결국 이 논리는 실패 확률이

$$\text{err}(d/k, \rho, \delta, k)$$

이하임을 알 수 있습니다.

**Quotients**: $f: \langle \omega \rangle \rightarrow \mathbb{F}$를 $p: S \rightarrow \mathbb{F}$에 대하여 quotient 한다는 것은,

$$\text{Quotient}(f, S, p)(x) = \frac{f(x) - \hat{p}(x)}{\prod_{a \in S}(x - a)}$$

를 계산하는 것을 의미합니다. 단, $\hat{p}$는 $p$와 $S$에서 agree 하는 $\deg p < \lvert S \rvert$를 만족시키는 다항식입니다.

이 역시, 다음을 만족시킴을 증명할 수 있습니다.
- $f \in \text{RS}[\mathbb{F}, \langle \omega \rangle, d]$가 $p$와 $S$에서 agree하는 degree $d$ 미만 다항식의 evaluation이라면

$$\text{Quotient}(f, S, p) \in \text{RS}[\mathbb{F}, \langle \omega \rangle, d - \lvert S \rvert]$$

- 모든 $f$와 $\delta$-close 한 degree $d$ 미만 다항식이 $p$와 $S$ 전체에서 agree 하지는 않는다면

$$\Delta (\text{Quotient}(f, S, p), \text{RS}[\mathbb{F}, \langle \omega \rangle, d - \lvert S \rvert]) \ge \delta$$

- $p$를 안다고 가정하면, $\text{Quotient}(f, S, p)$를 계산하는 것은 $f$의 evaluation access 1번으로 충분.

이를 증명해봅시다. 첫 번째 사실과 세 번째 사실은 자명합니다. 두 번째 사실을 보여봅시다.

정확하게는, adversarial case에서 $\text{Quotient}(f, S, p)$는 $S$ 위에서 잘 정의되지 않기 때문에, $\text{Fill}: S \rightarrow \mathbb{F}$를 추가로 정의하고 이 함수가 $\text{Quotient}$의 $S$ 위에서의 evaluation 결과를 맡게 됩니다. 다음을 보입시다.

$f$로부터 $\delta$-close 한 모든 codeword $u$에 대하여 $u\vert_S \neq p\vert_S$라면,

$$T = \{ x \in \mathcal{L} \cap S : p(x) \neq f(x) \}$$

라고 할 때 다음이 성립합니다.

$$\Delta(\text{Quotient}(f, S, p, \text{Fill}), \text{RS}[\mathbb{F}, \mathcal{L}, d - \lvert S \rvert]) + \lvert T \rvert / \lvert \mathcal{L} \rvert > \delta$$

$g = \text{Quotient}(f, S, p, \text{Fill})$이라 하고, 귀류법으로 $(1 - \delta + \lvert T \rvert / \lvert \mathcal{L} \rvert)$ 이상의 비율로 $g$와 agree 하는 codeword $\hat{g}$가 존재한다고 가정합시다. 이를 기반으로 차수 $d$ 미만의 다항식에 대응하는 codeword를 만듭시다.

$$\hat{w}(x) = \hat{g} \cdot \left(\prod_{a \in S} (x - a)\right) + \hat{p}(x)$$

를 잡으면 $\deg \hat{w} < d$입니다. 또한, $x \in L \setminus T$이며 $g(x) = \hat{g}(x)$가 성립하는 $x$에 대해서

$$\hat{w}(x) = g(x) \cdot \left(\prod_{a \in S} (x - a)\right) + \hat{p}(x) = f(x)$$

입니다. 만약 $x \notin S$라면 자명하게 성립하고, $x \in S \setminus T$라면 $\hat{w}(x) = \hat{p}(x) = p(x) = f(x)$이므로 성립합니다.

한편, 해당 조건을 만족하는 $x$의 비율은 최소 $(1 - \delta)$이므로, $f$는 $\hat{w}$와 $\delta$-close 하게 됩니다. 그런데

$$\hat{w}(x) = \hat{p}(x) = p(x)$$

가 모든 $x \in S$에 대해서 성립하므로, 이는 가정에 모순이 되어 증명이 끝납니다.

STIR Iteration의 기본적인 아이디어는 다음과 같습니다. $\mathcal{L} = \langle \omega \rangle$, $\mathcal{L}' = \omega \cdot \langle \omega^2 \rangle$이라고 합니다.

Step 1: 먼저, verifier가 $r^{\text{fold}}$를 $\mathbb{F}$에서 sample 해서 보냅니다.

Step 2: Prover가 $g: \mathcal{L}' \rightarrow \mathbb{F}$를 보냅니다. Honest prover의 경우, $g$는 $\text{Fold}(f, r^{\text{fold}})$의 extension입니다.

Step 3: Verifier가 $r^{\text{out}} \in \mathbb{F} \setminus \mathcal{L}'$을 하나 sample 해서 보냅니다.

Step 4: Prover가 $\beta$를 보냅니다. Honest prover의 경우, $\beta = g(r^{\text{out}})$입니다.

Step 5: Verifier가 $t$번 $r_i^{\text{shift}} \in \langle \omega^k \rangle$를 sample 한 다음, $y_i = f_{r^{\text{fold}}}(r_i^{\text{shift}})$를 계산합니다. 여기서 $f_{r^{\text{fold}}}$의 계산은 $f$를 access 하는 것으로 virtual oracle을 만들어서 진행합니다. 이제, 집합 $\mathcal{G} = (r^{\text{out}} , r_1^{\text{shift}} , \cdots, r_t^{\text{shift}})$와 $p : \mathcal{G} \rightarrow \mathbb{F}$를 잡아 $p(r^{\text{out}}) = \beta$와 $p(r_i^{\text{shift}}) = y_i$가 성립하도록 다항식 $p$를 만들고, $f' = \text{Quotient}(g, \mathcal{G}, p)$를 잡습니다. $f'$의 oracle access는 $g$의 oracle access를 통해서 (Step 2에서 전달함) 할 수 있음을 알 수 있습니다.

**Claim**: $f$가 $\text{RS}[\mathbb{F}, \mathcal{L}, d]$에서 $\delta$-far라면, $f'$은 $\text{RS}[\mathbb{F}, \mathcal{L}', d/k - \lvert \mathcal{G} \rvert]$에서 $(1 - \sqrt{\rho'})$-far 합니다. 이 명제는 최대 $(1-\delta)^t + \text{poly}(\lvert \mathcal{L} \rvert) / \lvert \mathbb{F} \rvert$의 확률로 실패함을 증명할 수 있습니다.

**Proof**: $f$가 $\delta$-far 하다고 하면, 일단 $f_{r^{\text{fold}}}$ 역시 $\delta$-far 합니다. 이 명제의 실패 확률은 $\text{poly}(\lvert \mathcal{L} \rvert) / \lvert \mathbb{F} \rvert$입니다.

이제 증명할 것은 $g$에서 $(1 - \sqrt{\rho'})$ 거리 안에 있는 codeword 중 $r^{\text{out}}$에서 $\beta$로 evaluate 되는 것이 최대 하나 있다는 사실입니다. 이는, $\text{RS}[\mathbb{F}, \mathcal{L}', d/k]$가 $\gamma = 1 - \sqrt{\rho'}$와 $l = \text{poly}(\lvert \mathcal{L} \rvert)$에 대해서 $(\gamma, l)$-list-decodable 이므로 (Johnson bound), 해당 거리에 있는 codeword의 개수가 $l$ 이하임을 알 수 있습니다. 두 codeword가 agree 하는 점의 개수는 최대 $d/k$이므로, 두 codeword가 같은 값을 가지는 경우의 수는 최대 $l^2 \cdot (d/k)$ 정도입니다. 그런데 경우의 수 안에 $r^{\text{out}}$이 있어야 하므로, 확률은 여전히 $\text{poly}(\lvert \mathcal{L} \rvert) / \lvert \mathbb{F} \rvert$ 정도입니다.

만약 해당 codeword가 존재하지 않는다면 Quotient의 성질에 따라 $f'$은 $(1 - \sqrt{\rho'})$-far 하게 됩니다.

만약 해당 codeword $u$가 존재한다면, $u$는 $f_{r^{\text{fold}}}$와 $\delta$-far 합니다. $r_i^{\text{shift}}$가 disagreement 지점에서 sample 된다면, 바로 Quotient의 성질에 의해 $f'$은 $(1 - \sqrt{\rho'})$-far 하게 됩니다. 모두 agreement 지점에서 sample 될 확률은 최대 $(1- \delta)^t$임을 알 수 있습니다. 이제 union bound를 쓰면 마무리.

그런데 문제가 하나 있습니다. 결과의 degree가 $d/k - \lvert \mathcal{G} \rvert$라는 건데, 물론 작아지면 좋긴 하지만 2의 거듭제곱임을 유지해야 프로토콜이 진행되므로, 이를 다시 $d/k$로 올려놓을 필요가 있습니다. 이를 위해서 필요한 게 바로 degree correction입니다. 결국, 목표는 $f$를 통해서 쉽게 계산할 수 있는 $f^\star$를 만들되, $f$가 codeword면 $f^\star$도 codeword도 $f$가 $\delta$-far면 $f^\star$도 $\delta$-far이도록 하는 것입니다. 이때, degree를 $d$에서 $d^\star$로 올리는 것이 문제가 되겠습니다. 이제 $e = d^\star - d$로 두고, $r$을 random sampling 한 뒤

$$f^\star(x) = \sum_{i=0}^e r^i (x^i \cdot f(x)) = f(x) \cdot \frac{1 - (rx)^{e+1}}{1 - rx}$$

로 둡니다. 이 식이 조건을 만족함을 간단하게 증명해봅시다. 우선 degree 조건은 걱정할 필요 없으며, codeword가 codeword로 감 역시 자명합니다. distance preservation이 문제인데, correlated agreement를 사용하면 어렵지 않게 해결할 수 있습니다. 결국, $r$이 random 하므로, $f^\star$가 $\delta$-close 하면, correlated agreement에 의해, $\lvert S \rvert \ge (1 - \delta) \cdot \lvert \mathcal{L} \rvert$가 있어 $x^i \cdot f(x) = f_i(x)$가 $S$ 위에서 성립하는 다항식 $f_i$가 있음을 알 수 있습니다. 여기서 $\deg f_i < d^\star$. 이제 목표는 여기서 $\deg f_0 < d$를 보이는 것입니다.

이를 위해서, 뒤로부터 시작하는 귀납법을 통해 $\deg f_i < d + i$를 증명합니다. $i = e$에서는 $\deg f_e < d^\star = d + e$이므로 만족합니다. 이제 $S$ 위에서 $x f_i(x) = f_{i+1}(x)$이고, 양쪽 다 degree가 최대 $d^\star + 1$입니다. 즉, $\lvert S \rvert > d^\star + 1$이기만 하면 $x f_i(x) = f_{i+1}(x)$를 얻어 $\deg f_i = \deg f_{i+1} - 1 < d + i$를 얻을 수 있습니다.

$\lvert S \vert \ge d^\star + 1$을 위해서는 $\delta < \min (1 - \sqrt{\rho}, 1 - (1 + 1/d^\star) \rho)$면 충분하며, 실제로 이 조건이 추가됩니다.

$f^\star$의 evaluation access 역시 $f$의 evaluation 한 번으로 매우 쉽게 되므로, 원하는 결과를 얻었습니다.

이 과정이 실패할 확률은, 결국 $d^\star + 1 - d$개의 다항식의 correlated agreement가 사용되므로,

$$\text{err}(d^\star, \rho, \delta, d^\star + 1 - d)$$

정도임을 알 수 있습니다.

차수가 다른 여러 다항식에 대한 degree correction도 비슷하게 가능하며, 증명도 동일합니다. 이제 degree correction으로 문제를 다시 $\text{RS}[\mathbb{F}, \mathcal{L}', d/k]$에서 풀고, 이 과정을 충분히 반복하면 프로토콜이 완성됩니다.

# STIR: Concrete Protocol

다음 변수들을 잡습니다.
- iteration count $M$
- initial degree $d$, power of 2
- folding parameter $k_0, k_1, \cdots , k_M$. 단, $d \ge \prod_i k_i$.
- evaluation domain $\mathcal{L}_0, \cdots, \mathcal{L}_M$.
- 단, $\mathcal{L}_i$는 smooth coset of $\mathbb{F}^\star$.
- 또한, $\lvert L_i \rvert > d / \prod_{j < i} k_j$
- repetition parameter $t_0, \cdots, t_M$.
- out-of-domain repetition parameter $s$.

그리고 $d_i = d / \prod_{j < i} k_j$로 정의합니다. 프로토콜의 순서는 다음과 같습니다.

시작은 $f_0: \mathcal{L}_0 \rightarrow \mathbb{F}$와 그 oracle로 시작합니다. Honest case에서는 $f_0 \in \text{RS}[\mathbb{F}, \mathcal{L}_0, d]$.

그 후, verifier가 $r_0^{\text{fold}} \in \mathbb{F}$를 보냅니다. 이제부터 interaction이 $M$ round에 걸쳐 진행됩니다.

각 $1 \le i \le M$에 대하여, interaction loop는 다음과 같이 진행됩니다.
- Prover가 $g_i: \mathcal{L}_i \rightarrow \mathbb{F}$를 보냅니다.
- 이는 Honest case에서는 $f_{i-1}$을 $r_{i-1}^{\text{fold}}$로 $k_{i-1}$-Fold 한 다항식의 evaluation입니다.
- Verifier가 $r_{i, 1}^{\text{out}}, \cdots, r_{i, s}^{\text{out}} \in \mathbb{F} \setminus \mathcal{L}_i$를 sample 하고 전달합니다.
- Prover가 field element $\beta_{i, 1}, \cdots , \beta_{i, s}$를 전달합니다.
- Honest case에서, $\beta_{i, j} = g_i(r_{i, j}^{\text{out}})$입니다.
- Verifier가 $r_i^{\text{fold}}$와 $r_i^{\text{comb}}$을 전달하고, $r_{i, 1}^{\text{shift}}, \cdots, r_{i, t_{i-1}}^{\text{shift}} \in \mathcal{L}_{i-1}^k$를 sample하고 전달합니다.
- Prover는 $\mathcal{G}_i$를 아래와 같이 잡고, $g_i' = \text{Quotient}(g_i, \mathcal{G}_i)$를 전달합니다.
- Honest case에서는 $\text{Fill}$ 역시 자연스럽게 정의됩니다.

$$\mathcal{G}_i = (r_{i,1}^{\text{out}} , \cdots, r_{i,s}^{\text{out}}, r_{i,1}^{\text{shift}}, \cdots, r_{i, t_{i-1}}^{\text{shift}})$$

- 그 후, 다음 다항식은 $f_i = \text{DegCor}(d_i, r_i^{\text{comb}}, g_i', d_i - \lvert \mathcal{G}_i \rvert)$가 됩니다.

최종적으로는, Prover가 $f_M$을 $r_M^{\text{fold}}$로 fold 한 다항식의 모든 계수를 보냅니다.

Verifier는 다음 과정을 거칩니다. 우선 interaction loop의 정당함을 확인해야 합니다. 각 $1 \le i \le M$에 대하여,
- $f_{i-1}$을 query 해서 $f_{i-1}$을 $r_{i-1}^{\text{fold}}$로 $k_{i-1}$-fold 한 다항식의 결과를 $r_{i, j}^{\text{shift}}$에 대해 직접 계산합니다.
- $\mathcal{G}_i$ 위에서 $p_i$가 다음을 만족하도록 잡습니다.

$$p_i(r_{i,j}^{\text{out}}) = \beta_{i, j}, \quad p_i(r_{i, j}^{\text{shift}}) = \text{Fold}(f_{i-1}, k_{i-1}, r_{i-1}^{\text{fold}})(r_{i, j}^{\text{shift}})$$

- 그 후, $g_i'$을 virtual oracle $\text{Quotient}(g_i, \mathcal{G}_i, p_i, \text{Fill}_i)$로 잡고
- 그 후 $f_i: \mathcal{L}_i \rightarrow \mathbb{F}$를 $\text{DegCor}(d_i, r_i^{\text{comb}}, g_i', d_i - \lvert \mathcal{G}_i \rvert)$로 virtual 하게 잡고, 다음 round로 넘어갑니다.

그 후, 마지막 다항식을 체크합니다. $r_1^{\text{fin}}, \cdots, r_{t_M}^{\text{fin}}$을 $\mathcal{L}_M$에서 잡고,

$$p(r_j^{\text{fin}}) = \text{Fold}(f_M, k_M, r_M^{\text{fold}})(r_j^{\text{fin}})$$

인지 확인합니다. 또한, 각 $1 \le i \le M$에 대하여 $x \in \mathcal{G}_i \cap \mathcal{L}_i$인 모든 $x$에 대해서 $g_i(x) = p_i(x)$를 확인합니다.

추후에, round-by-round soundness error가 $2^{-\lambda}$ 미만이도록 parameter를 설정합니다. 특히, 실제로는
- $k_i$가 power of 2인 상수 $k$로 고정되고, $s = 1$로 고정됩니다.
- 최종 단계에서 degree가 $d_{\text{stop}}$이 되며, $M = \lfloor \log_k (d/d_{\text{stop}}) \rfloor$입니다.
- $\mathcal{L}_{i-1} = \langle \omega \rangle$인 경우 $\mathcal{L}_i = \omega \cdot \langle \omega^2 \rangle$입니다.
- 이 경우 $\mathcal{L}_{i-1}^k$와 $\mathcal{L}_i$가 disjoint 해져, $\mathcal{G}_i \cap \mathcal{L}_i = \emptyset$이 됩니다.

그 후 parameter 들을 상당히 열심히 잘 잡아서 (Appendix C) 앞서 언급했던 query complexity인

$$\mathcal{O}_k \left( \log d + \lambda \cdot \log \left( \frac{\log d}{- \log \rho} \right) \right)$$

를 얻을 수 있습니다. 본격적으로 round-by-round soundness를 이야기 하기 전에, 이게 뭔지부터 알아봅시다.

# Interlude: Round-by-Round Soundness

https://eprint.iacr.org/2018/1004.pdf 논문의 내용을 잠시 다룹니다.

FRI, STIR, 기타 ZKP 접근 모두 결국 interactive system에 보통 Fiat-Shamir를 덮어서 non-interactive system을 만듭니다. Fiat-Shamir를 간략하게 설명하자면, verifier의 메시지를 verifier가 직접 보내는 대신, 지금까지의 transcript를 hash 해서 얻는 방법입니다. 그러면 verifier는 중간에 직접 메시지를 보낼 필요가 없고, 마지막에 전체 proof를 검증하는 과정에서 verifier의 메시지가 제대로 잘 계산되었는지 (진짜로 지금까지의 transcript의 hash인지) 검증하면 됩니다. 이러면 verifier는 proof를 한꺼번에 받게 되므로, non-interactive system이 완성됩니다.

보통 Fiat-Shamir의 security analysis는 Random Oracle Model에서 진행되었는데, 이 경우 증명된 사실은 기존 protocol $\Pi$가 computational soundness를 갖고 round의 수가 $\mathcal{O}(1)$이라면 Fiat-Shamir를 덮은 protocol인 $\Pi_{\text{FS}}$ 역시 soundness를 갖는다는 것입니다. 이러한 상황에서 해결하면 좋을 것 같은 문제는 두 가지입니다.

첫 번째 문제는 Random Oracle Model을 사용하지 않고, hash $H$가 특정 성질을 만족하면 $H$를 사용한 Fiat-Shamir가 soundness를 보존하는지 직접 증명하는 방법을 찾는 것입니다. 즉, "Fiat-Shamir-Compatible"한 hash family를 concrete하게 찾거나, 존재성을 증명하는 문제가 있습니다. 2018/1004의 저자들은 LWE를 기반으로 한 FHE를 통해서 이러한 efficiently computable hash function을 직접 잡고, 이를 GKR에 적용하여 SNARG를 완성시킵니다. 이를 위해서 "correlation intractable" hash function이라는 개념을 도입합니다.

두 번째 문제는 constant number of rounds를 더 확장시킬 수 없냐는 것입니다. GKR도 그렇고, FRI도 그렇고, STIR도 그렇고, 모두 round의 수가 constant는 아니기 때문입니다. PLONK와 같은 경우 round의 수가 $\mathcal{O}(1)$이지만, FRI/STIR는 그렇지 못합니다. 그러므로, round 수의 제한을 해결할 방법이 필요합니다. 이를 해결하기 위해서, soundness의 notion을 강화한 round-by-round soundness라는 개념을 도입합니다. round-by-round soundness를 갖는 interactive proof는 round 수의 관계없이, Fiat-Shamir를 적용했을 때 soundness를 보존합니다. 앞서 언급한 correlation intractable hash function을 사용하면 concrete 한 instantiation도 가능합니다.

round-by-round soundness는 현재 "상태"에 대해서 (efficiently computable 하지 않아도 되는) 상태값 $1$ 또는 $0$을 부여하는 것으로 시작합니다. 즉, 현재 "상태"가 accept 각인지 reject 각인지를 미리 정의해놓고, 상태가 각 round 마다 어떻게 바뀌는지 분석합니다. $\Pi$가 round-by-round soundness error $\epsilon$을 갖는다는 것은, instance $x$와 transcript prefix $\tau$에 대한 함수 $\text{State}(x, \tau) = 0/1$가 있어 다음 조건들을 만족하는 것입니다.

**1**: $x \notin L$이라면 $\text{State}(x, \emptyset) = 0$

**2**: instance $x$와 transcript prefix $\tau$가 $\text{State}(x, \tau) = 0$이라면, 임의의 다음 prover message $\alpha$에 대하여

$$\text{Pr}_{\beta} [\text{State}(x, \tau \vert \alpha \vert \beta) = 1] \le \epsilon$$

이 성립합니다. 여기서 $\beta$는 verifier의 다음 message space에서 sample 되었다고 보면 됩니다.

**3**: $\tau$가 full transcript라면, $\text{State}(x, \tau) = 0$인 경우 실제로 verifier가 reject 합니다.

이제 intuitive 하게 Random Oracle Model에서 왜 soundness가 보존되는지 알 수 있습니다. $x \notin L$이라면 State 값은 0으로 시작할 것이고, 각 round에서 $\beta$는 random oracle에서 뽑히므로 State 값이 1로 갈 확률은 각 round마다 최대 $\epsilon$입니다. 그러므로, Union Bound에 의해 최대 $r \cdot \epsilon$의 실패 확률을 제외하고 최종 상태에서도 State 값이 0으로 유지가 되며, 이때 verifier는 실제로 proof를 reject 하게 됩니다.

대표적인 Fiat-Shamir + multi-round-protocol의 반례를 생각해보면 조금 더 명확하게 round-by-round soundness의 강점을 알 수 있습니다. 가장 유명한 예시는, $x \notin L$인 경우 한 번의 prover/verifier interaction의 실패 확률이 $1/2$인 상황에서, soundness를 amplify 하기 위해 동일한 interaction을 $\lambda$번 진행하는 경우가 있습니다. 이 경우, Fiat-Shamir를 단순히 적용하면 각 round에 대해서 prover가 Fiat-Shamir 결과로 유도되는 verifier message가 $1/2$ 확률로 가능한 성공 경우가 나오도록 하는 prover message를 탐색하는 방식으로 공격을 할 수 있습니다. 그런데, 생각을 해보면 이건 마치 round-by-round soundness error가 $1/2$인 경우와 같습니다. 그러니, 새로운 round-by-round soundness라는 접근에서는 기존 방식이 soundness를 가지지 않고, 즉 Fiat-Shamir로 compile 하는 것이 안전하지 않다는 결론을 얻을 수 있습니다. 이렇게 보면 결국 "각 round의 soundness"를 본다는 의미가 더 명확해집니다. 새삼 round-by-round soundness 이름 잘 지었네요.

FRI의 round-by-round soundness도 최근에 증명되었습니다. https://eprint.iacr.org/2023/1071.

# STIR's Round-by-Round Soundness

이제 STIR의 round-by-round soundness를 분석해봅시다.

$f \notin \text{RS}[\mathbb{F}, \mathcal{L}_0, d_0]$라고 하고, $\rho_i = d_i/\lvert \mathcal{L}_i \rvert$라고 합시다. 또한, $\delta_0, \cdots, \delta_M$이 다음을 만족한다고 합시다.
- $\delta_0 \in (0, \Delta(f, \text{RS}[\mathbb{F}, \mathcal{L}_0, d_0])) \cap (0, 1 - \sqrt{\rho_0})$
- $1 \le i \le M$에 대해, $\delta_i \in (0, \min ( 1 - \rho_i - 1 / \lvert \mathcal{L}_i \rvert, 1 - \sqrt{\rho_i}))$
- $1 \le i \le M$에 대해, $\text{RS}[\mathbb{F}, \mathcal{L}_i, d_i]$는 $(\delta_i, l_i)$-list decodable

STIR의 round-by-round soundness error $(\epsilon^{\text{fold}}, \epsilon_1^{\text{out}}, \epsilon_1^{\text{shift}}, \cdots, \epsilon_M^{\text{out}}, \epsilon_M^{\text{shift}}, \epsilon^{\text{fin}})$은 다음을 만족합니다.

$$\epsilon^{\text{fold}} \le \text{err}(d_0/k_0, \rho_0, \delta_0, k_0)$$

$$\epsilon_i^{\text{out}} \le \frac{l_i^2}{2} \cdot \left( \frac{d_i}{ \lvert \mathbb{F} \rvert - \lvert \mathcal{L}_i \rvert} \right)^s$$

$$\epsilon_i^{\text{shift}} \le (1 - \delta_{i-1})^{t_{i-1}} + \text{err}(d_i, \rho_i, \delta_i, t_{i-1} + s) + \text{err}(d_i/k_i, \rho_i, \delta_i, k_i)$$

$$\epsilon^{\text{fin}} \le (1 - \delta_M)^{t_M}$$

앞서 언급했듯이, 실제로 parameter를 설정할 때 $\epsilon < 2^{-\lambda}$가 만족하도록 합니다.

이제 본격적으로 증명을 해봅시다. 증명을 위해서는, State Function을 잡아야 합니다.

Iteration을 따라가면서, State Function을 정의해가며 round-by-round soundness를 봅시다.

**시작 시점**

$$\text{State}(f, \emptyset) = 1 \iff f \in \text{RS}[\mathbb{F}, \mathcal{L}, d]$$

**$r_0^{\text{fold}}$ 전달: Bounding $\epsilon^{\text{fold}}$**

$$\text{State}(f, r_0^{\text{fold}}) = 1 \iff \Delta(\text{Fold}(f, k_0, r_0^{\text{fold}}, \text{RS}[\mathbb{F}, \mathcal{L}_0^{k_0}, d_0/k_0])) \le \delta_0$$

로 정의합시다. 이제, round-by-round soundness error를 생각합시다.

$\text{State}(f, \emptyset) = 0$에서 $\text{State}(f, r_0^{\text{fold}}) = 1$로 갈 확률은

$$\text{err}(d_0/k_0, \rho_0, \delta_0, k_0)$$

이하임을 앞서 증명한 Fold의 두 번째 성질에서 알 수 있습니다.

**Defining State Function in Iteration Part 1: Out**

현재 transcript는 다음과 같습니다.

$$r_0^{\text{fold}}, \text{tr}_1, \cdots, \text{tr}_{i-1}, g_i$$

이 경우, $\text{State}(f, \text{tr} \lvert (r_{i,1}^{\text{out}}, \cdots, r_{i, s}^{\text{out}})) = 1$은 다음과 동치입니다.

다음 두 조건 (#1, #2)가 모두 성립해야 합니다. 단, $f_{i-1}$은 verifier의 logic으로 transcript에서 유도됩니다.

조건 #1: 다음 둘 중 최소한 하나가 성립합니다. 위의 명제를 #1-a, 아래의 명제를 #1-b라 합시다.

$$\Delta(\text{Fold}(f_{i-1}, k_{i-1}, r_{i-1}^{\text{fold}}), \text{RS}[\mathbb{F}, \mathcal{L}_{i-1}^{k_{i-1}}, d_i]) \le \delta_{i-1}$$

$$\exists u, u' \in \text{List}(g_i, d_i, \delta_i), \quad u(r_{i,j}^{\text{out}}) = u'(r_{i,j}^{\text{out}}) \quad \forall 1 \le j \le s$$

조건 #2: 각 $1 \le j < i$에 대하여, $x \in \mathcal{G}_j \cap \mathcal{L}_j$에 대해

$$g_j(x) = p_j(x)$$

**Defining State Function in Iteration Part 2: Shift**

Iteration에 있기 때문에, 이때의 State를 먼저 정의해야 증명이 가능합니다.

현재 transcript는

$$r_0^{\text{fold}}, \text{tr}_1, \cdots, \text{tr}_{i-1}, g_i, r_{i, 1}^{\text{out}}, \cdots, r_{i, s}^{\text{out}}, \beta_{i, 1}, \cdots, \beta_{i, s}$$

입니다. 이 경우, 다음 State가 1일 필요충분조건, 즉

$$\text{State}(f, \text{tr} \lvert (r_i^{\text{fold}}, r_i^{\text{comb}}, r_{i,1}^{\text{shift}}, \cdots, r_{i, t_{i-1}}^{\text{shift}})) = 1$$

의 조건은 다음 두 명제가 모두 성립한다는 것입니다.

조건 #1: $f_i$가 verifier의 logic으로 유도되는 다음 함수일 때,

$$\Delta(\text{Fold}(f_i, k_i, r_i^{\text{fold}}), \text{RS}[\mathbb{F}, \mathcal{L}_i^{k_i}, d_i/k_i]) \le \delta_i$$

조건 #2: 각 $1 \le j \le i$에 대하여, $x \in \mathcal{G}_j \cap \mathcal{L}_j$에 대해

$$g_j(x) = p_j(x)$$

이제 round-by-round soundness error를 계산할 수 있습니다.

**Bounding $\epsilon_i^{\text{out}}$**

이제 State 값이 0에서 1로 가는 경우를 고민해야 합니다. 만약 $i-1$번째 Shift 단계에서 조건 #2가 성립하지 않는다면, $i$번째 Out 단계에서도 조건 #2는 성립하지 않습니다. 그러므로, 이 경우에서는 무조건 State 값이 0에서 0으로 갑니다. 남은 고려해야 하는 경우는 $i-1$번째 Shift 단계에서 조건 #2는 성립하지만 조건 #1은 성립하지 않는 경우, $i$번째 Out 단계에서 조건 #1이 성립할 확률을 구하는 것입니다. 그런데, $i-1$번째 Shift 단계에서 조건 #1이 성립하지 않으므로, $i$번째 Out 단계에서 조건 #1-a는 성립하지 않습니다. 그러므로, 조건 #1이 성립하려면 조건 #1-b가 성립해야 합니다. 이 확률은, 두 codeword가 agree 할 수 있는 점이 $d$개 미만이므로,

$$\epsilon_i^{\text{out}} \le \frac{l_i^2}{2} \cdot \left( \frac{d}{ \lvert \mathbb{F} \rvert - \lvert \mathcal{L}_i \rvert} \right)^s$$

임이 간단한 Union Bound를 통해서 증명됩니다.

**Bounding $\epsilon_i^{\text{shift}}$**

역시, $i$번째 Out 단계에서 조건 #2가 성립하지 않으면 $i$번째 Shift 단계에서도 조건 #2가 성립하지 않습니다. 이 경우에서는 State 값이 0에서 0으로 가니, 자명합니다. 그러니, $i$번째 Out 단계에서 조건 #2는 성립하고 조건 #1-a와 조건 #1-b가 둘 다 성립하지 않는다고 가정하고, $i$번째 Shift 단계에서 State 값이 1이 될 확률을 구합시다.

우선, verifier의 입장에서, $g_i$와 가까운 codeword 중 $p_i$와 $\mathcal{G}_i$에서 agree 하는 게 매우 낮은 확률로 있음을 보여야 합니다. 앞서 언급한 트릭과 정확하게 동일하게 진행됩니다. 조건 #1-b가 성립하지 않으므로,

$$u \in \text{List}(g_i, d_i, \delta_i), \quad u(r_{i,j}^{\text{out}}) = \beta_{i, j} \quad \forall 1 \le j \le s$$

가 전부 성립하는 $u$는 없거나 유일합니다. 없으면 바로 증명이 끝납니다.

이제 $u$가 유일한 경우를 생각하면 됩니다. 그런데 가정에 의해서 $\text{Fold}(f_{i-1}, k_{i-1}, r_{i-1}^{\text{fold}})$가 Reed-Solomon code와 $\delta_{i-1}$-far 하므로, $u$와 fold 결과가 $r_{i, j}^{\text{shift}}$에서 전부 agree 할 확률은 최대 $(1 - \delta_{i-1})^{t_{i-1}}$ 입니다.

이제, 이 확률을 제외하고, 해당 codeword $u$가 없다고 가정합시다. 이제, Quotient의 성질에 따라서,

$$\Delta(g_i', \text{RS}[\mathbb{F}, \mathcal{L}_i, d_i- \lvert \mathcal{G}_i \rvert]) > \delta_i - \lvert T_i \rvert / \lvert \mathcal{L}_i \rvert$$

인데, 생각해보면 여기서

$$T_i = \{x \in \mathcal{G}_i \cap \mathcal{L}_i : g_i(x) \neq p_i(x)\}$$

이고, 조건 #2를 만족하려면 $T_i = \emptyset$입니다. 그러니, 단순히

$$\Delta(g_i', \text{RS}[\mathbb{F}, \mathcal{L}_i, d_i- \lvert \mathcal{G}_i \rvert]) > \delta_i$$

라고 생각해도 좋습니다. 이제, degree correction의 성질에 의해

$$\Delta(f_i, \text{RS}[\mathbb{F}, \mathcal{L}_i, d_i]) > \delta_i$$

가 성립하고, 이 명제의 실패 확률이

$$\text{err}(d_i, \rho_i, \delta_i, \lvert \mathcal{G}_i \rvert) = \text{err}(d_i, \rho_i, \delta_i, t_{i-1} + s)$$

임을 알 수 있습니다. 이제 여기서 다시 fold 하는 과정을 생각하면

$$\Delta(\text{Fold}(f_i, k_i, r_i^{\text{fold}}), \text{RS}[\mathbb{F}, \mathcal{L}_i^{k_i}, d_i/k_i]) \le \delta_i$$

가 성립할 확률은 최대

$$\text{err}(d_i / k_i, \rho_i, \delta_i, k_i)$$

가 됩니다. 그러니, 여기서 언급한 실패 확률 세 개를 전부 더하면 Union Bound로 증명이 끝납니다.

**최종 단계: Bounding $\epsilon^{\text{fin}}$**

현재 transcript는

$$r_0^{\text{fold}}, \text{tr}_1, \cdots, \text{tr}_{M}, p$$

이며, $\text{State}(f, tr \vert (r_1^{\text{fin}}, \cdots, r_{t_M}^{\text{fin}})) = 1$은 다음 두 조건이 모두 성립하는 것과 동치입니다.

조건 #1: 각 $1 \le j \le t_M$에 대하여

$$p(r_j^{\text{fin}}) = \text{Fold}(f_M, k, r_M^{\text{fold}})(r_j^{\text{fin}})$$

조건 #2: 각 $1 \le j \le M$에 대하여, $x \in \mathcal{G}_j \cap \mathcal{L}_j$에 대해

$$g_j(x) = p_j(x)$$

마찬가지로, 이전 상태에서 조건 #2가 성립하지 않으면 이번 상태에서도 조건 #2는 성립하지 않습니다. 그러므로, 이 상황에서는 State 값이 0에서 0으로 가는 것이 보장됩니다. 그러니, 이전 상태에서 조건 #1이 성립하지 않고 조건 #2는 성립한다고 가정하고, 이번 상태에서 조건 #1과 조건 #2가 성립할 확률을 고민하면 됩니다. 그런데, 조건 #1이 성립하지 않으면 fold 된 결과가 Reed-Solomon code와 $\delta_M$-far 합니다.

그러므로, $t_M$개의 시도에서 fold의 결과가 전부 valid codeword $p$의 결과와 agree 할 확률은 최대

$$(1 - \delta_M)^{t_M}$$

미만임을 알 수 있습니다. 또한, 최종 단계에서 State 값이 0이면 verifier가 reject 함은 프로토콜 정의상 자명합니다. 그러므로, STIR의 round-by-round soundness가 이렇게 꽤 간단하게 증명됩니다.