note: Scalable Reward Distribution algorithm

มาดู optimized algorithm ในการคำนวณ reward จากการ stake กัน

คำถาม

การคำนวณ reward ของ user ที่ stake เขียน code ยังไง ?

ก่อนอื่นต้องมาดู process การแจก stake reward กันก่อน

เช่น

ถ้า Alice stake 40 LP token

Bob stake 60 LP token

ถ้าแจก Cake token เป็น reward ให้กับคนที่มา stake ในเวลานั้นๆ

โดยจะแจก R token ต่อวินาที

ซึ่งถ้า Alice stake คนเดียว คงจะได้ไปเต็มๆ

แต่ดันมี Bob มา stake ด้วย

จึงต้องแบ่ง Reward กันตามสัดส่วน ตามสูตร

โดย R คือ จำนวน reward token ที่แจกในเวลา t นั้นๆ

l(t) = จำนวน staked token ทั้งหมดของ user คนนั้น ณ เวลา t นั้นๆ

L(t) = จำนวน staked token ทั้งหมดใน pool ณ เวลา t นั้นๆ

โอเค เราได้สูตร version แรกมาแล้ว ซึ่งสูตรนี้จะ work ถ้าทุกคน stake ตอน pool เปิด

แต่ถ้า user เพิ่งมา stake ณ เวลา t0 แล้ว claim reward ( aka การถอน stake ) ในตอนเวลา t1

แสดงว่า user จะได้ reward ตั้งแต่เวลา t0 — t1 รวมกัน (เช่น ถ้าการ คิด reward เป็นต่อวินาที แล้ว stake ไป 3 วินาที ก็จะได้ reward 3 ครั้ง)

ดังนั้นจาก reward ที่ user จะได้ ณ เวลา t1 คือ

โอเค มาลองเขียน contract version นี้กันก่อน จะได้ code การคิด reward ประมาณนี้

    function distribute() public {
        uint256 rewardPerSecond = 1e18;
        uint256 t1 = block.timestamp;
        for (uint256 i = 0; i < userList.length; i++) {
            address user = userList[i];
            uint256 t0 = startPointCaculateUserReward[user];
            for (uint256 t = t0; t <= t1; t++) {
                uint256 rewardThisSecond = (rewardPerSecond *
                    userStakeAmount[user]) / totalStakedAmount;
                userAccumulatedReward[user] += rewardThisSecond;
            }
            startPointCaculateUserReward[user] = t1 + 1;
        }
    }

จะเห็นได้ว่าอันนี้มี O(n) ซึ่งเปลืองค่า gas มากๆ (n = ลูป t)

แล้วเราจะแก้ปัญหานี้ยังไง ?

จากสูตร

จะเห็นได้ว่าสูตรนี้เป็นการคำนวณ reward ตาม จำนวนเหรียญที่ user ถือ (l(t))

แต่ถ้าเรา assume ว่าค่า l ในช่วง จาก t0 ไปยัง t1 เท่ากันตลอด (เมื่อมีการเปลี่ยนแปลงค่า l โดยการ deposit/withdraw จะทำการ distribute ให้เสร็จก่อนคิด reward ใหม่) จะได้ว่า

โดยที่ค่า sum จาก t0 ไปยัง t1 สามารถแปลงได้เป็น

โดยที่เมื่อเรากำหนดว่า

จะได้ว่า reward ของ user ตั้งแต่เวลา t0 ถึง t1 เท่ากับสมการ

นั่นเอง

แล้วสมการนี้ช่วยเรื่อง O(second) ยังไง ?

จากสมการนี้เราจะสามารถคำนวณ reward ของ user ได้ด้วย O(1)

เนื่องจากการคำนวณ reward ไม่จำเป็นจะต้องวนลูปทุก second แต่สามารถคำนวณ reward จาก checkpoint ล่าสุดที่ user claim reward ไปแล้วได้เลย

จัวอย่างเช่น code ของ uniswap pool ที่เมื่อมีการ stake เข้ามาจะทำการ

1. คำนวณค่า s (uniswap เรียกค่านี้ว่า rewardPerTokenStored)

function stake(uint256 amount) public updateRewardPerToken {
        ...
}

    modifier updateRewardPerToken {
        getReward();
        _;
    }

function getReward() public {
        uint256 reward = earned(msg.sender);
        ...
    }

    function earned(address account) public view returns(uint256) {
        return balanceOf(account).mul(
            rewardPerToken().sub(userRewardPerTokenPaid[account])
        ).div(1e18);
    }

    function rewardPerToken() public view returns(uint256) {
        return rewardPerTokenStored.add(
            totalSupply() == 0 ? 0 : (now.sub(lastUpdateTime)).mul(REWARD_RATE).mul(1e18).div(totalSupply())
        );
    }

โดยเราจะพบว่า uniswap เอาค่า R เข้าไปคูณใน S เลย ดังนั้นจะได้สูตร

S=R/L แทน 1/L นั่นเอง

2. คำนวณ reward ที่ต้องจ่าย user

โดยเมื่อได้ค่า rewardPerTokenStored มาแล้วจะทำการหา reward ที่ user มีในขณะนี้ด้วยสูตร

l * (S1-S2)

ตาม code

function earned(address account) public view returns(uint256) {
        return balanceOf(account).mul(
            rewardPerToken().sub(userRewardPerTokenPaid[account])
        ).div(1e18);
    }

3. จ่าย reward ให้กับ user แล้วจำไว้ว่าเคยจ่ายไปเท่าไหร่แล้ว

function getReward() public {
        uint256 reward = earned(msg.sender);

        rewardPerTokenStored = rewardPerToken();
        userRewardPerTokenPaid[msg.sender] = rewardPerTokenStored;
        lastUpdateTime = now;

        if (reward > 0) {
            snx.safeTransfer(msg.sender, reward);
            emit RewardPaid(msg.sender, reward);
        }
    }

4. จากนั้นจึงทำไปทำ logic ของการ stake เหรียญต่อไปนั่นเอง

function stake(uint256 amount) public updateRewardPerToken {
        _mint(msg.sender, amount);
        uni.safeTransferFrom(msg.sender, address(this), amount);
        emit Staked(msg.sender, amount);
    }

เช่นเดียวกัน ในการ withdraw ก็จะทำการคิดเรื่อง reward ให้เสร็จก่อนไปทำ withdraw เช่นกัน

จะเห็นได้ว่าการคำนวณ reward แบบนี้ใช้แค่ O(1) เท่านั้น ซึ่งทำให้เป็นการคำนวณแบบที่เหมาะกับ on chain นั่นเอง

โอเค คร่าวๆประมาณนี้ จริงๆจะมี paper ที่อธิบาย algorithm ที่ว่ามานี้ด้วย

และยังมี contract ที่คำนวณ reward ให้แต่ละ pool ไม่เท่ากันด้วย (จากก้อน reward เดียวกัน) เช่น

sushiswap/contracts/MasterChef.sol at 271458b558afa6fdfd3e46b8eef5ee6618b60f9d ·…

และยังมีการคำนวณ reward แบบ non fungiable ด้วย !

Liquidity Mining on Uniswap v3

แต่วันนี้เอาไว้แค่นี้ก่อนดีกว่า

fyi: เหมือนยังอธิบายไม่เคลียร์เท่าไหร่แหะ จริงๆจะมีเรื่อง push vs pull based solution ด้วย ถ้างงลองอ่าน paper ไม่ก็ดูคลิป https://www.youtube.com/watch?v=6ZO5aYg1GI8 ก็ได้ครับ

Referrences

How to become a smart contract auditor

Liquidity Mining on Uniswap v3

sushiswap/contracts/MasterChef.sol at 271458b558afa6fdfd3e46b8eef5ee6618b60f9d ·…

First commit · k06a/Unipool@e4bdb0a

https://uploads-ssl.webflow.com/5ad71ffeb79acc67c8bcdaba/5ad8d1193a40977462982470_scalable-reward-distribution-paper.pdf