Plinko PIR tutorial
Special thanks to Alex Hoover, Keewoo Lee and Ali for feedback and review
特别感谢 Alex Hoover、Keewoo Lee 和 Ali 的反馈和审查
One underrated form of privacy, that is not well satisfied by ZK-SNARKs , traditional versions of FHE or other commonly talked about methods, is private reads .
一种被低估的隐私形式是私人读取，ZK-SNARK、传统版本的 FHE 或其他常见的方法并不能很好地满足这种形式。
Users want to learn things from a large database, without revealing what they're reading.
用户希望从大型数据库中学习内容，而又不想透露他们正在阅读的内容。
Some use cases of this include:
一些用例包括：
There is a category of privacy protocols that are directly designed to solve this problem, called private information retrieval (PIR) .
有一类隐私协议就是专门为了解决这个问题而设计的，称为隐私信息检索（PIR）。
A server has a database \(D\) .
服务器有一个数据库 \(D\) 。
A client has an index \(i\) .
客户端有一个索引 \(i\) 。
The client sends the server a query, the server replies back with an answer that allows the client to reconstruct \(D[i]\) , all without the server learning anything about \(i\) .
客户端向服务器发送查询，服务器回复一个答案，允许客户端重建 \(D[i]\) ，而服务器无需了解任何有关 \(i\) 的信息。
In this post I will describe some basics that underlies all PIR protocols, and then describe Plinko , a protocol that efficiently achieves this.
在这篇文章中，我将描述所有 PIR 协议的一些基础知识，然后描述 Plinko，一个有效实现这一目标的协议。
To understand more complicated PIR protocols, it's best to start with "classic two-server PIR".
要了解更复杂的 PIR 协议，最好从“经典的双服务器 PIR”开始。
Classic two-server PIR assumes that a client is making queries to two servers, and it trusts that at least one of the two is honest.
经典的双服务器 PIR 假设客户端正在向两台服务器进行查询，并且它相信两台服务器中至少有一台是诚实的。
Here's how the protocol works:
该协议的工作原理如下：
The key idea is that each server receives what looks like a completely random subset of the indices.
关键思想是每个服务器接收看起来完全随机的索引子集。
There is not even a slight bias from mixing in \(i\) , because that modification is as likely to add the value as it is to remove it.
混合 \(i\) 甚至不会产生轻微的偏差，因为该修改很可能会添加该值，也可能会删除该值。
The two servers give XOR-sums of subsets that are almost identical, but differ in one place: one includes \(D[i]\) and the other doesn't.
两台服务器给出的子集的异或和几乎相同，但有一处不同：一台包含 \(D[i]\)，而另一台则不包含。
The client gets these two values, and takes the difference between the two, which gives \(D[i]\) .
客户端获取这两个值，并取两者之间的差值，得到 \(D[i]\) 。
This naturally generalizes to "cells" that are bigger than one bit; you could have each \(D[i]\) have eg.
这自然可以推广到大于一位的“单元”；你可以让每个 \(D[i]\) 有例如。
1000 bits, and the protocol is exactly the same.
1000位，协议完全一样。
There are two well-understood modifications to classic two-server PIR that solve (1).
对经典双服务器 PIR 有两个易于理解的修改来解决 (1)。
One strategy is PIR with preprocessing .
一种策略是带有预处理的 PIR。
Notice that in the protocol above, you can compute one of the two random sample sets before you even know which \(i\) you want to query for.
请注意，在上面的协议中，您甚至可以在知道要查询哪个\(i\) 之前计算两个随机样本集之一。
You generate thousands of these random queries.
您会生成数千个这样的随机查询。
You have an initial phase where you download (but do not need to store) the whole file \(D\) , and you compute the XOR sums for these random sets of indices locally.
您有一个初始阶段，您下载（但不需要存储）整个文件 \(D\) ，并在本地计算这些随机索引集的 XOR 和。
Essentially, you are acting as one of the two servers - and in this way, satisfy the 1-of-2 trust assumption all by yourself, so you do not need to trust the other server.
本质上，您充当两台服务器之一 - 通过这种方式，您自己就可以满足 1-of-2 信任假设，因此您不需要信任另一台服务器。
This approach does require a huge amount of upfront bandwidth, but you can do it ahead of time, or do it in the background and use a more inefficient form of PIR to answer any queries that you get before it finishes.
这种方法确实需要大量的前期带宽，但您可以提前执行，或者在后台执行，并使用效率较低的 PIR 形式来回答在完成之前收到的任何查询。
The other strategy is single-server PIR .
另一种策略是单服务器 PIR 。
Basically, you use some variant of homomorphic encryption (often simpler than full-on FHE) to encrypt your query, in such a way that the server can compute on your encrypted query to give you an encrypted answer.
基本上，您使用某种同态加密的变体（通常比完整的 FHE 更简单）来加密您的查询，这样服务器就可以对您的加密查询进行计算，从而为您提供加密的答案。
This has high computational overhead on the server side, and so is not yet feasible for very large datasets.
这在服务器端具有很高的计算开销，因此对于非常大的数据集尚不可行。
This strategy can be combined with PIR with preprocessing, so you can theoretically avoid the initial download by doing that procedure homomorphically encrypted on the server side.
该策略可以与具有预处理功能的 PIR 相结合，因此理论上可以通过在服务器端执行同态加密的过程来避免初始下载。
Plinko solves (2) and (3) - or at least, it decreases both communication overhead and server-side compute overhead from \(O(N)\) to \(O(\sqrt{N})\) where \(N\) is the number of cells.
Plinko 解决了 (2) 和 (3) - 或者至少，它将通信开销和服务器端计算开销从 \(O(N)\) 减少到 \(O(\sqrt{N})\)，其中 \(N\) 是单元格数量。
It uses the preprocessing strategy to remove the trust assumption.
它使用预处理策略来消除信任假设。
Theoretically, you can do the preprocessing in FHE; it is currently an open problem to do this efficiently enough.
理论上可以在FHE中进行预处理；目前，如何足够有效地做到这一点是一个悬而未决的问题。
There is also an easy way for the client to update hints if the data set changes.
如果数据集发生变化，客户端还有一种简单的方法来更新提示。
Now, let's get into the protocol!
现在，让我们进入协议！
Treat the database as being a square, with \(\sqrt{N}\) rows and \(\sqrt{N}\) columns:
将数据库视为一个正方形，具有 \(\sqrt{N}\) 行和 \(\sqrt{N}\) 列：
The client generates a random master seed \(S\) .
客户端生成一个随机主种子 \(S\) 。
For each row \(i\) , the client uses the master seed to generate a row seed \(S_i\) .
对于每一行 \(i\) ，客户端使用主种子生成行种子 \(S_i\) 。
The client generates roughly \(128 * \sqrt{N}\) hints .
客户端生成大约 \(128 * \sqrt{N}\) 提示。
Each hint is generated as follows:
每个提示的生成方式如下：
The "hash" that is used to compute the \(c_i\) values could be a regular hash, but that leads to (tolerable but significant) inefficiency during the query phase.
用于计算 \(c_i\) 值的“哈希”可以是常规哈希，但这会导致查询阶段的效率低下（可以容忍但很严重）。
So instead, Plinko prefers special type of hash called an "invertible PRF".
因此，Plinko 更喜欢称为“可逆 PRF”的特殊类型的哈希。
The core property that it achieves is that given \(S_i\) and \(c_i\) , you can easily recover all \(j\) values that lead to that \(c_i\) .
它实现的核心属性是，给定 \(S_i\) 和 \(c_i\) ，您可以轻松恢复导致该 \(c_i\) 的所有 \(j\) 值。
In practical terms, this means that for any cell \((r_i, c_i)\) , you can easily find all hints that "include" that cell.
实际上，这意味着对于任何单元格 \((r_i, c_i)\) ，您可以轻松找到“包含”该单元格的所有提示。
Additionally, the setup phase generates some "backup hints".
此外，设置阶段会生成一些“备份提示”。
These are constructed like regular hints, except for each index \(j\) , you choose \(\frac{\sqrt{N}}{2}\) rows, and compute a pair of hints: one over the chosen subset of rows, and the other for its complement (ie.
它们的构造与常规提示类似，除了每个索引 \(j\) 之外，您选择 \(\frac{\sqrt{N}}{2}\) 行，并计算一对提示：一个针对所选的行子集，另一个针对其补集（即。
the \(\frac{\sqrt{N}}{2}\) rows that were not chosen):
未选择的 \(\frac{\sqrt{N}}{2}\) 行）：
This whole process can be done "streaming", without requiring the client to store any data at any point in time other than the hints themselves.
整个过程可以“流式”完成，除了提示本身之外，不需要客户端在任何时间点存储任何数据。
In total, the client needs to download the whole data set and store data equal to roughly \(64 * \sqrt{N}\) cells, plus \(\sqrt{N}\) cells per backup hint (the client will need one backup hint for each query that the client will make).
总的来说，客户端需要下载整个数据集并存储大约相当于 \(64 * \sqrt{N}\) 个单元格的数据，加上每个备份提示的 \(\sqrt{N}\) 个单元格（客户端对于客户端将进行的每个查询都需要一个备份提示）。
If desired, the process can also be done in FHE, which means the client would only need to download the hints, but the server would need to do FHE work over the whole dataset; this is of course expensive, and optimizing it is an ongoing problem.
如果需要，该过程也可以在 FHE 中完成，这意味着客户端只需要下载提示，但服务器需要对整个数据集进行 FHE 工作；这当然是昂贵的，并且优化它是一个持续存在的问题。
Suppose you are interested in a specific coordinate \((x, y)\) .
假设您对特定坐标 \((x, y)\) 感兴趣。
First, you discover a hint index \(j\) that generates a hint that contains \((x, y)\) .
首先，您发现一个提示索引 \(j\) ，它生成包含 \((x, y)\) 的提示。
This is where the "invertible PRF" mechanism helps: it lets you immediately run the function in reverse knowing \(S_x\) and \(y\) to compute all \(j\) 's such that \(H(S_x, j) = y\) .
这就是“可逆 PRF”机制发挥作用的地方：它可以让您在知道 \(S_x\) 和 \(y\) 的情况下立即反向运行函数来计算所有 \(j\) ，使得 \(H(S_x, j) = y\) 。
However, if you want to avoid this complexity, you could just set \(H(S_x, j) = sha256(S_x, \lfloor \frac{j}{16} \rfloor)[j \% 16: (j \% 16) + 2]\) and then compute on average \(\frac{\sqrt{N}}{16}\) hashes every time.
但是，如果你想避免这种复杂性，你可以设置 \(H(S_x, j) = sha256(S_x, \lfloor \frac{j}{16} \rfloor)[j \% 16: (j \% 16) + 2]\) ，然后每次计算平均 \(\frac{\sqrt{N}}{16}\) 哈希值。
Then, you determine the \(\frac{\sqrt{N}}{2} + 1\) rows that the hint generates.
然后，您确定提示生成的 \(\frac{\sqrt{N}}{2} + 1\) 行。
You take out row \(x\) .
您取出行 \(x\) 。
You then send the server a message that contains:
然后，您向服务器发送一条消息，其中包含：
You send these in a random order, so the server does not know which is which.
您以随机顺序发送这些内容，因此服务器不知道哪个是哪个。
As far as the server can tell, you just sent it a random set of points, one per row, with the rows split in half in an arbitrary way.
据服务器所知，您只是向它发送了一组随机点，每行一个，并且行以任意方式分成两半。
The server XORs both sets of cells, and replies with both outputs.
服务器对两组单元进行异或，并用两个输出进行回复。
The client then locally takes its hint, XORs it with the (non-junk) value returned by the server, and it has its answer.
然后，客户端在本地获取其提示，将其与服务器返回的（非垃圾）值进行异或，然后得到答案。
The server does a computation based on \(\sqrt{N}\) cells, and returns that data to the client.
服务器基于 \(\sqrt{N}\) 个单元格进行计算，并将该数据返回给客户端。
The server knows nothing about which cell the client wants (provided the client does not reuse hints), because the client gave the server every point in the set in its hint except the point it actually wants.
服务器不知道客户端想要哪个单元格（假设客户端不重复使用提示），因为客户端在其提示中向服务器提供了集合中的每个点，除了它实际想要的点。
And without knowing the hash that generated these subsets, to the server, all the row and column choices look completely random.
在不知道生成这些子集的哈希的情况下，对于服务器来说，所有行和列选择看起来都是完全随机的。
To avoid using a hint twice (and thus leaking data), when the client makes a query, it dumps the hint that it used, and "promotes" a backup hint into being a regular hint.
为了避免两次使用提示（从而泄漏数据），当客户端进行查询时，它会转储它使用的提示，并将备份提示“提升”为常规提示。
Remember that each "backup hint" is a pair of hints, one that is based on a random subset of the rows, and the other based on its complement.
请记住，每个“备份提示”都是一对提示，一个基于行的随机子集，另一个基于其补集。
The algorithm is simple:
算法很简单：
Now, you have a set of \(\frac{\sqrt{N}}{2} + 1\) rows with an XOR of one randomly-chosen column from each row: exactly the same format as a regular hint.
现在，您有一组 \(\frac{\sqrt{N}}{2} + 1\) 行，其中对每行中随机选择的一个列进行异或：与常规提示的格式完全相同。
Suppose a value in the data updates.
假设数据更新中有一个值。
Then, you can find all hints that contain that value, and simply do a direct update: mix in the XOR of the old value and the new value.
然后，您可以找到包含该值的所有提示，并简单地进行直接更新：混合旧值和新值的 XOR。
In asymptotic terms, everything in Plinko is \(O(\sqrt{N})\) : the size of the hints that the client needs to store, the data transmitted per query ( technically that's \(O(\sqrt{N} * log(N))\) ), and the server-side compute costs.
用渐近术语来说，Plinko 中的所有内容都是 \(O(\sqrt{N})\) ：客户端需要存储的提示大小、每个查询传输的数据（技术上是 \(O(\sqrt{N} * log(N))\) ）以及服务器端计算成本。
But it helps to put this all into the context of a real-world workload.
但将这一切放入现实世界工作负载的背景中会有所帮助。
So let's use the real-world workload that I am the most familiar with: Ethereum.
那么让我们使用我最熟悉的现实世界工作负载：以太坊。
Suppose that you are querying a dataset with 10 billion values, each of which are 32 bytes.
假设您正在查询包含 100 亿个值的数据集，每个值都是 32 字节。
This is a pretty good description of the Ethereum state tree, in a couple of years when it gets significantly bigger due to scale.
这是对以太坊状态树的一个很好的描述，几年后它会因为规模而变得更大。
We use cuckoo hashing to convert a key-value store into a "flat" lookup table of the type that Plinko handles.
我们使用布谷鸟散列将键值存储转换为 Plinko 处理类型的“平面”查找表。
To include Merkle branches, one simple way (though not the optimal way) is to treat them separately as queries into smaller databases; if it's a binary tree , then the first level is full-sized, the second level is half-sized, the third level is quarter-sized, etc; because PIR costs are all proportional to sqrt, this means that our total costs will all be multiplied by \(1 + 1 + \frac{1}{\sqrt{2}} + \frac{1}{2} + \frac{1}{2\sqrt{2}} + ...
要包含 Merkle 分支，一种简单的方法（尽管不是最佳方法）是将它们单独视为对较小数据库的查询；如果是二叉树，则第一层是全尺寸，第二层是半尺寸，第三层是四分之一尺寸，依此类推；因为 PIR 成本都与 sqrt 成正比，这意味着我们的总成本将全部乘以 \(1 + 1 + \frac{1}{\sqrt{2}} + \frac{1}{2} + \frac{1}{2\sqrt{2}} + ...
= 3 + \sqrt{2} \approx 4.414\) .
= 3 + \sqrt{2} \约 4.414\) 。
Ethereum's state tree is (for now) a less-efficient hexary tree , but you can ZK-prove equivalence to a binary tree to get the efficiencies of a binary tree today.
以太坊的状态树（目前）是效率较低的六叉树，但您可以通过 ZK 证明与二叉树的等价性，以获得当今二叉树的效率。
But first, let's provide raw costs without the Merkle branches.
但首先，让我们提供没有 Merkle 分支的原始成本。
This implies a 100000×100000 grid, where each cell is 32 bytes (256 bits).
这意味着 100000×100000 网格，其中每个单元为 32 字节（256 位）。
The client would need to store 100000×128 hints, which is 100000 × 128 × 32 bytes ~= 390 MB , plus some extra backup hints.
客户端需要存储 100000×128 个提示，即 100000 × 128 × 32 字节 ~= 390 MB ，加上一些额外的备份提示。
For each query, the client would need to send the server a partitioning of the rows into two parts, and 100000 column indices.
对于每个查询，客户端需要向服务器发送将行分为两部分的分区以及 100000 个列索引。
We could be super-clever and do slightly better than this, but if we do it naively, the row partition is 100000 bits (12.2 kB) and the column indices are 100000 * ceil(log2(100000)) = 1.7m bits = 202.7 kB.
我们可以非常聪明，做得比这更好，但如果我们天真地这样做，行分区是 100000 位 (12.2 kB)，列索引是 100000 * ceil(log2(100000)) = 1.7m 位 = 202.7 kB。
These two sum up to 215 kB per query.
每个查询这两项总计为 215 kB。
If we introduce Merkle branches, the hint costs blow up to about 1.68 GB .
如果我们引入 Merkle 分支，提示成本将飙升至约 1.68 GB 。
With clever work, we can actually avoid the per-query communication costs increasing by 4.414x, because we can adjust the PIR in such a way that we use the same (or rather, analogous) query indices for the datasets representing different levels of the tree.
通过巧妙的工作，我们实际上可以避免每个查询的通信成本增加 4.414 倍，因为我们可以通过对代表树的不同级别的数据集使用相同（或者更确切地说，类似）的查询索引的方式来调整 PIR。
Server-side costs involve reading and XOR'ing 100000 cells, or 3.05MB per query; the XOR is negligible, but the read load is significant.
服务器端成本涉及读取和异或 100000 个单元，或每次查询 3.05MB； XOR 可以忽略不计，但读取负载很大。
Adding Merkle branches would blow this up to about 13.4 MB in theory, though the realistic added cost may well be negligible because clever engineering can ensure that matching values are always in the same page (memory pages are usually 4096 bytes).
理论上，添加 Merkle 分支会将其增加到约 13.4 MB，但实际增加的成本很可能可以忽略不计，因为巧妙的工程可以确保匹配值始终位于同一页面中（内存页面通常为 4096 字节）。
Our main tool to fiddle with these numbers is to make the rectangle unbalanced (have different width and height) : we can increase hint storage by 2x to reduce query size by 2x.
我们摆弄这些数字的主要工具是使矩形不平衡（具有不同的宽度和高度）：我们可以将提示存储增加 2 倍，以将查询大小减少 2 倍。
Realistically, this is a good tradeoff: storing even 10 GB of hints is not that hard, but especially if nodes are sending multiple queries every 200 milliseconds, 215 kB per query is higher than we would be comfortable with.
实际上，这是一个很好的权衡：存储甚至 10 GB 的提示也不是那么困难，但特别是如果节点每 200 毫秒发送多个查询，则每个查询 215 kB 的大小超出了我们的承受范围。
In the case of a search engine, the size of the objects would be much larger (eg.
在搜索引擎的情况下，对象的大小会大得多（例如。
10 kB per text webpage), but the number of queries may be smaller.
每个文本网页 10 kB），但查询数量可能会更少。
Hence, query complexity would be relatively low, but hint size would be large.
因此，查询复杂度相对较低，但提示大小会很大。
To compensate for this, it may make sense to make the rectangle unbalanced in the other direction .
为了补偿这一点，使矩形在另一个方向上不平衡可能是有意义的。
One already-existing alternative to Plinko is TreePIR .
Plinko 的一种现有替代方案是 TreePIR 。
TreePIR works by using a "puncturable PRF": a hash function where you can provide a key that allows evaluating it at all points except for one chosen point.
TreePIR 通过使用“可穿刺 PRF”来工作：一种哈希函数，您可以在其中提供一个密钥，允许在除一个选定点之外的所有点上对其进行评估。
This allows you to generate a representation of the query columns ("values generated from a seed \(S\) except the \(j\) 'th value") that is logarithmic-sized - much more compact than providing the whole list directly:
这允许您生成对数大小的查询列的表示（“从种子 \(S\) 生成的值，除了第 \(j\) 个值”）——比直接提供整个列表要紧凑得多：
The full approach is somewhat more clever than the above diagram.
完整的方法比上图更聪明。
The idea in this diagram reveals the excluded index 01100, violating privacy.
该图中的想法揭示了排除的索引 01100，侵犯了隐私。
TreePIR works by providing the yellow values without revealing their (horizontal) position in the tree.
TreePIR 的工作原理是提供黄色值，而不透露它们在树中的（水平）位置。
There are \(2^{log_2(\sqrt{N})} = \sqrt{N}\) possible sets of leaf values, and thus \(\sqrt{N}\) possible sets of columns, that can be generated by taking the left and right choice of position for each yellow value.
有 \(2^{log_2(\sqrt{N})} = \sqrt{N}\) 可能的叶值集，因此有 \(\sqrt{N}\) 可能的列集，可以通过为每个黄色值选择左右位置来生成。
The server has an \(O(\sqrt{N} * log(N))\) time algorithm to compute the XOR sum of chosen cells for every possible arrangement simultaneously.
服务器具有 O(\sqrt{N} * log(N))\) 时间算法来同时计算每种可能排列的所选单元格的异或和。
The client knows which of these sums corresponds to the set that it actually needs.
客户端知道这些总和中的哪一个对应于它实际需要的集合。
It uses single-server PIR to ask for it.
它使用单服务器 PIR 来请求。
This reduces communication complexity to logarithmic, at the cost of increased server work, and at the cost of removing the "invertible PRF" mechanism, forcing the client to "grind" through many possible hints until they find a matching hint.
这将通信复杂性降低到对数，但代价是增加了服务器工作量，并以删除“可逆 PRF”机制为代价，迫使客户端“磨练”许多可能的提示，直到找到匹配的提示。
There are various theoretical lower bounds for how much overhead a PIR protocol needs to have.
PIR 协议需要的开销有多种理论上的下限。
In reality, however, most of these bounds come with caveats, and so the "real" lower bounds are far fewer.
然而实际上，大多数这些界限都带有警告，因此“真正的”下限要少得多。
For example, if you have obfuscation, you can make any of these protocols require only a constant real-time communication overhead - but of course, today, such protocols are still quite far away from practicality.
例如，如果你有混淆，你可以使这些协议中的任何一个只需要恒定的实时通信开销——但当然，今天，这样的协议离实用性还很远。
The harder thing to reduce is server-side computation.
更难减少的是服务器端计算。
Because it's "just" XOR, the workload in Plinko is already not a big deal.
因为它“只是”异或，所以 Plinko 中的工作量已经不是什么大问题了。
But if we want to remove the client-side \(O(N)\) download requirement, then we need the server side to do much heavier computation.
但如果我们想消除客户端\(O(N)\)下载要求，那么我们需要服务器端进行更繁重的计算。
With Plinko, PIR is much further along than it was a decade ago, but there is still theoretically much further that these protocols could go.
有了 Plinko，PIR 比十年前进步了很多，但理论上这些协议仍然可以走得更远。