这篇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)