ZKP研究现状

首先得知道研究成果主要发表在哪里

理论方面的成果主要发表在三大密码会和TCC上，而应用成果主要是ACM CCS、SP、Usenix以及各种现实的密码学应用，包括但不限于各种链，Github仓库等等

近二十年来，ZKP的研究主要集中在六个方向

  • Lookup argument：主要思想是利用查表代替计算，从而减少验证的计算开销
  • Linear Time Provers：希望尽可能的减小Prover的计算开销，从而提高证明系统的处理能力
  • Vector Commitments：向量承诺经常出现在各种方案中，最大的优点就是可以将一个很长的向量压缩到一个固定大小的承诺值上
  • Recursive Argument：对证明的证明进行证明，在延迟可验证函数中会用到
  • Post-Quantum Signature：以ZK的方式构建抗量子签名方案，具体不太清楚，但是三大密码会上均有相关论文
  • Forking Lemmas：对分叉引理的研究很重要，因为他是多签名和格密码学的研究基础，也是可证明安全性理论的基础之一

‍

Recursive Argument

递归证明可以对证明的证明进行证明

比如Nova，其递归的计算开销为两次群乘法，Prover的开销为2次大小为$O(|F|)$的群幂运算

举个例子，如果有两个证明，分别是$(A\vec x)\cdot (B\vec x)=0$和$(A\vec y)\cdot (B\vec y)=0$，利用递归证明可以整合成$(A(\vec x+\gamma \vec y))\cdot (B(\vec x+\gamma \vec y))=0+\gamma^2 [\_]$

$[BCLMS21]$改进了Nova，Halo又改进了$[BCLMS21]$，使得其仅基于DLOG假设的承诺，无需FFT，也无需PCP证明系统

$[BCLMS21]$：Proof-Carry Data without Succinct Arguments

$[BGH19]$：Halo:Recursive Proof Composition without a Trusted Setup

$[KST22]$Nova:Recursive Zero-Knowledge Arguments from Folding Schemes

‍

Linear Time Provers

此方面的研究主要是为了提高Prover的计算效率，尽可能地减少Prover的计算时间

然而证明的生成时间已经成为了目前大多数证明系统的效率瓶颈，为了尽可能的减小证明大小，大部分SNARK的Prover time都是拟线性的（Quasi-Linear），因为需要计算大量的多项式乘法来压缩证明串

此外还有一个问题，由于多项式乘法基本不可能实现并行处理，所以这也是导致效率难以优化的主要原因之一

最近有不少成果做到了Linear-Time Prover，接下来介绍几个比较具有代表性的

  • HyperPlonk：基于IOP的Plonkish约束系统，可以实现定制的门，所有的操作均在布尔超立方（boolean hypercube）上完成
  • Orion：一种基于高效纠错码的Linear time Prover，方案基于Brakedown改进，加u人了码交换技术，可以将证明大小和Verifier time减小至$\log ^2N$
  • $[BCL22]$：一种基于R1CS的IOP证明系统，通过结合了组合证明，将证明大小和Verifier time减小至$\log ^2N$
  • $[BCHO22]$：从内存的角度考虑SNARK的设计与应用，因为内存也是系统性能的一部分，这篇paper给出了鹅两种方案，分别做到拟线性的内存开销和线性Prover，或者线性内存开销和拟线性的Prover

尽管有这么多的方案可以将Prover的时间压缩至线性，但是他们都无法做到在确保证明大小为常数的同时实现线性Prover Time

$[CBBZ22]$：HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates

$[XZS22]$：Orion: Zero Knowledge Proof with Linear Prover Time

$[BCL22]$：Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier

$[BCHO22]$：Gemini: Elastic SNARKs for Diverse Environments

‍

Forking Lemmas

从理论上来说，研究分叉引理主要是因为多轮论证和FS变换并不能很好的结合在一起

举个例子，Bulletproof作为一个需要多轮递归完成的证明，其非交互性协议的安全性在很长一段时间内都没有得到证明

而从实践角度来说，似乎并没有对分叉引理有一个比较清晰的认知，所以一直是睁一只眼闭一只眼的状态

不过最近两年有一些新的研究成果，比如$[ACK21]$和$[AF22]$，这些成果表明FS变换实际上是没啥问题的

$[ACK21]$：A Compressed Σ-Protocol Theory for Lattices

$[AF22]$：Parallel Repetition of $(k_1, \dots , k_μ )$-Special-Sound Multi-round Interactive Proofs

‍

Lookup Argument

还是Prover Time的问题，不过查表论证换了一个角度来优化

因为生成和验证证明都需要计算，那lookup的思路就是利用查表的方式来取代一部分的计算，然后再结合高效的算术运算来加快证明的时间

因为一个很大的计算可能需要大量的约束条件，其中有些约束可能会被频繁用到，而与其在每次用到这些约束时重新计算，不如直接预计算这些约束，然后在用到的时候通过查表的方式访问即可

举个例子，比如有两个多项式$C(X),\phi(X)$如下

$$ C(X)=\lambda_1(X)+2\lambda_2(X)+...+n\lambda_n(X)\\\phi(X)=a_1\lambda_1(X)+...+a_n\lambda_n(X) $$

此时我想证明所有的$a_i$都在$\{1,...,n\}$内

有一个方法可以完成：我们可以证明，对于所有的$w_i$，都存在一个$w_j$，满足$\phi(w_i)=C(w_j)$

具体的Lookup方案可以看halo2的标准和Plonkish算术话，这里给一个Halo2的文档：zcash.ithub.io/halo2

除此之外，也有paper利用了lookup构建证明方案，比如Plonkup方案$[GW20]$，对于比较小的表来说优化的不错，且该方案基于Bulletproof、KZG承诺和FRI

还有$[CFHKKO22]$，该方案基于隐藏阶群构建，对较大的表进行了优化，且对表的大小无限制

$[GK22]$， 基于KZG群，同样对大表进行了优化，但是对集合成员有一定限制

Baloo：Caulk/Caulk+的后续工作，对大表进行了优化，基于KZG进行实例化，prover time为查找次数的拟线性阶，且与表的大小无关

$[GW20]$：plookup: A simplified polynomial protocol for lookup tables

$[CFHKKO22]$：Succinct Zero-Knowledge Batch Proofs for Set Accumulators

$[GK22]$：flookup: Fractional decomposition-based lookups in quasi-linear time independent of table size

$[ZBKMNS22]$：Caulk: Lookup Arguments in Sublinear Time

$[PK22]$：Caulk+: Table-independent lookup arguments

$[ZGKMR22]$：Baloo: Nearly Optimal Lookup Arguments

‍

PQ Signatures

NIST标准委员会对后量子签名提出了新的要求，要求其不基于格来构建

主要想法是任何方案都可能会被攻破，DLOG、格、配对都有可能会被攻破，NIST希望有备案，确保一个方案被攻破时有其他的备案，所以希望有一些不基于格构建的签名方案，比如基于纠错码的方案

基于纠错码的常用构建方式是利用MPC-in-the-head来证明hash原像的知识

目前PQ签名方案比较有代表性的是下列这些

  • $[FJR22]$：基于线性码的综合解码的困难性
  • $[BGKOSZ21]$：基于反向AES的困难性
  • $[KZ22]$：Picnic4$[Cha+17,Cha+19]$，基于反向LowMC的困难性（LowMC$[Alb+15]$是SPN架构中的一种方案）

$[FJR22]$：Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs

$[BGKOSZ21]$：Banquet: Short and Fast Signatures from AES

$[KZ22]$：Efficient Lifting for Shorter Zero-Knowledge Proofs and Post-Quantum Signatures

$[Cha+17]$：Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives

$[Cha+19]$：The Picnic Signature Scheme Design Document (version 2)

$[Alb+15]$：Ciphers for MPC and FHE

‍

教育资源

最近几年ZKP的学习资源确实比较匮乏（自己整理的时候也这样感觉），不过也有一些值得学习的内容，整理如下

文档

  • ZKProof Community Reference

zkpstandard/zkreference: The official repository hosting the ZKProof Community Reference & Proposals documents. (github.com)

  • Probabilistic Proof Systems：COSC544 - Fall 2020 Prof. Justin Thaler

Link:COSC 544 - Probabilistic Proof Systems

  • Proofs, Arguments, and Zero-Knowledge：也是Justin Thaler教授写的，目前最新的一版是2022年11月1日的这般
  • 第九届BIU密码学冬令营 - Zero Knowledge专题

Youtube:The 9th BIU Winter School on Cryptography

  • The MoomMath Manual to ZK-SNARKS：一个比较容易读懂的SNARK教程，实际上这是一个区块链项目，旨在zkSNARK的教学

Gitcoin:The MoonMath Manual to zk-SNARKs

Github:LeastAuthority/moonmath-manual

  • The Mathematics behind zkSNARKS：zkSNARK背后的数学

Youtube:The Mathematics behind zkSNARKS

  • Modern Computer Algebra：目前最新的是第三版，原书很贵且不免费，不过书里面介绍了很多重要的算法，包括SNARK需要用到的各种多项式运算和操作
  • Guide To Pairing-based Cryptography：详细介绍了配对的一些细节

只找到了电子版，而且只有第三章

相关网站

  • ZKProof：（应该是）最大的ZKP社区

Link：zkproof.org

  • ZK Podcast：也是一个ZKP网站，社区规模也不小

Link：zeroknowledge.fm

  • ZK HACK：ZKP相关的挑战

Link：zkhack.dev

博客

以V神、各大学者和medium为主

论坛

  • zkhack的论坛：askcryp.to

ZKP的应用

  • 单一秘密领袖选择（Single Secret Leader Election）：以太坊，filecoin都在用
  • 可验证延迟函数（Verifiable Delay Function）：
  • zk-VM：又称为可验证计算，包括tinyRAM等等