3.2.3 场景三：数独挑战
我们知道数独是一种逻辑性的数字填充游戏，玩家必须以数字添进每一格，而每行、每列和每个宫（即3×3的大格）有1～9所有数字，且同一个数字在行、列、对角线中皆不重复。游戏设计者会提供一部分数字，使得谜题只有一个答案，如图3-3所示。
图3-3 数独
小明、小丽、小刚三个好朋友很喜欢玩数独游戏。他们三个经常互相出题给对方做。有时候，他们会找来一些非常难的题互相挑战对方。
1．你行你证明
一天，小明想出了一道非常难的数独题，小丽花了很长时间尝试去解开这个数独，但是怎么都解不出结果。小丽觉得小明在耍她，“这题压根就无解！你做给我看看。”她跑到小明那里抱怨。
“我能证明给你看这题是有解的，而且我知道这个解。”小明淡定地回答道。
小丽想：“等你证明给我看之后，我就把解记下来然后去找小刚，给他也做一下这题。”
不料，小明却说：“我会用零知识证明的方法给你证明我会这解这道题。也就是说，我不会把解题步骤给你看，却能让你信服我确实会解这道题。”
小丽半信半疑，也好奇这个零知识证明的方法。
2．证明就证明
小明准备了81（9×9）张空白的卡片放在桌上，每张纸上写上1～9中的一个数字，然后让小丽闭上眼睛转过身去，随后把这81张卡片小心翼翼地按照解的排列放在桌上，代表谜底的卡片，有数字的那一面朝下放在桌上；那些代表谜面的卡片，有数字的那一面则朝上放在桌上。
3．随机抽查验证
如图3-4所示，放置好所有卡片后，小明让小丽转过身，睁开眼。小明对小丽说：“你不能偷看这些面朝下的卡片。”
小丽很是失望，她原本以为可以看到一个完整的解。
小明说：“我能让你检验这些解，你可以随意选择按照行，或者按照列，或者按照3×3的九宫格来检验我的解。你挑一种吧。”
小丽很困惑，嘴上不住念叨着，然后告诉小明她决定选择按照行的方法来验证，小明接着把每一行的9张卡片收起来单独放到一个麻布袋里。所有卡片都被收起来放在9个麻布袋里（见图3-4）。小明接着摇了摇每个麻布袋，把里面的卡片顺序都打散。最后把这9个麻布袋交给小丽。
图3-4 九宫格与麻布袋
4．不暴露题解的验证方法
“好了，你可以打开这些布袋了，”小明对小丽说，“每个布袋里应该都有正好9张，没有重复数字的，分别是数字1～9的卡片。”小丽打开每个布袋一看，果真是这样，如图3-5所示。
图3-5 装有卡片的麻布袋
“可是，这证明不了什么吧？我也可以这样做给你看。只要保证每一行都是1～9这9张卡片，不去管纵列和九宫格里的数字是不是也都是没有重复的，不就行了？”小丽费解地问道。
小明解释说：“可是我事先并不知道你会按照‘行’还是按照‘列’来收集卡片，或者是按照‘九宫格’。我又不是你肚子里的蛔虫……我是按照题解来放置卡片的。”
小丽仔细想了想小明说的话，确实，一个数独只有在有真正正确的解的情况下，才能保证每一行、每一列、每一个九宫格里的数字都是没有重复的1～9。小明如果真的在骗她，随机抽查至少有1/3的概率可以抓到他在骗人。
5．不信！随机验证多试几次
小丽心里还是有些不服，觉得小明仍然有欺骗她的可能性，所以要求小明再把卡片复原，按照原来的方法，重新选。这样反复验证了几次，每次都选一个不一样的试验方法。试了好多次都是一样的结果。小丽这下不得不承认，小明要么运气非常非常好，每次都能押中小丽会选择哪种试验方式，要么就是他确实知道题的解。同时也很失望，这么多次试验下来，也还是不知道真正的解，她只知道小明放置卡片的排列里大概率每行、每列、每个九宫格都是没有重复的数字，这就说明这题是大概率有解的，同理得证，小明很可能确实知道数独的解。
小刚在看了这种零知识证明的方法后，三个好友养成了通过零知识证明去证明自己知道数独题的解的习惯。毕竟每个人在解题的时候都花了很大工夫，不想轻易地把题解直接告诉别人。虽然每次零知识证明的过程很花时间，但是他们的成就感得到了满足。
6．席卷全球的数独风暴
通过互联网，小明和小丽发现了全世界更多的数独爱好者，他俩决定开一个直播间，直播解数独。为了展现自己的聪明才智，每周开播前，小明在粉丝团里随机抽取一个粉丝递交的数独，直播时，小明会把题解告诉小丽，然后由小丽用零知识证明的方法向观看直播的人们证明这题有解，并且自己知道题解。
7．作弊风波
这一天，小明和小丽准备直播一个非常难的数独，可是小明发现他把解出的答案落在自己家了。时间紧迫，要重新算一遍指定赶不上开播的时间。但是他和小丽还是决定开播。开播前，小明和小丽说：“咱俩假装弄一弄零知识证明，我告诉你一会儿我会怎么选试验方式。你只要确保每次我选的那种试验方式（每行、每列或每个九宫格）里的数字不要重复就行。”
小丽同意了。
事后，小明和小丽把他俩这次作假的方法告诉了小刚，小刚很失望地斥责他俩：“你们这样做和作弊有什么区别？对得起支持你们的人吗？我再也不相信你们俩的零知识证明了！”
8．非交互式证明（Non-interactive Proofs）
小刚很不爽。他很享受之前和小明、小丽一起挑战数独的乐趣，但是，现在的他觉得无法信任小明和小丽。小刚想找到另一种方法来保证直播中的小明和小丽不能再这样作假。冥思苦想之后，小刚告诉小明、小丽，他终于想到了一个好方法。小刚把自己关在屋里忙活了一整天，第二天他把小明、小丽叫来，给他们展示自己的新发明：零知识数独非交互式证明机——“The Zero-Knowledge Sudoku Non-Interactive Proof Machine”（zk-SNIPM）。
这台机器基本上就是把小明和小丽之前做的那套证明自动化，不再需要人为交互。小明只要把卡片放在传送带上，机器会自动选择按行、列或九宫格来收取卡片，放到袋子里打乱顺序，然后把袋子通过传送带再送出来。然后小明就可以当着镜头的面拆开袋子展示里面的卡片。
这台机器有一个控制面板，打开里面是一串旋钮，这些旋钮用来指示每次试验的选择（行——Rows、列——Columns、九宫格——Blocks），如图3-6所示。
图3-6 非交互式机器
小刚已经设置好了试验的序列，然后把控制面板焊死，以保证小明和小丽不会知道他到底选择了哪一个试验序列。
小刚可以完全信任自己这台机器，他放心地把机器交给小明和小丽，让他俩下次直播就直接用这台机器来证明。
9．魔法盒子的开启仪式
小明和小丽很羡慕小刚有这台机器，并且想也能用这台机器来验证小刚自己出的数独题。问题来了，小刚如果知道自己选了什么样的试验序列，那么，用这台机器去验证小刚自己的数独题解，小刚就可以作弊。
怎么解决这个问题呢？其实也挺简单的，只要把大伙聚集起来，共同把控制面板重新打开，然后由大家一起来设置控制面板上的试验序列即可。这个过程可以称之为“可信任的初始设置仪式”（Trusted Setup Ceremony）。
为了增加随机性和保密性，如果把这台机器放在一个漆黑的房间里，并且把旋钮上的指示贴纸也都撕去。三人分别进入到这个屋子，大家进房间时蒙上眼睛来减少作弊的可能性。这样，最后这些旋钮所代表的试验序列他们三个人基本上就都没有办法知道。即便他们三个人中有两个人事先商量好自己会怎么选，他们也无法得知第三个人会怎么选，从而没有办法作假。等仪式结束之后，他们一起把控制面板焊死，这样至少比原来的可信度增加了不少。
10．如何破解魔法盒子？
有那么一天，小明在家守着这台机器。他开始反思它是不是像大家认为的那样安全可靠。过了一会儿，他开始尝试给机器故意传送一些假的题解（只保证每行、每列或每个九宫格的数字不重复），试图通过这种试错来找出机器里设置的试验序列。慢慢反复尝试，终于把机器里的试验序列都推断出来了。他既兴奋又沮丧，如何能设计一个更好的证明机呢？
11．故事的本质
看到这里，相信读者又巩固了对零知识证明的基本认知：零知识证明的本质，就是在不暴露我所知道或拥有的某样东西的前提下，向别人证明我有很大概率（零知识证明说到底是一个概率上的证明）确实知道或拥有这个东西。
故事里要证明的，就是一个数独题的题解，小明让小丽每次随机抽取行、列、九宫格的卡片，并收集在一起随机打乱，小丽通过拆开袋子并不能知道题的解，但是却能相信小明很大概率知道题的解。
本场景中的zk-SNIPM也是暗指零知识证明现在最普遍的zk-SNARKs（Zero-Knowledge Succinct Non-Interactive Argument of Knowledge）算法。zk-SNIPM还有改进的余地，比如用一台扫描仪把第一次卡片的组合就全扫描下来，然后一次性同时验证所有的试验序列。这样就很难用试错的方式来破解机器。
小明和小丽最开始的那种互动式证明方法暗指的是交互式零知识证明（interactive zero-knowledge proof）。交互式零知识证明需要验证方（小丽）在证明方（小明）放好答案（commitment）后，不断发送随机试验。如果验证和证明双方事先串通好，那么他们就可以在不知道真实答案的情况下作弊（simulate/forge a proof）。
非交互式证明则不需要这种互动，但会额外需要一些机器或者程序，并且需要一串试验序列，这个试验序列不能被任何人知道。有了这么一个程序和试验序列，证明机就能自动算出一个证明，并且能防止任何一方作假。
这里需要再升级一下，通过同态加密的方法，把采样点隐藏起来，把加密后的点写入区块链，一样可以完成验证，同时还不暴露采样点。这样就形成了最终的zk-SNARKs。
zk-SNARKs目前也存在很多已知的问题，比如：第一步从函数到代数表达式再到多项式的转换过于复杂，实际操作起来难度太高。采样点的生成仍然需要依赖一个可信的操作方。这个操作方知道采样点，可以伪造任何证明（这也是Zcash引入Trusted Setup的原因）。这个设置的过程需要在系统初始化的时候完成。如果在以太坊上，我们部署了一个新的函数，就没法通过链上的方法完成这个安全的初始化，这也间接限制了其应用。
而技术的问题最终总会被技术升级所解决。零知识证明为区块链带来保护隐私的特性，有可能带来区块链的下一个爆发点。
Zcash是在2016年10月28日推出的一种新的加密货币。它是一个比特币的克隆，来自比特币代码库0.11的分叉，Zcash通过增加完全匿名交易的附加功能与比特币、以太坊区分开来。因此，Zcash被誉为“不可跟踪的”加密学货币。
Zcash为了实现匿名交易，采用了零知识证明的密码学和计算机科学分支技术。即使是这个世界上最聪明的数学家也将零知识证明描述为“月球数学”，全球只有少数专门的研究人员对零知识证明运作细节有完全的了解。
零知识证明通过在公共Zcash区块链上创建匿名交易来实现Zcash的“不可跟踪”。Zcash上加密的交易隐藏了发件人和收件人的地址，以及一个地址发送给另一个地址的价值。这是独一无二的，因为迄今为止，其他区块链会显示从一个地址到另一个地址的价值传输，并且区块链上的任何人都可以看到此交易的值。与其他区块链不同，Zcash用户可以完全隐藏交易，唯一公开的是在某个时间点发生了某件事。
发送Zcash的地址都是匿名的，这意味着如果你不知道他们的实际身份或真实世界的地址，则无法看到货币从哪里流入或流出。