一文读懂零知识zk-SNARKs

区块链是随着2009年比特币的引入而备受关注的技术，它为去中心化结构的发展打开了新的大门。从那时起，人们开始表现出对了解区块链技术基础知识的强烈兴趣，并用这些基础技术尝试建立一个完全分布式，可扩展和安全的环境，采用技术改善传统流程中所存在的问题。

然而人们也意识到这种技术还有很多缺陷，主要是隐私和匿名性。每个人都可以看到区块链上的数据，任何人都可以轻松地跟踪信息实现溯源。使得任何人都很难匿名执行任何交易，但是完全的隐私又会带来难以监管的问题。这为区块链在许多方面的应用带来了阻碍。

为了解决隐私和匿名性的问题人们采用了很多技术，其中零知识证明和其相关的密码学在平衡隐私和透明的需求上卓有成效。而zk-SNARK就是当前最为先进的隐私工具。

为了向你解释zk-SNARK究竟是怎样一种技术，不妨先来看一个小故事

在中学的数学课上，老师布置了一道关于一元二次方程求解的作业。

小明与小红是班上数学最好的两个学生，每次他们都争着第一个算出老师作业的答案。而这次小明先算出了答案，于是他开始试图向小红炫耀他已经解决了问题，但他不希望告诉小红他的答案，因为他费了好大的劲才算出来。这时他意识到他需要一种向小红提供证据的方法，但同时又不会泄漏他算出来的答案。

是否想起了上个系列中阿里巴巴向强盗证明他知道口令的例子？

小明需要零知识的证据!

幸运的是，这个学校很鼓励这种竞争，为此学校提供了一些有用的计算工具来帮助小明。他们提供了两个加密密钥，一个交给小明这样的想要证明自己已经算出答案的孩子，另一个给小红这样的需要验证别人答案是否正确的孩子。学校还提供了正确答案的哈希值和两种便捷的算法。

于是小明输入他的答案，学校的答案的哈希值、证明者密钥，通过学校的生成证明的算法来运行这些输入值，并得到了一些乱码，这就构成了小明的证明。现在，他可以在不泄露自己答案的情况下向小红证明“我算出了答案”。

小红采用学校的答案的哈希值，小明的证明、为验证者准备的密钥，并通过验证算法运行它们。得出来的是“答案正确”，于是小红可以相信小明得到了正确答案。

但是小红十分怀疑小明，她想起来一年级的时候，小明曾借她了一块橡皮并且再也没还过。她觉得小明可能窃取了学校用来生成证明者和验证者密钥的秘密，然后用它来构成一个可以让错误答案也验证成为正确的方法。

然而学校向小红保证，这是不可能的，因为证明的秘密是在一个秘密“仪式”中产生的（这个仪式的过程我们将在之后揭秘），就连校长也无法破解，她可以放心的回到教室，请求小明在作业上提供一些帮助了。

这就是Zero-knowledgesuccinct non-interactive arguments of knowledge (zk-SNARK)。zk-SNARK确实是一种非常精妙的方法，它可以在不揭示任何信息的前提下证明某个论断为真。下面让我们回顾一下这个小故事，那么zk-SNARK究竟意味着什么呢？

    succinct  简洁性

这样的证明是简洁的，也就是小红可以迅速验证小明的答案，即使语句很大，也能在几毫秒内验证证明。此属性还有助于解决可扩展性问题。

    non-interactive 非交互性

小红不必带小明进入校长的房间，也不必在小明分享他的证明后与他对话，她随时可以检查证明是否正确。因此“验证者”与“证明者”之间不存在交互的过程，这与我们之前的阿里巴巴与强盗的例子很不相同。在交互式零知识协议中，证明者和验证者彼此交换多个消息，直到证明者确信证明者知道某些秘密为止。对于存在“公共验证者”的非交互零知识证明，验证者和证明者不需要直接相互交互。相反，此“公共验证者”可以将加密的查询发送给证明者，并将加密的响应发送回验证者。

    Argument 论证

zk-SNARK假设证明者的计算能力有限。因此，这些证明满足了当前计算的可靠性，但不满足100%的可靠性。这意味着如果证明者的计算能力足够强大，则系统的安全性就可能出现危险。不过在当前的计算技术之下，系统的安全性是完全足够的。

    knowledge知识

zk-SNARK包含一个知识性的论点，也就是可以说它能够使小红确信小明的答案正确。可以说明一个证明的需求实际上有答案，以便甚至产生一个参数，证实该说法。

ZK-SNARKs 具体如何运作？

Zk-SNARK背后具体的数学原理是是十分精妙且复杂的，然而这里我们采用简化和压缩后的原理，向你概述它的背后实现方式。

首先，证明的问题会被以某种方式编码成为一组多项式，而证明者的目标是使验证者相信这个等式是成立的。比如

我们知道，一个多项式可以被可视化成为图中的所示的曲线，而一个朴素的想法是，如果两个多项式曲线上的点处处相等，那么两个多项式也就是相等的。

事实上，我们可以更简单的验证。因为不同的多项式，一定在大多数点的求值是不同的，就如上图所示。因此我们可以通过只验证几个点，就基本可以确定这件事。问题的关键是我们选取的点需要是随机且保密的，而这些随机值往往是可信设置中的潜在威胁，使用后需要立即销毁，以防止恶意者利用其进行构造证明来攻击。

比如我们验证上面的等式，可以选取一个随机点x=10：

当代入x=10这样的随机点时，我们可以直接验证得到两个多项式是不同的。

但是，验证者必须知道这个随机值才能进行验证，要不然如何比较呢？这时我们会采用同态加密这样的工具来掩盖这样的随机值信息。这使得在随机值保持私密的同时，验证者可以比较多项式是否相等。

在Zcash的最初版本中，最初的成员使用了一个“仪式”来产生这样的随机私钥，（就是上面校长办公室中的那个“仪式”），“仪式”其实就是一个产生随机结果的多方计算（multi-party computation）。而这些参与者只要有一方保持忠诚，私钥就无法被复制，这意味着只有所有参与方都背叛了系统才能导致系统损毁。即便如此，这仍然是一个需要信任的设置，需要我们解决。

我们了解了zk-SNARK实际上是一种带有零知识特性的非交互简洁论证，而之前我们已经介绍过了零知识证明的相关讲述，那么非交互与简洁的特性为零知识证明带来了什么？

    非交互性与简洁性的作用

在许多情况下，我们都可以从非交互性或简洁性中受益匪浅。交互性强的方案将产生多笔区块链交易，增加区块链网络的负担并抬高验证成本。当我们要允许多个独立的验证者验证给定的证明而不必每个人都单独查询证明者时，非交互性会起到关键性的作用。而当用于存储证明的介质非常昂贵或者我们需要非常短的验证时间时，我们往往需要简洁性。对于这样的分类帐本，zk-SNARK为区块链交易的效率带来的改变可以说是惊人的。

    初始化可信设置问题

Zcash 是 zk-SNARKs 的首个广泛应用，也是如今零知识证明比较常见的一种。而这个技术的最大问题是证明者和验证者之间需要一个「初始化可信设置」——这意味着需要一组公共参数来构建 zk-SNARKs，其潜在的问题是，参数通常由小部分群体制定，可能存在信任问题。此外，在理论上，如果证明者拥有足够的算力，就可以提交假证据，影响整个系统。这是为什么量子计算机被认为是可以威胁这种算法的原因。所以「初始化可信设置」是其他新技术努力尝试克服的最核心问题。虽然零知识证明系统可以来保护区块链网络之间的隐私，但很多系统都还是需要可信设置。

为解决这个问题，斯坦福密码学家Benedikt Bünz 等人提出Bulletproof技术，相比较早的zk-SNARKs，不需要初始化可信设置，但是验证成本可能会高一些，但远低于其他技术比如 zk-STARKs。而全球密码学研究人员也陆续提出了各种各样的零知识证明相关的技术，比如说PLONK、Halo、Sonic、DARK（Diophantine Argument of Knowledge）、Supersonic。

而之后Ben Fisch和Benedikt Bünz提出的最新的零知识证明技术Supersonic是不需要可信设置的。Sonic （Supersonic的前身）和 PLONK 在零知识证明技术的某些方面取得了进展，虽然还是需要进行初始化可信设置的，但这个初始可信设置再也不是专用（application specific）的了。而 DARK是一种加密学工具，它可以帮助 Sonic 和 PLONK移除他们的可信设置，让它们变得更好。Sonic （音速）与 Dark组合的技术就是Supersonic （超音速），Supersonic 是一种无需初始化可信设置的 zk-SNARK。我们将会在接下来的文章中再来详细介绍他们。