Abstract

在本文构建了一个Prover的计算开销几乎为线性阶的零知识证明系统，若假设存在线性时间可计算的抗碰撞Hash函数，则本文的方案满足完美完备性，统计诚实验证者零知识性和计算知识合理性

本文通过TinyRAM模型来捕获通用处理器中的计算，实例由TinyRAM程序和公共输入组成，witness包含程序的私有输入

本文的证明系统的主要优点是具有渐进有效的Prover计算，且循环轮数仅为对数阶，Verifier的运行时间和通信开销与程序执行时间呈亚线性关系

1 Introduction

ZKP的应用场景很多，比如构建可抵抗CCA攻击的公钥加密方案、数字签名方案，投票系统，电子现金，可验证外包计算等等，但是ZKP的高复杂性会显著影响这些应用的性能，因此ZKP的计算效率决定了其在这些应用中的可用性

大部分ZKP方案通过算术电路或布尔电路的可满足性来构建，但是实际应用中需要证明的statement通常是一个与程序执行相关联的statement，比如：在给定公共输入$x$和私有输入$w$，运行指定程序$P$，程序的输出为$z$，理论上此类问题可以归约至电路可满足性问题，但是此类归约会产生大量的计算开销

对于ZKP方案的性能而言，有许多衡量标准，一般主要考量Prover和Verifier的运行时间，执行效率（需要的代数操作的数量），双方之间的通信量和协议执行的轮数，现阶段的方案在Verifier时间、通信开销和轮数均有很大程度的优化，但是Prover运行时间成为了系统的瓶颈，也是部分应用程序（比如可验证外包计算）的主要障碍，

综上，本文主要关注如何从一个与程序执行相关的statement中构造一个具有高效Prover的ZKP系统

1.1 Out Contribution

本文采用TinyRAM模型$[BG+13,BSCG+13]$进行计算，TinyRAM包含一个具有小指令集的随机访问机（Random Access Machine），用于处理宽度为$W$比特的字和地址（TinyRAM的规范可以参考Harvard架构处理器，该架构的规范要求执行中的程序与正在处理的数据分开存储，且执行过程中不会改变，根据$[BG+13]$的结论，任何C语言编写的程序均可有效的编译为TinyRAM程序，且编译过程的开销恒定）

本文的证明系统采用公共掷币方式，实例由TinyRAM程序$P$和提供给该程序的公共数据组成，witness为程序的私有输入，对应的statement为：在给定公共输入和私有输入上运行$P$，其会在特定的时间和内存范围内终止并输出0

本文采用$[BG+13,BSCG+13]$的TinyRAM模型进行计算，利用线性时间可计算Hash函数，可以得到图1中的渐进效率（Prover和Verifier均视为字大小相同的TinyRAM程序），经分析，本文的方案适用于计算密集型的场景

这里有一点需要注意：方案需要用到公共参数，不过公共参数可以从一个小的URS中导出，计算步骤也很简单，因此对整体系统的效率影响可以忽略不计

此外，这个公共参数可以有一些变体，利用变体可以有效证明参数的结构是否正确，利用这一点，证明系统可以实现让Prover在不信任参数的情况下获得诚实Verifier的零知识证明的属性，这意味着参数可以由Verifier指定，从而系统可以在无需Setup的普通模型中工作

基于上面这一点，由于公共参数独立于实例，因此本文的做法是将公共参数分离到一个单独的setup中，从而其可以用于多个独立的证明

‍

1.2 New techniques

根据Ben-Sasson等人的方法，在TinyRAM程序的证明系统中，Prover需要对按照时间排序的执行轨迹和按照地址排序的内存轨迹进行承诺，通过将描述特定时间下TinyRAM状态的字、内存地址和标志位嵌入到域元素中，之后利用电路来检查$t$时刻和$t+1$时刻之间的执行轨迹转换的正确性，利用另一电路来检查特定地址读写内存的正确性，最后利用一个嵌入置换网络的电路来检查两个轨迹之间的内存一致性，从而验证TinyRAM的计算正确性，由于证明的每个步骤中可以使用相同的电路来证明状态转换，因此可以通过批处理的方式来将计算开销平摊到多个电路中

将上述方法与$[BBC+17]$中的线性时间的算术电路可满足性证明结合在一起，可能可以获得亚线性通信开销的证明系统，但是与TinyRAM的时间开销相比，由于嵌入置换网络的电路需要对数数量的线性层来描述置换，处理逻辑运算需要分解为域上的位运算，也会增加开销

对于置换网络的开销，本文通过将内存一致性与某个置换相关联来代替原来的置换网络，该置换将执行轨迹中的一次内存地址访问映射到执行轨迹中同一内存地址的下一次访问，经分析，本文的置换证明需要线性次数的域运算，而对于位分解的开销，本文引入了新的分解方式，并通过查找证明来检查域元素是否在某个允许的值表内，从而降低逻辑运算的开销

综上，本文结合$[BCG+17]$来构造本文的证明系统

‍

2 Preliminaries

先介绍一下本文的一些概念和符号记法

  • $y \larr A(x)$：输入$x$，输出$y$
  • $y \larr A(x;r)$：函数以随机性$r$作为输入
  • $\lambda$：安全参数
  • $[n]$：表示正整数集合$\{1,\dots,n\}$
  • $\boldsymbol v$：表示有限域$\mathbb F$上的向量
  • $\overset{chan}{\longleftrightarrow}$：Prover和Verifier通信的信道
  • $view_V\larr <P(s) \overset{chan}{\longleftrightarrow} V(t)>$：Prover和Verifier的输入分别为$s,t$，$view_V$表示Verifier执行过程中的视角
  • $trans_P\larr <P(s) \overset{chan}{\longleftrightarrow} V(t)>$：Prover和Verifier之间的交互脚本
  • $<P(s) \overset{chan}{\longleftrightarrow} V(t)>=b$：若$b=1$则表示接受，否则表示拒绝
  • $\longleftrightarrow$：标准信道
  • $\overset{ILC}{\longleftrightarrow}$：表示理想线性承诺信道（Ideal Linear Commitment channel，ILC），如图2所示，Prover可以利用ILC信道对固定长度的域元素向量进行承诺

本文为公共掷币的证明系统，且ILC信道中的三个操作$(commit,send,open)$可以任意排列执行，因此可以不失一般性的假设Verifier仅在协议末尾发起一次大的承诺揭示请求

  • $\mathcal R=(pp,u,w)$：表示可以高效决定的关系
  • $\mathcal L=\{(pp,u)|\exist w:(pp,u,w)\in \mathcal R\}$：关系$\mathcal R$对应的语言

2.1 Proof of knowledge

本文沿用$[BBC+17]$中的定义，证明系统定义为三个有状态PPT算法$(K,P,V)$，其中setup算法$K$仅运行一次，用于输出$P,V$所需要的公共参数$pp$，根据前面提到的，$pp$是可公开验证的（甚至可以是Verifier生成的），因此安全性分析中可以假设$K$是可信的

对于信道$\overset{chan}{\longleftrightarrow}$上关系$\mathcal R$的协议$(K,P,V)$，若满足完美完备性，计算知识合理性，则称其为知识证明（Proof of Knowledge）

本文构建的证明系统为具有特殊诚实Verifier零知识性（Special HVZK）的公共掷币知识证明，由于SHVZK仅可以确保模拟器适用于诚实Verifier，而某些应用中要求模拟器在适用于恶意的Verifier仍然满足零知识性，安全性较弱，但是可以用FS变换来将协议变为非交互式的，从而提高这一安全性，此时协议在随机预言机中满足完全零知识性

若随机预言机不可取，则另一个选择是在Prover和Verifier之间采用硬币翻转（coin flipping）来决定挑战，可以令$pp$包含一个陷门承诺方案，Prover对$\delta_1,\dots,\delta_\mu$进行承诺并开始执行协议，对于协议第$i$轮Verifier的挑战$\rho_i$，Prover将挑战修改为$\rho_i'=\rho_i\oplus \delta_i$，协议结束时Prover再揭示$\delta_i$的承诺

上述硬币翻转的方式可以向模拟器提供一个模拟陷门，陷门可以用于模拟证明过程中的公共掷币挑战$\rho_i'$，从而使得模拟器可以完成模拟

2.2 TinyRAM

TinyRAM是使用$K$个寄存器在字长为$W$比特上运行的随机存取模型，具体可以参考$[BSCG+13]$，TinyRAM的状态包含下列几项

  • 程序$P$，表示为包含$L$个指令的列表
  • 程序计数器$pc$，大小为$W$
  • $K$个寄存器$\{reg_0,\dots,reg_{K-1}\}$，大小均为$W$，第$i$个寄存器$reg_i$中的数据记为$r_i$
  • 状态标志位$flag$，大小为单比特
  • $M$个长度为$W$的内存地址$0,\dots,M-1$

TinyRAM的初始化过程会先将初始输入读入内存（未使用的内存置0），同时将$pc$和$flag$置0，程序为一个包含$L$个指令的列表，指令内容及其含义如表1所示（和汇编差不多），程序采用返回命令终止，返回命令会返回一个字，若为0则表示程序成功，否则表示失败

TinyRAM中区分有符号数据和无符号数据，有符号数据的计算采用角标$s$表示，比如有符号乘法$\times_s$和有符号比较$a\geq _s b$

​

TinyRAM模型中需要检查协议参与者在公共输入$x$和私有输入$w$上运行程序$P$是否提供了正确的程序输出$z$，不失一般性，可以将这一检查转换为一个扩展程序$v=(x,z)$，当且仅当$z$为程序输出时，该扩展程序输出0

本文将TinyRAM程序执行定义为四元组$u=(P,v,T,M)$，其中$v$表示程序$P$的输入字序列，$T$表示时间界，$M$表示内存大小，witness $w$为另一字序列（不失一般性假设$|v|+|w|=M$，可通过填充0完成），需要证明的关系如下图所示，表示在公共输入$x$和私有输入$w$上采用$M$个寄存器运行程序$P$，程序会在$T$步内结束并输出0

本文的方案主要关注需要大量计算的程序，因此本文假设$T>L+M$

3 Proofs for the Correct Program Execution over the ILC Channel

本节从宏观的角度看一下ILC信道上的TinyRAM程序证明系统，以自顶向下的方式描述如何在ILC模型中验证程序是否正确执行，如图11所示

在ILC信道中，Prover可以对长度为$k$的域元素向量进行承诺（域$\mathbb F$和向量长度$k$由公共参数指定），向量会秘密保存在信道内，Verifier可以利用信道向Prover发送消息或请求揭示一个向量的承诺

第一层描述ILC模型中如何证明TinyRAM的正确执行，根据前面介绍的，这一层可以分解为三个关系$\mathcal R_{mem},\mathcal R_{check},\mathcal R_{step}$，此外还需要一个关系$\mathcal R_{format}$，用以验证承诺值具有正确的格式

第二层中，将上述四个关系分解为若干个通用关系$\mathcal R_{const},\mathcal R_{perm},\mathcal R_{range},\mathcal R_{eq},\mathcal R_{blookup},\mathcal R_{lookup}$（分解方式详见原文附录A）

第三层中，将上述通用关系进一步分解为ILC中的元素关系，包括求和，乘积，移位，分解方式详见原文附录B

第四次和最后一层为再ILC中证明第三层中的元素关系，具体证明方式详见附录A

各个子关系的具体构造在本系列的Part 2中介绍

3.1 Commitments to the Tables

本方案中首先需要对扩展witness进行承诺，扩展witness包括执行表$Exe$，程序表$Prog$，范围表$EvenBits$和指数表$Pow$，每个表视为一个矩阵

Prover首先对$Exe$表的各个列进行承诺，方式如下：假设$Exe$表有$T$行（不失一般性，假设$T=(l-1)\cdot k-1$，其中$k$表示ILC向量承诺的长度），首先将每一列排列成一个$l\times k$的矩阵，且该矩阵中自第二列起，每一列的第一个元素与前一列的最后一个元素相等，其余元素依次排列

以$Exe$表的第一列（时间列）为例，排列得到时间矩阵$E_t$，之后Prover对该矩阵按行进行ILC向量承诺

Prover依次处理$Exe$表中的每一列，得到每一列的矩阵$E_t,E_{pc},\dots$，之后将这些矩阵叠加，得到一个大矩阵$E=\{e_i\},e_i\in \mathbb F^k$，并用ILC对该矩阵承诺

之后Prover需要用关系$\mathcal R_{format}$，证明$Exe$表的每一个列矩阵的最后一行都是第一行的移位

$Prog$表的承诺方式如下，假设$L\leq k$，Prvoer将$Prog$的每一列按行排列，并对其承诺，$Mem$表，$EvenBits$表，$Pow$表承诺方式类似，如下图所示（$(k_{W/2-1},\dots,k_0)$为$k$的二进制形式）

3.2 Proof for Correct TinyRAM Execution in the ILC Model

对于给定的witness，图12给出了Prover和Verifier如何利用ILC信道完成对关系$\mathcal R^{field}_{TinyRAM}$的证明

图13为对应的效率分析，这里假设ILC承诺向量的大小$k$约等于$\sqrt T$，记$\mu$为协议的总交互轮数，每一轮交互中Prover发送的承诺向量的数量记为$t_i$，总数量为$t=\sum_i^\mu t_i$

由于每个子证明都满足完美完备性，完美特殊HVZK，统计知识合理性，模拟脚本可以通过组合所有子关系的模拟脚本来获取，且所有子证明均具有可抽取知识合理性，因此主证明也满足这些性质

4 Proofs for the Correct Program Execution over the Standard Channel

第3节中介绍了ILC模型中的用于验证TinyRAM程序的SHVZK知识证明，本节利用$[BBC+17]$中的编译器将其转换为标准信道模型中的SHVZK知识证明，标准模型中Prover和Verifier会直接交换消息

$[BBC+17]$中的编译器采用Hash函数实现非交互式的承诺方案，并用纠错码和Hash函数实现CRS

Linear Error-Correcting Codes With Linear Distance

域$\mathbb F$上的线性纠错码将长度为$k$的消息通过映射$E_C$编码为长度为$n$的码字，码率为$\frac{k}{n}$，最短汉明距离记为$hd_{\min }$，$[BBC+17]$中采用了码率为常量且具有线性最短距离的高效编码方式来生成码字

Linear-Time Non-Interactive Commitments

Halevi和Micali$[HM96]$的结果表明，抗碰撞Hash函数可以得到满足统计隐藏性的紧凑承诺方案，本文利用Applebaum等人$[AHI+17]$的线性时间hash函数构造了本文的公共掷币的统计隐藏承诺方案

4.1 Compiling ILC proofs into the Proofs over the Standard Channel

记$(K_{ILC},P_{ILC},V_{ILC})$为ILC上的关系$\mathcal R$的证明，Bootle等人介绍了如何利用ILC参数来生成对应的线性距离线性纠错码$E_C$和对应的承诺密钥$ck$​

图14介绍了ILC模型的实例化，核心思想首先将向量映射到码字，然后将承诺方案应用到码字中来完成对向量的承诺

为了确保效率，纠错码每次会处理$m$个向量$v_1,\dots,v_m$，首先将这$m$个向量按行排列为一个矩阵$V$，之后定义矩阵$E=E_C(V)$，矩阵的每一行$e_i$对应于向量$v_i$的码字，记$E_j$表示矩阵$E$​的第$j$列

Prover将码字矩阵按列进行承诺，对于Verifier发起的请求$\boldsymbol q=(q_1,\dots,q_m)$，Prover计算一个线性组合$\boldsymbol v=\boldsymbol qV=\sum_i^m q_i\cdot \boldsymbol v_i$

之后Verifier此时请求揭示$E$中$\lambda$列$\{j_1,\dots,j_\lambda\}$，Prover揭示对应的承诺$\{c_{j_1},\dots,c_{j_\lambda}\}$，若Prover为诚实的，则有$\boldsymbol v=\sum_i^m\boldsymbol v_i$，由于纠错码满足线性的性质，此时有$E_c( \boldsymbol v)=\sum^m_iq_i\cdot \boldsymbol e_i$​，Verifier检查是否有$E_C(\boldsymbol v)_j=\boldsymbol qE_j$，从而验证Prover的线性组合$\boldsymbol v=\boldsymbol qV$

由于码字具有线性最短距离，除非对矩阵$E$的每一行的承诺接近于一个码字，且向量满足线性组合$\boldsymbol v=\boldsymbol qV=\sum_i^m q_i\cdot \boldsymbol v_i$，否则恶意的Prover成功作弊的概率可以忽略

但是上述方法并不满足零知识性，因为揭示的码字会泄露关于编码的向量，因此需要将编码替换为具有随机Exposure-Resilient性质的编码方式

Exposure-Resilient的概念具体可以参考$[2,3]$，这里大致介绍一下

$[2]$中定义了Exposure-Resilient Function，已知几乎所有的输入比特的情况下，该函数的输出看起来也是完全随机的（可以满足完美、统计、计算性）
ERF可以解决密钥为随机值时部分密钥暴露的安全问题，该函数也可以视为安全的伪随机生成器，可以作为组件用于构建其他密码方案

4.2 Efficiency of the compiled TinyRAM Proof System

方案要求参数$T,M$为安全参数$\lambda$多项式，也即$T=poly(\lambda),M=poly(\lambda)$，这里假设$T,M\geq \lambda$

为了寻址所有内存，同时需要确保电路大小在适当的范围内，本文假设字长$W=\Theta(\log \lambda)$，但是当字长为超对数（superlogarithmic）时效率会有所下降

为了确保方案具有可忽略的知识误差，本文要求域大小为超多项式（superpolynomial），也即$|\mathbb F|=\lambda^{\omega(1)}$

本文的证明系统适用于运行时间较长的场景，因此本文假设$T\gg L+M$，ILC证明中，Prover需要承诺$O(T)$个域元素，并进行$O(T)$次域运算，Verifier只需要$O(L+|v|+\sqrt T)$次域运算，具体的效率分析见图15

References

$[1]$ Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune K. Jakobsen, Mary Maller:Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution. IACR Cryptol. ePrint Arch. 2018: 380 (2018)

$[2]$ Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, Amit Sahai:Exposure-Resilient Functions and All-or-Nothing Transforms. EUROCRYPT 2000: 453-469

$[3]$ Yevgeniy Dodis:Exposure-resilient cryptography. Massachusetts Institute of Technology, Cambridge, MA, USA, 2000