最接地气的零知识证明解释（下）：神奇的机器

本文翻译自Aviv Zohar的博文《The Incredible Machine》。这是小编看过的最接地气、最好理解的“零知识证明”解释。推荐大家一定要看！文章分为两部分，下文是第二部分，第一部分请查看最接地气的零知识证明解释（上），一定要看！
上一回最接地气的零知识证明解释（上）说到，小C知道小A和小B造假，很生气……
神奇的机器和非交互证明
小C越想越气，他很喜欢解出数独谜题的那种爽感，也喜欢之前和小A、小B一起玩零知识证明的挑战，但小A、小B却打破了他的信任，他想找出一个检验零知识证明的方法。小C拼命想啊想，甚至失眠了数晚，终于让他想出了一个方法。然后他去找小A和小B，给他们展示自己的新发明“zk-SNIPM（零知识数独非交互式证明机）”。
这台机器本质上是小A和小B的测试的自动化版本。小A只需要把卡片放在传送带上，然后把数独的解放到机器上。机器会自动选择按行、或列、或九宫格来收集卡片，然后放到袋子里打乱顺序，袋子会通过传送带从另一边再送出来。然后小A就可以当着镜头的面拆开袋子展示里面的卡片。
这台机器有一个控制面板，上面有一长串的旋转钮，用来指示每次测试选择行还是列或者九宫格。
小C设置好了测试顺序选择，并且把机器的控制面板焊死了，以保证小A和小B不知道他选择了怎样的测试顺序。这下小C很放心了，他完全信任自己的这台机器，并把它交给小A和小B，让他俩在下次直播中用这台机器来证明。他很确定有了这台机器，小A和小B再也无法作弊了。
仪式
小A和小B很嫉妒小C的这台机器，并且也想用这台机器来验证数独的解（包括小C自己出的谜题）。问题是只有小C知道这台机器设置的测试顺序，他们没办法用它来验证小C的解，因为小C知道自己设置了怎样的测试顺序，有可能小C没有解出的题也能通过测试。小A建议小C把控制面板打开，把之前的设置清除，大家一起重新设置控制面板上的测试顺序，他把这个过程叫做“可信任的设置仪式”。
小A建议把这台机器放在一个黑屋子里，并把旋钮上的标签撕掉。他们三人分别进入这个屋子（小B还建议大家蒙住眼睛进入屋子以保证选择的随机性），并将机器上的旋钮旋转到一个随机的位置，顺时针旋转三分之一圈，或者顺指针旋转三分之二圈，或者保持原样，随便怎样都行。这样，没有人知道每个旋钮的最终设置（即测试顺序），即使其中两个参与者串通一气，没有另外一个人的帮助，他们也不会知道旋钮的最终状态。这个仪式结束后，他们一起把控制面板焊死了。
破解机器
一天下午，小B和小C因为有事要出远门，只有小A守着机器，他就想试试这台机器是不是真的像小C吹的那样安全。想了一会儿后，他决定给机器输入一些错误的题解，以此来测试机器的验证顺序。首先，他选择了一个他能解开的谜题，输入机器，观察机器是否接受这个解。然后，他不断重复这个过程，但他改变了输入的解，只在每行里包含1-9的数字，但每列和每个九宫格区域没有严格遵循包含数字1-9，且每个数字不重复的规则。机器没有报错，检验通过了，这意味着可以用这个方式来测试出机器里预先设定的检验顺序。
小A挺沮丧的，这个验证方式看来并不完美啊。
数独与零知识证明
上面数独游戏的证明就是零知识证明，证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明就是既能充分证明自己是某种权益的合法拥有者，又不把有关的信息泄露出去——即给外界的“知识”为“零”。
游戏中用来自动化验证数独题解的机器zk-SNIPM（零知识证明非交互式证明机）就像是“实体化的”zk-SNARKs（零知识非交互式证明）算法。zk-SNIPM存在一定漏洞，但可以通过设计进行改进，比如，用复印机把卡片的组合复印下来，然后同时验证这些卡片的行、列、九宫格区域。这样就很难通过试错的方式来破解机器。
小A和小B在直播中使用的验证方式，就像是“交互式零知识证明”。小B在小A提交答案后，不断地进行随机试验（即选择行、列或任意一个九宫格区域进行验证，证明每次选择的区域都包含数字1-9，并且数字不重复）。在这种情况下，如果两个人事先串通，那么在小A没有真正解出题的情况下，小B能够造假证明小A知道答案了。
非交互式证明则不需要小A和小B有任何交互，解决了验证者和证明者之间的造假问题，它通过预先将“密码”和“程序”隐藏在“机器”中，自动算出一个证明。