Abstract

Spartan是一个基于R1CS的zkSNARK方案，利用推广C-SAT的NPC语言

Spartan的特点在于，其为NP语言提供了第一个无可信设置的zkSNARK，且Verifier开销为亚线性阶，无需NP语句的一致性

此外，Spartan通过引入和校验协议来将Prover时间减少至最优的

本文通过将SPARK应用于不同的承诺方案来得到多个zkSNARK，这些方案中Verifier的开销在$O(\log^2 n)\sim O(\sqrt n)$之间（$n$表示NP statement的大小，开销取决于底层承诺方案），且均无需可信设置（需要通用可信设置的方案除外）

本文利用Rust实现了Spartan库$[3]$，该库在随机预言机模型中构建了第一个zkSNARK方案，安全性基于DLOG假设

1 Introduction

之前有许多zkSNARK方案，包括基于Merkle Tree+PCP、基于QAP、基于R1CS、基于MPC等等多种方案，但是这些方案存在一些问题

  • Hyrax中的计算模型基于分层算术电路，Verifier的开销和证明大小与电路深度相关，且将任意电路转换为分层电路会导致电路规模增大为原来的二次，因此诸如Hyrax之类的方案仅适用于深度较小的电路，且Hyrax进队具有统一结构的电路（比如数据并行电路）才能达到亚线性的Verifier开销
  • STARK要求具有一系列相同的子电路，否则无法做到亚线性的Verifier开销，任何电路均可以转换为此类型是，但是会将电路大小增加10至1000倍不等，间接导致Verifier开销增加
  • Ligero、Bulletproof、Aurora等方案的Verifier开销均为线性阶

本文旨在解决上述问题，主要贡献如下

本文基于R1CS表示的NP语句，构建了一个透明的zkSNARK，验证开销为亚线性阶，证明开销是目前所有方案中最优的，本文的方案结合了可抽取多项式承诺方案和信息论协议，合理性基于多项式承诺方案的假设（可在标准密码假设下进行实例化）

本文的方案为公共掷币方案，可在FS变换下转变为随机预言机中的非交互式协议

本文的核心是和校验协议，由于和校验协议在处理低阶多项式时的效率较差，因此本文提出了三种新的技术来解决此类效率问题

  • 计算承诺：用于实现亚线性阶的验证开销，由于Verifier需要在证明前处理NP statement，因此很难达到亚线性的开销，不过通过引入公共预处理步骤，可以使得成本在NP statement上呈亚线性阶

具体而言，Spartan中，Veriier读取生成证明的R1CS示例，并保留对一组编码R1CS结构的稀疏多线性多项式的承诺，后续生成证明时Prover对必要的多项式求值并证明稀疏多项式与Verifier保留的承诺值一致

  • SPARK：SPARK是一个密码学编译器，用于将现有的可抽取多线性多项式承诺方案转换为一个可以有效处理系数多线性多项式的方案，利用该编译器来达到最优Prover方案
  • R1CS的紧凑编码：本质是一个三阶多元多项式，可以拆分为四个多线性多项式

Spartan从zkSNARK的角度解释了概率证明不同研究之间的相关性，包括双高效IP、MIP和短PCP

下图是近几年方案的效率比较

图1
图1

‍

2 Preliminaries

  • $Sat_L(x,w)$：若有$x\in L$，则$Sat_L(x,w)=1$，否则为0，若$Sat_L(x,w)=1$，对应的$(x,w)$二元组称为可满足实例
  • R1CS实例：记为七元组$(\mathbb F,A,B,C,io,m,n)$，其中$io$表示公共输入输出，$m\geq |io|+1$，矩阵$A,B,C$中非零元素的数量至多为$n$个

原文中间有一些定义，都是之前提到过的，内容基本一致，只不过用的符号和表述方法不同，这里不再赘述

此外还有一些多线性多项式扩展和和校验协议的概念，具体可以看之前的博客

3 The sum-check protocol: opportunities and challenges

本节介绍一些和校验协议与本文协议的相关内容

由于本文的目的是基于R1CS构建简洁交互式知识论证，对应的关系为$Sat_{R1CS}(x,w)=1$，如果使用和校验协议构建的话，会遇到下列三个问题

  1. 需要将R1CS实例编码为和校验实例：此时需要构造一个阶为$l$，包含$\mu$个变量的多项式，且当且仅当在$Sat_{R1CS}(x,w)=1$时，该多项式在$\{0,1\}^\mu$上的求和值为$T$（$l$为某一小常量，$\mu=O(\log m)$）
  2. 构造简洁通信量方案：尽管和校验协议的通信量是简洁的，但是和校验协议中，Verifier需要在每一轮验证等式$g(r)=e$，而$g(r)$的值又取决于$(x,w)$，一种朴素的计算$g(r)$的方式为Prover直接发送$w$，但是这种方式需要$O(m)$的通信量且不满足零知识性
  3. 实现Verifier的简洁性：若要将交互式论证编译为zkSNARK，Verifier的开销必须与NP statement呈亚线性关系，但是对于无特定结构的statement（比如数据并行的statement），计算$g(r)$的需要的操作数量为$O(n)$

有一种解决方法时Verifier对R1CS的实例结构进行预处理，从而可以加速具有相同结构的不同R1CS实例，但是需要注意预处理必须不包含任何陷门（要不然就是可信设置了）

通过构建布尔公式可满足性来构造协议，但是此类方式会导致转化为R1CS时更为冗长，Blumberg等人利用低阶多项式构建算术电路可满足性问题的MIP协议（，但在实践中，与R1CS相比还是有比较大的常量因子，且编程此类协议的挑战也不小

为了解决这些问题，之前的学者主要有下列几种解决方案

  • MIP协议：Multi-prover Interactive Proof，Blumberg等人利用低阶多项式构建算术电路可满足性问题的MIP协议，通过引入多个未被腐化的Prover的方式解决了上述第二个问题，尽管该方案可以将MIP转换为zkSNARK，但是该方案依赖于全同态（FHE），且协议的合理性错误很差（$|\mathbb F|=2^{300}$时仅可实现23比特的安全级别），因此并不实用，而且该方案并没有解决第三个问题，因此得到的ZKP协议并不是zkSNARK
  • Short PCP：Babai等人设计了一个短PCP协议，但是由于此类方案生成的PCP串是NP statement的超多项式阶，因此基于此类短PCP协议构建zkSNARK仍然不切实际
  • DEIP（Double Efficient Interactive Proof）：DEIP通过限制分层形式的确定性电路来解决上述三个问题，通过一系列的和校验协议来递归的将输出的statement规约至输入的statement，此类方案中Verifier的开销与电路的深度呈线性阶，因此此类方案仅适用于深度较小的电路，而且此类方案需要使用布尔电路（布尔电路比等效的算术电路的规模要大好几个数量级），因此也不太实用
    Zhang等人通过多项式承诺方案将DEIP扩展到NP类中，但是该方案需要可信设置，Wahby等人无需可信设置，但是仍然需要分层电路的限制，且这两个方案都专注于数据并行运算的结构，实践中有较大的限制

4 An encoding of R1CS instances as low-degree polynomials

本节介绍如何解决上面的第一个问题，也即将R1CS实例的压缩编码转换为一个三阶的多元多项式

这里原文给出了一个定理，要求$Sat_{R1CS}(x,w)=1$，且要求域$\mathbb F$的大小为安全参数$\lambda$的指数级，$m=O(\lambda)$

对于R1CS实例$x=(\mathbb F,A,B,C,io,m,n)$，记$s= \lceil \log m \rceil$，转换方式与前一篇三角形计数的方式类似，将三个矩阵$A,B,C$视为映射$\{0,1\}^s\times \{0,1\}^s\rarr \mathbb F$，此时每个矩阵中的每一个元素均可用一个长度为$2s$的串来访问（或者一个由两个长度为$s$的串构成的二元组访问）

此时对于给定的witness $w$，令$Z=(io,1,w)$，可以将$Z$表示为映射$\{0,1\}^s\rarr \mathbb F$，因此$Z$中的任意元素可以用一个长度为$s$的串访问

下面定义一个函数$F_{io}(\cdot )$，该函数用于对witness编码，对于任意的$x\in\{0,1\}^s$，当且仅当$Sat_{R1CS}(x,w)=1$时$F_{io}(x)=0$，函数具体如下

$$ F_{io}(x)= \Big( \sum_{y\in \{0,1\}^s}A(x,y)\cdot Z(y) \Big)\cdot \Big( \sum_{y\in \{0,1\}^s}B(x,y)\cdot Z(y) \Big) -\sum_{y\in \{0,1\}^s}C(x,y)\cdot Z(y) $$

由于$F$是函数，不能直接用于和校验协议，因此需要进行一次多项式扩展$\tilde F_{io}:\mathbb F^s\rarr \mathbb F$，得到扩展后的多项式

$$ \tilde F_{io}(x)= \bigg( \sum_{y\in \{0,1\}^s}\tilde A(x,y)\cdot \tilde Z(y) \bigg )\cdot \bigg( \sum_{y\in \{0,1\}^s}\tilde B(x,y)\cdot \tilde Z(y) \bigg ) -\sum_{y\in \{0,1\}^s}\tilde C(x,y)\cdot \tilde Z(y) $$

$\tilde F_{io}$也是当且仅当$Sat_{R1CS}(x,w)=1$时求值为0

由于$\tilde F_{io}$是一个$s$个变量的低阶多变量多项式，Verifier可以利用和校验协议检查$\sum_{x\in \{0,1\}^s}\tilde F_{io}(x)=0$，但是这不意味着对所有的$x\in \{0,1\}^s$都成立，因为在所有的$2^s$个项中，可能存在相互可以抵消的项，从而使得最终结果为零

这里通过引入另一个多项式$Q_{io}(t)$来解决这个问题，其中$\tilde{eq}(t,x)$为对应的基多项式

$$ Q_{io}(t)=\sum_{x\in \{0,1\}^s}\tilde F_{io}(x)\cdot \tilde{eq}(t,x)\\ \tilde {eq}(t,x)=\prod^s_{i=1}(t_i\cdot x_i+(1-t_i)\cdot (1-x_i)) $$

对于所有的$t\in \{0,1\}^s$，$Q_{io}(t)$也是一个多变量多项式，且满足$Q_{io}(t)=\tilde F_{io}(t)$，因此当且仅当$\tilde F_{io}$在$s$维布尔超立方中求值均为0时，$Q_{io}$也是一个零多项式

根据$Z(\cdot )$的定义，$\tilde F_{io}$在$s$维布尔超立方中求值均为0时，代表$Sat_{R1CS}(x,w)=1$

对于检查$Q_{io}$是否也是一个零多项式，可以随机选择$\tau _R\in \mathbb F^s$，检查等式$Q_{io}(\tau)=0$即可，此时该等式的合理性错误为$\frac{\log m}{|\mathbb F|}$

这里可以分析一下，如果存在$x\in \{0,1\}^s$，满足$\tilde F_{io}(x)\neq 0$，则代表$Q_{io}(t)$也是一个非零多项式，根据SZ引理，只有至多$d$个$t\in \mathbb F$，可以使得等式$Q_{io}(t)=0$成立（这里有$d=s=\log m$），因此合理性错误为$\frac{\log m}{|\mathbb F|}$

这里可以证明一下为什么当且仅当$Sat_{R1CS}(x,w)=1$时$F_{io}(x)=0$

对于给定的R1CS实例$x=(\mathbb F,A,B,C,io,m,n)$，定义一个多项式$\mathcal G_{io,\tau}(x)=\tilde F_{io}(x)\cdot \tilde {eq}(\tau,x)$，此时上述的$Q_{io}(\tau)=\sum_{x\in \{0,1\}^s}\mathcal G_{io,\tau}(x)$，注意到若在扩展多项式$\tilde F_{io}$中使用了相关的多项式$A,B,C,Z$，则$\mathcal G$为一个三阶$s$变量的多项式

此时在和校验协议中，有$T=0,\mu=s=\log m,l=3$，因此当根据前面的合理性错误分析，对于随机选择的$\tau$，使得$Q_{io}(\tau)=0$的概率在安全参数$\lambda$下可忽略

5 A family of NIZKs with succinct proofs for R1CS

本节首先介绍一个具有简介通信开销的交互式论证， 然后再利用前面的转换将其编译为随机预言机模型中的NIZK

5.1 A new public-coin succinct interactive argument of knowledge

本文一个比较关键的部分，首先给一个定理

Thm 1：给定可抽取的多线性多项式承诺方案，存在一个公共掷币的简洁交互式知识论证，安全性基于使用的多项式承诺方案，R1CS实例的大小为$n=O(\lambda)$

根据上面的分析，对于R1CS实例$x$是否可满足，Verifier只需要检查$\sum_{x\in \{0,1\}^s}\mathcal G_{io,\tau}(x)=0$即可，利用和校验协议，这一检查可以转变为随机选择$r_x\in \mathbb F^s$并检查$e_x=\mathcal G_{io,\tau}(r_x)$，为了实现简洁性，Verifier需要有一种方式来避免计算$e_x$时的线性阶计算量

上一节提到了$\mathcal G_{io,\tau}(x)=\tilde F_{io}(x)\cdot \tilde {eq}(\tau,x)$，因此计算$\mathcal G_{io,\tau}(r_x)$必须计算$\tilde F_{io}(x)$和$\tilde {eq}(\tau_x,x)$，后者的计算开销为$O(\log m)$，但是对于前者的计算，Verifier需要对于所有的$y\in \{0,1\}^s$，计算$\tilde A(r_x,y),\tilde B(r_x,y),\tilde C(r_x,y),\tilde Z(y)$，且由于$\tilde Z$的计算，最终的通信量会大于等于$O(|w|)$

本文通过结合下列三个协议来解决通信开销和计算量的问题：和校验协议，randomized mini协议（不知道这是个啥），以及多项式承诺方案

首先将$\tilde F_{io}(r_x)$拆分为$\tilde F_{io}(r_x)=\bar A(r_x)\cdot \bar B(r_x)-\bar C(r_x)$，$\bar A$如下，$\bar B,\bar C$类似

$$ \bar A(r_x)=\sum_{y\in \{0,1\}^s}\tilde A(r_x,y)\cdot \tilde Z(y) $$

此时Prover可以将前面的对Verifier的声明拆分为下面三个：$\bar A(r_x)=v_A,\bar B(r_x)=v_B,\bar C(r_x)=v_C$，此时Verifier的验证等式转变为

$$ \mathcal g_{io,\tau}(r_x)=(v_A\cdot v_B-v_C)\cdot \tilde{eq}(r_x,\tau)=e_x $$

但是上述过程还要求Verifier验证$\bar A(r_x),\bar B(r_x),\bar C(r_x)$的值是否正确，此时双方可以在这三个多项式上执行三个独立的和校验协议来验证，本文通过引入随机数的方式，将三个结合成一个来完成验证，具体如下

  1. 首先选择随机数$r_A,r_B,r_C\in_R\mathbb F$，计算$c=r_A\cdot v_A+r_B\cdot v_B+r_C\cdot v_C$
  2. 之后双方执行和校验协议，令$L(r_x)=r_A\cdot \bar A(r_x)+r_B\cdot \bar B(r_x)+r_C\cdot \bar C(r_x)$，Verifier验证等式$L(r_x)=c$

这里可以利用SZ引理证明，$L(r_x)=c$，且$\bar A(r_x)\neq v_A,\bar B(r_x)\neq v_B,\bar C(r_x)\neq v_C$的概率小于等于$\frac{1}{|\mathbb F|}$

根据前面提到的，这里$L(r_x)$可以展开写成下面这个等式

$$ L(r_x)=\sum_{y\in \{0,1\}^s}r_A\cdot \tilde A(r_x,y)\cdot \tilde Z(y)+r_B\cdot \tilde B(r_x,y)\cdot \tilde Z(y)+r_C\cdot \tilde C(r_x,y)\cdot \tilde Z(y) $$

这里将$L(r_x)$记为$L(r_x)=\sum_{y\in\{0,1\}^s}M_{r_x}(y)$，为了完成上面第二步的验证，Verifier需要选择一个$r_y\in \mathbb F^s$并计算$M_{r_x}(r_y)$，如下

$$ M_{r_x}(r_y)=\big ( r_A\cdot \tilde A(r_x,r_y)+r_B\cdot \tilde B(r_x,r_y)+r_C\cdot \tilde C(r_x,r_y)\big )\cdot \tilde Z(r_y) $$

注意到等式中只有$\tilde Z(r_y)$这一项取决于Prover的witness，其他三项Verifier可以根据R1CS statement在$O(n)$时间内计算出来（可以进一步减少计算量，后续介绍），这里引入一个可抽取的多项式承诺方案来降低和校验协议中计算$\tilde Z(r_y)$的通信开销，具体如下

不失一般性，假设$|w|=|io|+1$，首先Prover在和校验协议的第一轮前，先计算并发送多项式$\tilde w(\cdot )$的承诺，此时可以得到

$$ \tilde Z(r_y)=(1-r_y[0])\cdot \tilde w(r_y[1..])+r_y[0]\cdot \widetilde{(io,1)}(r_y[1..]) $$

$r_y[1..]$表示$r_y$的第二个元素开始的切片

最后，将上面所有的结合起来，我们可以得到下面的这个协议

图2
图2

这里分析一下双方的计算开销

  • Prover：和校验协议的计算开销为$O(n)$​，以及多项式$\tilde w(\cdot )$的承诺计算和求值的开销
  • Verifier：和校验协议的计算开销为$O(\log m)$，多项式$\tilde A,\tilde B,\tilde C$的计算开销为$O(n)$，以及多项式$\tilde w(\cdot )$求值的开销

双方之间的通信开销为：和校验协议中所需的$O(\log m)$通信开销，以及$\tilde w(\cdot )$的承诺与求值的通信开销

涉及到$\tilde w(\cdot )$的开销均取决于采用的多项式承诺方案，原文给出了三种不同的方案之间的对比

5.2 A family of NIZKs with succinct proofs for R1CS

5.1节介绍了公共掷币的交互式论证，但是还没有实现零知识性，为了加入零知识的性质，有两种比较有效的编译方法

  1. 基于Hyrax的编译器：依赖于零只是论证协议来构建点积关系和其他关系
  2. Libra和Virgo的编译器：依赖于可抽取的多项式承诺方案，此类编译器不会改变Prover和Verifier的通信开销的渐进性

原文第8节介绍了相关的编译器

6 Computation commitments: zkSNARKs for R1CS from NIZK

前面介绍了如何构建NIZK，但是方案并不是一个zkSNARK，因为Verifier在计算R1CS实例的开销仍然是线性阶的，本节介绍如何降低Verifie的开销

首先，如果R1CS实例没有特殊的结构的话，$O(n)$已经是时间上最优的了，为了进一步降低Verifier的开销，本文通过让Verifier执行一个预处理的步骤来降低开销

在协议开始前，Verifier可以访问R1CS的非io部分，并执行下列步骤（其中PC为多线性多项式的可抽取多项式承诺方案，$pp_{cc}\larr PC.Setup(1^\lambda,2\log m)$）

图3
图3

Verifier保留Encode输出的承诺（实际执行中$S_A=S_B=S_C=\bot$），之后交互式协议如第5节所示，但是需要将步骤16中计算$v_1,v_2,v_3$替换成下面计算$b_1,b_2,b_3$

图4
图4

这样一来，Verifier在预处理阶段计算三个多项式$\tilde A,\tilde B,\tilde C$的承诺$C_A,C_B,C_C$，之后在和校验协议时利用承诺和Prover提供的证明来在点$r$揭示承诺，从而将协议的Verifier开销降低至亚线性阶

重点来了，结合5.1节中的协议，总结一下

图5
图5

  1. 首先Prover计算$\tilde w$的承诺$C$，并将其发送给Verifier（上图中的第一行）
  2. 然后双方执行第一个和校验协议，Verifier验证等式$e_x=(v_A\cdot v_B-v_C)\cdot \tilde{eq}(r_x,\tau)$（上图5-7行）
  3. 若验证通过，则Verifier选择三个随机数$r_A,r_B,r_C$，双方计算$T_2$（上图第8-9行），此外Verifier还选择一个随机数$r_y$，之后双方基于$T_2$和$r_y$执行第二个和校验协议（上图第10-11行）
  4. Prover计算一个证明$v$（上图第12行）并发送给Verifier，利用该证明，Verifier验证$\tilde w$的承诺$C$的正确性（上图第13行）
  5. Prover计算$\tilde A,\tilde B,\tilde C$在随机点$(r_x,r_y)$处的求值$v_1,v_2,v_3$，Verifier用之前的承诺$C_A,C_B,C_C$验证求值的正确性（如图4所示）
  6. 若步骤4和5均验证通过，Verifier计算$\tilde Z$在$r_y$处的求值$v_Z$（上图第15行），同时将$v_1,v_2,v_3$作为三个多项式在随机点$(r_x,r_y)$处的求值，验证最终等式$e_y=(r_A\cdot v_A+r_B\cdot v_B+r_C\cdot v_C)\cdot v_Z$，验证通过则输出$b=1$

方案巧妙的点在于利用四个承诺$C,C_A,C_B,C_C$来将Verifier在$(r_x,r_y)$处对四个多项式的求值的开销降低至亚线性阶，Verifier只需要选择随机数，并要求Prover揭示对应的承诺即可

只要揭示的承诺验证通过，则Verifier就将Prover承诺的值视为多项式在该点的正确求值，并将其用于最终的验证等式

Remark 1：四个多项式的承诺使用的多项式承诺方案需要有较低的开销，且方案需要满足透明性，否则还不如线性阶的直接求值

Remark 2：Verifier的开销降低了，但是Prover的开销比较大，Verifier需要一个预处理的步骤

7 The SPARK compiler

本节介绍一个新的密码学编译器：SPARK，用于将现有的用于密集可抽取多项式承诺方案转换为可以有效处理稀疏多线性多项式的方案

本文的核心想法是通过使用zkSNARK，可以构建一个有效处理系数多线性多项式的承诺方案，目前有两个想法：Hyrax和5.2节中基于Spartan的NIZK，两者都可以做到通用结构的NP statement的亚线性Verifier开销

7.1 SPARK-naive: A straw-man solution

首先介绍Hyrax，该方案实现了均匀电路上的（尤其是数据并行电路上的）亚线性Verifier开销，Hyrax中的Prover开销与电路大小呈线性关系，Verifier开销为$O(d\log n+e)$，其中$d$为电路深度，$e$为Verifier在承诺方案中的开销

具体细节如下，令$M\in \{A,B,C\},s=\log m,\mu =2s$，根据前面提到的在一个随机点$r\in \mathbb F^\mu$处的多线性多项式求值表达式为

$$ \tilde M(r)=\sum_{i\in \{0,1\}^\mu::M(i)\neq 0}M(i)\cdot \tilde{eq}(i,r) \tag 1 $$

因为R1CS实例中的三个矩阵$A,B,C$中只有$n$个非零元素，因此上述等式中有至多$n$个点使得$M(i)\neq 0$，且求和式中每个$i$可以在$O(\mu)$次乘法中完成计算，此时考虑下面计算$\tilde M$的电路

注意到上述电路为通用的：因为相同的子电路有$n$个复制，且每个子电路需要$O(\mu)$次乘法，之后可以利用加法门，以二叉树的形式来计算最终的求和结果，此外由于数据并行单元之间没有共享的witness元素，因此可以实现真正的数据并行

基于上述方式，给定多线性多项式可抽取承诺方案$PC$，构建下列稀疏多线性多项式方案

如果使用Hyrax的承诺方案，$PC^{naive}$中Prover计算稀疏多线性多项式承诺的开销为$O(n\log n)$

7.2 Eliminating asymptotic overheads by leveraging memory checking

前面提到了，由于R1CS实例中的三个矩阵$A,B,C$均为稀疏矩阵，矩阵中只有$n=O(m)$个非零元素，但是整个矩阵有$m^2$个元素，此时如果对整个矩阵进行承诺，即便是最好的承诺方案也需要$O(m^2)$的开销

因此本文的方法是利用SPARK来降低承诺的开销，SPARK的大致思路是：与其对稀疏矩阵进行承诺，不如将该矩阵改写为一个稠密矩阵，并对稠密矩阵进行承诺，这里差个题外话，举个例子说明一下

比如我们需要对下面这个矩阵进行承诺

$$ \begin{bmatrix} 0 & 5 & 0\\ 8 & 0 & 9\\ 0 & 0 & 0\\ 0 &0 &0 \end{bmatrix} $$

此时我们可以用三个向量$raw,col,var$来压缩该矩阵（矩阵行列下标从0开始），如下

$$ \begin{aligned} raw&=[0,1,1]\\ col&=[1,0,2]\\ var&=[5,8,9] \end{aligned} $$

这样一来，通过$raw,col$对应的值，可以求出原稀疏矩阵中的非零元素$var$，从而达到压缩矩阵的目的

然后将这三个向量排列成矩阵并承诺，这样一来就可以降低对矩阵承诺的开销了

回到本文的协议，对于上面的矩阵$M$，将$r$表示为元组$(r_x,r_y),r_x,r_y\in \mathbb F^s,s=\log m=\mu/2$，此时可以将上面的多项式$\tilde M$改写成下列形式

$$ \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) $$

不过改写后的多项式仍然有$n$项，此时计算每个点仍然需要$\mu+1$次域上乘法，可以通过计算一个求值表来在$O(2^s)=O(m)$内计算$\tilde{eq}(i,r_x)$，$\tilde{eq}(j,r_y)$同理

但是利用这两个表来辅助求和仍然需要$n$次表的访问，本文的解决方案是利用Spice中的离线内存检查技术来解决这一问题，Spice的电路使用可串行化事务对持久存储上的操作进行编码

接下来描述一个大小为$O(n)$的电路来计算$\tilde M$的求值，先定义两个Hash函数$H,\mathcal H$如下

$$ H_\gamma(A,V,T)=[h_\gamma(A[0],V[0],T[0]),\dots,h_\gamma(A[l-1],V[l-1],T[l-1)]\\ h_\gamma(a,v,t)=a\cdot \gamma^2+v\cdot \gamma+t\\ \mathcal H_\gamma(\mathcal M)=\prod_{e\in \mathcal M}(e-\gamma) $$

三个Hash函数的合理性错误分别为$\frac{3}{|\mathbb F|},\frac{3\cdot l}{|\mathbb F|},\frac{3}{|\mathbb F|}$

首先定义稀疏多项式编码：对于给定稀疏多项式$\tilde M$，本文利用三个大小为$n$的向量对其编码，由于$\tilde M$表示$n$个型如$(i,j,M(i,j)),M(i,j)\neq 0$的元组，这里可以将$i,j$的$s$个比特视为$\mathbb F$中的一个域元素，此时可以令$row,col,val$为编码$n$个元组中的三个向量，此时有$k\in [n-1],row(k)=i,col(k)=j,var(k)=M(i,j)$

然后是定义用于内存检查的元数据，这些数据会在计算$\tilde M(r)$时加速内存检查，元数据由六个向量组成：$read-ts_{row},write-ts_{row},audit-ts_{row},read-ts_{col},write-ts_{col},audit-ts_{col}$，其中read,write表示读写操作相关的时间戳，audit表示离线内存检查中内存序列的最终时间戳

计算这些元数据只需要指定内存大小（$s=\log m$）和访问内存地址的序列（由$row,col$指定），相关的电路可以看原文

8 Implementation and optimizations/Experimental evaluation

最后是一些性能优化和实现，具体可以看原文和相关的github仓库

References

$[1]$ Srinath T. V. Setty:Spartan: Efficient and General-Purpose zkSNARKs Without Trusted Setup. CRYPTO (3) 2020: 704-737

$[2]$ Spartan: Efficient and general-purpose zkSNARKs without trusted setup - YouTube

$[3]$ microsoft/Spartan: Spartan: High-speed zkSNARKs without trusted setup (github.com)