作者：sdaftuar
来源：https://delvingbitcoin.org/t/mempool-incentive-compatibility/553
在本文中，我会尝试总结我当前对激励兼容性推理方式的理解，这些理解是在过去几年开发 “族群交易池” 项目 [1] 的过程中逐步形成的。
有启发的问题
给定一个容纳了许多交易的交易池，哪一笔交易应该选入下一个区块？假定网络中有不止一个矿工 [2]，他们的激励是在区块体积的限制下让下一个区块的手续费 [3] 尽可能多。
当然，一旦下一个区块挖出，我们又会重新回到这个问题。因此，这个问题可以自然延伸成：我们应该如何为交易池中的所有交易排序，从而在填充一切可以填充的区块空间时，确保可以最大化每一个区块可得到的手续费（总和）？（这个问题很好回答，因为一套对池内交易的全面排序似乎也有助于了解我们应该驱逐哪些交易。）
一个相关但更困难的问题随之而来：假设我们有两个不兼容的交易组合。我们如何确定哪一个集合是矿工能选择的最佳集合？如果我们可以回答这个问题，它就会给我们带来开发合适 RBF（“手续费替换”）策略的灵感。
通过 “手续费” 来排序
因为新交易总会涌现，所以，在任何时候，都难以确定我们可见的交易池中，有多少会在下一个区块中挖出 —— 更有利可图的新交易可能会出现，从而挤出我们在可见交易中选中的一些交易。
对于固定大小的交易池，池内交易的最优排序将取决于我们选择的大小（以 vbyte 为单位）。所以，要回答的理想问题集合会是这样的：对于每一个大于 0 的整数 N，给定我们要选择总体积为 N vbyte 的交易，为要最大化总手续费，池内交易的最优排序是什么样的？
如果我们知道这个问题的答案，那么该答案也会告诉我们关于一笔交易对我们的价值，我们可能想知道的一切。举个例子，如果一笔交易总是排在最后面（对 N 的每一个值来说都如此），那么它也将会是我们的交易池在满溢时、我们要逐出的第一笔交易。
当然，作为 “背包问题（knapsack 问题）” 的一种，像上面那样作答是不现实的。作为一个现实问题，更加便利的逼近答案的方法是，为我们的交易形成一个单一的排序（single ordering），也叫 “线性化（linearization）”；无论我们要适应何等大小的区块，都仅仅截断我们的有序列表，以估计该大小下的最优入块内容。
如果拓扑 [4] 不是问题，只需以手续费率降序排列所有交易，都可以非常好地逼近答案。只要交易单体都比区块体积小，那么这种近似将跟我们真正解决背包问题的理想答案接近（误差的上限由池内最大交易与区块的体积之比决定）。
但是，拓扑要求添加额外的约束 —— 比特币的共识规则要求我们将子交易放在父母交易的后面。这就引入了一个新问题：当交易之间可能存在依赖，我们该如何思考线性化？考虑一个有启发的案例（假设下面展示的所有交易都是 100 vbyte 大小）：
交易 A 的手续费率较低，交易 C 的手续费率比 A 高；但 A+B 的手续费率，又比 C 高。当然，此处的直觉是，也许我们会把 A 和 B 捆绑在一起，并将它们选为排在 C 签名的一个交易 “分家（chunk）”。但我们如何系统化这种理解、并让它跟 “C 的费率比 A 高，因此某些情况下应该优先选择 C” 的想法相协调？
手续费率图表作为解决这个问题的一种方法
上述例子提升了一个问题：我们如何知道哪一种线性化更好（ABC 还是 CAB）？我们能否确切说明 “对一组交易的某一种排序比另一种更好” 的含义？直觉上，我们会将 “以最少的交易体积收集最多的手续费” 作为理想的线性化。我们可以用图表来表达这种观念；给定一种线性化，绘制这些点 (xn,yn) 的集合，其中：
- xn 为前 n 笔交易的总体积
- yn 为前 n 笔交易的总手续费
- 且 n 大于等于 0，小于等于交易的总数量
这些点度量了一个矿工从兼容于这种线性化的交易子集中收取的手续费总和。
在上面这个 3 笔交易的例子中，ABC 和 CAB 两种线性化会产生这样的图表：
仔细看，其实并不清楚哪种排序更好，因为如果只从池中选择 100 vbyte，那么 CAB 排序是最好的；但如果要选择 200 vbyte，那么 ABC 是最好的。但是，我们应用前面的推理 —— 如果所有的交易（在我们的案例中是交易的分家）相比于区块体积都不大，那么最优排序完全不必考虑分割 A+B 的需要（我们可以把它们当成一笔交易）。在这个假设下，我们可以画出新的手续费率图表：
在这个图表中，两种排序都把 A+B 当成一个单元，而且我们可以看到现在的 ABC 图表是其原本图表的凸包（convex hull）：从左至右移动，连续线段的斜率（也即手续费率）是单调递减的。而在 CAB 排序中，我们可以意识到，在选择 A+B 之前永远不用考虑 C，因为如果我们选择所有三笔交易，其手续费率会升高；那么，我们也应该考虑它的凸包，这就产生了下面的图表：
使用这些新图表 —— 我们的初始图表的凸包 —— 作为我们正式的手续费率图表，作为一个线性化的表示，我们可以定义：某一线性化 O 与另一线性化 P “至少一样好”，当 O 的图形包含了 P 的图形的时候，或者说，P 图形上没有一个点超出了 O 图形（两者是等价的）。（类似地，我们可以说，O “严格优于” P，当 O 至少与 P 一样好，P 却不是至少与 O 一样好的时候 —— 也即，在 O 或 P 的某一些点上，O 的手续总和会超过 P 的）
注意，我们并不排除可能出现两个无法比较的手续费率图表 —— 没有一者能包含另一者。所以，对于给定的一组交易集合，这会在这些交易的线性化集合上产生片面排序。
注：总的来说，此处的关键洞见是，在交易分家相比区块体积较小的假设下，这些累积手续费图表的凸包就捕捉到了一个矿工的手续费最大化策略：TA 将使用这些交易的一种线性化来构造区块。
这种设定下可能的最优排序
使用凸包作为我们基础、以定义两个线性化的比较，可证明有非常好的效果。给定这种片面排序，事实证明，对任何一组交易，都总是存在一个最优的线性化（只是不一定唯一），它会至少跟可能构造的其它任何线性化一样好。Pieter Wuille 已经证明了这个定理。
构造一个最优排序的直觉方法是直接在几乎所有拓扑有效的交易子集选择手续费率最高的子集、不断重复、直到所有交易都被取完。很容易看出，如果存在一个最优的线性化，这个算法必然能找到它。
族群
另一个简单的观察是，最优排序中的交易分家将总是有内部拓扑关联的（如果不是，我们就可以通过将分家分割成有关联的部分、对结果运行排序，来优化整个排序）。因此，我们可以单独地线性化一组交易中有关联的部分，称为 “族群”，而依然能在所有族群中复原最优交易排序（只需合并每一个族群内部的分家排序）。这个洞见正是 “族群交易池” 提议背后的动机（中文译本）。
总结
给定手续费图表的构造以及上面定义的片面排序，必然存在一种（但不一定唯一）交易的线性化，可以用来构造任意体积的区块。这为交易构造问题给出了一种恰当的解决方案，而且其对可以找出的最优区块的偏离收到最大交易分家的体积与区块体积的比率限制。
比较不同交易集合的线性化
上面定义的手续费率图表可以用来确定我们要如何比较线性化同一组交易的不同选择。然而，我们要解决的第二个问题是，如何能够比较两组不兼容的交易的好处；这跟我们在设计 RBF 规则时要面对的是同一个问题。
背景
就我所知，在比特币 15 年的历史中，没有人设计出了能够保证替代交易除非真的让矿工收获更多利益、不然就会被拒绝的 RBF 规则（除去那些根本不允许 任何 替代交易（！）的软件版本）。
这里有一些能够显露问题特点的有启发的案例 [5]。我会集中在来自 Bitcoin Core 的 RBF 实现上（大部分已得到 BIP 125 的描述，而该 BIP 已经存在 8 年以上了），也会触及一些时有出现的其它观点。
手续费率规则
在 BIP125 中出现的规则，要求替换交易的手续费率必须超过所有与其（直接 [6]）冲突的交易。这 看起来 似乎意味着替代交易应该会比它要替代的原版交易更快挖出、矿工能更快获得更多手续费 —— 听起来会变成一个比原来更好的交易池。但是，在这种情况下就不是这样了：
在这个案例中，A 和 B 都在交易池中，而 B’ 是 B 的潜在替换交易。B’ 支付了更高的手续费，但是，打包 A+B’ 的矿工只能得到更低的整体手续费率（手续费总和也更小），不如打包 A+B 的矿工。应该没有什么疑问了：仅仅要求替代交易的手续费率比原版交易更高（甚至高得多），并不足以（仅凭自身）就保证激励兼容。
总手续费规则
BIP 125 也指定了替代交易必须使手续费总和提高。不过，这也并不能解决上一段提到的问题；就在这个例子中，我们可以看到，如果 A 和 B’ 已经在交易池中、B 到来了，那么 B 会在 BIP 125 规则下被拒绝（因为它的手续费率低于 B’），即使 A+B 的整体手续费率高于 A+B’。
当然，这是一个本应被允许的替代交易被拒绝的例子。我们也可以找出其它问题，就是该规则被用来允许本应被拒绝的交易进入交易池。请看：
假设 A 和 B 已在交易池中，而与 A 冲突的 A’ 到来。它的手续费率比 A（唯一与之直接冲突的交易）更高，而且支付了超过 A+B 的手续费总和。所以，在手续费率以及总手续费规则下，A’ 可以替换 A+B，即使 A+B 拥有更高的整体手续费率（25 聪/vbyte）。
即使将这条规则改成考虑非直接冲突交易的手续费率，也无济于事。如果我们要求替代交易的手续费率也要高于非直接冲突交易，那么（a）这依然不足以防止激励不兼容的替换交易；以及（b）它引入了一些显著的钉死攻击问题（可用来阻止本应被允许的替代交易）。这里是两个展示这两种特性的小例子：
在这个案例中，B’ 与 B1 和 B2 直接冲突。因为它比 B1 和 B2 拥有更高的手续费率，而且也支付了更多的手续费，它会通过手续费率和总手续费的检查，但是，C+B’ 的整体手续费率比 A+B1 更低（因为 C 的体积巨大）。所以，我们不应该接受 B’ 作为替换交易。
另一方面，如果我们要求一笔交易在手续费率上打败与之冲突的所有交易，这又会阻止一些本应接受的替代交易：
在这个案例中，如果 A+B 已经在交易池中，那么 A 就不会被接受，即使选择 A’ 会得到更高的手续费率和总手续费。
使用祖先费率
我曾经建议过，在 RBF 规则中不要仅仅使用一笔交易的手续费率 [8]，也要将祖先费率作为一项分数。具体来说，我最初的建议是在一笔交易的手续费率及其祖先费率中取小值，作为其挖矿分数的一个代表；我认为，这会给出它的挖矿好处的下界。但事实证明，这还是不够保守 —— 看看这个案例：
设想 C 是池内其它交易的一笔替换交易，而我们想要知道 C 的挖矿分数。C 自身的费率是 100 聪/vbyte；其祖先费率显然显然高得多，但其被挖出时候的实际费率是非常低的，因为 B 可以独立挖出。
似乎，任何 RBF 规则都需要考虑交易的实际拓扑，而祖先费率这样的统计数据正好掩盖了这些拓扑。
在 RBF 启发分析中使用真正的挖矿分数
在我最初的族群交易池提议中，我曾指出，如果我们拥有交易池的全面排序、从中我们可以知道每一笔交易被挖出时候的手续费率（“挖矿分数”），那么我们就能得出一个简单的 RBF 规则：只需要检查新交易的挖矿分数超过了任意可被驱逐的交易的挖矿分数，并且新交易的总手续费也大于被驱逐的交易的总手续费。
但是，事后证明，这个简单规则也不足以保证交易池在替代交易进入之后变好了。考虑这个例子，所有交易都是 100 vbyte 的大小，与 C 冲突的新交易 C’ 到来：
C’ 的挖矿分数是 3.5，比 C 的挖矿分数（约 3.2）要好一些。而且 C’ 也比 C 支付了更多手续费。然而，打包原版交易集合 {A, B, C, D} 的矿工可以用 300 vbyte（交易 ABC）收取 9.5 的手续费，但打包新交易集合 {A, B, C’, D} 的矿工却只能用 300 vbyte（交易 DC’A）收集 8 的手续费。
这个结果让我非常惊讶 —— 原版交易集合比我们预想的要好，这是因为在仅看具体被添加和移除的交易的挖矿分数时，交易拓扑在一定程度上被忽视了。
使用手续费图表作为一种 RBF 规则工具
在上面讨论过手续费图表作为一种衡量线性化质量的办法的优点之后，我们自然会好奇，它是否也能帮助我们设计 RBF 规则。
假设我们有一组交易 S 以及另一组不兼容的交易 T（因为某些与 S 内的交易相冲突的交易到来，T 出现了）。我们想要知道，矿工会坚守 S，还是迁移到 T。
如上所述，我们可以计算线性化 S (F(S)) 的手续费图表并与 T (F(T)) 的图表相比较。如果 F(S) 严格优于 F(T)，那么矿工应该会更喜欢 S。但是，如果 F(S) 和 F(T) 是不可比较的，那就意味着，在某个大小上，F(T) 的累积手续费会比 F(S) 的更高（当然，其手续费率也会），同时，反之也成立，因此我们无法说哪一个对矿工更好。
在一组交易的线性化设置中，我们有一个很好的特性：我们知道最优的线性化一定存在，它跟其它线性化至少一样好，所以怎么处理不可比较的线性化不会成为一个问题 [9]。但是，这个概念并不能推广到对不兼容的交易集的思考上。设想有这样两笔相互冲突的交易：
- 交易 A：费率为 100 聪/vbyte，体积为 100 vbyte，总手续费为 1 万聪
- 交易 A’：费率为 50 聪/vbyte，体积为 2000 vbyte，总手续费为 10 万聪
到底哪一个对一个矿工来说更好？即使两个交易池仅有 A-A’ 这一个不同，它们的手续费率图表也会变成无法比较的。如果交易池内没有跟 A’ 费率相当的交易，那么矿工就会更喜欢它，因为它可以最大化下一个区块的手续费。相反，如果许多交易的费率都在 A 与 A’ 之间，那么可能矿工会更喜欢交易 A。
对一个逗趣问题的简单分析
为了进一步展示要点，我们来看另一个例子，两笔体积相同的冲突交易（并且，为了简化，假设池内并没有其它交易）：
- 交易 B：1000 聪，可在下一个区块挖出
- 交易 B’：10 万聪，但是有时间锁，因此只能在 下下 个区块挖出，也即从当前看的未来第二个区块
那该怎么办呢？我认为，这其实取决于没有在此展现的外部条件。每个矿工都有两种选择：一，争先策略，尝试立即达标交易 B（并且，如果下一个区块没有确认 B，就赶紧打包 B’）；二，等待策略，放弃在下一个区块打包 B，在下下个区块打包 B’。
首先，我们假设一个矿工在网络中的算力占比是 0.5%。
我们可以计算出这两种策略对该矿工的好处，这会取决于网络中的其它矿工怎么做：
| 其他矿工的策略 | 等待策略的收益 | 争先策略的收益 |
|---|---|---|
| 等待 | 0.005∗100000=500 | 0.005∗1000+0.995∗0.005∗100000=502.5 |
| 争先 | 0.005∗0.005∗100000=2.5 | 0.005∗1000=5 |
所以，无论网络中的其他矿工怎么做，对于这个只占 0.5% 全网算力的矿工，争先策略都比等待策略要好，所以 TA 应该立即打包交易 B。
再看看如果是一个拥有 25% 算力的矿工，会怎么样：
| 其他矿工的策略 | 等待策略的收益 | 争先策略的收益 |
|---|---|---|
| 等待 | 0.25∗100000=25000 | 0.25∗1000+0.75∗0.25∗100000=19000 |
| 争先 | 0.25∗0.25∗100000=6250 | 0.25∗1000=250 |
对于这个矿工来说，无论其他矿工怎么做，等待策略的收益都超过了争先策略，所以这个大矿工会倾向不在下一个区块包含 B；跟小矿工相反。
我猜想会有一种更全面的办法来分析这个问题，但这个例子已经说明了，在面对冲突交易时，怎么选不能仅取决于交易自身 [10]。
注：一种要求手续费率图表严格优化的 RBF 规则可以防止激励不兼容的替代交易，但也可能会把激励兼容的替代交易也排除在外。这似乎是一个很好的进一步研究的题材。
DoS 攻击抗性考量
上述所有讨论都只关注激励兼容性，而没有考虑 DoS 抗性 —— 我们关心得仅仅是如何排序我们看到得交易，或者说哪些已知的交易最好保留。
在现实中，我们必须考虑我们的激励兼容性分析是否会引入 DoS 界面 —— 并不能显然看出它不会。我们的主要考虑是基本防止 “免费转发”，即防止交易无需付出任何形式的外部成本就可以在网络中转发的情况。如果允许免费转发，那么就可以用这样的 “免费” 交易淹没整个网络、吃光节点的 CPU 的网络资源。
因为我们在比特币 P2P 网络中的目标是去中心化以及允许任何人加入，我们无法容易地为特定的网络节点施加费用。相反，我们防止免费转转发的办法是保证被转发的交易总携带了与其字节量相称的手续费 —— 我们的目标是，在任意给定时间段内（比如，出块间隔内），交易池新增的总手续费 / 转发的字节量 >= 最低转发费率（minimum_relay_fee）。
虽然最低转发费率自身是一个任意的数值（Bitcoin Core 默认值是 1 聪/vbyte），这个原则保证了多使用网络就要多付出代价。而且，提高最低转发费率也就变成了提高网络使用成本的办法，降低该数值也会降低用户（或攻击者）耗尽网络资源的成本。
案例：BIP 125 的免费转发防止办法
最重要（但令人沮丧）的 BIP 125 规则之一就是要求交易池在接受一笔替代交易之后，总手续费必须增加 最低转发费率 * 新交易的体积（否则就拒绝该替代交易）。如前所述，BIP 125 规则没有实现激励兼容性，但因为这一条规则，至少能防止免费转发。
这条规则也是 RBF“钉死攻击” 的首要来源，它使得大体积、低手续费率的交易无法轻易被小体积、高手续费的交易替代。但要是我们取消了这条规则，所支付的手续费 / 所转发的体积 就不再受最低转发费率的限制。分析特定的情境需要我们考虑其他交易池规则（它们可能也会以某种方式限制使用量），但如果我们暂时不考虑 BIP 125 的总手续费规则，可以设计出一个简单的例子：
- 100 笔交易，每一笔的体积都是 10 万 vbyte，已在网络中转发并添加到本地交易池中，费率都与最低转发费率持平（假设是 1 聪/vbyte）。
- 一笔有 100 个输入的交易，每个输入都与上述某一个交易的某一个输入相冲突，其费率是 1.001 聪/vbyte（假设每个输入的大小都接近 1 万 vbyte，但实际上略小一些）。
这时候，超过 1000 万 vB 的数据要在网络中转发，但打包它只能多得 1 万聪手续费。这跟我们想要实施得最低费率是 1000 倍得降低 —— 意思是，在这种假设情形中，如果用户要通过更新节点设置来保证维持了最低费率，他们要把最低费率换成 1000 聪/vbyte，这可能不是我们想要的结果 [11]。
案例：交易池驱逐也是（受限制的）免费转发的一个源头
当交易池（再接受一笔新交易就要）超出其体积限制的时候，我们会从 “底部” 驱逐交易 —— 可能交易池的总手续费还会下降。为了避免不受限制的免费转发，在需要驱逐交易的时候，我们会提高进入交易池的费率要求，给最低转发费率增加一个等于被驱逐交易的费率的数值。
实质上，我们是让新交易为刚刚发生的驱逐付费。因为先有驱逐后有进入，那么就有可能出现免费转发（没有新交易到来的话），因为最终最低转发费率会回退到其初始值。这个衰减的量，以及我们可以一次性驱逐的最大体积，给出了一种计算（在一段时间内）可能发生的免费转发的数量的方法。
总结
一个有趣而且有价值的研究领域是确定在网络层面是否存在激励兼容但不具有 DoS 抗性的行为（并描述它们，如果有的话）。如果存在，这样的行为可能会给用户增加直接联系矿工的激励，这对他们有好处，却会伤害网络整体上的挖矿去中心化。
理解这些情境可能有助于我们尝试设计 具备 DoS 抗性的激励兼容协议，从而了解边界在哪里。
– – –
1. 我的想法基于与许多同侪的讨论，尤其是去年的；格外感谢 Pieter Wuille、Mark Erhardt、Clara Shikhelman、Greg Sanders、Gloria Zhao，以及 Anthony Towns 与我分享他们的洞见和分析。 ↩
2. 在只有一个矿工的情况下，排序并不重要，因为该矿工最终会获得所有手续费；所有矿工都会关心收到的总手续费。 ↩
3. 在这篇文章中，我会集中在 “如何排序池内交易以最大化手续费” 这个狭隘的问题上。我会略过矿工可能会故意不打包某些高手续费交易、以激励其他矿工延长自己挖出的链而不是重组链的博弈理论效应。 ↩
4. 在使用 “拓扑” 一词时，我的意思是共识规则限定了一个区块内的有效排序，即父交易必须放在子交易前面。 ↩
5. 例子可见：Gloria 的论述 RBF 的邮件，来自 RP #23121 的评论，以及一些在 #26451 的讨论。 ↩
6. “直接冲突” 的意思是花费了至少 1 个相同输入。“间接冲突” 的意思是并没有直接花费相同的输入，但却是一个直接冲突交易的后代。 ↩
7. 注意，其他 125 规则（例如反对引入新的未确认的父交易、允许冲突的交易数量限制），也完全没有帮助。这里展示的例子也没有违反这些规则。 ↩
8. 我一开始提出了一种这样的方法，在我还没意识到它早就已经破产（而且不仅仅因为它会让 RBF 钉死更加变得更加猖獗）之前。 ↩
9. 事实上，Pieter 提出了一种多项式时间的合并算法，可以取两个无法比较的线性化作为输入，产生一个严格优于任何一者的线性化。 ↩
10. 这个案例的一个有趣的边注是，虽然提供一种仅仅考虑手续费的 RBF 规则可能符合一个用户和一个小矿工的最佳利益，因为大矿工会从最大化总费用中受益，也许用户采用这种仅基于手续费的 RBF 策略会给矿工联合抵制这种行为的激励，因为他们都可以从更大的总手续费中获益。不过，我不知道这种博弈机制是不是真的会发生；也许这是一个值得进一步研究的话题。 ↩
11. 我设想有一些方法可以让网络的用量比我这里所述的上升更加恐怖的比例 —— 不是什么难题！我可以设想一种修改可以将倍数从 1000 倍降级变成 5000 倍降级，但细节很无聊，而且也许有更加精细化的情境。 ↩
sdaftuar 2024-03-21
https://www.btcstudy.org/2024/03/21/on-mempool-incentive-compatibility-by-sdaftuar/