3 STIR
3.1 STIR Main Theorem
Consider the following ingrediants:
A security parameter \(\lambda \in \mathbb {N}\).
A Reed-Solomon code \(\mathrm{RS}[\mathbb {F},\mathcal{L},d]\) with \(\rho :=\frac{d}{|\mathcal{L}|}\) where \(d\) is a power of \(2\), and \(\mathcal{L}\) is a smooth domain.
A proximity parameter \(\delta \in (0,1-1.05\cdot \sqrt{\rho })\).
A folding parameter \(k\in \mathbb {N}\) that is power of \(2\) with \(k\geq 4\).
If \(|\mathbb {F}|=\Omega (\frac{\lambda \cdot 2^\lambda \cdot d^2\cdot {|\mathcal{L}|}^2}{\log (1/\rho )})\), there is a public-coin IOPP for \(\mathrm{RS}[\mathbb {F},\mathcal{L},d]\) with the following parameters:
Round-by-round soundness error \(2^{-\lambda }\).
Round complexity: \(M:=O(\log _k{d})\).
Proof length: \(|\mathcal{L}|+O_k(\log {d})\).
Query complexity to the input: \(\frac{\lambda }{-\log {(1-\delta )}}\).
Query complexity to the proof strings: \(O_k(\log {d}+\lambda \cdot \log {\Big(\frac{\log {d}}{\log {1/\rho }}\Big)})\).
3.2 The STIR Construction
Consider the following ingrediants:
a field \(\mathbb {F}\),
an iteration count \(M\in \mathbb {N}\),
an initial degree parameter \(d\in \mathbb {N}\) that is a power of \(2\),
a folding parameters \(k_0,\ldots ,k_M\in \mathbb {N}\) that are powers of \(2\) with \(d\geq \prod _{i}k_i\),
evaluation domains \(\mathcal{L}_0,\ldots ,\mathcal{L}_M\subseteq \mathbb {F}\) where \(\mathcal{L}_i\) is a smooth coset of \({\mathbb {F}}^*\) with \(|\mathcal{L}_i|{\gt}\frac{d}{\prod _{j{\lt}i}k^j}\)
repetition parameters \(t_0,\ldots ,t_M\in \mathbb {N}\) where \(t_i+1\leq \frac{d}{\prod _{j\leq i}k^j}\) for every \(i\in \{ 0,\ldots ,M-1\} \),
out of domain repetition parameter \(s\in \mathbb {N}\).
For every \(i\in \{ 0,\ldots ,M\} \), set \(d_i:=\frac{d}{\prod _{j{\lt}i}k^j}\). The protocol proceeds as follows.
Initial function: Let \(f_0:\mathcal{L}\rightarrow \mathbb {F}\) be an oracle function. In the honest case, \(f_0=\mathrm{RS}[\mathbb {F},\mathcal{L}_0,d_0]\) and the prover has access to the polynomial \(\hat{f}\in \mathbb {F}^{{\lt}d_0}[X]\) whose restriction to \(\mathcal{L}_0\) is \(f_0\).
Initial folding: The verifier sends \(r^{\mathsf{Fold}}\gets \mathbb {F}\)
Interaction phase loop: For \(i\in \{ 1,\ldots ,M\} \):
Send folded function: The prover sends a function \(g_i:\mathcal{L}_i\rightarrow \mathbb {F}\). In the honest case \(g_i\) is the evaluation of the polynomial \(\hat{g}_i:=\mathsf{PolyFold}(\hat{f}_{i-1},k_{i-1},r^{\mathsf{fold}}_{i-1})\) over \(\mathcal{L}_i\).
Out-of-domain samples: The verifier sends \(r_{i,1}^{\mathsf{out}},\ldots ,r_{i,s}^{\mathsf{out}}\in \mathbb {F}\setminus \mathcal{L}_i\)
Out-of-domain reply: The prover sends field elements \(\beta _{i,1},\dots ,\beta _{i,s}\in \mathbb {F}\). In the honest case, \(\beta _{i,j}:=\hat{g}_{i}(r_{i,j}^{\mathsf{out}})\).
STIR message: The verifier sends \(r^{\mathsf{fold}}_i,r^{\mathsf{shift}}_i\in \mathbb {F}\) and \(r_{i,1}^{\mathsf{shift}},\ldots ,r_{i,t_{i-1}}^{\mathsf{shift}}\gets \mathcal{L}^{k_i-1}_{i-1}\)
Define next polynomial and send hole fills: The prover sends the oracle message \(\mathsf{Fill}_i:=(r^{\mathsf{shift}}_{i,1},\ldots ,r^{\mathsf{shift}}_{i,t_{i-1}})\cap \mathcal{L}_i\rightarrow \mathbb {F}\). In the honest case, the prover defines \(\mathcal{G}_i=\{ r^{\mathsf{out}}_{i,1},\ldots ,r^{\mathsf{out}}_{i,s},r^{\mathsf{shift}}_{i,1},\ldots ,r^{\mathsf{shift}}_{i,t_{i-1}}\} \), \(\hat{g}'_i:=\mathsf{PolyQuotient}(\hat{g}_i,\mathcal{G}_i)\) and \(\mathsf{Fill}_i(r^{\mathsf{shift}}_{i,j}):=\hat{g}'_i(r^{\mathsf{shift}}_{i,j})\) \((\text{ If }r^{\mathsf{shift}}_{i,j}\in \mathcal{L}_i)\)
Additionally, the honest prover defines the degree-corrected polynomial \(\hat{f}_i \in \mathbb {F}^{{\lt}d}[X]\) as follows:
\[ \hat{f}_i :=\mathsf{DegCor}(d_i,r_{i}^{\mathsf{comb}},\hat{g}'_i,d_i-|\mathcal{G}_i|) \]The protocol proceeds to the next iteration with \(\hat{f}_i\).
Final round: The prover sends \(d_M\) coefficients of a polynomial \(\hat{p}\in \mathbb {F}^{{\lt}d_M}[X]\). In the honest case, \(\hat{p}:=\mathsf{Fold}(\hat{f}_M,k_M,r^{\mathsf{fold}_M})\).
Verifier decision phase:
Main loop: For \(i=1,\ldots ,M:\)
For every \(j\in [t_{i-1}]\), query \(\mathsf{Fold}(f_{i-1},k_{i-1},r^{\mathsf{fold}}_{i-1})\) at \(r^{\mathsf{shift}}_{i,j}\). This involves querying \(f_{i-1}\) at all \(k_{i-1}\) points \(x\in {\mathcal{L}}_{i-1}\) with \(x^{k_i-1}=r^{\mathsf{shift}}_{i,j}\).
Define \(\mathcal{G}_i=\{ r^{\mathsf{out}}_{i,1},\ldots ,r^{\mathsf{out}}_{i,s},r^{\mathsf{shift}}_{i,1},\ldots ,r^{\mathsf{shift}}_{i,t_{i-1}}\} \) and let \(\mathsf{Ans}_i:\mathcal{G}_i\rightarrow \mathbb {F}\) be the function where \(\mathsf{Ans}_i(r^{\mathsf{out}}_{i,j})=\beta _{i,j}\) and \(\mathsf{Ans}_{i}(r^{\mathsf{shift}}_{i,j})=\mathsf{Fold}(f_{i-1},k_{i-1},r^{\mathsf{fold}}_{i-1})(r^{\mathsf{shift}}_{i,j})\). Finally, (virtually) set \(g'_i:=\mathsf{Quotient}(g_i,\mathcal{G}_i,\mathsf{Ans}_i,\mathsf{Fill}_i)\).
Define the virtual oracle \(f_i:\mathcal{L}_i\rightarrow \mathbb {F}\) as follows:
\[ f_i:=\mathsf{DegCor}(d_i,r^{\mathsf{comb}}_i,g'_i,d_i-|\mathcal{G}_i|). \]Observe that a query \(x\) to \(f_i\) translates to a single query either to \(g_i\) \((\text{ if} (x\notin \mathcal{G}_i))\) or to \(\mathsf{Fill}_i\) \((\text{ If } (x\in \mathcal{G}_i))\).
Consistency with final polynomial:
Sample random points \(r^{\mathsf{fin}}_1,\ldots ,r^{\mathsf{fin}}_{t_M}\rightarrow \mathcal{L}^{k_M}_{M}.\)
Check that \(\hat{p}(r^{\mathsf{fin}}_j)=\mathsf{Fold}(f_M,k_M,r^{\mathsf{fold}}_M)(r^{\mathsf{fin}}_j)\) for every \(j\in [t_M]\).
Consistency with \(\mathsf{Ans}\): For every \(i\in \{ i,\ldots ,M\} \) and every \(x_i\in \mathcal{G}_i\cap \mathcal{L}_i\) query \(g_i(x)\) and check that \(g_i(x)=\mathsf{Ans}_i(x)\).
3.3 Round-by-round soundness
Consider \((\mathbb {F},M,d,k_0,\ldots ,k_M,\mathcal{L}_0,\ldots ,\mathcal{L}_M,t_0,\ldots ,t_M)\) and \(d_0,\ldots ,d_M\) as in Construction 3.2, and for every \(0\leq i\leq M\) let \(\rho _i:=d_i/|\mathcal{L}_i|\). For every \(f\notin \mathrm{RS}[\mathbb {F},\mathcal{L}_0,d_0]\) and every \(\delta _0,\ldots ,\delta _M\) where
\(\delta _0\in (0,\Delta (f,\mathrm{RS}[\mathbb {F},\mathcal{L}_0,d_0])]\cap (0,1-{\mathsf{B}}^*(\rho _0))\)
for every \(0{\lt}i\leq M\): \(\delta _i\in (0,\min {\{ 1-\rho _i-\frac{1}{|\mathcal{L}_i|},1-{\mathsf{B}^*(\rho _i)}\} })\), and
for every \(0{\lt}i\leq M\): \(\mathrm{RS}[\mathbb {F},\mathcal{L}_i,d_i]\) is \((\delta _i,l_i)\)-list decodable,
STIR (Construction 3.2) has round-by-round soundness error \((\epsilon ^{\mathsf{fold}},\epsilon ^{\mathsf{out}}_1,\epsilon ^{\mathsf{shift}}_1,\ldots ,\epsilon ^{\mathsf{out}}_M,\epsilon ^{\mathsf{shift}}_M,\epsilon ^{\mathsf{fin}})\) where:
\(\epsilon ^{\mathsf{fold}}\leq \mathsf{err}^*(d_0/k_0,\rho _0,\delta _0,k_0)\).
\(\epsilon ^{\mathsf{out}}_i\leq \frac{l^2_i}{2}\cdot {\big(\frac{d_i}{|\mathbb {F}|-|\mathcal{L}_i|}\big)}^s\)
\(\epsilon ^{\mathsf{shift}}_i\leq {(1-\delta _{i-1})}^{t_{i-1}}+\mathsf{err}^*(d_i,\rho _i,\delta _i,t_{i-1}+s)+\mathsf{err}^*(d_i/k_i,\rho _i,\delta _i,k_i)\).
\(\epsilon ^{\mathsf{fin}}\leq {(1-\delta _M)}^{t_M}\).
Above, \({\mathsf{B}}^*\) and \({\mathsf{err}}^*\) are the proximity bound and error (respectively) described in Section 2.1.