# 零知识证明（一）-基本概念与Schnorr 协议

By [tom_ni](https://paragraph.com/@tom-ni) · 2022-06-14

---

为何需要零知识
-------

设想一种场景：

1）Alice声称自己研发出了一种可以解所有高考数学题的万能公式，任何题目10秒内都能计算出答案，并愿意以10eth的价格出售；

2）数学成绩一般的Bob表示非常有兴趣。 两人一拍即合。

然而，在交易之际却发生了问题，进入了一个死循环：

1）Alice表示，Bob必须要先付款，不然公式给到了Bob后他偷偷记下，然后拒不支付怎么办？

2）Bob则表示要先验货，如果自己付了钱，拿到的根本不是什么万能公式，Alice割完韭菜卷款跑路，那怎么办？

两人你来我往，尽管双方都有强烈的交易想法，但因为潜在的对手方风险，无人可以让步。最终这笔交易不了了之。

这正是一个典型的例子，“知识的保护”与“证明拥有知识”之间，Alice与Bob未能找到一个调和的方案，最终进入了死锁。 零知识证明（zero-knowledge proof，zk）正是应对这样一个场景而生的技术，即证明某个论点（Alice拥有万能公式）的同时，又不泄露论点中蕴藏的知识（万能公式本身）。

将其衍生到区块链中，数据上链后不可篡改的同时，也牺牲了一定程度的隐私性：用户的某些资产也许并不希望被大众所熟知。 如何即证明用户拥有资产，又不泄露资产的详情与用户的隐私，同样是零知识证明这项技术致力于解决的问题。

在此基础上，回到Alice与Bob的问题，一种能解决双方顾虑的“零知识”方案是：

1）由Bob随机选取题目，对Alice进行挑战；

2）Alice计算答案后供Bob验证正确性与时长。

期间：

1）Alice并未泄露任何有关公式的知识；

2）而Bob则可以任意选取大量的难题、偏题、压轴题；

随着验证数量越来越多，Alice真的拥有万能公式的置信度也就越高。

Schnorr 协议--一个简洁的零知识验证系统
------------------------

在此基础上来看一个实际的零知识证明协议：Schnorr Protocol。

首先引入些数学铺垫：

有一个形如下图的曲线，我们姑且称之为椭圆曲线：

![椭圆曲线](https://storage.googleapis.com/papyrus_images/644e6a10ec57f183eb21b5b7200d5ed2a600077044b950aa1869eb7d8999f8c5.png)

椭圆曲线

此外，我们灵机一动，定义了椭圆曲线上两点P、Q的加法，定义看上去虽然怪但实际运算也很简单：

P+Q = P、Q连线与椭圆曲线的交点（即：G）与X轴的对称点（R）

反映到图中即：P+Q = R

![P + Q = R](https://storage.googleapis.com/papyrus_images/4f1ee604b5c70ee7eaf96390e8d7be54a3fcef8334755f0414e8ad36bc934af4.png)

P + Q = R

如果考虑边界情况，即P、Q是同一个点：P+Q = P+P = 2P，也很简单，将P、Q连线变为P点的切线即可：

![P + Q = P + P = 2P = R](https://storage.googleapis.com/papyrus_images/22364a9f4117ddef4aad3e06961f2d3bce9f7c5f7ef05c24ecaeba95bcd07980.png)

P + Q = P + P = 2P = R

以此类推，3P、4P、5P…也非常容易计算。以3P的计算为例，上图中：

3P = P+2P = P + R。又回到了最基础的计算模式。

* * *

好了，这就是这部分的主要内容，下面是一个思考问题。根据上述的定义，请举一反三，已知蓝点S = a\*P，求解a的值。：

![S=aP，a=？](https://storage.googleapis.com/papyrus_images/7767e697f72d6aefabac5c331ef7e8fa067170edc000085735fd21b13e440aed.png)

S=aP，a=？

* * *

是的，正常情况下应该没有人做出来，**尽管已知a后计算aP很简单。但是在仅知道aP的情况下（即已知点S），求解a非常难！这个性质正是密码学安全性的一大基石**。

（如果真有同学做出来了，我愿意用10eth买你的办法。当然，得先有一个验证，可以是零知识的^\_^）

在此铺垫下，终于可以进入本篇章的主题：Schnorr协议。来看这张经典的流程图：

![Schnorr协议流程](https://storage.googleapis.com/papyrus_images/725678878aa58527fd7faf02e5fb820e56e1d6578203b8c70a840c1970afe4b5.png)

Schnorr协议流程

Alice手中保管着一个机密的数字a，她用a结合椭圆曲线加法计算出了a\*G：

1.  这里的a就是我们熟悉的私钥private key，需要严格保密；
    
2.  这里的PK = a_G，就是公钥，公开给大众。因为椭圆曲线的性质，即使大众知道了a_G，也很难算出a。
    

至此，我们来看，Schnorr协议如何简洁地完成一个零知识证明，即Alice向验证者Bob证明自己拥有私钥a的同时，又不泄露a的值：

1）首先，Alice生成了一个随机数r，并计算R = r_G，发送至Bob；_

_（Bob手上的信息：PK 、R）_

2）同时，Bob生成一个随机数c，用以挑战Alice\*；\*

_（Bob手上的信息：PK、R、c，他可以基于此计算R+c_PK）

3） 最后，Alice需要计算z = r + c\*a，并将z回传给Bob。

_（Bob手上的信息：PK、R、c、z）_

从这一步开始，Bob可以用其手上的信息进行验证：

1）如果Alice确实有a的值，那么Bob利用传回的z，可以计算：

**z\* G = （r + c_a）G = R+c_a\*G = R+c\*PK**，

应当与步骤2中他的计算结果相等。

2）反之，如果Alice并没有私钥a，她很难猜准z，使得z\*\*G = R+c\*PK。

至此Alice手中是否有私钥，得以验证。

同时，回顾Bob的所有信息PK、R、c、z：

1）PK = a\*G，因椭圆曲线的性质其很难解出a；

2）R = r\*G，r随机生成，和a没什么关系，且无法从R反推r的值；

3）c，Bob随机生成，和a也没什么关系；

4）z = r+c\*a，由于r不知，故无法从a = （z-r）/c中解出a的值。

因此纵观整个协议，Bob手上的信息未能透露任何关于a的知识。

可以看到**Schnorr协议，使得Alice向验证者Bob证明自己拥有私钥a的同时，又未泄露a的值，简洁地完成了一个零知识证明**。

零知识证明的三大性质
----------

上文的Schnorr协议让我们看到了一个简洁的零知识证明，但是事情没这么简单。

回顾Schnorr协议的步骤2，Bob生成了用于挑战的随机数c。

如果Alice破解了该随机数生成器的分布，可以预测Bob生成的c，那么她就能伪造R’ = z\*G - c\*PK, 在不知道a的情况下通过验证，欺骗Bob。

![Alice通过破解c值完成欺骗](https://storage.googleapis.com/papyrus_images/b1ceb8ddc4d36322e2b5cc28d74bad0c9233756c07006cdbc2b817ac0fe1465d.png)

Alice通过破解c值完成欺骗

而站在Bob的角度，如果他能通过重放攻击，使得Alice连续两次生成同样的随机数r，他就可以借助两次验证的结果，通过（z-z’）/（c-c'）反推出a：

![Bob重放r来反推a](https://storage.googleapis.com/papyrus_images/15fccd28a4bab8da1152fbf450e2a0574d9017327cf5fbe0a3e33459f2a6baab.png)

Bob重放r来反推a

因此看似简单明了的协议，在实现过程中其实存在许多安全问题需要克服。

而理想中，一个零知识证明协议，应当具备如下的三个性质：

1）**完备性**（completeness）：如果Alice拥有a，她就能通过Bob的验证；

2）**可靠性**（soundness）：如果Alice不拥有a，她就不能通过Bob的验证，上文中基于猜测随机数c对Bob进行欺诈就是soundness的反例；

3）**零知识**（zero-knowledge）：验证过程不能泄露a，上文中基于重放r反推出a就是反例。

可见实现一个完美的零知识协议，并能适配通用的应用场景，研发难度相当之大。

回到最初的问题，隐私作为一种强需求有着明确的应用场景，zk会是一种实用的技术，因此值得仔细研究。

本文作为零知识系列的开篇，首先建立一个直观的描述，希望日后不断学习的同时、亦能不断见证零知识技术的成熟。

---

*Originally published on [tom_ni](https://paragraph.com/@tom-ni/schnorr)*