Vitalik：混淆电路（Garbled circuits）快速入门

注：原文作者是以太坊联合创始人Vitalik Buterin。

特别感谢Dankrad Feist对本文进行的审阅工作。

混淆电路（Garbled circuits）是一种非常古老，且非常简单的密码学原语。它们很可能是通用“多方计算”（MPC）的最简单形式。

以下是该方案的常规设置：

1. 假设存在两方，爱丽丝（Alice ）和鲍勃（Bob），他们想要计算一些函数 f(alice_inputs, bob_inputs) ，这需要从双方那获取输入。爱丽丝（Alice）和鲍勃（Bob）都想知道计算函数 f 的结果，但是爱丽丝（Alice）不想鲍勃（Bob）知道她的输入，而鲍勃（Bob）则不想爱丽丝（Alice）知道他的输入。理想情况下，除了 f 的输出外，他们都不会得知任何其它东西。
2. 爱丽丝（Alice ）执行特殊的过程（“混淆”-garbling）来加密评估函数f的电路（意味着一组“与”、“或”门）。她将输入（也以与加密电路兼容的方式进行加密）传递给鲍勃（Bob）。
3. 鲍勃（Bob）使用一种称为“1-of-2茫然传输（Oblivious Transfer）”的技术来学习自己输入的加密形式，而不让爱丽丝（Alice ）知道他获得了哪些输入。
4. 鲍勃（Bob）在加密数据上运行加密电路，得到答案，并将其传递给爱丽丝（Alice ）。

额外的密码学封装可用于保护该方案，以防止爱丽丝（Alice ）和鲍勃（Bob）发送错误的信息并互相给出错误的答案。为了简单起见，我们不会讨论这些问题，尽管可以说“把ZK-SNARK封装在所有东西上”是其中之一有效的解决方案（相当繁重且次优！）。

那基本方案如何运作呢？ 让我们从电路开始：

这是一个最简单的电路例子，它实际上做了一些事情：它是一个两位加法器。它以二进制形式输入两个数字，每个数字具有两位，并输出一个三位二进制数字（即总和）。

现在，让我们对电路进行加密。首先，对于每个输入，我们随机生成两个“标签”（256位数字）：一个表示输入为0，另一个表示输入为1。然后我们也对每个中间线做同样的操作，不包括输出线。注意，这些数据不是爱丽丝（Alice ）发送给鲍勃（Bob）的“混淆”的一部分；到目前为止，这只是设置。

是门的索引（它是电路中的第一个门，第二个，第三个？）。如果你知道这两个输入的标签，并且你有混淆（garbling），那么你可以学习相应输出的标签，因为你只需计算相应的哈希，并将其减去即可。

这是第一个异或门（XOR gate）的混淆（garbling）：

请注意，我们直接包括0和1（的加密形式），因为此异或门的输出直接是程序的最终输出。 现在，让我们看一下最左边的与门（AND gate）：

在这里，门的输出仅用作其他门的输入，因此我们使用标签（label）而不是位（bit）来隐藏评估器（evaluator）中的这些中间位。

爱丽丝（Alice ）将提供给鲍勃（Bob）的混淆（garbling）只是每个门第三列中的所有内容，每个门的行被重新排序（以避免显示给定的行是否对应于任何一行中的0或1）。为了帮助鲍勃（Bob）了解为每个门解密哪个值，我们将使用一个特定的顺序：对于每个门，第一行变为两个输入标签均为偶数的行，第二行第二个标签为奇数，第三行第一个标签为奇数，第四行两个标签均为奇数（我们故意选择较早的标签，以便每个门在一个输出上都具有偶数标签，而在另一个输出上具有奇数标签）。我们以相同的方式混淆电路中的每个其他门。

总之，爱丽丝（Alice ）为电路中的每个门向鲍勃（Bob）发送了四个 约256位的数字。事实证明，4远非最佳值；有关如何将与门（AND gate）的数量减少为3甚至是2，以及将异或门（ XOR gate）数量减少为零，请参见 此处 的一些优化。请注意，这些优化确实依赖于某些更改，使用XOR代替加法和减法，尽管为了安全起见还是应该这样做。

当鲍勃（Bob）收到电路时，他向爱丽丝（Alice ）索要与她的输入相对应的标签，并且他使用称为“1-of-2茫然传输”的协议来向爱丽丝（Alice ）索要与自己的输入相对应的标签，而没有向爱丽丝（Alice ）透露他的输入是什么。然后他一个接一个地通过电路中的各个门，揭露每个中间门的输出线。

假设爱丽丝（Alice ）的输入是两条左线，她给出（0，1），而鲍勃（Bob）的输入是两条右线，他给出（1，1）。这又是带有标签的电路：

1. 在一开始，鲍勃（Bob）知道标签6816, 3621, 4872, 5851；
2. 鲍勃（Bob）评估第一个门，他知道6816和4872，因此他可以提取与（1，6816，4872）对应的输出值（请参见上表）并提取第一个输出位1；
3. 鲍勃（Bob）评估第二个门，他知道6816和4872，因此他可以提取与（2，6816，4872）对应的输出值（请参见上表）并提取标签5990；
4. 鲍勃（Bob）评估第三个门（异或门），他知道他知道3621和5851，并学习7504；
5. 鲍勃（Bob）评估第四个门（或门），他知道3621和5851，并学习6638；
6. 鲍勃（Bob）评估第五个门（与门），他知道3621和5851，并学习7684；
7. 鲍勃（Bob）评估第六个门（异或门），他知道5990和7504，并学习第二个输出位0；
8. 鲍勃（Bob）评估第七个门（与门），他知道5990和6638，并且学习了8674；
9. 鲍勃（Bob）评估第八个门（或门），他知道8674和7684，并学习了第三个输出位1；

这样鲍勃（Bob）就了解了输出：101 。在二进制中，10 + 11 实际上等于101（在电路中，输入和输出位都是以从最小到最大的顺序给出，这就是为什么爱丽丝的输入10在电路中被表示为（0，1）的原因），所以它起作用了！

请注意，加法的使用在混淆电路中是毫无意义的，因为知道101的鲍勃（Bob）可以减去他自己的输入并得到101 - 11 = 10 （爱丽丝的输入），从而破坏了隐私。 但是，一般情况下，混淆电路可用于不可逆的计算，因此请勿以此方式破坏隐私（例如，人们可能会想到一种计算，其中爱丽丝的输入和鲍勃的输入，是他们对个性测验的答案，而输出是一个位，决定算法是否认为它们是兼容的；而这一位的信息不会让爱丽丝和鲍勃知道彼此的个人测验答案。

1-of-2茫然传输（oblivious transfer）

现在让我们更多地讨论1-of-2茫然传输（oblivious transfer），这是鲍勃（Bob）用来从爱丽丝（Alice ）那获取与他自己输入对应标签的技术。问题是这样的：聚焦于鲍勃（Bob）的第一个输入位（第二个输入位的算法相同），爱丽丝（Alice ）有一个对应于0（6529）的标签，和一个对应于1（4872）的标签。鲍勃（Bob）有他想要的输入位：1。鲍勃（Bob）想学习正确的标签（4872），而又不让爱丽丝（Alice ）知道他的输入位是1。平凡的解决方案（爱丽丝只向鲍勃发送6529和4872）不起作用，因为爱丽丝（Alice ）只想放弃两个输入标签中的一个，如果鲍勃（Bob）同时接收两个输入标签，则可能泄漏爱丽丝（Alice）不想放弃的数据。

下面是一个使用椭圆曲线的简单协议：

1. 爱丽丝（Alice ）生成一个随机椭圆曲线点 H ；
2. 鲍勃（Bob）生成两个点 P1 和 P2 ，要求 P1 + P2 等于 H 。鲍勃（Bob）选择 P1 或 P2 为 G * k （即他知道对应私钥的点）。请注意， P1 + P2 = H 的要求可确保鲍勃（Bob）不能生成 P1 和 P2 。这是因为如果在鲍勃（Bob）知道 k1 和 k2 的情况下，如果 P1 = G * k1 和 P2 = G * k2 ，则 H = G *（k1 + k2） ，因此这意味着鲍勃（Bob）可提取 H的 离散对数（或“对应的私钥” ”），这意味着椭圆曲线密码系统的所有部分都被破坏了；
3. 爱丽丝（Alice ）确认 P1+P2=H ，并使用一些标准公钥加密方案（例如El-Gamal）加密 P1 下的 v1 和 P2 下的 v2 。鲍勃（Bob）只能解密这两个值中的一个，因为他知道最多对应一个值 （P1，P2） 的私钥，而爱丽丝（Alice ）又不知道是哪一个。

这解决了问题，鲍勃（Bob）根据输入位的不同，学习两个线标签（6529或4872）中的一个，而爱丽丝（Alice ）却不知道鲍勃（Bob）学习了哪个标签。

应用领域

混淆电路（Garbled circuits）对于很多应用都有潜在的用途，而不仅仅是2-of-2的计算。例如，你可以使用它们进行任意复杂度的多方计算，其中任意数量的参与者提供输入，这些输入可以在恒定数量的交互中运行。产生一个混淆电路是完全并行的，你可以同时进行多个混淆门。

因此，你可以简单地进行大规模多方计算，其中许多参与者计算电路中所有门的混淆（garbling），并发布与其输入对应的标签。标签本身是随机的，因此不会透露任何关于输入的信息，但是任何人都可以执行公布的混淆电路，并在“清除”中学习输出。有关使用混淆（garbling）作为成分的MPC协议的最新示例，请参见 此处 。

多方计算不是唯一的应用环境，在这种情况下，这种将计算拆分为可并行处理部分的技术可对秘密数据进行操作，然后再进行可明确运行的顺序部分，这是有用的，而混淆电路并不是实现这一点的唯一技术。一般来说，关于随机编码的文献，包括很多更复杂的技术，这一数学分支在函数加密和模糊处理等技术中也是很有用的。