利好Aleo隐私公链！零知识证明钱包应用将来会越来越快？

Original AleoAsia AleoAsia 2023-08-29

收录于合集

Aleo作为一条隐私公链，采用了零知识证明来保护隐私，因此也就牺牲了交互速度，导致用户体验较差。（为什么Aleo链的Leo 钱包这么慢？解释其工作原理及Aleo链的特点）

作为Aleo首款专用隐私钱包LeoWallet团队已经开始在推进采用WebGPU，寄望其能提高零知识证明的速度（Aleo生态|Leo钱包可以通过GPU提高执行速度？），同时，FoxWallet也在摸索如何加快执行速度：Aleo移动端钱包FoxWallet，这么快的原因是什么？

现在，又有关于WebGPU的研究成果出来了，似乎可以有助于用户早日在Aleo这类隐私公链上进行丝滑如一般公链的交互体验啊！我们一起来看看吧！

使用 WebGPU 加速客户端 ZK

作者：Koh Wei Jie (wj@geometry.xyz)。非常感谢 Hugo Berg 和 Kobi Gurkan 的反馈和贡献

网络浏览器中的零知识证明生成速度很慢。例如，运行 Google Chrome 的 M1 Macbook Pro 需要近 40 秒才能生成具有 163k 约束的电路的 zk-SNARK 证明。大多数有用的电路都具有从几秒到几分钟的验证时间。因此，屏蔽钱包和假名身份平台等支持隐私的应用程序的用户体验比传统的集中式应用程序差。此外，此类应用程序的证明生成不应外包给第三方服务器，因为这可能会造成去匿名化甚至资金损失的可能性。这使得问题变得更加紧迫。

相比之下，在浏览器外部（例如在命令行中）生成证明要快得多。这是因为浏览器内的证明生成本质上受到浏览器资源限制的约束，但命令行二进制文件可以利用更广泛的计算资源。特别是那些能够使用 GPU、FPGA 和 ASIC 等硬件的人可以实现显着的加速。业界现有团队已经瞄准 GPU 来加速证明生成。例如，Scroll 正在构建 GPU 证明器解决方案来为其 zkEVM rollup 提供支持，而 Ingonyama 的 ICICLE 库则使用 CUDA 平台加速 Gnark 等现有证明器。

在这篇文章中，我重点关注 GPU 对客户端证明生成的贡献。WebGPU 是一种新的浏览器标准，它为寻求基于浏览器的 Web 应用程序的可访问性和 GPU 计算能力的开发人员带来了希望。我将介绍 WebGPU，概述 GPU 并行编程模型，绘制浏览器中 WebGPU 加速证明生成的路径，并讨论未来研究的领域。最后，为了展示 WebGPU 在加速客户端 ZK 方面的潜力，我展示了一个演示 Web 应用程序，该应用程序对 CPU 和 GPU 中大量 Poseidon 哈希的计算进行基准测试。

关于WebGPU

WebGPU 由 W3C 工作组自 2017 年开始开发，是一个允许浏览器应用程序访问 GPU 计算资源的 API。它有望加速客户端 ZK 证明的生成，因为许多客户端设备已经包含 GPU，而且浏览器对 WebGPU 标准的支持正在成熟。2023 年 4 月，Google 在 Chrome 和 Edge 版本 113 中提供了 WebGPU（尽管在 Linux 和 Android 上默认未启用）。截至撰写本文时，WebGPU 也可在 Firefox 和 Safari 中使用，但用户必须启用配置设置才能使其工作。

尽管 WebGPU 上的大多数工作都针对图形应用程序，但它也支持通用计算。开发人员使用类似 Rust 的 WebGPU 着色语言 (WGSL) 编写针对 GPU 的代码（也称为着色器代码），并指定应有多少个 GPU 工作组专用于该任务。结果可能会因用户可用的硬件而异，但 WebGPU API 消除了 GPU 开发中固有的许多复杂性。

通过 WebGPU 实现并行性

在 GPU 上进行开发的计算和内存模型与在 CPU 上进行编程的计算和内存模型有很大不同。与 CPU 不同，GPU 首先是并行的。给定一个输入数据缓冲区和一段着色器代码，GPU 会动态地将数据分配给其工作组并管理同步，以便并行进行计算，而不是迭代缓冲区。通过足够多的工作组和编写良好的算法来最大限度地提高工作组利用率，程序可以实现显着的加速。

作为并行运行大量计算的示例，请考虑以下 WGSL 代码片段，该代码片段对每个输入值计算 x ^ 3 + 3 65535 次（使用溢出的 32 位无符号整数）：

考虑到 1024 个工作组中的 65536 个随机输入，入门级 Nvidia Quadro P520 在 180 毫秒内完成任务，而 2019 时代的英特尔酷睿 i7 CPU（运行编译后的 Rust 代码）则需要 8000 毫秒。

请注意，着色器代码和用于分派工作组的 WebGPU API 调用均未明确或完全指定如何处理并行性。相反，WebGPU 对 GPU 核心的低级分配进行抽象，以对输入/输出缓冲区中的数据运行着色器。

考虑到上述着色器代码将在缓冲区中的所有输入上并行执行。第 14 行指示 GPU 对索引为 global_id.x 的数据运行运算函数，该数据对应于工作组各自的计算着色器网格点，并用函数的结果替换同一位置的缓冲区中的值。计算着色器网格坐标和存储缓冲区之间的关系大多由 WebGPU 和 GPU 驱动程序从开发人员中抽象出来。然而，开发人员必须确定适当的工作组大小、要分派的工作组数量，并应用 GPU 编程的最佳实践。

此时，精明的读者可能会发现 GPU 编程带有大量行话。事实上，不同的术语可能指的是同一事物，甚至是一组概念上相似的事物，具体取决于所使用的 GPU 平台。例如，使用 Nvidia CUDA API 的开发人员将使用术语“线程块”而不是“工作组”，而术语“着色器”和“内核”的含义会重叠，具体取决于它们是否在 Apple 的 Metal API、OpenCL 或 CUDA 上下文中使用。因此，WebGPU 开发人员会发现从其他平台学习概念非常有用，以便更全面地掌握 GPU 编程范例。

密码算法的 GPU 加速

通过专门的研究和工程工作，GPU 加速的客户端证明器已经触手可及。学术界和工业界现有研究的好处，特别是向 ZPrize 竞赛提交的材料，可能会延续到 WebGPU 环境中。这项工作可以按照复杂性和抽象性的升序进行组织，如下所示。

有限域运算加速

常见证明系统最基本的构建模块是素数域上的域算术。由于GPU中最大支持的无符号整数数据类型是64位（u64），这远远小于许多常用字段的阶数，例如BN254（254位）、BLS12-381（381位）的基或标量字段，或 Pasta/Vesta 曲线（255 位），必须实现大整数算术和模数缩减算法，特别是模乘法，并且理想情况下，必须进行优化以利用 GPU 并行性。具有此类 GPU 特定优化的算法包括：

· Özerk 等人，第 15 页：使用较小宽度的中间值修改 Barrett 模数缩减以减少内存使用

· Atlas、Solbert、Domb：基于 Barrett 约简的简单、GPU 友好的模乘算法

也可以考虑不一定特定于 GPU 的优化，但需要在 GPU 上进行基准测试。例如：

· Gnark/Goff：基于粗集成操作数扫描（CIOS）方法的优化蒙哥马利模乘法

· Mitscha-Baude：使用数量稍少的肢体来表示蒙哥马利乘法的场元素

MSM 的加速

多标量乘法 (MSM) 构成了 ZK 证明生成中的大部分计算工作（大约 70%）。在 GPU 中加速这些操作可能具有挑战性，因为它们的内存架构无法像 FPGA 或 ASIC 那样实现高效操作（正如张等人所说），但由于消费设备目前还没有这样的利基硬件，尽管如此，任何针对以 WebGPU 编写的 MSM 的特定于 GPU 的优化都将很有价值。此类优化包括：

· Aztec/Barretenberg：在 Pippenger 算法中添加预处理步骤，以桶顺序对点进行排序，而不是让它们随机分布，从而加快内存访问速度

· Matter Labs/Yrrid Software：不仅结合了 Pippenger 算法的优化，还结合了有限域和椭圆曲线运算，比任一团队的 ZPrize 提交的结果提高了约 10%

· cuZK：将Pippenger算法转换为一系列稀疏矩阵运算

NTT 的加速

对于像 Groth16 这样的系统，数论变换 (NTT) 占用的证明时间虽小，但仍然占很大比例。虽然一些较新的证明系统完全避开 NTT，但加速此操作可能有利于现有应用程序。然而这对于 GPU 来说可能具有挑战性。我发现的关于这个主题的最新研究来自 Özerk 等人，他们通过在全局内存上使用共享内存并根据多项式的大小使用单核或多核方法来对 NTT 算法进行优化。另一种方法是在 GPU 繁忙时在 CPU 上简单地执行 NTT，就像 O(1) Labs 的实现一样。

WebGPU、WASM 和 Javascript 的集成

一个编写良好的浏览器内证明器应该结合基于 CPU 的计算，例如 WASM 和 Web Worker，同时在需要大规模并行性的地方利用 WebGPU。此外，即使达到 GPU 限制，他们也应该妥善处理故障。这是可能的，因为 WebGPU 允许应用程序查询用户的设备限制，例如最大工作组数量和最大缓冲区大小。因此，编写良好的应用程序可以根据此信息动态地将计算作业分配给用户的 GPU，以避免设备过载并导致进程失败。

示范

为了演示 WebGPU 在加密操作方面的潜力，我编写了一个演示应用程序，用于计算 16384 个随机 BN254 标量的 Poseidon 哈希值。配备 Nvidia Quadro P520 GPU 的 Firefox Nightly 在 103 毫秒内完成了任务，而基于 CPU 的实现（使用 snarkjs WASM 代码）则花费了大约 12 倍的时间。虽然此演示使用蒙哥马利乘法的粗集成操作数扫描变体来加速字段运算，但此演示的先前迭代使用每次乘法的 Barrett 约简，并且只有一半的加速（即比 snarkjs 快 6 倍）。

该演示可以在此网页上运行，源代码可在 Github 上获取。我很感谢 Sampriti 和他的团队编写了本演示所基于的大整数和字段算术 WGSL 代码。

限制和缺点

重要的是要了解 WebGPU 并不是客户端 ZK 的万能药。它的好处尚未实现，并且它无法解决导致浏览器中证明生成缓慢的所有瓶颈，例如下载大型证明密钥所需的带宽。此外，WebGPU 性能高度依赖于用户的设备，并且移动浏览器比桌面浏览器更受资源限制。

前进的道路

WebGPU 有望加速客户端证明生成，从而增强 ZK 应用程序的用户体验。然而，还有许多研究和工程工作需要完成。除了如上所述的 ZK 证明系统中常用算法（从有限域算法到 MSM）的实现和基准测试之外，进一步的研究途径还可以是发现 GPU 加速如何补充针对客户端设备（如 Shockwave Plus）的新证明系统由 Personae 实验室提供。通过WebGPU加速全同态加密和隐私信息检索也值得探索。

作为结束语，我认为 WebGPU-for-crypto 生态系统的当前状态类似于 2018 年底浏览器内 zk-SNARK 证明生成生态系统的状态，当时发布了 circom 和 snarkjs 的早期版本。当时，工具很少，晦涩难懂的错误困扰着开发人员，而且围绕这些工具的社区也很小。然而，随着对 ZK 开发的兴趣不断增长，开源和商业计划也随之增长以支持该生态系统。例如，0xPARC 等组织帮助 zkREPL 等开发人员工具诞生，以太坊基金会的 PSE 团队构建了一系列 ZK 应用程序。所有这一切的发生不仅是因为 ZK 密码学的学习曲线陡峭，而且可能是因为它的技术和哲学吸引力。也许客户端 ZK 的 WebGPU 也会发生同样的情况。有很多事情要做：构建由 WebGPU 驱动的 ZK 应用程序和开发人员工具、执行安全研究以及从 CUDA 等其他平台转换现有的 GPU 优化。简而言之，现在是参与其中的最佳时机。

原文链接： https://geometry.xyz/notebook/accelerating-client-side-zk-with-webgpu 原文作者：Koh Wei Jie，编译：AleoAsia