Halo：incremental verification + SNARKs without pairings

1. 引言

ZK-SNARKs通常需要验证等式是否成立。可将等式中的elements 数学抽象为 多项式 或 R1CS矩阵和向量，这种数学抽象可承载大量数据。

当前支撑以上数学抽象的密码学技术主要分为3大类：

• 1）Merkle trees：用于 FRI。对应为STARKs。
• 2）regular elliptic curves：用于 inner product arguments (IPAs)。对应为Bulletproofs。
• 3）elliptic curves with pairings and trusted setups：用于 KZG commitments。对应为“regular” SNARKs。

这3种技术的对比为：

Technology基于的密码学假设Proof sizeVerification timeFRIHashes only（quantum safe!）Large（10-200kB）Medium（poly-logarithmic）Inner product arguments (IPAs)Basic elliptic curvesMedium (1-3 kB)Very high (linear)KZG commitmentsElliptic curves + pairings + trusted setupShort (~500 bytes)Low (constant)IPA + Halo-style aggregationBasic elliptic curvesMedium (1-3 kB)Medium (constant but higher than KZG)

第一种和第三种技术最受关注。第二种技术（IPAs）具有linear verification time，即意味着： 尽管proof size小，但是verify proof所需的时间几乎总要 长于 自己直接运行计算的时间。

这就使得IPAs不适于用于扩容相关的ZK-SNARK场景： 没必要使用IPA-based argument来证明以太坊某一区块的有效性，因为verify proof所需时间 要长于 直接验证该block所需时间。

而KZG-based argument和FRI-based argument，其proof verify时间 要远远快于 自己直接运行计算所需的时间。

但是，最近的一些研究，支持将多个IPA proof合并为一个IPA proof。详细可看：

• Zcash halo2 背后技术衍化介绍

将多个IPA proof合并为一个IPA proof的合并技术是cheap的，而对合并后的IPA proof验证的时间 与 验证其中某一IPA proof所需的时间 相当。 这就使得，可将：

• 验证a size- n n n computation proof所需的时间为 O ( n ) O(n) O(n)

转为：

• 将size- n n n的computation 切分为更小的 size- k k k steps，为每个step生成一个proof，一共生成 n k \frac{n}{k} kn​个proof，将这些proof 合并为一个proof，验证 合并后的proof 时间为 a little more than O ( k ) O(k) O(k)。

这种合并技术还可用于incremental verification：

• 若持续有待证明的新事物，则可利用 现有proof + 新statement的proof，得到 a proof of the new combined statement。

incremental verification可用于验证完整性——如整个区块链的完整性。

2. Inner product argument

Inner product argument基础知识可参看：

• Zero-knowledge inner product argument（IPA）
• 内积证明

IPA不需要pairing运算，可使用任意椭圆曲线，哪怕是比特币和以太坊使用的secp256k1曲线，但是，为了可使用FFT加速，通常会选择具有FFT friendly order的曲线，详细可看：

• FFT friendly域内的lagrange polynomial计算

根据Bulletproofs: Short Proofs for Confidential Transactions and More学习笔记第3节可知，Inner product argument针对的场景经历了如下衍化：

• 1）Bootle 2016方案中的基本信息表达为：

  • public info： z ∈ Z p , A , B ∈ G , g ⃗ , h ⃗ ∈ G n z\in\mathbb{Z}_p,A,B\in\mathbb{G},\vec{g},\vec{h}\in\mathbb{G}^n z∈Zp​,A,B∈G,g ​,h ∈Gn
  • private info： a ⃗ , b ⃗ \vec{a},\vec{b} a ,b
  • relation： A = g ⃗ a ⃗ ∧ B = h ⃗ b ⃗ ∧ a ⃗ ⋅ b ⃗ = z A=\vec{g}^{\vec{a}}\wedge B=\vec{h}^{\vec{b}}\wedge \vec{a}\cdot\vec{b}=z A=g ​a ∧B=h b ∧a ⋅b =z

• 2）Bulletproofs论文中对待证明relation的修改，使得communication complexity 由 6 log ⁡ 2 ( n ) 6\log_2 (n) 6log2​(n)降为了 2 log ⁡ 2 ( n ) 2\log_2(n) 2log2​(n)。（注意此处的inner product为sound的，但不是zero-knowledge的） 基本信息表达为：

  • public info： c ∈ Z p , P ∈ G , g ⃗ , h ⃗ ∈ G n c\in\mathbb{Z}_p,P\in\mathbb{G},\vec{g},\vec{h}\in\mathbb{G}^n c∈Zp​,P∈G,g ​,h ∈Gn
  • private info： a ⃗ , b ⃗ \vec{a},\vec{b} a ,b
  • relation： P = g ⃗ a ⃗ h ⃗ b ⃗ ∧ a ⃗ ⋅ b ⃗ = c P=\vec{g}^{\vec{a}}\vec{h}^{\vec{b}}\wedge \vec{a}\cdot\vec{b}=c P=g ​a h b ∧a ⋅b =c

  进一步等价表达为：

  • public info： u , P ∈ G , g ⃗ , h ⃗ ∈ G n u,P\in\mathbb{G},\vec{g},\vec{h}\in\mathbb{G}^n u,P∈G,g ​,h ∈Gn
  • private info： a ⃗ , b ⃗ \vec{a},\vec{b} a ,b
  • relation： P = g ⃗ a ⃗ h ⃗ b ⃗ ⋅ u < a ⃗ ⋅ b ⃗ > P=\vec{g}^{\vec{a}}\vec{h}^{\vec{b}}\cdot u^{} P=g ​a h b ⋅u

2.1 将Inner product argument用于Polynomial commitment scheme

参考资料有：

• proof-carrying data from accumulation schemes学习笔记
• proof-carrying data from accumulation schemes代码解析
• Halo Infinite: Proof-Carrying Data from Additive Polynomial Commitments
• Halo: Recursive Proof Composition without a Trusted Setup 学习笔记

对于多项式 f ( X ) = ∑ i = 0 d a i X f(X)=\sum_{i=0}^{d}a_iX f(X)=∑i=0d​ai​X，为了证明 f ( z ) = c f(z)=c f(z)=c，当将inner product argument用于polynomial commitment scheme时，相当于 b ⃗ = ( 1 , z , z 2 , ⋯   , z d ) \vec{b}=(1,z,z^2,\cdots,z^d) b =(1,z,z2,⋯,zd)， b ⃗ \vec{b} b 由private info转为public info，具体的场景改为：

• public info： z ⃗ 0 = ( 1 , z , ⋯   , z d ) ∈ F q d + 1 \vec{z}_0=(1,z,\cdots,z^d)\in\mathbb{F}_q^{d+1} z 0​=(1,z,⋯,zd)∈Fqd+1​ 和 G ⃗ 0 = ( G 0 , G 1 , ⋯   , G d ) ∈ G d + 1 \vec{G}_0=(G_0,G_1,\cdots,G_d)\in\mathbb{G}^{d+1} G 0​=(G0​,G1​,⋯,Gd​)∈Gd+1， v ∈ F q v\in\mathbb{F}_q v∈Fq​， C ′ ∈ G C'\in\mathbb{G} C′∈G。
• private info： c ⃗ 0 = ( c 0 , c 1 , ⋯   , c d ) ∈ F q d + 1 \vec{c}_0=(c_0,c_1,\cdots,c_d)\in\mathbb{F}_q^{d+1} c 0​=(c0​,c1​,⋯,cd​)∈Fqd+1​
• relation： < c ⃗ 0 , z ⃗ 0 > = v =v =v且 C ′ = ∑ i = 0 d c i G i C'=\sum_{i=0}^{d}c_iG_i C′=∑i=0d​ci​Gi​

详细的基于inner product argument实现的polynomial commitment scheme可参看博客 proof-carrying data from accumulation schemes学习笔记 第1.5节“基于discrete logarithm 构建的polynomial commitment”内容。

基于IPA构建的polynomial commitment scheme，Verifier的验证计算压力较大，可借助Halo: Recursive Proof Composition without a Trusted Setup 学习笔记 中 第3.1节“Amortization Strategy摊销策略”引入helper角色（可与Prover复用）来减轻Verifier的计算压力。

基于IPA实现的polynomial commitment scheme 相应的代码示例有：

• https://github.com/ethereum/research/blob/master/bulletproofs/ipa_commitments.py（Python，不具有zero-knowledge）
• https://github.com/arkworks-rs/poly-commit/tree/master/src/ipa_pc（Rust语言，引入了randomizer实现了hiding属性，具有zero-knowledge）

2.2 合并多个polynomial commitment opening arguments

核心思想为借助commitment的同态属性，引入不同的challenge：

• 1）将open在同一point的不同多项式合并为一个多项式。
• 2）将open在不同point的 quotient polynomial f ( X ) − f ( z 0 ) X − z 0 , g ( x , Y ) − g ( x , y 0 ) Y − y 0 \frac{f(X)-f(z_0)}{X-z_0},\frac{g(x,Y)-g(x,y_0)}{Y-y_0} X−z0​f(X)−f(z0​)​,Y−y0​g(x,Y)−g(x,y0​)​ 合并为一个quotient polynomial。
• 3）将1）和2）合并为一个多项式。从而转为单polynomial commitment opening argument。

也可引申扩展为对多个R1CS proof的合并。详细可参见 Halo: Recursive Proof Composition without a Trusted Setup 学习笔记 第4.1节“合并多个polynomial commitment opening arguments” 和 第4.3节“a sequence of 同一arithmetic circuit arguments的完整协议实现”。

3. Incremental verification

仍然回到引言中讨论的应用场景： 验证整个区块链的有效性。

由于2.2中实现了可将多个IPA proof合并为一个IPA proof，从而可切分为小的steps，每个step可小到为 a single step of a virtual machine。

参考资料

[1] Halo and more: exploring incremental verification and SNARKs without pairings