带你一文了解零知识证明

本文插图
免责声明：本文旨在传递更多市场信息，不构成任何投资建议。文章仅代表作者观点，不代表火星财经官方立场。
小编：记得关注哦
来源：NervosNetwork
_本文原题：干货 | 零知识证明引论（一）
作者：Cyte
继上一次 Shor 发出了对支付网络中路由问题的全面研究之后，又有一位热爱研究的 Nervos 小伙伴 Cyte 对零知识证明做了详细的研究。
在这篇文章中， Cyte 会和大家介绍零知识证明 (ZKP)的定义，并将零知识证明与 SNARK 和 STARK 这两个概念进行辨析。
ZKP、SNARK 和 STARK 等这些密码学概念随着最近区块链的兴起变得热?起来。但是，它们经常会被误解和混用。其实，所有这些概念都属于一个更广义的范畴，叫做证明系统 (Proof System) ，或者叫做密码学证明（Cryptographic Proof）。零知识证明和 SNARK、STARK 之间都有交叉的部分，但并不相互包含。它们之间的关系可以用一张图来表示。

本文插图
本文将首先介绍证明系统的定义，并讨论证明系统的各类性质，重点讨论「零知识性」、「知识证明」、「简洁性」和「非交互性」。特别的，如果一个证明系统具有「零知识性」，那么它就被称为一个「零知识证明」。最后，文章会讨论 SNARK 和 STARK 的定义并将其进行比较。
证明系统
一个证明系统 (Proof System)是一个交互式协议，包含两个参与方 Prover 和 Verifier ，以及一个算法 Setup 。证明系统的作用是让 Prover 说服 Verifier 相信一件事，我们把这件事叫做一个陈述 (Statement) 。
协议开始前，需要由某人调用 Setup 算法。 Setup 算法接受一些公共参数作为输入，并输出 Prover 和 Verifier 所需的 Setup 信息，其中 Verifier 获知的信息记为， Prover 获知的信息记为。和的公共部分称为公共参考字符串 (Common Reference String, CRS) 。具体由谁、在什么时候调用 Setup 算法，取决于证明系统的设计。协议一开始， Prover 和 Verifier 同时得到输入陈述。 Prover 相对于 Verifier 必然要有一些额外的优势，例如更强大的计算能力，或者得到了一些额外的输入。除此之外， Prover 和 Verifier 还分别获知了和。 Setup 信息获取的时间取决于证明系统的设计。例如，有可能是 Prover 和 Verifier 早就下载好存在各自硬盘里可以反复使用的，也可能是协议开始前当场输入的。然后 Prover 和 Verifier 开始执行证明系统规定的协议。如果 Prover 和 Verifier 都是诚实的，那么它们都严格遵守协议执行。不过，也有可能某一方是恶意的，没有按照协议规定来执行，此时会发生什么事情，取决于证明系统的安全性。如果两方都是恶意的，它们都不遵守协议，那就和这个证明系统没关系了。最后， Verifier 输出 accept 或 reject ，表示是否相信陈述。一个证明系统需要满足两个性质：

完整性 (Completeness)：如果陈述是正确的，而 Prover 和 Verifier 都遵守这个协议，那么 Verifier 以至少的概率输出 accept ，这里被称为证明系统的完整性误差 (Completeness error)
可靠性 (Soundness)：如果陈述是不正确的，此时 Prover 必然是不诚实的，而 Verifier 遵守协议，那么任何 Prover 都不能让 Verifier 输出 accept 的概率超过，这个被称为证明系统的可靠性误差 (Soundness error)

这两个要求是使得一个证明系统成立的最基本的要求。少了哪个要求，我们都可以得到符合条件但完全没用的证明系统。例如，如果我们只要求完整性，那就无论 Prover 做什么， Verifier 永远只输出 accept 就好了；如果只要求可靠性，那就让 Verifier 永远只输出 reject 。此外，一般希望和都不超过，并且加起来小于，否则这个证明系统误差太大，也近乎无用。如果将一个证明系统的可靠性只对任何计算能力受限的Prover 成立，也就是说，计算能力无限的敌手是有可能欺骗 Verifier 的，此时这个证明系统只有计算可靠性 (Computational Soundness) ，这样的系统又称为论证系统 (Argument System) 。相比之下，对任何 Prover 都安全的可靠性被称为统计可靠性 (Statistical Soundness) 。