ZKP 直觉：阿里巴巴洞穴

零知识证明（ZKP）允许证明者向验证者证明自己知道某个秘密（或某个陈述为真），而不泄露秘密本身。它具有三个性质：完备性、可靠性和零知识性。

如果证明者知道秘密，就始终能够说服验证者。遵循协议的诚实证明者将以概率 1（或压倒性概率）成功。验证者不会拒绝有效证明。

作弊的证明者（不知道秘密）除以可忽略的概率外，无法说服验证者。每一轮交互都会降低作弊成功的概率——经过 k 轮后，作弊者的成功概率最多为 2^{-k}。

除了知道该陈述为真之外，验证者不会了解到任何其他信息。形式化地说：存在一个模拟器，它无需知道秘密，就能生成与真实的证明者—验证者交互记录不可区分的记录。验证者不会获得任何额外知识。

一个洞穴中有一条环形通道，中间有一扇魔法门。证明者 Alice 声称自己知道密码。验证者 Bob 在洞穴外等候。Alice 进入洞穴后向左或向右走。Bob 喊出她应从哪一侧出来。如果 Alice 知道密码，她总能从正确的一侧出来。每轮作弊成功的概率为：1/2。

经过 20 轮后，作弊者的成功概率为 2^{-20}，约为百万分之一。知道密码的 Alice 每次都能成功。Bob 永远不会知道密码——他只能看到 Alice 从自己要求的一侧出来。这就是零知识。

交互式 ZKP 要求证明者和验证者之间进行来回交互。非交互式 ZKP（NIZKs）使用 Fiat-Shamir 变换：将验证者的随机挑战替换为对承诺的哈希值（哈希值 = 随机预言机）。这样会生成一段任何人都能验证的单一证明字符串。

如果证明者的策略意味着可以提取出秘密，那么 ZKP 就是知识证明（PoK）。这比仅仅证明某个陈述为真更强。ECDSA 和 Schnorr 签名都是关于知道私钥的非交互式知识证明。

无需发送密码即可完成密码身份验证。无需泄露出生日期即可验证年龄。在不泄露薪资的情况下证明您的薪资处于某个范围内。在区块链中：证明您知道一笔有效交易，而不泄露该交易。

完美零知识：模拟器的输出与真实交互记录完全相同。统计零知识：除非发生可忽略概率的情况，否则不可区分。计算零知识：对于多项式时间验证者不可区分。保证越弱，证明就越高效。

洞穴协议是一个三步协议：承诺 → 挑战 → 响应。形式上称为西格玛协议。大多数实用 ZKP（Schnorr、Pedersen、Fiat-Shamir）都是西格玛协议或它们的组合。这个名称源自消息流图的 Σ 形状。

阿里巴巴洞穴协议经过多少轮后，作弊者的成功概率会低于 1/1000？

ZKP 能够在不泄露秘密的情况下证明知晓该秘密。三个性质：完备性、可靠性、零知识性。阿里巴巴洞穴展示了交互式 ZKP。下一步：西格玛协议和 Schnorr 身份识别。