Plinko PIR 教程

Plinko PIR 教程

特别感谢 Alex Hoover、Keewoo Lee 和 Ali 的反馈和审查

私有读取是一种被低估的隐私形式，ZK-SNARKs、传统版本的 FHE 或其他常被提及的方法都不能很好地满足这种需求。用户希望从大型数据库中学习东西，而不泄露他们正在阅读的内容。这包括以下用例：

• 保护隐私的维基百科（这样你就可以学习东西，甚至服务器都不知道你在读什么）
• 保护隐私的 RAG 或 LLM 搜索（这样你的本地 LLM 就可以从互联网获取数据，而不会泄露你正在查询的内容）
• 区块链数据读取（这样你就可以使用查询外部 RPC 节点的 DAPP，而节点不会知道你正在查询什么；参见 此处 的“私有读取”）

有一类隐私协议专门设计用于解决这个问题，称为 私有信息检索（PIR）。服务器有一个数据库 D。客户端有一个索引 i。客户端向服务器发送一个查询，服务器回复一个答案，允许客户端重建 D[i]，而服务器不会了解任何关于 i 的信息。在这篇文章中，我将介绍所有 PIR 协议的一些基础知识，然后介绍 Plinko，这是一个有效地实现这一目标的协议。

PIR 基础

要理解更复杂的 PIR 协议，最好从“经典双服务器 PIR”开始。经典双服务器 PIR 假设客户端正在向两台服务器发出查询，并且 信任 其中至少一台是诚实的。以下是协议的工作方式：

• 客户端想要知道 D[i]，在上面的例子中是 D[8]。
• 客户端生成 D 中索引的随机子集，平均约一半是满的（在上面的例子中，[1,5,6,10,15]）。
• 客户端将该子集发送到一个服务器，然后将一个修改后的子集发送到另一个服务器，其中 D[i] 的成员资格被翻转（即，如果它不在那里，则添加它，如果它在那里，则删除它）。
• 每个服务器计算它被要求的 D[i] 中的值的 XOR，并返回结果。
• 客户端 XOR 这两个值，它得到 D[i] 的值。

关键思想是，每个服务器接收到的看起来都是索引的完全随机的子集。甚至没有混合 i 带来的轻微偏差，因为修改添加或删除该值的可能性是一样的。这两个服务器给出几乎相同的子集的 XOR 和，但只有一个地方不同：一个包括 D[i]，另一个不包括。客户端得到这两个值，并取两者之间的差值，这给出了 D[i]。

这自然可以推广到大于一个比特的“单元格”；例如，你可以让每个 D[i] 有 1000 比特，协议是完全一样的。

这个协议有三个大的弱点：

1. 你必须信任两个服务器中的一个是诚实的。
2. 客户端的通信开销等于单元格的数量（如果单元格很大，这可以比数据的总大小小得多，但仍然很多）。
3. 服务器必须对一半的总数据进行 XOR 运算才能响应单个查询。

对经典双服务器 PIR 有两种广为人知的修改，可以解决（1）。

一种策略是 带预处理的 PIR。请注意，在上面的协议中，你甚至可以在知道你要查询哪个 i 之前，计算两个随机样本集中的一个。你生成成千上万个这样的随机查询。你有一个初始阶段，你下载（但不需要存储）整个文件 D，并且你在本地计算这些随机索引集的 XOR 和。本质上，你正在充当两个服务器中的一个——并且以这种方式，你自己满足二取一的信任假设，因此你不需要信任另一个服务器。这种方法确实需要大量的预先带宽，但你可以提前完成，或者在后台完成，并使用效率较低的 PIR 形式来回答你在完成之前收到的任何查询。

另一种策略是 单服务器 PIR。基本上，你使用某种形式的同态加密（通常比完全的 FHE 更简单）来加密你的查询，以便服务器可以在你的加密查询上进行计算，以给你一个加密的答案。这在服务器端有很高的计算开销，因此对于非常大的数据集来说，目前还不可行。这种策略可以与带预处理的 PIR 相结合，因此理论上你可以通过在服务器端对该过程进行同态加密来避免初始下载。

Plinko 解决了（2）和（3）——或者至少，它将通信开销和服务器端计算开销都从 O(N) 降低到 O(N)，其中 N 是单元格的数量。它使用预处理策略来消除信任假设。理论上，你可以在 FHE 中进行预处理；目前高效地完成这项工作是一个悬而未决的问题。

用 Plinko 的语言来说，有：

• 一个 设置阶段，客户端处理所有数据一次（但只记住少量“提示”）
• 一个 查询机制，客户端向服务器发出查询，并将答案与正确的提示相结合，以计算所需的值。

如果数据集更改，客户端也可以轻松更新提示。现在，让我们深入了解协议！

设置阶段

将数据库视为一个正方形，有 N 行和 N 列：

客户端生成一个随机主种子 S。对于每一行 i，客户端使用主种子生成一个行种子 Si。客户端生成大约 128∗N 提示。每个提示的生成方式如下：

• 随机（或者更确切地说，通过散列主种子进行伪随机）选择 N2+1 行
• 如果我们正在计算第 j 个提示，对于每一行 ri，使用一个哈希 H(Sri,j) 来生成一个随机列 ci。因此我们得到 N2+1 个 (ri,ci) 对
• 对这些对进行 XOR 运算，并保存该位

用于计算 ci 值的“哈希”可能是一个常规哈希，但这会导致查询阶段的（可以容忍但很显著的）效率低下。因此，Plinko 更喜欢一种特殊的哈希类型，称为“可逆 PRF”。它实现的核心属性是，给定 Si 和 ci，你可以轻松地恢复所有导致该 ci 的 j 值。实际上，这意味着对于任何单元格 (ri,ci)，你可以轻松地找到所有“包含”该单元格的提示。

此外，设置阶段还生成一些“备份提示”。这些提示的构造方式与常规提示类似，只是对于每个索引 j，你选择 N2 行，并计算一对提示：一个基于所选的行子集，另一个基于它的补集（即，未选择的 N2 行）：

整个过程可以“流式”完成，而不需要客户端在任何时间点存储任何数据，除了提示本身。总的来说，客户端需要下载整个数据集并存储大约等于 64\*N 个单元格的数据，加上每个备份提示 N 个单元格（客户端将需要为客户端将进行的每个查询提供一个备份提示）。

如果需要，该过程也可以在 FHE 中完成，这意味着客户端只需要下载提示，但服务器需要对整个数据集进行 FHE 工作；这当然很昂贵，优化它是一个持续存在的问题。

查询阶段

假设你对特定的坐标 (x,y) 感兴趣。首先，你发现一个提示索引 j，该索引生成一个包含 (x,y) 的提示。这就是“可逆 PRF”机制发挥作用的地方：它让你立即反向运行该函数，了解 Sx 和 y 以计算所有 H(Sx,j)=y 的 j。但是，如果你想避免这种复杂性，你可以只设置 H(Sx,j)=sha256(Sx,⌊j16⌋)[j%16:(j%16)+2]，然后每次平均计算 N16 个哈希。

然后，你确定该提示生成的 N2+1 行。你取出第 x 行。然后，你向服务器发送一条消息，其中包含：

你以随机顺序发送这些点集，因此服务器不知道哪个是哪个。就服务器而言，你只是向它发送了一组随机点，每行一个点，行以任意方式分成两半。服务器对两个集合的单元格进行 XOR 运算，并回复两个输出。

然后，客户端在本地获取其提示，将其与服务器返回的（非垃圾）值进行 XOR 运算，它就得到了答案。

服务器根据 N 个单元格进行计算，并将该数据返回给客户端。服务器不知道客户端想要哪个单元格（前提是客户端不重复使用提示），因为客户端向服务器提供了提示中集合中的每个点，除了它实际想要的点。而且，在不知道生成这些子集的哈希的情况下，对于服务器来说，所有行和列的选择看起来都是完全随机的。

备份查询

为了避免两次使用同一个提示（从而泄露数据），当客户端发出查询时，它会转储它使用的提示，并将备份提示“提升”为常规提示。请记住，每个“备份提示”是一对提示，一个基于行的一个随机子集，另一个基于它的补集。该算法很简单：

• 获取从不包含你查询的行的行子集生成的提示值
• 将你查询的值进行 XOR 运算

现在，你有一个包含 N2+1 行的集合，其中每行都有一个随机选择的列的 XOR：与常规提示的格式完全相同。

更新数据集

假设数据中的一个值更新了。然后，你可以找到包含该值的所有提示，并简单地进行直接更新：混合旧值和新值的 XOR。

这就是整个协议！

具体效率

在渐近项中，Plinko 中的一切都是 O(N)：客户端需要存储的提示的大小、每个查询传输的数据（技术上是 O(N∗log(N))），以及服务器端的计算成本。但将这一切放在真实世界的工作负载的背景下是有帮助的。因此，让我们使用我最熟悉的真实世界的工作负载：以太坊。

假设你正在查询一个包含 100 亿个值的数据集，每个值都是 32 字节。这很好地描述了以太坊状态树，在几年后，由于扩展，它会变得更大。我们使用 杜鹃散列 将键值存储转换为 Plinko 处理的那种“扁平”查找表。

要包含 Merkle 分支，一种简单的方法（虽然不是最优的方法）是将它们作为对较小数据库的查询单独处理；如果它是一棵 二叉树，那么第一层是全尺寸的，第二层是半尺寸的，第三层是四分之一尺寸的，等等；因为 PIR 成本都与 sqrt 成正比，这意味着我们的总成本将乘以 1+1+12+12+122+...=3+2≈4.414。以太坊的状态树（目前）是一个 效率较低的 十六叉 树，但你可以 ZK 证明与二叉树的等价性，以获得今天二叉树的效率。

但首先，让我们提供没有 Merkle 分支的原始成本。这意味着一个 100000×100000 的网格，其中每个单元格是 32 字节（256 位）。客户端需要存储 100000×128 个提示，即 100000 × 128 × 32 字节 ~= 390 MB，加上一些额外的备份提示。

对于每个查询，客户端需要向服务器发送行的两个部分的切分，以及 100000 个列索引。我们可以非常聪明地做得比这稍微好一些，但如果我们天真地做，行的切分是 100000 位（12.2 kB），列索引是 100000 * ceil(log2(100000)) = 1.7m 位 = 202.7 kB。这两者加起来是每个查询 215 kB。

如果我们引入 Merkle 分支，提示成本会飙升至约 1.68 GB。通过巧妙的工作，我们实际上可以避免每次查询的通信成本增加 4.414 倍，因为我们可以调整 PIR，以便我们对代表树的不同级别的数据集使用相同（或更确切地说，类似的）查询索引。

服务器端成本包括读取和 XOR 100000 个单元格，或每个查询 3.05MB；XOR 是可以忽略不计的，但读取负载很大。添加 Merkle 分支理论上会使这个值增加到约 13.4 MB，但实际的额外成本可能可以忽略不计，因为巧妙的工程可以确保匹配的值始终在同一页中（内存页通常为 4096 字节）。

我们用于调整这些数字的主要工具是使矩形不平衡（具有不同的宽度和高度）：我们可以将提示存储增加 2 倍以将查询大小减少 2 倍。实际上，这是一个很好的权衡：存储甚至 10 GB 的提示并不难，但特别是如果节点每 200 毫秒发送多个查询，则每个查询 215 kB 高于我们感到舒适的值。

在搜索引擎的情况下，对象的大小会大得多（例如，每个文本网页 10 kB），但查询的数量可能会更少。因此，查询复杂性会相对较低，但提示大小会很大。为了补偿这一点，使矩形 朝另一个方向 不平衡可能是有意义的。

超越 Plinko：与替代方案的比较

Plinko 的一个已经存在的替代方案是 TreePIR。TreePIR 的工作原理是使用“可穿刺 PRF”：一个哈希函数，你可以提供一个密钥，该密钥允许在所有点评估它，除了一个选定的点。这允许你生成查询列的表示（“从种子 S 生成的值，除了第 j 个值”），它是对数大小的——比直接提供整个列表紧凑得多：

完整的方法比上面的图表要聪明一些。此图中的想法揭示了排除的索引 01100，从而侵犯了隐私。TreePIR 的工作原理是提供黄色值，而不 揭示它们在树中的（水平）位置。通过为每个黄色值选择左侧和右侧的位置，可以生成 2log2(N)=N 组可能的叶子值，因此可以生成 N 组可能的列。服务器有一个 O(N∗log(N)) 时间算法，可同时计算每个可能排列的选定单元格的 XOR 和。客户端知道这些和中的哪一个对应于它实际需要的集合。它使用单服务器 PIR 来请求它。

这会将通信复杂性降低到对数级别，但代价是增加了服务器工作量，并消除了“可逆 PRF”机制，迫使客户端“研磨”许多可能的提示，直到它们找到匹配的提示。

对于 PIR 协议需要多少开销，有各种 理论 下限 界限。然而，实际上，这些界限中的大多数都带有警告，因此“真实”的下限要少得多。例如，如果你进行混淆，你可以使这些协议中的任何一个只需要恒定的实时通信开销——但当然，今天，这样的协议离实用还很远。更难减少的是服务器端计算。因为这“只是” XOR，所以 Plinko 中的工作负载已经没什么大不了的了。但是，如果我们想消除客户端 O(N) 的下载要求，那么我们需要服务器端进行更繁重的计算。

有了 Plinko，PIR 比十年前的进展要大得多，但从理论上讲，这些协议还有更大的发展空间。

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