基于 2-of-2 多方安全计算的 MACI 匿名化方案

Bryant Yu, Eric Zhang

感谢 Felix Cai 对 MACI 和隐私投票中多个问题的讨论。

这篇文章将展示基于 2-of-2 MPC 技术的 MACI 匿名化方案的具体实现。本文核心内容主要分为三个部分：从任意算法到逻辑电路的实现；从逻辑电路到混淆电路的实现；利用不经意传输实现多方安全计算。最后，我们总结基于多方安全计算的匿名化方案。

算法

在 MACI 系统中，操作员 Operator（记为 ）管理着一个数组，这个数组记为 deactivate[]，其元素个数与 registry 数组中的元素个数相同。数组中每个位置的编号代表了 key 值（用户的编号），而每个位置存储着对应的公钥。为了更好地理解 deactivate[] 数组，可参考如下例子：在 deactivate[] 数组中，假设 registry 中的用户 （deactivate[] 数组中的第一个元素）发起了 deactivate key 操作，操作员 收到该操作请求后，如果操作的合法性被 承认， 在 deactivate[] 数组中的第一个位置填入 registry 数组中第一个位置所包含的 value 值（用户 的公钥）。另外，假设用户 没有发起 deactivate key 操作，那么 deactivate[] 数组中的第二个元素的值为 0。这样一来, deactivate[] 数组的元素个数和 registry 数组中的元素个数相同就可以理解了。

现在，为了实现 MACI 系统对管理员的匿名性，需要设计一个 2-of-2 的 MPC 方案来实现以下两个性质:

  1. 假设拥有 的用户 想将 更改为 ，他需要实现让操作员（记为 ）不知道更新的 是替换的 。
  2. 拥有 的用户（称为 ）不能知道 deactivate[] 数组中的除了 外的其他任何元素。

先暂且不考虑这两个要实现的目标。先考虑更换密钥的操作: 发起更换 deactivate[] 数组中属于 的公钥的请求， 验证 的请求是否合法，如果合法，则执行更换公钥操作；否则，拒绝请求。

因此， 需要将即将被更换的公钥 和新的公钥 同时发送给 ， 首先查看在 deactivate[] 数组中，是否有元素 ，如果有，就将 换成 ；否则，拒绝 的请求。

根据上述逻辑，我们先设计一份伪代码来实现这个操作，如下:

用户 将 和 发送给 ， 将 与 deactivate[] 数组中的值进行比较，得出输出（，或 ），也就是说，如果 确实存在于 deactivate[] 数组中，则执行公钥更换操作；否则就不执行。

现在，假设 管理的数组 deactivate[]：，我们可以写出伪代码和其 Rust 实现:

function findElement(array, PK_1, PK_1′) {
  for (let i = 1; i < array.length; i++) {
    if (array[i] === PK_1) {
      return PK_1′;
    }
  }
  return false;
}
fn find_element(array: &[i32], a: i32, b: i32) -> bool {
  let mut result = false;
  for i in 1..array.len() {
      result = result || (array[i] == a && b == a);
  }
  result
}

至此，我们已经实现了简单的在明文下的公钥更换操作。下面，我们将介绍逻辑电路的生成原理，混淆电路的生成原理，以及混淆电路输入的加密。这些步骤是实现上述 MACI 匿名性质 1 的关键，也就是让 无从得知用户 的新公钥 对应的是 deactivate[] 数组中的哪一个元素。

逻辑电路的生成原理

现在需要将上述算法转换成逻辑电路，转换的逻辑就是用逻辑运算符构造逻辑电路。一个逻辑运算符（如 ）有两个输入和一个输出。每一个输入都有 0 和 1 两种可能。一个 逻辑门的计算规则可以用下表表示:

打个比方，在上面的例子中，假设 deactivate[] 中的元素个数是二，由 保管。而输入是由用户 和 共同完成。用户 输入的是公钥 和新公钥 ， 输入的是 deactivate[] 数组中的所有元素。

为了简单起见，暂且假设一个公钥由二位二进制数来表示（实际的公钥是 256 位二进制数）。那么，现在就需要用用户 的输入公钥，对比 deactivate[] 数组中的二把公钥。因此，需要对比二次。

对于一把公钥的对比，由于假设一把公钥有二位，那么就需要两个 表示的逻辑运算符和一个 的逻辑运算符来表示。两个 的输出是一个 的输入。用户将自己的输入输入到该组逻辑运算的子电路中。

逻辑电路由逻辑门组成，逻辑电路中的逻辑门被分为 层，比如上面的电路是两层。逻辑门第一层需要用户来添加输入, 其他层是中间节点，最后是根节点。对于用户输入的逻辑门，有两个输入和一个输出。其中一个输入由用户 完成。另外一个由 完成。这三个逻辑门组成了一个子逻辑电路。这个子逻辑电路负责一次公钥的对比。

因此，两个这样的子逻辑电路再配上一个 门，就可以完成一个简单的逻辑电路了。

为了便于理解，根据上述的假设，我们可以设计这样一个例子，假设用户 的 是 10，那么用户 在上图中第一个逻辑子电路的上方的 中输入 1，在上图中下方的 中输入 0。同时，用户 在上图中第二个逻辑子电路的上方的 中也输入 1，在上图中下方的 中也输入 0（用户 对于逻辑电路的输入）。

假设 deactivate[] 数组中的第一个和第二个元素分别是 10、11。那么， 需要在上图中第一个逻辑子电路中上方的 中输入 1，在第一个逻辑子电路中下方的 中输入 0。同时， 在第二个逻辑子电路中上方的 输入 1，在第二个逻辑子电路中下方的 输入 1（ 对于逻辑电路的输入）。

这样一来，第一个 的两个输入都是 1，输出自然也是 1。同理，第二个 的两个输入都是 0，输出自然也是 1（根据表一的计算规则可知）。这样一来， 的两个输入都是 1，输出也是 1。因此，通过执行第一个逻辑子电路的对比（即对比用户 对第一个逻辑子电路的输入和 deactivate[] 数组中第一个元素对第一个逻辑子电路的输入），得到的输出结果是 1，从而可以证明，用户 A 的输入和 deactivate[] 数组中的第一个元素是完全一致的（都是 10），因此可以证明用户 的输入确实在 deactivate[] 数组中。 也不需要再去验证第二个逻辑子电路了。

逻辑电路的生成工具

在现实中，为了让一个固定的算法转换成逻辑电路，需要用到一些工具，如

  1. Verilog HDL 和 VHDL：这两种硬件描述语言被广泛用于数字电路的设计和仿真，可以使用它们来描述算法的行为，并将其转换为逻辑电路的形式。这些语言都支持从高级语言（如C、C++ 和 Java）转换为硬件描述语言的形式。使用 Verilog 或 VHDL 需要一定的硬件设计和编程经验。
  2. Xilinx Vivado Design Suite：这是一款商业软件，用于 FPGA（现场可编程门阵列）的设计和开发。它提供了一个综合工具，可以将高级语言或 RTL（寄存器传输级）代码转换为逻辑电路的形式。它支持多种编程语言，包括 C、C++、SystemC、Verilog 和 VHDL 等。
  3. Yosys：这是一款开源的 EDA（电子设计自动化）工具，用于数字电路的设计和仿真。它支持从 Verilog 和 VHDL 等硬件描述语言转换为逻辑电路的形式。它也支持从高级语言（如 C、C++ 和 Python）转换为 RTL 代码，然后转换为逻辑电路的形式。

混淆电路（Garbled Circuit）

逻辑门的加密（混淆）

回到现在的例子中，因为我们的公钥在 deactivate[] 数组中都是有序号的（序号等价于用户的编号），且数组 deactivate[] 中的最大元素个数是有上限的（用户的个数）。因此，假设最大元素个数是 ，那么，就需要构建 个子电路，然后合成一个最终的逻辑电路。

由于逻辑电路在每一个 epoch 中（一个 epoch 是区块链更新 registry 中元素的一个周期）是固定的，那么，所有用户都可以使用这个早已经生成好的，并存储在区块链中的逻辑电路。在本文例子中，由于 deactivate[] 数组中只有两个元素，因此子电路只有两个（每个子电路对应于一次公钥的对比）。

注：在一个 epoch 中，registry 数组中元素个数是固定的，因此用户的输入和数组中的元素的对比次数是固定的，因此逻辑子电路的个数是确定的，且逻辑子电路是事先可以确定好的，因此整个逻辑电路是唯一确定的。

接下来，就是将逻辑电路的每一个输入进行加密，然后将每一个逻辑门进行混淆。

先考虑加密。加密这个动作是由用户 完成的。他对每一个输入和输出的 0 和 1 用加密值表示。注意，最终的根逻辑门的输出不需要进行加密，在本案例中，就是 0（对比失败），和 1（更换新的公钥）。如图所示：

逻辑电路中的每一条引线的 0 和 1 都用加密值代替。同时，每一个逻辑电路都有一个固定的编号（这个是所有人都已知的）。例如，编号 1、2、5 就构成了一个子电路 1（比较用户的公钥和数组中的第一把公钥）。

基于此，将逻辑电路的每一个逻辑门的输入和输出（除了根逻辑门）进行加密后，在 Operator 的视角里，对于加密后的逻辑电路，他就不知道每个逻辑门的输入数字（加密值）对应的明文（是 0 还是 1）。

输入加密的方法

在混淆电路中，为每个输入值生成两个随机 key 的过程通常是使用伪随机数生成器（PRNG）来实现的。常用的生成随机 key 的实现和库有很多，例如 OpenSSL、Crypto++、libsodium 等。

输出加密的方法

基于伪随机函数 PRF 的方法是 Yao 的混淆电路中实现对输出二进制数 0 和 1 的加密的主要方法之一。具体来说，这种方法可以实现对每个逻辑门的输出进行加密，保证了数据的机密性和可靠性。

在基于 PRF 的方法中，每个逻辑门的输出都被混淆成为一组包含多个 label 的二元组，其中每个 label 都是一个随机的 01 字符串。在生成每个 label 时，可以使用伪随机函数（PRF）来实现。具体来说，可以使用一个密钥和输入值（如 0 或 1）作为 PRF 的输入，然后得到一个随机的 01 字符串作为 label。由于 PRF 是一种可以模拟真正随机数的算法，因此生成的 label 具有高度的随机性和不可预测性，保证了数据的机密性和安全性。

在混淆输出时，可以将每个逻辑门的输出表示为一个包含两个 label 的二元组（如 {label0, label1}）。其中，当输入为 0 时，使用 label0 作为输出；当输入为 1 时，使用 label1 作为输出。在将逻辑门的输出发送给下一个参与方时，只发送一个包含正确 label 的二元组，保证了数据的机密性和保密性。常见的 PRF 包括 HMAC、SHA、AES 等。

需要注意的是，对逻辑门的输出采用上述方法的目的是为了便于不经意传输（oblivious transfer）的实现。

逻辑门的计算规则可以用下表表示:

现在，我们来举个例子：下面的图是对 真值表中输出的加密。也就是对 真值表中——

  • 第一行的输出 0 加密成 ，
  • 第二行的输出 0 加密成 ，
  • 第三行的输出 0 加密成 ，
  • 第四行的输出 1 加密成 。

其中 和 就是对应于用户A的输入的二种可能的加密值， 可以是 AES 加密算法。

逻辑门的加密真值表

这里其实就可以推导不经意传输过程了。比如，用户 A 将这四个输出——

——分别发送给 ，同时 还将自己的输入的加密值假如是 发送给 。对于 而言，他并不知道 所代表的具体数值。但是 知道，他需要在 门的输入是 1。因此， 需要使用的加密密钥是 （ 不需要将这个信息告诉 ）。 利用加密密钥 对 进行加密，就能够得到 。然后将 与 发送给他的四个输出进行对比，如果他的计算结果与四个收到的加密输出中的其中一个相等，就证明他的加密是有效的。

此时对于 来说，无法通过 推断出 的输入。同理， 也不知道 是使用 对 进行的加密，因此 也无法推断 对于这个逻辑门的输入。

用户 A 输入的生成

现在，我们继续假设，用户 公钥的编号是 1，数值是 10，而数组中的二把公钥（编号分别为 0、1）的数值分别是 11, 10。也就是说用户 的公钥在数组中。

接着，用户将自己的输入，分别输入到两个子电路中（sub-circuit 1 和 2）。用户在第一个逻辑子电路（1、2、5）中进行输入。他的输入是：在编号为 1 的逻辑门输入 2674（代表二进制数 1）；在编号为 2 的逻辑门输入 8798（代表二进制数 0）。用户在第二个逻辑子电路（3、4、6）中进行输入。那么，他的输入是：在编号为 3 的逻辑门中输入 9809（代表二进制数 1）；在编号为 4 的逻辑门中输入 3453（代表二进制数 0）。

那么，用户 的输入密文 2674, 8798 和 9809, 3453 对应的明文均是二进制数 1, 0。而对于 来说，密文 2674, 8798 和 9809, 3453 对应的明文均有四种可能 0, 0、0, 1、1, 0、1, 1。如果密文的长度从二位变成 256 位，那么明文的可能性就有 。因此，对于 来说，我们可以假设用户 所给出的密文是无法被 反推出来的。

电路混淆

接下来的步骤就是将逻辑电路进行混淆。

对于一个 逻辑门，真值表如下，可对应上图来看。

表一： 逻辑门真值表

现在，这个加密版本的 逻辑门（以上图逻辑门 1 为例）如下：

表二： 逻辑门真值表的加密版本

由于上面的没有打乱顺序， 可以很轻易的推断出，2376 对应于用户的输入 0，2674 对应于用户的输入 1。

现在来打乱表二的顺序，变成表三（混淆版本的逻辑门）。

表三： 逻辑门真值表的混淆版本

这样一来，根据这个表格的排序可能性， 想通过表三还原成真正的表一，会碰到四种可能性。那么，如果在一次证明中涉及到 个逻辑门，每个逻辑门用户 都做上述操作，那么就有 种可能性。这样，通过排序任意颠倒，使得 很难推断出每个数字到底代表 0 还是 1。

第一次通信

用户将这七个逻辑门所对应的混淆之后的逻辑门表发送给 。并把自己的输入发送给 （密文 2674, 8798）和 9809, 3453）还将自己的新公钥 发送给 ，还将一个哈希值 发送给 。总结，发送——逻辑门表、自己对每个叶子逻辑门的输入、新公钥、哈希值 ——给 。需要注意的是， 有能力将七个逻辑门分为三个部分，即子电路 1、子电路 2 和根逻辑门。也知道逻辑门 1、2、5 代表第一个子电路，逻辑门 3、4、6 代表第二个子电路。逻辑门 7 代表根逻辑门。这些信息是不能随便保密的，否则就很难让 求解算法了。（假设能够保密，会进一步增强隐私性，但是计算复杂度如何控制在可以容忍的范围是重点。）

此刻，我们做一个总结, 对每个子电路的输入都传给了 。但是， 不能根据这些输入来推断出 的每个输入的明文是什么。 的输入的位数 越长， 就越难从 的密文中推断出 的明文输入。同时， 也会将 的每个逻辑门的输入加密值，也就是 和 均发送给 。

到这里为止，我们已经实现了第一个目的，通过设计混淆电路和对混淆电路输入的加密， 已经无法从 提供的信息中推断出 想替换的公钥是 。接下来，我们会通过不经意传输实现第二个目的，那就是让 也无法得知 deactivate[] 数组中除了 意外的其他任何元素。

不经意传输（Oblivious Transfer）

由于对于每个子电路， 都知道自己需要输入的是什么：比如第一个子电路， 应该输入 11（也就是说对于逻辑门 1 和逻辑门 2， 都应该输入 1）；第二个子电路， 应该输入 10（也就是说对于逻辑门 3 和逻辑门 4， 应该分别输入 1 和 0）。但是，由于 不知道每个逻辑门的与他相关的引线的两个加密数字（ 和 ）哪个代表 0 哪个代表 1（如对于逻辑门 1 的 4543 和 3213 这两个加密值， 并不知道 4543 代表 0，3213 代表 1），因此， 需要求助 获得必要的信息。

此时，我们需要回顾两个一定要保证的性质：

  1. 假设拥有 的用户 1 想将 更改为 ，他需要实现让操作员（记为 ）不知道更新的 是替换的 。
  2. 拥有 的用户（称为 ）不能知道 deactivate[] 数组中的除了 外的其他任何元素。

因此，在 向 求助的过程中， 不能透露自己的公钥 ， 不能透露在数组中的任何一把公钥信息给 。而这两个特性均可以由不经意传输（OT）来保证。

下面详述 OT 的全过程。以编号为 1 的逻辑门也就是 为例， 现在很清楚，自己要在这个逻辑门中输入 1。

这个时候， 知道 对这个逻辑门的输入是 2674（）（ 不知道 2674 是啥意思）， 需要问 ，1 的加密值到底是 4543，还是 3213。但是，为了保证第二条性质， 不能直接告诉 ，他需要 1 的加密值。同理， 也不能把 0 等于 4543 以及 1 等于 3213 告诉 ，这样的话， 可以根据这些信息，推断出 的密文所对应的明文。

  1. 生成一个哈希值 。 这个哈希值已经于之前传输给了 。 将 和 发送给 。 验证 是否成立。如果成立，则进行下一步，否则则不需要回复 。

对这一步进行说明，只要这个 值没有后门，那么，对于 来说，他想要满足公式 ，他就需要先生成一把私钥 ，然后生成公钥 ，然后再通过 得到 。也就是说， 只能拥有 和 这两把公钥中的一把私钥。否则，就意味着 能破解 DH 离散困难。即 能从公式 中求解出 。

  1. 利用密码学协议（例如 ElGamal 协议）传输消息。 选择一个随机数 。将 和 发送给 。
  2. 由于 只有 和 这两把公钥中的一把私钥，因此 可以求解出其中一个秘密。但是 并不知道 求解出了哪个秘密。这保证了特性 2。

上述三个步骤，满足了第二个性质，但是没有满足第一个性质，也就是说， 在解密了其中一个加密值后，得到了明文 1，但是，也暴露了另一个明文 0。这样一来，混淆逻辑门表就暴露了很多信息给 ，这样让 有机会破解 的秘密，从而使得性质 1 无效。

对于此的解决方案是， 将加密值进行更改。将 和 改成 和 。这样一来， 会选择解密 得到 。然后在用 对这个逻辑门的输入 结合解密的信息 得到 。此时， 还是无法推断出 1 的加密值是 4543 还是 3213。他只知道，对于编号为 1 的逻辑门，他得到的输出是 2232。但是他又不知道，2232 代表 0 还是代表 1。

从对一个逻辑门的 OT 通信可以看出整个 OT 通信的全貌，即每个逻辑门的 OT 通信都是如此，且在一次 OT 通信过程中全部完成。这样， 就能得到所有叶子逻辑门的输出，这样他就能进一步得到分支逻辑门的输出，从而最终得到根逻辑门的输出。

方案改进

上述方案中，需要且可以改进的地方有很多。例如，改进算法设计，降低算法的复杂度；改进逻辑电路的设计，让逻辑电路变得更加简单（减少门的个数，减少通信是需要传递的信息）；增加方案的安全性，加大破解方案的计算复杂度；让交互变成非交互。

算法和逻辑电路的改进

当前逻辑电路实现的比较算法的复杂度是 ，如果数组有 个元素，那么通过循环对比，最多比较 次。

但是，如果采用 Merkle Patricia Tree 的数据结构的话，对比的次数要少很多（这是因为对于 256 位的公钥来说，形成的 MPT 一定是稀疏的，因此，可能筛选二到三轮就可以筛选出想要的值）。那么，一旦算法计算复杂度下降了，逻辑电路的设计也就要简单很多。

逻辑电路的设计也有化简的可能性。

的每个输入都不同， 也是。实际上，可以进行化简。变成如下图所示。

这样的化简可以让输入变少。

增加安全性

对于安全性，就是需要让 无法通过解密 的某些值而探索出 的秘密。当前设计上逻辑门的安全性尚待提高，比如 门。

如果 想输入的是 0，那么他得到的结果必然是 0，也就是说，他天然知道输出 0 的加密值，那么他就天然知道了 1 的加密值。同时，由于 的输入已经是确定的，那么他可以根据 的输入值，和1的输出的加密值所在的行，去分析，如果 1 的输出的加密值所在的行，不包含 的输入加密值，那么 的输入就是 0，否则就是 1。

为了解决这类问题，我们需要对输出全部进行加密。比如使用该种方法：上表中的四个输出值 0、0、0、1 分别加密为——

——这样一来，输出的四个值分别对应为四个不同的密文。因此，在此环境下， 无法通过上述推断来反推出 的输入值是 0 还是 1。但是，这种方法使得输出加密值的个数从二变成了四。通信复杂度会增大。

此外，非交互式的不经意传输协议也值得研究。

总结

上述方法首先不考虑需要实现 MACI 匿名化的两个目标，即在明文下设计一个算法，让 能够正确判断是否执行用户 的请求。基于此，再将所设计的算法转化成逻辑电路。再将逻辑电路转化成混淆电路。需要注意的是，逻辑电路在每一个区块链的 epoch 中是固定的且能够从区块链中直接获取的。用户 获取该 epoch 的逻辑电路，利用相应工具将逻辑电路转化成混淆电路。同时，用户 将每一个混淆电路的输入进行加密，并将加密好的信息发送给 。此时， 由于不知道加密后的输入对应的明文是什么， 也就不知道用户 具体的输入是什么了，这样就实现了匿名化的第一个性质。

进而，使用不经意传输是实现第二个目的的方法。通过不经意传输，用户 并不知道 具体采用了哪些加密值进行进一步的输入，因此用户 无法推断出 deactivate[] 数组中的其他元素信息。同时，由于 通过不经意传输获得了足够的有效输入，因此 将这些有效输入输入到被加密的混淆电路中，最终能够得到正确的输出，该输出和明文下执行第一节的算法所得到的输出是相同的。因此， 就能够根据输出来判断是否要执行用户 的请求。

最终， 将上述所有操作利用零知识证明生成操作的 proof。区块链对 proof 进行验证，验证通过后，区块链将根据 deactivate[] 数组中的元素和 registry 数组中的元素来更新 registry 数组并结束 epoch 和开启下一个 epoch。