零知识证明

Why and How zk-SNARK Works: Deﬁnitive Explanation

https://arxiv.org/abs/1906.07221

1. Introduction

零知识简洁的非交互知识论证（zk SNARK）是一种真正巧妙的方法，可以在不透露任何其他信息的情况下证明某件事是真的，然而，为什么它首先是有用的呢？

零知识证明在无数应用中是有利的，包括:

关于私人数据的证明声明:

一个人的银行帐户中有超过X钱
去年，一家银行没有与实体Y进行交易
匹配DNA而没有透露完整的DNA
一个人的信用评分高于Z

匿名授权：

证明请求者 R 有权访问网站的受限区域而不透露其身份（例如，登录名、密码）
证明一个来自允许的国家/州列表，但不透露具体来自哪个
证明一个人拥有地铁/地铁的月票而不透露卡的ID

匿名付款：

与任何identity完全分离的付款
在不透露收入的情况下支付税款

外包计算：

外包昂贵的计算并验证结果是否正确，无需重新执行；它开辟了一种去信任计算的类别
将区块链模型从每个人的计算都改变为一方计算，每个人都进行验证

尽管表面上听起来很棒，但底层方法是数学和密码学的“奇迹”，自 1985 年在主要著作“交互式证明系统的知识复杂性中引入以来，已经进行了第四个十年的研究随后引入了非交互式证明，这在区块链的背景下尤为重要。

在任何零知识证明系统中，都有一个验证人想要说服验证人某些陈述是真实的，而不披露任何其他信息，例如，验证人了解到验证人的银行账户中有X多个，但没有其他信息（即，未披露实际金额）。协议应满足三个属性：

完整性（Completeness）—如果陈述为真，那么证明者可以说服验证者
健全性（Soundness）—作弊的证明者无法说服验证者做出虚假陈述
零知识（Zero-knowledge）—交互只揭示一个陈述是否为真，而不是其他

2. The Medium of a Proof

让我们从简单开始，并尝试证明某些东西，而不必担心零知识，非交互性，其形式和适用性。

想象一下，我们有一个长度为 10 数组，我们想向验证者（例如程序）证明所有这些位都设置为 1，即我们知道一个数组，使得每个元素都等于 1。

验证者一次只能检查 (即读取) 一个元素。为了验证语句，可以通过以某种任意顺序读取元素，并检查它是否真正等于1，如果是，则在第一次检查后该语句的置信度为10%，或者如果该位不等于1，则语句完全无效。验证者必须进入下一轮，直到他获得足够的信心。在一些情况下，可以信任证明者并且只需要50% 置信度，在需要95% 置信度的其他情况下，必须检查所有单元。很明显，这种证明协议的缺点是，必须进行与元素数量成比例的检查数量，如果我们考虑数百万个元素的数组，这是不切实际的。

让我们考虑多项式，有一个曲线对应于多项式： $f(x) = x^3 - 6x^2 + 11x - 6$ 。多项式有一个有利的性质，即如果我们有两个不相等的次数最多为 d 的多项式，它们相交的点不超过 d。例如，让我们稍微修改原始多项式 $x^3 - 6x^2 + 10x - 5$ 。如果我们想找到两个多项式的交点，我们需要将它们等同起来。例如，要找到多项式与x轴相交的位置 (即 $f(x) = 0$ )，我们将 $x^3−6x^2+11x−6=0$ 等同，并且此类方程的解将是那些共享点: $x = 1$ ， $x = 2$ 和 $x = 3$ 。

同样，我们可以将多项式的原始版本和修改版本等同起来，以找到它们的交点。所得的多项式为1，且有明显的解 $x = 1$ 。因此只有一个交点。

$x^3 − 6x^2 + 11x − 6 = x^3 − 6x^2 + 10^x − 5$
$x − 1 = 0$

对于任意次数为 d 的多项式，任何此类方程的结果始终是另一个次数最多为 d 的多项式，因为没有乘法可以产生更高的次数。示例： $5x^3 + 7x^2 - x + 2 = 3x^3 - x^2 + 2x - 5$ ，简化为 $2x^3 + 8x^2 - 3x + 7 = 0$ 。代数基本定理告诉我们，d 次多项式最多可以有 d 个解。因此，我们可以得出结论，任意点处的任何多项式的求值类似于其唯一身份的表示。让我们在x = 10处评估我们的示例多项式。

$x^3 − 6x^2 + 11x − 6 = 504$
$x^3 − 6x^2 + 10x − 5 = 495$

事实上，在所有要计算的x选项中，最多只有3个选项在这些多项式中具有相同的计算，而所有其他选项都会不同。这就是为什么如果证明者声称知道一些多项式 (无论其次数有多大)，他们可以遵循一个简单的协议来验证语句:

验证者为x选择一个随机值，并在本地计算他的多项式
验证人向证明人给出x，并要求对相关多项式进行求值
验证人在x处对其多项式进行求值，并将结果提供给验证人
验证人检查局部结果是否与验证人的结果相等，如果是，则以高置信度证明该陈述

例如，如果我们考虑 x 从 1 到 $10^{77}$ 的整数范围，则评估不同的点数为 $10^{77}-d$ 。此后，x 意外“击中”任何 $d$ 个共享点的概率等于 $d/10^{77}$ ，这被认为可以忽略不计。

注意：与无效位检查协议相比，新协议只需要一轮，并且在声明中给出了压倒性的信心（假设 d 充分小于范围的上限，几乎 100%）。

这就是为什么多项式是zk-SNARK的核心，尽管也可能存在其他证明介质。

3.一个多项式的非交互式零知识

3.1 证明多项式的知识

我们从证明多项式知识的问题开始，然后采用通用方法。在此过程中，我们将发现多项式的许多其他性质。到目前为止的讨论集中，关注一个弱的证明概念上，即各方必须相互信任，因为还没有措施来执行协议的规则。例如，证明者不需要知道多项式，他可以使用任何其他可用的方法来得出正确的结果。此外，如果验证者的多项式评估的幅度不大，比如说 10，验证者可以猜测一个数字，并且它被接受的概率是不可忽略的。我们必须解决协议的这种弱点，但首先知道多项式意味着什么？多项式可以表示为以下形式（其中 n 是多项式的次数）：

$c_nx^n + ... + c_1x^1 + c_0x^0$

如果有人说他知道一个 1 次多项式（即 $c_1x^1 + c_0x^0$ ），那意味着他真正知道的是系数 $c^0,c^1$ 。此外，系数可以有任何值，包括 0。让我们说，证明者声称知道3次多项式，使得x = 1和x = 2是所有可能解中的两个。这样的有效多项式之一是 $x^3 − 3x^2 + 2x = 0$ 。

3.2 因数分解 Factorization

代数的基本定理指出，只要多项式是可解的，任何多项式都可以分解为线性多项式 (即代表直线的1次多项式)。因此，我们可以将任何有效多项式表示为其因子的乘积:

$(x − a_0)(x − a_1)...(x − a_n) = 0$

同样，如果这些因子中的任何一个为零，则整个方程为零，因此，所有 $x-s$ 都是唯一的解。我们的示例可以分解为以下多项式: $x^3 − 3x^2 + 2x = (x − 0)(x − 1)(x − 2)$

x的值是：0，1，2，你可以很容易地在多项式的任一形式上检查这一点。

回到证明者声称他知道根为 1 和 2 的 3 次多项式，这意味着他的多项式具有以下形式：

$(x − 1)(x − 2) · . . .$

换句话说，(x − 1) 和 (x − 2) 是所讨论的多项式的余因子。因此，如果证明者想要证明他的多项式确实具有这些根而不公开多项式本身，则他需要证明他的多项式p(x) 是那些协因子 $t(x) = (x − 1)(x − 2)$ 的乘法，称为目标多项式，和一些任意多项式h(x) ，即: $p(x) = t(x) · h(x)$

换句话说，p(x) 具有t(x) 的所有根。找到h(x) 的自然方法是通过除法 $h(x) = p(x)/t(x)$ 。如果证明者找不到这样的h(x)，这意味着p(x) 没有必要的协因子t(x)，在这种情况下，多项式除法将具有余数。在我们的示例中，如果我们将 $p(x) = x^3 − 3x^2+ 2x$ 除以 $t(x) = (x − 1)(x − 2) = x^2 − 3x+2$ 。我们得到了无余数的结果 $h(x) = x$ 。

使用我们的多项式身份检查协议，我们可以比较多项式 $p(x)$ 和 $t(x)·h(x)$ ：

验证者对随机值r进行采样，计算t = t(r) (即求值)，并将r给证明者
证明者计算 $h(x) = p(x)/t(x)$ 并计算 $p(r)$ 和 $h(r)$ ; 结果值p，h提供给验证者
然后，验证器检查 $p = t·h$ ，如果是，则这些多项式相等，这意味着p(x) 具有t(x) 作为辅助因子。

为了将其付诸实践，让我们在示例中执行此协议:

$p(x) = x^3 − 3x^2 + 2x$
$t(x) = (x − 1)(x − 2)$

验证者对随机值 23 进行采样，计算 $t = t(23) = (23 - 1)(23 - 2) = 462$ 并将 23 提供给证明者
证明者计算 $h(x) = p(x)/t(x) = x$ ，计算 $p = p(23) = 10626$ 和 $h = h(23) = 23$ ，并向验证者提供p，h
验证者然后检查 $p = t · h: 10626 = 462 · 23$ ，这是真的，因此该陈述被证明

相反，如果证明者使用不同的 $p′(x)$ ，它没有正确的辅因子，例如 $p′(x) = 2x^3 − 3x^2 + 2x$ ，那么： $h(x) =7x − 6$

我们将得到 $2x+3$ ，余数为 $7x − 6$ ，即: $p(x) = t(x)×(2x+3) +7x − 6$ 。这意味着证明者必须将余数除以 $t(r)$ 才能评估 $h(x) = 2x+3+(7x − 6)/t(x)$ 。因此，由于验证者对x的随机选择，因此对于余数 $7x-6$ 被t(x) 整除的概率很低，因此，如果验证者将检查p和h补是整数，这样的证明将被拒绝。但是，该检查要求多项式系数也必须是整数。

现在，我们可以在不学习多项式本身的情况下检查多项式的特定属性，因此这已经为我们提供了某种形式的零知识和简洁。尽管如此，此构造仍存在多个问题:

证明者可能根本不知道要求的多项式p(x)。他可以计算评估值t = t(r)，选择一个随机数h并设置 $p = t·h$ ，因为等式成立，因此验证者将其接受为有效。
因为证明者知道随机点 $x = r$ ，所以他可以构造任何在 $r$ 处具有一个共享点的多项式，其中 $t(r)·h(r)$ 。
在原始陈述中，prover声称知道特定的次数多项式，在当前协议中没有次数的强制执行。因此，prover可以通过使用更高阶的多项式来作弊，该多项式也满足辅因子检查。

我们将在以下部分解决所有问题。

3.3 模糊评估 Obscure Evaluation

在上文中，如果将 $r$ 和 $t(r)$ 不是明文给出，而是作为黑匣子给出，那将是理想的选择，因此人们无法篡改协议，但仍然能够计算对这些模糊值。类似于哈希函数，因此在计算时很难返回到原始输入。

3.3.1 同态加密

这正是同态加密的目的。也就是说，它允许对一个值进行加密，并能够对这种加密应用算术运算。有多种方法可以实现加密的同态特性，我们将简要介绍一种简单的方法。

一般的想法是，我们选择一个基数的自然数g（比如5），然后对一个值进行加密，我们将g乘以该值的幂。例如，如果我们想要加密数字3： $5^3 = 125$

其中125是3的加密。如果要将这个加密的数字乘以2，则将其提高为2的指数: $125^2 = 15625 = (5^3)^2= 5^{2×3} = 5^6$

我们能够将未知值乘以2，并对其进行加密。我们还可以通过乘法添加两个加密值，例如3+2：

$5^3 · 5^2 = 5^{3+2} = 55 = 3125$

同样，我们可以通过除法减去加密的数字，例如5 − 3: $5^5/5^3 = 5^5 · 5^{−3} = 5^{5−3} = 5^2 = 25$

但是，由于基数5是公共的，因此很容易回到秘密数字，将加密的数字除以5，直到结果为1。除法的次数即为明文。

3.3.2 模算术 Modular Arithmetic

这就是模算法发挥作用的地方。模运算的思想如下：我们声明只选择前n个自然数，即0，1，…，n-1而不是拥有一个无限的数字集。如果任何给定的整数不在这个范围内，我们将其“环绕”。例如，让我们先选择六个数字。为了说明这一点，请考虑一个具有六个相等单位刻度的圆；这是我们的射程。

现在让我们看看数字8将落在哪里。打个比方，我们可以把它想象成一根绳子，它的长度是八个单位。如果我们把绳子连接到圆圈的开头并开始将绳子缠绕在它周围，旋转一圈后，我们还剩下一部分绳子.因此，如果我们继续这个过程，绳子将在2处结束。

它是模运算的结果。不管绳子有多长，它总是会停在圆圈的刻度之一处。因此，模运算将使其保持在一定范围内。 15 个单位的绳索将在 3 处停止，即 6 + 6 + 3（两个完整的圆圈，剩余 3 个单位）。负数的工作方式相同，唯一的区别是我们将其包装在相反的方向，对于 -8，结果将是 4。

而且，我们可以进行算术运算，结果总是在n个数的范围内。我们现在将使用符号“mod $n$ ”来表示数字的范围。例如：3 × 5 = 3 (mod 6); 5 + 2 = 1 (mod 6).

此外，最重要的特性是运算顺序无关紧要，例如，我们可以先执行所有运算，然后在每次运算后应用模或应用模。例如: $(2×4− 1)×3=3（mod\ 6）$ 相当于：2 × 4 = 2 (mod 6); 2 − 1 = 1 (mod 6); 1 × 3 = 3 (mod 6).

那到底为什么有帮助呢？事实证明，如果我们使用模算术，则具有运算结果，回到原始数字是不平凡的，因为许多不同的组合将具有相同的结果: 5 × 4 = 2 (mod 6); 4 × 2 = 2 (mod 6); 2 × 1 = 2 (mod 6).

如果没有模算术，结果的大小为它的解决方案提供了线索。否则，这条信息会被隐藏，而常见的算术属性会被保留。

3.3.3 强同态加密

如果我们回到同态加密并使用模运算，例如模 7，我们将得到：

$5^1 = 5\ (mod\ 7)$
$5^2 = 4\ (mod\ 7)$
$5^3 = 6\ (mod\ 7)$

和不同的指数会有相同的结果:

$5^5 = 3\ (mod\ 7)$
$5^{11} = 3\ (mod\ 7)$
$5^{17} = 3\ (mod\ 7)$

这是很难找到指数的地方。事实上，如果模数足够大，这样做就变得不可行，而现代密码学的很大一部分是基于这个问题的“难度”。该方案的所有同态属性都保留在模领域中：

encryption: $5^3 = 6\ (mod\ 7)$
multiplication: $6^2 = (5^3)^2 = 5^6 = 1\ (mod\ 7)$
addition: $5^3 · 5^2 = 5^5 = 3\ (mod\ 7)$

让我们明确说明加密函数： $E(v) = g^v\ (mod\ n)$ ，其中 v 是我们要加密的值。

这种同态加密方案存在局限性，尽管我们可以将加密值乘以未加密值，但我们不能将两个加密值乘以 (和除以)，也不能对加密值求幂。虽然从第一印象来看是不幸的，但这些属性将成为zk-SNARK的基石。

3.3.4 加密多项式

有了这样的工具，我们现在可以评估一个加密随机值为x的多项式，并相应地修改零知识协议。

让我们看看如何评估多项式 $p(x) = x^3−3x^2+ 2x$ 。正如我们以前建立的那样，多项式就是知道它的系数，在这种情况下，它们是: 1,-3,2。因为同态加密不允许对加密值求幂，所以我们必须得到从1到3的x幂的加密值: $E(x)$ ， $E(x^2)$ ， $E(x^3)$ ，这样我们可以对加密多项式求值如下:

$E(x^3)^1·E(x^2)^{-3}·E(x)^2=(g^{x3})^1·(g^{x^2})^{-3}·(g^x)^2= g^{1x^3}·g^{−3x^2} · g^{2x} = g^{x^3−3x^2+2x}$

作为这些操作的结果，我们在我们未知的某个 x 处对我们的多项式进行了加密。这是一个非常强大的机制，并且由于同态特性，相同多项式的加密计算在加密空间中总是相同的。我们现在可以更新协议的先前版本，对于d次多项式:

Veriﬁer:

采样一个随机值 s，即秘密
计算 s 的加密用指数0到d，即： $E(s^i) = g^{s^i}$
使用 s: $t(s)$ 评估未加密的目标多项式
s的加密指数被提供给证明者: $E(s^0)，E(s^1)，...，E(s^d)$

Prover:

计算多项式 $h(x)=p(x)/t(x)$
使用加密的指数 $g^{s^0}，g^{s^1}，.，g^{s^d}$ 和系数 $c_0，c_1，..，c_n$ 评估 $E (p(s)) = g^{p(s)} = ((g^{s^d})^{c_d})... (g^{s^1})^{c_1} · (g^{s^0})^{c_0}$ 和类似的 $E (h(s)) = g^{h(s)}$
将得到的 $g^p$ 和 $g^h$ 提供给验证者

Veriﬁer:

验证者的最后一步是检查加密空间中的 $p = t(s) · h$ ： $g^p = (g^h)^{t(s)} ⇒ g^p = g^{t(s)·h}$

由于证明者对s一无所知，因此很难提出不合法但仍匹配的评估。

虽然在这样的协议中，证明者的敏捷性是有限的，但他仍然可以使用任何其他方法来伪造证明，而无需实际使用所提供的 s 幂的加密，例如，如果证明者声称仅使用 2 次幂 $s^3$ 和 $s^1$ 有一个令人满意的多项式，这在当前协议中无法验证。

3.4 限制多项式

多项式的知识是其系数 $c_0, c_1,. . , c_i$ 。我们在协议中“分配”这些系数的方式是通过对秘密值 s 的相应加密幂求幂（即 $E(s^i)^{c_i} = g^{c_i·s^i}$ ）。我们已经在选择 s 的加密幂时限制了证明者，但这种限制并未强制执行，例如，可以使用任何可能的方法来找到满足方程 $z_p = (z_h)^{t(s)}$ 的任意值 $z_p$ 和 $z_h$ 并将它们提供给验证者而不是 $g^p$ 和 $g^h$ 。例如，对于一些随机 $r$ ， $z_h = g^r$ 和 $z_p = (g^{t(s)})^r$ ，其中 $g^{t(s)}$ 可以从提供的 s 的加密幂计算。这就是为什么验证者需要证明仅使用 s 的幂的加密来计算 $g^p$ 和 $g^h$ 而没有别的。

让我们考虑一个1次多项式的基本例子，该多项式具有一个变量和一个系数 $f(x)=c·x$ ，相应地，s的加密 $E(s)=g^s$ 。我们正在寻找的是确保只有s的加密，即 $g^s$ ，被一些任意系数c同态“乘以”，而不是其他任何东西。所以对于任意的c，结果必须是 $(g^s)^c$ 形式。

一种方法是要求对另一个移位的加密值与原始值一起执行相同的操作，充当“校验和”的算术模拟，确保结果是原始值的取幂。这是通过引入的指数知识假设Knowledge-of-Exponent Assumption (或KEA) 来实现的，更确切地说:

Alice有一个值a，她希望Bob指数到任何幂，唯一的要求是只有这个a可以指数，没有别的，以确保她：

选择随机 $α$
计算 $a' = a^α\ (mod\ n)$
向 Bob 提供元组 $(a, a')$ 并要求对每个值执行相同的任意取幂，并以结果元组 $(b, b')$ 进行回复，其中指数“ $α-shift$ ”保持不变，即 $b^α = b'\ (mod\ n)$

因为 Bob 无法从元组 $(a, a')$ 中提取 $α$ ，因此推测 Bob 可以产生有效响应的唯一方法是通过以下过程：

选择一些值c
计算 $b = (a)^c\ (mod\ n)$ 和 $b' = (a ')^c\ (mod\ n)$
回复 $(b, b')$
有了回答和 $α$ ，Alice检查等式： $(b)^α = b'$ ; $(a^c)^α = (a′)^c$ ; $a^{c·α} = (a^α)^c$
结论:
- Bob 对元组的两个值应用了相同的指数（即 c）
- Bob只能使用原始的Alice元组来维持α关系
- Bob知道应用的指数c，因为产生有效 (b，b ′) 的唯一方法是
- 爱丽丝没有学习c，原因是鲍勃无法学习 $α$

最终，这样的协议向Alice提供了一个证据，证明Bob确实将a乘以他已知的某个值，并且他不能进行任何其他操作，例如乘法、加法，因为这将消除 $α$ 移位关系。

在同态加密上下文中，幂运算是加密值的乘法。我们可以在简单的单系数多项式 $f(x)=c·x$ 的情况下应用相同的构造：

验证者选择随机s， $α$ ，并为幂1及其 “移位” 提供 $x = s$ 的评估 : $( g^s，g ^{α·s})$
验证者应用系数c:（（gs）c，（gα·s）c）=（gc·s，gα·c·s）
验证者检查 :( gc·s)α = g α·c·s

这种结构限制证明者仅使用提供的加密 s，因此证明者可以仅将系数 c 分配给验证者提供的多项式。我们现在可以将这种单项多项式方法缩放为多项多项式，因为每个项的系数分配是单独计算的，然后同态地“相加”在一起。因此，如果向证明者提供 s 的加密幂以及它们的移位值，他可以评估原始多项式和移位多项式，其中必须进行相同的检查。特别是对于 d 次多项式：

验证器提供加密权限gs0，gs1，gsd及其位移gαs0，gαs1，gαsd
验证程序：
- 使用提供的s:gp（s）=gs0 c0·gs1 c1·…的幂计算加密多项式gsd cd=gc0s0+c1s1++cdsd
- 用s的幂的相应 α 位移来评估加密的 “移位” 多项式: g α p(s) = gαs0 c0 · gαs1 c1 · . . · gαsd cd = gc0αs0 c1αs1...cdαsd = gα(c0s0 c1s1...cdsd)
- 将结果作为 $g^p$ ， $g^{p'}$ 提供给验证者
验证者检查： $(g^p)^α=g^{p'}$

对于我们之前的示例多项式 $p(x) = x^3 − 3x^2 + 2x$ ，这将是：

验证者提供 $E(s3) 、E(s2) 、E(s)$ 及其位移 $E(αs3) 、E(αs2) 、E(α s)$
Prover评估：
Veriﬁer checks (gp)α = gp′ :

现在我们可以确定，验证程序除了使用验证程序提供的多项式外，没有使用任何其他方法，因为没有其他方法来保持 $α$ 移位。此外，如果验证者希望确保在验证者的多项式中排除一些s的幂，例如j，他将不提供加密 $g^{s^j}$ 及其移位 $g^{αs^j}$ 。

与我们一开始的相比，我们现在有了一个健壮的协议。然而，无论加密如何，零知识属性仍然存在一个明显的缺点：虽然理论上多项式系数 $c_i$ 可以有很大范围的值，但实际上它可能非常有限（上例中为 6），这意味着验证者可以暴力破解有限范围的系数组合，直到结果等于证明者的答案。例如，如果我们考虑每个系数的 100 个值的范围，则 2 次多项式将总共有 100 万个不同的组合，考虑到蛮力将需要不到 100 万次迭代。此外，即使在只有一个系数且其值为 1 的情况下，安全协议也应该是安全的。

3.5 Zero-Knowledge

因为验证器只能从验证器发送的数据中提取关于未知多项式p（x）的知识，所以让我们考虑那些提供的值（证明）： $g^p, g^{p'}, g^h$ 。他们参与以下检查：

gp=gh（多项式p（x）有t（x）的根）

（gp）α=gp′t（s）（使用正确形式的多项式）

问题是我们如何改变证据，使支票仍然有效，但无法提取任何知识？从上一节可以得出一个答案：我们可以用一些随机数δ（δ）来“移位”这些值，例如（gp）δ。现在，为了提取知识，首先需要找到被认为不可行的δ。此外，这种随机化在统计学上与随机性是无法区分的。

为了保持关系，让我们检查验证者的检查。证明者的值之一位于方程式的每一侧。因此，如果我们用相同的 δ “移动” 它们中的每一个，方程必须保持平衡。

具体地，证明者对随机 δ 进行采样，并用g α p(s) δ gh(s) δ 对其证明值求幂，并提供给验证者进行验证:

(gp)δ = gh δ t(s) (gp)δ α = gp′ δ

合并后，我们可以观察到支票仍然有效：

注意: 零知识是多么容易被编织到建筑中，这通常被称为 “免费” 零知识。

3.6 Non-Interactivity

到目前为止，我们有一个交互式零知识方案。为什么会这样？由于该证明仅对原始验证者有效，其他任何人（其他验证者）都不能信任同一证明，因为：

验证者可以与证明者勾结，并披露那些允许伪造证明的秘密参数s，α
出于同样的原因，验证者可以自己生成假证据
验证者必须存储 α 和t(s)，直到所有相关的证明都被验证，这允许额外的攻击面，可能会泄露秘密参数

因此，为了证明语句（在这种情况下是多项式的知识），需要与每个验证者进行单独的交互。

虽然交互式证明系统有其使用案例，例如，当证明人只想说服一个专用的验证人（称为指定验证人），这样证明就不能再用于向其他人证明同一陈述时，当一个人需要同时（例如，在区块链等分布式系统中）或永久地说服多方时，这是非常有效的。验证方需要始终保持在线，并对每个验证方执行相同的计算。

因此，我们需要的秘密参数是可重用的，公开的，可信的和不可滥用的。

让我们首先考虑在秘密 (t(s)，α) 产生后如何保护它们。我们可以像验证者在发送给证明者之前对s的指数进行加密一样对它们进行加密。然而，我们使用的同态加密不支持两个加密值的乘法，这对于验证检查以使t(s) 和h以及p和 α 的加密相乘都是必需的。这就是密码配对的地方。

3.6.1 加密值的乘法

密码配对（双线性映射）是一种数学构造，用函数 $e(g^∗, g^*)$ , 给定来自一组数字的两个加密输入（例如， $e(g^a，g^b)$ ，允许将它们确定地映射到不同数字输出集中的乘法表示，即， $e(g^a,g^b)=e(g,g)^{ab}$ 。

由于源和输出编号集合不同，因此配对的结果不能用作另一个配对操作的输入。我们可以将输出集 (也称为 “目标集”) 视为来自 “不同的宇宙”。因此，我们不能将结果乘以另一个加密值，并通过名称本身建议我们一次只能乘以两个加密值。在某种意义上，它类似于一个散列函数，它将所有可能的输入值映射到一组可能的输出值中的一个元素，并且它不是平凡可逆的。

注意: 乍一看，这种限制只能阻碍依赖的功能，具有讽刺意味的是，在zk-SNARK情况下，它是该方案的安全性所拥有的最重要的属性。

配对函数 $e(g^*, g^*)$ 的一个基本（技术上不正确）的数学类比是说明有一种方法可以“交换”每个输入的基数和指数，这样基数 $g$ 在转换过程中会被修改成指数，例如 $g^a → a^g$ 。然后将两个“交换的”输入相乘，使得原始 a 和 b 值在相同的指数下相乘，例如： $e(g^a, g^b) = a^g · b^g = (ab)^g$

因此，由于在“交换”期间使用结果 $(ab)^g$ 在另一个配对（例如， $e ((ab)^g , g^c)$ ）中改变了碱基，因此不会产生所需的加密乘法 $abc$ 。配对的核心属性可以用等式表示：

e(ga, gb) = e(gb, ga) = e(gab, g1) = e(g1, gab) = e(g1, ga)b= e(g1, g1) ab= . . .

从技术上讲，配对的结果是目标集不同生成器g下原始值的加密产物，即 $(g^a，g^b)=g^{ab}$ 。因此，它具有同态加密的特性，例如，我们可以将多对的加密产物添加到一起：

$e(g^a, g^b) · e(g^c, g^d) = g^{ab} · g^{cd} = g^{ab+cd} = e(g, g)^{ab+cd}$

注意：加密配对利用椭圆曲线来实现这些属性，因此从现在起，符号 $g^n$ 将表示曲线上的生成器点，该点将被添加到自身 $n$ 次，而不是我们在前面部分中使用的乘法群生成器。

3.6.2 Trusted Party Setup

有了加密配对，我们现在可以设置安全的公共和可重用参数。让我们假设我们信任一个诚实的一方来生成秘密 s 和 α。一旦 α 和具有相应 α 位移的 s 的所有必要幂被加密（gα, gsi , gαsi for i in 0, 1, ..., d），必须删除原始值。

这些参数通常被称为公共参考字符串common reference string或CRS。CRS生成后，任何prover和veriﬁer都可以使用它来执行非交互式零知识证明协议。虽然不重要，但CRS的优化版本将包括对目标多项式target polynomial $g^{t(s)}$ 的加密评估。

此外，CRS分为两组（对于 $0、1、…、d$ 中的 $i$ ）：

证明Proving key: $( g^{s^i}，g^{αs^i})$
Veriﬁcation key: $(g^{t(s)}, g^α)$

由于能够乘以加密值，veriﬁer可以在协议的最后一步检查多项式，让veriﬁcation key veriﬁer进程从证明者那里接收到加密多项式评估 gp、gh、gp'：

checks that p = t · h in encrypted space: e gp, g1 = e gt, gh which is equivalent to e (g, g)p = e (g, g)t·h
checks polynomial restriction: e (gp, gα) = e gp′ , g

3.6.3 信任多人中的一人

虽然可信设置是有效的，但它并不有效，因为 CRS 的多个用户将不得不相信一个删除的 $α$ 和 $s$ ，因为目前没有办法证明这一点。因此，有必要最小化或消除这种信任。否则，不诚实的一方将能够在不被发现的情况下制作假证据。

实现这一点的一种方法是由多方使用前面部分中介绍的数学工具生成复合 CRS，这样这些方都不知道秘密。这是一种方法，让我们考虑三个参与者 Alice、Bob 和 Carol，对应的索引为 A、B 和 C，对于 i 在 1、2、...中。 . . , d:

Alice 对她的随机 $s_A$ 和 $α_A$ 进行采样并发布她的 CRS： $(g^{si_A}, g^{α_A}, g^{α_As^i_A})$
Bob生成他的 $α_B$ 和 $s_B$ ，增强Alice 的CRS通过同态加密乘法, $(gαA)αB gαAsiαBsi B = g (sAsB),gαAαB, gαAαB (sAsB)$ and publishes the resulting two-party Alice-Bob CRS: $gsi AB, gαAB , gαAB si AB$
Carol 的 $s_C$ 和 $α_C$ 也是如此：

作为这种协议的结果，我们有复合 $si = s^i_As^i_Bs^i_ C$ 和 $α = α_Aα_Bα_C$ 并且没有参与者知道其他参与者的秘密参数，除非他们串通。事实上，为了学习 $s$ 和 $α$ ，必须与其他所有参与者串通一气。因此，即使一个人是诚实的，也无法提供假证明。

注意：此过程可以根据需要对尽可能多的参与者重复。

可能存在的问题是如何验证参与者是否与 CRS 的每个值一致，因为对手可以采样多个不同的 s1、s2、...。 . . 和α1, α2, . . .，并将它们随机用于 s 的不同幂（或提供随机数作为增强的公共参考字符串），从而使 CRS 无效且不可用。

幸运的是，因为我们可以使用配对来乘以加密值，所以我们能够执行一致性检查，从第一个参数开始，并确保每个下一个参数都是从它派生的。参与者发布的每个 CRS 都可以检查如下：

我们将 $s$ 的 1 次幂作为规范值，并检查其他所有幂次的一致性： $e(g^{s^i}, g) = e(g^{s^1}, g^{s^{i−1}})$ for example:
- Power 2: $e(g^{s^2}, g)=e(g^{s^1}, g^{s^1})⇒e(g,g)^{s^{2}}=e(g,g)^{s^{1+1}}$
- Power 3: $e(g^{s^3}, g)=e(g^{s^1}, g^{s^2})⇒e(g,g)^{s^{3}}=e(g,g)^{s^{1+2}}$
我们现在检查前一步中的值的α-shift是否正确：

请注意，虽然我们验证每个参与者都与他们的秘密参数一致，但使用先前发布的 CRS 的要求并未对每个下一个参与者强制执行（在我们的示例中为 Bob 和 Carol）。因此，如果对手是链中的最后一个，他可以忽略先前的 CRS 并从头开始构造有效参数，就好像他是链中的第一个，因此是唯一知道秘密 s 和 α 的人。

我们可以通过额外要求除第一个参与者之外的每个参与者加密和发布他的秘密参数来解决这个问题，例如，Bob 还发布：

这允许验证 Bob 的 CRS 是 Alice 参数的适当倍数，因为 i in 1, 2, . . . , d:

$e(g^{s^3}, g)$

同样，Carol必须证明她的CRS是Alice-Bob的CRS的适当倍数。

这是一个强大的CRS设置方案，不完全依赖任何一方。实际上，即使只有一方是诚实的，并且删除并且从不共享其秘密参数，即使所有其他各方都合谋，它也是非常明智的。因此，CRS 设置中不相关的参与者越多，伪造证据的可能性就越小，如果竞争方参与，其可能性就可以忽略不计。该方案允许涉及对设置的易读性有疑问的其他不受信任的各方，因为验证步骤确保他们不会破坏最终的公共参考字符串 (也包括使用弱 α 和s)。

3.7 多项式知识的简洁非交互论证

我们现在准备巩固进化的zk-SNARKOP协议。形式上，为简洁起见，我们将使用大括号来表示由其旁边的下标填充的一组元素，例如si i ∈[d] 表示集合s1，s2，...，sd。

已商定目标多项式t（x）和校准仪多项式的d次：

Setup：

生成随机值 $s$ , $α$
计算加密 $g^α$ and $g^{s^i}$ , $g^{αs^i}$
proving key: ( $g^{s^i}$ , $g^{αs^i}$ )
veriﬁcation key: $(g^α, g^{t(s)})$

Proving：

分配系数 $\{c_i\},i∈\{0,...,d\}$ （即knowledge）， $p(x) = c_dx^d + · · · + c_1x^1 + c_0x^0$
计算多项式 $h(x) = p(x)/t(x)$
使用 $g^{s^i}$ 计算加密多项式 $g^{p(s)}$ 和 $g^{h(s)}$
使用 $g^{αs^i}$ 计算加密移位多项式 $g^{αp(s)}$
生成随机 $δ$
设置随机证明 $π = (g^{δp(s)}, g^{δh(s)}, g^{δαp(s)})$

Veriﬁcation：

parse proof $π$ as $(g^p, g^h, g^{p'})$
检查多项式限制： $e(g^{p'},g)=e(g^p,g^α)$
检查多项式辅因子: $e(g^{p},g)=e(g^{t(s)},g^h)$

如果有可能将配对的结果重用为另一个乘法，这样的协议将是完全不安全的，因为证明者可以分配 $g^{p'}=e(g^p,g^α)$ ，然后它将通过“多项式限制”检查： $e (e(g^p,g^α), g) = e(g^p,g^α)$

3.7.1 结论

我们来到了知识协议的零知识简洁非交互式参数，用于多项式问题的知识，这是一个利基用例。虽然可以声称证明者只需将 t(x) 乘以另一个有界多项式即可轻松构造此类多项式 p(x) 以使其通过测试，但该构造仍然有用。

验证者知道证明者有一个有效的多项式，但不知道是哪个特定的。我们可以添加多项式其他属性的额外证明，例如：除以多个多项式，是多项式的平方。可能存在接受、存储和奖励所有已证明多项式的服务，或者需要对必要形式的未知多项式进行加密评估。然而，拥有通用方案将允许无数的应用。

4. 通用零知识证明

我们已经用一个简单但充分的例子铺平了道路，其中涉及大多数 zk-SNARK，现在可以推进该方案以执行零知识程序。

4.1 Computation

让我们考虑一个简单的伪代码程序：

Algorithm 1 Operation depends on an input:
function calc(w, a, b)
    if w then
        return a × b
    else
        return a + b
    end if
end function

从高级的角度来看，它与多项式完全无关，我们有协议。因此，我们需要找到一种方法将程序转换为多项式形式。那么第一步就是把程序翻译成数学语言，这个比较简单，同样的语句可以表示如下（假设w为0或1）：

$f(w, a, b) = w(a × b) + (1 - w)(a + b)$

执行 $calc(1，4，2)$ 并计算 $f(1，4，2)$ 将得到相同的结果：8。相反地，calc（0,4,2）和f（0,4,2）都将解析为6。我们可以用这种方式表达任何一种有限程序。我们需要证明（在这个例子中），对于表达式 f(w, a, b) 的输入 (1, 4, 2)，输出是 8，换句话说，我们检查相等性： $w(a × b) + (1 − w)(a + b) = 8$

4.2 Single Operation

我们现在有了用数学语言表达的通用计算，但我们仍然需要将其转换为多项式领域。让我们仔细看看简而言之什么是计算。其核心的任何计算都由以下形式的基本操作组成：

left operand operator right operand = output

两个操作数（即值）正在由一个运算符（例如，+、-、×、÷）进行操作。例如，对于操作数 2 和 3 以及运算符“乘法”，它们将解析为 2 × 3 = 6。因为任何复杂的计算（或程序）都只是一系列操作，首先我们需要找出这样的操作的单一性用多项式表示。

4.2.1 多项式的算术性质

让我们看看多项式是如何与算术运算相关的。例如，如果您取两个多项式 f(x) 和 g(x) 并尝试将它们相乘 $h(x) = f(x)×g(x)$ ，则 h(x) 在任意 x 处的计算结果 x=r 将是 f(r) 和 g(r) 评估结果的乘积。让我们考虑以下两个多项式： $f(x) = 2x^2−9x+10$ 和 $g(x) = −4x^2+15x−9$ 。

对于x=1，这些值将计算为： $f(1)=2− 9+10=3,g(1)=−4+15− 9 = 2$ .

让我们将多项式相乘： $h(x) = f(x) × g(x) = −8x^4 + 66x^3 − 193x^2 + 231x − 90$

如果我们检查结果多项式 $f(x) × g(x)$ 在 x = 1 处的评估，我们将得到： $h(1) = -8 + 66 - 193 + 231 - 90 = 6$ ，因此 x = 1 处的值 f(x) 和 g(x) 的数量相乘，并且分别在每隔一个 x 处相乘。同样，如果我们将 f(x) 和 g(x) 相加，我们将得到 $−2x^2 +6x+1$ ，在 x = 1 时其值为 5。

如果我们可以将操作数值表示为多项式（我们确实可以按照概述），那么通过算术属性，我们将能够获得操作数所施加的操作的结果。

4.3 执行操作

如果证明人声称有两个数字相乘的结果，那么验证者如何检查？为了证明单个操作的正确性，我们必须对提供的操作数强制执行输出（结果）的正确性。如果我们再看看操作的形式：

left operand operator right operand = output

同样可以表示为一个运算多项式： $l(x)\ 运算符\ r(x) = o(x)$

一些a被选择：

l(x) - at a表示 (求值为) 左操作数的值
r(x) - at a表示右操作数的值
o(x) - 在 a 处表示操作的结果（输出）

因此，如果操作和输出由这些多项式正确表示，则 $l(a)\ operator\ r(a) = o(a)$ 的计算结果应保持不变。将输出多项式 $l(a)\ operator\ r(a) − o(a) = 0$ 表示运算多项式满足 $l(x)\ operator\ r(x) − o(x) = 0$ 。此后，如果运算多项式有效，则它必须具有根 $a$ ，因此，它必须包含辅因子 $(x−a)$ ，这是我们证明的目标多项式，即 $t(x) = x − a$ .

例如，让我们考虑操作： $3 × 2 = 6$

它可以用简单多项式 $l(x) = 3x，r(x) = 2x，o(x) = 6x$ 表示，它们的计算值为 $a = 1$ ，即 $l(1) = 3; r(1) = 2；o(1) = 6$ 。

然后，运算多项式将是:

$l(x) × r(x) = o(x)$

$3x × 2x = 6x$

$6x^2 − 6x = 0$

值得注意的是，运算多项式有 (x − 1) 作为余因子： $6x^2 - 6x = 6x(x - 1)$

因此，如果证明者提供了这样的多项式 $l(x)、r(x)、o(x)$ 而不是之前的 $p(x)$ ，那么验证者将接受它为有效的，因为它可以被 $t(x)$ 整除。相反，如果证明者试图作弊并将输出值替换为 4，例如 $o(x) = 4x$ ，则运算多项式将是 $6x^2 - 4x = 0$ . 没有解 x = 1，因此 $l(x)×r(x)−o(x)$ 不能被 $t(x)$ 整除而没有余数：

$h(x) =6x + 2+ 2/(x-1)$

4.4 Proof of Operation

让我们修改我们最新的协议以支持单次乘法运算证明。回想一下，以前我们已经证明了多项式 p(x) 的知识，但现在我们处理三个 l(x)、r(x)、o(x)。虽然我们可以定义 p(x) = l(x)×r(x)−o(x)，但有两个相反的论点。首先，在我们的协议中，加密值的乘法（即 l(s) × r(s)）在证明阶段是不可能的，因为配对只能使用一次，并且它是“多项式限制”检查所必需的.其次，这将为证明者留下一个机会，可以随意修改多项式的结构，但仍保持有效的辅因子 t(x)，例如 p(x) = l(x) 或 p(x) = l(x) − r(x) 甚至 p(x) = l(x) × r(x) + o(x)，只要 p(x) 有根 a。这种修改有效地意味着证明是关于不同的陈述，这当然是不希望的。

这就是为什么多项式l(s)，r(s)，o(s) 的评估必须由证明者单独提供的原因。这意味着多项式的知识必须调整。本质上，验证者需要在加密空间中检查的是l(s)× r(s)-o(s) = t(s)h(s)。虽然验证者可以使用密码配对执行乘法，但减法 (− o(x)) 是一项昂贵的操作21，这就是为什么我们将o(x) 移到等式的右侧: l(x)r(x) = t(x)h(x)+o(x)。

在加密空间中，验证者的检查转化为：

e(g, g)l(s)r(s) = e(g, g)t(s)h(s)+o(s)

虽然设置阶段保持不变，但以下是更新的协议：