这篇paper可能有一些抽象，大致思路和之前介绍基于纠错码的多项式承诺类似，可以看之前的博客$[4]$
Abstract
本文提出了NP语言的第一个线性Prover Time的SNARK，Prover构造证明时只需要$O(N)$次域运算（$N$表示R1CS实例大小），无需可信设置，且似乎满足后量子安全
Brakedown可以兼容任意满足大小的有限域，这是一个目前已知的证明系统中的新的性质
Brakedown借鉴了$[BCG20]$中基于线性时间编码的多项式承诺的相关思想，将其于线性时间交互式证明系统相结合，得到了一个线性时间IOP和对应的SNARK
除此之外，本文还基于RS码，实现了Brakedown的一个变体，本文称该变体为Shockwave，但是Shockwave不是线性时间的SNARK，不过它比Brakedown的证明大小和验证时间都要短
1 Introduction
目前阻碍SNARK应用于大型NP Statement的瓶颈之一为Prover的渐进和具体成本，使其难以应用于诸如加密货币这样的领域中
现有的SNARK基于有限域上的R1CS构建，R1CS不仅适用于概率检验，且还有很强的表达能力，之前的研究提出了多种将应用转换为R1CS的方案$[SVP+12,PGHR13,BFR+13,BCGT13,WSR+15,SAGL18a,LNS20,OBW20]$
本文的工作有两个重点，一是为基于R1CS的SNARK设计一个最快的Prover，并且Verifier最好可以达到亚线性阶，
本文的第二个工作是设计一个可以在任意（足够大的）有限域上执行的SNARK，之前的SNARK方案都需要对DLOG友好的或者FFT友好的域，或者需要一个或者多个特定大小的乘法或加法子群，因为这些方案需要基于这些子群上的一些假设来构建方案
然而许多应用场景并无法在这些域上进行计算，而且现有的大多数椭圆曲线群都是在对FFT操作不友好的域上进行设计的，即便是设计的SNARK协议有很好的灵活性，域的大小也会影响性能开销和证明大小
综上，本文设计了一个满足透明性的SNARK，而且似乎满足后量子安全，具有亚线性阶的证明大小和拟线性的运行时间
Formalizing fastest possible provers
SNARK的Prover到底可以有多快？以大小为$N$的R1CS为例，Prover至少需要读取整个实例，因此Prover的运行时间至少是$N$次域运算
所以SNARK中Prover的复杂度至少也得是线性阶的，只不过我们希望这个复杂度中的常数因子尽可能地小
目前的SNARK方案中，Prover的效率主要局限于下列一个或多个方面
- 对长度为$O(N)$的向量执行FFT
- 为长度为$O(N)$的向量构建Merkle Hash Tree
- 在群$\mathbb G$中执行规模为$O(N)$的群幂运算
FFT其实还好，因为最快的FFT算法的复杂度为$O(N\log N)$，主要是计算的域，域越大计算量也越大，而且FFT的算法有一个$\log N$的因子，不是线性阶的，如果想要实现线性阶的方案，肯定不能用FFT
其次是Merkle Tree，长度为$O(N)$的向量总共需要$O(N)$次Hash，这没啥大问题，但是关键在于对域元素的Hash的效率是否能与域运算的效率相比较，如果Hash效率比域运算高，那没啥问题，但是现在不太清楚标准Hash函数（比如SHA256）在对域元素计算时是否应当被视为一次
基于之前的工作，为了简化讨论的细节，本文可以认为实现本文Merkle Tree的Hash开销为线性阶的（不过从理论角度来说这并不严格）
最后是群幂运算，Pippenger算法的复杂度可以到$O(N\cdot \lambda /\log {(N\cdot \lambda)})$次群运算，与安全参数有关，如果说$\lambda$是$\omega(\log N)$，也即$2^\lambda$与$N$成超多项式关系，则上述复杂度可以视为$\omega(N)$次群运算，每个群运算的开销与域运算相当，但是事实上群运算的开销要比域运算慢好多倍，因此本文不认为这个过程是线性时间的
总而言之，本文不认为FFT和群幂运算为线性时间运算，Merkle Hash Tree可以认为是线性时间的
2 Preliminaries
- $\mathbb F$：
- $\lambda$：安全参数
- $[m]$：正整数集合$\{1,\dots,m\}$
- $g$：域上多项式
- $f:\{0,1\}^l\rarr \mathbb F$：映射
- $\tilde f$：上述映射的多线性扩展
- $\mathrm {Enc}:\mathbb F^m\rarr \mathbb F^N$：线性码的编码函数，该线性码的码率$\rho>0$，相对距离$\gamma >0$，本文采用的线性码为系统码（系统码的意思是信息元总是出现在码字中的固定位置，比如总是出现在码字的高$m$位）
本文还需要用到和校验协议的相关知识，具体可以看$[2]$
本文的R1CS关系定义如下
$$ \mathcal R_{R1CS}=\big\{ \lang (\mathbb F,A,B,C,\mathrm{io},m,n),w\rang :A\cdot (w,1,\mathrm{io})\circ B\cdot (w,1,\mathrm{io})=C\cdot (w,1,\mathrm{io}) \big\} $$
其中$A,B,C\in \mathbb F^{M\times M},M\geq |\mathrm{io}|+1$，矩阵$A,B,C$中至多有$N=\Omega(M)$个非零元素
不失一般性，本文假设$M,N$都是2的幂，且满足$M=|\mathrm{io}|+1$
本文的方案基于Spartan协议，该协议中，Prover每轮发送一个多项式作为预言机，且Verifier可以通过查询该多项式在某个随机点的求值进行验证
Brakedown的原文写了一堆Spartan的多项式IOP的形式化，这里略过，感兴趣的可以看之前的Spartan的博客$[3]$
3 Linear-Time Polynomial Commitments
线性时间的多项式承诺方案，基于$[BCG20]$这篇paper中的定理2
该定理表明，此类线性时间的承诺方案的承诺大小可以做到$O_{\lambda}(1)$，承诺算法的复杂度为$O(N)$次域运算，在非交互式RO模型下，Prover需要$O(N)$次域运算，Verifier验证需要$O_{\lambda}(N^{1/t})$次域运算，证明大小为$O_{\lambda}(N^{1/t})$（$t$为某个与承诺相关的参数）
然后接下来看一下这个参数$t$的相关内容，首先记$g$为一多线性多项式，包含$n$个系数（不失一般性假设$n=m^2$，如果不是也没关系），记$u$表示$g$的系数向量
这里可以知道，对于$g$的任意输入$r$，均存在两个向量$q_1,q_2\in \mathbb F^m$，使得$g(r)=\lang (q_1\otimes q_2),u \rang$，这里$\otimes$表示张量乘积，$\forall (i,j)\in [m]\times [m],(q_1 \otimes q_2)_{i,j}=q_{1,i}\cdot q_{2,j}$
然后我们将$u$视为一个$m\times m$的方阵，记该矩阵的第$i$行的行向量为$u_i=\{u_{i,j}\}_{i\in [m]}$，接下来看一下如何构造多项式承诺方案，分为三个阶段
Commitment Phase
承诺阶段中，首先利用编码函数$\mathrm{Enc}$，将矩阵按行进行编码，得到的码字矩阵记为$\hat u$，也即$\hat u=\{\mathrm{Enc}(u_i)\}_{i\in [m]}\in (\mathbb F^N)^m$
这里可以提一下IOP和普通模型与RO模型的区别：如果是IOP的话，Prover直接将码字矩阵$\hat u$发送给Verifier即可，Verifier再对码字矩阵进行一些随机查询
但是如果是普通模型或者RO模型，对$u$的承诺则是需要用到Merkle Tree的方式，先得到码字矩阵$\hat u$，然后再对码字矩阵的行向量进行承诺
Testing Phase
如果是IOP的Verifier，这里需要检查$\hat u$中的每一行都是$u$中对应行的一个码字
Verifier向Prover发送一个随机向量$r$，之后Prover计算这个随机向量与方阵$u$的乘积，得到一个目标向量$u'$（相当于$u'$是方阵$u$在向量$r$下的随即线性组合），Prover将$u'$返回给Verifier
Verifier收到$u'$后，需要检查其与$\hat u$的一致性，首先Verifier对$u'$进行编码，得到$\mathrm{Enc}(u')$，同时Verifier根据$r$和$\hat u$计算一个向量$v$
$$ v=\sum^m_{i=1}r_i\cdot \hat u_i $$
之后Verifier选择$\mathrm{Enc}(u')$中若干个（$l=\Theta(\lambda)$个）随机点，检查这些点是否都与向量$v$对应位置的值相等，若均相等，则一致性检查通过
这里用到了线性码的基本性质：码字之间的任意线性组合仍然是一个码字
Evaluation Phase
评估阶段的工作和测试阶段的工作其实差不多，只不过将随机向量$r$替换为了上面的$q_1$
这里记$u''$表示Prover在这个阶段发送的目标向量（和测试阶段的$u'$类似，只不过计算方式为$u''=\sum_i q_{1,i}\cdot u_i$）
这个步骤中，如果Prover是诚实的，则$u''$必然满足
$$ \lang u'',q_2 \rang=\lang (q_1\otimes q_2),u \rang $$
如果测试节点和评估阶段均通过验证，则Verifier输出$\lang u'',q_2\rang$
上述三个阶段的具体协议如下图所示
测试阶段可以在任何时候执行（可以在承诺阶段中顺便执行了，也可以在评估阶段之后，或者在两者之间）
Concrete Optimizations to the Commitment Scheme
这里可以在不影响正确性的前提下，对上述方案做一些优化，比如减少测试和评估阶段的证明大小
- 和前面提到的一样，测试和评估这两个阶段可以并行运行，且查询集$Q$在两个阶段中都可以用，这样一来可以将证明大小减少大约一半
- 前面提到了：不失一般性假设$n=m^2$，如果$u$不是方阵（$n\neq m^2$）也没关系，如果是方阵的话可以进一步减少测试和评估节点的证明大小
具体而言，令$r,c$分别表示$u$中的行数和列数，因此$u$包含的元素总数为$N=rc$，对应的承诺大小大约为$2c+r\cdot l$个域元素（$l$为码字矩阵中揭示的列的数量）
上面这个$2c$的向来自于Prover发送的两个不同的线性组合（分别是测试阶段的$u'$和评估阶段的$u''$），$r\cdot l$的项来自于Verifier的查询
为了尽可能缩短证明长度，一种方法是令$c\approx rl/2$（或者直接令$c=rl/2$都行），另一种方法是令$c\approx \sqrt{lN/2},r\approx \sqrt{2N/l}$，如果$u$是方阵的话， 此类方法可以将证明长度减少至大约$\sqrt {2lN}$个群元素
- 如果承诺阶段是可信的（Trusted），比如采用多项式承诺来实现全息（Holography），则测试阶段也可以省掉，又省了一点
- 如果Prover用Merkle Tree对$u$的行向量进行承诺，则在两个阶段揭示$\hat u$的$l$个点需要$m\cdot l$个Merkle Tree验证路径，这意味着Prover需要$\Theta(ml\log m)$次Hash计算，$[BBHR19]$给出了一种优化方案，可以减少Hash的数量
Soundness analysis for the testing phase
合理性分析没看，回头有空的话再补一下
4 Practical Linear Codes with Linear-Time Encoding
本节介绍如何用上一节的多项式承诺方案构建Brakedown，本文考虑距离$\delta=0.05$，码率$\rho=0.6$的编码方式（编码过程为递归的方式，和$[4]$中介绍的一样，只不过本文的距离和码率与$[4]$中的不同）
接下来看一下构造的细节
The construction in detail
记$q$为素数的幂，$\mathbb F_q$表示大小为$q$的域，对于随机变量$p\in [0,1]$，记其熵函数为$H(p)$
记$\mathcal G_{n,m,d}$表示二分图的分布，其中左侧包含$n$个结点，右侧包含$m$个结点，每个左侧结点总共与右侧的$d$个随机结点相连，对应的矩阵记为$\mathcal M_{n,m,d}$，在该矩阵的每一行中，都有$d$个不同的非零元素（具有相同的元素值）
二分图长下面这样
基于二分图，编码方式如算法1所示
先不看这堆花里胡哨的符号和参数，先看一下算法想做什么：算法1的目的是构造一个线性映射$\mathrm {Enc}_n:\mathbb F^n\rarr \mathbb F^{rn}$，也即对于任意长度为$n$非零域向量$x$，将其映射到一个长度为$rn$的域向量$w$，且$w$的汉明重量$||w||_0\geq \beta n$
而且这个编码方式得到的码字是系统码，$w$的前$n$位与信息元$x$相等（可以确保码字的生成矩阵是满秩的，也即$rank=n$，码率为$1/r$，码字距离$\delta=\beta/r$
接下来看一下算法的流程，第一步这个$c_n$不理它，这一步先利用参数$c_n$生成一个随机的稀疏矩阵$A\larr \mathcal M_{n,\alpha n,c_n}$（其实就是对应于$[4]$中的第一个无损扩展器）
然后第三步计算$y=x\cdot A$，这个用信息元和$A$相乘的过程就是编码的过程（具体可以看$[4]$，那个里面讲的比较详细，或者干脆直接去看对应的MOOC）
由于参数$\alpha<1$，这里我们可以以递归的方式继续对$y$进行处理，也即递归调用算法1，计算$z=\mathrm{Enc}_{\alpha n}(y)$
然后第五步的$d_n$也不用管，基于这个参数生成第二个稀疏矩阵$B$（其实就是第二个无损扩展器），计算$v=z\cdot B$
最后将三个部分拼起来，就得到了输出码字$w=x||z||v$
看不懂没关系，这里放一张可视化的编码流程图
其实和$[4]$中下面这个图的思路是一样的，只不过论文里面用的参数不一样，写的也复杂了一些
Running Time
可以简单看一下算法1的运行时间，这里记域乘法的数量为$T(n)$，因为可以看到编码过程主要包含的是向量与矩阵的乘法，域加法的数量显然比乘法少，而且惩罚的开销也比加法大，所以这里只考虑乘法的数量
从算法1的流程图来看，乘法数量满足下列不等式
$$ T(n)\leq n\cdot c_n+\alpha rn \cdot d_n+T(\alpha n)=n(c_n+\alpha r\cdot d_n)+T(\alpha n) $$
这里对$n$求极限，然后用无穷级数展开，就得到了
$$ T(n)<n\cdot \frac{c+\alpha rd}{1-\alpha} $$
数学不好，看不懂
Code distance
在介绍方案之前，先来分析一下码字的距离，由于采用线性码进行编码，因此只需要考虑非零码字的距离大于$\delta n/\rho=n/12$即可，可以分为三种情况，和$[4]$中最后的距离分析类似，只不过距离和码率不同而已，具体可以看那篇博客，这里不再赘述，严格证明可以看原文$[1]$，感兴趣的可以看看
原文的表2给出了不同参数下得到的码字距离、编码时间和对应的码率
数学不好，真看不懂
Stop recursing
但是这里忽略了一个很关键的点：由于上述编码是递归进行的，什么时候终止递归就是个问题
回顾一下$[4]$中的例子，采用的扩展器的$\alpha=0.5$，所以每次长度都会减半，而且那个例子假设了信息元的长度为2的幂，所以经过至多对数次递归之后，只需要处理长度为2的信息元，同时得到长度为1的码字，这就到了边界了，然后再向上逐层返回即可
由于Brakedown采用的扩展器的参数$\alpha$不为0.5，所以和那个例子有些出入，不过解决方案也很简单，设置一个边界条件$n_0$即可，当信息元的长度小于$n_0$的时候就可以终止递归了
其实$[4]$中的例子也是一样，只不过边界条件为2，而且隐含在了假设里面，不太明显
Brakedown设置的边界条件$n_0=30$
5 Linear-time commitments for sparse multilinear polynomials
这里为了基于线性时间的承诺方案构建SNARK，还需要一个组件：需要一个承诺方案，来完成对R1CS矩阵的多线性扩展的承诺，也即对$\tilde A,\tilde B,\tilde C$的承诺
更具体一些，这里为了确保与上述承诺方案一我们希望这个承诺方案在承诺、证明和求值上的开销也是线性阶的，这样不会影响整体SNARK效率，本文称之为密集（Dense）多项式承诺方案，因为Prover的运行时间与多项式的系数数量相关，而与这些系数有多少个是非零的无关
之前提到了，R1CS中的三个矩阵中只有$O(N)$个元素非零（转换到拉氏插值多项式中就是有$O(N)$个系数非零），这里我们需要一个对稀疏多项式的承诺方案，Spartan给出了解决方案，可以将对密集多项式的承诺方案转换为稀疏多项式的承诺方案，接下来简单回顾一下
对于一个包含$l$个变量的稀疏多项式$q$，其中非零系数的数量$k\ll 2^l$，承诺方先利用密集多项式承诺方案，对由这些非零系数所构成的多项式进行承诺
具体而言，将每个拉氏基多项式与$\{0,1\}^l$中的一个比特向量$S$相关联，并令$c_S$表示$q$中与$S$表示的单项式所对应的系数（没太理解），然后这里引入一个向量$v=\{(c_S,S):c_S\neq 0\}$
承诺方利用密集多项式承诺方案，对$v$的多线性扩展$\tilde v$进行承诺，然后Verifier发起一个查询$r$，此时可以利用交互式证明，在$r$处计算$q(r)$（比如用GKR协议），交互式证明的最后阶段，Verifier需要在一个随机点上对$v$进行求值
上述过程有一个问题，
Representing sparse polynomials with dense polynomials
看一下如何用密集多项式表示稀疏多项式，记$D$表示一个包含$2\log M$个变量的多变量多项式，且至多在$N=\Omega(M)$个点处的求值为非零
对于$r\in \mathbb F^{2\log M}$，$D(r)$的求值过程和Spartan中的思路类似，将$r$拆成两个部分$r=(r_x,r_y)$，记$\mathrm b$为映射$\{0,1\}^{\log M}\rarr \mathbb F$，对应的逆映射为$\mathrm b^{-1}$，然后计算下面这个式子
$$ D(r_x,r_y)=\sum_{k\in \{0,1\}^{\log N}}\mathrm{val}(k)\cdot \tilde{eq}(\mathrm b^{-1}(\mathrm{row}(k)),r_x)\cdot \tilde{eq}(\mathrm b^{-1}(\mathrm{col}(k)),r_y) $$
这里这个等式和Spartan里面的一样，只不过换了几个符号而已，可以对比一下Spartan里面的计算等式
$$ \tilde M(r_x,r_y)=\sum_{(i,j)\in(\{0,1\}^s,\{0,1\}^s)::M(i,j)\neq 0}M(i,j)\cdot \tilde{eq}(i,r_x)\cdot \tilde{eq}(j,r_y) $$
后面的和Spartan一样，将检查视为大小为$M$的内存上的$N$个查找，相关的可以看$[2,5]$，详细步骤如下图所示
最后把所有组件捏起来，就得到了本文的方案
References
$[1]$ Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, Riad S. Wahby:Brakedown: Linear-time and post-quantum SNARKs for R1CS. IACR Cryptol. ePrint Arch. 2021: 1043 (2021)
$[2]$ 多项式扩展与和校验协议 - 三两老友杂的小岛 (snowolf0620.xyz)
$[3]$ Spartan：满足透明性的通用高效zkSNARK方案 - 三两老友杂的小岛 (snowolf0620.xyz)
$[4]$ Polynomial Commitments based on Error-Correcting Codes - 三两老友杂的小岛 (snowolf0620.xyz)
$[5]$ Srinath T. V. Setty:Spartan: Efficient and general-purpose zkSNARKs without trusted setup. IACR Cryptol. ePrint Arch. 2019: 550 (2019)