零知识证明【非交互知识论证】一

Anca Nitulescu的zk-SNARKs: A Gentle Introduction[1]是一份非常好的零知识证明入门材料。在这里做一个概括性的不太严谨的总结。

想象我们从一副完整的扑克牌中抽了一张方块A，我们想要向对方证明我们手中的是一张红色的牌。我们可以通过披露的方式去证明我们手上的牌是方块A，也就是直接把牌展示给对方看。或者，如果我们想只想证明我们手中牌的颜色，我们也可以向对方展示牌堆中的所有黑桃和梅花牌。现在对方就可以在不知道我们手上的牌是什么的前提下，相信我们手上的牌是一张红色的牌。

为了说明一项协议（protocol）是零知识（zero-knowledge）的，我们需要定义一个模拟器（simulator）的概念。模拟器是存在于一个“理想世界（ideal world）”，这个世界对于验证者（verifier）来说是无法和现实世界（real-world）互相区分的（indistinguishable）。在理想世界中，模拟器拥有一种可以在不知道具体的命题（statement），只知道命题的为真的情况下仍然可以生成证明（proof）的能力。即，验证者无法通过观察区分现实世界中证明者（prover）生成的证明和理想世界中模拟器生成的证明。

知识证明（proof of knowledge）是一种用于证明者可以成功说服验证者其知道与某些命题的相关信息的交互协议（interactive protocol）。如果这个命题是“我是小明”，那么证明者需要展示他拥有小明的密码；如果这个命题是“我可以算出方程f(x) 的结果是y”，那么证明者必须说服验证者他知道计算的所有步骤并最终能推导出y。

接下来我们需要定义一台机器怎么才算是拥有知识（knowledge），这里我们需要再引入一个提取器（extractor）的概念。将知识分离出来对于证明者的程序来说并不是必要的，这是我们需要使用另一个叫做知识提取器（knowledge extractor）的机器接入证明者的程序，通过与证明者交互，从证明者那里提取出一个见证（witness）。见证也就是这个知识本身。

由于在后面证明者，验证者，证明，见证，提取器，模拟器等术语会经常出现，我们用英文来表示这些术语。

下一步需要介绍一下非交互证明系统（non-interatctive proof systems），它可以让prover和verifier的交互缩减到只有一轮。一些非交互协议只需要prover向verifier发送一条信息，另外一些需要verifier生成一些公共的设置信息，称为公共参考字符串（CRS，common reference string），这些信息可以提前生成，和需要证明的命题无关。为了确保安全性，CRS通常由一个第三方可信机构（trusted third party）生成。

在非交互证明中，我们最感兴趣的是其中的一个特殊形态，简洁非交互知识论证（SNARK，Succinct Non-interactive ARgument of Knowledge)。我们一项一项来解释这个看起来很长的术语：

• 简洁（succinct）：proof的大小和statement或者witness的大小相比非常小。

• 非交互（non-interactive）：不需要prover和verifier多轮交互。

• 论证（argument）：我们认为这个协议只在prover计算资源有限的情况下是安全的，如果prover有无限的算力，那么他就可以说服verifier相信一个错误的statement。

• 知识可靠性（knowledge-soundness）：prover在不知道statement某个确定的witness的情况下不可能构造一个proof。用上面定义过的正式概念来说：任何一个可以生成有效proof的prover，都存在一个extractor可以提取出这个witness。

通过使proof不泄露任何witness的信息，SNARK系统可以借一步增加zero-knowledge特性。我们把这种方案叫做zk-SNARK。一个zk-SNARK协议可以用三种算法描述：

• Gen：设置算法，该算法会生成一个必要的字符串crs和一些验证秘钥（verification key）vrs。这些信息会在后面的证明中使用，crs通常是公开的，vrs又是只对verifier可见。该算法由一个trusted third party执行。

• Prove：证明算法，输入上一步生成的crs，要证明的statement u 和对应的witness ω ，生成一个proof π 。

• Verify：验证算法，输入第一步生成的vrs，要证明的statement u 和proof π 。算法返回1表示接受这个proof，返回0表示拒绝这个proof。

[1] Nitulescu A. zk-SNARKs: A gentle introduction[J]. Ecole Normale Superieure, 2020.

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。