Современная реализация пулов ликвидности. Дерево ликвидности Azuro

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

Для начала.

Пулы ликвидности – это смарт-контракты, содержащие заблокированные крипто-токены, которые были предоставлены пользователями платформы. Они самоисполняются и не нуждаются в посредниках, чтобы заставить их работать. Они поддерживаются другими частями кода, такими как автоматизированные маркет-мейкеры (AMM) , которые помогают поддерживать баланс в пулах ликвидности с помощью математических формул.

За предоставляемые криптоактивы провайдеры ликвидности получают долю от торговых комиссий. Или токены протокола.

Реализация пула ликвидности в беттинг-протоколе.

Давайте немного погрузимся в беттинг.

Есть conditions — элементарное событие, на которое можно сделать скидку (да/нет или другой простой вариант). Conditions генерят определенную комиссию, все это заливается в пул ликвидности. Прибыль распределяется между провайдерами ликвидности, в соответствии с их долей.

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

Самое простое решение — просто считать, кто и в какой condition положит деньги. Но в этом случае приходится хранить данные про каждого холдера депозита: какую сумму он внес и когда, а потом каким-то образом это все синхронизировать. Явно, что это не будет работать на больших данных.

Что придумали.

Есть такая структура данных — дерево отрезков. Она позволяет достаточно быстро выполнять математические операции внутри массива. Операции могут быть разные: найти большее или меньшее значение, их произведения, или, как в нашем случае, найти сумму.

Дерево следует заполнять, начиная с листьев, корневые значения показывают сумму. Если нужно посчитать сумму, например, со второго элемента по шестой: мы можем смотреть по родителям листков и таким образом можно быстрее посчитать. С ростом элементов эффективность сразу заметна такой системы.

Работает эта структура данных за О-большое от логарифма.

Навигация по дереву.

Дерево удобнее нумеровать не с 0, а с 1. Тогда мы получим удобную систему: у нас всегда левый ребенок — родитель, умноженный на два. А правый — родитель, умноженный на два + ребенок. Четные индексы — слева, правые индексы — нечетные. Легко подниматься по дереву вверх.

В этом примере четыре листочка — четыре депозита ликвидности. При такой структуре, максимум депозитов в пул ликвидности — четыре. Azuro использует около триллиона листочков. И это не требует много GAS fee.

Как работают механизмы в дереве.

Первый провайдер заливает $100 — мы записываем его в четвертый листик, после чего он попадает во второй, а потом и в первый. Второй провайдер, который внес $200, проделывает такой же путь. После этого в первом листике становится $300.

nodeAddLiquidity(100$)
+--------------------------------------------+
|                    1 (100$)                |
+------------------------+-------------------+
|         2 (100$)       |         3         |
+-------------+----------+---------+---------+
|   4 (100$)  |     5    |    6    |    7    |
+-------------+----------+---------+---------+
     +100$

nodeAddLiquidity(200$)
+--------------------------------------------+
|                    1 (300$)                |
+------------------------+-------------------+
|         2 (300$)       |         3         |
+-------------+----------+---------+---------+
|   4 (100$)  | 5 (200$) |    6    |    7    |
+-------------+----------+---------+---------+
                  +200$

На каждый condition мы отправляем некоторое подкрепление коэффициентов. В любом бизнесе есть потребность гарантировать выплаты. Поэтому мы можем брать ассеты из пула ликвидности. Но мы делаем такое «ленивое» обновление, не достаем средства из каждого листочка, а забираем из полных корневых элементов (второго и первого листочка). При выводе ликвидности важно запомнить последний полный элемент. Просто нужно хранить его и итерировать с каждым обновлением ликвидности.

remove(30$)
+--------------------------------------------+
|                    1 (270$)                |
+------------------------+-------------------+
|         2 (270$)       |         3         |
+-------------+----------+---------+---------+
|   4 (100$)  | 5 (200$) |    6    |    7    |
+-------------+----------+---------+---------+

Чтобы избежать обмана, когда во время активного condition, кто-то может внести большой объем ликвидности — мы можем обновить только его родителя в дереве.

addLimit(15$, 5)
+15$  [4, 5]
+--------------------------------------------+
|                    1 (585$)                |
+------------------------+-------------------+
|         2 (285$)       |    3 (300$)       |
+-------------+----------+---------+---------+
|    4 (100$) | 5 (200$) | 6 (300$)|    7    |
+-------------+----------+---------+---------+

В случае, когда протокол возвращает прибыль — он передает сумму, которую возвращает и последний полный элемент. Например, если это 5, мы можем понять, что это был правый (нечетный) ребенок, значит он — последний (так как у родителя всего два листочка). Тогда мы обновляем только верхнего родителя. При выводе листки тоже не обновляются, также вывод вычисляется через значения родителя. Выгрузка из газ-репортера, при триллионе элементов показывает всего 300 000 газа, что примерно, как swap.

nodeWithdraw(5) 
+--------------------------------------------+
|                     1 (300$)               |
+------------------------+-------------------+
|           2 (0$)       |    3 (300$)       |
+-------------+----------+---------+---------+
|    4 (0$)   |  5 (0$)  | 6 (300$)|    7    |
+-------------+----------+---------+---------+
                  -190$