Стейкинг. Расчет наград. Часть 1

Но как рассчитать награду если таких пользователей очень много и пропорции в течении времени постоянно изменяются?

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

Вместо того, чтобы использовать механизм push-based, который сразу разделяет и распределяет вознаграждения между всеми участниками, разработанный алгоритм, хранит суммы вознаграждений и позволяет участникам произвольно снимать их в режиме "pull-based".

Рассмотрим только одно действие депозита на один адрес и только полное снятие. Дополнительные депозиты на существующий адрес можно моделировать как два депозита на разные адреса, а частичные снятия можно моделировать двумя более простыми операциями: полным снятием и новым депозитом.

Вознаграждение, заработанное участником j за его депозит stake_j, представляет собой сумму пропорциональных вознаграждений, извлеченных им из всех событий распределения, которые произошли во время действия депозита:

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

Предполагая, что stake_j был внесен в момент времени t1 и затем снят в момент времени t2 > t1, мы можем использовать массив St для вычисления общего вознаграждения для участника j:

или

Это позволяет вычислять вознаграждение для каждого события снятия в постоянное время O(1), за счет хранения всего массива St в памяти контракта.

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

Мы будем использовать mapping S0[j], чтобы сохранить значение S на момент времени, когда участник j внес депозит. Когда участник j снимет депозит, его общее вознаграждение можно вычислить, используя последнее значение S (на момент снятия) и снимок S0[j]:

Эта стратегия позволяет достичь как оптимальности по времени, так и по памяти, так как для N участников требуется O(N) памяти для отслеживания и mappinga значений S0, и реестра стейков.

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

Теперь реализуем этот алгоритм на Solidity. В контракте предоставлено 3 метода:

1. deposit - для добавления токенов в стейкинг.
2. distribute - для распределения вознаграждения всем участникам.
3. withdraw - для снятия застейканных токенов и накопленного вознаграждения.

pragma solidity 0.8.20;

contract ScalableRewardDistribution {
   
    event Deposit(address addr, uint256 value);
    event Distribute(uint256 value);
    event Withdraw(address addr, uint256 value);
    
    uint256 public T; // Сумма всех дипозитов
    uint256 public S; // Текущий коэффициент стейкинга
    uint256 public balance; // Баланс токенов для вознаграждения

    mapping (address => uint256) public stake; // Количество застейканных токенов
    mapping (address => uint256) public S0; // Коэффициент стейкинга в момент депозита на адрес

    constructor() {
        T = 0;
        S = 0;
    }

    function deposit(address _address, uint256 _amount) public {
        require(S0[_address] == 0, "withdraw before deposit");
        stake[_address] = _amount;
        S0[_address] = S;
        T = T + _amount;
        emit Deposit(_address, _amount);
    }

    function distribute(uint256 _reward) public {
        require(T != 0, "no active stake deposits");
        require(_reward > T, "reward too small to distribute");
        S = S + _reward / T;
        balance = balance + _reward;
        emit Distribute(_reward);
    }

    function withdraws(address _address) public {
        uint256 deposited = stake[_address];
        require(deposited > 0, "nothing to withdraw");
        uint256 reward = deposited * (S - S0[_address]);
        T = T - deposited;
        stake[_address] = 0;
        balance = balance - reward;
        emit Withdraw(_address, deposited+reward);
    }
}

Источники:

Batog. Scalable Reward Distribution on the Ethereum Blockchain