RISC Zero 上的《Where's Waldo》

返回

Where’s Waldo 是零知识证明的一个 常用类比。 特别是，如果你想证明你知道 Waldo 在哪儿，而不泄露他的位置，你可以：

1. 让你的朋友，验证者，在一张大海报上打印一个 Where’s Waldo 谜题。

2. 拿着海报，转过身，从图片上剪下 Waldo。处理掉剩下的部分。

3. 把剪下来的 Waldo 交给你的朋友，他们会确认这确实是 Waldo。

这 有点 像一个零知识证明（密码学成分较少，手工成分较多），但为什么不实现一个真正的零知识证明来证明你知道 Waldo 在哪儿呢？

这个例子实现了一个 RISC Zero 程序，允许证明者说服验证者，他们知道 Waldo 在一个公开的 Where’s Waldo 谜题中的位置，而不泄露 Waldo 的坐标。

为了更好地理解，请浏览 源代码 并自己运行这个例子。

概述

这个实现 Where’s Waldo 证明的例子旨在帮助你理解在使用 RISC Zero 创建更高级程序时的一些有用技术。

特别是，它应该帮助你理解：

• Merkleizing 大量数据，使 guest 可以验证地访问其中的小部分。

• 在 guest 中使用外部库，避免重复发明轮子。

本教程将 不 包括：

• 如何基于 starter template 创建项目（参见 Hello World 教程）

• 项目结构和关于构建系统的信息（参见 理解 RISC Zero zkVM Starter Template）

• RISC Zero zkVM 背后的密码学理论（参见我们的 证明系统解释器和参考资料）

• RISC Zero zkVM 的内部组件（参见我们的 zkVM 概述 文章）

• 使用多个 RISC Zero zkVM guest 方法的程序的设计考虑（参见我们的 投票机示例）

实现 Where’s Waldo

这个例子的方法类似于类比。它获取完整的 Where's Waldo 谜题图片，并“剪切”出 Waldo。

这个剪切操作发生在 zkVM guest 中，它保持输入，特别是 Waldo 的坐标，私有，同时允许验证者确认计算是正确完成的。在这种情况下，guest 的 journal 包含对 Where’s Waldo 谜题图像和剪切出的 Waldo 图像的承诺。

一旦验证者检查了 receipt 和 journal 中的源图像承诺，并查看了剪切出的图像以验证它确实是 Waldo，他们就可以确信 Prover 知道 Waldo 在谜题中的位置。

这个过程的关键是验证者检查 Prover 是否没有从验证者期望之外的其他源图像中剪切 Waldo（例如，他们是否没有去从另一个谜题中剪切 Waldo，因为他们实际上不知道 Waldo 在验证者给他们的谜题中的位置）。这是实现可验证程序时的一个常见问题，而这正是源图像承诺在这个例子中处理的问题。

现在让我们讨论一种解决这个问题的策略，特别是对于像图像这样的大型数据，Merkleization。

Merkleization

在最简单的方法中，guest 程序可以通过简单地哈希内存中的整个 Where’s Waldo 图像，并将哈希值用作承诺来创建一个承诺。不幸的是，哈希整个图像（我们预计图像会相当大）在 guest 中成本太高。那么 guest 如何在不给 host 提供不一致数据的机会（例如，交换 Where’s Waldo 谜题）的情况下访问它需要的数据呢？

因为我们只需要访问图像中相对较小的部分来生成 cutout，一个可行的方法是将图像分割成一个由小图像块组成的向量，并使用 Merkle tree 对这个向量进行承诺。根据需要，zkVM guest 然后可以向 host 请求图像块，并且 host 可以随每个块提供一个 Merkle 路径，证明该块是承诺图像的一部分。这使 guest 可以访问它需要的数据，同时确保所有数据都是承诺图像的一部分。

Merkle tree 是 向量承诺 的一个例子。给定一个 Merkle 根，它只是一个 SHA-256 摘要，guest 具有来自 prover 的承诺，将其绑定到完整的数据向量。特别是，guest 然后可以向 host 发送对完整向量中特定元素的请求，并且 host 将使用数据 和 Merkle 路径进行响应。有了这个 Merkle 路径（这是一个通向根的短哈希链），guest 可以验证数据来自承诺的向量。这很棒，因为它意味着 host 可以承诺非常大的数据向量，数量级为千兆字节甚至太字节，并且 guest 可以按需访问它的小部分，而无需读取整个内容。这个技巧，即让 prover 承诺大量数据，然后让 verifier 读取一小部分，实际上是 RISC Zero 零知识证明的核心。

在 Where's Waldo 示例中，我们想要 Merkleize 的数据是源 Where's Waldo 谜题图像。为了将其转换为向量，我们将图像分割成块，并给每个块一个一维索引。例如，一个分割成四个块的图像可以编号为 0 作为左上象限，1 作为右上象限，2 作为左下象限，3 作为右下象限。然后，这个块向量被哈希成一棵 Merkle 树，并且 guest 被赋予根。

当 verifier 想要检查 receipt 时，他们首先重复与 prover 相同的 Merkleization 过程，从源图像开始。如果他们从相同的图像开始，他们将得到相同的根。然后，他们可以将这个根与 journal 中的承诺进行比较。如果相等，他们就可以确信 prover 使用与 verifier 期望的相同的图像运行了 guest。

在 waldo_core::merkle 模块中，实现了 merkle_light crate 的一个包装器，支持使用 SHA-256 guest 电路，并提供了一个 VectorOracle 抽象。在 waldo_core::image 模块中，实现了一个用于图像的特定 MerkleTree 类型，以及一个可以在 guest 中用于图像操作的 ImageOracle 类型。这些模块实现了上面描述的想法。

类似的 Merkle 树抽象可以用于，例如，确保一个 secret word 是字典的一部分，一个支付目的地不在禁止地址列表中，或者一个用户在授权用户集合中。

图像处理

为了处理图像并剪切 Waldo，特别是为了裁剪和应用遮罩，此示例利用了流行的 image crate。这是通过在 ImageOracle 上实现 image::GenericImageView 来实现的。有了这个 trait，image crate 中提供的许多图像操作，以及 其他 提供的操作，都可以在 guest 中对 ImageOracle 使用。类似的方法可以用于生成可证明的模糊、图像缩小等等。

RISC Zero 最强大的一个方面是能够使用你最喜欢的库，并避免重复发明轮子。

参与进来

正如当前惊人的开源应用程序生态系统是由惊人的开源库驱动的一样，你编写的 zkVM 程序也将如此。如果你尝试导入一个库，但由于某种原因无法工作，如果你通过在 GitHub 上提交一个 issue 来告诉我们，我们将非常感激。

运行此示例

你可以在 GitHub 上的 risc0/examples 文件夹 中找到此示例（和许多其他示例）的源代码和构建说明。自己运行它，并将其用作创建你自己的项目的起点！

注意：此示例是内存密集型的；我们建议使用至少 64GB 内存的机器。如果你遇到问题，请提交一个 GitHub issue 或在 Discord 上寻求帮助。

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