篇首语:本文由小编为大家整理,主要介绍了Halo:incremental verification + SNARKs without pairings相关的知识,希望对你有一定的参考价值。
ZK-SNARKs通常需要验证等式是否成立。可将等式中的elements 数学抽象为 多项式 或 R1CS矩阵和向量,这种数学抽象可承载大量数据。
当前支撑以上数学抽象的密码学技术主要分为3大类:
这3种技术的对比为:
Technology | 基于的密码学假设 | Proof size | Verification time |
---|---|---|---|
FRI | Hashes only(quantum safe!) | Large(10-200kB) | Medium(poly-logarithmic) |
Inner product arguments (IPAs) | Basic elliptic curves | Medium (1-3 kB) | Very high (linear) |
KZG commitments | Elliptic curves + pairings + trusted setup | Short (~500 bytes) | Low (constant) |
IPA + Halo-style aggregation | Basic elliptic curves | Medium (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。详细可看:
将多个IPA proof合并为一个IPA proof的合并技术是cheap的,而对合并后的IPA proof验证的时间 与 验证其中某一IPA proof所需的时间 相当。
这就使得,可将:
转为:
这种合并技术还可用于incremental verification:
incremental verification可用于验证完整性——如整个区块链的完整性。
Inner product argument基础知识可参看:
IPA不需要pairing运算,可使用任意椭圆曲线,哪怕是比特币和以太坊使用的secp256k1曲线,但是,为了可使用FFT加速,通常会选择具有FFT friendly order的曲线,详细可看:
根据Bulletproofs: Short Proofs for Confidential Transactions and More学习笔记第3节可知,Inner product argument针对的场景经历了如下衍化:
1)Bootle 2016方案中的基本信息表达为:
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的)
基本信息表达为:
进一步等价表达为: