利用多方计算进行私有交易的 Backrunning

本文探讨了安全多方计算（MPC）的应用，以便在保护交易和搜索策略机密性的同时，允许搜索者对用户的交易进行backrunning。

感谢 Alejo Salles, Jonathan Passerat-Palmbach, Mateusz Morusiewicz, Quintus Kilbourn, Alex Obadia, Chris Hager, Leonardo Arias, 和 Hasu 的反馈与讨论。 🙏

请在 GitHub 上找到使用 MPC 进行backrunning私密交易的概念验证代码。欢迎在 论坛中讨论和合作。如果你更喜欢观看演示而不是阅读本文，也可以查看这 20 分钟的演示。

引言

区块链通过生成区块来运作，区块由提议者发布，并由用户生成的一系列交易按顺序执行。然而，提议者对交易顺序的修改和对某些交易的审查能力导致了 MEV 提取行业的兴起。在这个行业中，用户向专门提取价值、构建盈利区块并获得区块包含费用的搜索者、构建者和提议者支付高额费用。虽然一些形式的 MEV 被广泛视为对用户有害，但针对如何解决这个问题并没有广泛的共识。一些努力旨在通过使用交易顺序协议或带有门限密码学的私密内存池等方式来减轻 MEV，另一些努力则旨在重新塑造价值提取行业，使之惠及用户。本文探讨的方法属于后者。

在从用户到提议者的整个 MEV 交易供应链中检查时，解决这一模型中的 MEV——在该模型中没人会在区块上链之前获得任何反馈——显得过于复杂。在本文中，我们关注用户-搜索者接口，用户希望将其交易的机密性保持在搜索者面前，而搜索者同样希望将其搜索策略的机密性保持在用户和构建者面前。本文描述的方法允许同时进行前置运行和反向运行交易。虽然前置运行和某些其他形式的价值提取被认为对用户有害，但反向运行则允许高效的套利和清算，而不会影响用户，因为他们的交易已经完成。然而，竞争进行反向运行机会的搜索者在公共内存池中导致了负面副作用，例如竞价交易费用并使所有用户的交易变得更加昂贵。因此，需要一种解决方案，允许搜索者在不对所有人产生负面影响的情况下对用户的交易进行反向运行，其核心是隐私。

为使问题更具体，我们进一步简化，考虑仅有一个用户和一个搜索者的场景，他们将反向交易发送到一个被信任的构建者，该构建者不会从用户的交易中提取价值，并且将在同一个区块中包含用户的交易和搜索者签名的反向交易。

基于 SGX 的反向运行和隐蔽通道

在这种私密计算环境中，Intel 的软件保护扩展（SGX）等可信执行环境（TEEs）作为合理的解决方案浮现于脑海。Intel SGX 的目的在于提供安全的远程计算，这意味着对于在不受信任的机器上执行的可信程序输出的正确性可以得到保障。

基于 SGX 的backrunning私密交易

基于 SGX 的backrunning私密交易的解决方案可能包括以下步骤：

1. 用户向backrunning程序提交交易，该程序在搜索者的机器上的 SGX 区域内运行。
2. 搜索者向backrunning程序提供一个搜索程序和一个密钥。
3. backrunning程序在 SGX 区域内执行，并使用搜索程序从用户的交易生成反向交易。
4. 然后，反向交易使用搜索者提供的密钥进行签名。
5. 最后，用户的交易和签名的反向交易都被发送到构建者那里。

需要注意的是，SGX backrunning程序与所有实体之间的所有通信都可以通过传输层加密。

backrun_tx = SEARCH_PROGRAM(USER_TX)signature = sign(backrun_tx, SECRET_KEY)sendToBuilder(USER_TX, backrun_tx | signature)

然而，存在一个问题：隐蔽通道。隐蔽通道是一种通过利用现有显性通道秘密传递信息的方法，显性通道被滥用以渗透信息。另一种看待隐蔽通道的方式是将其视为一种在现有携带信号上秘密调制信息的方式。隐蔽通道与侧信道的区别在于，侧信道攻击允许攻击者仅从外部观察系统，而隐蔽通道攻击允许攻击者获得来自系统内部的支持。要担心的是（不受信任的）输入可能会以某种方式改变程序执行，从而通过隐蔽通道泄露机密信息。在这种情况下，搜索者程序可能会用于改变 SGX backrunning程序的执行，使得用户的交易被泄露。为了防止这种情况，至关重要的是检查存在的具体显性通道。

由于用户的交易已经是区域输出的一部分，因此该输出必须是（传输）加密的。否则，搜索者可以直接观察输出并以此学习用户的交易。另一种渗透信息的方式是通过网络通信，这必须受到限制以避免信息泄露。这意味着连接到以太坊 P2P 网络是不可能的，因每个连接和每个查询均可用于渗透信息。另两个需要考虑的显性通道是主机系统的 CPU 和内存。例如，隐蔽通道可以通过使用高或低的 CPU 使用率来编码信息，以表示二进制值。另一个隐蔽通道可以通过内存页面的分配或内存访问模式来编码信息。

为了确保用户的交易保持机密，搜索者的输入不得以任何方式改变程序执行，导致通过隐蔽通道泄露交易。限制搜索者输入的表达能力似乎是先决条件，但这可能对搜索者并不理想。因此，搜索者程序的表达能力与潜在隐蔽通道之间存在权衡。确定正确的平衡和起点可能是具有挑战性的，因为设计空间非常广泛。一种方法可能是从完全表达开始，逐渐限制表达能力，直到泄露的数据量被认为合理，但很难确定这一点。另一种方法可能是从完全受限开始，逐渐放宽限制，直到搜索者程序的表达能力足够，但不清楚如何判断何时实现这一点。或者，可能在表达能力与隐蔽通道权衡的中间某处开始也是一种盲目的方法。

基于 MPC 的backrunning

为了在不通过隐蔽通道泄露信息的情况下探索搜索程序的表达能力设计空间，我们使用 安全多方计算（MPC）。MPC 使多个参与方能够共同计算一个公共函数，同时保持输入机密，确保只公开函数的输出。实现这一点的一种常用技术是 Shamir 秘密分享，其中输入被分割成多个份额，在参与方之间分发，并在不泄露实际输入值的情况下对这些份额进行计算。

基于 MPC 的backrunning私密交易

在我们的设计中，我们使用 MPC 确保被信任不提取价值的构建者是唯一接收用户交易和签名反向交易结果的一方，从而消除隐蔽通道利用的可能性。MPC 设置类似于 SGX，但有两个关键区别。首先，backrunning程序作为用户与搜索者之间的通信协议运行，而不是作为在搜索者机器的 SGX 区域内运行的程序。其次，机密性通过 MPC 而不是 SGX 得到保证。

通过使用 MPC，我们可以安全地探索搜索程序的设计空间，而无需担心通过隐蔽通道的信息泄露。函数的输入通过采用加密技术保持机密，确保只公开函数的输出。我们使用 MP-SPDZ，一个通用的 MPC 框架，设计搜索者语言和backrunning协议。

需要强调的是，我们此时的目标是为探索打开空间，而不是创造一种实用的解决方案。为此，我们依赖于诸如 MPC 这类抽象概念，后者可以通过诸如 Shamir 秘密分享等技术实现，以在设计过程中实现机密性和安全性。

用户将完整交易输入到 MPC backrunning协议中，而搜索者则输入表示其策略的搜索者程序以及用于签署反向交易的密钥。MPC backrunning协议随后根据这些输入生成一个反向交易。搜索者程序由四部分组成，按顺序执行：

1. 常量列表。
2. 一组基本计算指令，格式为 <operand1_location> <operator> <operand2_location>，其中位置指的是协议内部存储中的操作数位置。该存储由 RLP 解码的用户交易和搜索者提供的常量的数据填充。计算的结果附加到协议的内部存储中，从而操作可以使用前面的计算结果。PoC 支持简单的算术运算，如加法、减法、乘法、除法和平方根。长度依赖于秘密信息的循环是不允许的，因为这会导致信息泄露。然而，可以通过展开循环来支持固定长度的循环。
3. 一组基本的比较指令，格式为 <comperand1_location> <comperator> <comperand2_location>。位置指的是协议内部存储中的比较操作数位置。PoC 当前支持以下比较：小于、小于或等于、大于、大于或等于、等于和不等于。
4. 一个用于填充反向交易的引用列表。第一个条目涉及 nonce 的协议内部存储位置，第二个条目涉及 gas limit 的存储位置，第三个条目涉及 gas price，以此类推。

现在，我们已描述了定义搜索程序结构的搜索者语言，让我们来看一下 MPC backrunning协议的设计：

## 协议内部存储storage = []
## RLP 解码用户的交易并附加到存储storage.append(RLPDecode(TX))
## 附加搜索者提供的常量到存储storage.append(SEARCHER_PROGRAM.constants)
## 在存储中执行搜索者提供的计算for p in SEARCHER_PROGRAM.computations:        execute(p, storage)
## 在存储中执行搜索者提供的比较，并跟踪所有返回的 True 是否最终为成功success = Truefor c in SEARCHER_PROGRAM.comparisons:        success &= perform(c, storage)
## 创建反向交易backrun_tx_unsigned = RLPEncode(propagateTx(SEARCHER_PROGRAM.references, storage))
## 签署反向交易backrun_tx_signed = sign(backrun_tx_unsigned, SECRET_KEY)
## 发送用户交易和签名的反向交易（或空态）到构建者if success:        sendToBuilder(TX, backrun_tx_signed)else:        sendToBuilder(TX, None)

概念验证详细解读

本部分深入探讨实施的技术细节。虽然理解高层设计不是必须的，但对于那些想深入了解的人来说，仍然可能是有趣的。如果你更愿意只是获取一个大致的概念，可以随意浏览本节并继续阅读本文的开放问题和结论部分。对于那些希望查看具体细节的人，我们提供了逐步示例。概念验证采用了 MP-SPDZ 实现，其语法与 Python 类似。有关如何设置和运行代码的代码和说明可以在 GitHub 上找到。

PoC 代码具有以下限制：

• 反向交易的签名生成未包含在此 PoC 中。尽管签名生成的实施对 PoC 有益，但考虑到探索搜索者程序的表达能力和潜在隐蔽通道之间的权衡，优先级并不算最高。
• 交易的发起者未被提取，这可能用于搜索和支付奖励。

为了演示 PoC，我们使用了一笔来自 2022 年 12 月的真实交易，其中 3.75 ETH 交换了 4,784.912579 USDT，交易链接：https://etherscan.io/tx/0xe31ba3d6c9a0a87730a6d49565f7d445aa7240ae823758ee74f4d4f76fdc9f28。

MPC backrunning协议由以下步骤组成：

1. 使用 RLP 解码用户交易并填充协议内部存储。
2. 从搜索者程序加载常量并将其添加到存储中。
3. 执行来自搜索者程序的计算。
4. 执行来自搜索者程序的比较。
5. 创建反向交易。

使用 RLP 解码交易

协议首先通过解码原始用户交易并填充存储来开始。内部存储随后看起来如下所示：

加载常量

下一步涉及从搜索者程序加载常量。需要注意的是，一些提供的常量代表链上的信息，例如在第 16088213 块上 ETH/USDT 池中的代币数量。这消除了协议查询 EVM 状态的需求。然而，更新这些常量由搜索者负责，因为 EVM 状态会改变。

必要的常量值已添加到协议内部存储。

执行计算

在深入搜索策略执行的计算之前，让我们澄清搜索者的目的以及 Uniswap v2 定价函数的工作原理。Uniswap v2 将资产的价格定义为池中相应资产的代币数 X 和 Y 的比例，即 USDT 和 WETH。然而，用户并没有准确获得这个价格，因为在购买或出售资产时，他们还会产生 0.3% 的固定费用。这个费用导致用户在购买资产时支付略高的价格，而在出售资产时接收到略低的价格。通过交易，池中的代币数量发生变化，因此价格也会变化。要计算池中新代币的数量，我们使用以下公式： (X{\text{after}} = X + \text{amount}) 和 (Y{\text{after}} = \frac{X \cdot Y}{X + \text{amount} \cdot (1 - \text{FEE})})。在这里，(\text{amount}) 表示销售的 X 代币数量。交易结束后，用户将收到 (Y - Y_{\text{after}}) 个 Y 资产的代币。我们可以将买卖后的价格计算为

[ \text{price} = \frac{X \cdot Y}{X + \text{amount} \cdot (1 - \text{FEE})} : (X + \text{amount}) ]

如果我们将此方程转化为以待售代币数量表示，并考虑 USDT 和 WETH 之间精度的差异，我们得到：

[ \text{amount} = \frac{\sqrt{\text{PREC} \cdot X \cdot (\text{FEE}^2 \cdot \text{PREC} \cdot X + 4 \cdot \text{PRICE} \cdot Y \cdot (1 - \text{FEE}))} + \text{PREC} \cdot X \cdot (\text{FEE} - 2)}{2 \cdot \text{PREC} \cdot (1 - \text{FEE})} ]

所以，搜索者为什么需要这个方程？假设在 Uniswap v2 池中的价格因交易变化，使其现在能够从其他交易所（例如中心化交易所（CEX））进行套利，搜索者可以利用该公式确定待售的（USDT）代币的数量，以最大数量地获取（ETH）代币，直到目标价格。这正是该公式的功能所在。

为了执行 ETH 对 USDT 在 Uniswap v2 的交易backrunning，搜索者的策略应考虑市场对 CEX 的价格、Uniswap v2 的定价函数以及 Uniswap v2 池的状态。这样，搜索者可以确定他们可以购买的代币数量，直到特定的目标价格并计算其利润。为了计算在反向交易中待售的 USDT 代币数量，搜索者应用前面的公式，其中 X 和 Y 是用户交易前后在 Uniswap v2 池中 WETH 和 USDT 的数量。固定的 FEE、PRICE 和 PREC 是由搜索者提供的。

利润计算公式为

[ \text{profit} = (\text{sell price} - \text{buy price}) \cdot \text{amountOut} - \text{cost} ]

其中 sell price 是搜索者在 CEX 卖出 ETH 时能够达成的价格下限，buy price 是搜索者以 USDT 在 Uniswap v2 上购买 ETH 的价格，amountOut 是反向交易中获得的 ETH 数量，而 cost 是执行链上交易和 CEX 交易的费用。尽管这些公式乍一看可能令人畏惧，但复杂性主要源于理解 Uniswap v2 的定价函数如何影响反向交易的计算。所需的所有计算都是基本的算术运算（加上平方根函数），所有必要信息都已经提供，或者可以从用户交易和搜索者提供的常量中推导出。计算在低级代码中表示，不包含变量、循环或分支，只包含对存储位置和操作数的引用。操作符代码为 0 代表加法，1 代表减法，2 代表乘法，3 代表除法，4 代表平方根。由于 MPC 在整数上操作，操作符名称将被视为将来的高级语言的一部分。

## 注意在 Uniswap 中费用的计算是基于 amountIn（尽管实际上是从 amountOut 中扣除的）
4 2 29 # 支付给 Uniswap 的费用 = amountIn * fee = 3750000000000000000 * 3 / 1000
53 3 30 # 上述运算的除法
4 1 54 # amountIn_fees = amountIn - fees
31 0 55 # swap 后池中 WETH（仅用于费用计算 - 不用于实际） = WETH_before + amountIn_fees
31 2 32 # swap 后的 USDT 在池中的数量 = WETH_before * USDT_before / WETH_after
57 3 56 # 上述除法的（= Y）
31 0 4 # swap 后池中 WETH，实际 = WETH_before + amountIn (= X)

## 此处是计算反向交易金额的运算# 注意这些计算稍微偏离了之前给出的公式，以最小化出现在整数而不是浮点数字上的误差
33 2 58 # VAR1 = PRECISION * X
35 2 29 # PRICE * fee（费用部分的 *3）
561 3 30 # PRICE * fee（上面的除法（/1000））
35 1 562 # PRICE_FEES = PRICE - PRICE * fee
63 2 59 # VAR2 = PRICE_FEES * Y
34 2 33 # VAR3 = 2 * PRECISION36 2 64 # VAR4 = 4 * VAR3
60 2 29 #   （VAR5） = VAR1 * FEE（费用部分的 *3）
67 3 30 # VAR5 上述的除法（/1000）
60 2 66 # VAR6 = VAR1 * VAR4
68 2 68 # VAR5 * VAR5
69 2 29 #   VAR6 * FEE（费用部分的 *3）
71 3 30 # VAR6 * FEE 上述的除法（/1000）
70 1 72 # VAR5 * VAR5 - VAR6 * FEE
73 0 69 # 上述 + VAR6
74 4 0 # sqrt()。第二个操作数未使用。
75 0 68 # sqrt() + VAR5
34 2 60 # 2 * VAR176 1 77 # sqrt() + VAR5 - 2 * VAR1# 分红计算完成
65 2 29 # VAR3 * FEE（费用部分的 *3）
79 3 30 # VAR3 * FEE 上述的除法／1000）
65 1 80 # VAR3 - VAR3 * FEE（= 除数）
78 3 81 # amount = dividend / divisor# 在此完成反向交易金额的计算

## 利润 = （卖出价格 - 买入价格） * amountOut / PRECISION - cost
# amountIn 现在指的是反向交易的数量。
82 2 29 # amountIn * FEE（费用部分的 *3）
83 3 30 # amountIn * FEE （上述的除法 / 1000）
58 0 82 # X + amountIn85 1 84 # X_after_fee = X + amountIn - amountIn * FEE
58 2 59 # X * Y
87 3 86 # Y_after = X * Y / X_after_fee
59 1 88 # amountOut = Y - Y_after
37 1 35 # 卖出价格 - 买入价格
90 2 89 # （卖出价格 - 买入价格） * amountOut
91 3 33 # （卖出价格 - 买入价格） * amountOut / PRECISION
92 1 38 # 利润 = （卖出价格 - 买入价格） * amountOut / PRECISION - cost# 利润计算已完成

执行比较以验证交易

搜索者希望确保反向交易仅在用户的交易确实在 Uniswap v2 上交换 ETH 对 USDT 并且反向交易确实有利可图时才会被发送到构建者。为此，搜索者执行比较，以验证用户的交易以及 MPC backrunning协议中上一步计算的结果。请注意，这种低级表示仅引用存储位置和比较器。比较器代码为 5 代表小于，6 代表小于或等于，7 代表大于，8 代表大于或等于，9 代表相等，10 代表不等。

3 9 23 # to address == Uniswap V2 router
5 9 24 # 函数选择符/方法 ID == swapExactETHForTokens(uint256,address[],address,uint256)
10 9 25 # 路径长度 == 2
11 9 26 # token1 == WETH
12 9 27 # token2 == USDT
9 8 28 # 截止日期 >= 最小截止日期
82 7 39 # backrun amountIn > 0
93 7 39 # backrun profit > 0

生成反向交易

反向交易的创建只涉及对协议内部存储项的位置列表进行引用，并使用 RLP 对其进行编码。在此 PoC 中，搜索者利用相同的 Uniswap v2 池来处理反向交易，但调用了 swapExactTokensForETH 函数，而不是用户使用的 swapExactETHForTokens 方法。通过输入 USDT，搜索者将获得可以出售以获得利润的 ETH。

40 # nonce
41 # gas limit
42 # gas price
23 # to address。Uniswap v2 路由器
39 # value. 043 # 函数选择符/方法 ID 为 swapExactTokensForETH(uint256,uint256,address[],address,uint256)
82 # amountIn
89 # amountOutMin == amountOut44 # 存储位置
45 # to address。ETH 的接收方
46 # 截止日期
25 # 地址[]/路径的长度
27 # token1。USDT
26 # token2。WETH

backrunning交易的结果

在第 16088213 块时，Uniswap v2 池中大约有 11,866.58 WETH 和 15,191,824.72 USDT。我们协议内部的计算与在第 16088214 块的链上池状态一致，显示大约 11,870.33 WETH 和 15,187,039.81 USDT。交换前 1 WETH 的价格约为 1,280.22 USDT，而在交换之后约为 1,279.41 USDT。

在此次 PoC 中，搜索者愿意以每个 WETH 最多支付 1,283.5 USDT，并以约 1,412.70 USDT（约 1,283.38 USDT/WETH 的价格）购买了大约 1.1008 WETH。搜索者还规定，他们可以在 CEX 上以至少 1,286.0 USDT 的价格出售 ETH，并且成本为 2.0 USDT（包括反向交易的成本）。

根据这些信息，反向交易产生的利润至少为 0.75 USDT。然而，如果搜索者规定只能以较低的价格出售 ETH，或者出售 ETH 加上反向交易的费用更高，那么反向交易将没有盈利，因此不会生成。

开放的问题和未来的工作

• 搜索者语言的表达能力：搜索者语言目前的功能可以通过加入更多操作符，例如模或移动，扩展。然而，不清楚该语言是否真的足够表达以实现所有现有搜索策略。
• 改善搜索者语言的可用性：当前搜索者语言是低级的，容易出错。一种解决方法是创建一种可以编译为低级搜索者语言的高级语言。高级语言可以包括变量名称、操作符名称、注释、固定长度循环，以及在单个表达式内执行多项操作的能力。这种高级语言的具体样子会是什么，能提供哪些额外功能？对计算步骤支持分支是否会有所帮助？
• 使 PoC 实用：当前的 MPC backrunning协议具有过高的计算和通信开销，导致其在现实世界中不切实际。例如，在最强的 MPC 安全模型中，其中三方中有两个可以任意恶意而保持信息的机密性，执行需要大约 22.5 小时，并需要 33.7 PB 的数据传输，跨越 9.6 百万次通信轮次。即使在用于测试的较弱安全模型中，假设两个方是诚实的，而第三方试图尽可能提取信息而不偏离协议时，执行仍需约 4 分钟并需要在 3.5 万次通信轮次中传输 6 GB 的数据。虽然此次 PoC 的重点是检验搜索者程序的表达能力与潜在隐蔽通道之间的平衡，而不是性能优化，但仍然有一个关键问题：如何使搜索者语言和backrunning协议实用化以适应人们的现实需要？多个可能的解决方案似乎是可想象的，例如使用 SGX 实现搜索者语言和backrunning协议，或将三方 MPC 设置转变为使用加扰电路的 2PC，或用同态加密替代 MPC，或者还可以搭配使用。通过探索这些选项，我们的目标是使搜索者语言和backrunning协议更具现实可用性。

结论

本文探讨了 MEV 交易供应链中的用户-搜索者接口，重点关注用户交易和搜索者策略的机密性，同时使搜索者能够执行反向交易。讨论了 SGX 的使用，并识别隐蔽通道作为对用户交易机密性的威胁。我们探讨了搜索者程序的表达能力与通过隐蔽通道信息泄露风险之间的平衡。为应对这一挑战，开发了一种backrunning协议和无隐蔽通道的搜索者语言，使用了 MPC。最后，我们在 Uniswap 交易上演示了一种概念验证的backrunning实现。

再次感谢你的阅读，期待你在 论坛上的评论! ⚡🤖

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