Blockchains, MEV and the knapsack problem: a primer
创建于 更新于
摘要
本报告围绕区块链中的最大可提取价值(MEV)问题,详细剖析区块生产过程中交易排序操控对价值分配的影响,重点分析了其与经典的0-1背包问题的紧密联系。报告梳理以太坊从PoW向PoS转型和EIP-1559机制引入等多次变革,阐释蜜池内交易私有化、继而采用密封式差别价拍卖以缓解MEV现象的实践逻辑。最后,对背包式多单位拍卖的不同价格机制(DP、GSP、UP)进行了理论与实验对比,指出GSP拍卖在效率与收入之间的折中优势,为继续设计优化MEV防控机制提供方向[page::0][page::3][page::9][page::28][page::31].
速读内容
- 区块链结构与块生产过程概述 [page::1][page::3]

- 交易通过公开或私有的mempool进入,块生产者选择交易并打包成块。
- 生产者收益由用户支付的手续费加区块奖励组成,区块大小限制使交易选择成为复杂的0-1背包问题。
- 背包问题的经济学解析 [page::4][page::5][page::6]
- 背包问题被模型化为容量有限的资源在多个不可分割对象间的最优选取,交易在块中的打包即为此例。
- 完全信息下的背包问题与单一决策者相关,目标为最大化包内值总和,非分割导致NP难题。
- 多主体不完全信息环境下,背包问题转化为市场机制设计问题,卖方(区块生产者)需要根据买方(用户)私有价值分配块空间。
- 区块链中的拍卖机制与MEV诱因 [page::10][page::11][page::12]
- 区块交易空间通过多单元拍卖分配,常用的密封式拍卖包括差别价(DP)、广义第二价(GSP)和统一价(UP)拍卖。
- MEV定义为通过包括、排除或重新排序区块内交易获取的超额价值,主要由块生产者可操控交易顺序引发。
- MEV引出“搜寻者”角色,其利用智能合约和交易竞价优先权提取套利、抢先交易等机会。
- 以太坊对MEV的应对机制演变 [page::16][page::17][page::18][page::22][page::23]

- 从公开mempool的优先费拍卖(PGA)向私有中继系统转型,采用密封差别价拍卖保护交易隐私,避免竞价无谓消耗。
- EIP-1559引入基础费烧毁机制及可变块大小,实现价格调节及通胀控制,优先费支付归块生产者。
- Merge后PoS机制下Proposer-Builder Separation(PBS)架构中,区块构建与提议分离,增强系统效率及抵御审查。

- 背包式多单位拍卖与效率/收入权衡分析 [page::26][page::27][page::28][page::29]
| 拍卖类型 | 主要特征 | 效率 | 收入 | 备注 |
|----------|---------------------------------|------------------|------------------|-------------------------------------|
| DP | 中标者按自出价支付 | 低 | 最高 | 可信机制,不是真实竞价均衡 |
| GSP | 中标者支付次高价 | 较高 | 较高 | 不真实竞价,但兼具效率与收入优势 |
| UP | 所有中标者支付最高落标价 | 最高 | 最低 | 唯一真实竞价机制,易受机制操纵 |
- 位置依赖背包问题研究前沿及挑战 [page::30]
- 交易排序影响价值,通过函数调整每笔交易价值,提出新的位置依赖背包装填模型。
- 结合拍卖设计面临极大复杂性,目前相关机制理论尚不成熟,开拓研究空间广阔。
深度阅读
金融研究报告详尽分析报告
---
1. 元数据与概览
- 报告标题: Blockchains, MEV and the knapsack problem: a primer
- 作者: Vijay Mohan(Lattice Analytics Pty Ltd, Melbourne, Australia)、Peyman Khezr(School of Economics, Finance and Marketing, RMIT, Melbourne, Australia)
- 发布日期: 未明确提及确切日期,但考虑到文本中提及的资料和近期发展,预计在2023年或2024年初
- 研究主题: 区块链技术中区块生产与最大可提取价值(MEV),以及区块生产中涉及的背包问题(knapsack problem)及其相关拍卖机制设计,聚焦主要以以太坊(Ethereum)为背景展开论述
核心论点及目的:
本报告旨在聚焦于区块链中“最大可提取价值(MEV)”的问题,即区块生产者通过调整区块内交易排序而获得的额外价值。指出区块构建过程实际上是背包问题的变种,从而引入“背包拍卖(knapsack auctions)”的设计视角来缓解MEV问题。通过介绍区块链的多层交易流、价值流以及拍卖机制,报告深入阐述以太坊在PoW向PoS转化过程中的制度改革及其应对MEV的策略。报告核心信息包括MEV产生机制、相关拍卖的性质以及优化区块交易排序所面临的计算复杂性和机制设计挑战。[page::0,1,3,11,29,31]
---
2. 逐节深度解读
2.1 区块生产与交易流(第1-3页)
- 主要论点:
区块链通过打包用户提交的交易形成区块。区块生产者根据不同共识机制(PoW矿工或PoS验证者)负责生产区块,获得区块奖励和用户支付的手续费。交易从公共内存池(mempool)传递给区块生产者。区块作为容量有限资源,必须选择一些交易满足容量约束,形成一个组合优化问题。
- 推理依据及关键数据:
区块容量有限,交易大小和交易费具有差异,交易排序权决定价值流向。指出该选择过程符合背包问题的性质,是NP-hard问题,即计算复杂性极高,算法往往采用贪心近似解法。
- 交易流与资金流分析(图表1):
图1展示用户、内存池、区块生产者及区块的关系,含交易和资金双流动机制。用户提交交易(蓝色箭头途径内存池至区块生产者),支付用户手续费 $Fu$ ,区块生产者获得费用和区块奖励 $R$ 。用户收益 $\piu = \hat{V}-Fu$ ,区块生产者收益 $\pib = Fu + R$ ,其中 $\hat{V}$ 是用户从区块中获得的总体价值。总剩余 $\Pi = \piu + \pib = \hat{V} + R$ 表示系统总体效用。
- 分析:
该过程强调了背包问题的三大复杂因素:交易体积差异、交易费不同及NP-hard的组合优化性质,突显区块构造的复杂性和效率问题。[page::1,2,3]
2.2 背包问题及经济模型、市场设计视角(第4-10页)
- 基本背包问题模型(Model I):
考虑单决策者在完全信息环境中进行交易组合。每个交易(对象)有大小 $ki$ 和价值 $vi$ ,容量约束 $K$ ,配送决策 $xi \in \{0,1\}$。目标求最大价值总和。
- 经济学视角:
背包问题类似于消费预算分配问题,但关键区别在于交易不可分割(0-1约束),导致问题为NP-hard,计算更为复杂。贪心算法Dantzig(1957)在分数背包情况下最优,但0-1背包只能得到近似解。
- 从单一决策者到多主体市场(Model II):
多买家通过竞标争夺销售者拥有的有限空间,这引入私有信息和战略竞价复杂性。买家有私有估值 $vi$,卖家观察不到,存在信息不对称。卖家设定定价规则,如何实现资源有效分配和合理定价是机制设计的核心。
- 机制设计难点:
(1) 真诚信息披露,(2) 分配效率最大化,(3) 计算可行性难以三者兼得。经济学重视(1)(2),算法博弈论重视(3),因此常需折中。
- 拍卖机制种类介绍:
描述三种常见多单位密封竞价拍卖:(a) 价格歧视拍卖(DP)、(b) 广义二价拍卖(GSP)、(c) 统一价格拍卖(UP),说明公平程度、战略特点及现实应用。[page::4-10]
2.3 最大可提取价值(MEV)介绍及以太坊案例(第11-24页)
- MEV定义:
区块生产者通过调整交易包含、排除或排序,从正常区块奖励和手续费外最大化提取的额外价值。
- MEV产生机理及举例:
用户交易在公开内存池中被其他“搜索者”(bot)观察到,可能抢先提交更高手续费的相似交易,如因智能合约资金误置导致抢兑等。此动态造成用户价值被转移给搜索者或区块生产者。
- MEV的分类及影响:
区分价值转移型MEV(如夹击攻击,损害用户利益)与价值创造型MEV(如完成套利校准市场价格,利于生态)。不同MEV类型对生态影响不同,需审慎管理。
- 区块设计变迁:
公开内存池引发优先费竞价(PGA)竞赛,导致效率及公平问题。引入隐私中继(Relay)利用密封竞价机制替代,缓解竞价竞赛和塞满网络负荷问题。
- EIP-1559升级:
调整费收费机制,引入基本费用基价(base fee)自动调节,基价燃烧,从而调节货币供应和区块容量(目标15M gas,最大30M gas)。增加恢复链上经济稳定性的同时,未解决所有MEV相关排序问题。
- “合并”(Merge)升级及“提议者-构建者分离”(PBS):
PoW转PoS,减少能耗,区分区块构建者和区块提议者角色,缓解部分MEV与审查问题。引入多方竞争块构建,提议者从中选择最优块,交易通过Relay秘密传输。竞价与价值流模型更为复杂,四类主体交互。
- 相关收益表达式复盘:
不同主体(用户、搜索者、构建者、提议者)收益体现了MEV价值流分配及燃烧机制的影响,反映生态经济价值的新平衡。[page::11-25]
2.4 区块链背包问题的具体表现与拍卖机制(第25-30页)
- 生产或吞吐效率:
确保最大交易数据量在限制容量内被打包,不考虑价值,只考虑尺寸最大化。对应传统子集和问题,NP-hard,易实现,但无考虑价值,缺乏配置效率。
- 配置效率与收益最大化:
考虑交易价值及费用,设计以背包拍卖形式竞价空间。单纯寻优价值总和 NP-hard,因此采用近似算法—贪心法优先打包单位价值最高的交易。改进设计包含比较贪心选择和最大单一大标。
- 拍卖机制特点与结果:
贪心算法虽简单计算,但非配置最优,存在唯一对应激励相容的价机制,对应统一价格UP拍卖。UP拍卖的唯一激励相容性带来可信度问题,因可被区块生产者作弊。DP(差别价格)拍卖不激励相容,但可信度高,是目前以太坊常用模式。GSP(广义二价)介于两者之间,实验表现显示效率和收益两方面折中较好,近年来被建议作为改进方案。
- MEV管控视角:
当前DP拍卖在效率上不优,可能助长不公平MEV价值分配。建议逐步向UP或GSP改良,以实现平衡的配置效率和收益激励,从而抑制个别主体通过作弊榨取MEV的现象。
- 位置依赖背包问题:
考虑交易执行顺序影响价值,提出位置依赖背包模型。现有大部分理论未覆盖,该问题属于新兴研究范畴。针对区块链交易排序和位置的拍卖机制仍处于探索阶段,涉及借鉴互联网广告竞价与限量发行产品竞价等领域机制设计成果。[page::25-30]
2.5 结论(第31页)
作者总结区块构建因应MEV问题经历巨大演变,以太坊体系不断引入“搜索者”、“Relay”、“构建者”和“提议者”等新角色以完善生态。尽管改革层出不穷,但实际仍面临中心化、审查风险和系统复杂性等新挑战。作者呼吁重视背包拍卖机制设计,以在效率、公平、激励兼容与可计算性之间找到更佳平衡,为后续研究与实践提供理论与框架指引。整体报告坚定区块链机制设计需多学科交叉深化。 [page::31]
---
3. 图表深度解读
图1(page 3)
- 描述:
展示区块链中价值与交易流动的基本结构。用户向内存池提交公共交易,竞价支付费用$fu$;区块生产者接收费用和区块奖励$R$ ,再向链上生成区块。
- 数据/趋势解读:
模型明晰体现价值$\hat{V}$从用户流向区块内,用户收益$\piu = \hat{V} - Fu$,区块生产者收益$\pib = Fu + R$,总剩余$\Pi = \hat{V} + R$。强调用户交易大小和费用差异使区块构建成为背包问题(NP-hard),难以最优求解,实际采用贪心算法。
- 联系文本:
图表支持文本关于区块容量受限、交易多样性及组合优化复杂性的论述,为后续MEV和拍卖设计奠定基础。[page::3]
图2(page 15)
- 描述:
引入搜索者角色,搜索者从内存池监听交易,生成自己的交易并竞价,通过提高手续费抽取用户交易价值。交易流及资金流更加复杂,包含用户、搜索者、区块生产者三方。
- 数据/趋势解读:
用户支付费用$Fu$,搜索者支付费用$Fs$,区块生产者从两者收取费用外,还获得区块奖励。用户价值$Vu$,搜索者MEV利润$Ms$,区块生产者MEV利润$Mb$。总剩余$\Pi = Vu + Ms + Mb + R$。体现MEV价值逐步从用户向搜索者与生产者转移。
- 联系文本:
图表深化了MEV概念,显示MEV是由于搜索者介入和交易排序权力导致的价值重分配,支持区块链生态中多元主体价值策略互动的描述。[page::15]
图3(page 17)
- 描述:
叙述Relay系统出现,以实现私密交易传递,降低公开内存池的优先竞价(PGA)负面效应。Relay充当中介,使搜索者和用户可将交易私下提交。
- 数据/趋势解读:
Relay缓解竞价战,允许用户交易隐私化,防止前置攻击。费用流向中加入搜索者至区块生产者的竞价费用$Fs$,但Relay未获得明确支付。Relay系统为两面市场平台,虽平台经济激励和可持续模型仍待研究。
- 联系文本:
图体现区块链中介市场发展对MEV治理的新架构变革,反映机制设计从“开放竞价”向“隐密竞价+市场中介”转变的趋势。[page::17]
图4(page 19)
- 描述:
展示EIP-1559后机制,引入基础费用燃烧($Bu$和$Bs$),优先费($Tu$和$Ts$)归区块生产者。基价燃烧为资金流出,减少以太币供给,增加以太币价值。
- 数据/趋势解读:
燃烧机制使部分费用直接退出经济循环,导致总剩余减少。同时,费用机制算法调整基价动态平衡需求和容量。燃烧量随交易量提升,可能产生通缩效应。优先费奖励激励矿工/区块生产者。
- 联系文本:
图表形象化EIP-1559激励结构改革,经济影响双重性:一方面抑制竞价膨胀,另一方面燃烧机制减少总剩余。[page::19]
图5(page 23)
- 描述:
合并后(Merge)以太坊系统结构,介绍PBS架构:区块构建者(builders)和区块提议者(proposers)分工,搜索者向构建者提交私密交易,构建者打包区块后经Relay转交提议者。
- 数据/趋势解读:
四类主体分工协作,交易流更复杂,价值流涉及基价燃烧、用户及搜索者优先费与支付给提议者的构建者支付费$Fb$。给出了四主体的收益表达式,体现MEV多方国际争夺以及燃烧带来的价值流出。
- 联系文本:
图表展现PoS机制下区块链生态复杂性提升与MEV治理新格局,通过角色分离减少审查,提升安全性。[page::23]
---
4. 估值分析
本报告围绕区块链交易排序及区块构造机制设计,讨论其拍卖机制的效用并无传统意义上的财务估值(如DCF、市盈率等)内容。相对应地,报告重点放在机制设计、剩余最大化及收益激励的数学优化与博弈论框架。可视“总剩余”$\Pi$作为系统经济产出的估值指标,体现了区块生产者和用户之间价值动态平衡。
拍卖机制中,不同竞价模型(DP、GSP、UP)及贪心算法构成政策设计框架的核心,通过竞价金额,间接形成区块空间“价格”,驱动交易选择与排序。但求解优化难度(NP-hard),促使采用近似求解。因而估值本质隐含于拍卖设计所得的收益最大化与用户剩余最大化之间的折中。
---
5. 风险因素评估
报告未专门章节列出风险,但通过分析可提炼出如下风险因素:
- MEV带来的价值转移风险: MEV行为可能损害普通用户利益,引发信任危机,降低用户参与积极性,甚至严重时可能危害生态稳定。,
- 系统复杂性与中心化风险: PBS等复杂机制未必实现预期效果,可能引发构建者、提议者或Relay中心化,产生垄断和审查风险。Heimbach等(2023)指出PBS刺激了审查和中心化问题。
- 算法与机制设计风险: 贪心算法与DP拍卖的不完美导致配置效率低下,助长不公平竞争,且存在机制不可信及作弊可能。
- 燃烧机制副作用: 基础费用燃烧虽减少供应,但随交易量增长导致经济收缩效应,可能抑制区块链整体经济增长或反向激励。
- 信息不对称及激励兼容难题: 多主体私有信息及战略竞价形成复杂博弈,机制难以完全保证激励相容,潜存多方操纵风险。
- Relay与生态平台运营风险: Relay经济激励尚未明确,目前主要靠社区资助,存在平台持续性和可靠性风险。
报告虽未详述缓解措施,但通过机制设计完善、拍卖类型选择与多角色分工体现隐含缓解思路。[page::16,21,29,31]
---
6. 批判性视角与细微差别
- 机制设计理想与现实落差:
报告提出的统一价格拍卖(UP)尽管激励相容性理想,但机制缺乏“可信性”,易遭区块生产者操纵。现实中采用的DP拍卖虽然可信,但牺牲了效率和激励相容性,指出机制设计的三难困境。
- 效率与收益的权衡挑战:
实验和模拟显示DP拍卖收益最高但效率最低,UP最高效率但收益最低,GSP在二者间折中,呼吁区块链研究界综合考量激励效果与分配效率,避免片面追求一方带来的负面影响。
- 对MEV的复杂评价:
MEV作为复杂且双刃剑现象,报告过程中表现较为中立,兼顾其负面效应与价值创造作用,提示监管和设计需差异化视角以及精细把控。
- 机制复杂性引发新问题:
新引入的角色和中介体系(Relay、PBS)虽意图降低MEV负面影响,但可能引发更严重的中心化和审查问题,增加系统复杂度,存在制度与实际治理缺口。
- 研究空白与未来挑战:
报告多次指出背包拍卖位置依赖、机制设计与策略学习领域尚无充分理论覆盖,有大量待解难题,提示当前对问题的认知仍旧不成熟。[page::9,28,30,31]
---
7. 结论性综合
本报告系统梳理了区块链(尤其是以太坊)中区块生产过程中核心水平的“背包问题”及其变种,揭示这一组合优化问题的NP-hard性质,以及交易在容量有限的区块中的择优打包本质。最大可提取价值(MEV)作为该领域的核心经济现象,反映了区块生产者通过交易排序获得超额收益的现实挑战,极大影响区块链生态的公平性与效率。
从图1到图5的多步骤演变,报告描绘了以太坊系统应对MEV,从公开内存池到Relay引入私有竞价,再到PoS共识下的PBS机制的变迁。每一步均伴随新的经济价值流、收益方分配以及机制设计创新。EIP-1559燃烧基础费用对通缩与总剩余均带来深刻影响,体现区块链经济运行机制和传统经济理论的复杂交织。
在拍卖设计方面,报告揭示现有DP拍卖虽广泛采用,却在激励相容性和配置效率上存在缺陷。实验和仿真数据显示UP拍卖优于DP拍卖但可信性不足,GSP拍卖可能成为折中选择,兼顾收益和效率,为未来区块链机制改进及MEV治理提供了可行路径。位置依赖型背包拍卖作为新兴研究焦点,对未来解决交易排序及MEV管理至关重要。
总体而言,报告强调:
- 区块链区块构建实为复杂背包问题,涉及多主体私有信息下的策略博弈。
- MEV的出现引发了区块排序价值再分配问题,严重影响用户利益与协议公平性。
- 已有多种设计尝试改善估值分配(如Relay系统、EIP-1559及PBS),但系统复杂性提升同时产生中心化、审查及治理隐忧。
- 拍卖机制设计,特别是背包竞价机制的优化,是实现区块链效率、公平和激励兼容的核心方向。
- 未来研究需深入探索位置依赖约束、策略学习和机制设计折中等关键问题,推动技术和机制协同发展。
本报告作为区块链经济机制设计的综合入门文献,既涵盖技术难点,也配合丰富图示和数学模型,极具指导价值与应用前景。[page::0-31]
---
综上,报告详尽介绍了区块链领域面对最大可提取价值的本质机制,从计算复杂性、机制设计、经济激励到最新的以太坊设计变革,紧密结合理论与实践,为学术研究和行业应用提供了重要的分析框架和策略路径。