ZKPunk logo

Discord server

ZKPunk is a content platform centered around Zero-Knowledge Proof (ZKP) technology, dedicated to promoting its adoption and development. ZKPunk focuses on integrating resources related to Zero-Knowledge Proofs, creating high-quality learning materials and tools to help ZKP enthusiasts worldwide better understand and apply this technology.

Your experiences make you unique, and in cryptography, ZKP can achieve something similar. With ZKP, your knowledge can generate a proof that is uniquely yours. We believe this capability will be a cornerstone of our digital lives in the future. Here, we aim to provide everything related to ZKP, from knowledge to hands-on experience. We hope more people will join us in building the future world together.

ZKPunk 是一个以零知识证明 (zkp) 技术为核心的内容平台,致力于推动零知识证明技术的普及与发展。ZKPunk 专注于整合零知识证明相关的资源,创建高质量的学习内容与工具,帮助全球零知识证明爱好者更好地理解和应用零知识证明技术。

你的经历让你成为独一无二的个体,在密码学中 zkp 也能够做到同样的事情。通过 zkp 你的 knowledge 能够生成仅属于你的 proof。我们相信这样的能力会是我们未来数字生活的关键设施。在这里我们尽可能提供 zkp 相关的一切知识和经验。希望能够让更多的人和我们一起,来共同参与到未来世界的建设中去。

🚀 愿景

By providing high-quality ZKP content and tools, we aim to promote the widespread adoption of ZKP technology and drive the further development of the entire ZKP ecosystem.

通过提供高质量的 zkp 内容与工具,促进 zkp 技术的普及,推动 zkp 技术的广泛应用整个 zkp 生态系统的进一步发展。

正在进行的项目

📔 ZKPedia

ZKPedia

The goal is to build a high-quality ZKP knowledge base that community members can easily access and learn from at any time.

旨在构建一个优质的 zkp 知识库,以方便社区成员随时访问并学习。

💡 ZK Insights

ZK Insight

It is a weekly report in the ZKP field, covering the latest technological advancements, academic papers, and project updates, helping the community stay at the forefront of developments in the ZKP industry.

是一个 zkp 领域的周报,涵盖 zkp 领域的最新技术进展、学术论文和项目更新,帮助社区保持对 zkp 行业发展的前沿洞察。

🏖️ ZK Academy

This part is designed for zkp learners of all levels, ideal for those who want an in-depth and comprehensive understanding of a specific area.

面向各类学习者的 zkp 课程,适合想深入和全面的了解某个方向的学习者。

Plonk course

FRI & Stark course

🔥 Contributors

Thank you for all your contributions!!



贡献流程

  1. Github 上 fork 本 Repo
  2. ./src/zk-everything 下新建一个文件夹,并在文件夹中新建一个 .md 文件,将文章内容写入
  3. src/SUMMARY.md 是前端网站显示的文件组织目录,修改该文件,找到一个合适的放置目录,将文章的本地 .md 文件位置链接过去
  4. 提交 Pull Request
  5. Pull Request 被 merge 后很快就会在 https://learn.zkpunk.pro 网站显示

文章格式

1. 文章元数据

可以添加一些文章的元数据, 如 「作者 (required)」,「标签、联系方式 (optional) 」

> 作者: 如 @Alice https://github.com/Alice
> 标签: 如 Halo2, Nova, STARK, Folding Schema .... # mdbook 暂不支持 tag 功能
> 时间: 2024-10-01

比如:

作者:Alice

2. 文章目录

文章开始之前,可以添加 [TOC] 来让 mdbook 自动生成该文章的 Table of contents(目录)

-----

[TOC]

-----

3. 文章正文

按照常规的 Markdown 格式去写就好

如果想要高亮显示某段文字, 可以使用 mdbook-admonish, 比如:

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

如何添加图片?

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

4. 文章末尾

可以列出 「致谢」 & 「参考文献」

# 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/)

关于 markdown 渲染

众所周知,Github 网站的 Latex 渲染功能非常弱,往往需要一些技巧才能让公式正常渲染。我们使用的 mdbook,不需要给 github markdown 渲染做专门的适配和魔改, 主流 Markdown 编辑器(如 Obsidian, Typora)里的 .md 文件都可以正常渲染

本地 Dev 预览方法:

  1. 安装 Rust

  2. 安装依赖

cargo install mdbook mdbook-latex  mdbook-toc
  1. 运行
mdbook serve --open

Tips :

  • src/SUMMARY.md 会在前端显示所有文件目录及其链接
  • 公式测试:可以在 katex.org 测试. 如果使用 Obisidian notes 编辑公式, 这里不需要任何修改

💡 @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

Hello ZKP

👩‍💻 作者: Jade 🔗 github仓库:awesome-zkp-learning

Introduction

如果你刚入门ZKP,个人推荐从视频课程开始,有老师带着学习,会更容易上手,并且课程也是比较系统的,能对ZKP有一个大致的把握。后续可以深入理论、项目、论文等等。ZKP和密码学、区块链紧密相关,因此这里也推荐了一些相关课程和书籍,而深入密码学又会发现和数学相关,特别是抽象代数、数论的知识,只能说前路漫漫,道阻且长,希望不会劝退你。

本文推荐资料概览如下:

xmind

本文的资料推荐完全是鉴于我个人的学习路径,是从我个人角度的一些推荐。每个人的专业背景与学习方法都有所不同,因此仅供参考。不管怎样,能从这里有所收获都是我莫大的荣幸。

闻道有先后,术业有专攻。我也一直在学习的路上,难免有所不足与错误,欢迎批评指正,与我讨论。

Contents

ZKP Courses

探索零知识证明系列 - 郭宇

如果你想通过博客文章来入门学习ZKP,强烈推荐郭宇老师的系列文章。相信很多人入门ZKP都是从这里开始的(至少我是😂)。推荐按照顺序来进行阅读,同时里面提到的一些概念可以结合 ZKP MOOC(见下一个推荐)中的第一讲Introduction and History of ZKP来进行学习,基本都有对应,不过ZKP MOOC中讲得更理论些。

ZKP MOOC - Zero Knowledge Proofs

如果你想系统了解ZKP,或者刚入门ZKP,这门课程强烈推荐。通过这门课程的学习,你会对ZKP有很深入的理解,同时课程涉及面也比较广。每节课的讲义都非常不错,值得反复回顾与学习。课程官网还给出了每节课的补充资料,可以延伸拓展。

Modern Zero Knowledge Cryptography - MIT IAP 2023

如果你想敲敲代码来学习ZKP,非常推荐这门课程,可以跟着课程学习Circom语言,自己动手写写电路约束。该课程还有课后作业,推荐自己做一做(我的作业是跟着ZK Shanghai 2023课程(可以看作该课程的中文版)做的,在下一条推荐中有我的作业链接,供参考)。

ZK Shanghai 2023 - Icer

如果你觉得直接看上一个推荐的英文课程Modern Zero Knowledge Cryptography有点难度,推荐看这个课程,可以理解为中文版。同时这门课程在讲解过程中也加入了老师的理解,有很多补充和扩展。课程的第7讲第8讲邀请了陆晨博士来讲解,比较偏数学一些,但其中的FFT算法在ZKP中应用还比较多,如果不好理解可以找其他一些资料来补充学习。作为ZKP入门,可以先尝试去理解,后续用到再深入进行研究。

WTF-zk

如果你想了解ZKP的数学原理,这门教程是不错的选择,讲解了ZKP中用到的抽象代数的知识,同时结合python代码,能边学习理论边用编程进行实践。

Blockchain

了解区块链也有助于理解ZKP的应用场景。

区块链技术与应用 - 肖臻

🔗 bilibili课程视频

如果你想深入了解区块链,非常推荐这门课程,课程由浅入深,讲了比特币和以太坊底层原理。

Cryptography Courses

密码学系列课程 - lynndell

这门课程从密码学的常见算法讲起,再讲到零知识证明。每一节课都很硬核,老师的讲义非常棒,值得自己反复研读,强烈推荐。

密码学基础系列

ECDSA多签系列

zk系列

Cryptography I - Dan Boneh

如果你觉得上面推荐的课程密码学系列课程还不够过瘾,强烈推荐这门课程,同时推荐读读这门课程的讲义,非常全面,讲义中的证明比较多,前期可以选择跳过。

Plonk

对ZKP有一个大致的了解后,可以具体来学学一些证明系统,首推Plonk。

理解Plonk系列 - 郭宇

如果你想深入理解Plonk,强烈推荐郭宇老师的这一系列文章。有的文章中会涉及较多的数学公式,推荐自己跟着文章手写推导一遍(或者更多),由于这些置换证明、算术约束、拷贝约束、查表约束等会在很多证明系统中反复用到,因此这里打下扎实的基础还是非常有必要的。

Halo2

在学习了Plonk之后,就可以开始看看Halo2。官方教程The halo2 Book可以作为学习手册进行参考。下面推荐一些不错的课程。

Halo2 - 0xPARC

强烈推荐跟着这门课程来入门Halo2。不仅有理论的讲解,也有编程实践,课上跟着老师敲敲代码,课后再自己独立实现下,或者改改代码实现不同的约束,相信会对Halo2有更深入的理解。

Halo2 - StarLi

这一系列的课程也可以作为上面推荐课程Halo2 - 0xPARC 的补充。

ZKEVM

ZKEVM或者ZKVM是一个非常庞大的项目,个人认为可以从一些介绍视频入手,有个大致的了解,再进行深入代码细节。(👀我还刚刚接触一点,下面是我看到的不错的资料,这里简单的做一些推荐,想更深入学习ZKVM或者ZKEVM,建议另外找更全面的资料)

ZKP Books

Proofs, Arguments, and Zero-Knlowledge - Justin Thaler

关于ZKP的书籍,很多人首推这本书。(👀我还未细看这本书,后续看完补充更详细的描述)

The MoonMath Manual

这本书还是比较全面,涵盖初等代数、抽象代数、椭圆曲线、电路以及 ZKP 的知识,尽可能地不涉及过多的数学理论,同时又和实践进行结合,非常推荐。

Mathematics Books

Algebra

高等代数 - 丘维声

强烈推荐丘老师的这本教材,有上下两册,通过这本书一步一步自然地引入了群、环、域的概念,对入门抽象代数很有帮助。网上也有丘老师的课程视频,可以结合着学习。

抽象代数 - 张贤科

如果你想看抽象代数的中文教材,我觉得这本很不错,带你从群环域到伽罗瓦群,书中也有部分提到ZKP中常用的有限域,但更多还是整个抽象代数的理论知识,对深入理解有限域有很多帮助。如果想要深入研究有限域,推荐阅读有更细化的书籍(下面在Finite Fields中有对应推荐)。

A Book of Abstract Algebra - Charles C. Pinter

如果你想看抽象代数的英文教材,推荐这本。还是比较推荐英文资料,这样在看到一些英文术语时能够直接对应上。

Algebra A Graduate Course

这本作为一些学校的本科教材,也比较推荐。

Finite Fields

ZKP中的大部分证明系统都是基于有限域来进行计算的,因此很有必要深入学习下有限域的理论知识。下面先推荐一些大家都说还不错的书籍。(👀由于我还未细读,后续再补充上这些书籍的描述与区别)

Finite Fields - Rudolf Lidl, Harald Niederreiter, P. M. Cohn

Handbook of Finite Fields - Gary L. Mullen, Daniel Panario

Introduction to Finite Fields and their Applications - RUDOLF LIDL, HARALD NIEDERREITER

Applications of Finite Fields - IanF.Blake, XuHong Gao, Ronald C. Mullin, et al

Cryptography Books

图解密码技术

这本书非常适合密码学入门,图解系列的书籍都比较易懂。

Foundations of Cryptography

这本书有两卷,第I卷是 Basic Tools,第II卷是 Basic Applications。涵盖的内容非常全面,在第I卷的第4章就讲到了ZKP。(👀还未细看这本书,后续看完补充更详细的描述)

Handbook of Elliptic and Hyperelliptic Curve Cryptography - ODED GOLDREICH

(👀还未细看这本书,后续看完补充更详细的描述)

Coding Theory

在FRI中,涉及到Reed-Solomon编码,因此如果要研究这些证明系统相关的细节,就比较有必要学习编码理论相关知识。

Essential Coding Theory

这本书非常推荐,编码理论讲得非常深入。

ZKP Resources

这里推荐一些不错的ZKP学习资源。

探索零知识证明系列

探索零知识证明系列作者:郭宇@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.

从零开始学习 zk-SNARK

核心要点

加密函数:

在同态加密中:

  • 模数 是双方都知道的。它通常是写在加密代码中的
  • 生成元 是一个整数,作为一个基用来生成一系列的数字(密钥,用来对数据进行加密)
  • 就是我们要加密的值

如果上述核心要点已经模糊/忘记的话, 就通读全文

证明的媒介

这里我们先不要去管零知识,非交互性,其形式和适用性这些概念,就从尝试证明一些简单的东西开始。

想象一下我们 (Prover) 有一个长度为10 的位数组,现在要向 verifier(例如,程序)证明这样一个陈述:我的所有的位都被设置成了 1

verifier 一次只能检查(读)一位。为了验证 Prover 的这个陈述,verifier 以某种任意的顺序读取元素并检查其是否确实等于 1 。如果第一次抽样检查的结果是 1,就设置「陈述」的可信度为 ⅒= 10%,否则,如果等于 0,就说明「陈述」是错误的。

验证者继续进行下一轮验证,直到获得足够的可信度为止。假如在一些场景下要信任 prover 需要至少 50% 的可信度,那就意味着必须执行 5 次校验。但假如在其它一些场景下需要 95% 的可信度,就需要检查所有的元素。很明显这个证明协议的缺点是: 必须要根据元素的数量进行检查,如果我们处理数百万个元素的数组,这么做是不现实的。

现在我们来看一下由数学方程式表示的多项式,它可以被画成坐标系上的一条曲线:

上面的曲线对应多项式: f(x) = x³ – 6x² +11x– 6。多项式的阶数取决于 x 的最大指数,当前多项式的阶数是 3

多项式有一个非常好的特性,就是如果我们有两个阶为 d (比如 3 ) 的不相等多项式,他们相交的点数不会超过 d ( 3 个)。 例如,稍微修改一下原来的多项式为 x³ – 6x² + 10x– 5 (注意 , 修改了多项式的最后一个系数,6 改成了 5 )并在图上用绿色标出:

这一点微小的修改就产生了变化很大的曲线。事实上,我们不可能找到两条不同的曲线,他们会在 某段区域内重合(他们只会相交于一些点)。

要找到多项式与 x 轴的交点(即 f(x) = 0),我们就要令 x³ – 6x² + 11x – 6 = 0,等式的解就是和 x 轴的交点: x= 1x= 2x= 3。即图上蓝色曲线和 x 轴相交的地方。

同样,我们也可以令上文中原始的多项式和修改后的多项式相等,找到它们的交点:
联立 : x³ – 6x² + 11x – 6 = x³ – 6x² + 10x – 5 , 得到:

即这两个多项式有一个交点。

任意一个由阶数为 d 的多项式组成的等式,最后都会被化简为另外一个阶数至多为 d 的多项式,这是因为等式中没有能够用来构造更高阶数的乘法。例如:5x³ + 7x² – x + 2 = 3x³ – x² + 2x– 5,简化为 2x³ + 8x² – 3x + 7 = 0。 阶数最多就是 3 (次方)

另外代数的基本原理也告诉我们,对于一个阶数为 d 的多项式最多有 d 个解,至多有 d 个共同点。

所以我们可以得出结论,任何多项式在任意点的计算结果(更多关于多项式求值参考:[Pik13])都可以看做是其唯一身份的表示。

如果一个 prover 声称他知道一些 verifier 也知道的多项式(无论多项式的阶数有多大)时,他们就可以按照一个简单的协议去验证:

  • verifier 选择一个随机值 并在本地计算多项式结果
  • verifier 将 值丢给 prover,让他计算该多项式的结果
  • prover 代入 x 到多项式计算并将结果给到 verifier
  • verifier 检查本地的计算结果和 prover 的计算结果是否相等,如果相等那就说明 prover 的陈述具有较高的可信度

例如,对于一个 阶多项式 , prover 如果不知道该多项式的 d 个解 , 如果把 x 的取值范围定在 1 到 , 那么 x 偶然“撞到”这 d 个结果相同的点中任意一个的概率就等于: (可认为不可能)

与低效的位检查协议相比,新的协议只需要一轮验证就可以让声明具有非常高的可信度(前提是假设 远小于 x 取值范围的上限 (是低阶多项式),可信度几乎是 100%)

这也是为什么即使可能存在其他的证明媒介,多项式依然是 zk-SNARK 核心的部分

even@安比实验室: 这一节告诉了我们多项式的一个重要性质:我们不可能找到共享连续段的两条不相等曲线,也就是任何多项式在任意点的计算结果都可以看做是其唯一身份的表示。也就是说只要能证明多项式上的某个随机点就可以证明这个多项式(只有在知道了多项式,才能算出这个点对于的值),这个性质是我们下面所有证明的核心。

这就是 Schwatz-Zippel 定理,它可以扩展到多变量多项式,即在一个多维空间内形成一个曲面。这个定理会在多个零知识证明方案的证明中反复出现。

问题 :

到目前为止,我们的协议还只是一个很弱的证明,因为协议中并没有采取任何措施去保证参与方必须按照协议的规则生成证明,所以参与方只能互相信任。

例如,prover 并不需要知道多项式,也可能通过其它方式得到正确的答案 (比如偷一个答案)。

而且,如果 verifier 要验证的多项式的解的取值范围不够大,比如我们前文说的 10,那个就可以去猜一个数字,猜对答案的概率是不可忽略不计的。因而我们必须要解决协议中的这个缺陷,在解决问题之前首先来想一下,知道多项式意味着什么呢?

多项式可以用下面的形式来表示(其中 n 指的是多项式的阶): 假设证明者声称他知道一个包含 x=1x=2 两个解的三阶多项式 , 满足此条件的一个有效的多项式就是

多项式的「知识」就是多项式的系数。所谓「知道」多项式就是指「知道」多项式的系数

因式分解

代数的基本定理表明了任意的一个多项式只要它有解,就可以将它分解成线性多项式(即,一个阶数为 1 的多项式代表一条线),因此,我们可以把任意有效的多项式看成是其因式的乘积:

也就是说如果任意一个因式为 0,那么整个等式都为 0,也就是说式子中所有的 就是多项式的所有解

所以这个多项式的解( 的值)就是:0,1,2,在任何形式下多项式的解都可以很轻松的被验证,只不过因式的形式可以让我们一眼就看出这些解(也称为根)

我们再回到前面的问题, prover 宣称他知道一个阶数为 3,其中两个根分别为 1 和 2 的多项式,也就是说这个多项式的形式为: 换句话说 是问题中多项式的两个因式。

因而如果 prover 想要在不揭示多项式的前提下证明他的多项式确实有这两个根,那么他就需要去证明他的多项式 和一些任意多项式 (例子中 )的乘积,即:

也称为目标多项式 target polynomial

换句话说,存在一些多项式 能使 与之相乘后等于 ,并由此得出, 中包含 ,所以 的根中也包含 的所有根,这也就是我们要证明的东西. 算出 的方式最自然的就是直接相除:

如果一个 prover 不能找到这样一个 也就意味着 中不包含因式 ,那么多项式相除就会有余数

例如我们用 p(x) = x³ – 3x² + 2x 除以 t(x) = (x – 1)(x – 2) (即 x² – 3x+ 2 )

注意:左边的式子是分母,右上角的是计算结果。底部是余数(多项式相除的解释及示例可以看这里 [Pik14] )。

我们算出结果 ,没有余数。

_注意:为简化起见,后面我们会用多项式的字母来代替计算结果,如:

多项式可以被因式分解成它的根的因式的乘积。这个性质就意味着,如果一个多项式有某些解,那么它被因式分解后的式子中一定包含这些解的因式。 有了这个性质,我们就可以愉快地去做一些证明啦。

利用多项式一致性检查协议我们就可以比较多项式 p(x)t(x) ⋅ h(x)

  • verifier 挑选一个随机值 , 计算 (即,求值) ,然后将 发送给 prover。
  • prover 计算 ,并对 p(r)h(r) 进行求值,将计算结果 p, h 提供给 verifier。
  • verifier 验证 ,如果多项式相等,就意味着 t(x)p(x) 的因式。

实践一下,用下面的例子来执行这个协议:

  • verifier 选一个随机数 23,并计算 t = t(23) = (23 – 1)(23 – 2) = 462,然后将 23 发给 prover
  • prover 计算 , 并对 p(r)h(r) 进行求值,p= p(23) = 10626,h = h(23) = 23,将 ph 提供给 verifier
  • verifier 再验证 :10626 = 462 ⋅ 23 是正确的,这样陈述就被证明了。

相反,如果 prover 其实不知道真正的 , 而是使用了一个不相干的 ,如 p′(x) = 2x³ – 3x² + 2x ,它并不包含必需的因式, 那么:

  • prover 计算 , 运算出结果 和余数
  • 为了计算出结果 , prover 不得不冒险用余数除以 , 即

不过由于 x 是 verifier 随机选择的,只有极低的概率余数 可以被 整除。如果后面 verifier 要另外再检查 p 和 h 必须是整数的话,这个证明就会被拒绝。

如此校验就同时要求多项式系数也是整数,这对协议产生了极大的限制

这就是为什么接下来我们要介绍能够使余数不被整除的密码学原理的原因,尽管这个原始值是有可能被整除的。

Remark 3.1 现在我们就可以在不知道多项式的前提下根据特定的性质来验证多项式了,这就已经给了我们一些零知识和简明性的特性。但是,这个结构中还存在好多问题:

  • prover 可能并不知道他所声称的
    • 因为 prover 知道随机点 ,他可以先算一下 ,然后选择一个随机值 ,由此计算出 。因为等式是成立的,所以也能通过 verifier 的校验。
    • 因为 prover 知道随机点 ,他可以构造出一个任意的多项式,这个任意多项式与 处有共同点。
  • 在前面的「陈述」中,prover 声称他知道一个特定阶数的多项式,但现在的协议对阶数并没有明确的要求。因而 prover 完全可以拿一个满足因式校验的超级高阶数的多项式来欺骗 verifier

下面我们就要来逐一得解决这些问题。

even@安比实验室:利用因式的性质构造出了一个证明协议,但这个协议存在一些缺陷,主要是由于

  1. 一旦 prover 知道了 ,他就可以反过来任意构造任何一个可以整除
  • 有的公司的 就直接写在开源代码里面 …. 作死 ….
  1. prover 知道了点 的值,就可以构造经过这一点的任意(高次)多项式,同样满足校验
  2. 协议并没有对 prover 的多项式阶数(次数)进行约束

模糊计算

Remark 3.1 中的前 2 个问题是由于 暴露了原始值 而导致的,即 知道了 但如果 verifier 给出的这个 值像放在黑盒里一样不可见的话就完美了,也就是一个人即使不破坏协议,也依然能在这些模糊的值上面完成计算。有点类似哈希函数,从计算结果就很难再回到原始值上

同态加密

这也就是要设计同态加密的原因。它允许加密一个值并在密文上进行算术运算。获取加密的同态性质的方法有多种,我们来介绍一个简单的方法。

总体思路就是我们选择一个基础的(基数需要具有某些特定的属性)的自然数 g(如 5),然后我们以要加密的值为指数对 g 进行求幂。例如,如果我们要对 3 进行加密:

这里 125 就是 3 对应的密文。如果我们想要对被加密的值乘 2,我们可以以 2 为指数来对这个密文进行计算。

我们不仅可以用 2 来乘以一个未知的值并保持密文的有效性,还可以通过密文相乘来使两个值相加,例如 3+2:

同样的,我们还可以通过相除提取加密的数字,例如:5-3

不过由于基数 5 是公开的,很容易就可以找到被加密的数字。只要将密文一直除以 5,直到结果为 1,那么做除法的次数也就是被加密值的数。

比如有一段密文是 125 , 那么 , 除了 3 次得到 1 , hacker 自然知道加密值是 3 , 这毫无加密可言, 所以我们需要 Mod 模运算

模运算

这里就到了模运算发挥作用的地方了。模运算的思路如下:除了我们所选择的组成有限集合的前 n 个自然数(即,01,…,n-1)以外,任何超出此范围的给定整数,我们就将它“缠绕”起来。例如,我们选择前六个数。为了说明这一点,可以把它看做一个有六个单位大小相等刻度的圆;这就是我们所说的范围(通常指的是有限域)。

img

现在我们看一下数字八应该在哪里。打个比方,我们可以把它看成一条长度为 8 的绳子。img

如果我们将绳子固定在圆圈的开头img

然后用绳子缠绕圆圈,我们在缠完一圈后还剩下一部分的绳子。

img

然后我们继续缠绕,这根绳子将在刻度 2 的地方终止。

img

这就是模运算操作的结果。无论这根绳子多长,它最终都会在圆圈一个刻度处终止。因而模运算结果将保持在一定范围内(例子中是 0 到 5)。长度为 15 的绳子将会在刻度 3 的地方终止,即 6 + 6 + 3 (缠 2 个完整的圈并剩下 3 个单位长的部分)。

负数运算类似,唯一不同的地方就是它是沿相反方向缠绕的,如 -8 的取模结果是 4。

我们执行算术运算,结果都将落在这 n 的范围内。现在开始我们将用符号 “mod n” 来表示这个范围内的数。

3 × 5 = 3 mod 6

5 + 2 = 1 mod 6

另外,模运算最重要的性质就是运算顺序无所谓

例如,我们可以先做完所有的操作,然后再取模,或者每操作完一步都去取模。例如 (2 × 4 – 1) × 3 = 3 (mod 6) 就等于:

2 × 4 = 2 mod 6

2 - 1 = 1 mod 6

1 × 3 = 3 mod 6

那么模运算到底有什么用呢?就是如果我们使用模运算,从运算结果再回到原始值并不容易,因为不同的组合会产生一个同样的运算结果

5 × 4 = 2 mod 6

4 × 2 = 2 mod 6

2 × 1 = 2 mod 6

……

设想一下 , 如果没有模运算的话,计算结果的大小会给找出原始值提供一些线索。

除非这里既能把信息隐藏起来,又可以保留常见的算术属性。

强同态加密

我们再回到同态加密上,使用模运算,例如取模 7,我们可以得到:

…………

其中在某些不同的指数下运算得到了同样的结果 , 比如 7 的运算结果都是 3

……

这样就很难知道指数是多少了。 事实上,如果模取得相当大,从运算结果倒推指数运算就不可行了; 现代密码学很大程度上就是基于这个问题的“困难”。

而方案中所有的同态性质都在模运算中保留了下来:

    • 根据密文 6 , 不能推出原文 3
    • 根据密文 3 , 无法推出私钥

(原文)注意:模相除有点难 , 超出范围了, 这里不表。

我们来明确地说明一下加密函数:

  • 是想要加密的值
  • 模数 是双方都知道的, 它通常写在加密代码中
  • 生成元 是一个整数,作为一个基用来生成一系列的数字比如
  • 通常称为密钥,用来对数据进行加密

Remark 3.2 : 这个同态加密模式有一个限制,我们可以将 加密值 乘以 未加密值 ,但不能将两个已经加密的值相乘( we cannot exponentiate an encrypted value)(或者相除),也就是说我们不能对加密值取幂。

在同态加密中,求幂运算会破坏同态的性质,导致加密后的数据无法被正确解密。因此,同态加密不允许对已经加密值进行再次的求幂运算。 Besides, 密文之间的乘法操作可能会泄露有关明文的信息。特别是在某些强同态加密方案中,如果不小心执行操作,可能会导致信息泄露。

虽然这些性质第一感觉看起来很不友好,但是这却构成了 zk-SNARK 的基础。这个限制后面将在“加密值乘法 (Multiplication of Encrypted Values) ”一节中讲到。

  • 通过模运算形成的集合被称为「有限域」,
  • 通过计算指数再进行模运算形成的集合构成「循环群」。
  • 常见的同态加密方式除了整数幂取模之外,还有椭圆曲线上的倍乘。

加密多项式

配合这些工具,我们现在就可以在加密的随机数 x 上做运算并相应地修改零知识协议了。

我们来看一下如何计算多项式 p(x) = x³ – 3x² + 2x

我们前面明确了,知道一个多项式就是知道它的系数,也就是这个例子中知道:1, -3, 2

因为同态加密并不允许再对加密值求幂,所以我们必须要给出 x 的 1 到 3 次幂取加密值:E(x),E(x²),E(x³),那么我们要计算的加密多项式就是:

所以通过这些运算,我们就获得了多项式在一些未知数 处的加密计算结果。这确实是一个很强大的机制,因为同态的性质,同一个多项式的加密运算在加密空间中始终是相同的

我们现在就可以更新前面版本的协议了,比如对于阶数为 d 的多项式:

协议过程

前面提到 : Prover 想要在不揭示多项式的前提下证明他的多项式确实有这两个根,他需要去证明他的多项式 和一些任意多项式 的乘积,即: 也称为 target polynomial

协议过程如下 :

Verifier

  • Verifier 自己取一个随机数 ,作为秘密值
  • 多项式指数 ( )取值为 0,1,…,d 时分别计算出 次幂的加密结果,即: (注意是 次方)
  • 代入 自己计算未加密的 target poly , 留作验证备用
  • 将对 的幂的加密值丢给 prover: , 即
    • 看起来, 目前 Verifier 知道 的阶数

Prover :

  • Prover 想证明它确实有这 2 个根 ( 即有 因式) :
  • Prover 自己计算多项式
  • 使用 Verifier 给的加密值 , 和自己的 的系数 计算 :
  • 同样计算
  • 将结果 (即 ) 和 (即 )提供给 verifier

注: 是加密函数

Verifier

  • 最后一步是 Verifier 校验 就能知道 Prover 到底是否有根 ; 为什么呢 ?
    • 注 : 是 Prover 传的 , 是 Verifier 自己算的 ;
  • 因为如果 成立 (即 成立) , 根据同态性质 , 即 成立 , 就说明 Prover 真的有多项式的解

问题: Prover 计算 , s 是 Prover 不知道的, 那如何计算 呢 ?
1. 郭师: 是一组 mod 过的 key-value , 是双方都知道的 2. 使用的是 而不是 原值 3. ∵
4. ∴

注意:g 是公开的, 双方都知道的 因为证明者并不知道跟 s 相关的任何信息,这就使得他很难提出不合法但是能够匹配验证的计算结果。

尽管这个协议中 prover 的灵活性有限,他依然可以在实际不使用 verifier 所提供的加密值进行计算,而是通过其它的方式来伪造证明。例如,如果 prover 声称有一个满足条件的多项式它只使用了 2 个求幂值 ,这个在当前协议中是不能验证的

even@安比实验室: 利用强同态加密这个工具,构造了一个相对较强的零知识证明协议。但是如上文所述,这里还是存在一些问题—— 无法验证 prover 是否是真的使用了 verifier 提供的值 来构造证明的

ref (IF 图挂了)

  • https://secbit.io/blog/2019/12/25/learn-zk-snark-from-zero-part-one/
  • https://learnblockchain.cn/article/287

Restricting a Polynomial (限制多项式)

上文说到 :

  1. 多项式的知识其实就是它的系数 的知识
  2. 上文的协议无法验证 prover 是否是真的使用了 verifier 提供的值 来构造证明

协议中, 我们通过对秘密值 s 的幂的加密值再进行求幂来对系数进行“赋值”。我们已经限制了 prover 对 s 幂的加密值的选择, 但是这个限制并不是强制的 ,也就是说,prover 可以使用任何可能的方法找到满足下面等式的值

https://arxiv.org/pdf/1906.07221.pdf

再用寻找到的 来代替 交给 verifier。 verifier 还是验证 是否成立 , 自然成立, 此时 cheat 成功

所以 verifier 需要能够知道 prover 给出的 就是用 s 幂的加密值 计算的, 而不是其它值算的

来看一个简单例子: 由 1 个变量和及其系数组成的一阶多项式 : 对应的加密值为 。这里我们要做的就是确保 prover 是拿 的加密值 而不是其他值与其系数 c 做同态相乘的。所以结果一定是这个形式(c 为任意值): 解决这个问题的一种方法就是用另一个“变换”的加密值做同样的操作,充当类似算术中“校验和”(Checksum) 的作用,以此确保结果是原始值的求幂值。

这个是通过 Knowledge-of-Exponent Assumption (简称 KEA) 方法来实现的,在 Dam91 中有介绍,更精准一点(注意 2 个字符的不同)说:

Alice 有一个值 ,她想要 Bob 对其进行任意指数的求幂(  is a generator of a finite field group used),唯一的要求是 Bob 只能对 进行求幂,为保证这一点,Alice 要:

  • 选择一个随机数
  • 计算
  • 提供一个元组 给 Bob, 然后让他对这 2 个值执行任意的求幂运算,返回结果元组 ( The α-shift remains the same. i.e. )

因为 Bob 无法从元组 中提取 的值 (暴力破解也难以实现),那么 Bob 只能老老实实地生成有效元组

  1. Bob 选择一个值 ( 可以类比上例的 )
  2. 计算
  3. 返回

有了 Bob 回复的 和自己的 ,Alice 就可以验证等式:

结论是:

  • Bob 在元组的两个值的计算上都用了同一个指数(即
  • Bob 只能用 Alice 原本的元组 来保持 α-shift
  • 构造验证值 的唯一方式是用同一个指数
  • Alice 并不知道 ,这和 Bob 不知道 的原因一样
  • 虽然 c 是被加密的,但它的可能取值范围并不足够大到保持其零知识的性质,这个问题我们将在后面“零知识”那一节解决。

最后这个协议提供了一个证明给 Alice ,Bob 确实是用他知道的某个值对 进行求幂的,而且他也不能做别的任何操作,例如:乘法,加法,因为这样就会破坏 α-shift (α-变换关系)

在同态加密中,求幂是对被加密值进行乘法运算。我们可以应用这个结构到一个简单的系数多项式 的例子中:

  • verifier 选择随机数 ,然后令 , 提供一阶及其 “shift” 的计算值:
  • prover 代入其私有的系数 计算:
  • verifier 验证:

这个结构“限制” prover 只能用 verifier 提供的加密的 进行计算,因而 prover 只能将系数 赋给 verifier 提供的多项式。

现在我们可以扩展这种单项式(monomial) 上的方法到多项式上,因为计算是先将每项的分配分开计算然后再 “同态地” 相加在一起的(这个方法是 Jens Groth 在 Gro10 中介绍的)。

所以如果 一个 的幂及其加密 shifted 就可以计算原始的和 shift 后的多项式,, where the same check must hold. 对于阶数为 的多项式:

verifier : 提供加密值 和他们的 α-shift prover :

  1. 计算给定的带有 的幂的 encrypted polynomial :

  2. evaluates encrypted “shifted” polynomial with the corresponding α-shift of the powers of :

  3. 将计算结果 发给 verfier

verfier 校验 :

前面的多项式例子 就变成了:

现在我们就可以确保 prover 是用了 verifier 提供的多项式而不是其它值做计算的了,因为别的方法不能够保持 α-shift 变换。 当然如果 verifier 想要确保在 prover 的多项式中排除了 的某些次幂,如 , 他就不提供对应的密文及其变换:

与前面的协议相比,我们现在已经有了一个比较健壮的协议。但是尽管已经做了加密,在 零知识 性质上也还依然存在一个很明显的缺陷:

即即使理论上多项式参数 是一个很广的取值范围内的值,在实际中, 这个范围可能很有限(比如前例中的 6),这就意味着 verifier 可以在有限范围的系数组合中进行暴力破解,获取 的知识 , 最终计算出一个与 的答案相等的结果 :

比如 将每个系数的取值范围定为 100,多项式阶数为 2,那么大概只会有 100 万种不同的组合,可以认为 暴力破解 的密钥只需要少于 100 万次的迭代

更重要的是,对于一个安全的协议, 即使在只有 1 个系数,值为 1 的例子中,安全协议也必须能够保证其安全 !!!

even@安比实验室: 有了 KEA,就可以约束 prover 只能通过用 verifier 提供的加密值去构造证明了。严格点讲,这里是用的是 KEA的扩展版本,叫做 The q-power Knowledge of Exponent Assumption.

Zero-Knowledge

上文说到 能从 发送的数据中暴力破解 ,来看一下 those provided values (the proof) :

双方都参与到了下面的 checks :

  1. (poly has roots of )
  2. (poly of a correct form is used)

问题是我们如何更换(一种新的)证明 (alter the proof) 使得这些 checks 依然有效,同时又保证没有知识能被提取?

Chap-1 给了一个提示: 我们可以使用随机值 (delta)来 “shift” 这些值, 如
现在,为了提取知识,就必须首先要知道一个不可知的值 δ。并且,这种随机化在统计学上与随机值没有什么区别。 (原文: in order to extract the knowledge, one first needs to find δ which is considered infeasible(不可行的). Moreover, such randomization is statistically indistinguishable from random.)

为了保持这种关系,我们在 的 checks 中验证一下。等式的每一边都有 prover 提供的值 , 如果我们用 来“变换” 每一个值,那么等式应该可以保持相等

Concretely (具体来讲),就是 prover 选择一个随机值 ,并用它对证明中的值进行求幂 (and exponentiates his proof values with )

不要怕, 我们在前面都已经见过了

and provides to the for verification: 合并一下(consolidation), 可以看到校验的等式依然成立 (the check still holds) :

注意零知识是如何轻而易举地融入到这个结构中去的,这通常也被称为“无成本的”零知识

even@安比实验室: 借助这个”无成本的”技巧,就可以轻松实现 zero-knowledge 了。但是这里实现零知识的方法和实际中的 Pinocchio 协议,还有 Groth16 方案略有不同。实际方案中是用乘法乘以

Non-interactivity & Distributed Setup

到现在为止,我们已经讲完了一个交互式的零知识方案。但为什么我们还需要有非交互式呢?因为交互式证明只对 original 有效,其他任何 都不能信任这个 proof,因为:

  • 可以和 串通,告诉 secret params ,有了这些参数 就肆意伪造 proof 来四处行骗
  • 也可以使用同样的方法自己伪造 proof
  • 必须保存 直到所有相关证明被验证完毕,这就带来了一个可能造成秘密参数泄漏的额外攻击面 (which allows an extra attack surface with possible leakage of secret parameters)

因而 就需要分别和每次每个 都做交互来证明一个 statement(该多项式的知识)

尽管 交互式证明 有它的用处,例如一个 只想让一个特定的 (称为目标 verifier,更多的信息参见 JSI96 )确信,就不能再重复利用同一个证明去向别人证明这个声明了,但是当一个 prover 想让众多的参与者同时或者永久地确信的话,这种方法就很低效了。 prover 需要保持一直在线并且对每一个 verifier 执行相同的计算

因而,我们就需要一个可以被重复使用,公开,可信,又不会被滥用的秘密参数

Pairing: Multiplication of Encrypted Values

Cryptographic pairings (bilinear map) is a mathematical construction, denoted as a function

它被给予一个数据集中的 2 encrypted inputs (e.g. ) , 可以将他们确定性地映射到另一组不同的输出数据集上的它们的乘积,即

因为源数据集和输出数据集(通常被称为一个 group )是不同的,所以一个配对的结果不能用做其他配对计算的输入。我们可以将输出集(也称为“目标集”)视为“不同的宇宙”。因而我们不能用另一个加密值乘以结果,而且配对这个名称本身也表明了,我们一次只能将两个加密值相乘

even@安比实验室: 换句话说,配对只支持 x * y 这种两个值的乘法,但不支持三个或以上的值相乘,比如不支持 x * y * z

Pairing 类似于一个 ,将所有可能的输入值映射到可能的输出值的集合中的一个元素上,通常情况下这个过程是不可逆的

注意:乍一眼看过去,这个限制可能会阻碍相关功能的实现,但在 zk-SNARK 中这反而是保证安全模式的最重要性质,参见前文 remark 3.3

配对函数 可以初步(and technically incorrect)类比(mathematical analogy) 成: “交换(swap)” 每一个输出的基数(base) 和 指数(exponent) 的操作,使得基数 在交换过程中被修改成了指数的方式,即 , “被转换”的两个输入一起被修改了,这样原始值 就在同一个指数下相乘了,即:

e(g^\textcolor{red}{a},g^\textcolor{red}{b}) =a^g \cdot b^g =(\textcolor{red}{ab})^g

因而因为基数(base) 在“转换”中被修改了,所以在另一个配对中不能再使用这个结果 ( 即: )构造出想要的加密乘积 了。配对的核心性质可以表示成下面的等式:

Note:配对操作是通过改变椭圆曲线来实现这些性质的,现在我们用的符号 就代表曲线上一个由生成元 自相加了 n 次的点,而不是我们前面用到的乘法群生成元。 The survey DBS04 provides a starting point for exploration of the cryptographic pairings.

Technically, 配对的结果是目标集(target set) 的不同 generator 下原始值(raw value) 的加密产物(encrypted product),即 。 因此它具有同态加密的性质,例如,我们可以将多个配对的加密乘积加在一起:

注意:配对操作是通过改变椭圆曲线来实现这些性质的,现在我们用的符号 就代表曲线上一个由 自相加了 次的点,而不是我们前面用到的乘法群生成元。 DBS04 这个 survey 提供了学习 Pairing 的 starting point

Trusted Party Setup

有了 cryptographic pairings,我们现在就准备去设置安全公开且可复用的参数了。假定一下我们让一个诚实的参与方来生成秘密值 . 一旦 / 的幂及其对应的 α-shift 被加密,那么原始数据就必须要被删除 ( ) :

这些参数通常被称为 common reference string (CRS) . CRS 生成后,任何的 都可以使用它来构造 非交互式的 零知识证明协议。CRS 的优化版本将包含目标多项式的加密值 (While non-crucial)

CRS 分成两组 :

  1. proving key (alse called evaluation key) :
  2. verification key :

使用 Pairing 就可以将 加密值相乘 (记得第一节说过, 加密值不能直接相乘, 会破坏同态的性质), 就可以在协议的最后一步验证多项式了 (有了 verification key 就可以处理从 那里得到的加密多项式的值 :

  • 在加密空间中校验
  • Chech polynomial Restriction : Recall what is [[#Zero-Knowledge]] :

Trusted MPC

尽管受信任设置很有效率,但众多 CRS 用户也必须要相信生成者确实删除了 α 和 s ,这一点没有办法证明(proof of ignorance 是一个正在积极研究的领域 DK18),所以这种方法依然是无效的。因而很有必要去最小化或者消除这种信任。否则一个不诚实的参与方就可以构造假证明而不被发现。

一种解决办法就是由多个参与方使用前面小节中介绍的数学工具来生成一个组合式CRS,这样这些参与方就都不知道「秘密」了。下面是一个实现方案,我们假设有三个参与者 Alice,Bob 和 Carol ,对应为 A,B 和 C,其中 i 为 1, 2, …, d:

  1. Alice 选择随机数 ,然后公开她的 CRS:
  2. Bob 选择他的随机数 ,然后通过同态乘法结合 Alice 的 CRS:
  3. 然后公开两方 Alice-Bob 的 CRS 结果:
  4. Carol 用她的随机数 做同样的事:
  5. 然后公开 Alice-Bob-Carol 的 CRS:
  6. 这个协议最后我们就获得了一个混合的

除非他们串谋,否则参与者们互相之间并不知道其他人的秘密参数。实际上,一个参与者必须要和其它所有的参与者串谋才能得到 sα,这样在所有的参与者中只要有一个是诚实的,就没有办法伪造证明。

注意:这个过程可以被尽可能多的参与者重复完成

有一个问题是如何验证参与者在生成 CRS 时用的随机数值是一致的,因为攻击者可以生成多个不同的随机数 ,然后代入这些不同的随机数去执行 s 的不同次幂计算(或提供随机数作为一个 CRS 的扩充),从而使 CRS 无效或者不可用。

庆幸的是,因为我们可以使用配对来乘以加密值,所以我们就可以从第一个参数开始逐一执行一致性校验,并且确保了每个参数都源于前一个。

我们用 s 的 1 次幂作为标准来校验每一个其它次幂的值与之是否保持一致 :

  • 例如 :
    • 2 次幂:
    • 3 次幂:

我们现在再验证一下前面步骤中 α-变换后的值是否正确:

  • 例如:
    • 3 次幂:

范围的缩写形式,在后面会经常看到

当我们在验证每一个参与者秘密参数的一致性时,要注意参与者生成 CRS 的过程并没有强制后一个参与者(就是我们例子中的 Bob 和 Carol)都要使用前面已经公开的 CRS。因而如果一个攻击者是链上的最后一个参与者,他可以像链上的第一个参与者一样忽略前面的 CRS 随便构造一个有效的 CRS,这样他就变成了唯一一个知道秘密 sα 的人。

为了解决这个问题,我们可以额外再要求除了第一个以外的每一个参与者去加密然后公开他的参数。例如,Bob 同样公开了 :

这就可以去验证 Bob 的 CRS 是乘以了 Alice 的参数后正常获得的, :

同样的,Carol 也必须证明她的 CRS 是乘以了 Alice-Bob 的 CRS 后正常获得的。

这是一个健壮的 CRS 设置模式,它并不完全依赖于单个参与者。事实上,即使其它所有的参与者都串谋了,只要有一个参与者是诚实的,他能够删除并且永远不共享它的秘密参数,这个 CRS 就是有效的。所以在设置 CRS (有时候被称为仪式 Wil16)的时候有越多不相关的参与者参与,伪造证明的可能性就越低。当有相互竞争的参与方参与的时候,就几乎不可能伪造证明了。这种模式能够包容其他一些怀疑这种 setup 可识别性的不受信方因为校验步骤确保了他们不会破坏(这里也包括很弱的 αs 的使用)最终的 CRS。

even@安比实验室: 现在有一些zkSNARK方案支持可升级的 CRS,任何怀疑CRS的参与方都可以对CRS 进行更新。此外还有一些 zkSNARK方案支持 Universal CRS,用不着对每一个电路进行受信任设置,而是只需要全局完成一次即可。除此之外,大量无需 Trusted Setup 的方案正在被充分研究。

Succinct Non-Interactive Argument of Knowledge of Polynomial

We are now ready to consolidate the evolved zk-SNARKOP protocol. (准备整合演进的 zk-SNARKOP 协议) , now denotes a set

我们已经明确 target poly 的多项式阶数 :

Setup

  • 挑选随机值
  • 计算加密值 , ,
  • 生成 proving key (和上面相同)
  • 生成 verification key (和上面相同)

Proving

  • 分配多项式系数 (即知识),
  • 自己求多项式 (一般用 FFT 完成 ?)
  • 代入 计算多项式 的值
  • 代入 计算变换多项式 的值
  • 选择随机数 (“零成本“的 zero-knowledge)
  • 构造随机化的证明(randomized proof) :

verification :

  • Parse proof(解析证明) as
    • 我觉得这里的表述有问题, 因为 是不知道 的(也不需要知道) , 用零知识武装自己的关键工具, 不需要解包或还原 只需用 Pairing 验证证明的一致性 :
  • 验证多项式约束:
    • —————— 保证 确实用了 提供的
  • 验证多项式系数:
    • —————— 保护了 , 实现了零成本 Zero-knowledge

Remark 3.3 如果 pairing 的结果有可能在其它类似的乘法协议中被复用,那么这里就完全没有安全性可言了,因为这样的话 可以自己构造 ,

这里我理解就是 拿到了并复用了, 然后他可以发送 作为 的值来 cheat

这样也可以通过“多项式约束”的检查: —— 因为这是个恒等式, 去验证一个 “恒等式” 没有任何意义 —— 结果永远是 Accept .

Conclusion

我们用 zk-SNARK 协议来解决多项式问题的知识,不过这是一个有局限的例子。因为大家可以说 只要用另外一个有界的多项式去乘以 就可以很容易得构造出一个能够通过测试的多项式 ,并且这种结构也是有效的。

知道 有一个有效的多项式,但是并不知道是哪一个。我们可以利用多项式的其他性质添加额外的证明,如: 被多个多项式整除,是某个多项式的平方。虽然可能会有一个服务能够接受,存储和奖励所有经过证明的多项式,或者有一个需求,加密计算某种形式的未知多项式。然而若有通用方案就可以支撑无数的应用。

even@安比实验室:总结一下这篇文章中一步一步解决了下面的几个问题:

  1. 保证 prover 的证明是按照规则正确构造的 ——> KEA ( )
  2. 保证知识的零知性 ——> “无成本的” 变换
  3. 可复用证明 ——> 非交互式
  4. 非交互中如何设置安全公开且可复用的参数 ——> 参数加密,verifier 借助 airing 进行验证
  5. 保证参数的生成者不泄密 ——> MPC’s Setup

至此,一个用来证明多项式知识的完整的 zk-SNARK 协议就构造出来了,不过现在的协议在通用性上依然还有很多限制,后面的文章将继续介绍如何构造通用的 zk-SNARK。

Ref :

  • https://secbit.io/blog/2020/01/01/learn-zk-snark-from-zero-part-two/
  • https://medium.com/@imolfar/why-and-how-zk-snark-works-2-proving-knowledge-of-a-polynomial-f817760e2805
  • https://medium.com/@imolfar/why-and-how-zk-snark-works-3-non-interactivity-distributed-setup-c0310c0e5d1c

Computation

Let us consider a simple program in pseudocode:

Algorithm 1: Operation depends on an input 
—————————————————————————————————————————————————————————
function calc(w, a, b)         
    if w then         
        return a × b         
    else         
        return a + b         
    end if         
end function

Therefore we need to find a way to convert a program into the polynomial form , like this

Executing and evaluating will yield the same result: 8. and would both be resolved to 6. We can express any kind of finite program in such a way.

猜想一下,是否只要是能够用多项式表示的程序都可以做证明?

Single Operation

Any computation at it is core consists of elemental operations of the form:

If we can represent operand values as polynomials (and we indeed can as outlined) then through the arithmetic properties, we will be able to get the result of an operation imposed by an operand. (如果我们可以将操作数的值表示为多项式(我们也确实可以这么做),那么利用算术属性,我们就能够得到操作数的计算结果了。)

@Even : 回忆一下,在本系列的第一篇——多项式的性质与证明中,我们曾经说过“任何多项式在任意点的计算结果都可以看做是其唯一身份的表示。”

反过来当我们知道某个多项式的时候,是不是也就意味着我们知道多项式上某个点的取值。这就是借助多项式来完成证明的依据。

Enforcing Operation

如果一个 prover 声称有某 2 个数字的乘积,verifier 要怎样去验证呢?

Recap computation form, 我们也可以将其表示为一个运算多项式 :

在计算过程中, 如果操作数(operands)结果(output) 都能用多项式的形式正确地表示出来,那么 就应该成立

也就表明, 当取值为 时, 多项式 成立,

即该多项式一定有一个根 , 因此,这个多项式里面一定包含因式(cofactor) , 这就是我们要证明的目标多项式(target polynomial) ,即

For example, let us consider operation:

可以用一个简单的多项式表示它: ,即

运算多项式就变成了 :

因而如果 用多项式 来代替 因其依然可被 整除,所以 就认可其是有效的

相反,如果 prover 尝试用 , 即 来代替输出值去欺骗 verifier ,即 ,那么运算多项式就变成了 , 这个多项式并没有 的解,因而 不能被 整除:

因而 不会接受这个计算结果(就像**因式分解**这一章描述的那样)

在前面的协议中,我们要证明的多项式是 ,这里我们把 替换成 , 这仍然是被 承认有效的。这里目标多项式 的根就是对应能够计算出数学表达式的值的

上面例子里面取 作为运算编码的位置, 1 可以换成任何别的值,比如说 .. 在 [GGPR] 与 [PHGR] 论文中,这个取值是一个随机值,被称为 “root”

Proof of Operation

前面多项式的 SNARK一章,我们已经能够证明多项式 的知识了,只不过现在要计算的是三个多项式 的知识。我们可以定义 ,但这里存在两个争议点。

  1. ① 在我们的协议中, 证明阶段是不能做加密值乘法计算的 (即 ),因为 Pairing 只能用一次(不能复用, 会有安全风险?) —— Pairing 要用在校验多项式的约束上
  2. ② 这里给证明者留下了一个可以修改多项式结构(修改知识) 但依然保留有效因式 的机会,for example or or even —— 只需要 有一个根 就可以骗过 , 这样是不行的 !

所以 必须要 分别提供 多项式 值的证明,即协议必须修改要证明的多项式的知识( knowledge of polynomial must be adjusted.)

In essence(本质上), 在加密空间中要验证的是 .

即使 可以用 Pairing 来执行乘法(multiplication),但在 Pairing 中做减法 ( ) 是非常昂贵的计算(would require to find inverse of ),所以咱们把 移到右边:

在加密空间中, 的验证就可以转换成:

Red Part: recall that the result of cryptographic pairings supports encrypted addition through multiplication, see section on pairings.

保持 setup 阶段不变,协议更新为:

这个协议就能够证明两个值相乘的计算结果是正确的了。

你可能注意到了在这个新的协议中我们放弃了 - 零知识 部分。这么做是为了简化协议, 后面的章节我们会再变回零知识 ~

even@安比实验室:上面例子里面取 这个特殊值作为运算编码的位置。当然这里的 1 可以换成任何别的值,比如说换成 等等。在[GGPR] 与 [PHGR] 论文中,这个取值是一个随机值,被称为 “root”

名词定义

operand : 符号左边叫 left operand , right operand

  • 是具体的操作数, 比如 里的 a & b ; 里的 2 & 3

oprand polynomials : l(x) and r(x).

  • left operand polynomial (green) 几个约束等式的操作数左边竖列, 构成的 poly 叫 left operand polynomial
  • right operand polynomial (blue) ….

output polynomials : 等式右边的所有 Output 操作数 竖列 构成的 poly 叫 output polynomials

Multiple Operations

We can prove a single operation, but how do we scale(拓展) to prove (which is our ultimate goal)? Let us try to add just one another operation. Consider the need to compute the product: :

来看一个有三个乘法运算的例子 2 × 1 × 3 × 2,它按照下面的步骤执行:

我们要把它们表示为多项式,对于 相应的要 。 即通过点 , 同样的:

we use Polynomial Interpolation to represent these.

Interpolation Result :

Multi-Operation Polynomials

Now we have operand polynomials , let us see step-by-step how the correctness of each operation is verified.

Recall that a verifier is looking for equality .

本例中,计算是在点 处被表示出来的,所以 target poly 在这些点处必须 evaluation 为 ,换句话说, 的根 root 必须是 1,2 和 3,它的基本形式就是:

在实际过程中, 一般是放到单位根 root of unity —— 里的

Firstly, are multiplied which results in:

Secondly, the is subtracted from the result of which is :

已经可以看出每一个 operands multiplication 都对应了正确的结果。最后一步 要算出一个有效因式:

通过长除法(long division) 可以算出: :

自己代入 可以自己计算 : > PS: 这里为了简化过程, 省略了完整协议中的 `δ-zero-knowledge` 和 `α-shift`

现在显然 ,这就是我们要证明的内容。

这里只用了一组多项式 就将所有计算的约束关系表示出来了,有几步计算, 也就对应着目标多项式 要有几个根 (这里我这么理解: 计算的步数多了, 那么 的根也就多了, 比如可能是 , 因为约束等式的行数多了, 也就需要同步约束这些等式符合所有的计算完整性验证 )

当前的协议似乎存在一些缺陷,多项式只能证明 拥有一组多项式