Zero-Knowledge Proof - Githubissues

jasperzhong commented 3 years ago

传说中的零知识证明.

jasperzhong commented 3 years ago

零知识证明是在不共享或者透露底层数据的情况下验证事物. 一般通过多次测试的方式验证，即验证者(verifier)提问, 并且能验证证明者(prover)回答的正确性, 但又不知道他是如何做到的. 听起来很神奇.

我觉得零知识证明有点像写test, 只能调用API, 但你不知道API内部是如何实现的. 如果test多次验证都通过, 则证明程序正确(因为不可能每次都蒙对).

举的几个例子非常经典: 比如阿里巴巴的山洞问题,

阿里巴巴知道大门的密码，但是又不想告诉四十大盗. 他每次都随机在A或者B藏起来, 然后四十大盗过来, 让他随机从A或者B出来. 这样如果每次都能出来, 那说明阿里巴巴是知道大门密码的.

jasperzhong commented 3 years ago

百万富翁问题. by 姚期智

也叫安全多方计算.

太nb了. 不愧拿图灵奖...

简言之. 两个富翁想比较财富多少，但是又不想说出具体数值. 形式化一下, A有资产i亿元, B有资产j亿元. 0 < i, j <= 10.

先举一个例子. 有十个带锁的箱子

A不知道B拿出的是第几个箱子. 但是可以打开箱子. 于是有两种情况:

在密码学中, 锁是公钥, 钥是私钥.

m里面其实包括了B的资产，但是A并不知道X是多少，更不知道k是多少. 所以无法知道B的财富值.

A有公钥和私钥
- 计算 k - j + 1, k - j + 2, ...., k - j + 10, 其中必有一项是 k - j + j = k. 所以k其实是隐藏在这10个数之中.
- 解密. y_u = D(k-j+u). 得到10个数据y1, y2, ..., yj, ..., y10. 其中 yj = D(k) = X. 但A不知道是哪个 , 但确实有一个数是X.
- 求模. z_u = y_u % P. P是质数. 得到z1, z2, ..., zj, ..., z10
- z1, z2, ..., zi不变, z_{i+1}, ..., z_10都加1. 将这10个数发送给B.
B检验. 只关注第j个数据zj. 因为zj其实是yj取模得到的. 而yj其实是X, X是B想的.
- X % P = zj -> j <=i
- X % P != zj -> j > i

所以A和B都不知道对方财富，但是还是能比较大小.

jasperzhong commented 3 years ago

还有一种非交互式的零知识证明. zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge).

这个协议特点是prover只向verifier发送一次数据, 避免了多轮的交互过程. 这样是非常高效的.

其流程如下 Computation → Arithmetic Circuit → R1CS → QAP → zk-SNARK

比如这是计算表达式(a+b)(bc)的"算术电路"图.

输入的a, b, c就像流过这个电路一样, 得到最终输出.

建立Rank 1 Constraint System (R1CS)来验证这些值"正确地流过了". 比如在上面的例子中, R1SC会验证b和c的mul操作输出是b*c.
verifier需要去验证"算术电路"上的所有线路(或者叫约束). 但可以把原来的"算术电路"表示转换为Quadratic Arithmetic Program (QAP)的电路表示, 而转换后只需要验证一个约束. 这个约束是去检验多项式, 而不是数字. 这个多项式可能会很大, 但没有关系, 因为只要有一点点不一样, 那么两个多项式在很多数据点都会对不上. 所以我们只需要在随机一些数据点上检验两个多项式的结果否吻合即可.
但如果prover事先知道要verifier要选择的测试数据点, 那么就可以伪造一个满足这些数据点的多项式. 所以zk-SNARKs使用了同态加密和椭圆曲线配对来加密这些数据点. 所以就连verifier自己也不知道其所使用的数据点.

jasperzhong / cs-notes