Этот проект представляет подход «дерева отрезков» для учета пополнений, изъятий ликвидности и справедливого распределения прибыли/проигрышей для игрового протокола.
Дерево отрезков - это структура данных, позволяющая эффективно находить сумму и менять данные в элементах отрезка. Дерево отрезков используется для учета предоставленной ликвидности. Каждый депозит представлен в виде отдельного элемента "листа" на дереве отрезков. Листы - самые удаленные элементы в дереве отрезков. Два листа (левый и правый) объединяются в один узел предок. Два узла (левый и правый) объединяются в узел предка и так далее до единого корня всего дерева отрезков. Корневой узел дерева отрезков представляет собой наиболее актуальное значение суммы нижних элементов (листьев). Корень не имеет предков, а листья не имееют потомков.
В задаче учета ликвидности корневой узел содержит наиболее актуальную ликвидность.
Все узлы дерева ликвидности записаны как элементы массива. Для хранения данных в элементах K, необходим массив размерностью K*2+1. Элемент номер 0 не используется, корневой узел имеет номер 1, первый лист имеет номер K Потомки корневого узла: 2 - левый потомок 3 - правый потомок
Навигация внутри дерева ликвидности производится через соотношение номера узлов, левый потомок узла X имеет номер 2*X , правый потомок имеет номер 2*X+1.
Пример дерева ликвидности для хранения 4-х элементов
+--------------------------------------------+
| 1 (top node) |
+------------------------+-------------------+
| 2 | 3 |
+-------------+----------+---------+---------+
| 4 (leaf) | 5 | 6 | 7 |
+-------------+----------+---------+---------+
При каждом добавлении ликвидности производится:
- инициализацией следующего по порядку листа (следующего не использованного).
- добавление суммы в предка листа
- добавления суммы в вышестоящего предка и так далее до корня дерева ликвидности, рекурсивно.
За добавление ликвидности в контракте отвечает метод function nodeAddLiquidity(uint128 amount) public
Таким образом после добавления, будет добавлена сумма amount
в лист и во все ноды-предки, включая корневой узел.
Инициализация листа может быть сделана только один раз.
В дальнейшем сумма в листе может только меняться в результате распределения прибыли/убытка или вывода ликвидности (полного) из листа.
Пример состояния дерева ликвидности после добавления ликвидности, обновились узлы 4, 5, 2, 1
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$
Для обеспечения "игры", можно "брать" ликвидность, согласно текущего состояния дерева ликвидности: текущей суммы в корневом узле 1 и для дальнейшего справделивого распределения необходимо "запомнить" последний актуальный лист.
Взятие ликвидности происходит методом function remove(uint128 amount) public
.
Метод remove
использует "ленивое обновление" нижестоящих узлов, таким образом, что если обновляемый список листов полностью лежит в родительском узле, то обновляется только данный родительский узел и дальнейшие изменения дочерних узлов не производятся и откладывается.
Пример состояния дерева ликвидности после взятия ликвидности для "игры" (10$), обновились узлы 1 и 2 , т.к. изменения касаются только списка листов [4, 5], и весь список входит в узел 2, нужно обновить только сумму узла 1 и 2
remove(30$)
+--------------------------------------------+
| 1 (270$) |
+------------------------+-------------------+
| 2 (270$) | 3 |
+-------------+----------+---------+---------+
| 4 (100$) | 5 (200$) | 6 | 7 |
+-------------+----------+---------+---------+
после этого, например, произошло добавление ликвидности (в следующий лист 6), обновились узлы 6, 3, 1
nodeAddLiquidity(300$)
+--------------------------------------------+
| 1 (570$) |
+------------------------+-------------------+
| 2 (270$) | 3 (300$) |
+-------------+----------+---------+---------+
| 4 (100$) | 5 (200$) | 6 (300$)| 7 |
+-------------+----------+---------+---------+
+300$
Происходит с указанием суммы возвращения и номера листа, указывающего диапазон распределения возвращенной суммы от первого элемента до актуального на момент "взятия ликвидности".
Производится методом function addLimit(uint128 amount, uint48 leaf) public
В примере, сначала обновляются узлы 4, 5 согласно предыдущего измененеия (remove(30$)), затем обновляются узлы 1, 2. Данные в 4, 5 не меняются, т.к. 4, 5 входят в узел 2 и ленивое обновление остановилось на 2
addLimit(15$, 5)
+15$ [4, 5]
+--------------------------------------------+
| 1 (585$) |
+------------------------+-------------------+
| 2 (285$) | 3 (300$) |
+-------------+----------+---------+---------+
| 4 (100$) | 5 (200$) | 6 (300$)| 7 |
+-------------+----------+---------+---------+
Производится методом function nodeWithdraw(uint48 leaf) public
Для вывода сначала производится:
- поиск "самого обновленного предка" от листа
- обновление (актуализация) данных по сумме в листе от "самого обновленного предка", таким образом в листе обновится сумма
- затем выводится полностью ликвидность из листа, с обновлением всех узлов-предков от листа до корня.
nodeWithdraw(4)
+--------------------------------------------+
| 1 (490$) |
+------------------------+-------------------+
| 2 (190$) | 3 (300$) |
+-------------+----------+---------+---------+
| 4 (0$) | 5 (200$) | 6 (300$)| 7 |
+-------------+----------+---------+---------+
-95$
nodeWithdraw(5)
+--------------------------------------------+
| 1 (300$) |
+------------------------+-------------------+
| 2 (0$) | 3 (300$) |
+-------------+----------+---------+---------+
| 4 (0$) | 5 (0$) | 6 (300$)| 7 |
+-------------+----------+---------+---------+
-190$
- в пул добавлено 10000$ ликвидити провайдеров Алисы и Боба
- создано игровое событие, использущее существующую ликвидность (10000$)
- новый ликвидити провайдер (Кларк) добавляет 1000$ в пулл
- событие завершается:
- игроки выиграли 2000$, из пула вычитается 2000$ и т.к. игровое событие использовало только ликвидность Алисы и Боба (10000$), на момент создания события, то вычитаемая сумма 2000$ вычитается пропорционально из депозитов Алисы и Боба
- игроки проиграли 2000$ и пул получает 2000$ и т.к. игровое событие использовало только ликвидность Алисы и Боба (10000$), на момент создания события, то сумма прибыли 2000$ начисляется пропорционально на депозиты Алисы и Боба
- в обоих случая депозит Кларка не участвует и остается не изменным
подробности в тесте There are 10000$ of liquidity, Bob added 1000$, remove 2000$ lose of leaves 4, 5, Clarc not affected
- в пул добавлено 15000$ ликвидити провайдеров Алисы, Боба и Кларка (5000$)
- создано игровое событие, использущее существующую ликвидность (15000$)
- событие завершается:
- игроки выиграли 3000$, из пула вычитается 3000$ и т.к. игровое событие использовало ликвидность Алисы, Боба и Кларка (15000$), на момент создания события, то вычитаемая сумма 3000$ вычитается пропорционально из депозитов Алисы, Боба и Кларка
- игроки проиграли 3000$ и пул получает 3000$ и т.к. игровое событие использовало ликвидность Алисы, Боба и Кларка (15000$), на момент создания события, то сумма прибыли 3000$ начисляется пропорционально на депозиты Алисы, Боба и Кларка
- в обоих случая депозит Кларка участвует:
- при потере пула, депозит Кларка будет 5000$ - 1000$ = 4000$
- при заработке пула, депозит Кларка будет 5000$ + 1000$ = 6000$
подробности в тесте There are 15000$ of liquidity, Bob added 1000$, remove 3000$ lose of leaves 4, 5, 6. Clarc affected