前言

在区块链背景下，zk-SNARK 是一种先进的安全技术，可以增强隐私并确保加密交易的透明度。

Zk-SNARK 允许在不泄露知识的情况下证明知识，从而保证用户信息的绝对保护。

Zcash 是领先的加密货币，采用 zk-SNARK 技术实现交易完全匿名化，确保高安全性，不暴露用户个人信息。这提高了用户进行在线交易时的安全性和可靠性。

在“探索 ZK-SNARK”研究系列的第 1 部分中，我将深入探讨有关 zk-SNARK 的重要细节以及该技术背后的底层算法和加密，非常详细且易于您理解。

zk-SNARK 的概念和作用机制

zk-SNARK 基础知识

Zk-SNARK的全称是Zero-Knowledge Succinct Non-Interactive Argument of Knowledge，大致翻译为“Concise and non-interactiveproof of non-knowledge discovery”（我这样翻译是为了更容易理解）。这是一种证明结构，允许一方（证明者）证明其拥有某些信息，例如密钥，而无需透露该信息，也不需要与另一方（验证者）合作。

目前，zk-SNARK 是最流行的证明系统。

我们将把首字母缩略词“zk-SNARK”分解成更小的组成部分，以最清楚地检查它们的含义。

  • “零知识”：这意味着输入信息将被隐藏，不会透露给验证者。换句话说，验证者无法知道有关该知识的任何信息，只能知道其有效性。

  • “Succinct”（短）：这意味着生成的证明很小，大约几百字节，并且验证很快。这是SNARK带来的第一个好处。

  • “非交互”：这是 SNARK 的第二个好处，双方（证明者和验证者），证明由从证明者到验证者的单个消息组成，无需来回通信。

  • “知识论证”：是一个技术术语，意思是如果验证者接受证明，那么证明者必须实际上知道与被验证的声明相关的秘密（而不仅仅是让验证者相信该陈述是真实的）。

作用机制

从数学上讲，zk-SNARK 由 3 种算法组成：

  • 密钥生成（KG）：这是一种密钥生成算法，它将生成一对密钥，一个用于证明（pk），一个用于验证（vk）。密钥生成算法将安全参数 λ 和 C 程序作为输入，然后输出密钥。此步骤也称为可信设置步骤。我们将在下面的部分详细介绍它。(pk, vk) = KG(λ, C)

  • 证明（P）：该证明算法将通过输入证明密钥 pk、陈述 x 和证人 w 来进行证明。输出是证明 prf.prf = P(pk, x, w)

  • 验证（V）：验证算法将验证密钥 vk、语句 x 和证明 prf 作为输入。输出是接受或拒绝。

验证结果 = V(vk, x, prf)

ZK-SNARK 的优点

  • ZK-SNARK 带来了许多重要的好处，特别是在增强各种应用程序的匿名性、安全性、可扩展性和交易效率方面。以下是软件应用程序的 2 个主要优势：

    1. 隐私：“零知识”属性允许隐藏与计算相关的敏感数据，同时仍然证明语句的正确性。换句话说，zk-snark 在不泄露个人信息的情况下进行交易，保持交易信息的匿名性和安全性。这在 Zcash 等加密货币中非常有用，用户可以在不透露交易金额、来源或目的地的情况下发送资金。

    2. 可扩展性：由于证明大小小，验证时间短，验证者可以快速知道计算是否忠实执行，而无需重新运行计算，从而减少验证复杂计算所需的时间和资源，从而提高系统性能和可靠性，同时还有助于降低成本并增强其可扩展性。

值得信赖的设立仪式

信任建立过程是一个重要步骤，只需执行一次即可生成一组必要的数据，以便以后每次部署加密协议时使用。

在 ZK-SNARK 中，此信任设置步骤对于生成证明和验证密钥是必要的。然后将这些密钥公开，允许参与者使用它们来创建和验证证据。

对于每个新的 C 程序，需要执行新的可信设置，因为它取决于该 C 程序的详细信息。在设置过程中，KG 密钥生成过程使用秘密 lambda 和 C 程序作为输入来生成公钥 (pk) 和验证密钥 (vk)。

（pk，vk）= KG（λ，C）

因此，可靠的设置过程不是标准的，应该针对每个新程序单独进行。

有毒废物（有毒废物）

可靠的设置需要一个名为 lamda 的秘密参数。这个参数通常被称为“有毒废物”，有时会导致 zk-SNARK 难以应用于实际应用。

这是因为，谁掌握了这个参数，就有能力制造假证据。具体来说，lambda 持有者可以为任何具有公共输入 x 的 C 程序生成一个名为 fakeProof 的假证明，这样

V（vk，x，fakeProof）= true

在不知道秘密证人 w 的情况下被判定为真实。这是灾难性的！

为 zk-SNARK 生成公共参数的最有效方法是通过某人生成公钥和私钥对（类似于 ECDSA 密钥对），然后销毁私钥。但令人担忧的是，如何确定这边确实消除了那些“有毒废物”？

因此，为了解决这个问题，应用了多方计算（Multi-Party Computation，MPC）。

MPC 是一种加密协议，允许多方参与分布式计算，而任何一方都无法访问另一方的机密数据。

在每个信任建立过程中，多方共同参与该过程以生成必要的加密组件，例如公钥（pk）和验证密钥（vk）。各方都为此过程贡献了部分机密数据。

此过程后各方的最终目标是彻底消除有毒废物。这种情况下的可靠性假设是，只要 n 个参与者之一是诚实的，最终结果就保证是安全的。

在信任设置期间，n 方中的每一方都会携带其秘密 lambda 来共同生成证明和验证密钥。

为了让这个设置失败，需要所有 n 方都怀有恶意并互相分享他们的秘密。然而，只要其中一方决定不泄露其秘密，信托的建立过程仍然会成功，从而不可能产生虚假证据。

zk-snark 背后的数学和编码

数学基础

群论

ZK-SNARK 利用群论对椭圆曲线和其他群进行计算，特别是在使用双线性配对和相关算法时。

简单地说，群就是一组元素{a,b,c,…}结合二元运算，这里用“•”表示。

如果集合和运算满足以下属性，则称为群：

  • 闭包：对于组 G 中的所有 a 和 b，运算 a • b 也必须在 G 中。

  • 结合性：对于 G 中的所有 a、b 和 c，运算 (a • b) • c 必须等于 a • (b • c)。

  • 单位元素：G 中必须有一个元素 e，使得对于 G 中的每个元素 a，操作 e • a 和 a • e 等于 a。这个元素是独一无二的。

  • 逆元素：对于 G 中的每个元素 a，G 中必须有一个元素 b，通常称为 a^-1，使得操作 a • b 和 b • a 等于来自单元 e 的操作。

子群

当群中元素的子集服从该群的所有属性时，该集合称为原群的子群。

字段

域是一种特殊的代数结构，其中一组元素执行两个基本运算：加法和乘法。每个领域都必须遵守一系列基本公理，这些公理定义并保证了其一般属性。

以下是域必须满足的公理，其中 a、b 和 c 是域 F 的任意元素：

  1. 加法和乘法的结合性：a + (b + c)= (a + b) + c 且 a · (b · c) = (a · b) · c

  2. 加法和乘法的交换律：a + b = b + a 和 a · b = b · a

  3. 加法和乘法方程：F 中存在两个不同的元素 0 和 1，使得 a + 0 = a 和 a · 1 = a

  4. 加法逆元：对于 F 中的每个 a，F 中都存在一个元素，表示为 -a，称为 a 的加法逆元，使得 a + (−a) = 0

  5. 乘法逆元：对于 F 中的每个 a≠ 0，F 中存在一个元素，表示为 a^ -1，称为 a 的乘法逆元，使得 a · a^ -1 = 1

  6. 乘法相对于加法的分布：a· (b + c) = (a·b) + (a·c)

字段的示例包括具有加法和乘法的实数集，以及以素数为模的整数，其中定义了加法和乘法。

有限域

在 ZK-SNARK 中，所有运算都在有限域中执行，其中值和运算以素数为模或基于素数多项式定义。

有限域是具有有限数量元素的域，例如以 p 为模的整数集，其中 p 是素数。

对于有限域，域中元素的数量（称为域的阶）可以是：

  • 一些素数（素数域）

  • 或者素数的幂（扩展域）

在简单素数域中，元素可以用 0 到 p-1 之间的整数表示，其中 Zp = {0, 1, …, p-1}。

Zp 的扩展称为乘法群 Zp*，由与 p 互质的元素组成，即 Zp* = {1, …, p-1}。

有限域生成器

在每个有限域中，都存在一个称为生成器的元素，它能够使用其求幂生成群中的所有元素。

例如，考虑素数域中的群 Z5* Z5 = {0, 1, 2, 3, 4}，则 Z5* = {1, 2, 3, 4}。 在 Z5* 组中，乘法是二元运算，并且乘法以模 5 执行；例如，乘以 3 × 4 不会得到 12，而是得到 2，因为 12 mod 5 = 2。

群 Z5* 是循环群并具有生成元 2 和 3，因为：

  • 对于生成器 2，我们有：

2^0=1，

2^1 = 2，

2^2=4，

2^3=3，

2^4 = 1（重复循环）

  • 对于生成器 3，我们有：

3^0=1，

3^1 = 3，

3^2=4，

3^3=2，

3^4 = 1（重复循环）

这些属性使 Z5* 成为一个强大的加密操作组，并且通常用于 ZK-SNARK 等加密算法中。

群同态

同态是两个相似的代数结构（例如群或域）之间的映射，并且它们保留该结构内的运算。

具体来说，同态是从 A 组到 B 组的映射 f，当这两个组具有相同的二元运算（例如乘法或加法）时。此映射保留了操作，这意味着：

如果 ⋅ 是 A 组和 B 组结构中的二元运算，则对于 A 组中的每个元素 a 和 b，映射 f 满足条件：

f ( x ⋅ y )= f ( x )⋅ f ( y )

这确保了应用于组 A 中的元素的运算结果在通过 f 映射到组 B 后，仍然与直接对组 B 执行的运算相同。

同态是处理双线性对属性的基础，使得 zk-SNARK 中生成和验证证明的过程更加高效。

多项式

多项式是构建二次算术程序 (QAP) 的核心组成部分，其中问题通过多项式表示并通过多项式评估和承诺来解决。

多项式是由变量和常数组成的数学表达式，使用加法、乘法和非负整数指数求幂。

例如，多项式 5x² + 2x + 8 就是一个很好的例子。

当考虑多项式方程时，它可以表示数字之间无数个不同的方程。例如，如果方程 A(x) + B(x) = C(x) 成立，那么它对于 x 的所有值也成立，例如：

A（0）+B（0）=C（0）

A（1）+ B（1）= C（1）

A（2）+B（2）=C（2）

A（3）+B（3）=C（3）

等等。

关于多项式的次数，由多项式中变量的最大幂决定。例如，多项式 6x⁴ + 2x³ + 3 的次数为 4，因为变量 x 的最高次方为 4。

密码学

哈希函数

哈希函数广泛用于在加密协议中创建“承诺”，有助于确保数据无法在未经检测的情况下被修改。

哈希函数是一种算法或数学函数，可将可变长度的输入数据字符串转换为固定长度的输出字符串（称为哈希值）。

哈希函数表示公式可以描述如下：

f（米）= H

其中 f 是哈希函数，m 是消息，H 是结果哈希值。

哈希函数具有许多重要的属性，使其在许多密码应用程序中非常有用。这些属性包括：

  • 原像抵抗：从数学上讲，从哈希值中检索原始消息非常困难。

  • 第二个原像抵抗：给定一个特定的输入消息及其哈希值，很难找到另一个产生相同哈希值的消息。

  • 抗碰撞性：很难找到产生相同哈希值的两个不同消息。

好的哈希函数的一个非常理想的特性是雪崩效应。 这是输入的微小变化会导致输出发生较大变化的特性，使输出显得随机且难以区分。

加密

简而言之，加密是将输入消息（明文）转换为看似随机的输出（密文）的过程，以便只有授权人员才能解码和理解该信息。加密基于密钥的使用，密钥是发送者和接收者用来加密和解密信息的一组数学值。

加密算法有两种类型：对称加密和非对称加密。

对称加密

在对称加密中，通信过程中涉及的所有各方都使用相同的密钥来加密和解密消息。该密钥在双方之间保密，以确保交换信息的安全。

非对称加密

在非对称加密（也称为公钥加密）中，有两种类型的密钥：用于加密的公钥和用于解密的私钥。私钥由接收者保密（因此称为“私钥”），而公钥可以与任何想要发送机密信息的人广泛共享（因此称为“私钥”）。

非对称加密广泛应用于以下几种情况：

  • 发送安全消息：发送者使用接收者的公钥对消息进行加密，然后将其发送给接收者。只有拥有私钥的接收者才能解密并读取消息。

  • 证明私钥的所有权（了解）：在证明私钥所有权的过程中，发送者使用其私钥对消息进行加密（或签名），然后将其发送给接收者。接收者使用发送者的公钥来解密消息。此过程通常称为数字签名，如此加密的消息称为“数字签名”。由此，数字签名证明该消息是由拥有相应私钥的人发送的，并且还有助于验证消息中信息的完整性。

同态加密（Homomorphic crypto）

同态加密在高级零知识证明的设计中具有很大影响力，因为它允许对加密数据进行计算而无需解密它们。

同态加密是一种特殊类型的加密，允许直接对加密数据执行计算。这意味着可以对加密数据执行额外的计算，而无需密钥。这些计算的结果保持加密状态，确保安全性，而不会泄露原始数据内容。

在实践中，允许对加密数据进行各种任意计算的全同态加密仍然存在很多局限性，尚未得到广泛应用。然而，对同态结构进行某些操作是可行的，并且已经在实际应用中得到应用。

这些操作包括加密数据的加法和乘法，这为无需解密的安全数据处理开辟了新的可能性。

椭圆曲线密码术 (ECC)

在 ZK-SNARK 中，由于实现双线性配对的分组操作，椭圆曲线发挥着重要作用。 ECC（椭圆曲线密码学）提供了一个用于创建和验证零知识证明的高效平台。

椭圆曲线是满足特定数学方程的一组点。椭圆曲线的方程具有以下形式：

其中，a和b是已知常数。该方程的图形如下所示：

椭圆曲线有许多不同的表示形式，但该技术主要是寻找满足特定数学方程的点。

椭圆曲线的特性使其在许多数学领域，尤其是密码学领域非常重要。

椭圆曲线的一个有趣的特性是它们的水平对称性。曲线上的任何点都可以反映在 x 轴上，同时保持曲线完整。这意味着，如果您在曲线上取任意两点并通过它们画一条线，该线将在第三个点处与曲线相交。

想象一下这是一场台球游戏，球从一个点射出，当它击中椭圆曲线时，它会垂直向上或垂直向下弹起，具体取决于它相对于 x 轴的位置。

椭圆曲线的一个有趣的特性是，您可以在曲线上“点”两个点来创建一个新点。您还可以连续“点”一个点以在曲线上创建不同的点。

但有趣的是，如果你知道终点和起点，计算从起点到终点所需的“点”数量是非常困难的！

想象一下一个人在一个房间里独自玩耍，按照游戏规则击球。然后其他人进来看看球的最终位置。即使他们知道初始位置和比赛规则，如果不从头开始回顾整个比赛，他们也无法知道球被击中了多少次。这在密码学中创造了一种特殊的属性，称为不可逆性，并且是许多强大应用程序（例如陷门函数）的基础。

椭圆曲线上的离散对数是一个难题，它支撑着基于椭圆曲线的密码学。与分解不同的是，没有捷径可以解决这个问题，这使得破解椭圆曲线密码学比使用 RSA 和 Diffie-Hellman 更难。

虽然 ECC 通过较短的密钥提供了高级别的安全性，但它在低功耗设备上仍然保留了良好的性能。这使得 ECC 成为资源有限的移动设备和系统上的加密应用程序的理想选择。

在本节的最后，我阐述了 zk-SNARK 背后的一些基本数学和编码概念，在下一部分中，我将详细阐述更高级的概念，例如二次算术程序、椭圆曲线配对。

感谢您阅读本文。如果您喜欢这篇文章，别忘了关注并留下掌声。

文章来源：团队技术/研究 – AlphaTrue

参考来源：

1.来源​​：Reitwiessner，C.（2016）。简而言之，zkSNARKs。以太坊博客，6，1-15。https://chriseth.github.io/notes/articles/zksnarks/zksnarks.pdf

2. https://medium.com/coinmonks/from-zero-to-hero-in-zero-knowledge-proofs-part-7-61d639c2ef02

3. https://celo.academy/t/zk-snarks-proofs-as-a-privacy-solution-on-the-blockchain/1961

4.来源：Chen, T., Lu, H., Kunpittaya, T., & Luo, A. (2022)。zk-snarks 综述。arXiv 预印本 arXiv:2202.06877。https://arxiv.org/pdf/2202.06877.pdf

5. https://medium.com/coinmonks/from-zero-to-hero-in-zero-knowledge-proofs-part-8-262f923f1537

6. https://medium.com/@hira.siddiqui/from-zero-to-hero-in-zero-knowledge-proofs-part-2-ef17ce470f2d

7. Easttom, W. (2022). 现代密码学：加密和信息安全的应用数学。Springer Nature。

8. https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/