🦄

Uniswapが1200ものアドレスにトークン配布した方法が賢すぎるのでメモ

4 min read

仕組みとしては、マークルツリーを使った物。

これだけで察しのいい人は気づいてしまったかもw

https://github.com/Uniswap/merkle-distributor

どうやったか?

  1. Uniswapを利用した人のアドレスを集める
  2. 最初のコミュニティ配布時にアドレスが1200個だったらしい
  3. マークルツリーを使って1200のアドレスを圧縮してマークルルートを計算する
  4. マークルルートだけをデプロイ時にコントラクトに入れておく
  5. ノード、ツリー、ルートを渡して、検証する
// https://github.com/Uniswap/merkle-distributor/blob/master/contracts/MerkleDistributor.sol#L34-L47
    function claim(uint256 index, address account, uint256 amount, bytes32[] calldata merkleProof) external override {
        require(!isClaimed(index), 'MerkleDistributor: Drop already claimed.');

        // Verify the merkle proof.
        bytes32 node = keccak256(abi.encodePacked(index, account, amount));
        require(MerkleProof.verify(merkleProof, merkleRoot, node), 'MerkleDistributor: Invalid proof.');

        // Mark it claimed and send the token.
        _setClaimed(index);
        require(IERC20(token).transfer(account, amount), 'MerkleDistributor: Transfer failed.');

        emit Claimed(index, account, amount);
    }

// https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/cryptography/MerkleProof.sol
...
  function verifyProof(bytes _proof, bytes32 _root, bytes32 _leaf) public pure returns (bool) {
    // Check if proof length is a multiple of 32
    if (_proof.length % 32 != 0) return false;

    bytes32 proofElement;
    bytes32 computedHash = _leaf;

    for (uint256 i = 32; i <= _proof.length; i += 32) {
      assembly {
        // Load the current element of the proof
        proofElement := mload(add(_proof, i))
      }

      if (computedHash < proofElement) {
        // Hash(current computed hash + current element of the proof)
        computedHash = keccak256(computedHash, proofElement);
      } else {
        // Hash(current element of the proof + current computed hash)
        computedHash = keccak256(proofElement, computedHash);
      }
    }

マークルツリー関係ないけど、めちゃくちゃテクい圧縮もしているw脱帽w

// https://github.com/Uniswap/merkle-distributor/blob/c3255bfa2b684594ecd562cacd7664b0f18330bf/contracts/MerkleDistributor.sol#L12-L32
    mapping(uint256 => uint256) private claimedBitMap;

    function isClaimed(uint256 index) public view override returns (bool) {
        uint256 claimedWordIndex = index / 256;
        uint256 claimedBitIndex = index % 256;
        uint256 claimedWord = claimedBitMap[claimedWordIndex];
        uint256 mask = (1 << claimedBitIndex);
        return claimedWord & mask == mask;
    }

    function _setClaimed(uint256 index) private {
        uint256 claimedWordIndex = index / 256;
        uint256 claimedBitIndex = index % 256;
        claimedBitMap[claimedWordIndex] = claimedBitMap[claimedWordIndex] | (1 << claimedBitIndex);
    }

これのどこがすごいのか?

  • マークルツリーを使って、コントラクトのストレージを32byteまでに圧縮している
    • 素人がこれを実装しようとすると mapping(address => bool)とかで表現して、24kbとかストレージコスト使ってしまう(1/750も節約できてる)
  • どんだけアドレスが増えても同じコストで検証可能
  • Ethereumはストレージコストが高い
    • calldata(関数の引数)は比較的安いので、リーフを全部外に出してしまうってのは大アリ

いくら節約できたのか?

ガバガバフェルミ推定で適当に出す。

2020年 9月頭のは平均 120Gweiぐらいだったみたい。

素直にERC20であるUniを1200アドレスに送金した場合を考える

当時のEth価値の価値に換算するために20%かける。
1200 address * $14 * 20% = $3,360

$3,360はえぐい!

コントラクトで利用者に引出させる

多分これが、Token Distributorのコントラクトが作られた時のtx。

https://etherscan.io/tx/0x1d80567e3e5946d391a72125f57f203732f8dd706ce6007e4a729a592b8624cd

当時のガス代だとコントラクトをデプロイするのにかかったのは $33!!!安い!

利用者全員のガス代を考えると、$12ぐらいでclaimできるみたいなので、
$12 * 1200 = $14,400
という感じで、全員のコストでいうと割高になってしまう。

まあ、これの何が大事って、プラットフォームが大金を用意せずともなんとかなるってところですね。

まとめ

Uniswapは頭を使って、なるべく少ないコストでトークンを配布した!
節約金額でいうとUniswapは $3,327つまり、35万円ぐらい節約できたわけです。
賢い!

参考

https://github.com/Uniswap/merkle-distributor