上一篇讲的感觉和Zcash不是很有关系，只能算是对零知识证明的一个抛砖引玉。顺便纠正一下，我原来看到的数据是去年的，今年两位富豪都已经身价过300亿美元了
当然这不重要~另外补充一下上一篇文章的reference《知道了这个方法，两个人不需要裁判就能玩暗军棋》。
这一次想分享一个有趣的例子–数独游戏，很好地展现了概率可验证证明（probabilistic checkable proof）在零知识证明中的作用。这回故事的主角变成了Peggy和Victor，因为不得不提到NP问题中的证明者（prover）和验证者（verifier）（又拿人家概念的首字母造人名
）。数独是一个NP问题，因为给定一个数独的解，只需要验证每行每列每个3×3方框是不是都是1-9，所需时间为3×9×9×9次比较，对于更大的n×n数独，所需时间也为3n^3次比较，因此可以在多项式时间内验证解。
NP问题的陈述可以是“我Alice有0.25 ZEC”，也可以是“我Peggy知道这个数独谜题的解”，但是Peggy既想炫耀自己解出了数独谜题，又不想自己的脑力劳动果实轻易被Vector窃取，如何在不让Vector看到解的情况下让他对自己心服口服呢？这么高的要求实现起来看似不容易，但并非做不到。
比如这是一道数独的谜面：
它的谜底是：
Vector手上有若干份含有28道测试题的量表。每一回合Peggy都可以随机选取一个1-9的置换σ，比如σ(1)=2, σ(2)=8, σ(3)=6, σ(4)=5, σ(5)=4, σ(6)=9, σ(7)=1, σ(8)=7, σ(9)=3，然后按照这个置换把她的解对应为一个新的9×9方阵。
每份量表前27题是“请Peggy展示新方阵的第×行/第×列/第×个方框，Vector检查是否为1-9的排列”，第28题是“请Peggy展示数独谜面经过置换后的版本，Vector检查新谜面是否为旧谜面的置换”。
Vector可以选择其中一题让Peggy作答，正确则打√，错误则打×。
比如他选择检查第三行：
如果不是1-9的排列，Vector直接挂掉Peggy，因为Peggy原来的解的第三行也不满足要求，说明她牛皮吹破了。如果是1-9的排列，可能Peggy确实完全正确，也有可能是蒙混过关，因为Vector只检查了28个条件中的一个，那么Peggy侥幸通过的概率是多少呢？想象Peggy完成了整份量表，在28题上打√打×，但一定至少有一道上打了×。
但Vector只能知道其中一题的结果，他选到打×的题的概率至少为1/28，选到打√的题的概率至多为27/28，也就意味着这一回合Vector被Peggy欺骗的概率为27/28。如果只有一个回合，Vector是肯定不能相信Peggy的，他可以通过不断拿出新的量表考验Peggy来降低他被欺骗的概率。除了Peggy每次得选择不同的置换外，操作和之前一样。Peggy一旦失败就缴械投降，考核结束，否则如果在150个回合后她还顽强地存活，Vector就可以选择相信她了，因为(27/28)^150 < 0.5%。事实上Vector可以选择任意多的回合数，就看他有多苛刻了。
上面的设计充分实现了零知识证明的三个性质：
-
完全性（Completeness），如果声明是真实的，诚实的Peggy可以通过这个机制向诚实的Vector证明自己是正确的。因为诚实的Peggy必定每个回合都能通过Vector的考验，最后Vector也一定会认可她。
-
健全性（Soundness），如果声明是虚假的，撒谎的Peggy只有很小的概率可以通过这个机制欺骗诚实的Vector。因为撒谎的Peggy连续150个回合每次都骗过Vector的概率<0.5%。
-
零知识（Zero-knowledge），如果声明是真实的，Vector和第三方除了知道Peggy是正确的这个事实外别无所知。因为Vector每次查看的某一行/某一列/某一方框/谜面都是被随机打乱过的，从中不能看到一丝Peggy求解的谜底的影子。
概率可验证证明虽然会漏报（False Negative）（漏报的例子有：警察没有找到犯罪嫌疑人、医生没有发现病人长的肿瘤），证明流程也有点复杂，但确保了证明的隐私性和安全性，所以这个trade-off是值得而又精妙的。
有了零知识证明的铺垫，就可以介绍Zcash有哪些需要被零知识证明，又是怎样work的了。
Reference：
http://blog.computationalcomplexity.org/2006/08/zero-knowledge-sudoku.html