笔记：Basefold 在 List Decoding 下的 Soundness 证明
在上一篇文章《Basefold 在 List Decoding 下的 Soundness 证明概览》中，梳理了 [H24] 论文中 soundness 证明的思路，本篇文章将沿着这个思路深入论文中的证明细节，主要是 [H24, Lemma 1] 的证明，其证明了 Basefold 协议在 commit 阶段的 soundness error。
Lemma 1 [H24, Lemma 1] (Soundness commit phase). Take a proximity parameter θ = 1 − ( 1 + 1 2 ⋅ m ) ⋅ ρ \theta=1-\left(1 + \frac{1}{2 \cdot m}\right) \cdot \sqrt{\rho} θ = 1 − ( 1 + 2 ⋅ m 1 ) ⋅ ρ m ≥ 3 m\geq3 m ≥ 3 P ∗ P^* P ∗ r ≥ 0 r\geq0 r ≥ 0
ε C = ε 0 + ε 1 + … + ε r , \varepsilon_C=\varepsilon_0+\varepsilon_1+\ldots+\varepsilon_r, ε C = ε 0 + ε 1 + … + ε r , where ε 0 = ε ( C i , M , θ ) \varepsilon_0=\varepsilon(\mathcal{C}_i,M,\theta) ε 0 = ε ( C i , M , θ )
ε i : = ε ( C i , 1 , B i , θ ) + 1 ∣ F ∣ , \varepsilon_i:=\varepsilon(\mathcal{C}_i,1,B_i,\theta)+\frac{1}{|F|}, ε i := ε ( C i , 1 , B i , θ ) + ∣ F ∣ 1 , with ε ( C i , 1 , B i , θ ) \varepsilon(\mathcal{C}_i,1,B_i,\theta) ε ( C i , 1 , B i , θ ) B i = ∣ D ∣ ∣ D i ∣ = 2 i B_i=\frac{|D|}{|D_i|}=2^i B i = ∣ D i ∣ ∣ D ∣ = 2 i ( g 0 , … , g M ) (g_0,\ldots,g_M) ( g 0 , … , g M ) R \mathcal{R} R
引理中提到的 [H24, Theorem 3] 就是在 list decoding 下针对 subcode 的 correlated agreement 定理，而 [H24, Theorem 4] 就是 [H24, Theorem 3] 的 weighted 版本。
关系 R \mathcal{R} R P ∗ P^* P ∗ ( g 0 , … , g M ) (g_{0}, \ldots, g_{M}) ( g 0 , … , g M ) ω ⃗ = ( ω 1 , … , ω n ) \vec{\omega} = (\omega_1, \ldots, \omega_n) ω = ( ω 1 , … , ω n ) v 0 , … , v M v_0, \ldots, v_M v 0 , … , v M
R = { ∃ p 0 , … , p M ∈ F [ X ] < 2 n s.t. ( g 0 , … , g M ) : d ( ( g 0 , … , g M ) , ( p 0 , … , p M ) ) < θ ∧ ⋀ k = 0 M P k ( ω 1 , … , ω n ) = v k } . \mathcal{R}=\left\{\begin{array}{c}
\exists p_0, \ldots, p_M \in \mathscr{F}[X]^{<2^n} \text { s.t. } \\
\left(g_0, \ldots, g_M\right): d\left(\left(g_0, \ldots, g_M\right),\left(p_0, \ldots, p_M\right)\right)<\theta \\
\wedge \bigwedge_{k=0}^M P_k\left(\omega_1, \ldots, \omega_n\right)=v_k
\end{array}\right\}. R = ⎩ ⎨ ⎧ ∃ p 0 , … , p M ∈ F [ X ] < 2 n s.t. ( g 0 , … , g M ) : d ( ( g 0 , … , g M ) , ( p 0 , … , p M ) ) < θ ∧ ⋀ k = 0 M P k ( ω 1 , … , ω n ) = v k ⎭ ⎬ ⎫ . Lemma 1 说明的就是如果 P ∗ P^* P ∗ ε C \varepsilon_C ε C P ∗ P^* P ∗ R \mathcal{R} R
在这里，还需要用数学语言去定义 P ∗ P^* P ∗ 0 ≤ r ≤ n 0 \le r \le n 0 ≤ r ≤ n P ∗ P^* P ∗ P ∗ P^* P ∗ f 0 , Λ 0 , f 1 , Λ 1 , f 2 , Λ 2 , … , Λ r − 1 , f r f_0, \Lambda_0, f_1, \Lambda_1, f_2, \Lambda_2, \ldots, \Lambda_{r-1}, f_r f 0 , Λ 0 , f 1 , Λ 1 , f 2 , Λ 2 , … , Λ r − 1 , f r D 0 D_0 D 0 x x x α = 1 − θ ∈ ( 0 , 1 ) \alpha = 1 - \theta \in (0,1) α = 1 − θ ∈ ( 0 , 1 )
α = ( 1 + 1 2 ⋅ m ) ⋅ ρ \alpha = \left(1 + \frac{1}{2 \cdot m}\right) \cdot \sqrt{\rho} α = ( 1 + 2 ⋅ m 1 ) ⋅ ρ 用 F i \mathcal{F}_i F i C i = R S 2 n − i [ F , D i ] \mathcal{C}_i = \mathrm{RS}_{2^{n-i}}[F, D_i] C i = RS 2 n − i [ F , D i ] D i D_i D i D D D i i i D i = π i ( D ) , i = 0 , … , n D_i = \pi^i(D), i = 0, \ldots, n D i = π i ( D ) , i = 0 , … , n C i ′ ⊆ C i \mathcal{C}_i' \subseteq \mathcal{C}_i C i ′ ⊆ C i
F i ′ = { p ( X ) ∈ F i : P ( ω i + 1 , … , ω n ) = 0 } . \mathcal{F}_i' = \left\{p(X) \in \mathcal{F}_i: P(\omega_{i + 1}, \ldots, \omega_n) = 0 \right\}. F i ′ = { p ( X ) ∈ F i : P ( ω i + 1 , … , ω n ) = 0 } . sumcheck 检查正确。意味着存在 p r ( X ) ∈ F r p_r(X) \in \mathcal{F}_r p r ( X ) ∈ F r P r P_r P r
L ( ( ω 1 , … , ω r ) , ( λ 1 , … , λ r ) ) ⋅ P r ( ω 1 , … , ω n ) = q r − 1 ( λ r ) L((\omega_1, \ldots, \omega_r), (\lambda_1, \ldots, \lambda_r)) \cdot P_r(\omega_1, \ldots, \omega_n) = q_{r-1}(\lambda_r) L (( ω 1 , … , ω r ) , ( λ 1 , … , λ r )) ⋅ P r ( ω 1 , … , ω n ) = q r − 1 ( λ r ) 根据 q i ( X ) q_i(X) q i ( X ) Λ i ( X ) \Lambda_i(X) Λ i ( X ) P r P_r P r
L ( ( ω 1 , … , ω r ) , ( λ 1 , … , λ r ) ) ⋅ P r ( ω r + 1 , … , ω n ) = q r − 1 ( λ r ) = L ( ( ω 1 , … , ω r ) , ( λ 1 , … , λ r ) ) ⋅ Λ r − 1 ( λ r ) (1) \begin{aligned}
L((\omega_1, \ldots, \omega_r), (\lambda_1, \ldots, \lambda_r)) \cdot & P_r(\omega_{r + 1}, \ldots, \omega_n) = q_{r-1}(\lambda_r) \\
& = L((\omega_1, \ldots, \omega_r), (\lambda_1, \ldots, \lambda_r)) \cdot \Lambda_{r - 1}(\lambda_r)
\end{aligned} \tag{1} L (( ω 1 , … , ω r ) , ( λ 1 , … , λ r )) ⋅ P r ( ω r + 1 , … , ω n ) = q r − 1 ( λ r ) = L (( ω 1 , … , ω r ) , ( λ 1 , … , λ r )) ⋅ Λ r − 1 ( λ r ) ( 1 ) 折叠正确。需要满足
∣ { x ∈ D 0 : ( f 0 , … , f r ) satisfy all folding checks along x ∧ f r ( π r ( x ) ) = p r ( π r ( x ) ) } ∣ ≥ α ⋅ ∣ D 0 ∣ (2) \left| \left\{ x \in D_0 : \quad \begin{array}{c}
(f_0, \ldots, f_r) \text{ satisfy all folding checks along } x \\
\wedge f_r(\pi^r(x)) = p_r(\pi^r(x))
\end{array}\right\}\right| \ge \alpha \cdot |D_0| \tag{2} ∣ ∣ { x ∈ D 0 : ( f 0 , … , f r ) satisfy all folding checks along x ∧ f r ( π r ( x )) = p r ( π r ( x )) } ∣ ∣ ≥ α ⋅ ∣ D 0 ∣ ( 2 ) 这里只有当在 D 0 D_0 D 0 x x x π r \pi^r π r
当满足 1 和 2 两个条件时，就说这样的 ( f 0 , Λ 0 , f 1 , Λ 1 , f 2 , Λ 2 , … , Λ r − 1 , f r ) (f_0, \Lambda_0, f_1, \Lambda_1, f_2, \Lambda_2, \ldots, \Lambda_{r-1}, f_r) ( f 0 , Λ 0 , f 1 , Λ 1 , f 2 , Λ 2 , … , Λ r − 1 , f r ) ( λ 0 , … , λ r ) (\lambda_0, \ldots, \lambda_r) ( λ 0 , … , λ r )
Lemma 1 证明 ¶ Lemma 1 的证明采用的是数学归纳法，先证明当 r = 0 r = 0 r = 0 0 ≤ r < n 0 \le r < n 0 ≤ r < n r + 1 r + 1 r + 1 r + 1 r + 1 r + 1 λ r + 1 \lambda_{r + 1} λ r + 1 f r + 1 f_{r + 1} f r + 1 f r + 1 ′ f_{r + 1}' f r + 1 ′ f r , 0 f_{r,0} f r , 0 f r , 1 f_{r,1} f r , 1 f r f_r f r r r r r r r r + 1 r + 1 r + 1
证明：首先证明当 r = 0 r = 0 r = 0 P ∗ P^* P ∗ ε ( C 0 , M , θ ) \varepsilon(\mathcal{C}_0,M,\theta) ε ( C 0 , M , θ ) ( g 1 , … , g M ) ∈ R (g_1, \ldots, g_M) \in \mathcal{R} ( g 1 , … , g M ) ∈ R ε ( C 0 , M , θ ) \varepsilon(\mathcal{C}_0,M,\theta) ε ( C 0 , M , θ ) P ∗ P^* P ∗ f 0 f_0 f 0 λ 0 \lambda_0 λ 0 g k ′ = g k − v k g_k' = g_k - v_k g k ′ = g k − v k C 0 ′ ⊆ C 0 \mathcal{C}_0' \subseteq \mathcal{C}_0 C 0 ′ ⊆ C 0
Pr [ λ 0 : ∃ p 0 ′ ∈ F 0 ′ s.t. a g r e e ( ∑ k = 0 M g k ′ ⋅ λ 0 k , p 0 ′ ( X ) ) ≥ α ] > ε ( C 0 , M , θ ) \Pr \left[ \lambda_0: \exists p_0' \in \mathcal{F}_0' \text{ s.t. } \mathrm{agree} \left( \sum_{k = 0}^{M} g_k' \cdot \lambda_0^k, p_0'(X) \right) \ge \alpha \right] > \varepsilon(\mathcal{C}_0,M,\theta) Pr [ λ 0 : ∃ p 0 ′ ∈ F 0 ′ s.t. agree ( k = 0 ∑ M g k ′ ⋅ λ 0 k , p 0 ′ ( X ) ) ≥ α ] > ε ( C 0 , M , θ ) 这里考虑的是多项式 g k ′ = g k − v k g_k' = g_k - v_k g k ′ = g k − v k g k g_k g k C 0 ′ \mathcal{C}_0' C 0 ′
p 0 ′ ( X ) , … , p M ′ ( X ) ∈ F 0 ′ p_0'(X), \ldots, p_M'(X) \in \mathcal{F}_0' p 0 ′ ( X ) , … , p M ′ ( X ) ∈ F 0 ′ 以及存在集合 D 0 ′ ⊆ D D_0' \subseteq D D 0 ′ ⊆ D
∣ D 0 ′ ∣ / ∣ D ∣ ≥ α |D_0'|/|D| \ge \alpha ∣ D 0 ′ ∣/∣ D ∣ ≥ α p k ′ ( X ) ∣ D 0 ′ = g k ′ ( X ) ∣ D 0 ′ p_k'(X)|_{D_0'} = g_k'(X)|_{D_0'} p k ′ ( X ) ∣ D 0 ′ = g k ′ ( X ) ∣ D 0 ′ 现在找到了多项式 p 0 ′ ( X ) , … , p M ′ ( X ) p_0'(X), \ldots, p_M'(X) p 0 ′ ( X ) , … , p M ′ ( X )
p 0 ′ ( X ) + v 0 , … , p M ′ ( X ) + v M ∈ F 0 p_0'(X) + v_0, \ldots, p_M'(X) + v_M \in \mathcal{F}_0 p 0 ′ ( X ) + v 0 , … , p M ′ ( X ) + v M ∈ F 0 就满足
( p k ′ ( X ) + v k ) ∣ D 0 ′ = ( g k ′ ( X ) + v k ) ∣ D 0 ′ = g k ( X ) ∣ D 0 ′ 0 ≤ k ≤ M (p_k'(X) + v_k)|_{D_0'} = (g_k'(X) + v_k)|_{D_0'} = g_k(X)|_{D_0'} \quad 0 \le k \le M ( p k ′ ( X ) + v k ) ∣ D 0 ′ = ( g k ′ ( X ) + v k ) ∣ D 0 ′ = g k ( X ) ∣ D 0 ′ 0 ≤ k ≤ M p 0 ′ ( X ) + v 0 p_0'(X) + v_0 p 0 ′ ( X ) + v 0 P k ∈ F [ X 1 , … , X n ] P_k \in F[X_1, \ldots, X_n] P k ∈ F [ X 1 , … , X n ] P k ( ω ⃗ ) = v k P_k(\vec{\omega}) = v_k P k ( ω ) = v k ( g 1 , … , g M ) ∈ R (g_1, \ldots, g_M) \in \mathcal{R} ( g 1 , … , g M ) ∈ R
现在假设引理在 0 ≤ r < n 0 \le r < n 0 ≤ r < n r + 1 r + 1 r + 1 r + 1 r + 1 r + 1 P ∗ P^* P ∗ ( ε 0 + ε 1 + … + ε r ) + ε r + 1 (\varepsilon_0 + \varepsilon_1 + \ldots + \varepsilon_r) + \varepsilon_{r + 1} ( ε 0 + ε 1 + … + ε r ) + ε r + 1 t r r = ( λ 0 , f 0 , Λ 0 , … , λ r , f r , Λ r ) \mathrm{tr}_r = (\lambda_0, f_0, \Lambda_0, \ldots, \lambda_r, f_r, \Lambda_r) tr r = ( λ 0 , f 0 , Λ 0 , … , λ r , f r , Λ r ) T \mathfrak{T} T
Pr [ T ] > ε 0 + … + ε r \operatorname{Pr}[\mathfrak{T}]>\varepsilon_0+\ldots+\varepsilon_r Pr [ T ] > ε 0 + … + ε r 的条件下，P ∗ P^* P ∗ ε r + 1 \varepsilon_{r + 1} ε r + 1
Pr [ λ r + 1 : ∃ f r + 1 s.t. ( λ 0 , f 0 , Λ 0 , … , λ r , f r , Λ r , f r + 1 ) is α -good for ( λ 0 , … , λ r + 1 ) ] > ε r + 1 \Pr \left[ \lambda_{r+1}:
\begin{array}{c}
\exists f_{r + 1} \text{ s.t. } (\lambda_0, f_0, \Lambda_0, \ldots, \lambda_r, f_r, \Lambda_r, f_{r + 1}) \\
\text{is $\alpha$-good for } (\lambda_0, \ldots, \lambda_{r + 1})
\end{array}
\right] > \varepsilon_{r + 1} Pr [ λ r + 1 : ∃ f r + 1 s.t. ( λ 0 , f 0 , Λ 0 , … , λ r , f r , Λ r , f r + 1 ) is α -good for ( λ 0 , … , λ r + 1 ) ] > ε r + 1 由 α - good 的定义可以得到，对于满足 α -good 的 λ r + 1 \lambda_{r + 1} λ r + 1 p r + 1 ∈ F r + 1 p_{r + 1} \in \mathcal{F}_{r + 1} p r + 1 ∈ F r + 1
a g r e e ν r ( ( 1 − λ r + 1 ) ⋅ f r , 0 + λ r + 1 ⋅ f r , 1 , p r + 1 ) ≥ α (3) \mathrm{agree}_{\nu_r}((1 - \lambda_{r + 1}) \cdot f_{r,0} + \lambda_{r + 1} \cdot f_{r,1}, p_{r + 1}) \ge \alpha \tag{3} agree ν r (( 1 − λ r + 1 ) ⋅ f r , 0 + λ r + 1 ⋅ f r , 1 , p r + 1 ) ≥ α ( 3 ) 这里的 ν r \nu_r ν r y ∈ D r + 1 y \in D_{r + 1} y ∈ D r + 1
δ r ( y ) : = ∣ { x ∈ π − ( r + 1 ) ( y ) : ( f 0 , … , f r ) satisfies all folding checks along x } ∣ ∣ π − ( r + 1 ) ( y ) ∣ \delta_r(y) : = \frac{|\{x \in \pi^{-(r + 1)}(y): (f_0, \ldots, f_r) \text{ satisfies all folding checks along } x \}|}{|\pi^{-(r+1)}(y)|} δ r ( y ) := ∣ π − ( r + 1 ) ( y ) ∣ ∣ { x ∈ π − ( r + 1 ) ( y ) : ( f 0 , … , f r ) satisfies all folding checks along x } ∣ 这里解释下式 ( 3 ) (3) ( 3 ) ( 2 ) (2) ( 2 ) a g r e e \mathrm{agree} agree ( 3 ) (3) ( 3 )
ν r ( { y ∈ D r + 1 : ( ( 1 − λ r + 1 ) ⋅ f r , 0 + λ r + 1 ⋅ f r , 1 ) ( y ) = p r + 1 ( y ) } ) ∣ D r + 1 ∣ ≥ α \frac{\nu_r(\{ y \in D_{r + 1}: ((1 - \lambda_{r + 1}) \cdot f_{r,0} + \lambda_{r + 1} \cdot f_{r,1})(y) = p_{r + 1}(y)\})}{|D_{r + 1}|} \ge \alpha ∣ D r + 1 ∣ ν r ({ y ∈ D r + 1 : (( 1 − λ r + 1 ) ⋅ f r , 0 + λ r + 1 ⋅ f r , 1 ) ( y ) = p r + 1 ( y )}) ≥ α 先将在 D r + 1 D_{r + 1} D r + 1 y y y S r + 1 S_{r + 1} S r + 1 ν r \nu_r ν r
ν r ( S r + 1 ) = ∑ y ∈ S r + 1 δ r ( y ) = ∑ y ∈ S r + 1 ∣ { x ∈ π − ( r + 1 ) ( y ) : ( f 0 , … , f r ) satisfies all folding checks along x } ∣ ∣ π − ( r + 1 ) ( y ) ∣ = ∑ y ∈ S r + 1 ∣ { x ∈ π − ( r + 1 ) ( y ) : ( f 0 , … , f r ) satisfies all folding checks along x } ∣ 2 r + 1 : = ∑ y ∈ S r + 1 ∣ S y , 0 ∣ 2 r + 1 = ∑ y ∈ S r + 1 ∣ S y , 0 ∣ 2 r + 1 \begin{aligned}
\nu_r (S_{r + 1}) & = \sum_{y \in S_{r + 1}} \delta_r(y) \\
& = \sum_{y \in S_{r + 1}} \frac{|\{x \in \pi^{-(r + 1)}(y): (f_0, \ldots, f_r) \text{ satisfies all folding checks along } x \}|}{|\pi^{-(r+1)}(y)|} \\
& = \sum_{y \in S_{r + 1}} \frac{|\{x \in \pi^{-(r + 1)}(y): (f_0, \ldots, f_r) \text{ satisfies all folding checks along } x \}|}{2^{r + 1}} \\
& := \sum_{y \in S_{r + 1}} \frac{|S_{y,0}|}{2^{r + 1}} \\
& = \frac{\sum_{y \in S_{r + 1}} |S_{y,0}|}{2^{r + 1}}
\end{aligned} ν r ( S r + 1 ) = y ∈ S r + 1 ∑ δ r ( y ) = y ∈ S r + 1 ∑ ∣ π − ( r + 1 ) ( y ) ∣ ∣ { x ∈ π − ( r + 1 ) ( y ) : ( f 0 , … , f r ) satisfies all folding checks along x } ∣ = y ∈ S r + 1 ∑ 2 r + 1 ∣ { x ∈ π − ( r + 1 ) ( y ) : ( f 0 , … , f r ) satisfies all folding checks along x } ∣ := y ∈ S r + 1 ∑ 2 r + 1 ∣ S y , 0 ∣ = 2 r + 1 ∑ y ∈ S r + 1 ∣ S y , 0 ∣ 因此
a g r e e ν r ( ( 1 − λ r + 1 ) ⋅ f r , 0 + λ r + 1 ⋅ f r , 1 , p r + 1 ) = ν r ( S r + 1 ) ∣ D r + 1 ∣ = ∑ y ∈ S r + 1 ∣ S y , 0 ∣ 2 r + 1 ⋅ ∣ D r + 1 ∣ = ∑ y ∈ S r + 1 ∣ S y , 0 ∣ ∣ D 0 ∣ \begin{aligned}
\mathrm{agree}_{\nu_r}((1 - \lambda_{r + 1}) \cdot f_{r,0} + \lambda_{r + 1} \cdot f_{r,1}, p_{r + 1}) & = \frac{\nu_r(S_{r + 1})}{|D_{r + 1}|} \\
& = \frac{\sum_{y \in S_{r + 1}} |S_{y,0}|}{2^{r + 1} \cdot |D_{r + 1}|} \\
& = \frac{\sum_{y \in S_{r + 1}} |S_{y,0}|}{|D_{0}|}
\end{aligned} agree ν r (( 1 − λ r + 1 ) ⋅ f r , 0 + λ r + 1 ⋅ f r , 1 , p r + 1 ) = ∣ D r + 1 ∣ ν r ( S r + 1 ) = 2 r + 1 ⋅ ∣ D r + 1 ∣ ∑ y ∈ S r + 1 ∣ S y , 0 ∣ = ∣ D 0 ∣ ∑ y ∈ S r + 1 ∣ S y , 0 ∣ 上式中分子 ∑ y ∈ S r + 1 ∣ S y , 0 ∣ \sum_{y \in S_{r + 1}} |S_{y,0}| ∑ y ∈ S r + 1 ∣ S y , 0 ∣ D 0 D_0 D 0 r + 1 r + 1 r + 1 ( f 0 , … , f r ) (f_0, \ldots, f_r) ( f 0 , … , f r ) ( 3 ) (3) ( 3 )
∑ y ∈ S r + 1 ∣ S y , 0 ∣ ≥ α ⋅ ∣ D 0 ∣ \sum_{y \in S_{r + 1}} |S_{y,0}| \ge \alpha \cdot |D_{0}| y ∈ S r + 1 ∑ ∣ S y , 0 ∣ ≥ α ⋅ ∣ D 0 ∣ 这与 α -good 定义中式 ( 2 ) (2) ( 2 ) p r + 1 ( X ) p_{r+1}(X) p r + 1 ( X ) P r + 1 P_{r+1} P r + 1
L ( ( ω 1 , … , ω r + 1 ) , ( λ 1 , … , λ r + 1 ) ) ⋅ P r + 1 ( ω r + 2 , … , ω n ) = q r ( λ r + 1 ) = L ( ( ω 1 , … , ω r + 1 ) , ( λ 1 , … , λ r + 1 ) ) ⋅ Λ r ( λ r + 1 ) \begin{aligned}
L((\omega_1, \ldots, \omega_{r+1}), (\lambda_1, \ldots, \lambda_{r + 1})) \cdot & P_{r+1}(\omega_{r + 2}, \ldots, \omega_n) = q_{r}(\lambda_{r + 1}) \\
& = L((\omega_1, \ldots, \omega_{r + 1}), (\lambda_1, \ldots, \lambda_{r + 1})) \cdot \Lambda_{r}(\lambda_{r + 1})
\end{aligned} L (( ω 1 , … , ω r + 1 ) , ( λ 1 , … , λ r + 1 )) ⋅ P r + 1 ( ω r + 2 , … , ω n ) = q r ( λ r + 1 ) = L (( ω 1 , … , ω r + 1 ) , ( λ 1 , … , λ r + 1 )) ⋅ Λ r ( λ r + 1 ) 推出
L ( ( ω 1 , … , ω r ) , ( λ 1 , … , λ r ) ) ⋅ L ( ω r + 1 , λ r + 1 ) ⋅ P r + 1 ( ω r + 2 , … , ω n ) = L ( ( ω 1 , … , ω r ) , ( λ 1 , … , λ r ) ) ⋅ L ( ω r + 1 , λ r + 1 ) ⋅ Λ r ( λ r + 1 ) \begin{aligned}
L((\omega_1, \ldots, \omega_{r}), (\lambda_1, \ldots, \lambda_{r})) \cdot L(\omega_{r+1}, \lambda_{r + 1}) \cdot & P_{r+1}(\omega_{r + 2}, \ldots, \omega_n) \\
& = L((\omega_1, \ldots, \omega_{r}), (\lambda_1, \ldots, \lambda_{r})) \cdot L(\omega_{r+1}, \lambda_{r + 1}) \cdot \Lambda_{r}(\lambda_{r + 1})
\end{aligned} L (( ω 1 , … , ω r ) , ( λ 1 , … , λ r )) ⋅ L ( ω r + 1 , λ r + 1 ) ⋅ P r + 1 ( ω r + 2 , … , ω n ) = L (( ω 1 , … , ω r ) , ( λ 1 , … , λ r )) ⋅ L ( ω r + 1 , λ r + 1 ) ⋅ Λ r ( λ r + 1 ) 对于 λ r + 1 \lambda_{r + 1} λ r + 1 1 / ∣ F ∣ 1/|F| 1/∣ F ∣ L ( ω r + 1 , λ r + 1 ) = 0 L(\omega_{r+1}, \lambda_{r + 1}) = 0 L ( ω r + 1 , λ r + 1 ) = 0 1 / ∣ F ∣ 1/|F| 1/∣ F ∣
ε r + 1 − 1 ∣ F ∣ = ε ( C i + 1 , 1 , B r + 1 , θ ) \varepsilon_{r + 1} - \frac{1}{|F|} = \varepsilon(\mathcal{C}_{i + 1}, 1, B_{r + 1}, \theta) ε r + 1 − ∣ F ∣ 1 = ε ( C i + 1 , 1 , B r + 1 , θ ) 的概率，使得多项式 p r + 1 ′ = p r + 1 − Λ r ( λ r + 1 ) ∈ F r + 1 ′ p_{r+1}' = p_{r + 1} - \Lambda_r(\lambda_{r + 1}) \in \mathcal{F}_{r + 1}' p r + 1 ′ = p r + 1 − Λ r ( λ r + 1 ) ∈ F r + 1 ′ f r , 0 ′ = f r , 0 − Λ r ( 0 ) f_{r,0}' = f_{r,0} - \Lambda_r(0) f r , 0 ′ = f r , 0 − Λ r ( 0 ) f r , 1 ′ = f r , 1 − Λ r ( 1 ) f_{r,1}' = f_{r,1} - \Lambda_r(1) f r , 1 ′ = f r , 1 − Λ r ( 1 )
a g r e e ν r ( ( 1 − λ r + 1 ) ⋅ f r , 0 ′ + λ r + 1 ⋅ f r , 1 ′ , p r + 1 ′ ) ≥ α \mathrm{agree}_{\nu_r}((1 - \lambda_{r + 1}) \cdot f_{r,0}' + \lambda_{r + 1} \cdot f_{r,1}', p_{r + 1}') \ge \alpha agree ν r (( 1 − λ r + 1 ) ⋅ f r , 0 ′ + λ r + 1 ⋅ f r , 1 ′ , p r + 1 ′ ) ≥ α 上面满足的条件可以写为
Pr [ λ r + 1 : ∃ p r + 1 ′ ∈ F r + 1 ′ s.t. a g r e e ν r ( ( 1 − λ r + 1 ) ⋅ f r , 0 ′ + λ r + 1 ⋅ f r , 1 ′ , p r + 1 ′ ) ≥ α ] > ε ( C i + 1 , 1 , B r + 1 , θ ) \begin{aligned}
\Pr \left[ \lambda_{r+1}: \quad
\begin{array}{c}
\exists p_{r + 1}' \in \mathcal{F}_{r+1}' \text{ s.t. } \\
\mathrm{agree}_{\nu_r}((1 - \lambda_{r + 1}) \cdot f_{r,0}' + \lambda_{r + 1} \cdot f_{r,1}', p_{r + 1}') \ge \alpha
\end{array}
\right] > \varepsilon(\mathcal{C}_{i + 1}, 1, B_{r + 1}, \theta)
\end{aligned} Pr [ λ r + 1 : ∃ p r + 1 ′ ∈ F r + 1 ′ s.t. agree ν r (( 1 − λ r + 1 ) ⋅ f r , 0 ′ + λ r + 1 ⋅ f r , 1 ′ , p r + 1 ′ ) ≥ α ] > ε ( C i + 1 , 1 , B r + 1 , θ ) 这也就满足了 [H24, Theorem 4] 带权重的 correlated agreement 定理的条件，因此可以得到存在多项式 p r , 0 ′ ( X ) , p r , 1 ′ ( X ) ∈ F r + 1 ′ p_{r,0}'(X), p_{r,1}'(X) \in \mathcal{F}_{r+1}' p r , 0 ′ ( X ) , p r , 1 ′ ( X ) ∈ F r + 1 ′ A r + 1 ⊆ D r + 1 A_{r + 1} \subseteq D_{r+1} A r + 1 ⊆ D r + 1
ν r ( A r + 1 ) ≥ 1 − θ \nu_r(A_{r+1}) \ge 1 - \theta ν r ( A r + 1 ) ≥ 1 − θ p r , 0 ′ ( X ) ∣ A r + 1 = f r , 0 ′ ( X ) ∣ A r + 1 p_{r,0}'(X)|_{A_{r+1}} = f_{r,0}'(X)|_{A_{r+1}} p r , 0 ′ ( X ) ∣ A r + 1 = f r , 0 ′ ( X ) ∣ A r + 1 p r , 1 ′ ( X ) ∣ A r + 1 = f r , 1 ′ ( X ) ∣ A r + 1 p_{r,1}'(X)|_{A_{r+1}} = f_{r,1}'(X)|_{A_{r+1}} p r , 1 ′ ( X ) ∣ A r + 1 = f r , 1 ′ ( X ) ∣ A r + 1 现在已经找到了多项式 p r , 0 ′ ( X ) , p r , 1 ′ ( X ) p_{r,0}'(X), p_{r,1}'(X) p r , 0 ′ ( X ) , p r , 1 ′ ( X )
p r , 0 ( X ) = p r , 0 ′ ( X ) + Λ r ( 0 ) , p r , 1 ( X ) = p r , 1 ′ ( X ) + Λ r ( 1 ) ∈ F r + 1 p_{r,0}(X) = p_{r,0}'(X) + \Lambda_r(0), \quad p_{r,1}(X) = p_{r,1}'(X) + \Lambda_r(1) \in \mathcal{F}_{r+1} p r , 0 ( X ) = p r , 0 ′ ( X ) + Λ r ( 0 ) , p r , 1 ( X ) = p r , 1 ′ ( X ) + Λ r ( 1 ) ∈ F r + 1 而
f r , 0 ( X ) = f r , 0 ′ ( X ) + Λ r ( 0 ) , f r , 1 ( X ) = f r , 1 ′ ( X ) + Λ r ( 1 ) f_{r,0}(X) = f_{r,0}'(X) + \Lambda_r(0), \quad f_{r,1}(X) = f_{r,1}'(X) + \Lambda_r(1) f r , 0 ( X ) = f r , 0 ′ ( X ) + Λ r ( 0 ) , f r , 1 ( X ) = f r , 1 ′ ( X ) + Λ r ( 1 ) 根据 correlated agreement 给出的结论 2 ，可以得到
p r , 0 ( X ) ∣ A r + 1 = f r , 0 ( X ) ∣ A r + 1 , p r , 1 ( X ) ∣ A r + 1 = f r , 1 ( X ) ∣ A r + 1 p_{r,0}(X)|_{A_{r+1}} = f_{r,0}(X)|_{A_{r+1}}, \quad p_{r,1}(X)|_{A_{r+1}} = f_{r,1}(X)|_{A_{r+1}} p r , 0 ( X ) ∣ A r + 1 = f r , 0 ( X ) ∣ A r + 1 , p r , 1 ( X ) ∣ A r + 1 = f r , 1 ( X ) ∣ A r + 1 对于 p r , 0 ( X ) , p r , 1 ( X ) p_{r,0}(X), p_{r,1}(X) p r , 0 ( X ) , p r , 1 ( X ) P r , 0 P_{r,0} P r , 0 P r , 1 P_{r,1} P r , 1 F r ′ \mathcal{F}_{r}' F r ′
P r , 0 ( ω r + 2 , … , ω n ) = Λ r ( 0 ) P r , 1 ( ω r + 2 , … , ω n ) = Λ r ( 1 ) \begin{aligned}
P_{r,0}(\omega_{r+2}, \ldots, \omega_{n}) = \Lambda_r(0) \\
P_{r,1}(\omega_{r+2}, \ldots, \omega_{n}) = \Lambda_r(1)
\end{aligned} P r , 0 ( ω r + 2 , … , ω n ) = Λ r ( 0 ) P r , 1 ( ω r + 2 , … , ω n ) = Λ r ( 1 ) 将集合 A r + 1 A_{r+1} A r + 1 A r = π − 1 ( A r + 1 ) ⊆ D r A_r = \pi^{-1}(A_{r+1}) \subseteq D_r A r = π − 1 ( A r + 1 ) ⊆ D r f r f_r f r
p r ( X ) = p r , 0 ( X 2 ) + X ⋅ p r , 1 ( X 2 ) ∈ F r p_r(X) = p_{r,0}(X^2) + X \cdot p_{r,1}(X^2) \in \mathcal{F}_{r} p r ( X ) = p r , 0 ( X 2 ) + X ⋅ p r , 1 ( X 2 ) ∈ F r 是一致的。对于与 p r ( X ) p_r(X) p r ( X ) P r P_r P r
P r ( ω r + 1 , ω r + 2 , … , ω n ) = ( 1 − ω r + 1 ) ⋅ P r , 0 ( ω r + 2 , … , ω n ) + ω r + 1 ⋅ P r , 1 ( ω r + 2 , … , ω n ) = ( 1 − ω r + 1 ) ⋅ Λ r ( 0 ) + ω r + 1 ⋅ Λ r ( 1 ) = L ( ω r + 1 , 0 ) ⋅ Λ r ( 0 ) + L ( ω r + 1 , 1 ) ⋅ Λ r ( 1 ) \begin{aligned}
P_r(\omega_{r + 1}, \omega_{r + 2}, \ldots, \omega_n) & = (1 - \omega_{r + 1}) \cdot P_{r,0}(\omega_{r+2}, \ldots, \omega_{n}) + \omega_{r + 1} \cdot P_{r,1}(\omega_{r+2}, \ldots, \omega_{n}) \\
& = (1 - \omega_{r + 1}) \cdot \Lambda_r(0) + \omega_{r + 1} \cdot \Lambda_r(1) \\
& = L(\omega_{r + 1}, 0) \cdot \Lambda_r(0) + L(\omega_{r + 1}, 1) \cdot \Lambda_r(1)
\end{aligned} P r ( ω r + 1 , ω r + 2 , … , ω n ) = ( 1 − ω r + 1 ) ⋅ P r , 0 ( ω r + 2 , … , ω n ) + ω r + 1 ⋅ P r , 1 ( ω r + 2 , … , ω n ) = ( 1 − ω r + 1 ) ⋅ Λ r ( 0 ) + ω r + 1 ⋅ Λ r ( 1 ) = L ( ω r + 1 , 0 ) ⋅ Λ r ( 0 ) + L ( ω r + 1 , 1 ) ⋅ Λ r ( 1 ) 由此可以得到在第 r r r
L ( ω 1 , … , ω r , λ 1 , … , λ r ) ⋅ P r ( ω r + 1 , ω r + 2 , … , ω n ) = L ( ω 1 , … , ω r , λ 1 , … , λ r ) ⋅ L ( ω r + 1 , 0 ) ⋅ Λ r ( 0 ) + L ( ω 1 , … , ω r , λ 1 , … , λ r ) ⋅ L ( ω r + 1 , 1 ) ⋅ Λ r ( 1 ) = q r ( 0 ) + q r ( 1 ) = q r − 1 ( λ r ) \begin{aligned}
L(\omega_{1}, \ldots, \omega_{r}, \lambda_1, \ldots, \lambda_r) &\cdot P_r(\omega_{r + 1}, \omega_{r + 2}, \ldots, \omega_n) \\
& = L(\omega_{1}, \ldots, \omega_{r}, \lambda_1, \ldots, \lambda_r) \cdot L(\omega_{r + 1}, 0) \cdot \Lambda_r(0) \\
& \quad + L(\omega_{1}, \ldots, \omega_{r}, \lambda_1, \ldots, \lambda_r) \cdot L(\omega_{r + 1}, 1) \cdot \Lambda_r(1) \\
& = q_r(0) + q_r(1) \\
& = q_{r - 1}(\lambda_r)
\end{aligned} L ( ω 1 , … , ω r , λ 1 , … , λ r ) ⋅ P r ( ω r + 1 , ω r + 2 , … , ω n ) = L ( ω 1 , … , ω r , λ 1 , … , λ r ) ⋅ L ( ω r + 1 , 0 ) ⋅ Λ r ( 0 ) + L ( ω 1 , … , ω r , λ 1 , … , λ r ) ⋅ L ( ω r + 1 , 1 ) ⋅ Λ r ( 1 ) = q r ( 0 ) + q r ( 1 ) = q r − 1 ( λ r ) 现在得到了在第 r r r x ∈ π − 1 ( A r ) x \in \pi^{-1}(A_r) x ∈ π − 1 ( A r )
∣ { x ∈ π − r ( A r ) : all folding checks hold for f 0 , … , f r } ∣ ∣ D 0 ∣ = 1 ∣ D 0 ∣ ⋅ ∑ y ∈ A r + 1 δ ( y ) ⋅ ∣ π − ( r + 1 ) ( y ) ∣ = 2 r + 1 ∣ D 0 ∣ ⋅ ∑ y ∈ A r + 1 δ ( y ) = 1 ∣ D r + 1 ∣ ⋅ ∑ y ∈ A r + 1 δ ( y ) = ν r ( A r + 1 ) \begin{aligned}
& \frac{|\{x \in \pi^{-r}(A_r): \text{all folding checks hold for } f_0, \ldots, f_r \}|}{|D_0|} \\
& = \frac{1}{|D_0|} \cdot \sum_{y \in A_{r+1}} \delta(y) \cdot |\pi^{-(r+1)}(y)| \\
& = \frac{2^{r + 1}}{|D_0|} \cdot \sum_{y \in A_{r+1}} \delta(y) \\
& = \frac{1}{|D_{r + 1}|} \cdot \sum_{y \in A_{r+1}} \delta(y) \\
& = \nu_r(A_{r+1})
\end{aligned} ∣ D 0 ∣ ∣ { x ∈ π − r ( A r ) : all folding checks hold for f 0 , … , f r } ∣ = ∣ D 0 ∣ 1 ⋅ y ∈ A r + 1 ∑ δ ( y ) ⋅ ∣ π − ( r + 1 ) ( y ) ∣ = ∣ D 0 ∣ 2 r + 1 ⋅ y ∈ A r + 1 ∑ δ ( y ) = ∣ D r + 1 ∣ 1 ⋅ y ∈ A r + 1 ∑ δ ( y ) = ν r ( A r + 1 ) 前面通过 correlated agreement 定理已经得到 ν r ( A r + 1 ) ≥ α \nu_r(A_{r+1}) \ge \alpha ν r ( A r + 1 ) ≥ α D 0 D_0 D 0 x x x r r r ( f 0 , Λ 0 , … , f r , Λ r ) (f_0, \Lambda_0, \ldots, f_r, \Lambda_r) ( f 0 , Λ 0 , … , f r , Λ r ) ( λ 0 , … , λ r ) (\lambda_0, \ldots, \lambda_r) ( λ 0 , … , λ r )
Pr [ T ] > ε 0 + … + ε r \operatorname{Pr}[\mathfrak{T}]>\varepsilon_0+\ldots+\varepsilon_r Pr [ T ] > ε 0 + … + ε r 因此其满足引理的条件，由归纳假设，在第 r r r ( g 0 , … , g M ) ∈ R (g_0, \ldots, g_M) \in \mathcal{R} ( g 0 , … , g M ) ∈ R r + 1 r + 1 r + 1 \Box
References ¶ [H24] Ulrich Haböck. “Basefold in the List Decoding Regime.” Cryptology ePrint Archive (2024).