Fast amortized Kate proofs

1. 引言

具体见以太坊基金会Feist和khovratovich整理的Fast amortized Kate proofs 文档。

1.1 Setup

令 g g g 为 a group G \mathbb{G} G element。 [ a ] = a ⋅ g [a] = a\cdot g [a]=a⋅g 为a group element，其中 a a a 为integer。

令 s s s 为某秘密值，则 a universal setup of degree m m m 包含了 m m m 个 G \mathbb{G} G elements: [ s ] , [ s 2 ] , … , [ s m ] . [s], [s^2], \ldots, [s^m]. [s],[s2],…,[sm].

1.2 Commitment

令 f ( X ) = ∑ 0 ≤ i ≤ m f i X i f(X) = \sum_{0\leq i \leq m}f_i X^i f(X)=∑0≤i≤m​fi​Xi 为 degree为 m m m的多项式，则 commitment C f ∈ G C_f\in \mathbb{G} Cf​∈G 定义为： C f = ∑ 0 ≤ i ≤ m f i [ s i ] , C_f = \sum_{0\leq i \leq m} f_i[s^i], Cf​=0≤i≤m∑​fi​[si], 为 an evaluation of f f f at point s s s。

1.3 Kate Proof

对于任意的 y y y，都有 f ( X ) − f ( y ) f(X)-f(y) f(X)−f(y)可整除 ( X − y ) (X-y) (X−y)。因此，对 f ( y ) = z f(y)=z f(y)=z 的proof定义为： π [ f ( y ) = z ] = C T , \pi[f(y)=z] = C_T, π[f(y)=z]=CT​, 其中 T y ( X ) = f ( X ) − z X − y T_y(X) = \frac{f(X)-z}{X-y} Ty​(X)=X−yf(X)−z​ 为 degree为 ( m − 1 ) (m-1) (m−1)的多项式。

该proof可由group内的 m m m次scalar multiplication运算来获得。 T y ( X ) = ∑ 0 ≤ i ≤ m − 1 t i X i T_y(X)=\sum_{0\leq i \leq m-1}t_i X^i Ty​(X)=∑0≤i≤m−1​ti​Xi多项式的系数可按如下方式计算，每步有一个scalar multiplication运算： T y ( X ) = ∑ 0 ≤ i ≤ m − 1 t i X i ; (1) T_y(X) = \sum_{0\leq i \leq m-1}t_i X^i;\tag{1} Ty​(X)=0≤i≤m−1∑​ti​Xi;(1) t m − 1 = f m ; (2) t_{m-1} = f_m;\tag{2} tm−1​=fm​;(2) t j = f j + 1 + y ⋅ t j + 1 (3) t_j = f_{j+1}+y\cdot t_{j+1} \tag{3} tj​=fj+1​+y⋅tj+1​(3)

将最后一个等式展开，有： T y ( X ) = f m X m − 1 + ( f m − 1 + y f m ) X m − 2 + ( f m − 2 + y f m − 1 + y 2 f m ) X m − 3 + + ( f m − 3 + y f m − 2 + y 2 f m − 1 + y 3 ) X m − 4 + ⋯ + ( f 1 + y f 2 + y 2 f 3 + ⋯ + y m − 1 f m ) . (4) \begin{aligned} T_y(X) =f_mX^{m-1} + (f_{m-1}+yf_{m})X^{m-2} + (f_{m-2}+yf_{m-1}+y^2f_m)X^{m-3} +\\+ (f_{m-3}+yf_{m-2}+y^2f_{m-1}+y^3)X^{m-4}+\cdots + (f_{1}+yf_{2}+y^2f_3+\cdots+y^{m-1}f_m). \end{aligned}\tag{4} Ty​(X)=fm​Xm−1+(fm−1​+yfm​)Xm−2+(fm−2​+yfm−1​+y2fm​)Xm−3++(fm−3​+yfm−2​+y2fm−1​+y3)Xm−4+⋯+(f1​+yf2​+y2f3​+⋯+ym−1fm​).​(4)

2. Multiple proofs

令 w w w为 2 n 2^n 2n-th root of unity。接下来，将为 w , w 2 , w 3 , … , w 2 n = 1 w,w^2,w^3,\ldots, w^{2^n}=1 w,w2,w3,…,w2n=1构建Kate proof。

对 w k w^k wk的Kate proof为： π [ f ( w k ) = z k ] = C T w k = f m [ s m − 1 ] + ( f m − 1 + w k f m ) [ s m − 2 ] + ( f m − 2 + w k f m − 1 + w 2 k f m ) [ s m − 3 ] + + ( f m − 3 + w k f m − 2 + w 2 k f m − 1 + w 3 k ) [ s m − 4 ] + ⋯ + ( f 1 + w k f 2 + w 2 k f 3 + ⋯ + w ( m − 1 ) k f m ) . (5) \begin{aligned} \pi[f(w^k)=z^k] = C_{T_{w^k}} =f_m[s^{m-1}] + (f_{m-1}+w^kf_{m})[s^{m-2}] + (f_{m-2}+w^kf_{m-1}+w^{2k}f_m)[s^{m-3}] +\\+ (f_{m-3}+w^kf_{m-2}+w^{2k}f_{m-1}+w^{3k})[s^{m-4}]+\cdots + (f_{1}+w^kf_{2}+w^{2k}f_3+\cdots+w^{(m-1)k}f_m). \end{aligned}\tag{5} π[f(wk)=zk]=CTwk​​=fm​[sm−1]+(fm−1​+wkfm​)[sm−2]+(fm−2​+wkfm−1​+w2kfm​)[sm−3]++(fm−3​+wkfm−2​+w2kfm−1​+w3k)[sm−4]+⋯+(f1​+wkf2​+w2kf3​+⋯+w(m−1)kfm​).​(5)

将以上等式右侧各项进行重组，对于 2 n ≥ m 2^n\geq m 2n≥m，有： C T w k = ( f m [ s m − 1 ] + f m − 1 [ s m − 2 ] + f m − 2 [ s m − 3 ] + ⋯ + f 2 [ s ] + f 1 ) + + ( f m [ s m − 2 ] + f m − 1 [ s m − 3 ] + f m − 2 [ s m − 4 ] + ⋯ + f 3 [ s ] + f 2 ) w k + + ( f m [ s m − 3 ] + f m − 1 [ s m − 4 ] + f m − 2 [ s m − 5 ] + ⋯ + f 4 [ s ] + f 3 ) w 2 k + + ( f m [ s m − 4 ] + f m − 1 [ s m − 5 ] + f m − 2 [ s m − 6 ] + ⋯ + f 5 [ s ] + f 4 ) w 3 k + ⋯ + ( f m [ s ] + f m − 1 ) w ( m − 2 ) k + f m w ( m − 1 ) k . (6) \begin{aligned} C_{T_{w^k}} =&\left(f_m[s^{m-1}]+f_{m-1}[s^{m-2}]+f_{m-2}[s^{m-3}]+\cdots + f_2[s]+f_1\right)+\\ &+\left(f_m[s^{m-2}]+f_{m-1}[s^{m-3}]+f_{m-2}[s^{m-4}]+\cdots + f_3[s]+f_2\right)w^k+\\ &+\left(f_m[s^{m-3}]+f_{m-1}[s^{m-4}]+f_{m-2}[s^{m-5}]+\cdots + f_4[s]+f_3\right)w^{2k}+\\ &+\left(f_m[s^{m-4}]+f_{m-1}[s^{m-5}]+f_{m-2}[s^{m-6}]+\cdots + f_5[s]+f_4\right)w^{3k}+\\ &\cdots\\ &+(f_m[s]+f_{m-1})w^{(m-2)k}+f_mw^{(m-1)k}.\tag{6} \end{aligned} CTwk​​=​(fm​[sm−1]+fm−1​[sm−2]+fm−2​[sm−3]+⋯+f2​[s]+f1​)++(fm​[sm−2]+fm−1​[sm−3]+fm−2​[sm−4]+⋯+f3​[s]+f2​)wk++(fm​[sm−3]+fm−1​[sm−4]+fm−2​[sm−5]+⋯+f4​[s]+f3​)w2k++(fm​[sm−4]+fm−1​[sm−5]+fm−2​[sm−6]+⋯+f5​[s]+f4​)w3k+⋯+(fm​[s]+fm−1​)w(m−2)k+fm​w(m−1)k.​(6)

对于 1 ≤ i ≤ 2 n 1\leq i \leq 2^n 1≤i≤2n，定义： h i = ( f m [ s m − i ] + f m − 1 [ s m − i − 1 ] + f m − 2 [ s m − i − 2 ] + ⋯ + f i + 1 [ s ] + f i ) h_i = \left(f_m[s^{m-i}]+f_{m-1}[s^{m-i-1}]+f_{m-2}[s^{m-i-2}]+\cdots + f_{i+1}[s]+f_i\right) hi​=(fm​[sm−i]+fm−1​[sm−i−1]+fm−2​[sm−i−2]+⋯+fi+1​[s]+fi​) 当 i > m i>m i>m时，有 h i = 0 h_i=0 hi​=0。

此时，可将 C T w k C_{T_{w^k}} CTwk​​表示为： C T w k = h 1 + h 2 w k + h 3 w 2 k + ⋯ + h m w ( m − 1 ) k . C_{T_{w^k}} = h_1 + h_2w^k + h_3w^{2k}+\cdots + h_mw^{(m-1)k}. CTwk​​=h1​+h2​wk+h3​w2k+⋯+hm​w(m−1)k.

回想下，对于系数 a = [ a 1 , a 2 , … , a 2 n ] \mathbf{a}=[a_1,a_2,\ldots,a_{2^n}] a=[a1​,a2​,…,a2n​]，经Discrete Fourier Transform转换为点值表示为： a ^ = [ a 1 ^ , a 2 ^ , … , a 2 n ^ ] \widehat{\mathbf{a}}= [\widehat{a_1},\widehat{a_2},\ldots,\widehat{a_{2^n}}] a =[a1​ ​,a2​ ​,…,a2n​ ​] 其中： a k ^ = ∑ i a i w k i \widehat{a_k} = \sum_{i}a_iw^{ki} ak​ ​=i∑​ai​wki

因此，对于 h = [ h 1 , h 2 , … , h 2 n ] \mathbf{h} = [h_1,h_2,\ldots,h_{2^n}] h=[h1​,h2​,…,h2n​] 和 C T w k C_{T_{w^k}} CTwk​​，可将 C T = [ C T w 1 , C T w 2 , … , C T w 2 n ] \mathbf{C}_T = [C_{T_{w^1}},C_{T_{w^2}},\ldots,C_{T_{w^{2^n}}}] CT​=[CTw1​​,CTw2​​,…,CTw2n​​] 看成是对 h \mathbf{h} h的点值表示，采用FFT算法，计算cost为 O ( n 2 n ) O(n2^n) O(n2n)：【此时要求 m ≤ 2 n m\leq 2^n m≤2n，若 m > 2 n m>2^n m>2n，向量 h \mathbf{h} h可稍作调整——“wrapping around” the extra ≠ 0 \neq 0 ​=0 terms，然后也成立。】 C T = D F T ( h ) \mathbf{C}_T = \mathrm{DFT}(\mathbf{h}) CT​=DFT(h)

2.1 计算 h \mathbf{h} h

假设 m = O ( 2 n ) m=O(2^n) m=O(2n)。 以上等式 ( 6 ) (6) (6)中，若直接计算 h \mathbf{h} h，计算cost为 O ( 2 2 n ) O(2^{2n}) O(22n)。

可进一步优化，将 ( h ) \mathbf(h) (h)计算表示为： [ h 1 h 2 h 3 ⋮ h m − 1 h m ] = [ f m f m − 1 f m − 2 f m − 3 ⋯ f 1 0 f m f m − 1 f m − 2 ⋯ f 2 0 0 f m f m − 1 ⋯ f 3 ⋱ 0 0 0 0 ⋯ f m − 1 0 0 0 0 ⋯ f m ] ⋅ [ [ s m − 1 ] [ s m − 2 ] [ s m − 3 ] ⋮ [ s ] 1 ] \begin{bmatrix} h_1\\ h_2\\ h_3\\ \vdots\\ h_{m-1}\\ h_m \end{bmatrix}= \begin{bmatrix} f_m &f_{m-1}&f_{m-2}&f_{m-3}&\cdots & f_1\\ 0& f_m &f_{m-1}&f_{m-2}&\cdots & f_2\\ 0 & 0& f_m &f_{m-1}&\cdots & f_3\\ &&\ddots&&&\\ 0 & 0& 0 &0&\cdots & f_{m-1}\\ 0 & 0& 0 &0&\cdots & f_m\\ \end{bmatrix}\cdot\begin{bmatrix} [s^{m-1}]\\ [s^{m-2}]\\ [s^{m-3}]\\ \vdots\\ [s]\\ 1 \end{bmatrix} ⎣⎢⎢⎢⎢⎢⎢⎢⎡​h1​h2​h3​⋮hm−1​hm​​⎦⎥⎥⎥⎥⎥⎥⎥⎤​=⎣⎢⎢⎢⎢⎢⎢⎡​fm​0000​fm−1​fm​000​fm−2​fm−1​fm​⋱00​fm−3​fm−2​fm−1​00​⋯⋯⋯⋯⋯​f1​f2​f3​fm−1​fm​​⎦⎥⎥⎥⎥⎥⎥⎤​⋅⎣⎢⎢⎢⎢⎢⎢⎢⎡​[sm−1][sm−2][sm−3]⋮[s]1​⎦⎥⎥⎥⎥⎥⎥⎥⎤​

其中矩阵 A = [ f m f m − 1 f m − 2 f m − 3 ⋯ f 1 0 f m f m − 1 f m − 2 ⋯ f 2 0 0 f m f m − 1 ⋯ f 3 ⋯ 0 0 0 0 ⋯ f m − 1 0 0 0 0 ⋯ f m ] A = \begin{bmatrix} f_m &f_{m-1}&f_{m-2}&f_{m-3}&\cdots & f_1\\ 0& f_m &f_{m-1}&f_{m-2}&\cdots & f_2\\ 0 & 0& f_m &f_{m-1}&\cdots & f_3\\ &&\cdots&&&\\ 0 & 0& 0 &0&\cdots & f_{m-1}\\ 0 & 0& 0 &0&\cdots & f_m\\ \end{bmatrix} A=⎣⎢⎢⎢⎢⎢⎢⎡​fm​0000​fm−1​fm​000​fm−2​fm−1​fm​⋯00​fm−3​fm−2​fm−1​00​⋯⋯⋯⋯⋯​f1​f2​f3​fm−1​fm​​⎦⎥⎥⎥⎥⎥⎥⎤​ 为Toeplitz矩阵。根据 http://www.netlib.org/utk/people/JackDongarra/etemplates/node384.html 中的FFT算法可知，向量 与 m × m m\times m m×m Toeplitz矩阵 相乘 的cost为 O ( m log ⁡ m ) O(m\log m) O(mlogm)。

因此，根据 S R S SRS SRS来计算 h \mathbf{h} h，然后计算所有 2 n 2^n 2n个Kate proof（即 C T \mathbf{C}_T CT​），仅需要 O ( n 2 n ) O(n2^n) O(n2n)次scalar multiplication。

3. Multi-reveal

令 ψ ∈ F p \psi\in\mathbb{F}_p ψ∈Fp​为 ℓ \ell ℓ-th root of unity，有 ψ ℓ = 1 \psi^{\ell}=1 ψℓ=1。

针对的场景为： 想reveal多个polynomial evaluations f ( y ) = z 0 f(y) = z_0 f(y)=z0​, f ( ψ y ) = z 1 f(\psi y) = z_1 f(ψy)=z1​, … \ldots …, f ( ψ ℓ − 1 y ) = z ℓ − 1 f(\psi^{\ell-1} y)=z_{\ell - 1} f(ψℓ−1y)=zℓ−1​

注意有： ( x − y ) ⋅ ( x − ψ y ) ⋯ ( x − ψ ℓ − 1 y ) = x ℓ − y ℓ (x-y)\cdot(x-\psi y) \cdots (x - \psi^{\ell-1} y) = x^\ell - y^\ell (x−y)⋅(x−ψy)⋯(x−ψℓ−1y)=xℓ−yℓ

因此，相应的proof为计算多项式： g ( x ) = f ( x ) / / ( x ℓ − y ℓ ) g(x) = f(x) // (x^\ell - y^\ell) g(x)=f(x)//(xℓ−yℓ) 其中 / / // // 表示the truncated long division，然后计算proof： π [ f ( y ) = z 0 , … , f ( ψ ℓ − 1 y ) = z ℓ − 1 ] = [ g ( s ) ] \pi[f(y) = z_0, \ldots, f(\psi^{\ell-1}y)=z_{\ell - 1}] = [g(s)] π[f(y)=z0​,…,f(ψℓ−1y)=zℓ−1​]=[g(s)]

根据现有值 插值 可获得 checking polynomial h ( x ) = f ( x ) m o d    ( x ℓ − y ℓ ) h(x)=f(x)\mod (x^\ell-y^\ell) h(x)=f(x)mod(xℓ−yℓ)，然后验证如下方程式成立即可： e ( C f , ⋅ ) = e ( π [ f ( y ) = z 0 , … , f ( ψ ℓ − 1 y ) = z ℓ − 1 ] , [ s ℓ − y ℓ ] ) e ( h ( s ) , ⋅ ) e(C_f, \cdot) = e(\pi[f(y) = z_0, \ldots, f(\psi^{\ell-1}y)=z_{\ell - 1}], [s^\ell - y^\ell]) e(h(s),\cdot) e(Cf​,⋅)=e(π[f(y)=z0​,…,f(ψℓ−1y)=zℓ−1​],[sℓ−yℓ])e(h(s),⋅)

3.1 Multiple multi-reveals——奇数 ℓ \ell ℓ

将第节的multiproof进一步归纳为multiple multi-reveals。

令 w w w为 2 n 2^n 2n-th root of unity，需计算proofs： π [ f ( 1 ) , … , f ( ψ ℓ − 1 ) ] = C T w 0 , ℓ π [ f ( w ) , … , f ( w ψ ℓ − 1 ) ] = C T w 1 , ℓ ⋮ π [ f ( w 2 n − 1 ) , … , f ( w 2 n − 1 ψ ℓ − 1 ) ] = C T w 2 n − 1 , ℓ \begin{aligned} \pi[f(1), \ldots, f(\psi^{\ell-1})] &=& C_{T_{w^0, \ell}} \\ \pi[f(w), \ldots, f(w\psi^{\ell-1})] &=& C_{T_{w^1, \ell}} \\ &\vdots& \\ \pi[f(w^{2^n-1}), \ldots, f(w^{2^n-1}\psi^{\ell-1})] &=& C_{T_{w^{2^n-1}, \ell}} \end{aligned} π[f(1),…,f(ψℓ−1)]π[f(w),…,f(wψℓ−1)]π[f(w2n−1),…,f(w2n−1ψℓ−1)]​==⋮=​CTw0,ℓ​​CTw1,ℓ​​CTw2n−1,ℓ​​​

对 w k w^k wk的proof为： π [ f ( w k ) , … , f ( w k ψ ℓ − 1 ) ] = C T w k , ℓ = f m [ s m − ℓ ] + f m − 1 [ s m − ℓ − 1 ] + ⋯ + f m − ℓ + 1 [ s m − 2 ℓ + 1 ] + + ( f m − ℓ + w k ℓ f m ) [ s m − 2 ℓ ] + ( f m − ℓ − 1 + w k ℓ f m − 1 ) [ s m − 2 ℓ − 1 ] + ⋯ + ( f m − 2 ℓ + 1 + w k ℓ f m − ℓ + 1 ) [ s m − 3 ℓ + 1 ] + + ( f m − 2 ℓ + w k ℓ f m − ℓ + w 2 k ℓ f m ) [ s m − 3 ℓ ] + ( f m − 2 ℓ − 1 + w k ℓ f m − ℓ − 1 + w 2 k ℓ f m − 1 ) [ s m − 3 ℓ − 1 ] + ⋯ + ( f m − 3 ℓ + 1 + w k ℓ f m − 2 ℓ + 1 + w 2 k ℓ f m − ℓ + 1 ) [ s m − 4 ℓ + 1 ] + ⋮ \begin{aligned} \pi[f(w^k), \ldots, f(w^k\psi^{\ell-1})] = C_{T_{w^k,\ell}} =f_m[s^{m-\ell}] + f_{m-1}[s^{m-\ell - 1}] + \dots + f_{m-\ell+1}[s^{m-2\ell+1}] +\\+ (f_{m-\ell}+w^{k\ell}f_{m})[s^{m-2\ell}] + (f_{m-\ell-1}+w^{k\ell}f_{m-1})[s^{m-2\ell-1}] + \cdots + (f_{m-2\ell+1}+w^{k\ell}f_{m-\ell+1})[s^{m-3\ell+1}] +\\+ (f_{m-2\ell}+w^{k\ell}f_{m-\ell} +w^{2k\ell}f_{m})[s^{m-3\ell}] + (f_{m-2\ell-1}+w^{k\ell}f_{m-\ell-1} + w^{2k\ell}f_{m-1})[s^{m-3\ell-1}] + \\ \cdots + (f_{m-3\ell+1}+w^{k\ell}f_{m-2\ell+1}+w^{2k\ell}f_{m-\ell+1})[s^{m-4\ell+1}] +\\ \vdots \\ \end{aligned} π[f(wk),…,f(wkψℓ−1)]=CTwk,ℓ​​=fm​[sm−ℓ]+fm−1​[sm−ℓ−1]+⋯+fm−ℓ+1​[sm−2ℓ+1]++(fm−ℓ​+wkℓfm​)[sm−2ℓ]+(fm−ℓ−1​+wkℓfm−1​)[sm−2ℓ−1]+⋯+(fm−2ℓ+1​+wkℓfm−ℓ+1​)[sm−3ℓ+1]++(fm−2ℓ​+wkℓfm−ℓ​+w2kℓfm​)[sm−3ℓ]+(fm−2ℓ−1​+wkℓfm−ℓ−1​+w2kℓfm−1​)[sm−3ℓ−1]+⋯+(fm−3ℓ+1​+wkℓfm−2ℓ+1​+w2kℓfm−ℓ+1​)[sm−4ℓ+1]+⋮​

令 2 n ≥ m 2^n\geq m 2n≥m，对以上等式右侧各项重组，有： C T w k , ℓ = ( f m [ s m − ℓ ] + f m − 1 [ s m − ℓ − 1 ] + f m − 2 [ s m − ℓ − 2 ] + ⋯ + f ℓ + 1 [ s ] + f ℓ ) + + ( f m [ s m − 2 ℓ ] + f m − 1 [ s m − 2 ℓ − 1 ] + f m − 2 [ s m − 2 ℓ − 2 ] + ⋯ + f 2 ℓ + 1 [ s ] + f 2 ℓ ) w k ℓ + + ( f m [ s m − 3 ℓ ] + f m − 1 [ s m − 3 ℓ − 1 ] + f m − 2 [ s m − 3 ℓ − 2 ] + ⋯ + f 3 ℓ + 1 [ s ] + f 3 ℓ ) w 2 k ℓ + + ( f m [ s m − 4 ℓ ] + f m − 1 [ s m − 4 ℓ − 1 ] + f m − 2 [ s m − 4 ℓ − 2 ] + ⋯ + f 4 ℓ + 1 [ s ] + f 4 ℓ ) w 3 k ℓ + ⋮ ( ⋯   ) w ⌊ m / ℓ ⌋ k ℓ \begin{aligned} C_{T_{w^k,\ell}} =&\left(f_m[s^{m-\ell}]+f_{m-1}[s^{m-\ell -1}]+f_{m-2}[s^{m-\ell-2}]+\cdots + f_{\ell+1}[s]+f_\ell\right)+\\ &+\left(f_m[s^{m-2\ell}]+f_{m-1}[s^{m-2\ell-1}]+f_{m-2}[s^{m-2\ell-2}]+\cdots + f_{2\ell+1}[s]+f_{2\ell}\right)w^{k\ell}+\\ &+\left(f_m[s^{m-3\ell}]+f_{m-1}[s^{m-3\ell-1}]+f_{m-2}[s^{m-3\ell-2}]+\cdots + f_{3\ell+1}[s]+f_{3\ell}\right)w^{2k\ell}+\\ &+\left(f_m[s^{m-4\ell}]+f_{m-1}[s^{m-4\ell-1}]+f_{m-2}[s^{m-4\ell-2}]+\cdots + f_{4\ell+1}[s]+f_{4\ell}\right)w^{3k\ell}+\\ &\vdots \\ & (\cdots) w^{\lfloor m / \ell\rfloor k\ell} \end{aligned} CTwk,ℓ​​=​(fm​[sm−ℓ]+fm−1​[sm−ℓ−1]+fm−2​[sm−ℓ−2]+⋯+fℓ+1​[s]+fℓ​)++(fm​[sm−2ℓ]+fm−1​[sm−2ℓ−1]+fm−2​[sm−2ℓ−2]+⋯+f2ℓ+1​[s]+f2ℓ​)wkℓ++(fm​[sm−3ℓ]+fm−1​[sm−3ℓ−1]+fm−2​[sm−3ℓ−2]+⋯+f3ℓ+1​[s]+f3ℓ​)w2kℓ++(fm​[sm−4ℓ]+fm−1​[sm−4ℓ−1]+fm−2​[sm−4ℓ−2]+⋯+f4ℓ+1​[s]+f4ℓ​)w3kℓ+⋮(⋯)w⌊m/ℓ⌋kℓ​ 对于 i ≥ 1 i\geq 1 i≥1，有：【当 i > m i>m i>m，有 h i = 0 h_i=0 hi​=0。】 h i = ( f m [ s m − i ] + f m − 1 [ s m − i − 1 ] + f m − 2 [ s m − i − 2 ] + ⋯ + f i + 1 [ s ] + f i ) . h_i = \left(f_m[s^{m-i}]+f_{m-1}[s^{m-i-1}]+f_{m-2}[s^{m-i-2}]+\cdots + f_{i+1}[s]+f_i\right). hi​=(fm​[sm−i]+fm−1​[sm−i−1]+fm−2​[sm−i−2]+⋯+fi+1​[s]+fi​). 从而有： C T w k , ℓ = h ℓ + h 2 ℓ w k ℓ + h 3 ℓ w 2 k ℓ + ⋯ + h m ℓ w ( m − 1 ) k ℓ (28) C_{T_{w^k,\ell}} = h_\ell + h_{2\ell}w^{k\ell} + h_{3\ell}w^{2k\ell}+\cdots + h_{m\ell}w^{(m-1)k\ell} \tag{28} CTwk,ℓ​​=hℓ​+h2ℓ​wkℓ+h3ℓ​w2kℓ+⋯+hmℓ​w(m−1)kℓ(28)

令： C T ℓ = [ C T w , ℓ , C T w 2 , ℓ , … , C T w 2 n , ℓ ] \mathbf{C}_{T_\ell} = [C_{T_{w, \ell}},C_{T_{w^{2}, \ell}},\ldots,C_{T_{w^{2^n}, \ell}}] CTℓ​​=[CTw,ℓ​​,CTw2,ℓ​​,…,CTw2n,ℓ​​] 以及 h ℓ = [ h ℓ , 0 h ℓ + 1 , … , 0 h 2 ℓ − 1 , h 2 ℓ , 0 h 2 ℓ + 1 , … , 0 h 3 ℓ − 1 , h 3 ℓ + 1 , 0 h 3 ℓ + 1 , … , 0 h 2 n + ℓ − 1 ] . \mathbf{h_\ell} = [h_\ell,0h_{\ell+1},\ldots,0h_{2\ell-1},h_{2\ell},0h_{2\ell+1},\ldots,0h_{3\ell-1},h_{3\ell+1},0h_{3\ell+1},\ldots,0h_{2^n+\ell-1}]. hℓ​=[hℓ​,0hℓ+1​,…,0h2ℓ−1​,h2ℓ​,0h2ℓ+1​,…,0h3ℓ−1​,h3ℓ+1​,0h3ℓ+1​,…,0h2n+ℓ−1​].

根据 h ℓ \mathbf{h_{\ell}} hℓ​，采用FFT算法，计算 C T ℓ \mathbf{C}_{T_{\ell}} CTℓ​​的计算cost为 O ( n 2 n ) O(n2^n) O(n2n)： C T ℓ = D F T ( h ℓ ) \mathbf{C}_{T_\ell} = \mathrm{DFT}(\mathbf{h_\ell}) CTℓ​​=DFT(hℓ​)

3.1.1 计算 h ℓ \mathbf{h_\ell} hℓ​

对2.1节算法稍作调整，即可用于计算 h ℓ \mathbf{h_\ell} hℓ​。

首先定义： h ℓ , i ℓ , j = f m − j [ s m − i ℓ − j ] + f m − ℓ − j [ s m − ( i + 1 ) ℓ − j ] + f m − 2 ℓ − j [ s m − ( i + 2 ) ℓ − j ] + ⋯ + f ( m − j ) % ℓ + ( i + 1 ) ℓ [ s ( m − j ) % ℓ + ℓ ] + f ( m − j ) % ℓ + i ℓ [ s ( m − j ) % ℓ ] . \begin{aligned} \mathbf{h}_{\ell, i\ell, j} = f_{m-j}[s^{m-i\ell-j}] + f_{m-\ell-j}[s^{m-(i+1)\ell-j}] + f_{m-2\ell-j}[s^{m-(i+2)\ell-j}] + \cdots\\ + f_{(m - j) \% \ell + (i+1)\ell}[s^{(m-j)\% \ell + \ell}] + f_{(m - j) \% \ell + i\ell}[s^{(m-j)\% \ell}]. \end{aligned} hℓ,iℓ,j​=fm−j​[sm−iℓ−j]+fm−ℓ−j​[sm−(i+1)ℓ−j]+fm−2ℓ−j​[sm−(i+2)ℓ−j]+⋯+f(m−j)%ℓ+(i+1)ℓ​[s(m−j)%ℓ+ℓ]+f(m−j)%ℓ+iℓ​[s(m−j)%ℓ].​ 有： h i ℓ = ∑ j = 0 ℓ − 1 h ℓ , i ℓ , j \mathbf{h}_{i\ell} = \sum_{j=0}^{\ell-1}\mathbf{h}_{\ell, i\ell, j} hiℓ​=j=0∑ℓ−1​hℓ,iℓ,j​

h ℓ , i ℓ , j \mathbf{h}_{\ell, i\ell, j} hℓ,iℓ,j​可根据 ℓ \ell ℓ Toeplitz matrix multiplication计算： [ h ℓ , 1 ℓ , j h ℓ , 2 ℓ , j h ℓ , 3 ℓ , j ⋮ h ℓ , ( ⌊ m − j ℓ ⌋ − 1 ) ℓ , j h ℓ , ⌊ m − j ℓ ⌋ ℓ , j ] = [ f m − j f m − 1 ℓ − j f m − 2 ℓ − j f m − 3 ℓ − j ⋯ f ( m − j ) % ℓ + ℓ 0 f m − j f m − 1 ℓ − j f m − 2 ℓ − j ⋯ f ( m − j ) % ℓ + 2 ℓ 0 0 f m − j f m − 1 ℓ − j ⋯ f ( m − j ) % ℓ + 3 ℓ ⋱ 0 0 0 0 ⋯ f m − ℓ − j 0 0 0 0 ⋯ f m − j ] ⋅ [ [ s m − 1 ℓ − j ] [ s m − 2 ℓ − j ] [ s m − 3 ℓ − j ] ⋮ [ s ( m − j ) % ℓ + ℓ ] [ s ( m − j ) % ℓ ] ] \begin{bmatrix} h_{\ell,1\ell,j}\\ h_{\ell,2\ell,j}\\ h_{\ell,3\ell,j}\\ \vdots\\ h_{\ell,(\lfloor \frac{m-j}{\ell}\rfloor-1)\ell,j}\\ h_{\ell,\lfloor \frac{m-j}{\ell}\rfloor\ell,j} \end{bmatrix}= \begin{bmatrix} f_{m-j} &f_{m-1\ell-j}&f_{m-2\ell-j}&f_{m-3\ell-j}&\cdots & f_{(m - j) \% \ell + \ell}\\ 0& f_{m-j} &f_{m-1\ell-j}&f_{m-2\ell-j}&\cdots & f_{(m - j) \% \ell + 2\ell}\\ 0 & 0& f_{m-j} &f_{m-1\ell-j}&\cdots & f_{(m - j) \% \ell + 3\ell}\\ &&&&\ddots&\\ 0 & 0& 0 &0&\cdots & f_{m-\ell-j}\\ 0 & 0& 0 &0&\cdots & f_{m-j}\\ \end{bmatrix}\cdot\begin{bmatrix} [s^{m-1\ell-j}]\\ [s^{m-2\ell-j}]\\ [s^{m-3\ell-j}]\\ \vdots\\ [s^{(m-j)\% \ell + \ell}]\\ [s^{(m-j)\% \ell}] \end{bmatrix} ⎣⎢⎢⎢⎢⎢⎢⎢⎡​hℓ,1ℓ,j​hℓ,2ℓ,j​hℓ,3ℓ,j​⋮hℓ,(⌊ℓm−j​⌋−1)ℓ,j​hℓ,⌊ℓm−j​⌋ℓ,j​​⎦⎥⎥⎥⎥⎥⎥⎥⎤​=⎣⎢⎢⎢⎢⎢⎢⎡​fm−j​0000​fm−1ℓ−j​fm−j​000​fm−2ℓ−j​fm−1ℓ−j​fm−j​00​fm−3ℓ−j​fm−2ℓ−j​fm−1ℓ−j​00​⋯⋯⋯⋱⋯⋯​f(m−j)%ℓ+ℓ​f(m−j)%ℓ+2ℓ​f(m−j)%ℓ+3ℓ​fm−ℓ−j​fm−j​​⎦⎥⎥⎥⎥⎥⎥⎤​⋅⎣⎢⎢⎢⎢⎢⎢⎢⎡​[sm−1ℓ−j][sm−2ℓ−j][sm−3ℓ−j]⋮[s(m−j)%ℓ+ℓ][s(m−j)%ℓ]​⎦⎥⎥⎥⎥⎥⎥⎥⎤​

与2.1节类似，可采用FFT算法来计算。向量 与 Toeplitz矩阵 乘法与多项式系数无关，因此该FFT可提前预计算，在预计算中处理 ℓ \ell ℓ Fourier transforms of size 2 m / ℓ 2m/\ell 2m/ℓ。但是，the output of the multiplication can be added before transforming back，因此仅需要一次IFT of size 2 m / ℓ 2m/\ell 2m/ℓ。

3.2 Multiple multi-reveals—— ℓ \ell ℓ为power of two

令 ℓ = 2 r < 2 n \ell=2^r