零知识证明【非交互知识论证】一 (2-2)

• 知识可靠性（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://tongren.me），接着再看更方便。