从零开始学 MPC - 每个人都可以学会

假设你和你的朋友都是百万富翁。你想找出谁更富有——但是不想向彼此透露各自的净资产。换句话说，你希望共同计算函数 a≥b a \geq b，而不让任一方知道另一方的数值。这是一个经典的激励问题：百万富翁问题。

MPC为此类问题提供了解决方案。MPC，或多方计算，是指多个方如何在不透露其私密输入的情况下，对私人输入进行共享计算。实际上，MPC使我们能够安全地共同计算任何函数 f(x1,x2,x3,⋯) f(x_1, x_2, x_3, \cdots) f(x1​,x2​,x3​,⋯)，其中输入的任意子集对于任一方都是私密的。（虽然有针对多个方的MPC协议，但我们在这篇文章中只讨论两个方的MPC。）

这听起来很酷，但可能吗？MPC实际上很容易实现。让我们从头开始走过一个基本的MPC实现。在几百行代码中，我们将构建执行Yao的加密电路协议↗所需的所有基本构件。

生成素数

为了进行MPC，我们需要非对称加密。最简单的非对称原语可能是RSA↗，而要进行RSA，我们需要生成一些素数。

我们可以通过猜测和检查来生成素数。然而，我们首先需要一种方法来快速检查一个数字是否为素数。有很多测试存在，但一个常见的测试是Rabin-Miller素性测试↗。这是一个基于初等数论的简单测试，且相当容易实现：

def rabin_miller(n, k=40):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

看看它是否有效。

>>> rabin_miller(101)
True
>>> rabin_miller(1234567891234567)
False
>>> rabin_miller(2**2203-1)
True

不错。这是一个概率算法，其中参数 k 决定了你的确定性。这是因为我们选择的随机基数 a 的可能性存在微小的误报率。有趣的是，如果基数可以预先预测，那么可以伪造通过该测试但实际上是合成数的伪素数。不过我们在这里并不太关心，因为我们的素数候选是随机生成的。

在实践中，像 k=40 对于RSA大小的数字来说是可以的。它的运行时间是多对数时间，因此我们可以用它进行猜测和检查。在实践中，首次筛选出任何小素数会更快，然后再运行更昂贵的全测试。

def gen_prime(n=2048):
    while True:
        p = randbits(n)
        p |= 1 # 我们只想要奇数
        for p in SMALL_PRIMES:
            if n % p == 0:
                break
        else:
            if rabin_miller(p):
                return p

RSA

现在我们有了素数，可以进行RSA↗。RSA非常简单，所以我们只需进行。

def gen_rsa_params(n=2048):
    p, q = gen_prime(n//2), gen_prime(n//2)
    N = p * q
    e = 65537
    phi = (p-1)*(q-1)
    d = pow(e, -1, phi)
    return e,d,N

Python 3.8及以上版本支持使用 pow(x, -1, N) 来进行模逆。在此之前，可以使用扩展欧几里得算法↗来进行。

像往常一样，加密为 pow(m,e,N)，解密为 pow(c,d,N)。让我们测试一下：

>>> e,d,N = gen_rsa_params(32) # 小N用于示例目的
>>> (e, N) # 公钥
(65537, 2393534501)
>>> d # 私钥
2037798773
>>> m = 123456789 # 消息
>>> c = pow(m,e,N) # 加密
>>> c # 密文
1967143072
>>> pow(c,d,N) # 解密
123456789

注意：这是教科书式RSA↗，这是不好的。在实践中，安全使用RSA并不容易，并且需要诸如填充↗、生成安全的随机数↗、避免侧信道攻击↗等内容。一般来说，你不应该自己设计加密，而是应该使用专家编写的库等等。（但这仅仅是出于学习目的，所以让我们继续。）

无知传输

现在我们有了RSA，我们可以构建无知传输↗。无知传输是MPC的构建块。实际上，它对于MPC来说是完整的，这意味着你可以仅通过无知传输构建任何MPC。

在无知传输中，有两个方：_发送者_和接收者。发送者Alice有两个消息。她希望让接收者Bob选择接收这两个消息中的一个，而不透露另一个消息。然而，接收者也不想透露他选择了哪个消息。

这里有一个更直观的类比。假设你是发送者，而我是接收者。你把两个消息放进两个看起来相同的盒子里。然后，你转过身，我拿走其中一个盒子。当你转过身时，你无法知道我选择了哪个盒子，而我也不知道另一个盒子里有什么。

要用密码学实现这一点，我们将构建1–2无知传输。数字1和2表示接收者可以选择接收两个消息中的一个。首先，让我们考虑以下协议。该协议无法工作，我们将看到原因：

0. Alice有消息 m0,m1 m_0, m_1 m0​, m1​。Bob希望接收 mb m_b m​b，其中 b 是 0 或 1。
1. Alice生成两个随机填充 x0,x1 x_0, x_1 x0​, x1​，将它们都给Bob。
2. Bob也生成一个随机填充 k k k。
3. Bob选择两个填充中的一个 x b x_b x​b​，然后用自己的填充将其盲化：x b + k x_b + k xb​+k。这返回给Alice。
4. Alice不能知道Bob选择了哪个 x，因为 k 是未知的。Alice减去她自己两个填充，得到 (x b + k) − x 0 (x_b + k) - x_0(xb​+k)−x0​和 (x b + k) − x 1 (x_b + k) - x_1(xb​+k)−x1​。这其中一个将等于 k，而另一个对Alice来说是没有意义的（例如，x 1 + k − x 0 x_1 + k - x_0 x1​+k−x0​）。
5. Alice取两个值，并用它们填充两个消息：m 0 + x b + k − x 0 m_0 + x_b + k - x_0 m0​+xb​+k−x0​和 m 1 + x b + k − x 1 m_1 + x_b + k - x_1 m1​+xb​+k−x1​。其中一个将等于 m b + k m_b + k mb​+k。这两个都发送给Bob。
6. Bob从两个消息中去掉 k。一个将去掉变为 m b m_b m​b​，Alice的其他消息对Bob来说是无用的，因为他无法在没有私钥的情况下预测其中填充的值， (x b + k − x b ′ ) d (x_b + k - x_{b'})^d (xb​+k−xb′​)d。

在这个协议中，Bob成功接收了他的消息 mb m_b m​b​，而不透露他选择了哪个。不过，有一个问题：Bob也可以算出另一个消息！由于Bob拥有x0和x1，他还可以恢复mb′ m_{b'} mb′​。这打破了发送者只会透露所选消息的期望属性。

我们可以用非对称加密来修复这个问题。问题出在第5步，当Alice在发送之前对两个消息进行填充时。问题是Bob可以计算出两个消息的填充值。我们可以通过让Alice对她的值进行某种私钥运算（即解密）来解决这个问题。一个天真的尝试可能看起来像 m 0 + (x b + k − x 0) d m_0 + (x_b + k - x_0)^d m0​+(xb​+k−x0​)d；然而，这样做不起作用。

问题在于：Bob现在如何去掉Alice的填充？没有私钥，他无法计算或预测其值。为了解决这个问题，我们将让Bob在第3步中加密他的盲化k。在这种情况下，当Alice在第5步中稍后解密填充时，这将抵消Bob的加密，留给一个填充值k，这个值是Bob知道的。对于另一个填充，它将解密为毫无意义的垃圾。现在，Bob将能够预测Alice的填充，而Alice用于另一个消息的填充仍是不可解码的。

这是完整的修订协议：

0. Alice有消息m0,m1m_0,m_1m0​,m1​。Bob希望接收mb m_b mb​，其中b是0或1。
1. Alice生成两个随机填充x0,x1x_0,x_1x0​,x1​，将它们都给Bob。
2. Bob也生成一个随机填充k k k。他用Alice的RSA公钥加密它：k e k^e ke。
3. Bob选择两个填充中一个x b x_b xb​，然后用自己的加密填充盲化它：x b + k e x_b + k^e xb​+ke。这返回给Alice。
4. 即便拥有私钥，Alice也无法知道Bob选择哪个x，因为k可以是任何东西。Alice减去她的两个填充值得到(x b + k e) − x 0 (x_b + k^e) - x_0(xb​+ke)−x0​和(x b + k e) − x 1 (x_b + k^e) - x_1(xb​+ke)−x1​。其中一个将等于k e k^e ke，另一个对Alice来说是毫无意义的（例如，x 1 + k e − x 0 x_1 + k^e - x_0 x1​+ke−x0​）。
5. Alice 解密两个填充。一个会等于k k k，另一个则是毫无意义的。Alice取这两个值并用它们对两个消息进行填充：m 0 + (x b + k e − x 0) d m_0 + (x_b + k^e - x_0)^d m0​+(xb​+ke−x0​)d和m 1 + (x b + k e − x 1) d m_1 + (x_b + k^e - x_1)^d m1​+(xb​+ke−x1​)d。一个将等于m b + k m_b + k mb​+k。这两个都发送给Bob。
6. Bob从两个消息中去掉k k k。一个将去掉变为m b m_b mb​。Alice的其他消息对Bob来说是无用的，因为他无法在没有私钥的情况下预测其填充的值(x b + k e − x b ′ ) d (x_b + k^e - x_{b'})^d (xb​+ke−xb′​)d。

在这个新版修正协议中，Bob可以安全地接收他的消息，而Alice仅透露她的两个消息中的一个！

该协议是计算上安全的。它不是信息论安全的，意味着Bob可以使用猜测和检查来尝试猜测Alice的消息。然而，考虑到消息的大小足够，这不太可能发生。有信息理论安全的OT协议（例如，基于切割和选择的协议）。

现在，让我们在Python中实现它。由于这是一个互动协议，我们将使用协程模拟Alice和Bob之间的通信，使用yield来传递消息。

def oblivious_transfer_alice(m0, m1, e, d, N, nbits=2048):
    x0, x1 = randbits(nbits), randbits(nbits)
    v = yield (e, N, x0, x1) # 将参数发送给bob，等待他的回复
    k0 = pow(v - x0, d, N)
    k1 = pow(v - x1, d, N)
    m0k = (m0 + k0) % N
    m1k = (m1 + k1) % N
    yield m0k, m1k # 回复两个填充消息

def oblivious_transfer_bob(b, nbits=2048):
    assert b in (0, 1)
    e, N, x0, x1 = yield # 从Alice接收参数
    k = randbits(nbits)
    v = ((x0, x1)[b] + pow(k, e, N)) % N
    m0k, m1k = yield v # 将(x_b + k^e)发送给Alice，等待她回复
    mb = ((m0k, m1k)[b] - k) % N
    yield mb # 接收的消息！

每个协程模拟了传输中的一个方。我们可以这样使用协程：

def oblivious_transfer(alice, bob):
    e, N, x0, x1 = next(alice)
    next(bob) # 运行Bob直到第一个yield语句
    v = bob.send((e, N, x0, x1))
    m0k, m1k = alice.send(v)
    mb = bob.send((m0k, m1k))
    return mb

现在我们有了基本的MPC构建块，我们可以使用无知传输构建任何我们想要的MPC。这正是我们接下来要与加密电路一起做的事情。

加密电路

与其从上往下解释加密电路，不如从下往上构建它。总体想法是，我们使用1–2无知传输以MPC的方式评估各个逻辑门。然后“画出剩下的猫头鹰↗”(https://i.kym-cdn.com/photos/images/original/000/572/078/d6d.jpg)。做得好，现在你有了通用的MPC。

计算单个门

首先，让我们尝试对AND门进行MPC处理。我们的门涉及三根线：输入A和B以及输出线。假设Alice知道值A，Bob知道值B，而他们想共同计算输出Out。

我们将这样做。为所有三条线的每个布尔值0和1选择一个随机的k位数字，k是一个安全参数。我们称这些为标签。每条线有两个标签。

• A0=12214430034326763207138511821778...A_{\color{blue}0} = 12214430034326763207138511821778...A0​=12214430034326763207138511821778...
• A1=15587367908968267934296553115483...A_{\color{red}1} = 15587367908968267934296553115483...A1​=15587367908968267934296553115483...
• B0=66560761019031368742675262660503...B_{\color{blue}0} = 66560761019031368742675262660503...B0​=66560761019031368742675262660503...
• B1=⋯B_{\color{red}1} = \cdotsB1​=⋯
• Out0=⋯Out_{\color{blue}0} = \cdotsOut0​=⋯
• Out1=⋯Out_{\color{red}1} = \cdotsOut1​=⋯

好的。现在让我们看一下真值表：

对于每一行，取输出线值的标签。然后，使用对称密码，用从输入线值的标签派生的密钥对标签进行加密。

此外，洗牌表格以便无法轻易判断每个逻辑输入值对应的是哪个值。

这就是所谓的加密表，用于AND门。

这就是MPC协议开始的地方。Alice将这个加密表和她的输入的标签（要么A0 A_0 A0​，要么A1 A_1 A1​）给Bob。这不会泄露任何信息给Bob，因为他不知道标签对应的是什么。对Bob而言，它们只是随机数。Bob如何评估这个加密表？

假设目前Bob也神奇地知道他的输入的标签（不论是B0 B_0 B0​还是B1 B_1 B1​）。有了这些，Bob可以遍历加密表中的四个条目，进行尝试解密↗，直到一个成功。然后他会得到一个输出标签，要么是Out0 Out_0 Out0​，要么是Out1 Out_1 Out1​。举个具体的例子，如果Alice的值是0，而Bob的值是1，他就能解密正到Out0的标签EncA0,B1(Out0) Enc_{A_0,B_1}(Out_0)EncA0​,B1​​(Out0​)。Bob将这个标签发送回Alice。

此时，Alice知道门的输出为0。记住她不知道Bob是0还是1——她只知道结果。Alice也与Bob分享这个结果。如果Bob不想盲目信任Alice的结果，他们可以整个协议再次运行，但交换角色，由Bob进行加密并发送表。

整体协议有效，除了一个问题。还记得我们假设Bob神奇地知道了他的输入标签？他应该如何向Alice询问而不透露他的输入？Alice可以发送两个标签，但这样Bob就可以利用这一点从加密表中提取信息。在我们的示例中，Bob现在可以解密两个表中的行。看到两个值相同，他可以推断出Alice的值一定是零，因为解密后的标签是同一值（如果Alice的值为1，输出将不同）。

为了解决这个问题，我们使用之前开发的无知传输！我们将让Bob通过1–2无知传输从Alice接收他的标签。Alice将让Bob选择B0 B_0 B0​和B1 B_1 B1​；Alice不知道Bob选择了哪一个，而Bob将只了解到他的输入值，而不必得知另一个。

最后一点，在这个例子中，Bob（输入为1）仍然能够推测Alice的输入为0，这是由于计算本身（AND函数）造成的，而不是协议的弱点。如果我们有一个包含更多输入位的电路，比如比较器，每个方会学到关于对方输入的信息相对较少。

单个门的实现

好的，让我们实际编码这个东西。

首先，我们需要一个对称加密原语。冒着违反文章标题的风险，我将只是导入AES↗。有更简单的原语（受欢迎的包括TEA↗和RC4↗），它们在这篇文章中同样适用，但是这些算法都较弱。（不管怎样，这不是本文的主要重点，所以我们继续。）

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import long_to_bytes, bytes_to_long

def symmetric_enc(key, x):
    cipher = AES.new(key, AES.MODE_CTR)
    ciphertext = cipher.encrypt(pad(long_to_bytes(x), 16))
    nonce = cipher.nonce
    return ciphertext, nonce

def symmetric_dec(key, ciphertext, nonce):
    cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
    x = bytes_to_long(unpad(cipher.decrypt(ciphertext), 16))
    return x

让我们试试：

>>> key = b'This is my key__'
>>> ciphertext, nonce = symmetric_enc(key, 12345)
>>> ciphertext.hex(), nonce.hex()
('db6f1eef1b94bbc04016176f8dfbdd4765b7ab61355d087d8e869c15e77b8e29', '7ad8c3a7dff064e2')
>>> symmetric_dec(key, ciphertext, nonce)
12345

好的！

为了将两个标签组合成一个密钥，我们可以使用一些哈希函数。我将使用Keccak↗。

from Crypto.Hash import SHA3_256

def combine_keys(keys, k=128):
    h = SHA3_256.new()
    for ki in keys:
        h.update(long_to_bytes(ki))
    return h.digest()

现在，这里是实际的表格加密。首先，我们需要标记真值表，同时跟踪每个标签对应的线和逻辑值。

def label_table(logic_table, output_name, input_names, k=128):
    labels = {}
    # 为每个变量生成0和1的标签
    for var in (output_name, *input_names):
        labels[var] = [randbits(k), randbits(k)]

    labeled_table = []
    # 一些itertools的事，以支持任意数量的输入线
    # 输入线的数量=逻辑表的维数
    for inp_values in itertools.product((0,1), repeat=len(input_names)):
        output_value = functools.reduce(operator.getitem, inp_values, logic_table)
        output_label = labels[output_name][output_value]
        input_labels = [labels[input_names[i]][v] for i, v in enumerate(inp_values)]
        labeled_table.append((output_label, input_labels))
    return labeled_table, labels

让我们试试。我们将k=5 k=5 k=5，以便标签较小，以作说明。

>>> labeled_table, labels = label_table([[0, 0], [0, 1]], "out", ["A", "B"], k=5)
>>> labels
{'out': [30, 27], 'A': [28, 19], 'B': [17, 30]}
>>> labeled_table
[(30, [28, 17]), # 0 = 0 & 0\
 (30, [28, 30]), # 0 = 0 & 1\
 (30, [19, 17]), # 0 = 1 & 0\
 (27, [19, 30])] # 1 = 1 & 1

好的。现在，让我们加密这个表：

def garble_table(labeled_table, k=128):
    result = []
    for row in labeled_table:
        output_label, input_labels = row
        key = combine_keys(input_labels)
        c, nonce = symmetric_enc(key, output_label)
        result.append((c, nonce))
    Crypto.Random.random.shuffle(result)
    return result

让我们测试一下：```

garble_table(labeledtable) [(b'\x02\xd6H\x01\xb2\xc9\xbe*"\x842\xb77\xf5\x81\xd2\xd2\x00\xbb\xb9\xcc\xce5\xe5\x89\x94\xc7"w\x03\x14>', b'\xdc\x0bWT\x8cM\xda\x01'),\ (b'\x9f\xd7\xe71\x922V\x92s\x90Z\x81tY\x0f5\xa2K/\xb7\x10\xf5\xbec\xd0\xff&\x05\x82\xc2\x80 ', b'\x95[\xf6Q&kZE'),\ (b'\xe7A\x8e\xf2#+\xcd\xc9\xa2\xe8\xb4p\xbdd\x93\\xf7U\xdc\x01u\xb6,JW\x18\xa2\xb5~\xe6\xd6', b'\xc1\xde\xca\xc5\xe90tu'),\ (b'\xfa\xdc\x9d\xe5&\x81\x03q\xf4\x15\x1c%\xc2t\xb0\xbf\x0b0Vk\xbdNm\xe8CT\xb3\x01\xd7\x82\xe7\x12', b'J,q)B\x88\xe9r')]\ \

\
这个混淆表看起来像一个加密的二进制块，正如预期的那样。要评估混淆表：\
\
```\
def eval_garbled_table(garbled_table, inputs):\
for row in garbled_table:\
ciphertext, nonce = row\
try:\
key = combine_keys(inputs)\
output_label = symmetric_dec(key, ciphertext, nonce)\
except ValueError: # 解密失败，填充不正确\
continue\
return output_label\
\
a, b = 1, 1\
eval_garbled_table(garbled_table, [labels['A'][a], labels['B'][b]])\
27\
labels['out'][1] # 验证这是否与 out=1 的标签匹配\
27\
\
```\
\
它工作了！接下来我们也在 `NOT` 门上试试。通过 `AND` 和 `NOT`，我们在功能上是完整的。\
\
```\
labeled_table, labels = label_table([1, 0], "out", "x", k=5)\
labels\
{'out': [23, 25], 'x': [31, 24]}\
labeled_table\
[(25, [31]), (23, [24])]\
garbled_table = garble_table(labeled_table)\
eval_garbled_table(garbled_table, [labels['x'][0]])\
25\
labels['out'][1]\
25\
\
```\
\
很好！但是，我们的对称加密有一个大问题。每隔一段时间，解密在我们的混淆表中的错误行意外地成功。由于偶然性，解密有有效填充，而我们的混淆表评估器产生了错误的结果。我们如何防止这个问题呢？\
\
##### 防止试验解密中的假阳性\
\
在某种意义上，我们的填充像是一个校验和，通过使随机解密成功的可能性不大。这里有一个例子：\
\
```\
from Crypto.Util.Padding import pad, unpad\
pad(b'test', 16)\
b'test\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'\
unpad(b'test\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c', 16)\
b'test' # <-- 成功的去填充\
unpad(b'test\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0d', 16)\
只有一个字节改变！ ^\
Traceback (most recent call last):\
File "<stdin>", line 1, in <module>\
File "python3.10/site-packages/Crypto/Util/Padding.py", line 95, in unpad\
raise ValueError("PKCS#7 padding is incorrect.")\
ValueError: PKCS#7 padding is incorrect.\
\
```\
\
这类似于一种错误检测。也许我们可以通过使用校验和来加强这一点。我们可以使用像弗莱彻校验和或 CRC-32 这样的简单校验和。不幸的是，虽然这能降低错误率，但我们仍然遇到校验和_意外_有效的情况。\
\
那么，对于 SHA-2 这样的加密哈希函数呢？这将保证消息在意外有效的情况下不会出现。因此我们只需在末尾添加一个哈希，对吗？也许，但一般来说，这种方式[非常容易↗](https://moxie.org/2011/12/13/the-cryptographic-doom-principle.html)出错。我们真正想要的是 [认证加密模式↗](https://en.wikipedia.org/wiki/Authenticated_encryption)。认证加密不仅保护明文的机密性，还保护真实性（即，完整性）。\
\
我们可以构建一个认证加密，假设使用 [HMAC↗](https://en.wikipedia.org/wiki/HMAC) 和我们的分组密码配对，但更容易使用 [GCM↗](https://en.wikipedia.org/wiki/Galois/Counter_Mode)。GCM 性能优越，仅使用 AES 即可实现认证加密，而无需引入其他加密原语。将我们的代码修改为使用 GCM 代替 CTR 模式是简单的。这里是更新后的代码：\
\
```\
def symmetric_enc(key, x):\
cipher = AES.new(key, AES.MODE_GCM)\
ciphertext, tag = cipher.encrypt_and_digest(pad(long_to_bytes(x), 16))\
nonce = cipher.nonce\
return ciphertext, tag, nonce\
\
def symmetric_dec(key, ciphertext, tag, nonce):\
cipher = AES.new(key, AES.MODE_GCM, nonce=nonce)\
x = bytes_to_long(unpad(cipher.decrypt_and_verify(ciphertext, tag), 16))\
return x\
\
```\
\
现在我们的代码不再依赖填充来检测无效解密（填充本身并未设计用于此！）。相反，我们依赖于 GCM，这是专门为解决此问题而设计的。请注意，现在我们不仅要存储密文和随机数，还需要存储一个_标签_。你可以把这个标签看作一个像 MAC 一样的完整性检查。\
\
#### 计算两个门\
\
现在我们可以混淆并评估一个门。那两个串联的门呢？\
\
基本上与之前的原理相同。我们为所有线路生成逻辑值 0 和 1 的标签：输入线 A、B 和 C；中间线 X；以及输出线 Y。然后我们混淆两个真值表，每个门一个。\
\
![](https://img.learnblockchain.cn/2025/04/04/951f120613c27-9d377181b100986206d4380e4061cd31.png)\
\
为了评估电路，我们按顺序评估门，从输入开始，向前推进。因此，我们首先会评估门 1 的混淆表，以获得线路 X 的解密标签；然后，我们可以评估门 2 的混淆表，以获得线路 Y 的解密标签。\
\
![](https://img.learnblockchain.cn/2025/04/04/17beb18e67942-52566a49c104a00086a8ff8787344260.png)\
\
#### 支持 N 门\
\
现在我们有了基本情况，也有了归纳情况。我们基本上可以做任何任意电路。\
\
我们将电路表示为有向图，其中边是线路，节点是门。这通常被称为 [netlist↗](https://en.wikipedia.org/wiki/Netlist)。\
\
电路的混淆版本是Alice传输给Bob的内容。这也是有向图，具有与原始电路相同的连通性，但节点是混淆表而不是门。网络（及其门）可以有任意数量的输入和输出线路。一些输入是Alice私人拥有的，一些是Bob私人拥有的。与 1 门示例一样，Alice公开将她的输入线标签提供给Bob。对于Bob的输入线，他通过盲转移从Alice那里接收它们。\
\
为了评估电路，Bob从输入线开始，按 [拓扑顺序↗](https://en.wikipedia.org/wiki/Topological_sorting) 迭代访问门。在拓扑顺序中，当一个节点被访问时，其所有前驱都已被访问。在我们的情况下，这意味着在我们评估一个混淆表时，所有输入线的标签都是可用的。\
\
你可以在 [这里↗](https://github.com/stong/mpc-from-scratch/blob/2ed031b13a6ec26a6a87ee7db48772237306b939/mpc.py#L269-L339) 找到这个算法的代码实现。\
\
### 逻辑综合\
\
这很好，但我们难道真的期望自己手动构建所有我们希望使用门级逻辑的 MPC 计算吗？也许手动编写像 N 位比较器或全加器这样的东西很简单，但复杂计算呢？如果我们想要 MPC 的以下内容—— `Sign(message, key=Hash(Alice key, Bob key))`（例如，为了创建一个 2-of-2 多签名），我们显然不必从门开始重新实现非对称加密和哈希函数，对吗？幸运的是，这是一个已经解决的问题。我们可以用 [HDL↗](https://en.wikipedia.org/wiki/Hardware_description_language)（如 Verilog）编写高级代码，并将其综合成门级逻辑。\
\
如果你不熟悉硬件设计，HDL 是一种编程语言，但用于电路设计。对于这个类比要小心，因为一些熟悉的编程语言概念不能直接转换到电路中。例如，我们在传统意义上并没有“循环”；我们可以通过有限次数展开来假装有一个循环。而且，与编程语言中的变量不同的是，线路不应该被多次赋值（即，被多个事物驱动）。从某种意义上说，一切都是 [全局值编号↗](https://en.wikipedia.org/wiki/Value_numbering)，就像 [SSA 形式↗](https://en.wikipedia.org/wiki/Static_single-assignment_form)。如果你做过符号执行或者使用过 SMT 求解器，这些差异你会很熟悉。\
\
对于实际的综合，有一些流行的开源工具，如 [Yosys↗](https://yosyshq.net/yosys/)。Yosys 还处理 [技术映射↗](https://yosyshq.readthedocs.io/projects/yosys/en/latest/CHAPTER_Techmap.html)。技术映射的主要思想是我们告知综合工具我们可以使用的门 / IP 块 / 单元，综合工具将尽力生成一个良好的设计。如果你以前写过 LLVM 后端，我喜欢把这看作是 LLVM 的 [模式匹配↗](https://eli.thegreenplace.net/2013/02/25/a-deeper-look-into-the-llvm-code-generator-part-1) 和降级。\
\
作为我们第一个非平凡的 MPC 示例，假设Alice和Bob有两个 32 位数字 `x` 和 `y`，并想要查看它们是否是彼此的乘法逆。我们可以轻松在 Verilog 中编写此逻辑：\
\
```\
// circuit.v\
module mycircuit(x, y, out);\
input wire [31:0] x;\
input wire [31:0] y;\
output wire out = (x * y) == 1;\
endmodule\
\
```\
\
我们可以使用以下 Yosys 脚本将其综合为门：\
\
```\
## 读取设计\
read_verilog circuit.v\
\
## 主要逻辑综合步骤\
synth\
\
## 技术映射步骤。告知 yosys 我们的平台支持的门\
## 我们仅实现了 AND 和 NOT 门，因此告知 abc 这一点\
abc -g AND # 'NOT' 总是自动添加\
\
## 调整设计，以便只使用 1 位线路\
splitnets -ports -format _\
\
## 杂项清理\
clean_zerowidth\
clean -purge\
\
## 保存降级设计\
write_verilog -simple-lhs -noattr out.v\
\
```\
\
生成的门级设计如下所示：\
\
![](https://img.learnblockchain.cn/2025/04/04/scroll-5f6be1bc668adb19fa10b94dde1b493b.gif)\
\
为了好玩，如果我们用 Graphviz 可视化它，这就是它的样子。32 位设计太大了，无法显示，所以这里是 4 位版本：\
\
![](https://img.learnblockchain.cn/2025/04/04/eb955e7e573f8-af300325cb2b1285f6df8d0916f23ea7.png)\
\
当然，我们很高兴让 Yosys 为我们生成这个，而不是手动编码。这只是一个简单的乘法器。想象一下，对于更复杂的计算，设计会有多复杂！\
\
### 综合所有内容\
\
此时，我们准备好实际进行我们的 MPC。再次在示例中，Alice和Bob希望确认他们的两个 32 位数字，XXX 和 YYY，是彼此的乘法逆。Alice的输入 XXX 是 1185372425，而Bob的输入 YYY 是 1337。电路将是 `out = (x * y) == 1`。让我们试试。\
\
![](https://img.learnblockchain.cn/2025/04/04/final-8c7f7a40bf596699edc65283fddb04eb.gif)\
\
我们现在可以看到所有步骤的实际操作。首先，它创建电路中的所有门。然后，它为每个线路分配标签。Bob使用盲转移接收他的输入标签，然后以拓扑顺序评估所有门。最后，他将输入标签返还给Alice，Alice发布结果：`out=1`。好极了！\
\
现在让我们研究一些使我们的实现更高效的方法。\
\
#### 优化 1：避免试验解密\
\
对于每个门，我们必须在找到混淆表中的正确条目之前进行最多四次试验解密，或者在平均情况下 2.5 次解密。这效率低下，我们可以做得更好。\
\
我们可以通过在每一行中编码信息，以表示它对应于哪些输入密钥，从而避免试验解密。这种方法在 [这篇论文↗](https://eprint.iacr.org/2012/265.pdf) 的第 5.1 节中用复杂的数学方程进行了描述，但我将在这里用普通的英语概要说明。\
\
首先，回想一下每个密文是用从两个输入标签派生的联合密钥进行加密的，每根线有一个标签。对于每根输入线，有两个标签：一个用于逻辑 0，另一个用于逻辑 1。未经损失的可一般性，我们可以生成两个标签，使其最低有效位 (LSB) 总是不同。这并不会泄露有关实际逻辑值的信息，因为逻辑 0 的标签可能具有 LSB 1 或 0；毕竟标签是随机的。然后，对于每个表条目，我们将两个标签的 LSB 附加到密文：\
\
| 输出 |\
| --- |\
| EncA0,B1(Out0)∥LSB(A0)∥LSB(B1)Enc\_{A_{\\color{blue}0},B_{\\color{red}1}}(Out\_{\\color{blue}0}) \\\| LSB(A\_0) \\\| LSB(B\_1)EncA0​​(Out0​)∥LSB(A0​)∥LSB(B1​) |\
| EncA1,B1(Out1)∥LSB(A1)∥LSB(B1)Enc\_{A_{\\color{red}}1,B_{\\color{red}1}}(Out\_{\\color{red}1}) \\\| LSB(A\_1) \\\| LSB(B\_1)EncA1​​(Out1​)∥LSB(A1​)∥LSB(B1​) |\
| EncA1,B0(Out0)∥LSB(A1)∥LSB(B0)Enc\_{A_{\\color{red}}1,B_{\\color{blue}0}}(Out\_{\\color{blue}0}) \\\| LSB(A\_1) \\\| LSB(B\_0)EncA1​​(Out0​)∥LSB(A1​)∥LSB(B0​) |\
| EncA0,B0(Out0)∥LSB(A0)∥LSB(B0)Enc\_{A_{\\color{blue}0},B_{\\color{blue}0}}(Out\_{\\color{blue}0}) \\\| LSB(A\_0) \\\| LSB(B\_0)EncA0​​(Out0​)∥LSB(A0​)∥LSB(B0​) |\
\
然后，我们可以寻找与输入标签匹配的 LSB。\
\
更好的是，我们可以按两个 LSB 对表进行排序（这在安全上是可行的，因为 LSB 是随机的），以便以 O(1)O(1)O(1) 索引。到那时，由于信息通过行的排列隐式编码，我们也可以移除附加的 LSB。通过这个优化，我们可以选择不使用认证加密，因为我们应该总是拥有正确的密钥对应于相应的密文。\
\
#### 优化 2：支持更多门\
\
我们的 MPC 实现可以正常工作，但综合电路非常庞大。为了使实现更高效，我们将增加对超出 `AND` 和 `NOT` 的一些其他门的支持。这里是我们目前支持的门：\
\
```\
def truth_table(gate):\
if gate == 'and':\
return [[0, 0], [0, 1]]\
elif gate == 'not':\
return [1, 0]\
elif gate == 'const_0':\
return 0\
elif gate == 'const_1':\
return 1\
else:\
raise ValueError('unsupported gate', gate)\
\
```\
\
Yosys 输出的设计非常庞大，因为它必须仅从 `AND` 和 `NOT` 门综合一切。但就我们的 MPC 而言，我们的混淆电路非常庞大且评估速度慢——电路的_深度_非常大。如果我们有更多的门类型可供使用，Yosys 将能够综合出一个更小的电路。\
\
从技术上讲，我们真正需要的是 `NAND`。在现实生活中，更复杂的单元与单元尺寸之间存在一些实际权衡。如果单元较简单，则可以在给定的平面或晶圆上放置更多。相同的原理也适用于我们的 MPC。对于我们来说，如果使用更复杂的真值表，我们可以综合出具有更少门（_深度_）的小电路。这会影响评估复杂性。然而，门的输入数量（_宽度_）会影响混淆表中的条目数量，从而影响我们协议的通信复杂性。\
\
更抽象地说，我们正在研究电路宽度和深度之间的权衡。我们可以将整个计算编码到一个巨大的真值表中，但表大小与宽度成指数关系。通过使用多个较小的门，我们权衡出一些宽度——更深但宽度较小。这就是为什么混淆电路相对单纯的盲转移如此重要的原因。\
\
无论如何，我们已经在使用 `AND` 门，其宽度为 2（= 四个真值表条目）和 `NOT` 门，其宽度为 1（= 两个真值表条目）。当 Yosys 综合 `NOT(AND(...))` 时，这实际上是六个表条目。一个无窥优化是也增加 `NAND` 门，它常量折叠了这个外部的 `NOT` 门。但我们可以进一步支持常见的双输入门类型。让我们通过将这些真值表硬编码来增加对 `AND`、`NAND`、`OR`、`NOR`、`XOR`、`XNOR`、`ANDNOT` 和 `ORNOT` 一组简单门的支持。\
\
```\
# [...]\
elif gate == 'nand':\
return [[1, 1], [1, 0]]\
elif gate == 'xor':\
return [[0, 1], [1, 0]]\
elif gate == 'nor':\
return [[1, 0], [0, 0]]\
# [[... 你明白了]]\
\
```\
\
我们更新 Yosys 脚本中的 `abc` 调用：\
\
```\
## 现在我们有了更多的门！请使用它们\
## 'gates' 是 AND,NAND,OR,NOR,XOR,XNOR,ANDNOT,ORNOT 的简写\
abc -g gates\
\
```\
\
现在，如果我们查看综合的设计，它显著更小了。之前的设计有超过 8000 个内部线路，而新的设计只有 3000 个。不仅如此，如果我们计算混淆电路中条目的总数，它也更少了。新的设计总共有 12056 个条目，而旧设计有 24842 个。增加对这些额外门的支持将条目数量减少了 50%!\
\
最后，供娱乐，这里可视化的 4 位设计——使用新的门类型。\
\
![](https://img.learnblockchain.cn/2025/04/04/e871e6eab0c61-3ac915f028edb9f9a28905f9eb41273c.png)\
\
#### 查找表\
\
然而我们可以做得更好。Yosys 中的技术映射步骤支持直接合成到查找表 (LUT) 中。除了考虑门，这正是我们真正想要的，因为我们的混淆电路实质上只是一个真值表网络。\
\
我们可以指定我们希望 LUT 有多大（即，输入数量）。这里有一个宽度-深度权衡，因为更大的 LUT 导致电路深度减少，但表条目增多。nnn 输入查找表中的条目数量为 2n2^n2n，因此我们预计最佳 nnn 会很小。与此同时，ABC 主要优化电路深度，而牺牲面积。\
\
| nnn | \# LUT2 | \# LUT3 | \# LUT4 | \# LUT5 | \# LUT6 | \# LUT 总计 | 总 LUT 条目 | 电路深度 |\
| --- | --- | --- | --- | --- | --- | --- | --- | --- |\
| 2 | 1607 |  |  |  |  | 2098 | 6428 | 44 |\
| 3 | 709 | 942 |  |  |  | 1638 | 10372 | 26 |\
| 4 | 653 | 920 | 46 |  |  | 1376 | 10708 | 19 |\
| 5 | 330 | 360 | 106 | 489 |  | 1285 | 21544 | 16 |\
| 6 | 548 | 256 | 66 | 80 | 471 | 950 | 36116 | 12 |\
\
不意外的是，我们确实感受到了更大 LUT 所带来的指数成本，因此我们让我们坚持更小的 LUT。要进行 LUT 合成，我们可以像这样修改 Yosys 脚本中的 `abc` 调用：\
\
```\
abc -lut 4\
\
```\
\
综合后的代码看起来像这样：\
\
```\
// [...]\
assign _0735_ = 16'h7888 >> { x_14, y_1, x_15, y_0 }; // 4-way LUT\
assign _0736_ = 8'h78 >> { _0737_, x_10, y_5 }; // 3-way LUT\
assign _0737_ = 16'h7888 >> { x_11, y_4, x_12, y_3 };\
assign _0738_ = 16'hb24d >> { _0739_, _0684_, _0677_, _0676_ };\
// [...]\
\
```\
\
#### 进一步优化\
\
在我们的混淆电路实现上，还有许多方法可以进一步改进。作为进一步阅读，有以下内容：[FreeXOR↗](https://www.cs.toronto.edu/~vlad/papers/XOR_ICALP08.pdf)，具有零成本的 `XOR` 门；[半门↗](https://eprint.iacr.org/2014/756.pdf)，每个门使用两个 AES 而不是四个；以及 [切分与调整↗](https://eprint.iacr.org/2021/749.pdf)，每个门使用 1.5 AES 块长度。我们不打算详细介绍这些论文，但如果你对如何使混淆电路在现实用例中更高效感兴趣，我们推荐你了解一下这些内容。\
\
### 讨论\
\
在结束之前，让我们讨论一些值得提出的事项。\
\
#### 组合逻辑\
\
在此时，请注意，我们只有[组合逻辑↗](https://en.wikipedia.org/wiki/Combinational_logic)，没有[时序↗](https://en.wikipedia.org/wiki/Sequential_logic)。这意味着我们没有触发器或翻转器。由于缺乏时序逻辑，我们没有寄存器，因此我们无法构建任何有状态的内容。CPU 实际上是状态机。如果我们想要构建一个通用的 MPC “CPU”，我们需要调整我们的加密原语。我们可以通过展开循环并每个周期复制一次 CPU 设计来模拟 CPU 周期，但这非常低效。在电路中减少重复的一个优化是出口并重新输入任何状态作为线路，并多次运行混淆电路（即每个周期进行一次求值）。\
\
#### 半诚实与恶意模型\
\
我们的 MPC 实现是在假设参与者是 [_半诚实_ ↗](https://en.wikipedia.org/wiki/Secure_multi-party_computation)。这意味着参与者会尽一切可能窃取他人私密信息，但他们不会偏离协议。这意味着，例如，他们确实不会提供虚假的或恶意的输入或响应给协议。\
\
更现实的模型是_恶意_模型。在这个模型中，敌方操纵并控制计算中多个参与者，可以遵循任何多项式时间策略试图攻击协议。我们不会在这篇博客文章中涉及这一点，但混淆电路可以扩展以在两种状态下工作。例如，[切分与选择技术↗](https://eprint.iacr.org/2013/079.pdf)让混淆者承诺一组电路，评估者首先打开子集以检查它们是否计算正确的函数，然后将未打开的电路用于协议的其余部分。\
\
#### 进一步阅读\
\
请查看以下资源：\
\
- [ABY↗](https://github.com/encryptogroup/ABY)，一个更为严肃的混淆电路实现\
- [ezPC↗](https://github.com/mpc-msri/EzPC)，另一个 MPC 实现\
- [批量 OT↗](https://eprint.iacr.org/2021/682.pdf) 论文\
\
### 结论\
\
在这篇文章中，我们构建了一个可用的 MPC 实现，以 Yao 的混淆电路协议的形式。我们从零开始构建了所有必要的原语。首先，我们构建了素数生成和 RSA，然后从那个非对称原语构建了 1-2 盲转移。利用盲转移作为 MPC 构建块，我们然后开发了混淆电路。我们解释了混淆和评估单个真值表的工作原理，然后扩展成完整电路。最后，我们回顾了如何使用逻辑合成和硬件设计工具来进行我们的 MPC。\
\
你可以在 [GitHub↗](https://github.com/stong/mpc-from-scratch) 找到这个项目的完整实现代码。我们鼓励你去看看！\
\
### 感谢\
\
我想感谢 [Catherine (whitequark)↗](https://mastodon.social/@whitequark) 在 Yosys 和硬件与逻辑合成部分的有益反馈和建议。\
\
我还要感谢来自 Zellic 加密团队的 Avi Weinstock 和 Mohit Sharma，感谢他们对混淆电路细节的有用反馈。\
\
### 关于我们\
\
Zellic 专注于保护新兴技术。我们的安全研究人员在从财富 500 强到 DeFi 巨头的最有价值目标中发现了漏洞。\
\
开发人员、创始人和投资者信任我们的安全评估，以快速、自信且没有关键漏洞地上市。凭借我们在现实世界攻击性安全研究中的背景，我们能够发现他人遗漏的内容。\
\
[联系我们↗](https://zellic.io/contact)，享受比其他审计更优质的审计。真正的审计，而不是橡皮图章。\

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