零知识证明

零知识证明（Zero Knowledge Proof）由S.Goldwasser、S.Micali 及 C.Rackoff于1985年在论文《The Knowledge Complexity of Interactive Proof Systems》（交互式证明系统中的知识复杂性）首次提出，是一种用于证明者在不泄露任何其他信息的情况下证明其掌握知识正确性的密码学协议。零知识证明目前有多种实现方式，如zk-SNARKS、zk-STARKS、PLONK以及Bulletproofs。每种方式在证明大小、证明者时间以及验证时间上都有自己的优缺点。

该协议的一方称为证明者（Prover），用 $P$ 表示；另一方称为验证者（Verifier），用 $V$ 表示。零知识证明指 $P$ 试图使 $V$ 相信某个论断是正确的，但却不向 $V$ 泄露任何有用的信息，即 $P$ 在论证的过程中 $V$ 得不到任何有用的信息。零知识证明除了证明证明者论断的正确性外不泄露任何其他信息或知识。
零知识证明一般包含以下阶段：

承诺（Commit）：证明者针对命题做出承诺，该承诺等待验证者提出挑战并进行验证。
挑战（Challenge）：验证者选择随机数（即上述例子中的行、列或格）对提出的承诺进行挑战。
回应挑战（Response）：证明者将收到的随机数结合给出的承诺（承诺不可修改），返回挑战的回应。
验证（Verify）：验证者验证挑战的回应是否正确，如果错误，则证明失败。

证明者与验证者重复执行以上步骤，直到可以相信的概率达到验证者接受的条件，证明成功。
零知识证明具有以下特点：

完备性（Completeness）：如果证明者和验证者都是诚实的，并遵守证明过程的每一步进行正确的计算，则该证明一定会成功，验证者也一定能够接受证明者；
合理性（Soundness）：没有人能够假冒证明者，从而使这个证明成功；
零知识性（Zero-Knowledge）：证明过程执行完后，验证者只会得悉"证明者拥有这项知识"，而没有获得关于这项知识本身的任何信息。

零知识证明的例子

山洞问题

如果要用一个概念直观地解释零知识证明如何证明用户拥有数据，可以想象一个山洞只有一个入口，洞里面有两条路（路径A和路径B），这两条路由一扇门连接，要说出密码才能通过这扇门。

Alice希望向Bob证明她知道开门的密码，但不想将密码透露给Bob。因此，Bob需要站在山洞外，Alice从其中一条路走进山洞，而Bob并不知道她选了哪条路。接着，Bob指定Alice从其中一条路回到山洞入口（注：这是随机选择的）。

如果Alice最初选择从路径A走到门口，但Bob让她从路径B回来，唯一的方法就是穿过那扇门，而穿过门必须知道密码。为了充分证明Alice真的知道门的密码，而不是运气好刚好选到了同一条路，这个过程可以反复重复好几次。

这一步操作完成后，Bob就可以非常确信Alice知道门的密码，与此同时Alice也不用向Bob透露密码是什么。虽然以上只是零知识证明机制简单的概念演示，但真正的零知识证明运用的是密码学，在不透露数据的情况下证明数据的存在。在这个山洞的示例中有一个输入数据，一条路径和一个输出数据。在计算机中也存在类似的系统和电路，传入数据，数据通过某些电路门之后再输出。零知识证明利用了类似这种电路机制来创建证明。

红绿色盲问题

Q：有两颗形状、大小完全一样的球：一颗红球、一颗绿球，X XX是红绿色盲，Y YY能够向X XX证明这两颗球是一红一绿吗？

A：X左手拿着红球，右手拿着绿球，并在背后不让Y看到，进行交换（或者不交换）两只球
Y能够根据颜色精准判断X是否进行了交换
执行上述操作N次后，即能在X是色盲的情况下，Y仍能够向X证明能这两颗球是一红一绿

数独问题

假设 $P$ 给出一道数独题目，由 $V$ 来完成，但 $V$ 过了很久都未能解出，他怀疑该数独题目没有解，要求 $P$ 证明该题目有解。因此 $P$ 希望在不告诉 $V$ 答案相关的任何信息的情况下证明这道题有解且自己知道这个解。

1）承诺

$P$ 将答案的每个数字写在纸片上，并按照答案摆放(正面朝下)，题目中已有的数字正面朝上，这81个纸片的放置为 $P$ 的“承诺”。

2）挑战

$V$ 不能直接将纸片翻转查看数字，但是 $V$ 可以在行、列、格中任意指定一种验证方式。如图所示， $V$ 选择按照行的方式进行挑战。

3）挑战回应

$P$ 按照 $V$ 选择行验证方式将桌面上每行的9张卡片装入一个袋子里，并且将纸片进行混淆后，把袋子交给 $V$ ，作为挑战的回应。

4）验证

$V$ 打开纸袋可验证每个纸袋里的9张纸片刚好为1 − 9，即 $P$ 在承诺阶段做出的承诺满足“每行1 − 9都出现且只出现一次”的要求，同时在一定程度上说明 $P$ 做出的承诺很可能是一个合法的解（因为随意给出的数字不会满足这一要求，并且在承诺的时候并不知道 $V$ 会选择行、列、格哪种验证方式）。