Deep EVM #16: Бандлинг и разрешение конфликтов — упаковка прибыльных транзакций
Engineering Team
От одной транзакции к бандлу
В предыдущих статьях мы нашли арбитражные маршруты и оптимизировали каждый по отдельности. Но серчер может обнаружить десятки прибыльных возможностей в одном блоке. Вопрос: можно ли исполнить их все?
Ответ: не всегда. Две арбитражные транзакции могут конфликтовать — если они трогают одни и те же пулы, первая транзакция меняет резервы, и вторая становится убыточной. Задача бандлинга — выбрать максимально прибыльное подмножество совместимых транзакций.
Формализация конфликтов
Две транзакции конфликтуют, если множества пулов, к которым они обращаются, пересекаются:
use std::collections::HashSet;
#[derive(Clone, Debug)]
pub struct MevOpportunity {
pub id: usize,
pub route: ArbitrageRoute,
pub input: U256,
pub gross_profit: U256,
pub gas_used: u64,
pub accessed_pools: HashSet<Address>,
}
impl MevOpportunity {
pub fn conflicts_with(&self, other: &MevOpportunity) -> bool {
self.accessed_pools
.intersection(&other.accessed_pools)
.next()
.is_some()
}
}
Граф конфликтов
Построим граф, где узлы — MEV-возможности, рёбра — конфликты. Задача выбора максимально прибыльного подмножества без конфликтов — это задача Maximum Weight Independent Set (MWIS) на графе конфликтов.
pub struct ConflictGraph {
pub opportunities: Vec<MevOpportunity>,
pub conflicts: Vec<Vec<bool>>, // матрица смежности
}
impl ConflictGraph {
pub fn build(opportunities: Vec<MevOpportunity>) -> Self {
let n = opportunities.len();
let mut conflicts = vec![vec![false; n]; n];
for i in 0..n {
for j in (i + 1)..n {
if opportunities[i].conflicts_with(&opportunities[j]) {
conflicts[i][j] = true;
conflicts[j][i] = true;
}
}
}
Self { opportunities, conflicts }
}
}
MWIS — NP-трудная задача в общем случае, но на практике граф конфликтов MEV-возможностей имеет специфическую структуру: большинство возможностей не конфликтуют (разные пулы), и граф разреженный.
Жадный алгоритм
Для десятков возможностей жадный алгоритм даёт хороший результат:
impl ConflictGraph {
pub fn greedy_selection(&self) -> Vec<usize> {
let n = self.opportunities.len();
// Сортируем по прибыли (убывание)
let mut indices: Vec<usize> = (0..n).collect();
indices.sort_by(|&a, &b| {
self.opportunities[b].gross_profit
.cmp(&self.opportunities[a].gross_profit)
});
let mut selected = Vec::new();
let mut excluded = vec![false; n];
for &i in &indices {
if excluded[i] {
continue;
}
selected.push(i);
// Исключаем все конфликтующие
for j in 0..n {
if self.conflicts[i][j] {
excluded[j] = true;
}
}
}
selected
}
}
Время работы
Жадный алгоритм: O(n^2) для построения графа конфликтов + O(n log n) для сортировки + O(n^2) для отбора. Для n=100 это микросекунды.
Точный алгоритм для малых графов
Когда возможностей мало (n <= 20), можно решить точно через bitmask DP:
pub fn exact_mwis(graph: &ConflictGraph) -> Vec<usize> {
let n = graph.opportunities.len();
assert!(n <= 20, "Too many opportunities for exact solution");
let mut best_profit = U256::ZERO;
let mut best_mask = 0u32;
// Предвычисляем маски конфликтов
let mut conflict_mask = vec![0u32; n];
for i in 0..n {
for j in 0..n {
if graph.conflicts[i][j] {
conflict_mask[i] |= 1 << j;
}
}
}
// Перебираем все подмножества
for mask in 0..(1u32 << n) {
// Проверяем что нет конфликтов внутри подмножества
let mut valid = true;
for i in 0..n {
if mask & (1 << i) != 0 {
if mask & conflict_mask[i] & !(1 << i) != 0 {
valid = false;
break;
}
}
}
if !valid {
continue;
}
// Считаем суммарную прибыль
let mut profit = U256::ZERO;
for i in 0..n {
if mask & (1 << i) != 0 {
profit += graph.opportunities[i].gross_profit;
}
}
if profit > best_profit {
best_profit = profit;
best_mask = mask;
}
}
// Декодируем маску в индексы
(0..n).filter(|&i| best_mask & (1 << i) != 0).collect()
}
Пересимуляция после разрешения конфликтов
Важный нюанс: даже не конфликтующие транзакции могут влиять друг на друга через непрямые эффекты (например, изменение base fee). Поэтому после выбора подмножества — пересимулируем весь бандл последовательно:
pub fn validate_bundle(
forker: &mut StateForker,
opportunities: &[&MevOpportunity],
) -> Vec<(usize, U256)> {
let mut results = Vec::new();
// Симулируем транзакции последовательно на одном стейте
for opp in opportunities {
let snapshot = forker.snapshot();
let calldata = encode_arbitrage_calldata(&opp.route, opp.input);
let result = forker.simulate_call(
SEARCHER_ADDRESS,
CONTRACT_ADDRESS,
calldata,
U256::ZERO,
);
if result.success {
let profit = decode_profit(&result.output);
if profit > U256::ZERO {
results.push((opp.id, profit));
// НЕ откатываем — следующая транзакция видит изменённый стейт
continue;
}
}
// Откатываем неуспешную транзакцию
forker.rollback(snapshot);
}
results
}
Сборка и отправка бандла
После валидации собираем Flashbots-бандл:
use ethers_flashbots::{BundleRequest, FlashbotsMiddleware};
pub async fn submit_flashbots_bundle(
flashbots: &FlashbotsMiddleware,
opportunities: &[&MevOpportunity],
target_block: u64,
) -> Result<(), Box<dyn std::error::Error>> {
let mut bundle = BundleRequest::new();
for opp in opportunities {
let tx = build_transaction(&opp.route, opp.input).await?;
bundle = bundle.push_transaction(tx);
}
bundle = bundle
.set_block(target_block)
.set_simulation_block(target_block - 1);
let pending = flashbots
.inner()
.send_bundle(&bundle)
.await?;
// Ждём результат
match pending.await? {
Some(receipt) => {
println!("Bundle included in block {}", receipt.block_number);
}
None => {
println!("Bundle not included — competing searcher won");
}
}
Ok(())
}
Стратегия приоритетной комиссии
Сколько отдавать билдеру? Слишком мало — бандл не включат. Слишком много — нет прибыли.
pub fn calculate_priority_fee(
total_profit: U256,
gas_used: u64,
base_fee: U256,
competition_level: f64, // 0.0-1.0
) -> U256 {
let gas_cost = U256::from(gas_used) * base_fee;
let net_after_gas = total_profit.saturating_sub(gas_cost);
// Отдаём 85-99% в зависимости от конкуренции
let share = 0.85 + competition_level * 0.14; // 85% - 99%
let tip = (net_after_gas.as_u128() as f64 * share) as u128;
U256::from(tip)
}
В реальности серчеры мониторят, какой процент их бандлов включается, и динамически регулируют долю.
Полный пайплайн серчера
pub async fn full_pipeline(
graph: &ArbitrageGraph,
forker: &mut StateForker,
flashbots: &FlashbotsMiddleware,
block: &Block,
) {
// 1. Поиск маршрутов (~50 мс)
let routes = graph.find_cycles(WETH, 3);
// 2. Симуляция и оптимизация (~200 мс)
let mut opportunities = Vec::new();
for route in routes.iter().take(50) {
let snapshot = forker.snapshot();
let (input, profit) = find_optimal_input(
forker, route, MIN_INPUT, MAX_INPUT, 30,
);
forker.rollback(snapshot);
if profit > MIN_PROFIT_THRESHOLD {
opportunities.push(MevOpportunity {
id: opportunities.len(),
route: route.clone(),
input,
gross_profit: profit,
gas_used: 300_000,
accessed_pools: route.pool_set(),
});
}
}
// 3. Разрешение конфликтов (~1 мс)
let conflict_graph = ConflictGraph::build(opportunities);
let selected = if conflict_graph.opportunities.len() <= 20 {
exact_mwis(&conflict_graph)
} else {
conflict_graph.greedy_selection()
};
// 4. Валидация бандла (~100 мс)
let selected_opps: Vec<_> = selected.iter()
.map(|&i| &conflict_graph.opportunities[i])
.collect();
let validated = validate_bundle(forker, &selected_opps);
// 5. Отправка (~10 мс)
if !validated.is_empty() {
let total_profit: U256 = validated.iter()
.map(|(_, p)| *p)
.sum();
submit_flashbots_bundle(
flashbots,
&selected_opps,
block.number + 1,
).await;
}
}
Мониторинг и метрики
Production-серчер отслеживает:
- Inclusion rate — доля включённых бандлов
- Revenue per block — средняя прибыль за блок
- Latency P99 — 99-й перцентиль времени пайплайна
- Missed opportunities — возможности, упущенные из-за таймаута
use prometheus::{IntCounter, Histogram, register_int_counter, register_histogram};
lazy_static! {
static ref BUNDLES_SUBMITTED: IntCounter = register_int_counter!(
"bundles_submitted_total", "Total bundles submitted"
).unwrap();
static ref BUNDLES_INCLUDED: IntCounter = register_int_counter!(
"bundles_included_total", "Total bundles included in blocks"
).unwrap();
static ref PIPELINE_LATENCY: Histogram = register_histogram!(
"pipeline_latency_seconds", "Pipeline execution time"
).unwrap();
}
Итоги
Бандлинг — финальная стадия MEV-пайплайна. Граф конфликтов формализует зависимости между возможностями. Жадный алгоритм даёт хороший результат за O(n^2), точный bitmask DP решает задачу для n <= 20. Пересимуляция бандла на едином стейте подтверждает реальную прибыль. Flashbots API доставляет бандл билдерам. Цикл из 16 статей Deep EVM завершён: от опкодов до production MEV-серчера.