Motivations and Drawbacks
之前博客中采用的多项式承诺方案都是以KZG10为主，部分还有诸如Bulletproof和Dark的承诺方案，这些方案都是基于DLOG假设或者未知阶群
本部分介绍一种基于纠错码的多项式承诺方案，与之前的承诺方案相比，具有下列优势
- 可能是后量子安全的
- 无需群幂操作（Prover只需要进行Hash、加法和乘法）
- 全局参数很短
但是缺点也比较明显
- 证明大小很大（MB级别的大小）
- 缺乏代数结构，不具备同态性
- 难以聚合（KZG的聚合性就很好）
Error-correcting Code
纠错码是一个信息论和编码理论中广泛研究的方向，此类编码方式可以用来纠正传输过程中发生的错误
一个纠错码记为$[n,k,\Delta]$，对应一个编码函数$Enc(m)$，表示将长度为$k$的信息元$m$编码长度为$n$的码字$c$，任意两个码字之间的最短汉明距离记为$\Delta$，解码函数记为$Dec(c)$
举个例子，比如一个$[2,6,3]$的码字如下
| m | C |
|---|---|
| 00 | 000000 |
| 01 | 000111 |
| 10 | 111000 |
| 11 | 111111 |
不难看出任意两个码字的最短距离$\Delta=3$，根据纠错码的理论，上述纠错码可以纠正一位错误
例如收到的码字为$010111$，如果译码函数采用最短距离译码方式，则会将码字译为$01$，因为与这个接收码字距离最短的正确的码字为$000111$，其对应的信息元为$01$
Rate and Relative Distance
纠错码有两个很重要的参数：码率（Rate）和相对距离（Relative Distance），码率记为$r=\frac{k}{n}$，表示信息元在码字中的占比，相对距离记为$\frac{\Delta}{n}$，表示两个码字最小差异的比例
这个相对距离很好理解，比如上面的$[2,6,3]$码，相对距离为$3/6=0.5$，意思是任意两个码字至少有50%的部分是不相同的
根据编码理论，通常希望码率尽可能地高，而从纠错的角度出发，又希望相对距离足够大，这样就可以区分不同的码字，使得码字具有更强的纠错能力，但是这两个参数通常是冲突的，因此对编码理论的研究之一就是在这两个参数之间进行权衡
Linear Code
线性码，意思是任意两个码字的线性组合仍然是一个码字
注意到线性码中的“线性”二字，这意味着此类码具有很好的代数特性，此类码字的编码函数通常表示为信息元向量$\vec m$与生成矩阵$\mathbf G$相乘
Reed-Solomon Code
RS码，一个非常经典的编码方式，其实这个编码方式就在我们身边，二维码的纠错方式就是用的RS码
除了二维码上的应用，RS码也是一个非常重要的密码学原语，用于构建诸如STARK、秘密共享等密码学协议
RS码是一个基于有限域的编码，编码函数是一个映射$f:\mathbb F^k_p\rarr \mathbb F^n_p$，它将信息元视为互不相同的，阶为$k-1$的一元多项式，而对应的码字就是在$n$个点上对这个多项式进行求值（Evaluations），求值的过程可以用FFT来完成（所以编码复杂度为$O(n\log n)$）
举个例子，比如$\omega$为$n$次单位根（$\omega^n\equiv 1\mod p$），则我们可以在集合$\{\omega,\omega^2,\dots,\omega^n\}$上对这个多项式求值
RS码是线性码，和上面提到的一样，可以用信息元向量与生成矩阵表示
RS码的很多性质都由其距离$\Delta$决定，很多密码学协议也是基于RS码的距离特性构建的
RS码的距离$\Delta=n-k+1$，这个很好理解，因为信息元被视为阶为$k-1$的多项式，而这个多项式至多有$k-1$个互不相同的根，所以$\Delta=n-(k-1)$
举个例子，如果$n=2k$，可以算出码率$r=0.5$，相对距离也为$0.5$
Polynomial Commitments based on Linear Codes
Overview
先简单看一下如何利用线性码构建多项式承诺，此类方案早在Breakdown和Orion的paper中就有使用，其优点在于证明大小和验证时间复杂度都是平方根的
可以先直观感受一下这个方案是如何实现平方根阶的复杂度的，这里假设多项式的系数向量的长度为某个整数的平方（也即$d=k^2$，如果不是的话可以填充）
首先看一下原来计算$f(u)$的方式，就是上图中下面的那个求和式，不难看出很复杂
但是我们可以将系数向量排列成大小为$\sqrt d =k$的方阵，然后前后分别乘上对应的向量，就可以完成求值了，不难看出这个矩阵乘法和下面的求和式是等价的
这样一来，我们就将构造一个证明大小为$\sqrt d$的多项式承诺的问题，归约到了向量-矩阵乘法的问题
但是这里仍然有一个问题：即便这个方阵大小为$\sqrt d$，方阵本质上还是包含了$d=k^2$个元素，如果发送整个矩阵的话，那证明大小又回到了线性阶了
为了确保平方根阶的证明大小，这里采用线性码处理这个矩阵，如下图所示
我们利用线性码，对矩阵的每一行进行编码，根据前面提到的编码知识，原始矩阵中每一行有$k$个元素（信息元长度为$k$），编码后可以得到长度为$n$的码字，之后将这些码字组成一个新的矩阵，就得到了上图右侧的样子
这里为了确保$n$不会太大，所以采用码率为常数的编码方式
得到了上面的码字矩阵之后，我们利用Merkle Tree对这个码字矩阵按列进行承诺（一共有$n$列）
然后在基于Merkle Tree来构建协议即可
不难看出，这个思路其实很简单，只需要Merkle Tree，一个抗碰撞的Hash函数，一个码率为常数的线性码即可，无需可信设置，公共参数的大小也是常量级比的
Step 1:Proximity Test
基于上述思想，看一下方案的一些具体细节，这里接着上面的Merkle Tree继续介绍
第一步是渐进测试（Proximity Test），这一步需要检查Merkle Tree所承诺的矩阵确实承诺了$k=\sqrt d$个码字
以RS码为例，在这一步中，Verifier不仅需要检查Prover所承诺的矩阵确实了$k$个码字，还需要检查这些码字都是RS码的码字，而不是Prover随机生成的向量
检查的方式很简单，Verifier构造一个长度为$k$的随机向量$(r_1,\dots,r_{\sqrt d})$，发送给Prover，Prover将这个随机向量与码字矩阵相乘，如下图所示
相乘的结果是一个长度为$k$的向量，记为$w$，Prover需要将这个向量返回给Verifier
之后Verifier请求Prover揭示矩阵中的若干列（Merkle Tree承诺的揭示），然后Verifier需要执行三个检查
- 检查向量$w$是一个码字
- 检查Merkle Tree承诺的揭示的正确性
- 检查揭示的列与对应位置的随机值的内积的一致性
这里分别来看这三个检查，第二个很好理解，检查承诺的揭示，如果揭示值与承诺值不一致，显然Verifier会拒绝
第一个检查$w$是一个码字，这里也很好理解，前面提到了线性码的特点在于，其任意码字之间的线性组合也是一个码字，这里采用一个随机向量对这个码字矩阵做一个线性组合，因此如果Prover没有违背协议（矩阵确实是码字矩阵，而不是随机生成的向量构成的矩阵），则得到的向量$w$也必然是一个码字
第三个是检查揭示的列向量与对应位置随机性乘积的一致性，实际上就是检查揭示的列向量与向量$p$中对应位置的值是否一致
当且仅当上述三个检查都通过时，Verifier则认为Prover所承诺的矩阵为码字矩阵
这里可以把三个检查一起看：如果向量$p$不是一个码字，首先不能通过第一个检查
其次，根据承诺的绑定性，Prover无法将矩阵中的列揭示为其他的值，此时在Verifier的随机向量的限制下，对于无法通过第一个检查的向量$p$，仅有少数可以满足第三个检查的列向量的组合，Prover找到其中的一组的概率很小（指数级的小）
正式的合理性分析在论文$[AHIV17]$里面，这里可以看一下
前面提到了码字的距离的概念，如果说Prover承诺的码字矩阵$C$与任意码字的距离为$e$远的（$e$-far，意思是与合法码字的距离大于$e$，这里$e<\frac{\Delta}{4}$），那么上述向量$w$与任意码字的距离小于$e$的概率不大于$\frac{e+1}{|\mathbb F|}$
而如果$w$与任意码字的距离是$e$远的，则上述检查3中，若揭示的列向量的数量为$t$，则检查3通过的概率不大于$(1-\frac{e}{n})^t$
简单来说就是，如果矩阵$C$不是码字矩阵，那$w$是一个合法的码字的概率很小，几乎不可能通过第一个检查
此时由于$w$不是合法的码字，因此通过检查3的概率也很小（会与揭示的列向量的数量呈指数级减小）
这里有一个优化的点：因为$w$是合法的码字，而码字又是由信息元得来的，因此Prover可以在原来的信息元矩阵中找到这个码字所对应的行向量，发送那个行向量
Verifier收到之后，再通过RS码的编码方式恢复出对应的码字就可以了，这样又可以减少一部分的通信量
Step 2: Consistecy check
这一步的目的是检查原来的求值点向量$(1,u,\dots,u^{\sqrt d-1})$与原始矩阵（不是码字矩阵）的乘积与结果向量之间的一致性，而且这一步的工作和上面的渐进测试的工作基本一致
这里因为是求值点向量与原始矩阵做一个乘积，可以视为用向量$(1,u,\dots,u^{\sqrt d-1})$对原来的信息元做了一个线性组合，然后Prover将这个线性组合后的向量发送给Verifier
然后Verifier此时只需要完成上面的检查3，也即检查上一步中揭示的列向量与接受向量对应位置的值是否一致即可
因为Prover发送的是由合法的信息元矩阵所构造的向量，所以检查1不用做了（此时相当于上一步中最后优化的那种情况，发送信息元即可）
然后这一步中揭示的列和渐进测试中揭示的列是相同的，所以检查2也不用做了
Scheme
综上，我们可以把这个基于线性码的方案抽象为一个算法四元组$(KeyGen,Com,Eval,Vfy)$
- $KeyGen$：这里的密钥生成函数主要是选择一个合适的、满足抗碰撞性的函数
- $Com$：将原始多项式$f$的系数构造为$\sqrt d$阶的方阵，用线性码对该方阵进行编码，然后利用Merkle Tree对码字矩阵按列进行承诺
- $Eval$：求值算法，计算Step 1和Step 2中相关的向量
- $Vfy$：验证算法，完成Step 1或Step 2中的验证步骤
这里我们可以分析一下方案的效率
- $KeyGen$：开销为$O(1)$，在抗碰撞Hash函数族中选一个Hash函数即可，而且这个步骤满足透明性，所以方案也满足透明性
- $Com$：如果采用RS码的话，编码过程的复杂度为$O(d\log d)$次域乘法，如果线性编码时间的线性码则只需要$O(d)$
Merkle Tree需要$O(d)$次Hash，得到的承诺大小为$O(1)$ - $Eval$：$O(d)$
- $Vfy$：$O(\sqrt d)$
- 证明大小：$O(\sqrt d)$
只看复杂度的话还是太抽象了，这里看一下$[GLSTW21]$的benchmark，这篇paper测试了$d=2^{25}$的情况，采用线性编码时间的线性码，单线程机器进行测试，结果如下
- Commit Time：36s
- Eval Time：3.2s
- Proof Size：49MB
- Verifier Time：0.7s
不看Proof Size的话，其他三项还是非常不错的，可以对标甚至优于KZG10和Bulletproof等承诺方案（因为没有用到群幂运算，当然快了）
但是缺点在于Proof Size真的太大了，导致其实际上并不是非常适用
Linear-Time Encodable Code
线性编码时间的码在构造线性Prover Time的SNARK中很有用，最早于2017年提出，最近几年也有过不少方案，如下图所示
这些方案都有一个特点：他们都采用了相对距离为常数的线性编码时间的编码来构造
这里先简单介绍一下这些方案的基本实现思路，以及如何构造一个相对距离恒定的编码
Expander Graph
线性编码时间的编码最早由Spielman于1996年提出，其核心思想基于一个称为扩展图（Expander Graph）的概念，大致结构如下图所示
笔者不太懂图论，不了解扩展图的相关概念，笔者只能从wiki搬运一句话：扩展图是一种具有很强连通性的稀疏图
感兴趣的小伙伴可以看一些参考资料$[2-4]$
这里可以看到图中每一个蓝色结点的结点都连接了三个绿色的结点，而且蓝色结点之间没有边，绿色节点之间也没有
这张图有一个很好的扩展，就是中间深紫色梯形框出来的这个，因为左侧的两个蓝色的结点连接了右侧的五个结点，这一组结点（包含两个蓝色和五个绿色）的扩展很好
这里可以有助于理解一下“扩展”的意思：因为每个蓝色节点都连接了3个绿色结点，理论上来说，两个蓝色结点可以连接最多六个绿色节点
而我们选择的这两个蓝色结点连接了五个，所以扩展很好（？）
然后接下来看一下扩展图如何实现期望的相对距离，这里令左侧的蓝色结点为信源符号，右侧的绿色结点表示码元符号
举个例子，右侧最上面的绿色结点与左侧上面的两个蓝色结点相连，这意味着这个绿色的码元符号取决于这两个蓝色的信源符号
不难看出，此类编码方式是线性码，可以用生成矩阵来表示，而且这个编码方式可以在线性时间内完成，因为左侧的每个信源符号都与有限个码元符号（上图为3个）相关，因此编码的时间为信源符号数量的常数倍（上图为3倍）
此类编码方式的特点在于：即便是信源只包含非常少量非零元素，他仍然会扩散到右侧的足够多的码元中，从而增加码字之间的距离
还是以上面那个图中的梯形为例，假设右侧的蓝色结点仅有一个非零，那么这个非零结点仍然会扩散到右侧的三个码元符号中，尽管这两个信源符号只能映射到五个码元符号，但是由于存在一个非零信源符号，因此这五个码元符号中至少有三个也是非零的
不过这里只是举个例子，这个例子还不足以满足本文所需要的恒定距离的码字
Lossless Expander
接下来正式介绍如何使用扩展图构造一个具有恒定相对距离的线性编码时间的码
首先是定一个新的概念，称为无损扩展器（Lossless Expander），此类扩展器的扩展性极佳，几乎是所有扩展图中扩展性最好的
在无损扩展器中，有几个参数
- $k$：表示左侧结点的数量
- $\alpha$：常数，$0<\alpha<1$，对应到右侧结点的数量为$\alpha \cdot k$
- $g$：常数，左侧节点的阶，表示每个左侧结点连接了多少个右侧结点，上图中$g=3$
基于上述三个参数，记左侧结点的一个子集为$S$，如果上图是一个无损扩展器，则这个子集$S$中包含的右侧结点的数量$|\Gamma(S)|=g|S|$，因为每个左侧结点都与右侧的$g$个结点相连
但是显然这个$\Gamma$函数不是对于所有子集都成立，因为右侧结点数量不一定是左侧的$g$倍，因此也没有足够多的结点与左侧匹配（因此上图也不是无损扩展器），这里必须要求子集中的结点数量满足$|S|\leq \frac{\alpha\cdot |L|}{g}$才有上述等式成立，有这个等式也意味着这是一个损失扩展（Loss Expand）
这里定义两个参数，$\beta,\delta$，此时的$\beta$就是损失系数，然后可以将上述$\Gamma$函数的定义改写为
$$ |\Gamma(S)|\geq (1-\beta)\cdot g\cdot |S| $$
对应的将$|S|$中的$\alpha$替换为$\delta$，得到$|S|\leq \frac{\delta\cdot |L|}{g}$，根据定义，当$\delta$越趋近$\alpha$时（$\delta\rarr \alpha$），则意味着$\beta$也越趋近于0（$\beta \rarr 0$）
Encoding Overview
接下来简单介绍一下如何利用扩展器来进行编码
编码的过程可能要比理解扩展器本身要复杂的多，不过本质上是一个递归的编码过程
假设这里我们有一个码率为$0.25$的线性码编码方式，也即对于消息长度为$k$，编码后的码字长度为$4k$，且这个编码算法的相对距离很好（比如可以用RS码）
然后扩展器的编码方式如下图所示，这里可以不失一般性假设$k$为2的幂
递归编码步骤如下
- 将消息$m$复制一份，之后对其中的一份消息作用一个$\alpha=0.5$的无损扩展器，得到长度为$k/2$的输出
- 利用前面这个码率为$0.25$的线性码对这个无损扩展器的输出结果进行编码，得到长度为$2k$的码字$c_1$
- 最后再对这个码字作用一次无损扩展器，得到长度为$k$的码字$c_2$
这里需要注意：步骤3中的无损扩展器和步骤1中的无损扩展器不相同，因为他们的输入长度都不同，所以不是同一个扩展器，只不过它们具有相同的$\alpha$而已
然后就是前面提到了这个编码过程是递归的，递归的点再上图中的紫色字部分，最开始我们处理长度为$k$的原始消息，经过第一个扩展器后得到了长度为$k/2$的输出
这时候先不对这个输出进行编码，而是重复上述过程，回到步骤1，将这个长度为$k/2$的输出作为输入，复制一份，然后作用扩展器，得到$k/4$的输出，依此类推，直到递归走到头，然后开始自底向上往回编码，直至处理到最开始的关于原始消息所对应的码字$c_1,c_2$，此时编码的结果为$c=m||c_1||c_2$
如果采用的线性码的相对距离为$\Delta$，则上述编码方式的相对距离为常数$\Delta'=\min \{\Delta,\frac{\delta}{4g}\}$，详细分析可以看$[4]$，这里随便分析一下，分两种情况讨论（仅讨论非零码字）
第一种情况很简单，如果消息$m$本身的重量大于$4k\Delta'$，那不用分析了，因为观察码字的结构$c=m||c_1||c_2$，第一部分就是消息$m$，这一部分的重量已经大于$4k\Delta'$了，所以对应的相对距离也确实是常数，证毕
第二种情况复杂一些，如果消息$m$本身的重量小于等于$4k\Delta'$，这里就取决于无损扩展器了
回顾一下无损扩展器中，我们对左侧结点的子集的大小$|S|$有一个限制，根据$|\Gamma(S)|\geq (1-\beta)\cdot g\cdot |S|$这个不等式，我们可以得到$\Gamma(S)$中至少有一个结点对应于$S$中的一个独立的结点，这表明第一个扩展器的输出中至少有一个结点是非零的，从而其编码后的码字$c_1$的重量至少为$2k\Delta$，此时又可以细分为两种情况
如果说$2k\Delta\geq 4k\Delta'$，那和第一种情况一样，因为$c_1$也是码字的一部分，所以整个码字的种类也必然大于$4k\Delta'$，证毕
如果$c_1$的重量小于$4k\Delta'$（但是仍然大于等于$2k\Delta$），此时第二个扩展器的作用就来了，可以证明经过第二个扩展器的作用后，码字$c_2$的重量大于等于$2k\Delta'$，然后又因为$\Delta\geq \Delta'$，$c_1,c_2$的重量加起来为$2k\Delta+2k\Delta'\geq 4k\Delta'$，证毕
无损扩展器的选择可以看$[5]$
Improvements of the code
上述编码方式还有很多优化的空间，具体可以看Brakedown$[6]$和Orion$[7]$这两篇paper，这里不再展开
Putting everything together
把上面所有的东西捏起来，我们就可以得到一个基于线性码的多项式承诺方案，然后再基于这个多项式承诺方案构建SNARK
不难看出，全部捏起来以后，得到的承诺方案无需透明设置，初始化算法复杂度仅为$O(1)$，承诺和Prover Time为$O(d)$，与多项式大小呈线性阶，而且很有可能满足后量子安全性
唯一的缺点就是，证明大小真的是太大了，复杂度来到了$O(\sqrt d)$级别，实践中可以达到MB级别，很难实用
References
$[1]$ ZKP MOOC Lecture 7: Polynomial Commitments based on Error-correcting Codes - YouTube
$[2]$ Expander graph - Wikipedia
$[3]$ PCP Theorem Part 2: Expander Graph - 知乎 (zhihu.com)
$[4]$ Erez Druk, Yuval Ishai:Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications. ITCS 2014: 169-182
$[5]$ Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson:Randomness conductors and constant-degree lossless expanders. STOC 2002: 659-668
$[6]$ 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)
$[7]$ Tiancheng Xie, Yupeng Zhang, Dawn Song:Orion: Zero Knowledge Proof with Linear Prover Time. IACR Cryptol. ePrint Arch. 2022: 1010 (2022)