区研大咖问回顾|如何快速搭建零知识证明的认知框架

嘉宾介绍

Even

安比实验室工程师|从零开始学习zk-snark系列翻译者,零知识证明项目 zkPod-node 和形式化验证项目 tokenlibs-with-proofs 核心开发者。

热身

安比(SECBIT)实验室:由中科大郭宇博士创建,核心团队来自于中科大、清华、耶鲁以及360、阿里、Intel等国内外顶尖高校与企业。专业领域覆盖信息安全、操作系统、程序语言理论、分布式计算、形式化验证、编译器、博弈论、密码学。目前专注于区块链安全技术,已经服务客户上百家,核心业务包括区块链代码安全审计、形式化建模与验证、区块链行为监控、区块链底层技术解决方案。

Q&A

1.零知识证明是什么?它的发展过程是怎样的,它和区块链技术又是怎样的关系?

零知识证明是现代密码学的几个重要组成部分之一。通俗的来讲,它指的是证明者能够在不向验证者提供任何有用的信息的情况下,通过「交互」使验证者相信某个论断是正确的。但其实零知识是一种广义的密码学协议属性,在几乎所有的密码学安全协议中都会涉及「零知识」这个概念。而这里的「证明」一词指的是一种交互式系统,也是涉及所有的密码学安全协议,甚至包括基本的加密,签名等基础模块。

零知识证明非常有趣,也非常反直觉,很多人在初步了解零知识证明的用处之后,都会感慨密码学的神奇。当你深入到零知识证明的原理层面后,你会更加惊奇于内部的精密构造,以及这个概念的伟大。零知识证明的底层理论基础是计算复杂性理论加上信息论,比如图灵机,P,NP问题,纸带,算法这些概念都被数学化,这是可以一路回溯到罗素、哥德尔、图灵等先驱的贡献,伴随着计算机互联网一路成长起来的理论技术。而我们通常所提到的零知识证明技术,狭义上是指一类构造零知识证明的通用技术,比如像zkSNARK,zkSTARK。

零知识证明这个概念最早诞生于 20 世纪 80 年代,由 S.Goldwasser、S.Micali 及 C.Rackoff 在一篇名为 「交互式证明系统的知识复杂性」的论文中提出。但是在随后的很长一段时间里,碍于一直没有较好的通用性方案和较高的运行成本,零知识证明一直停留在理论阶段而没有得到广泛的应用。

不过最近十年,零知识证明技术在理论上倒是得到了快速的发展。这段时间里有很多的传奇密码学家,可以说正是由于他们不懈的耕耘,才研究出了这么神奇的黑科技。比如其中一位,Jens Groth,他以前是 UCL大学的计算机系的教授,现在是 Difinity 的首席科学家,这个大神发表过很多的零知识证明论文。他在 2010 年发表的文章「Short Pairing-Based Non-interactive Zero-Knowledge Arguments」(简称 Groth10)为后来的零知识证明协议 Pinocchio 打下了坚实的基础。这篇论文也是目前最前沿的一些零知识证明系统,比如Marlin, Spartan, Sonics, Libra,Plonk 等等的重要基础。

而在2012年的时候,一篇里程碑式的论文出现了,简称 GGPR,这篇论文提出了 QAP 这个重要概念。这个大大提升了 Groth 10 算法的效率,它通过高效的多项式编码,使得证明尺寸被压缩到了常数级,而且特别特别小。到了2013年,Byan Parno,继续改进,提出了Pinocchio 协议,也就是Zcash 最早采用的零知识证明系统。Pinocchio 算是一个标志性的进展,让密码学家们看到了工程应用的希望。大家可以去看看 Pinocchio 论文,有一半的篇幅都在讲性能。

差不多2016年的时候,ZCash诞生,零知识证明与区块链技术一起走进了大众的视野。而随着这几年的发展,零知识证明已经成为了区块链不可或缺的一环,它可以很好的解决区块链在实际应用中面临的一些问题,比如保护用户的隐私数据,还比如区块链扩容,还有在区块链上实现公共校验等等,零知识证明真正在区块链领域引起广泛关注是从 2019 年才开始的,而它在区块链上的应用其实还有很多待挖掘的场景,相信很快大家就可以看到。

2.通过even上面的分享,大家应该都对零知识证明有了初步的理解,接下来本次AMA的重点来了!even将分5个模块,为大家梳理出零知识证明目前最主流算法—————zk-SNARK的认知框架。接下来会按照顺序打出5个模块的题目,由even老师为我们详细讲解。

2.1 zksnark 的概念是什么?

zkSNARK 全称 zero-knowledge succint non-interactive arguments of knowledge,中文翻译过来就是「简洁非交互的零知识证明」,这个到底是什么意思呢?zero-knowledge很明显就是指零知识。succint我们通常翻译成简洁的,它的意思就是说这类协议验证过程中传输的数据量较小而且验证方法简单。non-interactive的意思是非交互,零知识证明协议分为交互式和非交互式,简单来说,交互式的零知识证明需要验证双方完成一次交互,这类的证明有一个特点是不能复用,也就是说证明者每次都要生成一个新的证明给一个验证者做校验,这样做比较麻烦,但只能用一次也有好处,就是这个证明不可能被重复冒用。相反,非交互的零知识证明过程不需要交互,证明者只要生成一次证明就可以由多个验证者验证,相应的它有一个缺点就是证明一旦公开是有被拿来冒用的安全性风险的。

Arguments of knowledge其实严格来说它不能称为证明,它是区别于 Proof of knowledge的。这两者的区别是什么呢?Proof 是说即使未来出路算力超强量子计算机,黑客也没有办法伪造证明,而对于Argument,虽然以现在的计算机运算能力没有办法伪造证明,但如果出现超级计算机,还是有可能伪造的。这就是 zkSNARK 的概念。零知识证明的协议有很多,如 Pinocchio,Bulletproof,Groth16,zkStark,Marlin,Plonk,Sonic 等等。而我们平时所看到的介绍 zkSNARK 算法的文章,其实大部分说的都是 Pinocchio 协议。

2.2 zksnark算法的主流协议都有哪些?

前面我们已经说过 Pinocchio 协议,后面还出现了很多的协议,比如2019年Zcash 切换到了 Groth16 证明系统,这是一个在 Pinocchio 协议上的进一步极致优化,Groth16把证明尺寸压缩了将近一半,也就是只有100来字节,但是Groth16 也有一个明显问题就是,就是它需要对每一个计算过程进行 Trusted Setup,一旦代码有一点点修改,那么就需要重新来完成 Trusted Setup,这个其实非常麻烦也比较容易受到质疑。不过后来就出现许多新的零知识证明系统试图去解决这个问题。

这些协议大致可以分为两类,一大类是可更新的全局 Trusted-setup,另一大类是「Transparent- Setup」。第一类Trusted-setup的协议有很多,比如 Sonic, PLONK,Marlin。而我们经常看到的zkSTARK和Bulletproof就是属于第二类Transparent-Setup,还有一些大家可能没怎么听说过,比如Ligero,Virgo,Hyrax。

2019年整体呈现了一种大爆发的情况,比如 Spartan、SuperSonic、zk-SHARK,还有最近 ZCash 团队公布了一个可递归证明的零知识证明系统,叫做 Halo。

2.3 通过一个例子简单介绍Pinocchio协议的原理和大致框架

Pinocchio协议大致可以分为五个步骤。前三步是Trusted-Setup过程。第四步是生成证明,第五步是验证证明。

第一步:首先你要把需要进行证明的计算过程产生相应的算术电路。所谓的算术电路是指一种计算模型,简单的说它就是把要证明的数学公式转换成统一格式的算式,有很多的乘法和加法组成,这就构成了所谓的乘法门和加法门,然后这些门之间可以再用线连接在一起,用户就可以把数值输入到电路的输入线上,然后经过门的计算,我们会在电路的输出线上得到经过计算的数值。电路的编写目前来说还是比较难掌握,需要开发者有不少的经验。

第二步:把算术电路转换成一种叫做 R1CS 的约束系统。R1CS 是指rank-1 constraint system,也就是一阶约束系统。这里其实就做了两件事,第一件事是把所有的加法和常数乘法折叠在一起,最后只剩下所有乘法门。第二步,把所有乘法运算的两个输入和输出的约束关系合并成了三个巨大的矩阵A,B与C,这三个矩阵可以相乘的,A * B = C。

第三步:根据三个矩阵产生QAP,这一步比较绕,理解起来也比较难。简单的说就算把所有的取值和约束条件整合起来到一个多项式关系中,再利用多项式的性质,选取一个点去校验就能证明数据的正确性了,并且这个点是放到了椭圆曲线上进行同态地校验的,并不会暴露出去。这一步完成后会生成一堆的参数,我们可以称它为「证明密钥」和「验证密钥」用来完成后面的证明过程。

第四步:证明者生成证明。证明者拿到(证明密钥),然后把它与证明者要证明的秘密数据结合起来,拼回多项式在这个挑战点上的取值。证明者将算出来的值发送给验证者,发送的内容也就是几个值而已,所以证明其实很小很小。

第五步:验证者验证证明。验证者拿到「验证密钥」和证明者算出来的值,利用椭圆曲线配对操作来验证证明者的计算是否正确。Pinocchio 协议的过程其实特别绕,细节也很多,上面只是讲了一个大致的框架,感兴趣的小伙伴推荐大家多去看一看专门的文章。

2.4 椭圆曲线在零知识证明中占据什么地位?

前面提到的同态加密就是在椭圆曲线点上做的运算,而椭圆曲线加密配对更是椭圆曲线上的一个很重要的性质。绝大部分主流的零知识协议都是基于椭圆曲线做运算的,可以说零知识证明离不开椭圆曲线。

2.5 Libsnark的简介与调用

零知识证明方面的第三方库其实并不是很多,libsnark算术最为大家熟知一个了,它是一个C++的库。libsnark 提供了多个通用证明系统的实现,其中就包括大家比较常见的 Pinocchio 和 Groth16。libsnark的框架看起来有点复杂,但是利用 libsnark 库开发 zk-SNARKs 应用难度倒还好。时间关系这里就不详细介绍了

3. 区块链领域有不少使用零知识证明的项目,比如我们都比较熟悉的zcash等,可以给我们介绍一些值得。去了解的优秀项目吗?它们现在的情况又是怎么样的?

目前零知识证明的项目不少,大部分都集中在保护隐私和提高扩展性上。零知识证明最早应用在公链上,用于保护用户的交易信息隐私,比如最早的zcash,以及Monero。相信大家都听说过一个协议 MimbleWimble,这是一个为了提高比特币的可扩展性和隐私性而创建的协议,MimbleWimble 协议里面也用到了零知识证明,它是用来构造一种叫做 range proof的证明。Grin 和 Beam 就是 MimbleWimble 的两个独立实现。另外还有去年的明星项目 Coda 以简洁为特点,它是利用 zk-SNARK 将区块进行压缩,成为单个证明。

以上这些是公链基础项目,另一方面,零知识证明还大量的应用在了现有公链基础上的二层扩容和DAPP上。就以以太坊为例,去年最火热的一项技术之一就是:ZKRollup。它是以太坊二层扩容的解决方案之一,简单的说,它就是由主链的智能合约来保管所有的资产,在链下或者侧链完成多笔交易后聚集起来,生成一个零知识证明提交到智能合约中,完成验证和转账。基于 zkRollup 的项目很多,比如 Loopring DEX Protocol 3.0,dfusion, ZK Sync协议等等。除了zkRollup,基于零知识证明的DAPP 还有一些,比如我们安比实验室的零知识项目 zkPoD ,这是一个基于零知识证明和区块链的去中介的公平交易协议。零知识证明的项目还有很多,这里就不一一介绍了,除了公链基础项目以外,其实区块链领域绝大部分的零知识证明项目都是在最近一两年才推出的。

4. 安比实验室一直在做着零知识证明的研究和布道,那么可以比较体系化的给小伙伴们分享下学习资源吗?此外推荐一些相关的优秀文献吧,帮助我们对这门学科有更好的认知~

我们之前整理的一份零知识证明学习资源汇总的文章。这篇文章收集了大量关于零知识证明的中英文学习资料,后续我们还会对这篇汇总文章做更新,欢迎大家持续关注。对于zk-SNARK的学习,之前看到了一篇比较好文章,就把它翻译成中文了。

当然,除了这个系列文章以外,学习零知识证明比较经典的资源,zcash 官方的零知识证明系列,V神的文章都是很好的学习资源。不过要打好零知识证明的基础,其实建议大家找几本密码学的书来学习一下。比如《图解密码学》这本书很好,非常适合入门学习。更深一点的书籍的话建议大家去看斯坦福 Dan Boneh的《A Graduate Course in Applied Cryptography》和 Jonathan Katz 教授的《Introduction to Modern Cryptography》。

5. 零知识证明涉及的知识面的确很广泛,那么可以为大家推荐一条学习的路线吗?此外,在学习过程中,哪些坑是需要避开的~~

首先呢,建议大家先去了解一些基本概念。零知识证明涉及的知识其实非常多,需要学习的内容也很多,建议大家先从一个协议开始,比如就从 Pinocchio 协议开始,这个资料也比较多。当然椭圆曲线,pairing,同态加密这些基础知识都是必不可少的,建议大家去学一学。

第二阶段就是建议大家开始上手写一些代码,建议可以试着写写简单的代码,做过开发的小伙伴应该都有过这样的感觉,面对一个很难理解的概念原理,用代码实现一下就会容易理解狠毒,所以多写写代码真的非常重要。

第三阶段就是深入理解基础原理,功底深厚的小伙伴可以直接去看论文,密码学基础相对较弱的小伙伴可以找几本密码学书来看一看,系统的学习一下密码学的知识。不过非常花时间,一开始可能完全看不懂,需要慢慢啃,哈哈!

第四阶段就是上手设计零知识相关的安全协议,这个就难度比较高了,建议咨询相关密码学专业人士。

零知识证明的学习之路并不简单,最后给大家一点点小建议~

1~多写代码!!

没有什么不是先动手写几行代码解决不了的,哈哈哈!很多复杂的原理其实多试试写点代码,多实现一些小例子就很容易get到点了,所以强烈建议大家多写写代码。

2~分享和讨论很重要,学习零知识证明过程很枯燥,涉及的内容也比较多,一个人学很难坚持,也容易走入误区

3~打好基础,零知识证明作为现代密码学重要的组成部分,自然离不开密码学基础知识,零知识证明的背后牵扯的基础知识非常非常多,要想深入学好零知识证明,打好密码学基本功是必不可少的

自由提问

F1:请问不使用 pairings 的零知识证明有哪些?它们之间相比有什么优劣呢?

像zkStark,BulletProof 都没有用到 pairings,他们是另外一套证明思路,并不单单只是去掉了pairings,使用pairing的好处能让proof size变成常数大小,这个是非pairing方案做不到的。目前非pairing的方案其实发展得挺快的。使用 pairing 的方案大都基于groth10技术,需要用到一个 non-falsifiable 的安全性假设,也就是KEA 假设,使用 pairing 的方案的一个特征就是需要 trusted-setup。非pairing的一些则是用了 random oracle + fiat-shamir trans,有些密码学家喜欢使用pairing,有些喜欢非pairing的方案。萝卜白菜,各有所爱,哈哈哈~

F2:如何确认一个用户已经对他的数据进行加密了呢?

这个可能就要具体情况具体分析了,比如明文的持有者是谁,加密算法是什么,应用场景是什么样的,解决办法都不一样。

采访策划:11,Shawn,Even

执行:11,Shawn

主持:11

Leave a Reply

Your email address will not be published.

当前无网络链接