Welcome to the

World!



🔍 How to contribute?

🚩 Our Vision & Roadmap







📖 What is z2o-k7e?

z2o-k7e is a community-driven project dedicated to collaborative ZKP (Zero-Knowledge Proof) learning and zkp-tutorial writing . In 4 terms zkp co-learning journey since February 2023, we’ve explored & co-learned resources like https://www.zkiap.com, https://zk-learning.org, plonkathon , and 0xPARC halo2 (ongoing), engaging with over 300+ enthusiastic participants!

In this journey, our vibrant community learns collectively, assists one another with q-a, and write zkp-related content collaboratively.

At z2o-k7e, we award bounties to motivate learners for their tech insights, encourage active community maintenance, and promote the organization of ZKP-centric knowledge. Collectively, our mission is to enhance the quality of ZKP Public Goods.

🚀 In 2023, we completed 4 rounds of collaborative learning on different topics of zkp. Now, we plan to accomplish another 4 sessions of zkp collaborative learning in 2024, including advanced topics like plonky3/Nova/zkVM/STARK ….



🚩 Problem Statement:

The world of zkp is riddled with challenges - so many noises, steep entry barriers, convoluted learning processes, an absence of dedicated learning communities, and a deluge of often nebulous information. Through z2o-k7e & the zkp colearning community, we’re committed to confronting and tackling these issues head-on.



🌟 Core Contributors


愿景 Vision

内容层面:随着 zkp 社群共学的进行,建设一系列质量极高的中英文 zkp tutorials

社区层面:

  1. 建设国内社群氛围最好,贡献参与度最高,内容质量极高的 web3 技术社群
  2. 作为中文 zkp 社区的窗口,不断培养和支持社群内 builder 的优质项目,引导大家贡献到国际化社区(如 PSE 等),同时将第一手优质信息共享至社群,引导讨论和积极贡献。

Roadmap

z2o-k7e 内容 Roadmap

z2o-k7e 产品



贡献流程

  1. Github 上 fork 本 Repo
  2. 可以在 ./src/zk-everythingmkdir 一个以自己名字命名的文件夹
  3. src/SUMMARY.md 是前端网站显示的文件组织目录,可以修改该文件,找到一个合适的放置目录,将文章的本地 .md 文件位置链接过去
  4. 正常的 PR 流程
  5. 经老师们审核后领取 Bounty!

文章格式

内容模板

  1. 文章 metadata ,如 「贡献者作者信息 (required)」, 「标签、联系方式 (optional) 」
> 作者: 如 @大壮 https://github.com/dazhuang      
> 标签: 如 halo2, Nova, STARK, Folding schema .... # mdbook 暂不支持 tag 功能
> 时间: 2023-09-10

比如:

作者:大壮

Author: 大壮

  1. 文章开始之前,可以添加 [TOC] 来让 mdbook 自动生成该文章的 Table of contents(目录)
[TOC]
  1. 可添加 admonition block,语法见这里

This will take a while, go and grab a drink of water.

  1. 文章正文(Markdown 格式的正文内容,无需担心 github 糟糕的渲染)

  2. 文章末尾可以列出 「致谢」 & 「参考文献 References」

# References
 - [trapdoor-tech halo2 book](https://trapdoor-tech.github.io/halo2-book-chinese/user/simple-example.html)
 - [icemelon/HaiCheng Shen](https://github.com/icemelon/halo2-examples/blob/master/src/fibonacci/example3.rs)
 - [0xPARC halo2](https://learn.0xparc.org/)

如何添加图片?

  • 推荐直接在 .md 文章同级目录 mkdir ./imgs 目录,mdbook 中直接引用该 imgs 目录相对路径
  • 如果您使用的是 OSS 云存储,则无需考虑图片存储,只需一个 .md 文件即可~

配套代码(optional)

如果文章有对应的实战代码那就再好不过啦!

可以直接 PR 到另一个 Repo,新建一个目录即可。

├── Nova
├── README.md
├── halo2-doc
├── halo2-learn
├── [Your code repo here !!]  # mkdir your code repo here !!
└── zk-everything

这边还没想好怎么放,可能后面位置有改动,不过…反正先放就好了 !

关于 md 渲染

众所周知,Github 网站的 Latex 等渲染功能非常弱鸡,往往需要一些奇技淫巧才能让公式等正常渲染出来。而在本 MDBOOK 中,您完全不需要关注这种伤害身心的问题,不需要给 github markdown 做专门的适配和魔改。在 Obsidian(或者如 Typora 等主流 Markdown 编辑器)里的 .md 文件显示是什么样的,本网站中都可完美无痛渲染!

本地 Dev 预览方法:

$ [安装 Rust]
$ cargo install mdbook mkbook-latex  mdbook-toc
$ mkbook serve --open       # 本地预览

Tips :

  • src/SUMMARY.md 是会在前端组织显示的所有文件目录及其链接
  • 公式测试:可以在 katex.org 测试,大家在 Obisidian notes 里怎么写公式,前端就会咋显示,

(contribution by PR process)

💡 @Demian: 作为 zkp 新人,走了很多弯路,也整理下自己的学习路径和一些参考资料供大家入门。 希望本教程可以帮助减少一些盲目的打击和莫名的痛苦,节省一点点时间

1. 建立对 zkp 的直观理解

① 在纵身潜入 ZKP 的海洋之前,可以先建立对它最直观的理解

  • 安比实验室(郭宇老师)所写的 zkp-intro 是公认目前全网最简洁易懂的 zkp 入门系列(而且还是中文的!!)
  • 前 3 篇需要看懂,不了解的概念就 Google + chatgpt + 社群询问 …
  • Chap 4-5 主要是非交互的 Schnorr 和 CRS、哈密尔顿环路等,看不懂没关系,可以先放一放

2. 最小必要背景知识

在建立了对 ZKP 最直观的了解后,如果你还是打算要学下去的话,那么就开始准备一些最小必要的基础知识吧!

2.1 椭圆曲线 ECC

需要掌握椭圆曲线加密(ECC)原理( 大概用时 30 min)

2.2 基础的群论、数论

初等数论 Number Theory

2.3 密码学基础

需要掌握:群环域概念、循环群、拉格朗日插值

2.4 ZK-SNARK 初识 & 原理:

需要掌握:直观理解循环群在 zk-snark 中是咋用的就可以,具体的算法细节可能要持续往后学,和 PLONK 的算法不断交叉回看才能懂。

推荐 sec-bit ZK-SNARK 的系列文章,也可在微信公众平台搜索,对于初学者先看 Part 1 / 2 就够了。

3. 理论交叉学习,我反复入门啊!

有了以上基础的打底,可以尝试一套体系完整的系列课程:

ZKIAP

ZKIAP 的课程是比较注重理论和实践结合的,第二课就有涉及到 Circom 写电路

zk-learning

理论详实,但是缺少代码实践,session 5 的 PLONK 是 top-down 讲解,搭配郭老师的 理解 PLONK 系列会更佳

crypto notes

土耳其小哥整理的,非常赞的 notes

ProofsArgsAndZK

author: justin thaler

https://zkhack.dev/whiteboard

https://www.rareskills.io/zk-bootcamp


其他优秀的 Courses (随便看看):

1. PSE appliedzkp.org/projects 
2. Rust
3. complaints about learning rust
4. Dan Boneh
5. "The Different types of ZK-EVM" article 
6. who was the first ZK-EVM.
7. ZK Summit – Zero Knowledge Summit
8. Zac Williamson inventing PLONK, running @aztecnetwork
9. @zeroknowledgefm podcast
10. Fiat-Shamir Transformation 
11. The Moon Math Manual https://github.com/LeastAuthority/moonmath-manual
12. ZK-Rollups that provide privacy by default are sometimes called ZK-ZK-Rollups
13. Circom
14. The "Proofs, Arguments, and Zero-Knowledge" book by Justin Thaler https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
15. Brecht – @taikoxyz CTO and @PrivacyScaling contributor
16. ZK HACK
17. Definition wars
18. how one should write zkEVM or ZK-EVM or Zk-EVM or zk-EVM
19. Lagrange interpolation

4. PLONK 协议の奥义

PLONK 无疑是目前最值得学习,需要彻底掌握的协议

《理解 Plonk》

出品:Secbit @郭宇 老师 , https://secbit.io/

是大家公认的全网(包括外网)最好的 PLONK Tutorial。

学习 PLONK,这一套就够了!(论文可以随便看一下)

PS: 如果文档看晕了,那么推荐郭老师的配套白板视频:


PLONK 代码实践

5. 要不…来点代码?

恭喜你来到了 Zero-knowledge 的荒原!下面就可以自己根据兴趣和方向选择一些代码进行研究和实践了

halo2

使用了 halo2 的 Applications:

  • ZK Email https://github.com/zkemail halo2
  • ZK Wordle: https://zordle.xyz/ halo2
  • Hammster: https://github.com/ytham/hammster halo2
  • zk-draw : Verifiable random draw with zero-knowledge of the random seed https://github.com/jae-cuz/zk-draw halo2
  • ZK Microphone: https://github.com/Miyamura80/ZKMicrophone
  • Building a Zero Knowledge web app with Halo 2 and Wasm (part 1)
  • zk-img: Fighting Deepfakes with Zero-Knowledge Proofs https://medium.com/@danieldkang/zk-img-fighting-deepfakes-with-zero-knowledge-proofs-9b76c23e3789 尚未开源

大部分由 @Kurt Pan 博士整理

Circom

使用了 Circom 的 Applications:

  • zkSudoku: https://zk-sudoku.vercel.app/ Circom
  • Tornado-Cash
  • Semaphore

学习路径:【EDITING…】

PSE demos

PSE Projects List : https://www.appliedzkp.org/projects

Semaphore

对于 Circom + ZKP 的代码实践例子比较多,首推 PSE 的 Semaphore,是个包括 zuzalu pass、Worldcoin 都有使用的 zkp 协议

Others:

【out of date】,请移步: zk Materials

Tools

探索零知识证明系列

探索零知识证明系列作者:郭宇@Secbit: Founder of Secbit, https://github.com/sec-bit , https://secbit.io/

原链接:https://github.com/sec-bit/learning-zkp/

初识「零知识」与「证明」

探索零知识证明系列(一)

引言:

我认为区块链很难称为一个“技术”。它更像是一个领域,包罗万象。或者形而上地说,区块链更像一个有机体,融合了各种不同的理论技术。

零知识证明是构建信任的重要技术,也是区块链这个有机体中不可缺少的一环。

零知识证明是打通链上数据与链下计算的关键技术,也是实现链上数据隐私保护的重要途径

要解释「零知识证明」,我们需要先解释「证明」,然后解释什么是「知识」,最后再解释什么是「零知识」。

提醒:文章内容难免有不准确或不严谨的描述,还请各位专业人士拨冗指正。

本文将在 Github 进行更新与修正。

“证明” 的前世今生

什么是证明?很多人可能和我一样,看到这两个字,会不禁想起中学考卷中各种三角相似的几何图形,当老师在神奇地画出一条辅助线后,证明过程突然显而易见,然后会懊悔自己为何没想到。

古希腊:「证明」 == 「洞见」

数学证明最早源于古希腊。他们发明(发现)了公理与逻辑,他们用证明来说服对方,而不是靠权威。这是彻头彻尾的「去中心化」。自古希腊以降,这种方法论影响了整个人类文明的进程。

勾股定理的证明

上图是「勾股定理」的巧妙证明。历史上曾出现过许许多多精巧的证明,神奇的思路,天才的灵感。一旦一个命题被证明,上帝都无能为力。嗯,对了,还有那个「上帝不是万能的」证明:上帝不能造出一块他举不起来的石头。

一个数学证明往往暗藏无比深刻的「洞见」,相信很多人都看过「费马大定理」的故事[1],这个定理证明横跨四百年,从费马写下「这里空间太小,我写不下」,到怀尔斯最终登顶,耗费了许多代人的聪明才智。最近如「彭加莱猜想」,稍微带点年代感的如「哥德巴赫猜想」,还有我非常敬佩的华裔科学家张益唐十年磨一剑,在仔细研究了「Goldston-Pintz-Yıldırım」和 「Bombieri-Friedlander-Iwaniec.」的证明「洞见」之后,证明了「质数间的有界间隔」[2]。

自十七世纪,莱布尼茨起,人们就梦想找到一种机械的手段,可以来自动完成证明,而不再依赖天才的灵光一现。

二十世纪初:「证明」 == 「符号推理」

时间到了十九世纪末,康托、布尔、弗雷格、希尔伯特、罗素、布劳威、哥德尔等人定义了形式化逻辑的符号系统。而「证明」则是在利用形式化逻辑的符号语言编写的推理过程。逻辑本身靠谱么?逻辑本身「自恰」吗?逻辑推理本身对不对,能够证明吗?这让 数学家/逻辑学家/计算机科学家 发明(发现) 了符号系统,语法 vs. 语义,可靠 vs. 完备,递归 vs. 无穷。(这部分精彩故事请参看『逻辑的引擎』一书[3])。

1910年,罗素发表了洪(zhuan)荒(tou)巨著『数学原理』。在书中,罗素与怀特海试图将数学完整地「形式化」下来。如果能达到这样的目标,所有的数学成果都将以证明的方式建立在坚实的基础上。下图就是『数学原理(卷二)』中的一页:

其中110.643这是一个命题:「1+1=2」,然后接下来就是这个定理的证明。大家可能奇怪,难道 1+1 还需要证明吗?是的,在数学原理一书中,数字 0,1,2,…… 都有严格定义,「加法」、「乘法」、「等于」都要严格定义,然后每一步的推理都需要指出依据。证明意味着什么?证明是可能繁琐无比的、但是每一步推理都严格无误。书中大量的证明都机械式的,按照公理和推理规则进行一种证明的构造,寻找证明就好像可以交给一个人,然后他无脑在公理与推理规则的集合中进行机械查找。

似乎人们距离「定理的自动证明」并不遥远了。

不幸的是,哥德尔在 1931 年证明了「哥德尔不完备性定理」[4],图灵在 1936 年证明了图灵机停机问题的不可判定性[5]。这些成果彻底终结了这个几百年的幻想。无论公理系统如何精巧设计,都无法抓住所有的真理。

证明不仅仅是一个严格推理,而且凝结了似乎很难机械化的创造性思维。证明中蕴含了大量的「知识」,每一次的突破,都将我们的认知提升到一个新的高度。不管是「洞见」,还是推理过程中所构造的「算法」,一个定理的证明的内涵往往远超出定理本身的结论。

六十年代:「证明」 == 「程序」

又过了半个世纪,到了六十年代,逻辑学家 Haskell Curry 和 William Howard 相继发现了在「逻辑系统」和「计算系统— Lambda 演算」中出现了很多「神奇的对应」,这就是后来被命名的「Curry-Howard Correspondence」。这个发现使得大家恍然大悟,「编写程序」和「编写证明」实际在概念上是完全统一的。而在这之后的 50 年,相关理论与技术发展使得证明不再停留在草稿纸上,而是可以用程序来表达。这个同构映射非常有趣:程序的类型对应于证明的定理;循环对应于归纳;……(这里推荐一本书:『软件基础』(Software Foundations 中译本)[6])。在直觉主义框架中,证明就意味着构造算法,构造算法实际上就是在写代码。(反过来也成立,嗯,码农码的不是代码,是数学证明,:P)

目前在计算机科学领域,许多理论的证明已经从纸上的草图变成了代码的形式,比较流行的「证明编程语言」有 Coq,Isabelle,Agda 等等。采用编程的方式来构造证明,证明的正确性检查可以机械地由程序完成,并且许多啰嗦重复性的劳动可以由程序来辅助完成。数学理论证明的大厦正在像计算机软件一样,逐步地构建过程中。1996 年 12 月 W. McCune 利用自动定理证明工具 EQP 证明了一个 长达 63 年历史的数学猜想「Ronbins 猜想」,『纽约时报』随后发表了一篇题为「Computer Math Proof Shows Reasoning Power」的文章[7],再一次探讨机器能否代替人类创造性思维的可能性。

利用机器的辅助确实能够有效帮助数学家的思维达到更多的未知空间,但是「寻找证明」仍然是最有挑战性的工作。「验证证明」,则必须是一个简单、机械、并且有限的工作。这是种天然的「不对称性」。

八十年代:「证明」 == 「交互」

时间拨到1985年,乔布斯刚刚离开苹果,而 S. Goldwasser 博士毕业后来到了 MIT,与 S. Micali,Rackoff 合写了一篇能载入计算机科学史册的经典:『交互式证明系统中的知识复杂性』[8]。

GMR89

他们对「证明」一词进行了重新的诠释,并提出了交互式证明系统的概念:通过构造两个图灵机进行「交互」而不是「推理」,来证明一个命题在概率上是否成立。「证明」这个概念再一次被拓展。

交互证明的表现形式是两个(或者多个图灵机)的「对话脚本」,或者称为 Transcript。而这个对话过程,其中有一个显式的「证明者」角色,还有一个显式的「验证者」。其中证明者向验证者证明一个命题成立,同时还「不泄露其他任何知识」。这种就被称为「零知识证明」。

再强调一遍,证明凝结了「知识」,但是证明过程确可以不泄露「知识」,同时这个证明验证过程仍然保持了简单、机械,并且有限性。这听上去是不是有点「反直觉」?

交互式证明

Alice: 我想向你证明我有一个方程的解,w^3 - (w+1)^2 + 7 = 0 (方程的解:w=3

Bob: 好啊,我听着呢

Alice: 但是我不会告诉你 x 具体是多少,除非你愿意掏钱,我才告诉你。

Bob: 可以啊,但是你要先证明你有方程的解,我再给钱你。

Alice: @#%^& (黑科技)

Bob: ?????? (黑科技)

Alice: &*#@! (黑科技)

Bob: ??????(黑科技)

…… (继续黑科技)

Alice: 好了,完了

Bob: 好吧,你确实有方程的解,不过是不是我掏了钱,你就会把答案告诉我?

Alice: 别废话,掏钱!

上面例子就是一个「交互式证明」。假设Alice知道方程的解, f(w) = 0,那么 Alice 如何让 Bob 确信她知道 w 呢?Alice 在 「黑科技阶段」 告诉了 Bob 一大堆的信息。好了,关键问题是,Bob 能不能从 Alice 所说的一大堆信息中猜出w 到底是几,或者能分析出关于 w 的蛛丝马迹呢?如果 Bob 有这个能力,Bob也许就没必要掏钱了,因为他已经获得了这个值钱的信息。

请注意,如果 Alice 与 Bob 的对话是 「零知识」 的,那么 Bob 除了知道 wf(w)=0 的解之外,不能获取其它任何关于 w 的信息。 这一点非常重要,这是保护 Alice 的利益。

现在回顾一下「零知识证明」这个词,英文叫 「Zero-Knowledge Proof」 。这个词包含三个关键部分:

  • 知识
  • 证明

各位可能已经有点感觉了,我们来尝试着解读一下:

  • 零: Alice 泄露了关于 w 的「零」知识,也就是没有泄露知识。
  • 知识:这里就是指的就是 w
  • 证明:就是Alice与Bob对话中的「黑科技部分」。

好了,证明也就是黑科技部分还没讲。看官们不要急,且听我慢慢道来。

零知识证明有什么用处?

一提零知识证明技术,很多人就想到了匿名 Coin,比如 Monero, 比如 ZCash。确实,这几个 Coin 很好地普及了零知识证明,我本人也是通过 ZCash 才第一次听说了零知识证明这个词。但是在更深入地了解这个技术之后,深深感觉这个技术的威力远不止这一点。

零知识证明技术可以解决数据的信任问题,计算的信任问题!

张三说他有100块钱,李四说他北大毕业,王五说要和八菲特共进午餐。空口无凭,Show me the proof

show-me-the-proof

那么「零知识证明」能解决数据的信任如何理解呢?在上一篇文章『zkPoD: 区块链,零知识证明与形式化验证,实现无中介、零信任的公平交易』[9]里面,我提到了一个概念「模拟」:

零知识证明技术可以「模拟」出一个第三方,来保证某一个论断是可信的

换句话说,当我们收到一个加了密的数据, 然后还有一个零知识证明。这个零知识证明是说 「关于数据的 X 断言成立」,那么这等价于有一个天使在我们耳边悄声说,「关于数据的X 断言成立」!

trusted-party

对于这个 X 断言,可以非常灵活,它可以是一个 NP复杂度的算法。大白话讲只要我们能写一段程序(一个多项式时间的算法)来判断一个数据是否满足 X 断言,那么这个断言就可以用零知识证明的方式来表达。通俗点讲,只要数据判定是客观的,那么就零知识证明就适用。

零知识证明的一些用处:

  • 数据的隐私保护:在一个数据表格中,多多少少都有一些信息不想被暴露,比如当年我的成绩单,我只想向人证明,我的成绩及格了,但是我不想让别人知道我到底考了61分还是62分,这会很尴尬。我没有心脏病,但是保险公司需要了解这一点,但是我不想让保险公司知道我的隐私信息。那我可以证明给保险公司看,我没有心脏病,但是病历的全部并不需要暴露。我是一家企业,我想向银行贷款,我只想向银行证明我具备健康的业务与还款能力,但是我不想让银行知道我们的一些商业秘密。
  • 计算压缩与区块链扩容:在众多的区块链扩容技术中,Vitalik 采用 zkSNARK 技术能够给现有的以太坊框架带来几十倍的性能提升。因为有了计算的证明,同样一个计算就没必要重复多次了,在传统的区块链架构中,同样的计算被重复多次,比如签名的校验,交易合法性校验,智能合约的执行等等。这些计算过程都可以被零知识证明技术进行压缩。
  • 端到端的通讯加密:用户之间可以互相发消息,但是不用担心服务器拿到所有的消息记录,同时消息也可以按照服务器的要求,出示相应的零知识证明,比如消息的来源、与发送的目的地。
  • 身份认证:用户可以向网站证明,他拥有私钥,或者知道某个只要用户自己才知道的秘密答案,而网站并不需要知道,但是网站可以通过验证这个零知识证明, 从而确认用户的身份
  • 去中心化存储:服务器可以向用户证明他们的数据被妥善保存,并且不泄露数据的任何内容。
  • 信用记录:信用记录是另一个可以充分发挥零知识证明优势的领域,用户可以有选择性的向另一方出示自己的信用记录,一方面可以有选择的出示满足对方要求的记录分数,同时证明信用记录的真实性。
  • 构造完全公平的线上数字化商品的交易协议[9]。
  • 更多的例子,可以是任何形式的数据共享,数据处理与数据传输。

举例:地图三染色问题

下面讲一个经典的问题,地图的三染色问题。如何用三种颜色染色一个地图,保证任意两个相邻的地区都是不同的颜色。我们把这个「地图三染色问题」转变成一个「连通图的顶点三染色问题」。假设每个地区都有一个首府(节点),然后把相邻的节点连接起来,这样地图染色问题可以变成一个连通图的顶点染色问题。

下面我们设计一个交互协议:

  • 「证明者」Alice
  • 「验证者」 Bob

Alice 手里有一个地图三染色的答案,请见下图。这个图总共有 6 个顶点,9 条边。

3c-0

现在 Alice 想证明给 Bob 她有答案,但是又不想让 Bob 知道这个答案。Alice 要怎么做呢?

Alice 先要对染过色的图进行一些「变换」,把颜色做一次大挪移,例如把所有的绿色变成橙色,把所有的蓝色变成绿色,把所有的橙色变成蓝色。然后 Alice 得到了一个新的染色答案,这时候她把新的图的每一个顶点都用纸片盖上,然后出示给 Bob 看。

3c-1

看下图,这时候 Bob 要出手了(请见下图),他要随机挑选一条「边」,注意是随机,不让 Alice 提前预测到的随机数。

3c-2

假设 Bob 挑选的是最下面的一条边,然后告诉 Alice。

3c-3

这时候 Alice 揭开这条边两端的纸片,让 Bob 检查,Bob 发现这两个顶点的颜色是不同的,那么 Bob 认为这次检验同构。这时候,Bob 只看到了图的局部,能被说服剩下的图顶点的染色都没问题吗?你肯定觉得这远远不够,也许恰好 Alice 蒙对了呢?其它没暴露的顶点可能是胡乱染色的。

没关系,Bob 可以要求 Alice 再来一遍,看下图

3c-4

Alice 再次把颜色做一次变换,把蓝色改成紫色,改绿色改成棕色,把橙色改成灰色,然后把所有的顶点盖上纸片。然后 Bob 再挑选一条边,比如像上图一样,选择的是一条竖着的边,然后让 Alice 揭开纸片看看,如果这时候 Bob 再次发现这条边两端的顶点颜色不同,那么 Bob 这时候已经有点动摇了,可能 Alice 真的有这个染色答案。可是,两次仍然不够,Bob 还想再多来几遍。

那么经过反复多次重复这三个步骤,可以让 Alice 作弊并能成功骗过 Bob 的概率会以指数级的方式减小。假设经过 n 轮之后,Alice 作弊的概率为

这里 |E| 是图中所有边的个数, 如果 n 足够大,这个概率 Pr 会变得非常非常小,变得「微不足道」。

可是,Bob 每次看到的局部染色情况都是 Alice 变换过后的结果,无论 Bob 看多少次,都不能拼出一个完整的三染色答案出来。实际上,Bob 在这个过程中,虽然获得了很多「信息」,但是却没有获得真正的「知识」。

信息 vs. 知识

  • 信息 「Information」
  • 知识 「Knowledge」

在地图三染色问题的交互证明中,当重复交互很多次之后,Bob 得到了大量的信息,但是这好比 Alice 发给 Bob 一堆随机数一样,Bob 并没有「知道」更多的东西。打个比方,如果 Alice 告诉 Bob 「1+1=2」,Bob 得到了这个信息,可是 Bob 并没有额外获取更多的「知识」,因为这个事实人人皆知。

假如 Alice 告诉 Bob 2^2^41-1这个数是一个质数,很显然这个是「知识」,因为要算出来这个数是不是一个质数,这需要耗费大量的算力。

假如 Alice 告诉 Bob,总共有两个顶点用了绿颜色,那么 Bob 就获得了宝贵的「知识」,因为基于他刚刚获取的这个信息,Bob 可以用更短的时间用一台图灵机去求解三染色问题。假如 Alice 又透露给 Bob,最左边的顶点颜色是用橙色,那么很显然,这个「信息」对于 Bob 求解问题并没有实质上的帮助。

我们可以尝试定义一下,如果 Bob 在交互过程中获得的「信息」,可以帮助提升 Bob 直接破解 Alice 秘密的能力,那么我们说 Bob 「获得了知识」。由此可见,知识这个词的定义与 Bob 的计算能力相关,如果信息并不能增加 Bob 的计算能力,那么信息不能被称为「知识」。比如在 Alice 与 Bob 交互过程中,Alice 每次都掷一个硬币,然后告诉 Bob 结果,从信息角度看,Bob 得到的信息只是一个「事件」,然而 Bob 并没有得到任何「知识」,因为 Bob 完全可以自己来掷硬币。

下面引用『Foundations of Cryptography—— Basic Tools』一书[10]中的总结

  1. 「知识」是与「计算难度」相关,而「信息」则不是

  2. 「知识」是与公共所知的东西有关,而「信息」主要与部分公开的东西有关

注:曾有人问我,这里的信息与知识的定义是否与 Kolmogorov 复杂性有关。根据算法信息论,一段字符串的信息量可以用产生字符串的最小程序的长度来测量。这个问题我不是很懂,希望路过的专业人士留言。

可验证计算与电路可满足性问题

看了上面的地图三染色问题,大家是不是没有感觉,好像这只是一个学术问题,如何跟现实问题关联起来?地图三染色问题是一个 NP-Complete 问题,这是「计算理论」中的一个名词。另外有一个叫做「电路可满足问题」也是同样是 NP-Complete 问题。NP-Complete 是一类问题,他的求解过程是多项式时间内难以完成的,即「求解困难」,但是验证解的过程是多项式时间可以完成的,即「验证简单」。

那什么是电路呢?下面是三个不同的「算术电路」:

circuits

可以看到一个电路由很多个门组成,其中有加法门,还有乘法门。每一个门有几个输入引脚,有几个输出引脚。每一个门做一次加法运算,或乘法运算。别看这么简单,我们平时跑的(没有死循环)代码,都可以用算术电路来表示。

这意味着什么呢?我们下面结合「零知识证明」与「电路可满足性问题」来试着解决数据的隐私保护问题。

下面请思考一个场景:Bob 交给 Alice 一段代码 P,和一个输入 x,让 Alice 来运行一遍,然后把运行结果告诉 Bob。可能这个计算需要消耗资源,而 Bob 把计算过程外包给了 Alice。然后 Alice 运行了一遍,得到了结果 y。然后把 y 告诉 Bob。下面问题来了:

如何让 Bob 在不运行代码的前提下,相信代码 P 运行的结果一定是 y 呢?

这里是思考时间,大家可以想个五分钟 ……

(五分钟后……)

Alice 的一种做法是可以把整个计算过程用手机拍下来,这个视频里面包含了计算机 CPU,还有内存,在整个运行过程中的每一晶体管的状态。很显然这么做是不现实的。那么有没有更可行的方案呢?

答案是 Bob 把程序 P 转换成一个完全等价的算术电路,然后把电路交给 Alice。Alice 只要计算这个电路就可以了,然后这个过程是可以用手机拍下来的,或者用纸记下来,如果电路规模没有那么大的话。Alice 只要把参数 6 输入到电路,然后记录下电路在运算过程中,所有与门相连的引脚线上的值。并且最后的电路输出引脚的值等于 y,那么 Bob 就能确信 Alice 确实进行了计算。Alice 需要把电路的所有门的输入与输出写到一张纸上,交给 Bob,这张纸就是一个计算证明。

这样 Bob 完全可以在不重复计算电路的情况下来验证这张纸上的证明对不对,验证过程很简单:

Bob 依次检查每一个门的输入输出能不能满足一个加法等式或者一个乘法等式

比如 1 号门是一个加法门,它的两个输入是 3,4,输出是7,那么很容易就知道这个门的计算是正确的。当 Bob 检查完所有的门之后,就能确信:

Alice 确确实实进行了计算,没有作弊。

这张纸上的内容就是「满足」算术电路 P 的一个解「Solution」。

所谓的电路可满足性就是指,存在满足电路的一个解。如果这个解的输出值等于一个确定值,那么这个解就能「表示」电路的计算过程。

对于 Alice 而言,Bob 如果用这种方式验证,她完全没有作弊的空间。但是这种方法很显然有个弊端:

  • 弊端一:如果电路比较大,那么证明就很大,Bob 检查证明的工作量也很大。
  • 弊端二:Bob 在验证过程中,知道了所有的电路运算细节,包括输入。

黑科技

我们再对刚才的 Alice 与 Bob 的场景做些修改。假如,Alice 自己还有一个秘密,比如说网银密码。而 Bob 想知道 Alice 的网银密码的长度是不是 20 位长。而 Alice 想了下,告诉他密码长度应该问题不大。这时候 Bob 把一个计算字符串长度的代码转换成了电路 Q,并且发给 Alice。Alice 用电路 Q 算了一下自己的密码,然后把电路所有门的引脚发给了 Bob,并带上运算结果 20。

Wai……t,这是有问题的,Bob 拿到电路运算过程中的所有内部细节之后,不就知道密码了吗?是的,Alice 显然不能这么做。那么 Alice 应该怎么做?

答案是有很多种办法,热爱区块链技术的读者最耳熟的就是 zkSNARK[11],还有zkSTARK[12],子弹证明BulletProof[13],以及一些比较小众的技术,都可以帮 Alice 做到:

Alice 以一种零知识的方式,向 Bob 证明她计算过了电路,并且使用了她的秘密输入。

换句话说,这些「零知识的电路可满足性证明协议」为 Alice 提供了强大的武器来向 Bob 证明她的网银密码长度为 20,并且除此之外, Bob 再也得不到任何其它有用的信息。除了网银密码,Alice 理论上可以向 Bob 证明任何她的隐私数据的某些特性,但是并不暴露任何别的信息。

「零知识的电路可满足性证明协议」提供了一种最直接的保护隐私/敏感数据的技术

最近几年来,零知识证明构造技术发展日新月异,并且在区块链技术领域得到了越来越多的应用。最新的零知识证明技术,有的技术可以让 Bob 高速验证证明(在移动设备上几毫秒验证完成);有的技术可以让所有吃瓜群众帮忙验证(非交互式零知识证明);有的技术支持非常小的证明大小(小到几十个字节)。后续文章我们会逐步展开介绍。

写在最后

无论是精妙的数论定理,地图三染色问题,还是电路可满足性问题。证明存在的意义是什么?所有的证明都体现了「证明」与「验证」的「不对称性」。证明可能是一个非常耗费算力,或者脑力的活动,无论是耗时几百年的「费马大定理」,还是比特币中的 POW 证明,这些证明都凝结了在寻找证明过程中所消耗的能量,证明过程可能是超乎寻常的复杂,偶尔需要天才横空出世。而验证过程一定(或者应该)是一个非常简单的,机械的,在(多项式)有效时间内且能终止的活动。某种意义上,这个不对称性真正体现了证明的意义,展示了零知识证明的价值。

粗略看,「证明」是「逻辑」的产物,但「逻辑」与「计算」却又有着密不可分的联系,大家可能模模糊糊感觉到一些关于「证明」与「计算」之间的关联,它们贯穿始终:如机械推理、证明表达、交互计算 。这是一个有趣但更宏大的哲学问题。

参考文献

  • [1] 西蒙, 辛格, 薛密. 费马大定理: 一个困惑了世间智者 358 年的谜[M]. 上海译文出版社, 1998.
  • [2] Alec Wilkinson. The Pursuit of Beauty: Yitang Zhang solves a pure-math mystery. The New Yorker. Feb. 2015.
  • [3] 马丁, 戴维斯, 张卜天. 逻辑的引擎[M]. 湖南科学技术出版社, 2012.
  • [4] Raymond Smullyan. Gödel’s Incompleteness Theorems, Oxford Univ.Press. 1991.
  • [5] Turing, Alan. “On computable numbers, with an application to the Entscheidungsproblem.” Proceedings of the London mathematical society 2.1 (1937): 230-265.
  • [6] Pierce, Benjamin C., et al. “Software foundations.” 中文译文: <https://github.com/Coq-zh/SF-zh
  • [7] Kolata, Gina. “Computer math proof shows reasoning power.” Math Horizons 4.3 (1997): 22-25.
  • [8] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. “The knowledge complexity of interactive proof systems.” SIAM Journal on computing 18.1 (1989): 186-208.
  • [9] zkPoD: 区块链,零知识证明与形式化验证,实现无中介、零信任的公平交易. 安比实验室. 2019.
  • [10] Oded, Goldreich. “Foundations of cryptography basic tools.” (2001).
  • [11] Gennaro, Rosario, et al. “Quadratic span programs and succinct NIZKs without PCPs.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin, Heidelberg, 2013.
  • [12] Ben-Sasson, Eli, et al. “Scalable, transparent, and post-quantum secure computational integrity.” IACR Cryptology ePrint Archive 2018 (2018): 46.
  • [13] Bünz, Benedikt, et al. “Bulletproofs: Short proofs for confidential transactions and more.” 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 2018.

理解「模拟」

探索零知识证明系列(二)

I know that I know nothing —— 苏格拉底

相信很多人都听说过零知识证明,但是只有极少数人听说过模拟,然而模拟是理解零知识的关键。

我们在第一篇文章『初识「零知识」与「证明」』(链接)[1]中介绍了一个简单的零知识交互系统:地图三染色问题。那么这个系统真的是零知识的吗?我们为什么要相信这个结论呢?有证明吗?在 Alice 与 Bob 的对话过程中,如果不零知识,Alice就被坑了。交互式系统的设计者「我」需要让 Alice 确信,这个对话确实是零知识的。

如果从直觉主义角度解释,要证明一个交互系统中存在信息泄露,那么你只需要指证:第几个 bit 导致信息泄露即可;但如果要证明不存在信息泄露,那么你要对着所有信息流中的所有 bit 说,这从1,2,3,4,5,…… 编号的 bit 都没泄露任何信息。看官们,这是不是很难?

本文约八千字,略微烧脑。

安全的定义与不可区分性

首先,一个交互式系统,也就是一个对话,它的「零知识」需要证明。毕竟,现代密码学是建立在严格的形式化系统之上。在证明之前,还需要明确「安全假设」到底有哪些。所谓安全假设,比如我们说一个系统的权限隔离做得无比精确,每一个用户只能看到被授权的信息,但是这基于一个安全假设:管理员账号没有被破解。又比如在手机银行软件里,只能通过短信认证码,才能完成转账功能,这也基于一个安全假设:你的手机 SIM 卡没有被克隆。如果我们深入地分析每一个我们感觉安全的系统,都存在大量的似乎不那么稳固的安全假设。比特币私钥安全吗?比特币账户的安全假设也不少:首先你的助记词不能让别人知道,手机钱包里私钥保存加密算法足够强,密钥派生算法正规,你不能忘记助记词,等等等。

脱离安全假设来谈安全都是在耍流氓。一切安全都有前提的。只有经过数学证明之后,大家才能够确信这个 算法/方案 的安全性基于一些非常明确的「安全假设」。

在证明之前,还缺少一个东西,那就是「安全定义」。在多数人的认知系统中,安全就是一个框,什么都可以往里装。大家应该好好提醒下自己,当谈论安全二字的时候,有没有想过到底什么是安全?怎么算安全?

「安全」需要有一个数学意义上的严格定义

伟大的科学家香农(Claude Shannon)从信息论的角度给出了一个非常靠谱的安全性定义[2]:

完美安全:假设你是一个攻击者,你通过密文获取不到任何有价值的信息,破解的唯一手段就是靠瞎蒙。

大家想一想,这个定义很有趣,通过密文获取不到信息,这就意味着你没有获得任何额外的计算能力,能够帮助让你以更短的时间来计算出明文。

但是这个定义太完美,以至于使用的加密算法都很难满足这个安全性定义。后来 Goldwasser 与 Micali 等人写了另一篇载入史册的经典『概率加密』[2]。

在这篇论文中定义了这样一个概念:语义安全。所谓语义安全在完美安全的定义上放松了些要求。

语义安全:假设你是一个攻击者,你通过密文在多项式时间内计算不出来任何有价值的信息。

好了,这个看起来靠谱多了。接下来一个问题就是,怎么理解「计算不出来信息」这个概念?这看来要对信息进行度量,信息的定义又是什么呢?

我们又引入一个概念——「不可区分性」,来重新表述加密算法的安全性:假设你是一个攻击者,而我有一个加密算法:

  1. 你随机产生两段等长的明文,m1=「白日依山尽,黄河入海流」,m2=「烫烫烫烫烫,烫烫烫烫烫」
  2. 你把这两段明文,m1m2 交给我
  3. 我随机挑选一个明文,不告诉你是哪一个,然后进行加密,产生一个密文 c
  4. 我把密文 c 出示给你看,让你猜这个c 究竟是由唐诗加密产生,还是乱码加密产生
  5. 如果你用一台计算机来破解c,在多项式时间内破解不出来,也就是说你没办法区分c的来源,那么就说明加密算法是语义安全的

OK,理解完「不可区分性」,我们再回到「零知识」,如何证明一个交互式系统是「零知识」呢?首先我们要定义下零知识这个概念。

注:不可区分性是概率意义上的不可区分;在学术上,它可以分为「完全不可区分」,「统计不可区分」,还有「计算不可区分」。在本文中,我们暂时不需要理解这些概念的差别。

遇见模拟器

先开个脑洞,设想在平行宇宙中,有两个平行的世界,一个叫做「理想世界」(Ideal World),另一个叫做「现实世界」(Real World)。我们每一个个体可以在两个平行世界中愉快地玩耍,但是两个世界的普通人无法互相感知,也无法互相沟通。

假设「你」是一个很厉害的密码破解者,而且「你」不是普通人,具备在平行宇宙之间穿梭的能力。而 Alice 有一个地图三染色的答案,你的目的是通过和 Alice 对话来获取地图三染色的答案,会话的过程参考上一篇文章的「地图三染色问题」协议。

继续脑洞,Alice 只存在「现实世界」中;在「理想世界」,Alice 被「替换」成了一个长相与声音一模一样的个体,我们称替身为 Zlice。下一步,把「你」同时放入两个世界中,但不让你知道是你当前位于哪一个世界。你的两个分身所面对的都是一个 “Alice”模样的人。

再重复一遍,在「现实世界」中, 与你对话的是一个真实的,并且诚实的 Alice;而在「理想世界」中,与你对话的是 Zlice (假 Alice),Zlice 虽然相貌语言与 Alice 并无二致,但差异是,Zlice 并不知道「知识」,即不知道一个三染色问题的答案。

接下来在这两个世界中,你的两个分身将同时与真假 Alice 进行对话。神奇的事情发生了,最终在两个世界中,你的两个分身都被说服了,都经过n轮挑战,没有发现对方作弊,即「你」的两个分身都认为对方确实知道「答案」。换句话说,「你」没有能力「区分」出来自己到底在 「现实世界」 还是 「理想世界」,当然也没能力「区分」和自己对话的究竟是 Alice 还是 Zlice。不仅如此,对于吃瓜群众我而言,如果把「我」作为观察者放入任何一个世界中,我会和你一样「无法区分」出来眼前的 这个长相为 “Alice” 的人到底是真还是假。

下面是烧脑结论:

这个交互系统为何是「零知识」?因为 Zlice 是没有任何知识,而且她和 Alice 不可区分。

我再换个方式解释:因为你和我都没办法区分我们究竟是在哪个世界中,两个世界发生的交互过程几乎不可区分,而且其中一个世界中根本就不存在知识,因此,我们说这个交互协议——「地图三染色问题」是「零知识的」。

这里还有个前提,理想世界必须是算法可构造的。然后,有一个「神」,他通过算法「模拟」了一个「理想世界」,其中构造了一个算法叫做 Zlice,她没有「知识」作为输入,也即「零知识」;除此之外,「理想世界」与「现实世界」一模一样。

设想你在对话过程中,如果真 Alice 泄露了信息,那么你就能立即区分出面前这个人是 真 Alice 还是 Zlice,Zlice 是不可能伪装泄露信息的。因此可以得出结论:

真Alice 没有泄露任何信息。

这个神,被称为「模拟器」(Simulator),而在理想世界中,和你对话的这个 Zlice 幻象其实也是「模拟器」,你在理想世界中,所有能感知到的东西都是模拟器「模拟」出来的。

好了,到这里,我们用「模拟器」这个概念对「零知识」进行了定义。

接下来,我们开始进入证明零知识的环节。

区分两个世界

(Save World State as Snapshot X)

证明的零知识过程,等价于构造(寻找)一个「模拟」算法,这个算法能够让模拟器来模拟出一个「没有知识」的理想世界。如果这个算法存在,而且两个世界不可区分,那么就证明完毕。

等等,可能「你」会觉得哪里不对劲。

假如说真的存在这种算法,而且它能够在没有知识的情况下骗过我,那么在「现实世界」中,不排除真 Alice 也使用了这样的算法来欺骗我。这样一来,我岂不是在两个世界中都被欺骗了。那么这个交互协议就失去意义了。

其实,这里有个关键点,借用电影『盗梦空间』中的剧照,在「理想世界」中有点东西是和「现实世界」本质不同的。这个东西是区分两个世界的关键,而它要让我们「无法感知」。这个东西不是梦境中的陀螺,它是一种「超能力」,模拟器 Simulator 所具备的超能力。

比如这样一种超能力:「时光倒流」。

(上图是电影『土拨鼠之日』的剧照,剧中主人公每次睡醒都会回到2月2日的早上,这样他永远活在同一天里)

等等,各位看官,不是刚才我们一直在讨论不可区分性吗?怎么两个世界又需要区分啦?“我糊涂了”。不要慌,所谓的不可区分性针对的是理想世界中的个体认知而言。而「可区分性」是对位于世界外部的神而言。

设想下在我们周围,如果有一个人有时空穿越能力,或者他能让时间回退到一年前,那么我们这些凡夫俗子完全是一脸茫(meng)然(bi)的,无从感知。那么,如果「模拟器」可以在他构造出的「理想世界」中实现「时间倒流」,那么他就可以达成一些神奇的事情,从而骗过作为验证者身份的「你」,也能骗过观察者「我」。对于「你」而言,你明白,在「理想世界」中,时间是可以回退的,但是在「现实世界」中,显然真 Alice 不可能拥有超能力。虽然你和我不能区分在哪个世界里,但是至少我们知道在两个世界中的其中「现实世界」里,对面那个Alice是没办法欺骗我们的,当然我们却不能说出我们到底在哪个世界中。

到此,交互协议的「零知识」已经证明完了。各位是否已经明白了?我再给大家再梳理下证明思路:

首先「零知识」是为了保护 Alice 的利益,因为 Alice 不想在交互过程中透露更多的信息给 Bob,不想让 Bob 知道她所拥有的秘密 w,甚至不想让 Bob 从交互的过程中分析出哪怕一丁点的信息。那么怎么保证这一点呢?「模拟器」这时候登场了,它能模拟出一个和现实世界外表一模一样的「理想世界」,然后「模拟器」在这个世界中可以轻松地骗过任何一个对手,让对方无法分辨自己是在现实世界中,还是理想世界中。因为「模拟器」手里没有那个秘密 w,「理想世界」是零知识的。又因为两个世界的不可区分性,所以我们可以得出结论:Alice 的交互协议是「零知识」的。

我们来看一个具体的例子,上一篇文章[1]中提到的地图3染色问题。

地图三染色问题的零知识证明

回忆一下「地图三染色问题交互系统」:

  • 第一步:Alice 把地图染色答案做一次完全置换,然后将所有顶点盖上纸片,交给 Bob
  • 第二步:Bob 随机挑选一条边
  • 第三步: Alice 打开指定边的两端顶点的纸片,Bob检验两个顶点的颜色是否相同,如果不同则通过,如果相同则失败
  • 回到第一步,重复 n

我们接下来就来证明上述这个交互是零知识的,这里先假设验证者 Bob 是诚实的,这有助于大家理解这个证明过程。然后我们再讨论,如果 Bob 不诚实的证明方法。

在「理想世界」中,跟 Bob 对话的是一个「模拟器」,它模拟出了整个世界的样子。Bob 按照三染色问题的交互协议进行交互。模拟器并没有一个三染色答案,它索性把所有的顶点都染成了灰色。

首先,模拟器模仿 Alice ,把每个顶点用纸片盖起来。然后发给 Bob。

Bob 随机挑选了一条边,挑战证明者。

模拟器这时候不能打开纸片,因为这条边两端的颜色都是灰色啊。

这时候,模拟器要发挥「超能力」了,他运用时间倒流的技能,回到对话第一步之前。

模拟器现在处于第一步,他把最下面那条边的两端染上任意不同的颜色,然后重新盖上纸片,并发给 Bob。

Bob 这时候无法感知到时间已经倒退回第一步了,对他来说,一切都是新鲜的,他「诚实」地再次选择了最下面的边。

这时候模拟器就可以放心地打开纸片,让 Bob 检查。Bob 很显然会被骗过。然后 Bob 一轮轮地重复这个过程,每一次模拟器都能用时间倒流的方式骗过 Bob。

于是在理想世界中,模拟器并没有任何三染色答案的「知识」,却同样能骗过Bob,并且从概率上来看,与「现实世界」中被观察到的交互过程高度地一致(完全一致的概率分布)。于是上面的过程展示了模拟器的算法的存在性,也就相当于证明了交互系统的「零知识性质」

不诚实的 Bob

在上面的证明过程中,有一个相当强的假设,就是每次时间倒流之后,Bob都会选择同一条边。如果 Bob 每次都会换一条不同的边呢?没关系,如果在模拟器第一次实施时间倒流之后,Bob又选择了不同的边,那么模拟器可以把颜色打乱之后,再次运行时间倒流,在多次时间倒流之后,Bob 极大的概率总会一次选择模拟器进行染色的那条边,然后这时候模拟器才走到第三步,打开纸片。

阿里巴巴、洞穴与芝麻开门

在网上众多的讲解「零知识证明」的中文科普文章中,有一个例子流传非常广,这就是阿里巴巴与强盗的故事。可惜地是,这些不同版本的故事都只讲了一半。那么我接下来讲一个不一样的「阿里巴巴」与「四十大盗」的故事:

在很久很久以前,在一个叫做巴格达的城市里,住着一个人叫阿里巴巴。每天阿里巴巴会到集市上买东西。

有一天,阿里巴巴被一个盗贼抢了钱包,于是他一路追着盗贼到了一个山洞口,然后盗贼就消失了。阿里巴巴发现洞口里面有两条岔路,如下图所示。

阿里巴巴不知道盗贼往哪边跑了,于是他决定去「左边」岔道看看,很快阿里巴巴就发现这是个死胡同,也不见盗贼踪影。然后他又去「右边」岔道检查,也是个死胡同,不见盗贼踪影。阿里巴巴自言自语道:「该死的盗贼跑哪去了呢?」

第二天,阿里巴巴又去集市买东西,这次另一个盗贼抢了他的篮子,然后阿里巴巴追着这个盗贼到了昨天同样的山洞口,然后盗贼又不见了,这一次阿里巴巴决定先去「右边」岔道看看,没有发现盗贼,然后再去左边看看,也同样不见盗贼。这好奇怪。

第三天,第四天,……,第四十天,同样的故事上演,阿里巴巴追着第四十个大盗到了神秘的洞口,盗贼就消失了。阿里巴巴想,这个山洞里面一定有机关,于是他躲在「右边」岔道的尽头,耐心地等了很长时间,这时一个盗贼跑了进来,走道岔道尽头之后,念了一个咒语「芝麻开门」。这时候墙壁居然打开了,盗贼跑进去之后,然后墙壁又合上了,这时候另一个受害者追了进来,找了半天,一无所获。

阿里巴巴随后等他们走了之后,试验了一下这个咒语,果然非常有效,而且阿里巴巴发现这个墙壁通向「左边」岔道。后来,阿里巴巴找到了更换咒语的办法,并且把一个新咒语和洞穴的地理位置写在了一张羊皮纸上。

注:到这里,故事并没有结束…. (上字幕)很久很久以后

在很多年后,到了80年代,阿里巴巴的羊皮纸流落到了几个密码学家手里,他们跑到巴格达,找到了洞穴的位置,尽管过了几个世纪,咒语居然仍然有效,这几个密码学家兴奋地打开墙壁,在两个岔道之间跑来跑去。

一家电视台很快知道了这个奇异事件,一个密码学家 Mick Ali(与密码学家 Micali 发音相似)决定向电视观众展示他知道这个咒语,首先,电视节目主持人把摄像机架在洞口,然后让所有人都在山洞口等待,这时候 Mick Ali一个人进入到山洞中,然后主持人抛一个硬币,来决定让 Mick Ali 从哪个岔道跑出来。为了纪念阿里巴巴与四十大盗,Mick Ali 重复了四十遍每次都成功。

节目非常成功。但很快,另外一个电视台眼红,也想拍一个类似的节目,但是Mick Ali 因为签了独家协议,没办法参与这个新节目。怎么办呢?第二个电视台的主持人心生一计,他找了一个和 Mick Ali 很像的演员,穿着打扮、姿态和说话口音都模仿 Mick Ali。然后他们开拍了,每次主持人掷硬币后,都让这个演员跑出来,但是很显然,演员并不知道咒语,没办法打开那个墙壁。于是有时候演员碰巧会成功,有时候则会失败,于是演员很辛苦,重复了将近一百次,才成功了四十次。最后这个狡猾的新节目主持人,把录制视频进行了剪辑,只保留了成功的片段,错误的片段都删除了。然后这个新节目和 Mick Ali 的节目在同一时间,不同频道播出。然后观众们完全无法区分哪个视频是真的,哪个视频是假的。第一个电视台的主持人完全明白 Mick Ali 是真正知道墙壁的咒语的人,但是他却不能把这个事实传递给无辜的观众们。

看到这里,大家是不是对「模拟」慢慢有了感觉?这里第二个电视台的主持人通过剪辑视频的方式,而不是「时间倒流」。他对「理想世界」,也就是电视中播出的内容所在的世界,进行了外部干预,达到了同样的效果。对理想世界而言,这种剪辑本质上就是一种超能力。

这个故事其实来源于一篇论文『如何向你的孩子解释零知识证明』(How to Explain Zero-Knowledge Protocols to Your Children)[3],发表在1989年的美密会议上。

模拟与图灵机

一谈到超能力,大家有没有觉得这玩意不科学。是的,如果我们无脑地用「超能力」来解释任何事情,那么我们逻辑就无法自恰(Consistent)。在理想世界中,模拟器是不能随便开挂的,比如模拟器肯定不能直接修改 Bob 的内部状态,比如 Bob 在验证步骤明明验证失败,但是模拟器强硬去把验证结果改为「接受」,这会导致我们可以证明:「任何的交互系统都是零知识的」,这个错误结论。

模拟器不是理想世界中全能的上帝

那么模拟器到底可以是什么呢?模拟器其实只是一个图灵机。所谓的「时间倒流」,「剪辑录像」这类的所谓超能力并不是玄乎的超自然能力,而是图灵机可以实现的功能。计算机专业的朋友们肯定都用过 VMWare,虚拟机之类的软件,本文讲的「模拟器」完全可以想象成一个「虚拟机」软件,它能虚拟出一个计算机环境,这个虚拟环境就是我们上文说的「理想世界」。「时间倒流」如何解释呢?不知道大家有没有用过虚拟机软件的「快照」功能(Snapshot),使用快照的时候,虚拟机软件可以把整个虚拟计算机的所有状态保存下来,然后在任意时刻,虚拟机软件都可以重新回到保存快照的位置继续运行。

注:其实所谓时间倒流是计算机中的一个基本操作,在程序语言理论中有一个概念叫做 Continuation。抽象地讲,Continuation 表示从现在开始到未来的计算。Continuation这是控制流的一个显式抽象,而 goto,call-with-current-continuation,甚至 thread scheduling 都可以看做是操作 Continuation 的操作符。比如采用call/cc,也就是call-with-current-continuation 就可以轻松地实现「回溯」功能。保存快照可以理解为保存当前的 Continuation,而回到过去的某一刻,就是应用这个Continuation。

不管 Zlice 还是 Bob,还有我们的每一个观察者,都是一个个可执行程序。这些程序被拷贝到了虚拟机里。Zlice 与 Bob 的会话实际上就是这两个程序之间的通讯。观察者是 Hook 在 Zlice 与 Bob 进程 IO 上的程序。在上文的地图三染色「理想世界」的诚实 Bob,实际上是 Bob 进程调用了虚拟机的「随机数发生器」,而这个随机数发生器是能被 Zlice 操纵的。「现实世界」是外部运行虚拟机软件的计算机环境。

大家是不是又有所悟,我再强调一下:

证明零知识的过程,就是要寻找一个算法,或者更通俗点说,写出一段代码,它运行在外部计算机系统中,但是实现了虚拟机的功能。而且在虚拟机中,需要有一个不带有「知识」作为输入的 Zlice,可以骗过放入虚拟机运行的 Bob。

如果还没理解上面我这句话,请时光回退到『区分两个世界』这一小节,重新思考模拟。:P (Load World State from Snapshot X)

柏拉图的洞穴寓言

模拟无处不在,哥德尔不完备性定理就使用了模拟的概念,用哥德尔数(Godel Numbers)模拟了形式算术。图灵提出了「Universal Turing Machine」(通用图灵机)的概念,这种图灵机可以模拟自身。

但最早的「模拟」概念,出自『理想国』一书的第七卷[4]中,古希腊哲学家柏拉图讲了这么一则寓言——Allegory of Cave:

plato’s cave

设想在一个暗无天日的山洞中,有一排被锁链锁住的囚徒,他们从小就只能看到前方的墙壁。这些囚徒们身后是一堵墙,再后面有一堆放着火,在火与墙壁之间,有一些人举着道具和木偶来回走,这样道具木偶就会在火光映射下在墙壁上投下影子。而这些囚徒们整天就只能看着这些影子。因为这些囚徒们从打出生起,所闻所见就只是前方洞壁上的各种影子,他们会以为所看到的这些影子就是真实的世界。

然而有一天,一个囚徒偶然挣脱锁链,他回头看到了火。但是他从小到大仅能看到暗淡的影子,他第一次看到了明亮的火光。看到了道具和木偶,假如有人告诉他,这些道具和木偶才是实物,他一定会嗤之以鼻,会坚持认为影子才是真实的。

柏拉图假设说,如果这个囚徒强制拖出洞穴,到外面去看到真实的世界, 一开始囚徒会不适应真实世界的光亮而感到刺目眩晕,他会因此而愤怒。 但是当他慢慢适应了这个世界,看到太阳,树木,河流,看到星空,他逐渐明白,这个世界比洞穴中那个世界更为优越高级。他再也不想回到黑暗的洞穴生活中了。

过了一段时间,他对洞穴中的囚徒心生怜悯,于是想去把他们都带出来。但是当他再次返回洞穴中,他因为已经适应了外面明亮的世界,回到洞穴中反而看不清楚。被锁的囚徒们反而认为他的视力受损,胡言乱语,是个疯子,最后当他想尽办法把这群囚徒带出洞穴时,被囚徒们联手杀死。

这是则人类命运的寓言,就和那一排被锁链锁着的囚徒类似, 我们以为眼睛看到的就是世界的真相,但实际上,那也许是幻象,就像洞穴墙壁上投下的影子一样。

未完待续

本文章介绍了理解零知识所需的关键概念——模拟。任何一个零知识的协议,都可以通过构造一个「理想世界」来理解。第一次接触这个概念的读者需要反复琢磨。

计算机科学中有两个方法论至关重要,第一个是「抽象」,第二个是「模拟」

回顾一下在地图三染色问题中,Bob 在「理想世界」与「现实世界」中的对话。虽然 Bob 无法区分两个世界,但是有一点,他可以确信:现实世界中,Alice 没有超能力。

问题来了,Alice 没有超能力,并不能直接证明 Alice 真的有答案。万一这个交互协议并不能保证 Alice 一定有知识呢?「零知识」保护了 Alice 的利益,谁来保证 Bob 的利益呢?这个问题留给下一篇。

致谢: 本文受密码学教授 Matthew Green 发表在2014年与2017年的两篇个人博客文章[10-11]启发。*

参考文献

  • [1] 初识「零知识」与「证明」. 安比实验室. 2019.
  • [2] Shafi Goldwasser and Silvio Micali, Probabilistic Encryption, Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984.
  • [3]Quisquater, J.J., Quisquater, M., Quisquater, M., Quisquater, M., Guillou, L., Guillou, M.A., Guillou, G., Guillou, A., Guillou, G. and Guillou, S., 1989, August. How to explain zero-knowledge protocols to your children. In Conference on the Theory and Application of Cryptology (pp. 628-631). Springer, New York, NY.
  • [4] 柏拉图 and 吴献书, 1986. 理想国 (Vol. 1, No. 986, p. 1). 商务印书馆.
  • [5] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. “The knowledge complexity of interactive proof systems.” SIAM Journal on computing 18.1 (1989): 186-208.
  • [6] Oded, Goldreich. “Foundations of cryptography basic tools.” (2001).
  • [7] Rackoff, Charles, and Daniel R. Simon. “Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack.” Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1991.
  • [8] Goldreich, Oded, Silvio Micali, and Avi Wigderson. “Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems.” Journal of the ACM (JACM) 38.3 (1991): 690-728.
  • [9] zkPoD: 区块链,零知识证明与形式化验证,实现无中介、零信任的公平交易. 安比实验室. 2019.
  • [10] Matthew Green. Zero Knowledge Proofs: An illustrated prime. 2014. https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/
  • [11] Matthew Green. Zero Knowledge Proofs: An illustrated primer, Part 2. 2017. https://blog.cryptographyengineering.com/2017/01/21/zero-knowledge-proofs-an-illustrated-primer-part-2/

寻找「知识」

探索零知识证明系列(三)

And what, Socrates, is the food of the soul? Surely, I said, knowledge is the food of the soul. 苏格拉底,什么是灵魂的食物?我说过,当然是知识。 —— 柏拉图

导言:有些理论非常有趣,零知识证明便是其中之一,摸索了许久,想写点什么,与大家一起讨论。本文是『探索零知识证明』系列的第三篇。全文约 8,000 字,少量数学公式。

本文将在 Github 进行更新与修正。

「零知识」vs. 「可靠性」

我们在许多介绍零知识证明的文章中都能看到这样三个性质:

  • Completeness —— 完备性
  • Soundness —— 可靠性
  • Zero-Knowledge —— 零知识

但是少有文章深入解释这个特性背后的深意和洞见。

在『系列(二)理解「模拟」』一文中,我们介绍了「模拟器」这个概念。许多介绍文章也避而不谈「模拟」,但「模拟」可以说是安全协议中核心的核心,因为它是定义「安全性」的重要武器。

通常,我们定义安全会采用这样一种方式,首先列出一些安全事件,然后说明:如果一个系统安全,那么列出来的安全事件都不会发生。

Rather than giving a list of the events that are not allowed to occur, it (the definition of zero-knowledge proof) gives a maximalist simulation condition.

— Boaz Barak

借用密码学家 Boaz Barak 的话,翻译一下,「零知识证明」并不是通过给出一个不允许发生的事件列表来定义,而是直接给出了一个最极致的「模拟条件」。

所谓「模拟条件」是指,通过「模拟」方法来实现一个「理想世界」,使之与「现实世界」不可区分;而由于在理想世界中不存在知识,所以可以推导出结论:现实世界满足「零知识」。

我们继续分析下一个交互系统(安全协议)的三个性质:「完备性」、「可靠性」与「零知识」。

可靠性(Soundness):Alice 在没有知识的情况下不能通过 Bob 的验证。

完备性(Completeness):Alice 在有知识的情况下可以通过 Bob 的验证。

零知识(Zero-knowledge):Alice 在交互的过程中不会泄露关于知识的任何信息。

我们可以看出来「可靠性」和「完备性」有一种「对称性」。可靠性保证了恶意的 Alice 一定失败,而完备性保证了诚实的 Alice 一定成功。

「完备性」比较容易证明,只要 Alice 诚实,Bob 也诚实,那么皆大欢喜。这好比,写好一段代码,喂了一个测试用例,跑完通过收工。

我们来想想「可靠性」应该如何定义?这个可靠性的逆否命题是:(在现实世界中)如果 Alice 能通过 Bob 的验证,那么 Alice 一定有知识。或者说:Alice 知道那……个「秘密」!

下面的问题是如何证明 Alice 知道一个「秘密」?

这好像也很难,对不对?假如我们需要证明一台机器知道一个「秘密」,最简单的办法就是我们在机器的硬盘里,或者内存中找到这个「秘密」,但是这样暴露了秘密。如果这台机器是黑盒子呢?或者是 Alice 呢?我们没有读心术,猜不到她心里的那个秘密。

如何定义「To Know」?

「零知识」保证了 验证者 Bob 没有(计算)能力来把和「知识」有关的信息「抽取」出来。不能抽取的「知识」不代表不存在。「可靠性」保证了知识的「存在性」。

只有「知识」在存在的前提下,保证「零知识」才有意义

本文将探讨「可靠性」和「To Know」。


为了进一步分析「知识」,接下来首先介绍一个非常简洁,用途广泛的零知识证明系统 —— Schnorr 协议。这个协议代表了一大类的安全协议,所谓的 Σ-协议,而且 Schnorr 协议扩展也是 零知识数据交换协议 zkPoD [1] 的核心技术之一。

简洁的 Schnorr 协议

Alice 拥有一个秘密数字,a,我们可以把这个数字想象成「私钥」,然后把它「映射」到椭圆曲线群上的一个点 a*G,简写为 aG。这个点我们把它当做「公钥」。

  • sk = a

  • PK = aG

请注意「映射」这个词,我们这里先简要介绍「同态」这个概念。椭圆曲线群有限域之间存在着一种同态映射关系。有限域,我们用 Zq这个符号表示,其中素数 q是指有限域的大小,它是指从 0, 1, 2, …, q-1 这样一个整数集合。而在一条椭圆曲线上,我们通过一个基点,G,可以产生一个「循环群」,标记为 0G, G, 2G, …, (q-1)G,正好是数量为 q个 曲线点的集合。任意两个曲线点正好可以进行一种「特殊的二元运算」,G + G = 2G2G + 3G = 5G,看起来这个二元运算好像和「加法」类似,满足交换律和结合律。于是我们就用 +这个符号来表示。之所以把这个群称为循环群,因为把群的最后一个元素 (q-1)G,再加上一个 G就回卷到群的第一个元素 0G

给任意一个有限域上的整数 r,我们就可以在循环群中找到一个对应的点 rG,或者用一个标量乘法来表示 r*G。但是反过来计算是很「困难」的,这是一个「密码学难题」—— 被称为离散对数难题[2]。

也就是说,如果任意给一个椭圆曲线循环群上的点 R,那么到底是有限域中的哪一个整数对应 R,这个计算是很难的,如果有限域足够大,比如说 256bit 这么大,我们姑且可以认为这个反向计算是不可能做到的。

Schnorr 协议充分利用了有限域和循环群之间单向映射,实现了最简单的零知识证明安全协议:Alice 向 Bob 证明她拥有 PK 对应的私钥 sk

第一步:为了保证零知识,Alice 需要先产生一个随机数,r,这个随机数的用途是用来保护私钥无法被 Bob 抽取出来。这个随机数也需要映射到椭圆曲线群上,rG

第二步:Bob 要提供一个随机数进行挑战,我们把它称为 c

第三步:Alice 根据挑战数计算 z = r + a * c,同时把 z发给 Bob,Bob通过下面的式子进行检验:

z*G ?= R + c*PK = rG + c*(aG)

大家可以看到 Bob 在第三步「同态地」检验 z 的计算过程。如果这个式子成立,那么就能证明 Alice 确实有私钥 a。可是,这是为什么呢?

z 的计算和验证过程很有趣,有几个关键技巧:

  1. 首先 Bob 必须给出一个「随机」挑战数,然后 Bob 在椭圆曲线上同态地检查 z 。如果我们把挑战数 c 看成是一个未知数,那么 r+a*c=z 可以看成是一个一元一次方程,其中 ra 是方程系数。请注意在 c 未知的前提下,如果 r + a*x = r' + a'*x 要成立,那么根据 Schwatz-Zippel 定理[3],极大概率上 r=r'a=a' 都成立。也就是说, Alice 在 c 未知的前提下,想找到另一对不同的 r',a' 来计算 z 骗过 Bob 是几乎不可能的。这个随机挑战数 c 实现了ra 的限制。虽然 Bob 随机选了一个数,但是由于 Alice 事先不知道,所以 Alice 不得不使用私钥 a 来计算 z。这里的关键: c 必须是个随机数。
  2. Bob 验证是在椭圆曲线群上完成。Bob 不知道r,但是他知道 r 映射到曲线上的点R;Bob 也不知道 a,但是他知道 a 映射到曲线群上的点 PK,即 a*G。通过同态映射与Schwatz-Zippel 定理,Bob 可以校验 z 的计算过程是否正确,从而知道 Alice 确实是通过 ra 计算得出的 z,但是又不暴露 ra 的值。
  3. 还有,在协议第一步中产生的随机数 r 保证了 a 的保密性。因为任何一个秘密当和一个符合「一致性分布」的随机数相加之后的和仍然符合「一致性分布」。

证明零知识

我们这里看一下 Schnorr 协议如何证明一个弱一些的「零知识」性质——「SHVZK」:

注:这里我们证明的仅仅是 Special Honest Verifier Zero-Knowledge(SHVZK)。SHVZK 要求协议中的 Bob 的行为不能不按常理出牌,比如他必须按协议约定,在第二步时,去传送带上取一个新鲜的随机数,并且立即使用。而通常意义上的「零知识」是不会对 Bob 做任何要求,所以我们说这里是一个弱一些的性质。虽然目前 Schnorr 协议不能证明完全的「零知识」,但经过添加一些协议步骤,就可以达到完全零知识的目的,细节这里不展开,有兴趣的读者请参考文献[4]。以后我们在讨论 Fiat-Shamir 变换时,还会再次讨论这个问题。

首先「模拟器」模拟一个「理想世界」,在理想世界中模拟出一个 Zlice 和 Bob 对话,Zlice 没有 Schnorr 协议中的知识,sk,而 Bob 是有公钥 PK的。请大家看下图,Bob 需要在 Schnorr 协议中的第二步出示一个随机数 c,这里有个额外的要求, 就是 Bob 只能「诚实地」从一个外部「随机数传送带」上拿一个随机数,每一个随机数都必须是事先抛k次「硬币」产生的一个 2^k 范围内的一次性分布随机数。Bob 不能采用任何别的方式产生随机数,这就是为何我们要求 Bob 是诚实的。

下面演示 Zlice 如何骗过 Bob:

序幕:请注意 Zlice 没有关于sk的知识,这时 Bob 的随机数传送带上已经预先放置了一些随机数。

第一步:Zlice 产生一个一致性分布的随机数c,并且利用一个新的「超能力」,将刚刚产生的随机数 c 替换掉 Bob 的随机数传送带上第一个随机数。这时候,Bob 无法察觉。

第二步:Zlice 再次产生一个随机数 z,然后计算 R'=z*G - c*PK,并将 R'发送给 Bob。

第三步:这时候Bob 会从随机数传送带上取得 c,并且将 c 发送给 Zlice。请注意这个c 正好就是第一步中 Zlice 产生的 c

第四步:Zlice 将第三步产生的随机数 z 发送给 Bob,Bob 按照 Schnorr 协议的验证公式进行验证,大家可以检查下,这个公式完美成立。

大家可以再对比下「现实世界」的 Schnorr 协议,在两个世界中,Bob 都能通过验证。

但区别是:

  • 在「理想世界中」,Zlice 没有 sk;而在「现实世界中」,Alice 有 sk
  • 在「理想世界中」,z 是一个随机数,没有涉及 sk;而在「现实世界中」,z 的计算过程里面包含 sk
  • 在「理想世界中」,Zlice 使用了超能力,替换了 Bob 的随机数;而在「现实世界中」,Alice 看不到 Bob 的随机数传送带,也无法更改传送带上的数字

这里请大家思考下:Schnorr 协议中,Bob 在第二步发挑战数能不能和第一步对调顺序?也就是说 Bob 能不能先发挑战数,然后 Alice 再发送 R = r*G

(两分钟后……)

答案是不能。

如果 Alice 能提前知道随机数,那么 (现实世界中的)Alice 就可以按照模拟器 Zlice 做法来欺骗 Bob。

再遇模拟器

其实,「可靠性」和「零知识」这两个性质在另一个维度上也是存在着一种对称性。可靠性保证了恶意的 Alice 一定失败,零知识保证了恶意的 Bob (窃取知识)一定不会成功。有趣地是,这种对称性将体现在模拟出来的「理想世界」中。

我们分析下可靠性这个定义:Alice 没有知识 导致 Bob 验证失败。它的逆否命题为:Bob 验证成功 导致 Alice 一定有知识。

我们再次求助模拟器,让他在可以发挥超能力的「理想世界」中,去检验 Alice 的知识。

再次,请大家设想在平行宇宙中,有两个世界,一个是叫做「理想世界」,另一个叫做「现实世界」。理想世界有趣的地方在于它是被「模拟器」模拟出来的,同时模拟器可以在理想世界中放入带有超能力的 NPC。这次把 Alice 的两个分身同时放入「理想世界」与「现实世界」。

假设「你」扮演 Bob 的角色,你想知道和你对话的 Alice 是否真的是「可靠的」。 于是把你放入「理想世界」,借助一个具有超能力的 NPC,你可以把对面的 Alice 的知识「抽取」出来。

W…hat?我们不是刚刚证明过:协议是零知识的吗?零知识就意味着 Bob 抽取不出任何的「知识」碎片。这里敲黑板,「零知识」是对于「现实世界」而言的。我们现在正在讨论的是神奇的「理想世界」。

重复一遍,在「理想世界」中,你可以借助一个有超能力的 NPC 来抽取 Alice 的知识,从而可以保证「现实世界」中的 Alice 无法作弊。可以想象一下,一个作弊的 Alice,她肯定没有知识,没有知识也就不可能在「理想世界」中让 NPC 抽取到任何东西。

然而在「现实世界」中,你无法借助 NPC,当然也就看不到 Alice 的知识,也就不会和「零知识」性质冲突。因为两个世界发生的事件是「不可区分」的,我们可以得到这样的结论:在「现实世界」中,Alice 一定是存在知识的。

整理一下思路:如何证明在一个交互会话中 Alice 不能作弊呢?我们需要为这个交互会话定义一个「模拟算法」,该算法可以模拟出一个「理想世界」,其中有一个特殊的角色叫做「抽取器」(Extractor),也就是我们前面说的 NPC,它能够通过「超能力」来「抽取」Alice 的知识,但是让对方「无所察觉」。

注意,超能力是必不可少的!这一点在『系列(二)理解「模拟」』有解释,如果模拟器在没有超能力的情况下具备作弊能力,那相当于证明了协议「不可靠」(Unsoudness)。同样地,如果「抽取器」在没有超能力的情况下具备抽取信息能力,那相当于证明了协议不零知(Not-zero-knowledge)。

最后一点,超能力是什么?这个要取决于具体的交互系统的证明,我们接下来就先拿我们刚刚讲过的Schnorr 协议切入。

Proof of Knowledge :「知识证明」

我们来证明一下 Schnorr 协议的「可靠性」,看看这个超能力 NPC 如何在「理想世界」中把 Alice 私钥抽取出来。而这个「超能力」,仍然是「时间倒流」。

schnorr-extractor-1

第一步:Alice 选择一个随机数 r,并且计算 R=r*G,并将 R 发给「抽取器」

schnorr-extractor-2

第二步:抽取器也选择一个随机的挑战数c,并且发给 Alice

schnorr-extractor-3

第三步:Alice 计算并且回应 z,然后抽取器检查 z是否正确

schnorr-extractor-4

第四步:抽取器发现 z 没有问题之后,发动超能力,将时间倒回第二步之前

schnorr-extractor-5

第五步:抽取器再次发送一个不同的随机挑战数 c'给 Alice,这时候 Alice 回到第二步,会有一种似曾相识的感觉,但是无法感知到时间倒回这个事实

schnorr-extractor-6

第六步:Alice 再次计算了 z',然后发给抽取器检查

schnorr-extractor-7

第七步:这时候抽取器有了zz',就可以直接推算出 Alice 所拥有的私钥 a,达成「知识抽取」

到这里,「可靠性」就基本证明完了。大家是不是对可靠性和零知性的「对称性」有点感觉了?

总结一下:「抽取器」在「理想世界」中,通过时间倒流的超能力,把 Alice 的「知识」完整地「抽取」出来,这就保证了一个没有知识的 Alice 是无法让抽取器达成目标,从而证明了「可靠性」。

注:并不是所有的可靠性都必须要求存在抽取器算法。采用抽取器来证明可靠性的证明系统被称为「Proof of Knowledge」。

解读 ECDSA 签名攻击

在区块链系统中到处可见的ECDSA 签名方案也是一个朴素的零知识证明系统。椭圆曲线数字签名方案 ECDSA 与 Schnorr 协议非常接近,基于 Schnorr 协议的签名方案发表在 1991年的『密码学杂志』[5]上。1991年,正值美国国家标准局(NIST)选择数字签名算法,优雅的 Schnorr 签名方案居然被申请了专利,因此 NIST 提出了另一套签名方案 DSA(Digital Signature Algorithm),随后这个方案支持了椭圆曲线,于是被称为 ECDSA。中本聪在构思比特币时,选择了 ECDSA 作为签名算法,但是曲线并没有选择 NIST 标准推荐的椭圆曲线 —— secp256-r1,而是 secp256-k1。因为江湖传言,NIST 可能在椭圆曲线参数选择上做了手脚,导致某些机构可以用不为人知的办法求解离散对数难题,从而有能力在「现实世界」中具备超能力。有不少人在怀疑,也许当年中本聪在设计比特币时,也有这种考虑,故意选择了 secp256-k1 这样一条貌似安全性稍弱的曲线。

我们拆解下 ECDSA 签名,用交互的方式定义一个类似 ECDSA 的认证方案,交互见下图。

ecdsa-sig

第一步:Alice 仍然是选择一个随机数 k,并将 k 映射到椭圆曲线上,得到点 K ,然后发送给 Bob

第二步:Bob 需要产生两个随机数,ce,然后交给 Alice

第三步:Alice 计算 s,并且发送给 Bob,他来验证 s 的计算过程是否正确

注:对熟悉 ECDSA 签名方案的读者,这里略作解释,Bob 产生的 c 对应被签消息的 Hash 值 Hash(m),而 e 则是由一个转换函数 F(K)来产生。其中 F(.) 是取椭圆曲线上的点的 x 坐标经过 (mod q) 得到[6]。

江湖上流传着一个说法:ECDSA 签名方案有个严重的安全隐患,如果在两次签名中使用了同一个随机数,那么签名者的私钥将会暴露出来。其实 Schnorr 签名方案也有同样的问题。

当年 Sony PlayStation 3 的工程师在调用 ECDSA 库函数时,本来应该输入随机数的参数位置上,却传入了一个常数。熟悉密码学的黑客们发现了这个严重的后门。2011年1月,神奇小子 Geohot 公开发布了 Sony PS3 的主私钥,这意味着任何用户都可以轻松拿到游戏机的 root 权限。Sony 随后大为光火…… (后续故事大家可以上网搜)

如果 Alice 在两次交互过程中使用了同一个 K,那么 Bob 可以通过发送两个不同的 cc' 来得到 ss',然后通过下面的公式算出私钥 a

k = (c - c')/(s - s')
a = (k * s - c)/e

那么我们应该怎么来看这个「安全后门」呢?大家想想看,这个安全后门和我们前面证明过的 Schnorr 协议的可靠性证明几乎一模一样!这个算法正是 ECDSA 认证协议的「可靠性」证明中的「抽取器」算法。只不过在可靠性证明中,为了让 Alice 使用同一个随机数 k 来认证两次,「抽取器」需要利用「时间倒流」的超能力。

但是在 Sony PS3 系统中,随机数被不明所以的工程师写成了一个固定不变的值,这样相当于直接赋予了黑客「超能力」,而这是在「现实世界」中。或者说,黑客在不需要「时间倒流」的情况下就能实现「抽取器」。

提醒下,不仅仅是随机数不能重复的问题。而是随机数必须是具有密码学安全强度的随机数。

设想下,如果随机数 r 是通过一个利用「线性同余」原理的伪随机数生成器产生,虽然 r的值一直在变化,但是仍然不能阻止「知识抽取」。假设线性同余算法为 r2= d*r1 + e (mod m),还回到 Schnorr 协议的第三步:

1: z1 = r1 + c1*a
2: z2 = r2 + c2*a

如果攻击者让 Alice 连续做两次签名,那么将 r2 代入 r1 之后,就出现了两个线性方程求解两个未知数 (r1, a) 的情况,z1, z2, c1, c2, d, e 对于 攻击者是已知的,这个方程组只用初中数学知识就可以求解。

请注意,这并不是 Schnorr 协议(或 ECDSA 协议)的「设计缺陷」,恰恰相反,这是 Schnorr 协议设计比较精巧的地方,它从原理上保证了协议的可靠性。类似技巧在密码学协议中频繁出现,达到一目了然的「简洁」。但是也不得不说,如果不清楚协议的内在机制,尤其是区分不清楚「理想世界」与「现实世界」,使用者很容易引入各种花式的「安全漏洞」。

作为一个能写出可靠软件的靠谱码农,我们需要了解哪些?彻底理解安全协议的设计机制当然是最好的,但是绝大多数情况下是非常耗费精力的。一般来说,我们把各种密码学工具当做「黑盒」来用,可能是不够的,我们最好还能了解下:

  1. 「安全定义」是什么?
  2. 「安全假设」到底是什么?
  3. 「理想世界」中的「超能力」到底是什么?

脑洞:我们生活在模拟世界中吗

第一次读懂「模拟器」时,我第一时间想到的是电影『黑客帝国』。我们生活所在「现实世界」也许是某一个模拟器模拟出来的「理想世界」,我们所看到、听到的以及感知到的一切都是被「模拟」出来的。在「现实世界」里,我们活在一个母体中。然而我们并不能意识到这一点。

早在春秋战国时期,庄子也在思考类似的问题:

昔者庄周梦为胡蝶,栩栩然胡蝶也,自喻适志与,不知周也。俄然觉,则蘧蘧然周也。不知周之梦为胡蝶与,胡蝶之梦为周与?周与胡蝶,则必有分矣。此之谓物化。——《庄子·齐物论》

通俗地解释下:庄子有一天睡着了,梦见自己变成了一只蝴蝶,翩翩起舞,醒来之后发现自己还是庄子,在梦中,蝴蝶并不知道自己是庄子。于是庄子沉思到底是他梦中变成了蝴蝶,还是蝴蝶梦中变成了庄子呢?如果梦境足够真实,……

「缸中之脑」是美国哲学家 Gilbert Harman 提出的这样一个想法:一个人的大脑可以被放入一个容器里面,然后插上电线,通过模拟各种电信号输入,使得大脑以为自己活在真实世界中。

这个想法源自哲学家笛卡尔的《第一哲学沉思集》[7],在书中他论证我们应该怀疑一切,需要逐一检验所有人类的知识,数学,几何,以及感知到的世界。然而他发现除了「我思故我在」之外,所有的知识都可能不靠谱,因为我们的大脑很可能被一个具有「超能力」的 Evil Demon 所欺骗。

2003 年牛津大学的哲学教授 Nick Bostrom 郑重其事地写了一篇论文『我们生活在计算机模拟世界中吗?』[8]。认为以下三个事实中,至少有一个成立:

  1. 人类文明彻底灭绝。
  2. 人类文明已经到达可以完全模拟现实世界的科技水平,但是处于某种原因,没有一个人愿意去创造出一个新的模拟世界,充当上帝的角色。
  3. 我们现在的人类文明就生活在一个模拟世界中。

硅谷企业家 Elon Musk 在一次公开采访中,谈到「我们生活在基础现实世界」的概率只有「十亿分之一」。也就是说,他认为我们生活在一个电脑游戏(模拟世界)中,在模拟世界之外,有一个程序员,他开发并操纵了这个世界,我们每个人都是一个游戏角色( NPC)。

在玩腻越狱 iPhone 和自动驾驶之后,神奇小子 Geohot 在今年三月份的「西南偏南」大会上做了一个题为「Jailbreaking the Simulation」的演讲[9]。他认为,我们被生活在一个模拟世界中,所谓的上帝就是外部世界里活蹦乱跳的码农们,他们编程创造了我们的「现实世界」,当然,他们可能启动了不止一个世界副本。然而,他们可能也生活在一个外层「模拟世界」中。

Jailbreaking the Simulation

如果我们确实生活在模拟世界中,或许我们可以在地球的某个地方找到一个后门——「Simulation Trapdoor」,从而获得「模拟器」的超能力,抽取出不可思议的「秘密知识」。

如果我们的世界的确是被程序模拟出来的,这个程序也许会有 Bug,如果有 Bug 存在,说不定我们可以利用这个 Bug 进行越狱,跳出「理想世界」,到达外面一层的世界中,与可爱的码农上帝聊一聊。

这是在开玩笑吗?下面摘自自知乎的一个段子[10]:

  • 问题:「如果世界是虚拟的,有哪些实例可以证明?」。
  • 回答:
  1. 为什么宏观上丰富多彩,但是微观的基本粒子却都是一模一样的?这正和图片富多彩,但是像素是一模一样的一回事
  2. 为什么光速有上限?因为机器的运行速度有限
  3. 为什么会有普朗克常量?因为机器的数据精度有限
  4. 为什么微观粒子都是几率云?这是为了避免系统陷入循环而增加的随机扰动
  5. 为什么有泡利不相容原理?看来系统采用的数据组织是多维数组
  6. 为什么量子计算机运行速度那么快,一瞬间可以尝试所有可能?因为这个本质上是调用了宿主机的接口
  7. 为什么会有量子纠缠?这实际上是引用同一个对象的两个指针
  8. 为什么会有观察者效应?这显然是lazy updating
  9. 为什么时间有开端?系统有启动时间

未完待续

设计一个密码学协议就好像在走钢丝,如果你想同时做到「零知识」和「可靠性」就意味着既要让协议内容充分随机,又要保证「知识」能够参与协议的交互。如果协议没有正确设计,亦或没有正确工程实现,都将导致系统安全性坍塌。比如可能破坏了零知性,导致「知识」在不经意间泄露;或者也许破坏了可靠性,导致任何人都能伪造证明。而且这种安全性,远比传统的代码底层机制漏洞来得更加严重,并且更难被发现。严格数学论证,这似乎是必不可少的。

我们的世界真的是某个「三体文明」模拟出来的吗?不能排除这个可能性,或许,我们需要认真地重新审视自己的各种执念。不过那又怎么样呢?至少自己的「思想」是真实的。

If you would be a real seeker after truth, it is necessary that at least once in your life you doubt, as far as possible, all things. 如果你是一个真正的真理探求者,在你人生中至少要有一次,尽可能地质疑所有的事情。 —— 笛卡尔

致谢:特别感谢 Shengchao Ding, Jie Zhang,Yu Chen 以及安比实验室小伙伴们(p0n1, even, aphasiayc, Vawheter, yghu, mr)的建议和指正。

参考文献

  • [1] zkPoD: 区块链,零知识证明与形式化验证,实现无中介、零信任的公平交易. 安比实验室. 2019.
  • [2] Hoffstein, Jeffrey, Jill Pipher, Joseph H. Silverman, and Joseph H. Silverman. An introduction to mathematical cryptography. Vol. 1. New York: springer, 2008.
  • [3] Schwartz–Zippel Lemma. Wikipedia. https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma
  • [4] Damgård, Ivan. “On Σ-protocols.” Lecture Notes, University of Aarhus, Department for Computer Science (2002).
  • [5] Schnorr, Claus-Peter. “Efficient signature generation by smart cards.” Journal of cryptology 4.3 (1991): 161-174.
  • [6] Brown, Daniel RL. “Generic groups, collision resistance, and ECDSA.” Designs, Codes and Cryptography 35.1 (2005): 119-152.
  • [7] 笛卡儿, 徐陶. 第一哲学沉思集. 九州出版社; 2008.
  • [8] Bostrom, Nick. “Are we living in a computer simulation?.” The Philosophical Quarterly 53.211 (2003): 243-255.
  • [9] Nick Statt. “Comma.ai founder George Hotz wants to free humanity from the AI simulation”. Mar 9, 2019. https://www.theverge.com/2019/3/9/18258030/george-hotz-ai-simulation-jailbreaking-reality-sxsw-2019
  • [10] doing@知乎. “如果世界是虚拟的,有哪些实例可以证明?”. 2017. https://www.zhihu.com/question/34642204/answer/156671701

随机「挑战」

探索零知识证明系列(四)

“Challenges are at times an indication of Lord’s trust in you.” 挑战,有时是上天信任你的一种表现。― D. Todd Christofferson

本文继续长篇大论零知识证明背后的机制原理,希望帮助大家理解这一类「现代密码学工具」的大致轮廓。本文约8000字,少量数学公式。

交互与挑战

我们之前介绍的零知识证明系统都是「交互式」的,需要验证者 Bob 在交互中提供一个或若干个「随机数」来挑战,比如「地图三染色问题」(参看『系列二』)中,验证者 Bob 需要「不断地」随机挑选一条边来挑战 Alice 的答案,直到 Bob 满意为止,而 Alice 的作弊概率会「指数级」地衰减。而让 Bob 相信证明的「基础」取决于 Bob 所挑选的随机数是不是足够随机。如果 Alice 能够提前预测到 Bob 的随机数,灾难就会发生,现实世界就会退化成「理想世界」,而 Alice 就可以立即升级成「模拟器」,通过超能力来愚弄 Bob。

而『系列三』中,我们分析了 Schnorr 协议,协议中虽然验证者 Bob 只需要挑选一个随机数 c 来挑战 Alice ,让她计算一个值 z,但 Bob 绝对不能让 Alice 有能力来预测到 c 的任何知识,否则,Alice 也会变身成模拟器。

随机数的重要性不言而喻:

通过随机数挑战是交互式零知识证明的「信任根基」。

但,「交互过程」会限制应用场景。如果能将交互式零知识证明变成「非交互」?这会非常非常激动人心。所谓的非交互可以看成是只有「一轮」的证明过程,即Alice 直接发一个证明给 Bob 进行验证。

非交互式零知识证明,英文是 Non-Interactive Zero Knowledge,简称 NIZK。它意味整个证明被编码为一个「字符串」,它可以写到一张纸上,通过邮件、聊天工具等各种方式随意发送给任何验证者,字符串甚至可以放在 Github 上随时供大家下载验证。

在区块链世界,「NIZK」可以作为共识协议的一部分。因为一个交易需要多个矿工进行校验。设想下,如果交易的发送者和每个矿工都要交互一下,让矿工进行挑战,那么共识过程将奇慢无比。而非交互式零知识证明则可以直接广播给所有的矿工节点,让他们自行验证。

可能有朋友会问:只让一个矿工挑战不就够了吗?把矿工和交易发送者的交互脚本编码成证明,然后广播给其他矿工,然后其他矿工就直接相信这个挑战过程是可信的,不也可以吗?但是,很显然,这里需要相信第一个交互矿工作为可信第三方,第三方?似乎不是一个好主意……

而非交互式零知识证明,以下我们直接说「NIZK」,似乎就很理想了,没有第三方赚差价。

「非交互」带来的困惑

非交互式零知识证明,NIZK,如果存在,那么它要比交互式证明强大得多。

  • 交互式证明,只能取信于一个验证者;而 NIZK 可以取信于多个验证者,以至所有人。
  • 交互式证明,只能在交互的那个时刻有效;而 NIZK 将始终有效。

NIZK 不仅可以跨越空间,还能跨越时间

听上去很美,不是吗?But, ……

重复下上节的一个结论:

通过随机数挑战是交互式零知识证明的「信任根基」。

可是如果 NIZK 失去了挑战过程,有什么后果?

我们已经回忆过「零知识」性质的证明(参考『系列二』),证明过程需要构造一个模拟器(算法),它也和验证者(Bob)在理想世界中进行交互,而验证者 Bob 没有能力区分出来对方是否是真的 Alice 还是一个模拟器。

如果现在考虑下 NIZK 中的 非交互式,假如「我」向「你」出示一张纸,上面写着一个「真」证明 X ,又假如「你」在看过这张纸之后确实相信我了;又因为协议是「零知识」,那么如果把「我」换成一个模拟器,模拟器也能「伪造」一个假证明 Y,能够也让「你」相信。

好了,问题来了:

  • 你如何区分 XY ,孰真孰假?当然你无法区分,因为协议是零知识的,你必须不能区分
  • 我可以同样可以把 Y 出示给你看,那岂不是「我」就可以欺骗你了吗?

是不是不和谐了?请大家在此处思考两分钟。

(两分钟后……)

因为 NIZK 没有了交互,也就没了挑战过程,所有的证明过程都有 Alice 来计算书写,理论上 Alice 确实是想写什么就写什么,没人拦得住,比如 Alice 就写「理想世界」的 假证明 Y

想必深刻理解模拟器的朋友,在这里会发现一个关键点:模拟器必须只能在「理想世界」中构造Y,也就是说,Y 这么邪恶的东西只能存在于「理想世界」,不能到「现实世界」祸害人间。

继续思考……

还有一个更深层次的问题,请大家回忆下「地图三染色问题」,之所以模拟器不能在「现实世界」中为非作歹,核心原因是,他在理想世界中有「时间倒流」的超能力,而在「现实世界」中不存在这种黑魔法。现实世界的「不存在性」是关键。

而且,NIZK 中没有交互,于是导致了一个严重的后果,模拟器没有办法使用「时间倒流」这个超能力,当然似乎也就不能区分证明者在两个世界中的行为。

换句话说,如果我们面对任何一个 NIZK 系统,似乎「模拟器」就很难高高在上了,它好像只能飘落人间,成为一个普普通通的凡人。如果,我说如果,按此推论,假设模拟器不再具备超能力,那就意味着 Alice 和模拟器没有区别,Alice 也可以成为一个模拟器,再继续推论,Alice 就可以在「现实世界」中任意欺骗 Bob,那么这个证明系统就不再有价值,因为它失去了「可靠性」。结论:任何的 NIZK 都不可靠。

这一定是哪里出了问题……

上面我们在分析的过程中,提到了交互挑战的缺失。确实,如果 Bob 不参与 Alice 产生证明的过程,证明所包含的每一个 bit 都由 Alice 提供,似乎「证明」本身不存在任何让 Bob 信任的「根基」。这个从「直觉」上似乎说不通。

那是不是说,没有 Bob 的参与就「彻底」没办法建立「信任根基」了呢?信任的根基还可以从哪里来呢?

答案是「第三方」!

Wait ……,协议交互不是只有两方吗? Alice 和 Bob,哪来第三方?

需要用特殊的方式引入第三方,而且方法不止一种,我们先研究第一种。

(泪目:不是说的好好的,咱们不引入第三方吗?)

回顾 Schnorr 协议

我们再看一下老朋友——Schnorr 协议,它是一个三步协议:第一步,Alice 发送一个承诺,然后第二步 Bob 发送随机数挑战,第三步,Alice 回应挑战。

我们来看,如何把一个三步的 Schnorr 协议变成一步。

看一下 Schnorr 协议的第二步,Bob 需要给出一个随机的挑战数 c,这里我们可以让 Alice 用下面这个式子来计算这个挑战数,从而达到去除协议第二步的目的。

c = Hash(PK, R)

其中 R 是 Alice 发给 Bob 的椭圆曲线点,PK 是公钥。大家可以好好看看这个利用 Hash 算法计算 c 的式子。这个式子达到了两个目的:

  1. Alice 在产生承诺 R 之前,没有办法预测 c,即使 c 最终变相是 Alice 挑选的
  2. c 通过 Hash 函数计算,会均匀分布在一个整数域内,而且可以作为一个随机数(注:请大家暂且这么理解,我们在后文再深入讨论

请注意:Alice 绝不能在产生 R 之前预测到 c,不然, Alice 就等于变相具有了「时间倒流」的超能力,从而能任意愚弄 Bob。

而一个密码学安全 Hash 函数是「单向」的,比如 SHA256,SHA3,blake2 等等。这样一来,虽然 c 是 Alice 计算的,但是 Alice 并没有能力实现通过挑选 c 来作弊。因为只要 Alice 一产生 Rc 就相当于固定下来了。我们假设 Alice 这个凡人在「现实世界」中是没有反向计算 Hash 的能力的。

schnorr-nizk

看上图,我们利用 Hash 函数,把三步 Schnorr 协议合并为了一步。Alice 可以直接发送:(R, c, z)。又因为 Bob 拥有 PK,于是 Bob 可以自行计算出 c,于是 Alice 可以只发送 (R, z) 即可。

我们把上面这个方案稍微变下形,就得到了「数字签名」方案。所谓的数字签名,就是「我」向「你」出示一个字符串,比如「白日依山尽,黄河入海流」,然后为了证明这句诗是我出示的,我需要签署某样东西。这个东西能证明我的身份和这句诗进行了关联。

从 NIZK 角度看数字签名

不严格地说,数字签名方案相当于在证明(1)我拥有私钥,并且(2)私钥和消息进行了关联计算。

我首先要证明我的身份,那么这个简单,这正是 Schnorr 协议的功能,能够向对方证明「我拥有私钥」这个陈述。并且这个证明过程是零知识的:不泄露关于「私钥」的任何知识。

那么如何和这句唐诗关联呢?我们修改下计算 c 的过程:

m = "白日依山尽,黄河入海流"
c = Hash(m, R)

这里为了保证攻击者不能随意伪造签名,正是利用了离散对数难题(DLP)与 Hash 函数满足抗第二原象(Secondary Preimage Resistance )这个假设。

注:这里严格点讲,为了保证数字签名的不可伪造性,需要证明 Schnorr 协议满足「Simulation Soundness」这个更强的性质。这点请参考文献[2]

上图就是大家所熟知的数字签名方案 —— Schnorr 签名方案[1]。在这里还有一个优化,Alice 发给 Bob 的内容不是 (R, z) 而是 (c, z),这是因为 R 可以通过 c, z 计算出来。

注:为什么说这是一个「优化」呢?目前针对椭圆曲线的攻击方法有 Shanks 算法、Lambda 算法 还有 Pollard’s rho 算法, 请大家记住他们的算法复杂度大约都是 [3],n 是有限域大小的位数。假设我们采用了非常接近 2^256 的有限域,也就是说 z 是 256bit,那么椭圆曲线群的大小也差不多要接近 256bit,这样一来,把 2^256 开平方根后就是 2^128,所以说 256bit 椭圆曲线群的安全性只有 128bit。那么,挑战数 c 也只需要 128bit 就足够了。这样 Alice 发送 c 要比发送 R 要更节省空间,而后者至少需要 256bit。cz两个数值加起来总共 384bit。相比现在流行的 ECDSA 签名方案来说,可以节省1/4 的宝贵空间。现在比特币开发团队已经准备将 ECDSA 签名方案改为一种类 Schnorr 协议的签名方案——muSig[4],可以实现更灵活地支持多签和聚合。

而采用 Hash 函数的方法来把一个交互式的证明系统变成非交互式的方法被称为 Fiat-Shamir 变换[5],它由密码学老前辈 Amos Fiat 和 Adi Shamir 两人在 1986 年提出。

重建信任 —— 随机预言精灵

前文提到,失去了挑战,似乎失去了证明的「信任根基」。而在 Schnorr 签名方案中,Hash 函数担负起了「挑战者」的角色,这个角色有一个非常学术的名字:「随机预言机」(Random Oracle)[6]。

可是这里为何用 Hash?实际上当 Alice 要产生公共随机数时,需要一个叫做「随机预言机」的玩意儿,这是什么?

开脑洞时间到!

我们设想在「现实世界」中,天上有一位「精灵」,他手持一个双栏表格,左边一栏为字符串,右边一栏为数字。任何人,包括你我,包括 Alice 和 Bob,都可以发字符串给「精灵」。

精灵在拿到字符串之后,会查表的左边栏,看看表格里有没有这个字符串,下面分两种情况:

  • 情况一:如果左边栏找不到字符串,那么精灵会产生一个「真随机数」,然后把字符串与随机数写入到表格中,然后把随机数返回地面上的凡人。
  • 情况二:如果左边栏有这个字符串记录,那么精灵会将右边栏里面的数字直接返回给地面。

大家会发现这个精灵的行为其实很像一个随机数发生器,但是又很不一样,不一样的地方在于当我们发送相同的字符串时,他会返回相同的数。这个精灵就是传说中的「随机预言机」。

而在合并 Schnorr 协议过程中,其实我们需要的是一个这样的随机预言精灵,而不是一个 Hash 函数。两者有什么不同的地方?区别就是:

  • 随机预言机每次对于新字符串返回的是一个具有一致性分布的「真」随机数
  • Hash 函数计算的结果并不是一个真正具有一致性分布的随机数

那么为什么前面用的是 Hash 函数呢?这是因为在现实世界中,**真正的随机预言机不存在!**为什么呢? 事实上,一个 Hash 函数不可能产生真的随机数,因为 Hash 函数是一个「确定性」算法,除了参数以外,再没有其它随机量被引入。

而一个具有密码学安全强度的 Hash 函数「似乎」可以充当一个「伪」随机预言机。那么合并后的安全协议需要额外增加一个很强的安全假设,这就是:

假设:一个密码学安全的 Hash 函数可以近似地模拟传说中的「随机预言机」

因为这个假设无法被证明,所以我们只能信任这个假设,或者说当做一个公理来用。插一句, Hash 函数的广义抗碰撞性质决定了它的输出可以模拟随机数,同时在很多情况下(并非所有),对 Hash 函数实施攻击难度很高,于是许多的密码学家都在大胆使用。

不使用这个假设的安全模型叫做「标准模型」,而使用这个假设的安全模型当然不能叫「非标准模型」,它有个好听的专有名词,叫做「随机预言模型」。

世界上有两种不同类型的人,喜欢甜豆花的,不喜欢甜豆花的。同样,世界上的密码学家分为两种,喜欢随机预言模型的,和不喜欢随机预言模型的[6]。

构造根基 —— 被绑架的精灵

Schnorr 协议经过 Fiat-Shamir 变换之后,就具有 NIZK 性质。这不同于我们证明过的 SHVZK,SHVZK 要求验证者诚实,而 NIZK 则不再对验证者有任何不现实的要求,因为验证者不参与交互,所谓要求诚实的验证者这个问题就不复存在。

注:如果验证者 Bob 不诚实会怎样?那么 Bob 有可能抽取出 Alice 的知识。但是对于三步 Schnorr 协议而言,它是否满足「零知识」,目前还处于未知状态。我们在系列三中只证明了它满足一个比较弱的性质:SHVZK

但是,当 Schnorr 协议摇身一变,变成非交互零知识证明系统之后,就真正的「零知识」了。

然而,可能你的问题也来了,这个论断听起来似乎有道理,请问能证明吗?

时间到了,“翠花,上模拟器”

怎么用模拟器大法来构造一个「理想世界」呢?大家可以想一下,我们之前使用过「时间倒流」,还有修改「随机数传送带」超能力来让「模拟器」来作弊。可是没有交互了,这就意味着:「时间倒流」超能力不能用;Bob 的随机数传送带也不存在了,「篡改传送带」这个超能力也不能用!

但模拟器总要具备某种「超能力」,从而能够构建信任的「根基」

(如果模拟器在没有超能力的情况下具备作弊能力,那相当于证明了协议的不可靠性)。

可能大家现在已经猜出来了,模拟器要在「随机预言机」上动手脚。

先考虑下构造一个「理想世界」来证明「零知识」。在理想世界中,模拟器「绑架」了负责提供预言的「精灵」,当 Bob 向精灵索要一个随机数的时候,精灵并没有给一个真随机数,而是给 Zlice(模拟器假扮的 Alice)提前准备好的一个数(也符合一致性分布,保证不可区分性),「精灵」无可奈何地返回 Bob 一个看起来随机,但实际上有后门的数字。所谓后门,就是这个数字是 Zlice 自己提前选择好的

  • 第一步:Zlice 随机选择 z,随机选择c,计算 R'=z*G - c*PK

  • 第二步:Zlice 将 c(m, R') 写入精灵的表格。

  • 第三步:Zlice 将签名 (c, z) 发送给 Bob。

  • 第四步:Bob 计算 R=z*G - c*PK,并向精灵发送 (m, R),精灵返回 c’。请注意,这里 Bob 计算出来的 R 和 Zlice 计算出来的 R' 是相等。

  • 第五步:Bob 验证 c ?= c',看看精灵传回来的随机数和对方发过来的随机数是否相等。如果相等,则验证签名通过;否则,则验证失败。

通过绑架「精灵」,Zlice 同样可以提前预知随机数,这和时间倒流能达到同样的效果。

我们已经证明了模拟器 Zlice 的「存在性」,于是我们上面已经证明了 NIZK。

接下来我们证明这个这个协议的「可靠性」。设想在另一个「理想世界」中,一个叫做「抽取器」的玩意儿,也同样绑架了精灵。当无辜 Alice 的向「精灵」索要一个随机数时,「精灵」返回了一个 c1,「抽取器」从精灵的表格中偷窥到了c1,当 Alice 计算出来 z1 之后,然后这时候「抽取器」仍然可以发动「时间倒流」超能力,让 Alice 倒退到第二步,再次向「精灵」要一个随机数,Alice 发送的字符串显然和第一次发送的字符串是相同的,(R, m)。按道理,因为 (R, m) 已经写在精灵表格的「左栏」里,所以一个诚实的「精灵」应该返回 c1。但是,「抽取器」绑架了精灵,他把表格中对应 (R, m) 这一行的「右栏」改成了一个不同的数 c2。当 Alice 计算出另一个 z2 之后,抽取器就完成了任务,通过下面的方程计算出 Alice 的私钥 sk

sk = (z1 - z2)/(c1 - c2)

Fiat-Shamir 变换 —— 从 Public-Coin 到 NIZK

不仅仅对于 Schnorr 协议,对于任意的 「Public-Coin 协议」,都可以用 Fiat-Shamir 变换来把整个协议「压缩」成一步交互,也就是一个非交互式的证明系统,这个变换技巧最早来自于 Amos Fiat 与 Adi Shamir 两人的论文『How to Prove Yourself: Practical Solutions to Identification and Signature Problems.』,发表在 1986 年的 Crypto 会议上[5]。也有一说,这个技巧来源于 Manuel Blum[6].

重复一遍,在 Public-coin 协议中,验证者 Bob 只做一类事情,就是产生一个随机数,然后挑战 Alice 。通过 Fiat-Shamir 变换,可以把 Bob 每一次的「挑战行为」用一次「随机预言」来代替。

而在具体实现中,随机预言需要用一个具有密码学安全强度的 Hash 函数(不能随便选,一定要采用密码学安全的 Hash),而 Hash 函数的参数应该是之前所有的上下文输入。下面是一个示例图,大家可以迅速理解这个 Fiat-Shamir 变换的做法。

前面提到,在非交互式证明系统中,需要引入一个第三方来构建信任的「根基」,使得 Bob 可以完全相信由 Alice 所构造的证明。在这里,第三方就是那个「精灵」,用学术黑话就是「随机预言」(Random Oracle)。这个精灵并不是一个真实存在的第三方,而是一个虚拟的第三方,它同时存在于「现实世界」与「理想世界」。在「现实世界」中,精灵是一个负责任的安静美男子,而在「理想世界」中,它会被「模拟器」绑架。

Public-Coin 协议还有一个好听的名字, 「Arthur-Merlin 游戏」 ……

圆桌骑士

看上图,左边的“白袍”就是 Merlin(魔法师梅林),中间拿剑的帅哥就是 King Arthur(亚瑟王),两个角色来源于中世纪欧洲传说——亚瑟王的圆桌骑士。

Arthur 是一个不耐烦的国王,他随身携带一个硬币,而 Merlin是一个有着无限制计算能力的神奇魔法师,然后魔法师想说服国王相信某个「论断」为真,于是魔法师会和国王进行到对话,但是由于国王比较懒,他每次只会抛一个硬币,然后「挑战」魔法师,而魔法师需要及时应对,而且需要让国王在 k 轮之后能够相信自己的论断。由于 Merlin 有魔法,所以亚瑟王抛的硬币都能被 Merlin 看到[7]。

这与我们在『系列一』中提到的交互式证明系统(Interactive Proof System,简称 IP)有些神似,但又不同。IP 由 Goldwasser,Micali 与 Rackoff(简称GMR)在 1985 年正式提出,它的证明能力覆盖很大一类的计算复杂性问题。而不同的地方在于:在 IP 的定义中,证明者 Prover 和 验证者 Verifier 都是可以抛硬币的图灵机,Verifier 可以偷偷抛硬币,并对 Prover 隐藏;而在 Arthur-Merlin 游戏中,国王只能抛硬币,不仅如此,而且抛硬币的结果总会被 Merlin 知道。

但是,Fiat-Shamir 变换只能在「随机预言模型」下证明安全,而用 Hash 函数实现随机预言的过程是否安全是缺少安全性证明的。不仅如此,「随机预言模型」下安全的协议可能是有不安全的,已经有人找到了一些反例[8];更不幸的是,S. Goldwasser 与 Y. Tauman 在 2003 年证明了 Fiat-Shamir 变换本身也是存在安全反例的[9]。但是这并不意味着 Fiat-Shamir 变换不能用,只是在使用过程中要非常小心,不能盲目套用。

尽管如此,人们无法抵挡 Fiat-Shamir 变换的诱惑,其使用极其广泛。值得一提的是,最热的通用非交互零知识证明 zkSNARK 的各种方案中,Fiat-Shamir 变换比比皆是。比如大家可能耳熟能详的 Bulletproofs(子弹证明),此外还有一些暂时还不那么有名的通用零知识证明方案,比如 Hyrax,Ligero,Supersonic,Libra 等(我们后续会抽丝剥茧,逐一解读)。

小心:Fiat-Shamir 变换中的安全隐患

在 Fiat-Shamir 变换中,要尤其注意喂给 Hash 函数的参数,在实际的代码实现中,就有这样的案例,漏掉了 Hash 函数的部分参数:

比如在 A, Hash(A), B, Hash(B) 中,第二个 Hash 函数就漏掉了参数A,正确的做法应该是A, Hash(A), B, Hash(A,B) 。这一类的做法会引入严重的安全漏洞,比如在瑞士的电子投票系统 SwissPost-Scytl 中,就在 Fiat-Shamir 变换的实现代码中多次漏掉了本来应该存在的参数,导致了攻击者不仅可以随意作废选票,还可以任意伪造选票,达到舞弊的目的[10]。因此在工程实现中,请务必注意。

细心读者也许会回看一下 Schnorr 签名,大家会发现 Schnorr 签名中的 Hash 算法似乎也漏掉了一个参数 PK,并不是严格的 Fiat-Shamir 变换,这被称为 Weak Fiat-Shamir 变换[11],不过这个特例并没有安全问题[3],请未成年人不要随意模仿。

最近一些学者开始在标准模型下研究如何严格证明 Fiat-Shamir 变换的安全性,目前要么引入额外的强安全假设,要么针对某个特定协议进行证明,但似乎进展并不大。

交互的威力

话说在1985年,当 GMR 三人的论文历经多次被拒之后终于被 STOC’85 接受,另一篇类似的工作也同时被 STOC’85 接受,这就是来自于匈牙利罗兰大学的 László Babai,与来自以色列理工的 Shlomo Moran 两人撰写的论文『Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes』[7],引入了 Public-coin 交互式协议(顾名思义,Verifier 只公开抛硬币)。

国王 Arthur 的方法很简单,通过反复地「随机」挑战来检验 Merlin 的论断,这符合我们前面讲述过的直觉:采用随机挑战来构建信任的「根基」。Babai 在论文中证明了一个有趣的结论:AM[k]=AM[2],其中 k 表示交互的次数,交互多次产生的效果居然和交互两次等价。所谓交互两次是指:Arthur 发一个挑战数,然后 Merlin 回应。

注:还有一类的问题属于 MA,这一类问题的交互顺序与 AM不同,MA中是 Merlin 先给出证明,然后 Arthur 抛硬币检验。已证明:MA 能处理的问题是 AM 的子集。

不仅如此,Babai 还大胆猜测: AM[poly]IP 是等价的。这是一个神奇的论断:国王很懒,他只需要通过抛多项式次硬币,就能成功挑战魔法师,而这种方式的表达能力居然完全等价于 GMR 描述的交互式证明系统 IP。果不其然,在 STOC’86 会议上,来自 S. Goldwasser 与 M. Sipser 的论文证明了这一点,AM[poly] == IP[12]。

这意味着:反复公开的「随机挑战」威力无穷,它等价于任意的交互式证明系统。但是 AM[poly] 和别的计算复杂性类的关系如何,是接下来的研究热点。

三年后,1989 年11月底,距今恰好三十年,年轻的密码学家 Noam Nisan 发出了一封邮件,把自己的临时学术结论发给了几个密码学家,然后他就跑去南美洲度假了。可是他不曾想到,这一个邮件会引爆历史上一场激烈的学术竞赛,M. Blum, S. Kannan, D. Lipton, D. Beaver, J. Feigenbaum, H. Karloff, C. Lund 等等一大群精英开始加入战斗,他们没日没夜地互相讨论,并且竞相发布自己的研究成果,终于在12月26号,刚好一个月,Adi Shamir 证明了下面的结论:

AM[poly] == IP == PSPACE

image-shamir

它解释了「有效证明」这个概念的计算理论特征,并且解释了「交互式证明系统」这个概念所能涵盖的计算能力。

注:NP 类 是 PSPACE 类的子集,前者大家比较熟悉,后者关联游戏或者下棋中的制胜策略[13]。

而 L. Babai 于是写了一篇文章,名为「Email and the unexpected power of interaction」(电子邮件与交互的始料未及的威力)[14],详细阐述了这一整个月在「邮件交互」中精彩纷呈的学术竞赛,以及关于「交互证明」的来龙去脉。

公共参考串 —— 另一种「信任根基」

除了采用「随机预言机」之外,非交互零知识证明系统采用「公共参考串」(Common Reference String),简称「CRS」,完成随机挑战。它是在证明者 Alice 在构造 NIZK 证明之前由一个受信任的第三方产生的随机字符串,CRS 必须由一个受信任的第三方来完成,同时共享给 Alice 和 验证者 Bob。

是的,你没看错,这里又出现了「第三方」!虽然第三方不直接参与证明,但是他要保证随机字符串产生过程的可信。而产生 CRS 的过程也被称为「Trusted Setup」,这是大家又爱又恨的玩意儿。显然,在现实场景中引入第三方会让人头疼。CRS 到底用来作什么?Trusted Setup 的信任何去何从?这部分内容将留给本系列的下一篇。

未完待续

非交互式零知识证明 NIZK 的「信任根基」也需要某种形式的随机「挑战」,一种「挑战」形式是交给「随机预言精灵」;另一种「挑战」是通过 Alice 与 Bob 双方共享的随机字符串来实现。两种挑战形式本质上都引入了第三方,并且两者都必须提供可以让「模拟器」利用的「后门」,以使得让模拟器在「理想世界」中具有某种「优势」,而这种优势在「现实世界」中必须失效。

NIZK 散发着无穷魅力,让我不时惊叹,在过去三十多年里,先驱们所探寻到的精妙结论,同时还有如此之多的未知角落,在等待灵感之光的照射。

本系列文章在 Github 上的项目仓库收到了第一个 Pull Request,来自Jingyu Hu(colortigerhu),只改了个把字,但那一瞬间,我感受到了生命力。知识交流,思想碰撞,很迷人,不是吗?

“Everyone we interact with becomes a part of us.” 与我们交往互动的每一个人都是我们自身的一部分。 ― Jodi Aman

致谢:特别感谢丁晟超,刘巍然,陈宇的专业建议和指正,感谢安比实验室小伙伴们(p0n1, even, aphasiayc, Vawheter, yghu, mr) 的修改建议。

致谢:自Nisan发起的密码学研究轶事参考自邓老师的文章[15]。

参考文献

  • [1] Schnorr, Claus-Peter. “Efficient signature generation by smart cards.” Journal of cryptology 4.3 (1991): 161-174.

  • [2] Paillier, Pascal, and Damien Vergnaud. “Discrete-log-based signatures may not be equivalent to discrete log.” International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2005.

  • [3] Pointcheval, David, and Jacques Stern. “Security arguments for digital signatures and blind signatures.” Journal of cryptology 13.3 (2000): 361-396.

  • [4] Maxwell, Gregory, Andrew Poelstra, Yannick Seurin, and Pieter Wuille. “Simple schnorr multi-signatures with applications to bitcoin.” Designs, Codes and Cryptography 87, no. 9 (2019): 2139-2164.

  • [5] Fiat, Amos, and Adi Shamir. “How to prove yourself: Practical solutions to identification and signature problems.” Conference on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1986.

  • [6] Bellare, Mihir, and Phillip Rogaway. “Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols.” Proc. of the 1st CCS (1995): 62-73.

  • [7] László Babai, and Shlomo Moran. “Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes.” Journal of Computer and System Sciences 36.2 (1988): 254-276.m

  • [8] Canetti, Ran, Oded Goldreich, and Shai Halevi. “The random oracle methodology, revisited.” Journal of the ACM (JACM)51.4 (2004): 557-594.

  • [9] Shafi Goldwasser, and Yael Tauman . “On the (in) security of the Fiat-Shamir paradigm.” 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. IEEE, 2003.

  • [10]Lewis, Sarah Jamie, Olivier Pereira, and Vanessa Teague. “Addendum to how not to prove your election outcome: The use of nonadaptive zero knowledge proofs in the ScytlSwissPost Internet voting system, and its implica tions for castasintended verifi cation.” Univ. Melbourne, Parkville, Australia (2019).

  • [11] Bernhard, David, Olivier Pereira, and Bogdan Warinschi. “How not to prove yourself: Pitfalls of the fiat-shamir heuristic and applications to helios.” International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2012.

  • [12] Goldwasser, Shafi, and Michael Sipser. “Private coins versus public coins in interactive proof systems.” Proceedings of the eighteenth annual ACM symposium on Theory of computing. ACM, 1986.

  • [13] Papadimitriou, Christos H. “Games against nature.” Journal of Computer and System Sciences 31.2 (1985): 288-301.

  • [14] Babai, László. “E-mail and the unexpected power of interaction.” Proceedings Fifth Annual Structure in Complexity Theory Conference. IEEE, 1990.

  • [15] Yi Deng. “零知识证明:一个略显严肃的科普.” https://zhuanlan.zhihu.com/p/29491567

埋藏「秘密」

Once exposed, a secret loses all its power. 一旦泄露,秘密就失去了全部威力 ― Ann Aguirre

这已经是本系列的第五篇文章了,这一篇继续深入非交互式零知识证明。 本文约 12,000 字。

提纲

  1. CRS 的前世今生
  2. 哈密尔顿环路问题
  3. 云中的秘密:Hidden Bits
  4. 升级随机性
  5. FLS变换:从 Hidden Bits 到 NIZK
  6. 寻找理想的 Trapdoor Permutation
  7. NIZK Proof vs. NIZK Argument
  8. 没有秘密的世界

追到这里的读者想必已对零知识证明有了一个大概的认识。你是否想过这个问题:零知识证明为何可行?这里请大家思考一下(比如系列一 中的地图三染色问题的流程) …… (此处停留三分钟)下面两个要素 似乎 必不可少:

  1. 「交互」:验证者通过多次反复挑战,把证明者作弊概率降低到一个极小的值
  2. 「隐藏随机性」:验证者产生让证明者无法预测的随机数进行挑战

然而对于非交互式零知识证明—— NIZK 来说,如何实现上面两点?在 系列四 我们介绍了如何采用「随机预言机」来扮演一个虚拟的「第三方」角色,实现虚拟的「交互」与「随机挑战」。本文将深入讲述另一种方法,如何通过一段共享的字符串去除「交互」与「隐藏随机性」。这个字符串必须事先由「第三方」来随机产生,这就是传说中的「公共参考串」(Common Reference String,简称 CRS)。

CRS 的前世今生

假如我们不借助任何其它手段,限定证明者 Prover 和验证者 Verifier 只能进行「一次交互」来实现「零知识证明」,那么他们只能证明「平凡」问题,也就是计算复杂类 BPPBounded-error Probabilistic Polynomial time),而这个复杂度类大家一般猜想可能等价于 P(但还悬而未决,没有被证明!BPP 可以理解为 P + Randomness)。

注:如果 Prover 与 Verifier 只做一次交互,在这样的 NIZK 系统中,我们很容易能构造一个 Decision Procedure —— Verify(x, Sim(x)),来证明和证伪定理,因此只能证明平凡问题 BPP。

平凡问题虽然也可以零知识证明,但没有意义!怎么理解呢?因为验证者直接可以在多项式时间内根据「输出」求解出「秘密输入」,虽然验证者能够求解,但是「证明」本身并没有额外为验证者提供更多的「知识」。换句话说,不需要证明者出示证明,验证者就知道命题为真,于是证明过程也是零知识的。

因此,当我们讨论「零知识证明」时,要考虑带「知识」的 NP 类问题。大家都知道,P 问题是「确定性图灵机」多项式时间内可以求解的复杂类,它的执行路径对于输入 x是一个线性的状态转移。而 NP 问题是「不确定性图灵机」多项式时间可以求解的问题类。所谓的不确定性图灵机,就是它每次往前走一步是不确定的,有很多个选择,只要任何一个执行路径能到达终止状态,就表示它解决了该问题 x。换句话说,它的执行轨迹是一棵树。那么如果我们把不确定性图灵机每一步的路径选择记录下来(这个执行路径的记录叫做 witness,也就是我们反复提到的「知识」),那么把(x, witness)交给一个确定性图灵机,那么它也能在多项式时间内解决掉 x 问题。

再强调一下,「知识」能提高图灵机的解决问题的能力。

NP 问题中存在着不想「泄露」给验证者的知识 witness,这时,在一个交互式证明系统中,证明者和验证者在「知识」的掌握程度上是不对等的。

为了保证证明过程的「零知识」,我们需要保证:模拟器与验证者的不对等。可是,模拟器没有 witness啊,怎么能让他们不对等呢?上一篇我们介绍了「随机预言机」,我们通过允许让模拟器可以绑架「随机预言精灵」的方式制造不平等。本篇将讲述如何利用 CRS 来制造不平等。

CRS 是一个在证明之前就已经公开的,并且在证明者与验证者之间共享的,随机字符串。我们怎么来使用 CRS 呢?直觉上,一串双方都「知道」的信息,并不会增加「知识」不对等的情况。

首先大家会想,能不能直接用 CRS 作为随机挑战数呢?可不可以让 CRS 来代替「随机预言精灵」的角色?答案是不行!

为什么?这是因为 CRS 是在证明之前就已经产生了,如果证明者 Prover 提前知道了所有的随机挑战数,那么很显然这个随机挑战也就失去了意义。

注:请大家回想下「随机预言机」是如何保证证明者无法提前预测「随机挑战数」的?没想明白的你,请重读系列(四)。

CRS 的使命就是让「模拟器」与「验证者」不平等。怎么做呢?隐藏一些「秘密」进去。

如果进一步追问,隐藏了「秘密」有什么用呢?当然有用啦,在「理想世界」中,模拟器与抽取器才能很开心地玩耍起来(获取某些超能力) ……

1988年,Manuel Blum,Paul Feldman 和 Silvio Micali 三位先驱发表的论文 「Non-Interactive Zero-Knowledge and Its Applications」(『非交互式零知识证明及其应用』[BFM88])展示了「交互」与「隐藏随机性」的不必要性。他们给出了一个地图三染色问题的 NIZK 证明系统,在一段共享的随机产生的字符串(即CRS)的帮助下。

不过,……,我不会告诉你这个方案需要共享大概 n^4 超长的 CRS,其中 n是要证明的「命题」的长度。

1990 年,Uriel Feige,Dror Lapidot 与 Adi Shamir 三人提出了另一种构造 NP 语言的 NIZK 方案 [FLS90]。与 [BFM88] 不一样的是,这个 NIZK 方案不再基于特定的数论假设,而是基于一个密码学工具 Trapdoor Permutation。在这个方案中,FLS 提出了「隐藏比特」(Hidden Bits)的概念,然后把 Hidden Bits 藏入了 CRS。对于模拟器而言,就可以通过修改 CRS 中的 Hidden Bits 来达到模拟的效果,从而体现出对验证者 Verifier 的优越性。不过,这个方案需要共享更长的 CRS,超过 k * n^5,这里 k 是安全参数。

此后,Hidden Bits 的思路被很多人采用,值得一提的是,Kilian 与 Petrank 采用了一种更巧妙的方法来使用 Hidden Bits [KP98](这里空间太小,写不下:),成功地把 CRS 的长度缩减到了 k * n^2。后来 J. Groth 继续优化 ,把 CRS 的长度缩小到了大约 k*n[Groth10a]。

除了 Hidden Bits,J. Groth,R. Ostrovsky 与 A. Sahai [GOS06] 使用了同态加密方案 Boneh-Goh-Nissim [BGN05] 或 Boneh-Boyen-Shacham 来实现 NIZK,他们把加密方案的「公钥」当做是 CRS,同时 Prover 加密作为证明,然后利用同态性质来证明另一个 NP-Complete 问题——布尔电路的可满足性问题。这个方案的最大优点,就是 CRS 长度是固定的,因为只是一个密钥而已,长度只有 k。对于模拟器而言,它可以通过超能力,拿到这个公钥所对应的陷门,从而能够实现密封任何信息,但得到相同的密文;对于抽取器而言,它可以用超能力拿到公钥对应的私钥,从而能够解密证明得到「知识」。

Jens Groth 在 2010 年基于 KEA(Knowledge of Exponent Assumption) 假设与 Pairing 提出了一种新的 NIZK Arguments 方案[Gorth10b],这也是后续许许多多 zkSNARKs 方案的起点。这里的 CRS 由一对对的 (g^x^n, g^⍺x^n) 构成,被用来实现「知识承诺」。其中 x 是两个随机数,在产生完 CRS 之后,必须被「遗忘」。有些人把这部分需要遗忘的随机数叫做「Toxic Wastes」,这容易误导读者。他们不仅无毒无害,而且非常有用。他们是被藏入 CRS 的「秘密」,是模拟器的武器。如果模拟器得到了 x,就能伪造证明,从而保证证明的零知识。而对于抽取器,他能直接通过 KEA 假设内建的抽取函数来抽取知识。

最新的 Sonic 方案[MBK+19]又在 [Groth10b] 的基础上实现了 Updateable CRS。如果任何人担心 CRS 中的秘密已经被泄露了,他就可以在原有 CRS 基础上打一个补丁,继续往里藏一个秘密,这样就能保证 CRS 的安全性。这里的 CRS 还是「Universal 全局」 的,即 CRS 只需要生成一次,就可以应付所有的命题证明。 这个方案后续被最新的 Plonk[GWC19],Marlin[CHMMVW19] 等方案采用。

接下来,我们就从一个简单的例子开始,理解如何基于 CRS 来构造 NIZK。在这之前,我们需要介绍一个 NP-Complete 问题——哈密尔顿环路问题。

哈密尔顿环路问题

想象出一个地图中有若干个城市,城市与城市间可以有公路。

假如给你一副地图,让你找出一条路径,不重复地走遍所有的公路(假设每条公路都是风景美如明信片的 Parkway,或许你想不重复地吃遍每条公路边上的麦当劳,出于某种情怀)。相信你会马上兴奋起来,这不就是小时候学过的「一笔画」么?判断一个地图能否一笔画,这是小学生做的数学题,我们可以计算每个城市连接的公路个数,根据奇偶性分成「奇点」与「偶点」。如果一个地图中存在两个奇点城市,那么你只能从一个奇点城市出发,遍历所有的公路,并且最终到达另一个奇点城市。这条路径就被称为「欧拉路径」(Euler’s Path)。

如果一个地图中所有的城市都是偶点,那么你可以从任意一个城市出发,轻松地找出一条路径,不重复地遍历所有的公路,并且回到起点。这个环路被称为「欧拉环路」(Euler’s Circuit)。

而如果地图存在超过2个以上的奇点,那么就不存在欧拉回路,比如著名的哥德斯堡七桥问题。

著名的哥德斯堡七桥问题就是这么描述,如果不重复地穿过下面七座桥。

哥德斯堡七桥地图显然存在多个奇点,不存在欧拉路径。如果给定任何一个地图,是否存在一个欧拉环路,这是一个 P 问题,也就是一个计算机可以在 poly(n) 多项式时间内寻找。

注:欧拉环路的寻找算法被称为 Fleury算法。

对于这样一个 P 问题, 如果一个证明者 Prover 证明他知道一个欧拉回路,那么他可以直接发送回路的明文,然后验证者 Verifier 验证回路正确与否。请注意,这个过程仍然是零知识的。因为,Verifier 并没有通过 Prover 发送的信息获得任何 额外的知识。换句话说,Verifier 并没有因为看到回路,而增强了自身计算能力,因为 Verifier 本来就可以自行计算欧拉回路。

而我们要讲的是「哈密尔顿环路问题」则是一个 NP 问题,描述如下:

是否一个地图存在一个环路,能不重复地穿过每一个城市

比如下面这张地图:

我们用一个矩阵 V * V 的矩阵来表示这个地图,凡是两个城市(A, B)有公路相连接,那么就在(A, B)(B, A)里面填上 1,否则填 0。这个矩阵被称为「邻接矩阵」,我们可以把这个邻接矩阵拍扁,就变成了一个 0/1 比特串。

寻找「哈密尔顿环路」是一个 NP-Complete 问题,换句话说,不存在一个算法使得计算机在 poly(n) 多项式时间内找到环路。但是,计算机可以在多项式时间内检验一个路径是否是「哈密尔顿环路」。比如这个地图中就有一个带方向的哈密尔顿环路,我们一眼就能验证这个环路确实穿过了每一个城市。如果一个地图有哈密尔顿环路,那么它的矩阵一定是满足下面的特征:每一行一定有一个1,每一列一定也有一个1

ZK-HAM 协议

我们下面给出一个三步交互的 Sigma 协议,Alice 向 Bob 证明她「知道」上面这个地图 G 的哈密尔顿环路。

  • 公共输入:G 为一个有 6 个顶点的地图,表示为一个 6*6 的邻接矩阵
  • 秘密输入:G的哈密尔顿环路 C(图中橙色的公路)

  • 第一步:Alice 随机选择一个「置换」,Perm(.),然后通过这个置换,产生一个新的图 G';然后 Alice 把G' 矩阵的每一个单元加密,产生一个新的矩阵发送给 Bob。

【名词解释】:所谓置换,大家可以想象成用 鼠标 随意拖动图中的点,但是点和点之间的连线会跟着点一起被拖动,拖动结束之后形成的图,进行重新编号就得到 G',比如上图左侧的两个图。经过置换变换的图前后是 同构 的。其中下图中,每一个顶点上角括号中的标号为拖动之前该顶点在上图中的编号。形式化一点可以这么定义:Perm()是一个 {1, V} 到 {1, V}的双射函数新图 G'的邻接矩阵,[perm(i), perm(i+1) ]=1 当且仅当 [i, i+1]=1,其中 i 是顶点编号,V 是顶点个数 。

  • 第二步:Bob 随机选择 b in {0, 1}} 进行挑战。

  • 第三步情况(1):Alice 根据 Bob 第二步发送的值:如果 b=0,那么 Alice 发送置换函数 Perm(),并且揭示完整的图 G'。而 Bob 则确认 G'是否是原图 G 经过置换无误。

  • 第三步情况(2):如果 Bob 第二步发送的b=1,那么 Alice 只揭示 G'中的哈密尔顿环路 C'即可。而 Bob 需要验证 C'是否是一个哈密尔顿环路

回忆一下三步 Sigma 协议,我们再理解下上面看似复杂的动作:

  • 第一步:被称为 Commit,证明者 Alice 需要把手里的答案进行同态变换,产生一个新答案,然后把每一条边都锁起来,交给 Bob;
  • 第二步:Bob 进行随机挑战;
  • 第三步:Alice 根据 Bob 的随机挑战,做出两种不同的回应。如果 Bob 挑战 0,那么Alice 打开第一步的承诺,表示自己在第一步没有作弊;如果 Bob 挑战 1,那么 Alice 只解密暴露出哈密尔顿环路的边(公路),其它边则不需解密。Bob 可以轻易地检查地图上露出来的那些边是否构成了一个不重复地经过所有城市的环路。

如果这个 Sigma 协议只走一遍的话, Alice 作弊的概率是 50%,如果重复 n 遍,Alice 作弊概率会指数级减小。大家可以试着用「模拟器」和「抽取器」的方法来证明这个协议的「零知识」与「可靠性」。

ZK-HAM 的变形:ZK-HAM-2

接下来把上面的这个三步协议改动一下。大家先考虑下这样一个简单事实:如果一个仅包含环路的子图 C 是 图 G的子图,C <= G那么说明 G 包含哈密尔顿环路。

这个事实等价于另一个事实:一个哈密尔顿图 G 的补集 !G 是环路子图 C 的补集 !C 的子图。

【名词解释】图的补集:所谓补集就是这样一个新地图,顶点保持不变,旧地图上的边在新地图中不存在,而新地图中的公路在旧地图中不存在,但是两个图重合在一起,就变成了一个完全图(完全图是指任意两个顶点之间都存在一条边)。

用邻接矩阵来理解,就是如果一个图G包含一个环路子图C,那么G矩阵中所有值为 0 的单元集合 必然被 C矩阵中所有值为0的单元集合包含。可以表示为 !G <= !C

根据第二个事实,我们可以定义如下的 Sigma 协议:

  • 公共输入:图G ,表示为 6*6 的邻接矩阵
  • 秘密输入:G的哈密尔顿环路 C(图中橙色的公路)

  • 第一步:

    • Alice 随机选择一个「置换」,Perm(.),并且通过C构造一个哈密尔顿环路子图 C'=Perm(C)
    • 然后 Alice 加密 C'的每一个单元,把加密后的结果发送给 Bob。
  • 第二步:Bob 随机选择 b in {0, 1}进行挑战

  • 第三步情况(1):如果 b=0,Alice 揭示完整的 C',而 Bob 验证这个 C' 是否确实是一个哈密尔顿环路子图。

  • 第三步情况(2):如果 b=1,Alice 发送 Perm(),同时按照 G'=Perm(G)中的所有含 0 单元所在的位置,揭示 C'中所对应的单元;Bob 验证 C'所有被揭示单元是否全部为 0

再理解下这三步 Sigma 协议:

  • 第一步:证明者 Alice 需要把哈密尔顿子图 C 进行置换变换,产生一个新的哈密尔顿子图 C',加密后交给 Bob;
  • 第二步:Bob 进行随机挑战,0 或者 1
  • 第三步:如果 Bob 挑战 0,那么 Alice 打开第一步的承诺,展示一个带有唯一环路的图;如果 Bob 挑战 1,Alice 则按照 G'中的 0单元的位置打开承诺,展示承诺中被打开的位置全部为 0

重点来了,大家仔细看看这个新版的 Sigma 协议的第一步。有没有发现什么情况?

第一步 Alice 发送的内容是与地图G无关的!

同样,第二步 Bob 发送的挑战也是与地图无关的。这样我们可以把第一步发的承诺改成事先准备好的比特串,而且我们假设这个比特串由一个可信第三方来产生,这样一来 Bob 就没有必要发送 b=0 这个分支,因为可信的第三方是诚实的,他一定是事先准备好一个正确的环路子图。这样,由于 Bob 只需要发送 1挑战分支,那么这一步也可以去除。

于是,三步协议变成了一步,我们成功去除了交互,有望实现 NIZK 。

我们接下来把 ZK-HAM-2 协议的第一步和第二步推到一个事先准备的字符串中,然后只让 Alice 发送第三步的内容给 Bob。如下图所示:

请注意,这里还不算是一个 NIZK 系统,因为这个共享字符串并不能对 Bob 公开,否则 Bob 就能算出环路 C。接下来,我们要解释一个新概念:「隐藏比特」(Hidden Bits)[FLS90]。Hidden Bits 是这样一串随机比特,它们对于验证者 Bob 隐藏,但是对于证明者 Alice 公开。然后在证明过程中,Alice 可以选择性地揭示一部分比特展示给 Bob 看。这是构造 NIZK 证明系统的一个利器,下面我们需要再继续深入 ……

云中的秘密:Hidden Bits

让我们再次开下脑洞,想象天上有朵云,云后面藏着一串随机产生的比特值,不是 0 就是 1,然后 Alice (证明者)带着一个「超级眼镜」,于是能够看到云后面所有的随机比特串,但是 Bob (验证者)却看不到。同时 Alice 手里还有一个「超级手电筒」,她可以打开手电筒用激光穿透云层,让 Bob 也能看见其中某个或某些比特。当然,Bob 能看到的比特的选择权完全在 Alice 手中。

云朵中隐藏的比特串就是所谓的 Hidden Bits

接下来我们要通过 Hidden Bits 来完成一个单步交互,完成 ZK-HAM-2 协议的功能。在 ZK-HAM-2 中的第一步,Alice 产生一个随机的置换 Perm(),然后通过 G 中的哈密尔顿环路子图 C 产生一个变换后的环路子图 C'=Perm(C)。这等价于,事先由任何人产生一个随机的哈密尔顿环路子图 C',然后 Alice 根据 CC' 计算得出一个相应的 Perm()

假设由某个「第三方」产生了一个随机的环路子图 C',编码成「邻接矩阵」比特串,放到云朵后面。假设 V 为顶点(城市)的个数,E 为边(公路)的条数。这个邻接矩阵的编码需要一个 V*V 长度的比特串,可以解释成一个 V*V 的矩阵,其中每一行只包含一个 1,每一列也只包含一个 1,矩阵的其它单元都为 0

接下来 Alice 如何构造证明呢?这其实很简单:

  1. Alice 通过「超级眼镜」得到了一个随机的哈密尔顿环路子图 C',然后计算得到一个置换 Perm(),使得 Perm(C)=C'

  2. Alice 根据 Perm() 来计算出一个换后的图 G'=Perm(G)

  3. Alice 产生证明,由两部分组成:(1)置换Perm() (2)G'的邻接矩阵中所有值为 0 的单元坐标所对应的 C'矩阵的值,相当于 Alice 需要用「超级手电筒」给 Bob 揭示的隐藏比特。

那么 Bob 怎么验证这个证明呢?Bob 拿到证明之后,只需要检验两个东西:

  1. Perm() 是否是一个合法的置换 V -> V,比如不能出现两个顶点映射到同一个顶点的情况。
  2. 对于 G 中的每一条「非边」,经过置换之后,Bob 抬头看天上对应的「隐藏比特」,比特值必须为 0

我们再仔细地深入理解下这个非交互协议。先从「完备性」入手:如果 Alice 没有作弊,那么很显然能够通过 Bob 的验证,这里请大家自行检查。

接下来我们分两步简要证明下「可靠性」:首先,因为 Bob 经过验证得知,所有 G 置换后的非边集合都已被揭示,且全为 0,那么可以得出结论,!G <= !C,即G的非边集合是环路子图 C的非边集合的子集。这等价于,C <= G,也就是说 G 包含一个哈密尔顿环路。这里请注意,这个可靠性概率是 100%。

然后,设想在一个「理想世界」中,Bob 获得了某种超能力(比如拿到 Alice 的「超级眼镜」),不需要 Alice 的超级手电筒,就能看穿云层,得到所有的隐藏比特 C'。然后当 Bob 得到 Perm()之后,就能通过 Perm() 反算出 C,于是 Bob 就相当于变身成了一个「抽取器」(Extractor),在理想世界中,它能把 Alice 要证明的知识给成功抽取出来。

那么怎么证明「零知识」呢?Alice 要具备一个超能力,就是在「理想世界」中,可以偷偷修改云朵中的隐藏比特。接下来就简单了,模拟器 Zlice 可以这么欺骗 Bob:

  1. Zlice 把云朵中的隐藏比特全部置为 0
  2. Zlice 随机产生一个合法的 Perm()

大家发现了,关键是,天上隐藏的比特必须是一个可信的字符串,所谓「可信」,就是指它确实应该是一个哈密尔顿环路子图。那么第三方需要可信。

可是,这样一个第三方是不是难以令人满意?Alice 和 Bob 要绝对信任他,不会和对手串谋。如果他和 Alice 串谋,可以把隐藏比特串直接设置为全 0;或者他和 Bob 串谋,直接把这个比特串给 Bob 看。这个协议看起来不错,但是很难实用。我们接下来要对这个简单协议进行升级。

升级随机性

第一个升级是让隐藏比特串变成一个「一致性均匀分布」的随机的隐藏比特串,是一个看起来相当随机的比特串,而不是一个刻意摆放好的哈密尔顿子图。

完全随机意味着比特串中的 0 的个数和 1出现的概率大概接近。那么接下来一个难题是如何让随机比特串中能出现一个随机的哈密尔顿环路子图矩阵。方法非常简单粗暴:产生一个足够长的随机串,然后从头扫描,直到找到一个随机的哈密尔顿环路为止。

可是……这个成功概率是不是非常非常小?我们下面给出一个概率没那么小的一种寻找方法。

  1. 我们先把比特串按照 5log(V) 的长度进行切分,然后如果每一个分片中的所有比特全为 1,那么我们把这个片段被视为邻接矩阵中的一个值为 1 的单元,否则视为一个值为 0 的单元。这样每一个矩阵单元出现 1 的概率为 1/(V^5)
  2. 我们取连续的 V^6 个片段,构成一个 V^3 * V^3 的大矩阵。如果大矩阵中包含一个 V*V的哈密尔顿环路矩阵,并且其他单元(总共 V^6 - V^2个) 都为 0。那么我们称这个大矩阵为「有用」。
  3. 根据概率计算,出现一个「有用」矩阵的概率为 1/[V^(3/2)]

注:「有用」矩阵的概率计算过程请参考 Fact 4.10.8, 「Foundations of Cryptography, Vol I」by Oded Goldreich,P304。

好了,我们需要升级下上一节的协议。因为现在「隐藏比特串」被拆分成了若干个大矩阵,这些大矩阵有些是「有用」的,有些是没用的。

接下来 Alice 要来构造证明了,她先戴上超级眼镜,扫描云朵中的 Hidden Bits,这要分两种情况,

  • Case 1:如果 Alice 遇到了一个没用的大矩阵 M,Alice 公开 M 的所有单元。

  • Case 2:如果 Alice 遇到了一个「有用」的大矩阵 M,这意味着 Alice 得到了一个随机的 哈密尔顿环路 C',然后 Alice 参照上一节的步骤进行证明即可。

那么 Bob 怎么验证这个证明呢?我们还要分情况进行讨论,

  • Case 1:如果 Alice 公开了全部的 M,那么 Bob 就检查这个 M 是否「无用」。如果 M 无用,就认为证明有效;否则拒绝。
  • Case 2:如果 Alice 发送的是形如(Perm()X)这样的证明,那么 Bob 按照上一节的验证方法进行验证。

对于这个协议,Bob 已经不再担心第三方是否作弊,故意产生一个全零的比特串,但是 Alice 仍然担心一旦第三方和 Bob 串谋,那么知识就彻底泄露了。

不仅如此,现在的协议还有个很强的限制,Alice 不能在看到隐藏比特之后再选择需要证明的 G,否则 Alice 就可以作弊。如果一个证明者选择证明的「命题」与 CRS 无关,那么这个证明者被称为 Non-adaptive Adversary。

FLS 变换:从 Hidden Bits 到 NIZK

接下来,我们再次升级协议,把「隐藏比特串」中的隐藏特性去除,变成「公共参考串」CRS。这里我们要借助一个密码学工具 —— Trapdoor Permutation,陷门置换。

所谓的陷门置换是指一个置换函数 F(x)x是一个集合 S 中的元素,然后函数 F(x)x 映射到 S 中的另一个元素 y。同时 F(x) 满足单向性,即通过 y 很难反算出 x;但是如果谁拥有陷门 t,就能实现反向计算F^(-1)(t,y)=x。陷门置换还可以匹配一个 Hardcore Predicate,h(x)=0/1,它能根据 S 集合中的元素产生一个一致性分布的 0/1比特。介绍完毕,大家是不是有点晕,没关系,晕一晕就习惯了。总之一句话,陷门置换可以对公共参考串和Hidden Bits 进行相互转换。

先假设有这样的密码学工具,然后我们升级协议。

我们把公共参考串看成是一个列表,y1, y2, y3, ..., yn,列表中的每一项都是集合 S 中的元素。然后通过 Hardcore Predicate 产生 Hidden Bits 中的每一个比特位。但是请注意,这里不能直接通过 h(y)=b 来产生 Hidden Bits,因为这样一来 Bob 就能自己算出所有的 Hidden Bits,这违反了上一节的协议。为了保证对 Bob 隐藏,我们需要用公共参考串的原象,也就是 x1, x2, x3, ..., xn 来产生 Hidden Bits,h(x)=b。Bob 虽然不能自己计算 b1, b2, b3, ..., bn,但是一旦得到一个 x,他就能检验 F(x)?=y来判断是否 x 是和公共参考串对应,同时再计算 h(x)=b 得到被揭示的 Hidden Bits,b

我们可以换一种不太准确,但是更直观的方式来理解,Alice 相当于自己产生一对公私钥。然后Alice 把公共参考串看成是一段「密文」,由于 Alice 有私钥,于是可以对密文进行解密,得到明文,这些明文,对于 Bob 而言就相当于是 Hidden Bits。当 Alice 要「揭示」Hidden Bits 时,就出示相应的明文片段,并且带上公钥,那么 Bob 就能通过公钥再次「加密」明文,与公共参考串的密文进行比对,确保 Alice 没有在揭示过程作弊。

下面是升级后的协议:

对于证明者 Alice

  1. Alice 随机选择一个 Trapdoor Permutation,(F, h, t)
  2. 根据公共参考串中的每一个 yi,利用陷门反向计算出 xi = F^(-1)(t, yi)
  3. 计算 Hidden Bits,bi=h(xi)
  4. 根据上一节的协议产生证明。假设 Alice 要揭示的 Hidden bits 的位置集合为 r1,r2,...,rl,那么 Alice 向 Bob 发送对应位置的 x,分别为 x_r1, x_r2, x_r3, ... x_rl ,连同(F, h),和证明一起并发给 Bob。

对于验证者 Bob

  1. 检查 (F, h) 是否为一个合法的 Trapdoor Permutation。
  2. L 中的每一个元素 x_r,计算出被揭示的 Hidden Bits bi=h(F(x_r)),然后按照上一节的协议检查证明。

这个新协议的「完备性」,请大家自行检查。

对于「零知识」,我们需要构造一个「模拟器」Zlice2,它的超能力是修改公共参考串。

  1. 模拟器直接调用上一节协议的模拟器 Zlice。得到一个三元组,(proof, {r}, {b})
  2. 对于每一个公共参考串位置,如果它对应某一个 r,模拟器从集合 S随机选择一个 x_r,使得 h(x_r)=b_r,这里 b_r就是 {b}中对应 r ;然后把 y_r=F(x_r) 作为假参考串的一部分。
  3. 对于每一个公共参考串位置,如果与 {r}无关,那么模拟器随机选一个 y即可
  4. 模拟器把所有的 y拼在一起,得到一个假CRS。

对于「可靠性」,事情变得不那么简单了。因为现在 Alice 有能力挑选 (F,h,t),Alice 可以挑选一个对自己有利,甚至作弊的 (F, h, t),使得她可以控制一次协议运行的 Hidden Bits {b}的结果。对于本节升级后的新协议而言,需要重复很多遍,以致于虽然 Alice 可以控制一次协议运行的 Hidden Bits,但是她对其它若干次协议运行的 Hidden Bits 无能为力。换句话说,Alice 无论如何挑选 (F, h, t) 都无法完全掌控多次的协议运行。

这个升级变换理论上可以支持任意的 Hidden Bits 模型下的非交互式零知识证明,被称为 FLS Protocol。FLS 变换有很多的好处:首先,这个随机产生的 CRS 可以多次使用,实现所谓的「Multi-Theorem NIZK」;其次,可以实现「Adaptive Soundness」,即 Alice 可以先看到 CRS,然后再选择要证明的内容。最后,这个协议还是「Adaptive Zero-Knowledge」,即 Bob 也可以先看到 CRS,然后再选择要证明的内容给 Alice。

注:Adaptive Adversary 是比较符合现实世界的安全情况,比如第二类CCA安全。因为 CRS 是公开的,攻击者可以先分析 CRS,再决定如何发起攻击。

寻找理想的 Trapdoor Permutation

陷门置换 Trapdoor Permutation 最早出现在姚期智老师的论文「Theory and Application of Trapdoor Functions」[Yao82]中,是公钥密码学的重要基础。在上一节给出的 FLS 变换中,需要一个理想化的 Trapdoor Permutation,所谓的理想化是指,每一个 n-bit 字符串都能唯一变成另一个 n-bit 字符串,并且不会出现「多对一」的映射关系。Alice 需要随机抽样一个 Index,发给 Bob,然后 Bob 要能检查出这个 Index 所对应的 F() 是否是一个「完美」的置换。问题来了,怎么 Bob 怎么能在多项式时间内检查出来呢?如果 Bob 不能检查,那么 Alice 就可以抽样一个不完美的 Permutation(比如一个「多对一」的函数),从而可能作弊,破坏「Soundness」这个性质,Bellare 和 Yung 发表在 1996 年的论文最早注意到了这一点,但是并没有完全解决这个问题[BY96]。

如何找到一个桥梁,能够将 Trapdoor Permutation 合适地抽象出来,同时能够对接到密码学工具的实现上,是一个及其有挑战性的工作。随后各路密码学家(包括 Oded Goldreich) 在这方面研究了很长时间,发表了许许多多的论文 ,各种不同类型的 Trapdoor Permutation 被定义、被研究,但是仍然不能让人满意。直到最近(2018年)一个工作是 Ran Canetti 与 Amit Lichtenberg 提出了 Certifiable Injective Trapdoor Function 这样一个新类型[RL18],并证明了这种 Trapdoor Permutation 终于能满足 FLS 变换要求。但这是不是故事的结束呢?理论密码学家们估计不会停下探索的脚步。

除了基于 Trapdoor Permutation 的 FLS 变换 ,还有各式各样的解决方案来升级 Hidden Bits Model,比如采用 Invariant Signature[BG90],或 Verifiable Random Generator [DN00] 来实现 Hidden Bits 的变换,或者弱可验证随机函数 [BGRV09], 还有一种叫做 publicly-verifiable trapdoor predicates 的方案[CHK03]。

三十年来,密码学家们发明的 NIZK 方案有很多,但 Hidden Bits 方法是目前已知唯一的办法,(1) 基于「一致性分布」的共享 CRS,(2) 实现任意 NP 语言的 NIZK Proofs(Not Arguments!)。

NIZK Proofs 与 NIZK Arguments

在本文中,我们构造的 NIZK 「证明」系统的可靠性属于「Statistical Soundness」,而零知识则属于「Computational Zero-Knowledge」。这意味着什么呢?这意味着,不管证明者 Alice 的算力有多强大(甚至超多项式),Alice 仍然无法作弊。但是,如果验证者 Bob 拥有超强的计算能力,那么是存在这种可能性:Bob 从证明中抽取到有价值的「知识」。

这又意味着什么?

这意味着,对于 NIZK Proofs 来说,它的长度肯定要比「知识」长,知识即 NP 问题中的 witness。只要 Bob 算力够强,他就可以把证明解密。对于「抽取器」而言,它也需要在没有交互的情况下抽取 witness 。证明最短的 NIZK Proofs 当属 Greg Gentry 等人采用「全同态加密」技术构造的 NIZK 方案了 [GGI+14],证明长度只是稍稍大于 witness 的长度。

那能不能构造证明尺寸小于 witness 的 NIZK 呢?答案是 YES!

还有一类的 NIZK 系统被称为 NIZK Arguments:它们的可靠性是「Computational Soundness」,零知识属于「Perfect Zero-Knowledge」或者「Statistical Zero-Knowledge」。这说明,Alice 如果算力超强,那么她是有作弊空间的,但是因为现实世界中,我们可以通过加大安全参数(Security Parameters)来极大地降低 Alice 作弊的可能性,但是能实现非常极致的零知识特性。由于弱化了可靠性,那么我们就可以继续压缩证明的尺寸。

注:在本系列中,我们并不刻意区分「证明」与「论证」这两个词。如果需要指明 Arguments 而非 Proofs,会专门强调。

假如说我们要公开一个 NIZK 证明到 Github上,假如过了一百年以后,Github 网站还在,而未来计算机的计算能力已经有了质的飞跃,这时候,一个 NIZK Proof 可能会被算力攻破,泄露知识,而 NIZK Argument 则很大可能性上还保持安全性。

现在流行的热词 —— zkSNARK 中的 AR正是指代 Argument。

NIZK Argument 可以实现 O(1) 常数级长度的证明,即与 witness 的长度无关。然而这需要隐藏更多的秘密到 CRS 中。

没有秘密的世界

1956 年,哥德尔在一封寄给冯诺依曼的信中提到了一个著名的问题,「P 是否等于 NP」。后来,这个问题被 Clay 研究所列为七个千禧年难题之一,悬赏百万美金。

零知识证明系统正是为了保护 witness 不泄露的前提下,实现 NP 问题的验证。那如果一旦证明了「P == NP」,这会意味着什么?这意味着 witness 不再有多大意义了,反正一个图灵机也可以在多项式时间内找到 witness。零知识证明试图保护的 witness 也变得徒劳无益。

事实上,如果「P == NP」,现有的公钥密码学、对称加密 AES 与 SM4、哈希算法所依赖的难解问题都可能坍塌,我们可能很难保存秘密。不仅如此,

如果 P == NP,我们所处的世界将会变得非常不一样。「Creative Leaps」将不再有价值,求解问题与验证问题之间的鸿沟不复存在。每个能欣赏交响乐的人都会成为莫扎特,每个会推理的人都会变成高斯,每个能判断投资好坏的人都会变成巴菲特。从达尔文进化论的观点出发:如果这就是我们存在的宇宙,为什么我们还没有进化得可以充分利用这个好处?—— Scott Aaronson (2006)

对于数学也一样,数学证明的验证过程也是多项式复杂度的,如果「P == NP」,那么也就存在着多项式时间寻找证明的算法(如果证明存在)。这意味着哥德巴赫猜想、黎曼猜想将有可能得到证明,难怪 Lance Fortnow 在博客[For04]里这么说:

A person who proves P == NP would walk home from the Clay Institute not with one million-dollar check but with seven. 如果谁能证明 P = NP,那么他不会只拿着一张百万美元支票回家,而是七张。 —— Lance Fortnow (2004)

2002年的调查显示,61% 的计算机科学家相信「P != NP」,而十年后,这个比例上升到了 83%[Wil12]。 而我是被 Scott Aaronson 的如下论断说服的:

自指论证:如果 P = NP 是事实,那么这个证明会比较容易被发现;但是如果 P != NP,那么这个证明会比较难发现。所以相信 P != NP 看起来会让 数学现实 更一致一些。—— Scott Aaronson (2006)

尽管是如此不情愿,如果我们真的生活在一个没有秘密的世界,那会是什么样子?「环形监狱 Panopticon」是 18 世纪英国哲学家 Jeremy Bentham 提出的一个惊悚概念。囚徒们被中心全天候监控,没有任何隐私可言,而且他们对自己是否处于被监控状态也无从得知。这个无比悲观的论调让人浑身不适,但很多人认为,这可能是两百多年前对未来网络数字时代的一则精准寓言。

从『Billy Budd』,卡夫卡的『The Trial』,到奥威尔的『1984』,到著名黑客 Kevin Mitnick 写的超级大卖书『隐形的艺术』(教你如何在大数据时代保护自己的信息),似乎,危机四伏,风险不断累积,对末日世界的想象给了作家们很好的素材 ……

偶尔无意中看到了一本有趣的漫画『The Private Eye』,它描述了一个劫后余生的后现代场景:在未来,我们的所有信息数据都存放在云上,然后突然有一天,这个数据云「爆炸」了,不知道是什么原因(可能是谁不小心打开了潘多拉的魔盒,找到了 P == NP 的构造性证明),反正所有的信息,包括每个人最阴暗的过去,都不再成为秘密;所有的数字化的资产都被抹掉,所有的在线知识库永久丢失;每个人的言行、账单、邮件、聊天消息、银行卡密码、中学考卷、GPS位置信息,写了一半的日记、删除的照片、上网记录,这些信息都将暴露给同事、邻居、 朋友、亲人、甚至任何一个好奇的人。

每个人都无地自容,惶惶不可终日,然后逐渐地,大家都选择隐藏自己,人们出门都要戴上面具,以小心翼翼地保护自己的身份,甚至一个人可以选择使用多个身份,国家法律规定任何偷窥行为都将被严惩,获取信息成为了一种至少无上的权力,照相机需要被严格管控,互联网不再存在,人们通讯又回到了电话亭时代 ……

这会是人类的终极命运么?

未完待续

本文开头提到了「隐藏随机性」并不是必要的,我们来回想下 Hidden Bits 模型。这些 Hidden Bits 并没有对 Prover 隐藏,而是敞开了让 Prover 知道,但是由于 Hidden Bits 是「一致性随机分布」的字符串, 所以即使让 Prover 知道了,他仍然逃不过随机挑战的火力。然而在流行的 zkSNARK 方案中,并没有采用「一致性随机分布」的 CRS,而是一组结构化的随机数。不管怎样,用 CRS 来构建「信任根基」的秘密,就是藏在其中的「秘密」。

这符合直觉,保守「秘密」也是一种信任。因为 Alice 不知道 CRS 中隐藏的秘密后门,所以无法作弊。同样,Bob 不知道 CRS 中的秘密,也就没办法获得「知识」。同样,人与人之间的协作既要建立在公开透明的基础上,也要保守秘密。

All human beings have three lives: public, private, and secret. 每个人都有三种生活,公开的,私人的,以及秘密的。—— Gabriel García Márqueel

致谢:感谢陈宇,丁晟超,张宇鹏,胡红钢,刘巍然,何德彪,万志国等老师的专业建议和指正,感谢安比实验室小伙伴(p0n1, even, valuka, Vawheter, yghu, mr)的修改建议。本文内容不代表他们观点。

最后附上漫画书的链接:http://panelsyndicate.com/comics/tpeye 作者甚至把创作过程的邮件和草图都放了出来,大家可以体验一下窥视制作过程的快感。

参考文献

  • [Aar06] Aaronson, Scott. Reasons to believe, 2006. https://www.scottaaronson.com/blog/?p=122
  • [BFM88] Blum, Manuel, Paul Feldman, and Silvio Micali. “Non-interactive zero-knowledge and its applications.” STOC’88. 1988.
  • [BG90] Bellare, Mihir, and Shafi Goldwasser. “New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs.” Conference on the Theory and Application of Cryptology. Springer, New York, NY, 1989.
  • [BGN05] Boneh, Dan, Eu-Jin Goh, and Kobbi Nissim. “Evaluating 2-DNF formulas on ciphertexts.” Theory of Cryptography Conference. Springer, Berlin, Heidelberg, 2005.
  • [BGRV09] Brakerski, Zvika, Shafi Goldwasser, Guy N. Rothblum, and Vinod Vaikuntanathan. “Weak verifiable random functions.” In Theory of Cryptography Conference, pp. 558-576. Springer, Berlin, Heidelberg, 2009.
  • [BY96] Bellare, Mihir, and Moti Yung. “Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation.” Journal of Cryptology 9.3 (1996): 149-166.
  • [CHK03] Canetti, Ran, Shai Halevi, and Jonathan Katz. “A forward-secure public-key encryption scheme.” International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2003.
  • [CHMMVW19] Chiesa, Alessandro, et al. Marlin: Preprocessing zksnarks with universal and updatable srs. Cryptology ePrint Archive, Report 2019/1047, 2019, https://eprint.iacr.org/2019/1047, 2019.
  • [DN00] Dwork, Cynthia, and Moni Naor. “Zaps and their applications.” Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE, 2000.
  • [FLS90] Feige, Uriel, Dror Lapidot, and Adi Shamir. “Multiple non-interactive zero knowledge proofs based on a single random string.” Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science. IEEE, 1990.
  • [For04] Fortnow, Lance. “What if P = NP?”. 2004. https://blog.computationalcomplexity.org/2004/05/what-if-p-np.html
  • [For09] Fortnow, Lance. “The status of the P versus NP problem.” Communications of the ACM 52.9 (2009): 78-86.
  • [Groth10a] Groth, Jens. “Short non-interactive zero-knowledge proofs.” International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2010.
  • [Groth10b] Groth, Jens. “Short pairing-based non-interactive zero-knowledge arguments.” International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2010.
  • [GOS06] Groth, Jens, Rafail Ostrovsky, and Amit Sahai. “Perfect non-interactive zero knowledge for NP.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2006.
  • [GWC19] Gabizon, Ariel, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. Cryptology ePrint Archive, Report 2019/953, 2019.
  • [KP98] Kilian, Joe, and Erez Petrank. “An efficient noninteractive zero-knowledge proof system for NP with general assumptions.” Journal of Cryptology 11.1 (1998): 1-27.
  • [MBK+19] Maller, Mary, et al. “Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings.” IACR Cryptology ePrint Archive 2019 (2019): 99.
  • [RL18] Ran Canetti and Amit Lichtenberg. “Certifying trapdoor permutations, revisited.” Theory of Cryptography Conference. Springer, Cham, 2018.
  • [Wil12]Gasarch, William I. “Guest Column: The Third P=? NP Poll.” ACM SIGACT News 50.1 (2019): 38-59.
  • [Yao82] Yao, Andrew C. “Theory and application of trapdoor functions.” 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). IEEE, 1982.

PLONK 系列作者:郭宇@Secbit: Founder of Secbit, https://github.com/sec-bit , https://secbit.io/

原链接:https://github.com/sec-bit/learning-zkp/tree/develop/plonk-intro-cn

理解 PLONK(一):Plonkish Arithmetization

算术化是指把计算转换成数学对象,然后进行零知识证明。 Plonkish 算术化是 Plonk 证明系统特有的算术化方法,在 Plonkish 出现之前,主流的电路表达形式为 R1CS,被 Pinocchio,Groth16,Bulletproofs 等广泛采用。2019 年 Plonk 方案提出了一种看似复古的电路编码方式,但由于 Plonk 方案将多项式的编码应用到了极致,它不再局限于算术电路中的「加法门」和「乘法门」,而是可以支持更灵活的「自定义门」与「查表门」。

我们先回顾一下 R1CS 的电路编码,也是相关介绍最多的算术化方案。然后我们对比引入 Plonkish 编码。

算术电路与 R1CS 算术化

一个算术电路包含若干个乘法门与加法门。每一个门都有「两个输入」引脚和一个「输出」引脚,任何一个输出引脚可以被接驳到多个门的输入引脚上。

先看一个非常简单的算术电路:

img20230414162317

这个电路表示了这样的一个计算:

电路中有4个变量,其中三个变量为输入变量 ,一个输出变量 ,其中还有一个输入为常数,其值为

一个电路有两种状态:「空白态」和「运算态」。当输入变量没有具体值的时候,电路处于「空白态」,这时我们只能描述电路引线之间的关系,即电路的结构拓扑。

接下来的问题是,我们要先编码电路的「空白态」,即编码各个门的位置,和他们之间引线连接关系。

R1CS 是通过图中的乘法门为中心,用三个「选择子」矩阵来「选择」乘法门的「左输入」、「右输入」、「输出」都分别连接了那些变量。

我们先看看图中最上面的乘法门的左输入,可以用下面的表格来描述:

这个表格只有一行,因此我们可以用一个向量 来代替,表示乘法门的左输入连接了两个变量, 。记住,所有的加法门都会被展开成多个变量的相加(或线性组合)。

再看看其右输入,连接了一个变量 和一个常数值,等价于连接了 的两倍,那么右输入的选择子矩阵可以记为

这里同样可以用一个行向量 来表示,其中的 即为上图中电路的常数引线。

最后乘法门的输出按照上面的方法可以描述为 ,即输出变量为

有了三个向量 ,我们可以通过一个「内积」等式来约束电路的运算:

这个等式化简之后正好可以得到:

如果我们把这几个变量换成赋值向量 ,那么电路的运算可以通过「内积」等式来验证:

而一个错误的赋值向量,比如 ,则不满足「内积等式」:

左边运算结果为 ,右边运算结果为 。当然,我们可以验证 也是一组合法(满足电路约束)的赋值。

并不是任何一个电路都存在赋值向量。凡是存在合法的赋值向量的电路,被称为可被满足的电路。判断一个电路是否可被满足,是一个 NP-Complete 问题,也是一个 NP 困难问题。

这里例子中的两个乘法门并不相同,上面的乘法门是左右输入中都含有变量,而下面的乘法门只有一边的输入为变量,另一边为常数。对于后者这类「常数乘法门」,后续我们也把他们看作为特殊的「加法门」,如下图所示,左边电路右下的乘法门等价于右边电路的右下加法门。

那么如果一个电路含有两个以上的乘法门,我们就不能用 三个向量之间的内积关系来表示运算,而需要构造「三个矩阵」的运算关系。

多个乘法门

比如下图所示电路,有两个乘法门,他们的左右输入都涉及到变量。

c

这个电路表示了这样的一个计算:

我们以乘法门为基准,对电路进行编码。第一步将电路中的乘法门依次编号(无所谓编码顺序,只要前后保持一致)。图中的两个乘法门编码为 #1#2

然后我们需要为每一个乘法门的中间值引线也给出变量名:比如四个输入变量被记为 ,其中 为第二个乘法门的输出,同时作为第一个乘法门的右输入。而 为第一个乘法门的输出。于是我们可以得到一个关于变量名的向量:

该电路的「空白态」可以用下面的三个矩阵来编码:

其中 为乘法门的数量,而 大致为引线的数量。每一个矩阵的第 行「选择」了第 个乘法门的输入输出变量。比如我们定义电路的左输入矩阵

其中第一个乘法门的左输入为 , 第二个乘法门的左输入为 。右输入矩阵 定义为:

其中1号门的右输入为 ,第二个乘法门的右输入为 。最后定义输出矩阵

我们把所有的引线赋值看作为一个向量: (这里用字母 ,取自 Assignments 首字母)

在上面的例子中,「赋值向量」为

于是我们可以轻易地检验下面的等式

其中符号 为 Hadamard Product,表示「按位乘法」。展开上面的按位乘法等式,我们可以得到这个电路的运算过程:

请注意,通常「赋值向量」中需要一个固定赋值为 的变量,这是为了处理加法门中的常量输入。

优缺点

由于 R1CS 编码以乘法门为中心,于是电路中的加法门并不会增加 矩阵的行数,因而对 Prover 的性能影响不大。R1CS 电路的编码清晰简单,利于在其上构造各种 SNARK 方案。

在 2019 年 Plonk 论文中的编码方案同时需要编码加法门与乘法门,看起来因此会增加约束的数量,降低 Proving 性能。但 Plonk 团队随后陆续引入了除乘法与加法外的运算门,比如实现范围检查的门,实现异或运算的门等等。不仅如此,Plonk 支持任何其输入输出满足多项式关系的门,即 Custom Gate,还有适用于实现 RAM 的状态转换门等,随着查表门的提出,Plonk 方案逐步成为许多应用的首选方案,其编码方式也有了一个专门的名词:Plonkish。

Plonkish 算术门

回看下例子电路,我们把三个门全都编号, ,同时把加法门的输出值也标记为变量

显然,上面的电路满足三个约束:

我们定义一个矩阵 来表示约束( 为算术门的数量):

为了区分加法和乘法,我们再定一个向量 来表示运算符

于是我们可以通过下面的等式来表示三个约束:

如果把上面的等式代入并展开,我们可以得到下面的约束等式:

化简后得:

这正好是三个算术门的计算约束。

总结下,Plonkish 需要一个矩阵 来描述电路空白态,而所有的赋值则写入了 矩阵。对于 Prover 和 Verifier 的交换协议, 是 Prover 的 witness,属于秘密知识,对 Verifier 保密, 矩阵代表了一个实现双方约定共识的电路描述。

不过仅仅有 矩阵是不足以精确描述上面的例子电路。

复制约束

比较下面两个电路,它们的 矩阵完全相同,但它们却完全不同。

两个电路的区别在于 是否被接入了 #1 号门。如果让 Prover 直接把电路赋值填入 表格,一个「诚实的」Prover 会在 两个位置填上相同的值;而一个「恶意的」Prover 完全可以填上不同的值。如果恶意 Prover 在 也填入不同的值,那么实际上 Prover 证明的是上图右边的电路,而非是和 Verifier 共识过的电路(左边)。

我们需要增加新的约束,强制要求右边电路图中 。这等价于我们要求 Prover 把同一个变量填入表格多个位置时,必须填入相等的值

这就需要一类新的约束——「拷贝约束」,即 Copy Constraint。Plonk 采用「置换证明」保证 表格中多个位置上的值满足拷贝关系。我们继续用上面这个电路图的案例来说明其基本思路:

设想我们把 表格中的所有位置索引排成一个向量:

然后把应该相等的两个位置互换,比如上图中要求 。于是我们得到了下面的位置向量:

然后我们要求 Prover 证明: 表格按照上面的置换之后,仍然等于自身。置换前后的相等性可以保证 Prover 无法作弊。

再来一个例子,当约束一个向量中有三个(或多个)位置上的值必须相同时,只需要把这三个(或多个)位置的值进行循环移位(左移位或者右移位),然后证明移位后的向量与原向量相等即可。比如:

如果要证明 ,那么只需要证明:

在经过置换的向量 中, 依次右移交换,即 放到了原来 的位置,而 放到了 的位置, 则放到了 的位置。

如果 ,那么 所有对应位置上的值都应该相等,可得: ,即 。这个方法可以适用于任意数量的等价关系。(后续证明两个向量相等的方法请见下章)

那么如何描述电路赋值表格中的交换呢?我们只需要记录 向量即可,当然 向量也可以写成表格的形式:

加上 ,空白电路可以描述为 ,电路的赋值为

再比较

R1CS 的 表格的宽度与引线的数量有关,行数跟乘法门数量有关。这个构造相当于把算术电路看成是仅有乘法门构成,但每个门有多个输入引脚(最多为所有引线的数量)。而 Plonkish 则是同等对待加法门与乘法门,并且因为输入引脚只有两个, 所以 表格的宽度固定,仅有三列(如果要支持高级的计算门,表格可以扩展到更多列)。这一特性是 Plonk 可以利用 Permutation Argument 实现拷贝约束的前提。

…, and thus our linear contraints are just wiring constraints that can be reduced to a permutation check.

按照 Plonk 论文的统计,一般情况下,算术电路中加法门的数量是乘法门的两倍。如果这样看来, 表格的行数会三倍于 R1CS 的矩阵。但这个让步会带来更多的算术化灵活度。

电路验证协议框架

有了电路空白结构的描述和赋值,我们可以大致描述下 Plonk 的协议框架。

首先 Prover 和 Verifier 会对一个共同的电路进行共识, 。 假设电路的公开输出为 ,而 为秘密输入。

Prover 填写 矩阵(Verifier 不可见):

其中增加的第四行是为了增加一个额外的算术约束: ,把 值显示地表示在 矩阵中。

相应的那么 Prover 和 Verifier 共识的 矩阵为

其中第四行约束,保证 ,可以把 代入下面的算术约束,可得 ,即

为了保证第一行的 也必须为 ,这就需要在 矩阵中添加额外的一条拷贝约束:让 变量的位置 与 第四行的输出 交换对调:

如果 Prover 是诚实的,那么对于 ,下面的算术约束等式成立:

验证协议的大概思路如下:

协议开始:Prover 如实填写 表格,然后把 表格的每一列进行编码,并进行多项式编码,并把编码后的结果发送给 Verifier

协议验证阶段:Verifier 与 Prover 通过进一步的交互,验证下面的等式是否成立:

当然这个验证还不够,还要验证 之间的关系。还有,Verifier 如何通过多项式来验证电路的运算,请看后续章节。

参考文献

  • [BG12] Bayer, Stephanie, and Jens Groth. “Efficient zero-knowledge argument for correctness of a shuffle.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2012.
  • [GWC19] Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. “Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge.” Cryptology ePrint Archive (2019).

理解 PLONK(二):多项式编码

在上篇文章里,我们可以把电路的计算的「合法性检查」转换成一组加法/乘法约束。假如总共有 N 个约束,那么Prover 可以通过多项式编码的方式把多个约束压缩成一个约束,让 Verifier 轻松检查。

多项式的概率检查

把多个约束验证合并的神奇能力来自于「多项式随机挑战」。如果有两个多项式 同为两个次数不超过 的多项式。那么 Verifier 只需要给出一个随机挑战值 ,计算 是否等于 即可大概率得知 ,其中出错的概率 。只要保证 足够大,那么检查出错的概率就可以忽略不计。

这个原理被称为 Schwartz-Zippel 定理。

假如要验证两个向量 是否等于 ,为了可以一步挑战验证,我们要先把三个向量编码成多项式。

一种最直接的方案是把向量当作多项式的「系数」进行编码

显然,如果 ,那么 。然后我们可以通过挑战一个随机数 来检验三个多项式在 处的取值,验证:

如果上式成立,那么

Lagrange 插值 与 Evaluation Form

假如我们要验证 ,用系数编码的方式就不容易处理了,因为 会产生很多的交叉项。并且 的项并不对应到 的系数,比如 的系数出现在 上,但同时 项的系数组成还有 。而 的系数。

我们需要另一种多项式编码方案,利用 Lagrange Basis。如果我们要构造多项式 ,使得它在定义域 上的取值为 ,即

插值需要用到一组插值多项式: ,其中 ,并且 。然后 可以按如下方式编码:

可以简单心算一下,当 时,等式右边除了第一项之外,其他项都等于零,于是 。看起来 像是一个选择器,这组多项式又被称为 Lagrange Polynomials。

我们用同样的方法来编码

如果 成立,那么 。如果 ,那么

我们现在已经把两个向量的按位乘积问题转换到了三个多项式之间的关系,接下来的问题是如何进行随机挑战验证。

我们发现:如果直接让 Verifier 发送随机数 挑战上面的等式,那么 只能属于 。如果只存在一个 使得 ,那么 Verifier 的一次挑战能发现这个错误的概率只有 ,这样 Verifier 需要挑战多次才能缩小检测出错的概率。不过这样不满足我们的要求,我们希望只通过一次挑战来检测出 Prover 的作弊行为。

我们可以把上面的等式的 取值范围去除,换成下面的等式:

这个等式在整个 定义域上都成立。这是为何?

首先我们看等式左边的多项式: ,不妨定义为 。我们可以看到 上等于零,那么意味着 恰好是 的「根集合」。于是 可以按照下面的方式进行因式分解:

换个说法, 可以被多项式 整除,并得到一个商多项式 。零多项式 又被称为 Vanishing Polynomial。

如果我们让 Prover 计算出这个 ,并且发送给 Verifier,又因为 是已知的系统参数,Verifier 可以自行计算 ,那么 Verifier 只需要一次随机检测即可判断 是否在 处等零。

进一步,如果我们使用多项式承诺(Polynomial Commitment),Verifier 可以让 Prover 来帮忙计算这些多项式在 处的取值,发送并证明这些值的正确性,这样能最大限度地减少 Verifier 的工作量。

但是, Verifier 计算 需要 的计算量。

那能否让 Verifier 继续减少工作量?答案是可以的,只要我们选择特殊的

单位根 Roots of Unity

如果我们选择单位根作为 ,那么 的计算量会降为

对于任何有限域 ,其中阶数 为素数。那么去除零之后剩下的元素构成了乘法群 ,阶数为 。由于 一定为偶数,那么 的乘法因子中一定包含若干个 ,假设记为 。那么 一定包含一个阶数为 的乘法子群。不妨设 ,那么一定存在一个阶数为 的乘法子群,记为 。 该乘法子群必然含有一个生成元,记为 ,并且 。这相当于把 次方根,因此被称为单位根。不过单位根不只有一个 ,我们会发现 都满足单位根的特性,即 。那么所有这些由 产生的单位根就组成了乘法子群

这些元素满足一定的对称性:比如 。又比如把所有的单位根求和,我们会得到零:

举一个简单的例子,我们可以在 中找到一个阶数为

其中乘法群的生成元为 。由于 13-1=3*2*2,所以存在一个阶数为 的乘法子群,其生成元为

在实际应用中,我们会选择一个较大的有限域,它能有一个较大的 Powers-of-2 乘法子群。比如椭圆曲线 BN254 的 Scalar Field,含有一个阶数为 的乘法子群,BLS-12-381 的Scalar Field 含有一个阶数为 的乘法子群。

在乘法子群 上,具有下面的性质:

我们可以进行简单的推导,假设 ,由于 的对称性,这个计算过程可以不断化简:

Lagrange Basis

对于 Lagrange 多项式, ,并且 。接下来,我们给出 的构造。

为了构造 ,先构造不等于零的多项式部分。由于 ,因此他一定包含 这个多项式因子。但该因子显然在 处可能不等于 ,即可能 。然后,我们只要让该因子除以这个可能不等于 的值即可,于是 定义如下:

不难发现, 处等于 ,其它位置 处等于

对于任意次数小于 的多项式 ,那么它都可以唯一地表示为:

我们可以用多项式在 上的值 来表示 。这被称为 多项式的求值形式(Evaluation Form),区别于系数形式(Coefficient Form)。

两种形式可以在 上可以通过 (Inverse) Fast Fourier Transform 算法来回转换,计算复杂度为

多项式的约束

利用 Lagrange Basis 我们可以方便地对各种向量计算进行约束。

比如我们想约束 向量的第一个元素为 。那么我们可以对这个向量进行编码,得到 ,并且进行如下约束:

Verifier 可以挑战验证下面的多项式等式:

再比如,我们想约束 向量的第一个元素为 ,最后一个元素为 ,其它元素任意。那么 应该满足下面两个约束。

那么通过 Verifier 给一个随机挑战数( ),上面两个约束可以合并为一个多项式约束:

接下来,Verifier 只要挑战下面的多项式等式即可:

如果想验证 两个等长向量除第一个元素之外,其它元素都相等,那要如何约束呢?假设 为两个向量的多项式编码,那么它们应该满足:

时,左边多项式的第一个因子等于零,而 时,则左边第二因子等于零,即表达了除第一项可以不等之外,其它点取值都必须相等。

可以看出,采用 Lagrange 多项式,我们可以灵活地约束多个向量之间的关系,并且可以把多个约束合并在一起,让 Verifier 仅通过很少的随机挑战就可验证多个向量约束。

Coset

在素数有限域的乘法群中,对于每一个乘法子群 ,都有多个等长的陪集(Coset),这些 Coset 具有和 类似的性质,在 Plonk 中也会用到 Coset 的概念,这里只做部分性质的介绍。

还拿 为例,我们取 ,并且乘法群的生成元 。于是我们可以得到下面两个 Coset:

\begin{split} H_1 &= g\cdot H = (g, g\omega, g\omega^2, g\omega^3) &= (2,10,11,3) \ H_2 &= g^2\cdot H = (g^2, g^2\omega, g^2\omega^2, g^2\omega^3) &= (4,7,9,6) \ \end{split}

可以看到 ,并且它们交集为空,没有任何重叠。并且它们的 Vanishing Polynomial 也可以快速计算:

References

  • Schwartz–Zippel lemma. https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma

理解 PLONK(三):置换证明

Plonkish 电路编码用两个矩阵 描述电路的空白结构,其中 为运算开关, 为置换关系,用来约束 矩阵中的某些位置必须被填入相等的值。本文重点讲解置换证明(Permutation Argument)的原理。

回顾拷贝关系

回顾一下 Plonkish 的 表格,总共有三列,行数按照 对齐。

我们想约束 Prover 在填写 表时,满足下面的拷贝关系: ,换句话说, 位置上的值需要被拷贝到 处,而 位置上的值需要被拷贝到 处, 位置上的值被拷贝到 处。

问题的挑战性在于,Verifier 要仅通过一次随机挑战就能完成 表格中多个拷贝关系的证明,并且在看不到 表格的情况下。

Plonk 的「拷贝约束」是通过「置换证明」(Permutation Argument)来实现,即把表格中需要约束相等的那些值进行循环换位,然后证明换位后的表格和原来的表格完全相等。

简化一下问题:如何证明两个等长向量 满足一个已知的置换 ,并且

举一个例子,假设 ,即他们满足一个「左移循环换位」的置换关系,那么 。如何能证明 ,那么两个向量对应位置的值都应该相等,

那么 ,于是可以得出结论: ,即 中的全部元素都相等。

对于 ,我们只需要针对那些需要相等的位置进行循环换位,然后让 Prover 证明 和经过循环换位后的 表格相等,那么可实现拷贝约束。证明两个表格相等,这个可以通过多项式编码,然后进行概率检验的方式完成。剩下的工作就是如何让 Prover 证明 确实是(诚实地)按照事先约定的方式进行循环移位。

那么接下来就是理解如何让 Prover 证明两个向量之间满足某一个「置换关系」。 置换证明(Permutation Argument)是 Plonk 协议中的核心部分,为了解释它的工作原理,我们先从一个基础协议开始——连乘证明(Grand Product Argument)。

冷启动:Grand Product

假设我们要证明下面的「连乘关系」 :

我们在上一篇文章介绍了如何证明一组「单乘法」,通过多项式编码,把多个单乘法压缩成单次乘法的验证。

这里对付连乘的基本思路是:让 Prover 利用一组单乘的证明来实现多个数的连乘证明,然后再通过多项式的编码,交给 Verifier 进行概率检查。

强调下:思路中的关键点是如何把一个连乘计算转换成多次的单乘计算。

我们需要通过引入一个「辅助向量」,把「连乘」的计算看成是一步步的单乘计算,然后辅助向量表示每次单乘之后的「中间值」: