Поиск оптимального маршрута с наимешьшим влиянием на цену в сети ethereum?

Question

[koti4ch]

Я работаю над реализацией интеллектуальной маршрутизации ордеров (SOR) в сетях EVM с использованием CFMM, таких как Uniswap v2 и v3. Цель — найти наиболее прибыльный маршрут между двумя токенами, включая косвенные маршруты через белый список промежуточных токенов.


В каждом ребре ~10-50 пар

Например: поиск оптимального маршрута для USDT → WBNB.
Дано:
• У меня есть tokenIn и tokenOut.
• Список пар с разных децентрализованных бирж: tokenIn–indirectToken, indirectToken–tokenOut.
• Данные по каждой паре (резервы, тик, цена и т. д.).
У каждой пары токенов может быть несколько пулов ликвидности разной глубины. Это может привести к ситуациям, когда tokenIn → indirectToken прибыльна, а indirectToken → tokenOut — нет из-за низкой ликвидности.

1. Задача с одним переходом. Начал с простейшего случая: маршрутизация внутри одной пары (например, USDT–WBNB). Научился точно распределять суммы по идентичным парам. (решено)
2. Задача с двумя переходами. Расширена до маршрутов с одним промежуточным токеном, например, USDT → WETH → WBNB. Разбита на две подзадачи: USDT–WETH и WETH–WBNB (с использованием шага 1). (решено)
3. Агрегация нескольких маршрутов и сравнение пар. После решения шага 2 я перешёл к объединению нескольких маршрутов. Столкнулся с проблемами при сравнении доходности пар. Во всех случаях сравнения/сортировки высоколиквидные пары, такие как USDT–WBNB, всегда занимают первое место, даже если они не оптимальны для других маршрутов. (не решено)

Текущая задача: поиск метода сравнения пар с разными токенами и введение приоритета для прямых пар (когда это целесообразно).

Вопросы:
- Как сравнить доходность пар, где один токен одинаков, например, USDT–WETH и USDT–WBTC?
- Как сравнить доходность пар, где оба токена различны, например, CAKE–WETH и USDT–WBTC?
- Какой алгоритм лучше всего подходит для построения графа? (Сейчас я рассматриваю алгоритм Levit.)
- Какой вес следует использовать для узлов/рёбер графа?
- Как сравнить пулы Uniswap v2 и v3 и выбрать лучший пул для включения в маршрут?

Answer 1

[rPman]

У вас в вопросе есть правильные слова, вы правильно поняли проблему но сформулировали вопрос немного не так.

Главная проблема - оценка ликвидности, способности проводить сделку на указанный объем за указанный интервал времени, для указанного лимита цены (очевидно что чем не выгоднее вы укажете цену тем больше вероятность совершить сделку).

Вытаскивать из такой скудной информации как текущий тикер цены (только цена и может быть объем за минуту) информацию о ликвидности почти невозможно (есть мнение что вытащить это можно, но что бы 'создать такой алгоритм' потребуется собирать историческую информацию долго, и более полную (полный дамп сделок на торговых площадках, включая лимитные сделки, т.е. предложения о сделке вне текущего рынка, в криптоэкономике биржи обычно этим делятся по websocket протоколу, читайте api).

Самый простой алгоритм, но не самый выгодный, это собирать текущее состояние 'стакана', список лимитных ордеров на покупку и продажу, на графике (цена-объем) он выглядит как кривой треугольник, сужающийся к текущему рынку, т.е. как стаканчик от мороженного (если торговых пар мало, то по каждой можно запрашивать готовый depth по api бирже, он обычно опаздывает на несколько секунд или даже очень оперативно). Для бирж на основе контрактов такой стакан тоже можно строить, но уже самому, анализируя сколько в и как залито предложений в пул (получаете объем а формула в самом контракте, обычно там все линейно минус комиссия от объема, т.е. экспонента).

Имея на руках стаканы, можно сделать предположение, что если сделки совершать по маркету (т.е. ровно по содержимому стакана) то сделка будет совершена в полном объеме в тот момент как ее создаешь (на практике к сожалению и это не так, но проблемы происходят редко и возможны если на рынке есть клиеинты, которые ищут таких ботов как ваш и пытаются им манипулировать), а значит расчет проведения кросс сделок будет простым, простым поиском в глубину проходишь по всем возможным комбинациям, постепенно набирая комиссию за сделку и как она становится выше некого разумного лимита, выкидываешь этот путь из пула путей...

если решать в лоб, то на старте количество комбинаций велико, но можно вручную прописать оптимальные маршруты, по которым алгоритм будет проводить проверку в первую очередь, и получаемая этими путями комиссия пусть будет отправной точкой для выбора остальных вариантов.

p.s. совет, если есть возможность дешево проводить операции в кредит (с небольшим плечом, x1..x10 но тут с оговорками) можно перед основной сделкой открывать кросс встречную сделку на бирже (пусть соседней), пока на руках удерживаете промежуточный актив. Условный пример, вы покупаете btc за usdt через промежуточную валюту xpoop, т.е. usdt -> xpoop -> btc, увидев что в ее стакане появилась вкусная цена, так вот на время, пока у вас на руках xpoop неплохо было бы на другой бирже открыть маржинальную позицию продажи xpoop за usdt или xpoop за btc на тот же объем, сколько на руках xpoop... по мере продажи xpoop на тот же объем уменьшаете маржинальную позицию, что бы к моменту ее полной продажи позиция закрылась. Зачем это делать? если xpoop продать не получится сразу, то пока открыта маржинальная позиция, она страхует от рисков удержания этого г**на, и дает вам время его продать по другим каналам (при резких изменениях его курса маржинальная позиция даст плюс или минус, противоположный минусу или плюсу цены этого промежуточного актива). делать это нужно только в том случае, если длительность сделки больше чем собственно время открытия сделки. Риски тут - разные цены на маржинальном рынке и на спотовом (где вы xpoop пытаетесь продавать), плюс за удержание маржинальной позиции биржа обычно берет дополнительную палату, а еще таких бирж может тупо не быть для монет со слабой ликвидностью, что тоже является хорошим маркером вообще в них не лезть.

Comments

[koti4ch]

Спасибо за ответ, но я думаю Вы не совсем поняли мой вопрос. Меня интересует именно, как обходить граф и какой алгоритм для этого использовать, который поможет найти оптимальный маршрут для минимизациия влияния на цену (price impact) и как сравнивать пары абсолютно межу собой, а не относительно таких же пар. Я пытаюсь реализовать роутинг на подобии, как это сделали odos или kyberswap. Любые данные из блокчейна сокеты/исторические это не проблема, если потребуется, то я могу максимально точно вычислять tvl каждого токена в паре (особенно v3, т.к. там нет метода, который бы возвращал резервы)

[Wexter]

koti4ch, для такого аж целая страница на вики есть https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...