由 Flashbots 开创的MEV竞拍服务已受到了矿工们的欢迎，那么这种竞拍是否是最优的呢？
注：原文作者是斯坦福大学电气工程博士Guillermo Angeris，placeholder 研讨员Alex Evans以及Gauntlet创始人Tarun Chitra。
在包（Bundle）分配问题中，矿工面临着固定数量的买卖，而他们要将这些买卖包括在给定的区块中，此外，矿工还能够挑选在该区块中包括（或扫除）的包（Bundle）数量。矿工经过将每个包（Bundle）包括在区块中来赚取赢利，可是，包（Bundle）具有许多必需要考虑的分配束缚。在这篇文章中，咱们给出了一个简略的整数线性规划问题（ILP）公式，并供给了一些基本的扩展。
简介
矿工可提取价值（MEV）这个术语，指的是矿工依据买卖排序可取得的任何超额赢利。在区块链等去中心化系统中，用户经过点对点的gossip网络向矿工提交一组买卖和费用。而矿工们会收集这些买卖，并将它们分批成一个彻底有序的序列，然后由大多数矿工验证并承受作为下一个区块。
可是，在许多区块链中（例如以太坊），矿工可挑选要包括的买卖集以及提交买卖的次序。
假如一名矿工提交一笔具有经济意义的买卖，他们能够对买卖从头排序以确保他们的买卖首先履行，这也被称为抢先买卖（front running）。自从MEV这一概念被提出以来，已经出现了许多涉及闪电贷、借贷以及三明治攻击的新式 MEV 办法。MEV代表了一种价值提取办法，而用户无法经过简略地修改其买卖竞价行为来消除它。
公正（Fairness）。从理论上讲，MEV 或许导致区块链共识不稳定，并或许迫运用户在预期买卖费用之外付出额定的费用来处理买卖。这也引出了许多研讨，而这些研讨的重点是确保买卖排序及包括方面的“公正性”。而公正算法尝试运用密码学办法，例如对买卖排序或待处理买卖状况的时刻锁许诺（time-locked commitments），以强制基于时刻的“公正”确保。
MEV竞拍。或许，有一些研讨作业标明，MEV是区块链独有的，它无法经过朴实的密码学办法删去。这一系列作业有效地标明，相比用密码学办法删去MEV，矿工和用户共享MEV赢利将导致稳定的均衡。
在这个由 Flashbots 开创的国际中，“探索者”企图找到买卖的最佳次序，然后竞标由矿工以特定次序履行的“包”买卖。这种出价经过 MEV 拍卖进行调停——即参与者愿意在链下拍卖中向矿工付出额定的优先出价。因而，MEV竞拍是更受欢迎的，并且这种办法在2021 年为矿工发明了超越 7 亿美元的额定收入。
最优性（Optimality）。可是，一个自然要问的理论问题是，这种竞拍是否是最优的呢？现在，Flashbots竞拍经过运用束缚求解器处理背包问题(Knapsack problem)来有效地履行买卖包（bundle）。可是从理论上讲，咱们应该期望近似整数线性规划 (ILP) 的处理计划是“最优”的吗？应该怎么描绘最优性？ 由于 MEV 是依据一切资产的可提取价值来界说的，因而任何最优概念都取决于任何一组买卖和包（bundle）可实现的最大赢利。
总结（Summary）。在这篇短论文中，咱们给出了在单个区块中包括买卖包（bundle）的最优ILP的首个正式描绘。咱们的描绘侧重于 MEV 的三种操作办法，包括抢先买卖（front running）、跟随买卖（back running）以及三明治买卖（sandwiching）。咱们假设在实践中运用的准确gas模拟办法是作为预处理步骤履行的，它将分配问题（寻找最优包分配的问题）与正确估量单个包（bundle）赢利的问题解耦。咱们的公式能够很容易地用高档描绘言语（例如CVXPY）进行优化并在实践中运用。
一、界说
在这节内容中，咱们首先来描绘一下这篇论文中运用的基本界说。
买卖（Transaction）：矿工一般从一系列的买卖开始，咱们把这些买卖写成一些调集T（将包括在区块中）。这些买卖由区块链的用户供给，它们能够是Uniswap 或Curve的swap买卖、借贷或预言机更新等买卖。
包（Bundle）：矿工还承受许多由用户提交的包（Bundle），所谓包（Bundle）是一个带有关联买卖的操作（action，咱们稍后界说），每个包（Bundle）还包括了一些出价，例如，用户愿意付出多少钱才能将其包（Bundle）包括在区块中。矿工能够决定区块中包括哪些包（Bundle）以及买卖。而矿工从包（Bundle）中取得的赢利，等于区块中包括的各个出价的总和。
操作（action）：从以前开始，每个包（Bundle）都将一个操作（action）与一笔买卖（t ∈ T）相关联。或许的操作（action）是：抢先买卖t（在t之前履行一笔买卖），跟随买卖（在 t 之后立即履行一笔买卖），以及三明治买卖（在t前后都履行一笔买卖）。
关于给定的买卖 t ∈ T，要么是进行三明治买卖t，要么是进行抢先买卖以及跟随买卖t。例如，假如有三个包（Bundle）与买卖t关联，其间一个在t之后进行跟随买卖，一个履行抢先买卖，另一个履行三明治买卖，那么矿工能够挑选包括抢先买卖包（Bundle）和跟随买卖包（Bundle），或许是三明治买卖包（Bundle），但不能一起包括这两个类型。
咱们把这三个操作的空间称为A。现在咱们能够很容易地将包（Bundle）界说为与买卖t ∈ T 相关联的操作（a ∈ A），而它会有一个出价金额（ p > 0）。即包（Bundle）是一个三元组(a,t, p) ∈ A × T × R+，一切包（Bundle）的调集将由 B ⊆ A × T × R+ 给出。
赢利最大化（Profit maximization）。剩下的问题是：矿工怎么挑选哪些买卖包括在他们的区块中，以实现赢利最大化？鄙人一节中，咱们将展现这一问题可表述为一个简略的整数线性规划问题（ILP），而其一般可经过现代核算机在合理的时刻内处理。
二、问题表述
咱们将赢利最大化问题表述为整数线性规划 (ILP)，咱们将其称为包（Bundle）分配问题。
设置函数。为方便起见，咱们将编写界说以下函数。这儿，t ∈ T是一笔买卖，而B是一切包（Bundle）的调集。
咱们将s（t）界说为与三明治买卖t关联的包（Bundle）调集：
类似地，f（t）是与t相关联的抢先买卖，b（t）是与t相关联的跟随买卖。咱们假设 B 由 b = 1, 2, ... 索引，其间 n 是提议的包（Bundle）的数量。
问题陈说：将包（Bundle）分配问题写成整数线性规划问题的一种简略办法如下：
这儿，
是优化变量，假如当时区块中应包括包（Bundle）b，则xb为1，否则为0。问题数据是
，这是一个向量，使得 cb ≥ 0 是矿工在他们的区块中包括包（Bundle）b所取得的赢利，而T是要包括在此区块中的买卖集（不包括包（Bundle））。
标准办法。 问题 (1) 能够用矩阵表明法写得更简洁一些。为此，咱们将界说m = |T|，买卖总数，以及矩阵
为：
关于每笔买卖t∈ T和包（bundle）b ∈ B，运用这些新的界说，问题（1）可用以下办法编写：
其间1是适当维度的全1向量，而
是优化变量。
解释。 咱们能够将方针和束缚解释如下。方针
仅仅是包括在区块中的包（bundle）给出的赢利总和。第一个束缚意味着区块中最多包括一个三明治包（bundle），或许区块中最多包括两个抢先买卖或跟随买卖 t的包（bundle）。第二个束缚意味着关于每笔买卖t，最多包括一个抢先买卖包（bundle），以及最多包括一个跟随买卖包（bundle），而最后一个束缚是将x的条目束缚为布尔值。
放宽松。一般来说，除了十分小的实例之外，问题 (1) 或许很难处理，由于x的条目有布尔束缚。可是，在许多实践情况下，将布尔束缚放宽为鸿沟束缚（box constraint，即 0 ≤ x ≤ 1），经过一些简略的舍入计划后，能够发生合理的实践性能以及合理的处理计划。一般来说，这个宽松问题的最佳方针，始终是矿工或许取得的最大赢利的上限，而任何舍入计划都会给出一个下限。这能够用来给出所提议的包（bundle）分配的次优程度的一个边界。例如，假如放宽后的赢利为1.2 ETH，而拟议分配的赢利为1 ETH，则拟议分配的次优性最多为 1.2/1 − 1 = 20%。换句话说，最多可将提议的分配提高20%。
2.1扩展
问题（1）有几个简略但十分有用的扩展。
包（bundle）束缚。例如，用户或许期望指定几个包（bundle），这些包（bundle）有必要由矿工一次性悉数包括，或许根本不包括。咱们能够把它写成包（bundle）Bi ⊆ B的子集。关于 i = 1, 。 . . , ℓ，假如Bi中包括任何一个包（bundle），则矿工有必要包括包（bundle）Bi的整个子集。
新的优化问题由下面的公式给出：
其间优化变量是
和
，而问题数据是在(2) 中界说的矩阵
和矩阵
：
换句话说，D是一个对角矩阵，其对角条目是调集Bi的巨细，而 F 是一个矩阵，使得 (Fx)i 给出了 Bi 中要包括在区块中的包（bundle）的数量。束缚Fx=Dy简略地表明，关于每个或许的i，要么包括一切| Bi | 包（bundle），要么只包括0个包（bundle）。
gas约束。另一种或许（且十分简略）的扩展，是在优化问题上包括总gas束缚。例如，当包括在区块中时，每个包（bundle）b ∈ B或许运用一些最大量的gas（由gb ≥ 0给出）。咱们能够很容易地附加束缚，即包（bundle）运用的最大 gas 总量不超越买卖（但不包括 包（bundle））履行后剩下的 gas 量；即
，其间 M ≥ 0 是剩下的gas量。咱们注意到，这或许是一个很难取得合理约束的数量，由于当区块中包括包（bundle）时，买卖运用的gas或许会发生巨大变化。有其他或许的办法来进行核算，但咱们不在这儿评论它们。
三、定论
在这篇论文中，咱们供给了一个简略但十分通用的公式，它能够用于处理矿工赢利最大化包（bundle）分配的问题。虽然该问题一般是NP问题，但咱们怀疑大多数整数线性规划求解器（乃至线性规划松弛）在实践情况下或许有很好的体现。
视野开拓
过去40年来，商人们调节“服务尺寸”， 有效的增加了消费者对 a.公寓 b.游艇，甚至是 c.私人飞机 的需求。-《让顾客自己来定价》
