去中心化隐私计算：ZEXE 和 VERI-ZEXE

介绍

ZEXE (零知识执行) 协议于 2018 年出现，引入了去中心化私有计算 (DPC) 的密码学原语。它旨在解决去中心化账本存在的两个主要缺点：隐私性和可扩展性。

让我们以比特币和以太坊为例。我们看到所有交易的历史记录都是公开的（这可能会泄露你公司的供应商、熟人或你雇用的服务的敏感信息）。以太坊提供可编程性，但要求每个节点执行每个操作，其中性能最差的设备充当瓶颈。ZCash 解决了隐私问题，但不提供可编程性，仅提供私有交易。ZEXE 试图兼得两者之长：

• 私下运行任意程序。
• 能够离线运行计算。
• 提供计算完整性的证明，节点可以快速验证。

有关该协议的概述，我们推荐我们之前关于 ZEXE 的文章。作为快速提醒，该协议提供以下功能：

1. 可编程性：我们可以运行任意程序。
2. 快速验证：我们可以通过使用 zk-SNARKs（零知识简洁非交互式知识论证）来证明我们计算的有效性，zk-SNARKs 提供简短（简洁）的证明，验证者可以在链上以几毫秒的速度进行检查。
3. 数据和函数隐私：当我们在账本中执行转换时，该协议会隐藏相关的输入信息和函数。

自 ZEXE 协议推出以来，人们对其进行了多次改进，以提高其性能。本文将分析原始协议与最近的提案 VERI-ZEXE 之间的差异。VERI-ZEXE 的作者将其协议的性能与 ZEXE 的原始提案及其早期修改进行了比较。当前改进版本的 ZEXE 协议与 VERI-ZEXE 之间没有比较。

构建块

我们提到 ZEXE 协议使用 zk-SNARKs，它允许我们为给定的计算提供完整性证明，任何人都可以比重新执行的朴素方法更快地验证。系统最高的成本与证明的生成有关，这依赖于椭圆曲线运算。你可以在 我们之前的文章 中查看一些 SNARK 系统的基础知识。

现代证明系统有两个主要的构建块：多项式交互式预言证明 -PIOP-（它将给定的计算转换为多项式方程）和多项式承诺方案 -PCS-。我们根据我们的选择获得不同的证明系统，每个系统都有优点和缺点。PIOP 的一些例子是 Marlin、PLONK（基于 Lagrange 基的置换，用于普适的非交互式知识论证）-及其所有衍生产品- 和 Spartan。在 PCS 中，我们有 KZG (Kate-Zarevucha-Goldberg)、FRI（快速里德-所罗门交互式预言邻近证明）、Bulletproofs 和 DARK（丢番图知识论证），仅举几例。

为了能够以快速有效的方式执行证明，我们需要“SNARK 友好”的密码学原语和操作。如果一个函数作为算术电路的表示很小，那么它就是“SNARK 友好”的。例如，直观且直接的按位运算（例如 AND 和 XOR）具有复杂的电路表示。因此，在 SNARK 的上下文中，函数的成本必须考虑用于表示运算及其变量的算术电路的复杂性。

SNARK 系统中的很大一部分成本来自：

• 多标量乘法（MSM）。这些是 $Q = \sum_k a_k P_k$ 形式的运算，其中 $a_k$ 是数字，$P_k$ 是属于椭圆曲线的点。
• 椭圆曲线配对。它们用于某些系统的验证。它们涉及字段扩展和不同椭圆曲线组之间的运算。
• 在非原生字段上的多项式求值。
• Fiat-Shamir 变换：需要哈希函数来生成挑战。许多成熟的密码学原语都具有复杂的算术电路表示，这使得它们的评估成本很高。

研究工作正在努力解决所有这些问题。GPU 或 FPGA 可以 加速 MSM 的计算。具有更友好的算术电路的新哈希函数和加密方案可以进一步降低常用密码学原语的复杂性（例如，Poseidon 和 Vision and Rescue）。

VERI-ZEXE 的选择

为了解决这些问题，VERI-ZEXE 改变了证明系统和密码学原语。以下是一些主要的修改：

• PLONK 作为 PIOP。在过去几年中，PLONK 已经看到了几次重大改进，例如高度自定义门、查找表的使用以及多线性多项式的使用（避免使用快速傅里叶变换）（例如 turboPLONK、ultraPLONK 和 hyperPLONK）。
• 通过 累积方案 的轻量级验证器电路。该协议将配对检查从 SNARK 电路中移出，并将验证延迟到账本的验证器。
• 实例合并。执行交易时，必须检查记录的出生和死亡 predicate。该协议没有单独验证每个 predicate，而是利用了这些 predicate 可以成对出生/死亡这一事实，从而产生更大的 predicate。但是，由于组合 predicate 的验证具有更简单的电路表示（这意味着操作的数量不会线性缩放），因此总体成本降低了。
• 证明批处理。我们可以通过利用某些 PCS（例如 KZG）的属性来批量生成和验证证明。这些允许同时打开 $N$ 个不同的 commitment，其成本不会随着 commitment 数量线性缩放（也就是说，你可以打开 $N$ 个 commitment 的成本低于 $N$ 个单独打开的成本）。
• 通过查找表的可变基 MSM。MSM 通过将 Pippenger 算法（将标量拆分为块）与 查找表 相结合来进行，从而降低了椭圆曲线加法的成本。
• 在非原生字段上的多项式求值。证明者和验证者的电路位于不同的有限域中。解决这个问题的一种方法是使用两对椭圆曲线。VERI-ZEXE 使用带有查找的范围检查的模块化加法和乘法，从而产生稍微复杂的电路。
• SNARK 友好的对称原语。使用具有更小电路表示的抗碰撞哈希函数、伪随机生成器和承诺方案（这减少了操作的数量），从而减少了内存和时间的使用。例如，Fiat-Shamir 变换使用 Rescue 排列的海绵结构。

PLONK 及其添加的使用，以及密码学原语的更简单构造，导致约束总数的数量级减少，这反过来又减少了 MSM 乘法的规模和总体证明时间。

累积方案 (AS) 和增量可验证计算 (IVC)

证明的验证需要计算昂贵的配对运算。原始的 ZEXE 协议使用增量可验证计算，通过 SNARK 递归来证明用户定义的 predicate 的可满足性：给定步骤 $N$ 的计算，证明者将收到状态 $zN$ 和证明 $\pi{N-1}$，证明上一步的正确执行。然后，证明者将执行步骤 $N$ 并生成证明 $\piN$，该证明证明“新状态 $z'$ 是正确执行的结果，并且 $\pi{N-1}$ 为真（换句话说，证明者正确地完成了之前的 $N-1$ 步）”。在最后一步中，计算负担随之而来：为了检查证明，验证者的计算嵌入在证明者的电路中，这减慢了证明的生成速度。

累积方案以不同的方式进行，将最终证明的验证延迟到账本的验证器。在计算的每个步骤中，证明者都会收到当前状态和一个累加器，该累加器是经过部分验证的（证明者检查累积结果是否正确，但不计算椭圆曲线配对运算）。累加器中的群元素必须使用随机数生成器进行掩码，该随机数生成器充当累加器验证器的附加 witness（秘密输入）。这种掩码确保累加器不会泄露有关正在执行的计算的信息，

查找表和高效的模块化运算

在 Pippenger 算法中使用查找表进行椭圆曲线加法和高效的模块化算术运算，可以将 PLONK 约束的数量减少 6 倍。

MSM 查找表背后的想法如下：

$Q = \sum_i a_i P_i$

Pippenger 算法将标量 $a_i$ 分成长度为 $c$ 的 $m$ 个窗口（例如，标量是一个 256 位数字，我们选择一个 8 位窗口）。我们可以将每个标量写成

$a_i = \sumj a{ij} 2^{mj}$

其中每个 $a_{ij}$ 的范围都在 $0,1,...,2^c-1$ 中。我们可以为每个点 $P_i$ 计算标量值的所有可能组合 $2P_i, 3P_i, 4P_i,...,(2^c-1)P_i$。

我们现在可以通过查看表格（它比纯粹的椭圆曲线运算具有更简单的描述）来计算结果 $Q{ij} = a{ij}P_i$，并获得第 $j$ 个桶的结果，

$B_j = \sumi Q{ij}$

我们最终可以通过对 $m$ 个桶进行加法来获得最终结果，

$Q = \sum_j B_j 2^{cj}$

来自 HyperPlonk 的进一步改进？

VERI-ZEXE 使用带有查找表的 PLONK，从而减少了约束并缩短了证明时间。两周前，HyperPLONK 发布，提供线性时间证明器和高度自定义门。关键变化之一是从单变量多项式（一个变量 $x$ 的多项式，例如 $(a_0+a_1x+a_2x^2+\cdots a_dx^d)$) 转换为多元线性多项式（多个变量的多项式，其中每个 $x_k$ 的次数最多为 1，例如 $a_0+a_1x_1+a_2x2+a{12}x_1x2+a{145}x_1x_4x_5$）。此更改避免了对非常大的系统（具有超过 $2^{20}$ 个约束）使用快速傅里叶变换 (FFT)，该变换具有超线性成本（粗略地说，$n$ 个点的 FFT 需要 $n \log(n)$ 运算）。初步研究表明，与原始提案的优化版本相比，这种新的 PLONK 版本对于具有超过 16000 个约束的电路表现更好。我们将在即将发布的文章中介绍这个主题。

总结

ZK 证明是许多新应用的关键，例如去中心化金融、治理等。ZEXE 协议引入了去中心化私有计算的概念，允许用户在公共账本上运行私有应用程序。最初的提案基于非通用证明系统，该系统具有高效的性能，但对于我们要运行的每个程序都需要一个新的可信设置。从那时起，证明系统（例如 Marlin 和 PLONK）和新的“SNARK 友好”密码学原语（例如对称密码和哈希函数）都进行了多次重大改进，从而提高了性能并降低了计算成本。这些更改允许功能较弱的设备充当证明者并运行更复杂的程序。

• 原文链接： blog.lambdaclass.com/dec...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～