学习区块链！理解一文零知识证明背后的简单逻辑
声明：本文旨在传递更多市场信息，不构成任何投资建议。文章仅代表作者观点，不代表火星财经官方立场。
边肖：记得要注意
文|李华
零知识证明的工程实现是一个非常具有挑战性的任务，但不代表理解零知识证明同样困难，背后的逻辑很简单。
你为什么需要知道它？隐私问题就不用提了。另一个重要原因是，随着对区块链探索的深入，我们发现通过密码学实现信任是对共识算法信任的有效补充，并且这两种信任可以以更低的摩擦结合，因此更容易实现和应用。从区块链技术最近的发展方向也可以察觉到这种趋势。
只有了解了这些密码方法背后的逻辑，才能不迷失，才能明白为什么要这样设计，适合什么样的应用场景。
隐藏的秘密旅程；证明秘密的旅程；构造普适零知识证明之旅。
1.隐藏秘密：单向函数
在《星际迷航》的宇宙中，P=NP，这对于计算界来说可能是一件好事。意味着所有可以在多项式时间内验证的问题，也可以在多项式时间内解决。但对于密码学来说，这可能是一场灾难。
密码学需要有一个“单向函数”，也就是说可以从A算出B，但是从B算出A在计算上是不可行的——只有当A到B的计算是单向的，才能隐藏A，如果P=NP，多项式时间内的可验证问题也是可解的，那么A可以由B算出，秘密是无法隐藏的。
这就是密码学背后的简单逻辑：单向函数。而单向函数背后的支撑就是P！=NP .
这和零知识证明有什么关系？我们可以把零知识证明分为两个功能。第一个作用是隐藏秘密，第二个作用是证明你有秘密。而隐藏秘密，如上所述，就是找到一个单向函数公式。
零知识证明：零知识证明是指让验证者相信一个断言为真，整个过程除了断言为真之外，不透露任何知识。为了更容易理解，本文将其简化为隐藏秘密和证明拥有秘密。
椭圆曲线算法(ECC)是一种广泛应用于密码学中的单向函数。看起来是这样的：k p=q在p已知的情况下，我们可以通过k计算q，但是反过来计算k就很难了。需要注意的是，密码学中加法或乘法的含义并不局限于大家熟悉的实数域中加法或乘法的含义。
我们来看看它是如何单向的。在这个函数中，p是椭圆曲线上的一点。我们在这个点上放一个小球，沿着切线方向击打出去。球在椭圆曲线上大概碰撞K次(大致可以这么理解)，最后落在一个点Q上，如果知道初始位置P和碰撞次数K，就可以计算出球的碰撞点Q。但如果我们只看到球落在Q上，我们就无法计算出它从P到Q的击打次数，也就是k。
下图是k=2的例子。球从P点出发，两次击中Q点，所以Q等于2 p，椭圆曲线算法常用于生成公钥和私钥。公钥是球的最后落点Q，私钥是撞击次数k，k P=Q的单向函数使得隐藏私钥的秘密成为可能。
椭圆曲线
2.证明秘密：同态
对于零知识证明来说，隐藏秘密只是第一步，我们还需要证明自己掌握了秘密。就像第一次旅程一样，我们只需要理解单向函数。在第二段旅程中，我们只需要了解“同态”。有了同态，我们就有能力证明秘密。那么什么是同态呢？
我们可以把单向函数看成一个映射关系，比如k P=Q就是从k到Q的映射：在一个空间里，我们有无数个k点，映射到另一个空间，就变成了无数个Q点。这就像现实世界和影子世界。通过光线的映射，真实空间中的物体在阴影空间中变成阴影。
这个时候，假设有一个机械表，机芯就是隐藏的秘密。我们把有运动的手表分割成八个部分，映射到阴影空间，那么阴影空间就会有八个阴影。但是注意，在现实空间中，我们展示给你的是一块完整的手表，机芯是未曝光的，这块手表在阴影空间会有阴影，我们称之为9号阴影。
现在，我们把八个部分的阴影结合起来。如果它们能形成一个完整的表影，我们就可以把这个表影和9号表影进行对比，如果它们相同，就可以证明这个表在真实空间中是有机芯的，因为它的影子和有机芯的零件的影子是一样的。其实这就完成了一个简单的零知识证明过程。
完全零件的阴影合成的手表阴影和完全手表的阴影是一样的，我们称这种映射同态。数学公式是f(手表)=f(第1部分…第8部分)=f(第1部分)… f(第8部分)。其中F(手表)是手表的影子，F(部分1).F (part 8)是手表的阴影加上零部件的阴影。
为了简化这个关系，f(a b)=f(a) f(b)，即先计算再加密f(a b)的结果与先加密再计算f(a) f(b)的结果相同。同态使我们能够直接计算密文，然后先计算出隐藏秘密的明文再加密，然后通过比较两者是否相同来验证明文中是否存在秘密。
同态的定义：在抽象代数中，同态是两个代数结构(如群、环或向量空间)之间保持结构不变的映射。
如果你只想了解零知识证明的基本逻辑，旅程可以到此结束。只有两个知识点：1。用单向函数隐藏秘密；2.用同态映射证明秘密。这不是很容易吗？
接下来，让我们看看这个过程在真正的密码学中是如何工作的。以椭圆曲线数字签名算法(ECDSA)为例，它是一种“零知识属性”的算法。你可以选择不看，不会影响你对同态的理解。
椭圆数字签名算法验证签名：在该算法中，关键过程是验证f(Z dA R)=f(Z) f(dA R)=f(Z) Qa R，其中Z是要用私钥签名的消息，dA是私钥，R与随机数有关，Qa是公钥。因为同态，这个方程是成立的，所以我们可以用方程右边的Qa(公钥)来验证Z是否由方程左边的dA(私钥)签名。这里dA是机芯，Z dAR是带机芯的手表，f(Z dA R)是这块手表的阴影，f(Z) f(dA R)是手表部件阴影组成的手表阴影。
椭圆曲线算法的同态性使得其他算法，如椭圆曲线数字签名算法，可以隐藏和证明秘密。但这种算法的能力是有限的，因为它只有加法同态，即f(a b)=f(a) f(b)，而没有乘法同态，即F (A B)=F (A) F (B)。
这就相当于把真实空间中的物体投射到阴影空间中，阴影空间可以通过加法来合并阴影，但是对于一些需要通过乘法来合并的阴影，就无能为力了。
我该怎么办？可以引入“配对函数”。比如椭圆曲线配对函数，就是对椭圆曲线算法进行一系列调整，生成一个新的映射空间，既满足加法同态，又满足类乘法同态(注意，只是类乘法同态)。这样，除了加法，我们还可以用类乘法来证明秘密。
现在，第二段旅程已经到达终点。我们需要知道的是，同态是证明秘密的关键，但并不是所有的映射关系都有“好”的同态，不同的应用场景对同态的要求也不同。在实际设计中，需要根据具体要求实现不同的同态。
如果原空间和映射空间同时满足加法同态和乘法同态，我们称之为全同态。同态是指密文可以任意操作(阴影可以任意组合)，对实现数据隐私有重要意义，但实现同态非常困难。
3.普适零知识证明：NPC问题
你一定注意到了，我们说椭圆曲线数字签名算法具有“零知识属性”，但我们不说它是零知识证明协议，因为它的主要业务是数字签名，隐藏私钥只是它必须实现的一个功能。而且只能隐藏私钥。如果你想让它帮你隐藏你自己的秘密，它不能。
零知识证明协议，比如大家熟悉的zk-SNARKs，主要业务是隐藏和证明各种需要隐藏的秘密。这是怎么做到的？
让我们回到本文开头的单向函数k P=Q，它可以隐藏一个秘密k .如果我们把它变得更复杂，比如t h=(v0a1 v1这样的多项式.am VM) (W0b1 w1).BM WM)，会不会有很多可以藏秘密的“空间”，比如放秘密？
其实上面文章中的复多项式就是zk-SNARKs中用来实现零知识证明的多项式，因为可以证明布尔电路，所以可以证明各种秘密。
为什么证明布尔电路就能证明各种秘密？因为布尔电路可满足性是一个NPC(NP-完全)问题，而NPC问题有一个“特点”，就是所有的NP问题(包括NPC)都可以在多项式时间内归结(转化)为一个特定的NPC问题。
比如布尔电路，图论三重着色，甚至大家熟悉的扫雷游戏都是NPC问题。我们可以将扫雷游戏定义为布尔电路的可满足性，即通过证明布尔电路的多项式来证明扫雷游戏的零知识；图论三色性可以归结为布尔电路的可满足性，即三色性的零知识证明可以通过证明布尔电路的多项式来实现.
理论上，我们可以基于任何NPC问题建立一个通用的零知识证明协议。但这只是理论上的，因为用它们做证明的难度完全不同。目前主流的方法是选择布尔电路或算术电路，因为它们相对容易实现，电路规模小。zk-SNARKs和Bulletproofs都是选择的方法。
扫雷游戏
4.零知识认证协议
历经三次旅程，零知识证明对我们来说可能不再神秘，但背后有一个简单的逻辑：1。单向函数是隐藏秘密的方式；2.同态映射是证明秘密的基础；3.证明NPC问题的多项式(但这不是唯一的方法)可以实现普适的零知识证明。
不同的零知识证明协议在这三点上的具体实现是不同的，主要的区别可能体现在第三点上。即使证明同一个NPC问题，也可能有完全不同的方法。由于设计的不同，最常提及的零知识证明协议的差异主要包括：
1.不同的计算空间和计算时间。更小的空间和更短的时间是我们不断改进零知识证明协议的主要动力，也是比较不同零知识证明协议的主要指标。
例如，下面的图表是ZCash的首席执行官Zooko Wilcox在谈到零知识证明协议时使用的表格。主要比较的是不同协议的证明时间、验证时间和证明大小。
资料来源：https://slideslive.com/38911617/privacy-for-everyone
2.您需要初始化可信设置吗？当然最好不需要可信设置，这样会减少信任问题和安全问题。但是，新的证明方法可能会带来新的计算问题。比如Bulletproofs不需要可信设置，但是在高复杂度下它的验证成本会非常高。
3.相关的安全假设。安全假说与安全密切相关。例如，Bulletproofs依赖于一个标准的安全假设：离散对数问题，加上一个随机预测模型；Zk-SNARKs依赖于一个无法证明的安全假设：指数知识假设。
很难同时满足以上指标和属性。因此，在设计零知识证明协议或选择零知识证明协议/方法作为协议的功能组件时，我们需要考虑具体场景的需求。比如对证明时间要求高的，可能要选择占用空间大或者通用性差的方法；如果有可信设置的要求，可能需要选择证明成本较高的方法。
因此，一方面零知识证明在不断发展，各种协议正在设计中，一些新的协议在某些方面会更有优势；另一方面，不同的协议有不同的应用场景，我们不得不根据需求来设计或选择，没有更好的协议可以适用于所有场景。
如果你愿意，旅程可以到此结束；要继续的话，下一段有点“野”。
寻找另一种方式
这是关于zk-STARKs的。同样是零知识证明协议，但是是基于信息编码的零知识证明，完全是另外一种方式，可能会扰乱你清晰的思维。
Zk-STARKs不使用密码学中的单向函数。简单来说，它是这样做的：假设P有九个数要证明，a1，a2，a9，然后将它们编码成b1，b2，b9，并且每个bi包含a1，a2，a9。在验证过程中，验证者V对b1、b2、b9，并且可以从少量bi中分析是否存在任何编码错误，从而检测a1，a2，a9大概率为真或不为真。
当V随机抽样P时，P可以主动用随机数混淆抽样的bi，同时使V完成验证，从而实现零知识。
所以zk-STARKs的“单向”并不是基于不可行的单向，而是因为所有的b1、b2、b9没有暴露，a1、a2、a9不能通过b1，b2，b9。在“同态”一节中，它不是抽象代数(或密码学)中的同态概念，而是基于线性编码纠错理论的抽样验证。
Zk-STARKs不是基于上述NPC难题验证的，而是基于概率检验。关于这种验证方法，我们可以从一个古老的验证系统PCP(probabilical ly Checkable proof)中找到线索，但是zk-STARKs使用的方法叫做IOP(Interactive Oracle proof)，与PCP不同的是它使用了Oracle。
之所以推出zk-STARKs，一方面是因为它也相当流行，另一方面也是想说明零知识证明可能是一个很难探索边界的东西。比如zk-STARKs就有很大的不同，所以本文只是理解零知识证明的一个角度，而这个角度由于自知力有限，不一定适合所有的零知识证明方法。