感觉这个坑会很大，就从合约安全那篇博客挖过来了，不然看的也心烦
写这篇博客也只是对着其他人的成果做笔记来push自己，本文对应的参考链接你们可以自己看这个：The RareSkills Book of Zero Knowledge | RareSkills
0. 瞎写的ZKP概念速通
简单用非数学语言过一下zkp是啥：比如某个人P希望向另一个人V证明某件事，但是P又不希望向V直接或者间接地泄露任何实际信息，这个时候就可以使用zkp去实现这一点
比如P想证明他能解决任何一个数独，但是P不希望泄露他具体是怎么做到的，甚至连数独的结果都不愿意展示给V，那么这个时候P可以这么办：把每一行、每一列、每一个九宫格的所有数字单独装进不同的袋子里（这样应该有9+9+9=27个袋子），此时V只需要检查每个袋子里面是不是都是只出现一次的1~9就可以了
当然，一次成功可能是瞎猫碰见死耗子，所以V可以让P再进行多轮同样的流程，这样概率相乘，如果小于某一个预设的值，那么就可以认为P确实能解决任何一个数独，整个过程中我们把P叫做证明者（Prover），V叫做验证者（Verifier），而过程中这些实际的数独结果叫做见证（Witness）
上述的过程实际上是存在P和V两人的信息传递的，我们一般把这种叫做交互式零知识证明（Interactive Zero-Knowledge Proofs，IR-ZKP），那么与之对应的则是非交互式零知识证明（Non-Interactive Zero-Knowledge Proofs, NIZK）
这次我们浓缩一下，不管是什么情况，我们都可以提炼成这样的场景：已知某公共函数$f$和一个结果值$y$，证明者P希望向验证者V证明他知道一组输入$x$，使得$f(x)=y$成立，同时不泄露$x$的具体值。而NIZK的做法则是这样：证明者P可以运行一个程序$g$，然后运行$g(f,x,y)$，最终得到一个证明$p$，而对于任意的验证者Vn，只需要知道$(f,y,p)$这个三元组就能验证P确实能做到他声明的陈述
1. ZK相关的简单密码学基础
我不会密码学，反正先学着吧
1.1 P/NP问题和ZKP
1.1.1 P/NP问题
首先，让我们回到经典的时间复杂度函数$O(n)$来，然后简单过一下基础：
- 对于时间复杂度为$O(n^c)$的算法（其中$n$为输入大小，$c$为非负常数），我们一般称该算法使用多项式时间
- 对于时间复杂度为$O(c^n)$的算法（其中$n$为输入大小，$c$为大于1的常数），我们一般称该算法使用指数时间
学过初高中数学的同学肯定知道，当$n\to+\infty$的时候，指数函数的增长速度会明显大于多项式函数，所以我们可以知道：使用多项式时间甚至更快的算法我们称其为高效算法，而使用指数时间的算法我们说它代价高昂
那么我们设计算法是为了什么？为了解决问题，对不对？解决一个问题需要我们进行求解，除此之外还要能验证解决方案，不然谁都可以说自己解决了某个问题，但是实际上只是特解满足，那世界就完蛋了
那么以求解和验证分别为平面上的两条轴，记正方向为更简单，负方向为更困难，那么我们就能将所有的问题分为如下四类：易求解易验证、易求解难验证、难求解易验证、难求解难验证，其中第二个可能性纯扯淡，你都求出来了怎么难验证了；除此之外考虑到空间和时间这两个因素，还能扯出更多花样，当然这里不会全部展开
注意这里的“难易度”是根据上面使用多项式时间还是指数时间区分的，也就是说某问题“易求解”表示问题可以在多项式时间内求解，而“难验证”就说明验证需要使用指数级的资源才能完成
除此之外，上面的分类最后也能得到一个结论：求解一个问题的难度至少和验证它的难度相持
顺带一提，前面我们提到了见证（Witness）这个概念，这里补充说明一下：它其实就是你正确解决了问题的证据。它可以不是原问题的解决方案，而是原问题的另一种替代表示方式的解决方案
那么快速过一下：
- 可以在多项式时间内求解，且解决方案可以在多项式时间内验证的问题被称为P类问题
- 只需要多项式空间资源就能解决的问题被称为PSPACE问题
- 可以在多项式时间内验证，但需要指数级资源进行求解的问题被称为NP类问题
这里我们可以发现
P就是Polynomial，也就是多项式的意思，但是需要注意这里的N实际上是Non-deterministic，即非确定性，这个概念和求解/验证使用的图灵机性质有关，但是这里不展开说明（问就是我也不懂），总之请不要说“NP问题就是非多项式问题”这种话，会被笑话的 φ(゜▽゜*)♪
我们可以看到PSPACE问题没有对时间进行限制，换句话说实际上需要指数级资源进行求解和验证的问题也可能是PSPACE问题，那这个难度明显比NP问题大，而P问题相比NP肯定又简单一点，所以我们可以有这样的初步结论：
- 如果某个人拥有指数级的资源用于验证PSPACE问题的见证，那么TA就能轻松求出任何P和NP问题的解，也因此P/NP问题都是PSPACE问题的子集，即$P\subseteq NP\subseteq PSPACE$
注意这里使用了子集$\subseteq$而非真子集$\subset$，实际上是因为目前还没有确定这些子集是否是真子集（举个例子的话就是经典的P=NP问题，我们马上会提到），因此用子集符号来保留集合相等的可能性
现在正在研究的一个问题就是P=NP问题，也就是在问这两个类别是否相等。如果相等，那就说明如果我们能高效地验证某个问题的见证，那么我们就一定能寻找到该问题的高效解（也就是NP→P）
当然，如果证明了P=NP，那么也就说明大部分现代密码学的算法都一定至少存在一个能破解它的高效算法，那肯定会轰动整个业界和学术界，不过目前也是花了很多时间和资源，依旧没能证明P=NP或者P≠NP，总之我们为了实际目的考虑，还是认为P≠NP吧，至少当我们使用现代密码学的时候已经默认了这一个观点
1.1.2 P，NP，布尔公式
P问题和NP问题有一个共同点，就是它们都易于求证，那么我们能否设计那么一个编码方式，它能描述各种不同的问题，不管是问题本身还是解决方案，那样我们就可以方便很多
对于上面的问题，当然可以，比如布尔公式，这样我们只需要验证布尔公式的解就可以验证P/NP问题的解决方案了，而且布尔公式验证十分快，但是对于非常复杂的布尔公式，求解倒是非常麻烦，是一个非常典型的NP问题
将一个问题转化为布尔公式实际上需要一点简单的离散数学的知识，不过这里不展开，毕竟我们这篇文章主要还是要以ZK为重点，至于不懂离散数学的同学可以回去翻翻课本或者找网课再看看
不过由于我们希望验证是快速的，因此构造这个布尔公式必须要在多项式时间内，否则我们构造出的布尔公式也将会是指数级的，进而使得验证见证的时间也是指数级的
不过我们也可以知道我们可以将P/NP问题转化为布尔公式，且如果我们有一个原问题的见证，那么它能被转换为对应布尔公式的变量赋值，且这些赋值能让布尔公式的结果返回True
1.1.3 P，NP，ZKP
其实前面我们已经可以发现ZKP就是在证明一个点：“我知道这个NP问题的一个见证”，于此同时不向你泄露任何有关这个见证的信息。由于NP问题的可高效验证性，你可以轻松验证ZKP说的是对的，但是你就是不知道见证是什么
而为了能让ZKP方便处理，我们前面提到过可以用布尔公式进行建模。不过到了ZK，它变了个名字：布尔电路
所以ZKP本质上就是这样一回事：先将问题转化为布尔电路，然后证明你拥有该电路的有效输入（这就是你的见证），over
当然，本质上ZKP利用的还是知识不对称性，因为求解很难，验证很简单，所以如果某一天真的证明了P=NP，那么NP的见证就会被高效地算出，知识不对称性就会被大幅削弱，ZKP中“隐藏见证”这个基础也名存实亡，现代密码学的困难假设也会崩塌
由于前面我们已经说明过P是NP的子集，因此在之后的内容中我们将只提到NP，因为它包含P
1.2 算术电路
前面我们提到了可以用布尔电路建模来验证NP问题的解，但是有个问题就是布尔电路在运算这块太繁琐了，比如下面的a+b=c：
1 | ((a₄ ∧ b₄ ∧ c₄) ∨ (¬a₄ ∧ ¬b₄ ∧ c₄) ∨ (¬a₄ ∧ b₄ ∧ ¬c₄) ∨ (a₄ ∧ ¬b₄ ∧ ¬c₄)) ∧ |
这谁看了都要头大个几秒，所以与其使用布尔电路对加法进行建模，我们倒不如直接使用加法和乘法（本质就是多次累加），这也就引出了我们这一部分的主题：算术电路
1.2.0 算术电路的简单定义
让我们直接给出算术电路的简单定义：
- 算术电路是一个仅使用加法、乘法和相等关系的方程组。
和前面强调的一样，不管是布尔电路还是算术电路，它们都只用于验证这一用途，即检查提供的输入是否有效，而不是计算电路的解
本质上减法和除法也可以转化为加法和乘法（毕竟是逆运算而已），所以我们只是用加法和乘法是完全OK的
如果我们对输入变量的赋值能使得布尔电路产生True的输出，那么我们称这个布尔电路被满足
与之相对的，如果我们对输入变量的赋值能使得所有的方程都成立，那么我们称这个算术电路被满足
所以换句话说，我们可以认为只有方程组的所有方程都成立，这个算术电路才被满足
举个例子：
1 | 6 = x₁ + x₂ |
这一个二元方程组就是一个简单的算术电路，而它可以被x₁=2, x₂=4这组输入所满足。当然肯定有人会说x₁=4, x₂=2同样成立，这也没错，但是别忘了我们关心的只是“电路是否被满足”这个问题，换句话说就是我们只关注“方程是否有解”而不是“方程的解是什么”
1.2.1 基于Circom的一些表达和运算（符）
下面使用的表达方式主要都是因为Circom是这样表达的，为了后续能写Circom电路方便所以这样表示
以及需要注意：Circom仅支持二次约束，简单来说就是两边表达式最高只能是2次方，如果需要更高次方的约束则
- 算术电路中的变量被称为信号（Signals）
这里我们会使用===这个运算符来表示相等关系，比如a === b+c这一个例子，这里我们会假设b和c都是我们的输入信号，而这一个例子本质上是在断言b+c与a相等，所以你也可以认为上面的例子就是assertEq(a,b+c)这一个意思
上面的操作其实起到了将b+c约束为a的操作，所以我们一般也会把这种相等关系的断言称之为约束（Constraints）
虽然从直觉上讲大于和小于关系也应该可以被称为约束（毕竟在学线性规划的时候就应该这么说过），但是很可惜，Circom没有运算符支持比较约束，任何进行比较的“约束”都需要使用
circomlib的比较模板（比如LessThan(N)），但是这个模板本身是作用于一个$\mathbb{Z}_p$标量场的（是叫BN254吧好像是），而且其使用的是一个有符号整型的语义，所以是可能造成整型溢出的，此处暂不展开为了方便，后续提到“约束”一词我们都认为是使用
===的相等约束
当然信号可以有初始的输入信号，也有作为中间变量的临时信号，所以表达式之间除去约束以外还会存在“赋值”操作，我们通常使用肥箭头<==进行赋值的操作，但是其实肥箭头本质上是由两部分组成的：一般的赋值<--和约束===，当然你可以使用瘦箭头赋值，但是因为缺少针对信号的约束，电路中途检查的时候发生了一点什么情况我就不好说了，所以还是推荐肥箭头
1.2.2 使用算术电路对布尔电路进行建模
前面我们聊到了可以使用布尔电路对算术电路建模，那么这里我们反过来，用算术电路对布尔电路进行建模吧
众所周知，布尔电路最关键的就是三个逻辑门：与（AND）、或（OR）和非（NOT），剩下的就是不同的信号和这些逻辑门的组合了而已，那么我们现在已经准备完毕，可以开始建模了
虽然算术电路和约束都不存在输出，但是这里为了描述方便还是使用赋值来表示输出
1.2.2.0 初始约束
我们首先需要确定输入的信号本身是否就存在一定的约束，在这里是存在的：布尔电路的信号只有1位，也就是说信号的取值只有0和1这两种可能性，因此我们需要进行类似这样的操作才可以进行下一步：
1 | x(x-1) === 0 |
这就能成功约束信号x的值到0和1这两种可能，后续三个逻辑门传入的变量都需要进行同样的操作，还请注意
1.2.2.1 与门
与门一大特点就是遇0则0，所以我们可以用乘法的方式表示：
1 | x(x-1) === 0 |
最终被赋值的t就是信号x和y相与的结果
1.2.2.2 非门
非门就是取值相反，所以可以用减法：
1 | x(x-1) === 0 |
1.2.2.3 或门
或门是遇1则1，那么除去双1的情况，都可以用相加表示，而双1情况要额外减去一个1，好在其他情况都至少有个0，所以：
1 | x(x-1) === 0 |
至此我们就成功实现了两种电路的相互建模
1.3 有限域和模运算
?. ZK电路安全
本质上ZK电路安全和一般的代码安全有些不一样，因为代码安全主要侧重于“代码干了什么”，而ZK电路本身就只是一些声明性质的方程组，所以它更侧重于“电路缺少了对什么的约束”
- 本文作者： 9C±Void
- 本文链接： https://cauliweak9.github.io/2026/10/26/zero-knowledge/
- 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！
我爹
我E神
式神
三极管全能神
Marin
N.E.Seeker