未来柚科技 | 零知识证明简述

一、零知识证明定义

零知识证明(Zero—Knowledge Proof)，指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄露任何关于被证明消息的信息。

二、零知识证明两种类型

目前有两种零知识证明：

1.交互式的 (Interactive)

2.非交互式的 (Non Interactive)

（1）交互式零知识证明（Interactive zero-knowledge proofs）：证明者和验证者需要进行多次互动，验证者会不断提出问题来挑战证明者，证明者则要不断回应这些挑战，直到验证者被说服。

交互式零知识证明---色盲游戏

Alice是色盲，Bob不是色盲，在Bob手上有两个大小，形状完全一样的球，但这两个球的颜色不一样，一个球是蓝色的，另一个球是红色的，由于Alice是色盲，所以Alice无法分辨这两个球是否是一样的，Bob需要向Alice证明这两个球是不一样的。在这里，Alice被称为验证者，他需要验证Bob的陈述正确与否，Bob被称为证明者，他需要证明自己的陈述（存在两个颜色不一样的球），Bob需要在Alice不能获得两个球的颜色的情况下，向Alice证明这两个球的颜色是不一样的这个事实，这与零知识证明的定义是相符合的。

Alice当Bob的面拿起两个球，左手拿蓝球，右手拿红球，然后将双手放到背后，这样Bob就看不到Alice手上的球了，Alice在背后随机交换左右手上的球，交换完成后Alice将手伸出，并询问Bob两个球是否交换过位置，如果Bob能看到球上的颜色，那么每次Alice换过球的位置后，Bob都能正确回答出Alice的问题。

第一次，Alice偷偷交换了手中球的位置，然后Alice问Bob是否交换了球的位置，如果Bob回答Yes，那么Alice有50%的概率相信Bob是可以区分这两个球的颜色，因为Bob有1/2的概率蒙对，所以Alice可以再进行一次测试。如果Bob回答No，那么Alice可以肯定Bob不能区分两个球的颜色。

第二次，Alice没有交换手中球的位置，然后Alice问Bob是否交换了球的位置。如果Bob回答No，那么Alice有75%的概率相信Bob是可以区分两个球的颜色。

第一次迭代后，Alice可以说Bob陈述的断言为真的概率为50％。如果Bob第二次回答正确，那么Alice可以说Bob陈述为真的概率达75％。在第三次迭代后，它将是87.5％。如果连续n次Bob都通过了检查，则Alice有1-(1/2)^n 的概率可以认为 Bob 说的是真的，这两个球的确是有红蓝两种颜色。

零知识证明是一种基于概率的验证方式，验证者（verifier）基于一定的随机性向证明者（prover)提出问题，如果证明者都能给出正确回答，则说明证明者大概率拥有他所声称的“知识”。零知识证明并不是数学意义上的证明，因为它存在小概率的误差，欺骗的证明者有可能通过虚假的陈述骗过验证者。换句话说，零知识证明是概率证明而不是确定性证明，但是也存在技术能将误差降低到可以忽略的值。

这种交互式方法有一些局限：

1.每次验证都需要进行整个冗长的过程。

2.证明方与验证方都需要同时在场，不管是在线还是面对面。

3.只能够取信于一个验证者，如果要取信于多个验证者，则对每个验证者都需要进行一遍证明过程。

4.只在某个时刻有效。

为了解决交互式零知识证明面临的问题，非交互式零知识证明应运而生。

（2）非交互式零知识证明（Non-interactive zero-kowledge proofs）：证明者只需要在第一次向验证者发送一个证明，验证者可以随时对该证明信息进行验证，并且只需要验证一次就能够判定是否选择相信证明者。这种证明方式比交互式证明需要更多的算力来完成。

非交互式零知识证明---数独游戏

如果将交互次数减少到一次就是非交互式零知识证明（Non-Interactive Zero-Knowledge, NIZK），可实现离线证明和公开验证。

数独游戏题目

数独是源自18世纪瑞士的一种数学游戏，是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。

Alice为了向Bob证明她已经解决了一个数独难题，为此Alice创建了一个防篡改的机器。Alice将生成好的数独答案放入机器中，机器可以向Bob发送证明。Alice的机器遵循以下公开可验证的协议：

首先，Alice在机器中放入尚未被解决的原始数独题目，数独中的谜题卡片三张正面朝上。

接下来，Alice上机器将他的答案正面朝下放置在相应的单元格上，同样也是每个单元格放三张。

最后Bob向机器获取证明，机器返回给Bob27个袋子：

·        机器将数独中每一行9张卡片取出，并分别混淆后放入一个袋子中，一共有9行，所以9个袋子

·        机器将数独中每一列9张卡片取出，并分别混淆后放入一个袋子中，一共有9列，所以9个袋子

·        机器将数独中每个粗线宫（3*3）内卡片取出，并分别混淆后放入一个袋子中，一共有9个，所以9个袋子

Bob分别对这27个袋子进行检查，如果每个袋子中的卡片都包含数字1到9，而且没有任何数字丢失或重复，那么Bob可以确认Alice的确解开了数独，并且Bob并没有从机器返回的证明中获取任何关于数独解的知识，因为机器返回给Bob袋子中的数据是被随机打乱的。

非交互式零知识证明克服了交互式零知识证明的一些缺点，不需要冗长的在线交互，可以取信于很多人（甚至所有人），证明始终有效，但是可能需要额外的机器和程序来确定实验的顺序。

例如，在数独这个例子中，由程序决定要验证的列或行。验证序列必须保密，否则验证者可能会在不知道真正“知识”的情况下通过验证。

上述的案例的成功，必须满足一定的规则：

完备性（Completeness）：只要证明者拥有相应的知识，那么就能通过验证者的验证，即证明者有足够大的概率使验证者确信。；

可靠性（Soundness）：如果证明者没有相应的知识，则无法通过验证者的验证，即证明者欺骗验证者的概率可以忽略。

零知识性（Zero-Knowledge）：证明者在交互过程中仅向验证者透露是否拥有相应知识的陈述，不会泄露任何关于知识的额外信息。

三、区块链上的零知识证明

零知识证明定义中有两个关键词：“不提供任何有用信息”、“证明论断是正确的”，基于这两个特点，直接扩展出零知识证明在区块链上的两大应用场景：

隐私：在隐私场景中，我们可以借助零知识证明的“不提供任何有用信息”特性，在不泄露交易细节(接收方、发送方、交易余额)的情况下，证明区块链上的资产转移是有效的。

扩容：在扩容场景中，不太关注零知识证明技术的“不提供任何有用信息”这个特性，更加关注“证明论断是正确的”这个特性。由于链上资源是有限的，所以我们需要把大量的计算迁移到链下进行，因此需要有一种技术能够证明这些在链下发生的动作是可信的，零知识证明正好可以帮助我们做链下可信计算的背书。

（1） 隐私计算

零知识证明可以满足消息的隐私性，可以解决常见的区块链网络中因透明性所带来的地址和资产额度等消息泄露。例如在区块链交易中，如果你需要证明你拥有某种资产，但同时又不想暴露资产的任何信息，那么就需要用到零知识证明。

隐私计算是零知识证明的一个重要的应用领域。若想保护隐私，则可以通过密码学的解决方案对链上数据进行加密，让链上的不同交易之间找不出关联性。零知识证明可以验证计算而不会暴露有关输入和计算本身的任何信息，保证链上数据隐私和安全。

（2） 扩容

若常用的区块链平台中产出新区块的验证时间很长，可直接更改为一人（节点）验证并生成证明，网络中的其他参与者都掌握快速验证该证明的方法，而不需要每个参与者都花费大量的时间来直接进行验证。

这涉及共识的成本问题，从经济学角度来看，以太坊，比特币等区块链网络交易成本高昂的原因在于：共识必须是昂贵的，廉价的共识一定程度上是不可信的。而其中的成本主要来自于区块链需要若干台设备的重复计算才能达成一致的共识。例如POW共识机制中，1000台机器做重复的计算工作，效率不会大于一台计算机的效率，但其所需要的成本是一台计算机的1000倍。这是所有的主流共识协议，无论是POW还是POS，为确保去中心化的共识所必须付出的成本。也就是不可能三角的束缚。

将零知识证明和区块链的一致共识结合起来，就可以达到仅用一台设备即可运行计算完成1000台设备重复计算的工作，从而极大降低了网络成本。零知识证明，通过采用密码学的方法，让其他设备验证一台设备计算的可靠性，而非直接参与重复计算。而且，在成本昂贵的区块链网络上，验证计算的正确性要比重复计算便宜得多。

因此，区块链依旧负责网络的共识和安全，而一些计算的工作则可以交给零知识证明在区块链网络外部完成，提升了区块链的拓展性。

四、零知识证明的挑战

零知识证明已被证实未来有巨大的潜力，但是当前离广泛应用还有很多难题尚未得到解决。

从数学意义上来讲，零知识证明并非真正的证明，因为证明者说谎而不被验证者识别的概率，虽然可以无限趋近于零，但它永远不会到达零。只要不是零，就非逻辑上的零知识证明，因此零知识证明并不能保证100 %有效。

硬件方面，市面上目前还没有专门用作零知识证明相关的硬件和软件。零知识证明需要证明者和验证者之间不断交互，因此需要大量的计算能力，这让零知识证明不适合在速度慢或移动的设备上使用。