Арбитраж DEX
Сегодня мы разберемся в оптимизации декс арбитража
Перевод данной статьи ТЫК
Начнем
Если вы изучаете MEV, вас должно заинтересовать понимание того, как максимизировать прибыль от арбитража
К счастью для вас, это то, во что мы сегодня разберем
На сегодняшний день крупнейшей формой MEV является арбитраж. Концепция проста: найти разницу в цене между биржами на заданные токены, совершить сделку, получить некоторую прибыль и в процессе привести цены токенов на биржах в соответствие друг с другом
Хотя концепция проста, найти самый прибыльный арбитраж на большом наборе бирж и токенов может быть сложно
При поиске оптимального арбитража вы соревнуетесь со временем блока, и есть много динамичных частей, который надо учитывать, например новые транзакции в мемпуле, изменение справочных цен на централизованных биржах и т.д.
К счастью для нас, этот оптимальный арбитраж оказался проблемой «convex optimsation» для Constant Function Market Makers (CFMM) (маркет-мейкеров с постоянными функциями), таких как Uniswap, Sushiswap, Balancer и т. д.
Что это означает, будет предметом этой статьи, но если коротко, то это означает, что мы можем эффективно решить проблему арбитража до глобальной оптимальности
Или, говоря простым языком, у нас есть формула, которая может эффективно найти набор сделок, который максимизирует арбитражную прибыль на наборе CFMM
Математические оптимизации
Convex optimisations (выпуклая оптимизация) - это подраздел математической оптимизации
Если мы хотим узнать о выпуклых оптимизациях, хорошее место для начала — получить общее представление о том, что такое математическая оптимизация
Математическая оптимизация — это выбор наилучшего элемента по некоторому критерию из некоторого набора доступных альтернатив
Итак, что это на самом деле означает, давайте сосредоточимся на наиболее распространенном варианте, который использует математическую оптимизацию при решении задач минимальных/максимальных значений
Задачи минимума/максимума — это задачи, которые минимизируют или максимизируют «целевую функцию» с учетом некоторых «ограничений» на входные значения этой функции
Обратите внимание, что ограничения могут быть в виде ограничений неравенства (x^2 + y^2 >= 1) или ограничений равенства (x^2 + y^2 = 1)
Например, при наличии бюджета купите как можно больше фруктов в супермаркете, где у каждого фрукта своя цена. Наши ограничения могут заключаться в том, что мы можем купить не более 5 бананов (b <= 5 ограничение неравенства) и что мы должны купить ровно один апельсин (а = 1 ограничение равенства)
Теперь давайте рассмотрим более сложный пример и нотацию, которая будет использоваться для представления проблемы. Я также предоставлю альтернативный способ просмотра, который может быть более интуитивным для тех, кто имеет опыт программирования
Пример ограниченной оптимизации
Вас просят максимизировать функцию f( x, y ), где
f( x, y ) = x^2 * y
x^2 + y^2 = 1
Ограничение предоставляет нам набор возможных значений x и y
Например, когда x = 1 и y = 1, x^2 + y^2 = 2, что не равно 1. Следовательно, это не соответствует ограничению и не является допустимой позицией x, y
Когда x = 0,70710678118 и y = 0,70710678118, x ^ 2 + y ^ 2 = 1, что равно 1. Следовательно, эти координаты x, y соответствуют ограничению и действительны
Эта же функция и ограничения могут быть представлены в виде функции в python. Наша цель — максимизировать то, что возвращает функция
Функция objective_function( x, y ) эквивалентна f( x, y ). Для ограничения я создал исключение
Эту проблему можно просмотреть графически с 3 осями: одна для x, одна для y и одна для возвращаемого результата f(x, y)
Выше приведен трехмерный график, который представляет эту проблему. Красный круг представляет все координаты x, y, которые удовлетворяют ограничению
x^2 + y^2 = 1
Еще один способ визуализировать этот график — представить, что вы рисуете мелом оси X и Y на полу большой игровой площадки
Учитывая координаты x, y, мы можем пройти к этой позиции на игровой площадке, и в этом месте нам будет возвращено значение f ( x, y )
Возвращаемое значение — целевая функция, которую мы пытаемся максимизировать. Его значение будет представлять некоторую высоту над или под полом. Поэтому высота над/под землей представляет нашу третью ось f(x, y)
Если бы у нас была возможность поместить плавающий теннисный мяч над/под землей на основе возвращаемой функции f(x, y), мы могли бы построить трехмерный график
Если сделать это по каждой координате, эта сеть плавающих теннисных мячей будет соответствовать трехмерному графику, который мы видим на изображениях выше
Тогда вопрос максимизации можно рассматривать как заданный набор теннисных мячей, размещенных над/под землей во всех координатах игровой площадки (x, y), где x^2 + y^2 = 1. Найдите теннисный мяч, который находится выше всего над землей
Постановка задачи оптимизации
Цель этого примера — показать нам, как формулируется задача оптимизации
У нас есть некоторая целевая функция, которую мы хотим минимизировать/максимизировать, и набор ограничений к ней. Важность этого станет очевидной, когда мы посмотрим на реальный арбитраж
Это весь контекст, который нам нужен для остальной части этой статьи, однако, если вы хотите узнать больше об этой конкретной проблеме, то есть набор видеороликов, описывающих решение. Не стесняйтесь вернуться в конце и просмотреть их, чтобы улучшить понимание
Теперь давайте перейдем к оптимизации, специфичной для арбитража CFMM, выпуклой оптимизации
Выпуклая оптимизация
Во-первых, давайте начнем с рассмотрения того, что делает нашу задачу оптимизации арбитража CFMM выпуклой. Мы будем иметь дело со многим из того, с чем мы уже сталкивались, а именно с целевой функцией и ограничениями
- Целевая функция должна быть выпуклой
- Функция равенства может быть линейной. Вы можете задаться вопросом, почему функция равенства может быть линейной, но мы увидим это в [3]
- Линейную функцию равенства можно преобразовать в 2 функции равенства, и, учитывая, что функция равенства является линейной, мы знаем, что связанные функции равенства будут выпуклыми (ТУТ подробнее об этом)
- Функции неравенства должны быть выпуклыми
Итак, мы определили, что нам нужно, чтобы целевая функция и ограничения неравенства были выпуклыми, но что определяет, является ли функция выпуклой?
Выпуклые функции
Давайте посмотрим на определение
Выпуклая функция — функция, для которой отрезок между любыми двумя точками её графика в векторном пространстве лежит по одну сторону соответствующей дуги графика
Изображение ниже поможет прояснить, что это значит
Мы можем видеть на втором и третьем графиках, что мы можем определить прямые между двумя точками на графике, которые идут пересекая график, указывая на то, что они невыпуклые
Если мы посмотрим на функцию Uniswap (x * y = k) на графике, то мы увидим, что это выпуклая функция
Опять же, это весь контекст, который нам нужен. Мы определили, что наша целевая функция и ограничения неравенства должны быть выпуклыми для задачи выпуклой оптимизации
Можно еще многое узнать о выпуклой оптимизации, свойстве двойственности, лагранжиане, методе внутренних точек и т. д., однако это не требуется для понимания остальной части статьи
Я бы посоветовал вам углубиться в эти темы после окончания. Вы можете начать с этих 3 видео, которые дают отличный обзор некоторых из этих концепций
Теперь, когда мы определили, что наша арбитражная задача CFMM является выпуклой, мы можем перейти к реализации
Арбитражная маршрутизация CFMM
В этом разделе основное внимание будет уделено улучшению вашего понимания того, как проблема арбитража оформляется в виде задачи выпуклой оптимизации, и решение этой проблемы с помощью Python
Мы будем в значительной степени опираться на 2 ресурса: первый — доклад Тео Диамандиса о выпуклой оптимизации, а второй — репозиторий github по выпуклой оптимизации от Гильермо Ангериса. Оба должны быть рассмотрены в конце статьи, чтобы закрепить ваше понимание
Весь код в остальной части статьи можно найти в этом gist, который представляет собой форк репозитория Гильермо с некоторыми дополнениями
Одно предостережение, которое следует отметить - мы будем игнорировать газ во время этих расчетов, чтобы все было просто. Обратите внимание, что Тео в своем выступлении затрагивает вопрос о том, как использовать газ
Обрамление проблемы
Постановка задачи дается набором пулов CFMM (постоянный маркет-мейкер). Есть ли возможность арбитража, и если да, то какой из них оптимален?
Эта проблема на самом деле является подмножеством проблемы маршрутизации CFMM
Позже мы увидим, что добавление одного дополнительного ограничения позволяет нам использовать эту проблему маршрутизации для решения нашей арбитражной оптимизации
Так как же сформулировать эту задачу маршрутизации в виде задачи выпуклой оптимизации?
Давайте рассмотрим его шаг за шагом, познакомив вас с математическим подходом и его переводом в код
Пространство поиска
Начнем с определения области поиска. Мы можем либо определить набор токенов и найти все пулы, содержащие эти токены, либо мы можем определить набор пулов, и в этом случае токены определяются пулами в нашем наборе данных
Наши токены будут помечены от 1 до «n», а пулы CFMM будут помечены от 1 до «m»
Связь между токенами и пулами представляет собой сеть CFMM и может быть просмотрена с помощью двудольного графа
Давайте взглянем на двудольный граф, а также на то, как токены и CFMM определены в arbitrage.py (обратите внимание, что в коде мы используем маркировку от 0 до n-1 и от 0 до m-1)
Это выглядит сложно, но я могу заверить вас, что это не так
- Пулы CFMM объявлены в коде как массив с именем «local_indices». Каждый пул CFMM сам по себе является массивом, элементы которого определяют, какие токены доступны в этом пуле. «m» равно 5, так как у нас есть 5 пулов CFMM
- Токены объявлены в коде как список [ 0, 1, 2, 3 ], называемый «global indices». «n» равно 4, так как у нас есть 4 элемента в списке. Числа в этом списке представляют токены, т.е.
- 0 = TOKEN-0
- 1 = TOKEN-1
- Хотя для простоты я обозначил эти токены TOKEN-X, вы можете представить их сопоставление с реальными токенами, такими как ETH, DAI, SOL и т. д.
- На двудольном графике пулы CFMM показаны слева, а токены — справа. Узел пула подключается к узлу токена, если этот пул содержит этот токена. Это дает нам полное представление о сети пулов CFMM, с которыми мы работаем
Давайте быстро пробежимся по каждому CFMM
- CFMM 0 — это пул Balancer (пулы Balancer могут содержать более 2 токенов)
- CFMM 1 это UniswapV2 пул
- CFMM 2 это UniswapV2 пул
- CFMM 3 это UniswapV2 пул
- CFMM 4 является пулом с постоянной суммой
В этот момент вы можете спросить, почему токены были определены как «global_indices», а пулы CFMM — как «local_indices»? Давай выясним
Global vs Local индексы
Приведенное выше наименование относится к маркировке токенов с глобальным индексом, которая применяется ко всем пулам CFMM, и маркировке с локальным индексом токенов, которая применяется к определенному пулу CFMM
Чтобы дать вам пример, мы объявили следующие глобальные индексы
Если мы посмотрим на локальный индекс для CFMM-2, то мы имеем
Это означает, что отображение индекса токена можно просматривать глобально или локально. Если мы посмотрим на глобальный индекс 0, то увидим, что он соответствует TOKEN-0. Если мы посмотрим на локальный индекс 0 в CFMM-2, то мы увидим, что он сопоставляется с TOKEN-1, отличным от сопоставления глобального индекса
Локальные индексы могут быть определены с помощью обозначений ниже
Ниже приведена таблица, показывающая как глобальный индекс, так и локальный индекс каждого CFMM
Поскольку наш глобальный индекс отличается от наших локальных, нам нужен способ перевода локальных индексов в глобальные индексы
В конечном итоге мы хотим увидеть чистую прибыль/убыток каждого токена во всей сети пулов CFMM после завершения всех сделок. Это будет отображаться в глобальном индексе
Для этого преобразования из локального индекса в глобальный используется набор матриц
Ниже приведен набор матриц для нашего примера
Обратите внимание, что A0 отображает CFMM-0, A1 CFMM-1 и т. д. Эти матрицы генерируются с использованием следующего кода
Мы увидим эти матрицы в действии позже в этой статье, а сейчас вам просто нужно знать, что они существуют и что их назначение — сопоставление локальных индексов с глобальными
Далее нам нужно посмотреть, как мы определяем наши сделки в CFMM
Сделки — лямбды и дельты
При совершении сделки/обмена с пулом у нас есть сумма, которую мы вкладываем в пул, называемая «Дельта», и сумма, которую мы выводим из пула, известная как «Лямбда»
Каждый токен в пуле имеет свои собственные значения «Дельта» и «Лямбда»
Например, если мы торгуем в пуле UniswapV2 ETH/DAI и вкладываем 1 ETH и получаем 2000 DAI, у нас будут следующие значения для «Дельта» и «Лямбда»
Торговая функция
Мы можем определить сделку, используя «Дельта» и «Лямбда», и использовать эти значения, чтобы гарантировать, что сделка соответствует торговой функции, которая управляет пулом
Мы определяем торговую функцию с помощью греческого символа "фи" φ
- Совершение сделки «Дельта i» и «Лямбда i» против «CFMM i»
- Результатом сделки является конвертация выставленных токенов «Дельта» в полученные токены «Лямбда»
- Сделка принимается, если она соответствует ограничению торговой функции. Торговая функция фи принимает резервы пула, «Дельта», «Лямбда» и «Гамма»
- «Гамма» представляет собой (1 - торговая комиссия CFMM). Это гарантирует, что мы принимаем во внимание торговую комиссию (0,3% для UniswapV2), которая будет отправлена в протокол из нашей «Дельты» при добавлении токенов в резервы
- Торговая функция гарантирует, что результатом сделки станет новый резерв, который больше или равен результату торговой функции старых резервов
Давайте посмотрим, как мы справимся с этим в коде
- Резервы объявляются для каждого пула CFMM. В этом примере они были жестко запрограммированы, в действительности вы будете постоянно обновлять эти резервы по мере того, как сделки происходят в сети. Первый элемент в массиве [ 4, 4, 4, 4 ] представляет пул Balancer и означает, что у нас есть следующее в пуле
- Торговые комиссии объявляются для каждого пула CFMM. Торговые комиссии определяются как 1 - фактическая комиссия. Например, UniswapV2 — это комиссия в размере 0,3%, поэтому наша комиссия составляет 0,997
- «Дельты» и «лямбды» объявляются и определяются с помощью cp, которая является библиотекой cvxpy. Эта библиотека представляет собой решатель выпуклой оптимизации. На данный момент в коде «Дельта» и «Лямбда» являются абстрактными, они не имеют реальной ценности, пока мы не попросим cvxpy решить оптимизацию
- Объявлены новые резервы. Мы видим, что они рассчитываются с использованием уравнения, которое мы видели ранее
Теперь, когда мы понимаем, как будет определяться каждый отдельный своп, мы можем определить «Net Network Trade»
Net Network Trade
«Net Network Trade» — это +/- каждого токена в сети в конце всех сделок относительно нашей начальной позиции
Здесь будут использоваться матрицы «Ai», которые мы определили ранее
Они позволяют нам совершить сделку с пулом CFMM, который состоит из токенов этого CFMM по их локальным индексам, и объединить его с нашей матрицей «Ai», чтобы обновить массив глобальных индексов, который будет представлять нашу «Net Network Trade»
«Net Network Trade» представлена греческой буквой "пси" Ψ. Её математическое обозначение показано ниже
На изображении выше указано, что пси Ψ представляет собой сумму всех сделок по всем CFMM 1 → m, где сделка определяется «Лямбда i» - «Дельта i», а «Ai» используется для преобразования этой сделки в ее глобальное отображение
Давайте снова углубимся в код, сосредоточившись на примере CFMM-2
- Пси обьявлено. Мы снова используем библиотеку cvxpy. Символ @ при использовании с матрицами означает скалярное произведение двух значений. У нас есть матрица A2, которая преобразует локальные индексы токенов в глобальные индексы токенов и (L-D), которая представляет собой «лямбда» — «дельта», т. е. сколько поступает во время свопа и сколько выходит. Мы суммируем результаты для CFMM, чтобы получить нашу «Net Network Trade»
- Демонстрация метода скалярного произведения для тех, кто не знаком с умножением матриц
- The result of the dot production calculation for CFMM-2 can be seen here. Each row represents the +/- of a token in the trade. Note the numbers above come from the cvxpy solution to our convex optimsation problem. Результат расчета для CFMM-2 можно увидеть здесь. Каждая строка представляет +/- токена в сделке. Обратите внимание, что приведенные выше числа взяты из решения cvxpy нашей задачи выпуклой оптимизации
Выше мы рассмотрели CFMM-2 отдельно, теперь давайте посмотрим на сумму всех CFMM, чтобы получить нашу матрицу «Net Network Trade»
Обратите внимание, что для этой диаграммы мы округлили результаты до 3 знаков после запятой, поэтому результат будет немного отличаться от вывода python в arbitrage.py
Каждая матрица представляет сделку, которая произошла на этом конкретном CFMM, где положительные значения соответствуют полученным токенам, а отрицательные значения — проданным токенам. Объединив все эти сделки вместе, мы получим нашу «Net Network Trade»
- CFMM-0 выполняет трейд
- CFMM-1 выполняет трейд
- CFMM-2 выполняет трейд
- CFMM-3 выполняет трейд
- CFMM-4 выполняет трейд
- Net Network Trade
Далее нам нужно подумать о том, что именно мы хотим максимизировать. Какова наша целевая функция?
Objective (Utility) Function
Целевая функция (Objective Function), которую иногда называют функцией полезности (Utility Function) — это то, что мы хотим максимизировать
Итак, что же мы все таки хотим максимизировать?
Мы хотим максимизировать общую стоимость, которую мы получаем в конце всех сделок. Для этого мы не можем использовать номер каждого отдельного токена, поскольку цены на токены различаются. Нам нужно преобразовать токены в общую единицу стоимости, нам нужно нормализовать данные
Мы можем сделать это, получив стоимость токенов в долларах США с внешних рынков с высокой ликвидностью
Это означает, что нашей целевой функцией является максимизация «Net Network Trade» в долларах США. Давайте проверим код
- Мы определяем рыночную стоимость каждого токена. Здесь мы используем жестко закодированный массив, но на самом деле мы будем постоянно запрашивать конечную данные с биржи, чтобы получить последние цены
- Целевая функция объявлена как obj. В нем говорится, что мы хотим максимизировать «market_value @ psi», как я упоминал ранее, @ в этом контексте означает матричное умножение
- Эти две матрицы представляют собой рыночный обьем и пси (стоимость каждого токена в долларах). Полученная матрица представляет собой «Net Network Trade» в долларах США, именно то, что мы пытаемся максимизировать
Как уже упоминалось, значения, которые я использовал здесь, взяты из фактического решения, на самом деле до решения выпуклой оптимизации все это абстрактные значения
Я включил их, так как чувствую, что видение реальных значений, а не символов, иногда может помочь нашему пониманию
Обратите внимание, что иногда мы можем захотеть максимизировать значение для определенных токенов. Если бы мы были заинтересованы только в приобретении ТОКЕН-0 и ТОКЕН-2, мы могли бы установить рыночную стоимость ТОКЕН-1 и ТОКЕН-3 на ноль. Это заставит оптимизацию максимизировать возвращаемое значение только в токенах 0 и 2, а не во всех 4 токенах
Теперь у нас есть целевая функция, и мы можем перейти к последней части головоломки, к ограничениям системы
Торговые ограничения
Проблема выпуклой оптимизации, которую мы решали на протяжении всей статьи, существует в сети пулов CFMM
Эти пулы имеют свои собственные законы, которые регулируют их
Эти законы представлены в форме торговых функций, о которых мы говорили ранее. Самая известная из них — Uniswap «x * y = k»
Изучение каждой торговой функции CFMM выходит за рамки этой статьи, но если вам интересно, прочитайте эту статью ТЫК
Выше приведены торговые функции для 3 DEX, на которых мы торгуем. В рамках этих 3 DEX мы торгуем в 5 пулах CFMM. У каждого пула есть стрелка, указывающая на используемую им торговую функцию
Давайте посмотрим, как эти ограничения определены в коде
- Торговая функция Balancer представляет собой функцию среднего геометрического. Она включает веса токенов в пуле и объявляется с помощью cp.geo_mean. Сумма весов ([4, 3, 2, 1]) в сумме составляет 1, представляющую все активы в пуле
- UniswapV2 также является маркет-мейкером среднего геометрического, поэтому cp.geo_mean снова можно использовать для определения ограничений для CFMM 1, 2 и 3
- Постоянная сумма использует другую торговую функцию, поэтому мы используем cp.sum
- Это не ограничение торговой функции, а ограничение, которое превращает нашу проблему маршрутизации в проблему арбитража, которую мы обсуждали ранее
- Утверждая, что в конце всех сделок не должно быть токенов, которые необходимо продавать, мы превращаем проблему маршрутизации в проблему арбитража
- Это ограничение проверяет, что каждый токен в пси (net network trade) больше или равен 0. Это означает, что в конце всех сделок для каждого токена мы получили этот токен
Решение задачи выпуклой оптимизации
Теперь, когда у нас есть целевая функция и ограничения, мы можем решить задачу выпуклой оптимизации
Целевая функция и ограничения, эффективно обрамляющие проблему, математически представлены в выступлении Тео с использованием следующих обозначений
- Наша целевая функция, которая представляет «Net Network Trade» в долларах США.
- Наши торговые ограничения для каждого CFMM от 1 → m
- Действительные значения для сумм сделок во всех CFMM (обратите внимание, что они не определены явно в коде)
- Арбитражное ограничение, (cT)Ψ — наша целевая функция, где (cT) — рыночная стоимость токенов. Арбитражное ограничение представляет собой функцию индикатора/штрафа. Когда Ψ >= 0, оно преобразуется в бесконечность, в противном случае оно превращается в 0. Поскольку все, где Ψ >= 0, приведет к отрицательной бесконечности, это гарантирует, что если это условие не будет выполнено, перестановка не будет выбрана (см. Доклад Тео)
Решение оптимизации дает нам общую стоимость Net Network Trade. Просматривая «лямбды» и «дельты» каждого пула CFMM, мы также можем увидеть, какие сделки были совершены, чтобы получить этот результат
Что cvxpy (cp) делает под капотом для решения этой проблемы, это отдельная статья, поэтому мы не будем в это углубляться. Если вам интересно, я рекомендую начать здесь, это документация для CFMMRouter.jl, оптимизатора, написанного для этой проблемы
Для контекста этой статьи важно то, что у нас есть инструмент, решающий задачи выпуклой оптимизации, и теперь мы знаем, как программно формулировать наши вопросы
После вызова решения нам будет предоставлен список сделок, которые, как известно, являются сделками, которые приводят к оптимальному арбитражу. Одна проблема, которая у нас все еще есть, заключается в том, что мы не знаем, в каком порядке их выполнять
Execution Ordering
Чтобы начать арбитраж, для первой сделки требуется некоторый капитал (даже если это flashloan). Таким образом, наша цель при заказе сделок должна состоять в том, чтобы свести к минимуму необходимый стартовый капитал
Здесь мы собираемся минимизировать стоимость всех токенов в долларах США, чтобы начать торговлю. Могут быть ситуации, когда у вас есть токен x, и вы хотите взвесить его по отношению к этому токену
Количество перестановок для сделки равно n! (n факториал), где n — количество сделок
В нашем случае у нас 5, поэтому у нас есть 5 х 4 х 3 х 2 х 1 = 120 перестановок
Чтобы не усложнять задачу, мы будем перебирать торговые ордера, чтобы определить наилучший ордер
Код относительно прост и в конечном итоге просто перебирает каждую перестановку и ведет подсчет того, сколько каждого токена потребовалось, с учетом любых токенов, которые были получены в предыдущих сделках
Вы можете посмотреть полный код arbitrage.py и поэкспериментировать с ним самостоятельно. Я же от себя добавил несколько операторов печати и комментариев вокруг кода
Вот вывод кода, определяющего сделки, порядок их выполнения, минимальное количество токенов, необходимое для запуска сделки, и общее количество токенов, полученных от арбитража
