证明、论证以及零知识

本书全面系统地阐述了零知识证明算法的理论 基础，设计方法以及截止到2022年主流零知识证明 算法的分类。从最基础的加密学原理讲起，本书阐 述了不同计算复杂性模型下的简洁交互式论证构建 ，并详细描述了通用程序和可满足性电路之间的转 换，通过多项式承诺方案实现简洁论证以及多项式 承诺方案的多种实现。第1章到第3章介绍基础概念 以及阐述交互式证明依赖强大的随机性。第4章、 第8章、第9章、第10章、第17章，从计算复杂性模 型角度（IP／MIP／PCP／IOP），阐述了交互式论 证系统构建的不同方法和性能。MIP＝PCP，并且多 项式IOP统一了IP、MIP以及IOP。第5章介绍了 Fiat－Shamir算法，将任意公开掷币交互式论证转 化为非交互式论证。第6章介绍如何将通用的图灵 程序转化为电路，并解释了算术电路实例转化为可 满足性电路实例的原因。第7章引入多项式承诺方 案以及低次测试，实现简洁交互式论证的雏形。第 11章、第13章介绍零知识的定义以及零知识实现的 两种方式：承诺－证明以及掩码多项式。第12章、 第14章、第15章、第16章介绍承诺方案，并总结了 多项式承诺方案的三种方式：基于IOP（第10章） ，基于离散对数难问题以及基于配对。第18章介绍 了SNARK的组合和递归。第19章是对本书中讲述的 所有零知识证明算法的分类总结。

第1章 介绍 1.1 数学证明 1.2 我们将学习哪些非传统的证明？ 第2章 强大的随机性：指纹法和Freivalds算法 2.1 Reed-Solomon编码 2.2 算法 2.3 指纹法和Freivalds算法的另外一个角度 2.4 单变量拉格朗日插值 第3章 定义和预备技术 3.1 交互式证明 3.2 论证系统 3.3 定义的鲁棒性和交互的强大 3.4 Sehwartz-Zippel引理 3.5 低次和多线性扩展 3.6 练习 第4章 交互式证明 4.1 协议 4.2 sum-check的第一个应用：#SAT∈IP 4.3 第二个应用：计算图中三角形个数的简单交互式证明 4.4 第三个应用：MATMUT的超高效IP 4.5 超高效MATMULTIP的一些应用 4.6 GKR协议及其高效实现 4.7 练习 第5章 通过Fiat-Shamir获得公开可验证的非交互式论证 5.1 随机预言机模型 5.2 Fiat-Shamir变换 5.3 变换的安全性 5.4 练习 第6章 前端：将计算机程序转换为电路 6.1 简介 6.2 机器码 6.3 第一种将程序转换为电路的技术 6.4 将小空间程序转换为浅电路 6.5 将计算机程序转换为电路可满足性实例 6.6 其他的变换方式和优化 6.7 练习 第7章 第一个简洁的交互式论证——解决电路可满足性问题 7.1 朴素方法：一种针对电路可满足性问题的交互式证明 7.2 电路可满足性问题的简洁证明 7.3 第一个电路可满足性问题的简洁论证 7.4 知识可靠性 第8章 MIP以及简洁论证 8.1 MIP的定义和基本结论 8.2 一个电路可满足性的高效MIP 8.3 深度电路的简洁论证 8.4 从电路-SAT到R1CS-SAT的扩展 8.5 MIP-NEXP 第9章 PCP与简洁论证 9.1 PCP：定义及与MIP的关系 9.2 将PCP编译为简洁论证 9.3 从MIP到第一个长度为多项式的PCP 9.4 电路可满足性问题的准线性长度的PCP 第10章 交互式预言机证明 10.1 IOP：定义和相关的简洁论证 10.2 多项式IOP和相关的简洁论证 10.3 R1CS-可满足性的多项式IOP 10.4 FRl和相关的多项式承诺 10.5 Ligero和Brakedown多项式承诺 10.6 通过多项式IOP统一IP、MIP、IOP 第11章 零知识证明和论证 11.1 零知识的定义 11.2 统计零知识（SZK）证明的局限 11.3 诚实验证者SZK（HVSZK）协议——解决图非同构问题 11.4 诚实验证者SZK协议——解决碰撞问题 第12章 ∑-协议和基于离散对数困难的承诺 12.1 密码学背景 12.2 离散对数知识的Schnorr∑-协议 12.3 同态承诺方案 第13章 通过承诺-证明和掩码多项式实现零知识 13.1 证明长度等于证据的长度加上乘法复杂度 13.2 去除对乘法复杂性的线性依赖：从1P到零知识论证系统 13.3 通过掩码多项式实现零知识 13.4 讨论和对比 第14章 基于离散对数难题的多项式承诺 14.1 承诺规模为线性大小的零知识方案 14.2 承诺是固定大小，求值证明是线性大小 14.3 权衡承诺大小与验证成本 14.4 Bulletproofs 第15章 基于配对的多项式承诺 15.1 密码学背景 15.2 KZG：使用配对和可信设置的单变量多项式承诺 15.3 多线性多项式的KZG扩展 15.4 Dory：具有对数级别验证成本的透明方案 第16章 多项式承诺总结 16.1 同态承诺多项式的批量求值 16.2 稀疏多项式的承诺方案 16.3 多项式承诺方案的优缺点 16.4 其他方法 第17章 线性PCP与简洁论证 17.1 概述：来自“长”结构化PCP的交互式论证 17.2 承诺线性PCP而不实例化 17.3 算术电路可满足性问题的第一个线性PCP 17.4 GGPR：一个大小为O（丨F丨s）的线性PCP，适用于电路可满足性问题和R1CS 17.5 非交互性和公开可验证性 第18章 SNARK组合与递归 18.1 组合两个不同的SNARK 18.2 更深层次的SNARK组合 18.3 SNARK组合的其他应用 18.4 通过递归构建用于迭代计算的SNARK 18.5 通过同态承诺实现迭代计算的SNARK 第19章 实用论证的鸟瞰视图 19.1 SNARK分类 19.2 论证方法的优缺点 19.3 影响具体效率的其他问题 致谢 附录 翻译词汇表 参考文献