为公平性重新排列区块中的交易

[TOC]

AIP-68 - 为公平性重新排列区块中的交易

一、概述

该AIP建议更新交易混洗器逻辑，以增加交易在区块中排序的公平性方面的其他考量。 除了使用发送者来分散交易（来自AIP-27），该AIP还将扩展到根据两个新类别 —— 模块和入口函数，分散相邻交易（在提议的顺序中）的排序，以便为非主导模块 / 入口函数的交易在由于达到区块 Gas 限制而导致的潜在区块截断中获得更好的生存机会。

1. 目标

设计一个新的交易混洗器，以便：

• 在任何类别中没有冲突的交易的相对顺序保持不变。
• 除了例外情况，交易的洗牌器保证了一个规则：发起相同入口功能的交易在洗牌之后仍将保持它们原有的相对次序。对于其他两个类别，即来自同一发送者的调用相同模块的交易也是如此。这是为了保守起见，即一个模块/入口函数在洗牌后的提议顺序中以相同的顺序接收交易。
• 对于相邻交易（由每个类别上的可配置冲突窗口大小定义）来说，唯一的变化是将它们移动到区块内的较后位置，从而使它们分散开来。
• 来自特殊地址（0x0 ~ 0xF）的模块不受上述不变性的限制。例如，通过Account::transfer()转移 Aptos 原生 token 的交易可以被提前，即使在提议的顺序中有另一个来自不同用户的交易在它之前。。这与当前旨在分散同一用户连续交易的混洗器逻辑（在特殊地址内的模块中）保持一致。

二、动机

根据AIP-33和AIP-57，当我们预估到某个区块的处理时间过长时，就会在执行过程中对该区块进行缩减。这种情况通常发生在，因某热门模块内一些高成本交易突然增多而占据了大量网络流量的时候，在这种情况下，大多数提议中的区块交易都是来自同一个入口函数，很多其他模块或入口函数的正常交易由于触发了区块大小限制而被排除在外，这最终会影响到所有用户的体验。

三、影响

采用提议的洗牌逻辑能够确保即使在链的负载主要由某个流行模块引起时，其他非主要模块仍能获得良好的用户体验。

四、替代解决方案

TIP

原作者注：…

五、规范

该算法分为两个步骤：

• 在第一阶段，将检查原始提议顺序中的每个交易，以确定它是否在考虑的每个方面（即交易发送者地址、入口函数模块和入口函数本身；大小可单独配置）的滑动窗口内没有冲突。根据结果，交易将被选择到输出顺序中，或保留在待处理区域。
• 由于选择了新的交易，先前选择的交易将从一个滑动窗口中弹出，使先前待处理的交易免受冲突。此时，将检查每个发送者 / 每个模块 / 每个入口函数的顺序不变。如果适用，未被阻塞的交易被选入输出顺序。此过程递归进行。
• 如果在第一阶段之后还有未处理的交易，则将选择其中一个“最早”的交易作为原始提议顺序中的交易。
  • 结果，从冲突窗口中弹出的交易将像在第一阶段中一样递归处理。

每个交易在两个步骤中最多被检查一次，即O(2 * n)。每个交易在每个冲突类型（交易发送方、入口函数模块和入口函数）的滑动窗口中最多出现一次，即O(3 * n)。每当一个交易从冲突窗口中出来时，都会通过遍历所有3个冲突类型来进行检查。因此，时间复杂度为O(3 * 3 * n) = O(n)。或者，如果考虑冲突类型数量为变量m，则时间复杂度为O(m * m * n)。

链上配置：

pub enum TransactionShufflerType {
    ...
    Fairness {
        sender_conflict_window_size: u32,
        module_conflict_window_size: u32,
        entry_fun_conflict_window_size: u32,
    },
}

六、参考实现

https://github.com/aptos-labs/aptos-core/pull/11882

七、风险和缺陷

• 这一变化让由交易洗牌所引入的区块交易确定性重排序变得更为复杂。尽管我们采取了上述规则来尽可能防止重排序被恶意利用，但理论上它仍有被利用的可能性。
• 任何工作负载都不能通过重排序不公正地影响其他工作负载的性能，尽管理论上可能存在试图绕开这种公平性规则的情况。即便如此，这样的规定至少确保了在该 AIP 出台后，情况不会变得比之前更差。

八、未来潜力

在形成初始区块提案的过程中，可以通过从内存池中挑选交易来引入类似的公平性考虑。

九、时间表

1. 建议的实施时间表

代码计划包含在 1.10 版本中

2. 建议的开发者平台支持时间表

TIP

原作者注：N/A

3. 建议的部署时间表

计划通过治理提案在 1.10 中启用

十、安全性考虑

参见风险和缺陷