Huff langで清算コントラクトを作る

## ガス最適化を追求する
#### きっかけ
Ethereumで清算ボットやアービトラージボットが跋扈している様子を見ていると、よくできたボットには細かなガス節約の工夫が施されていることが分かります。どこまでガスやコントラクトサイズを削れるか自分を試してみたくなりました。
スタックとメモリを低レベルで操作できる[**Huff lang**](https://docs.huff.sh)でシンプルな清算ボットを作ります。担保不足のアカウントはお仕置きよ⭐️

## Huff langとは

> Huffは、Ethereum Virtual Machine（EVM）上で動作する高度に最適化されたスマートコントラクトを開発するために設計された低レベルのプログラミング言語です。HuffはEVMの内部構造を隠蔽せず、代わりにそのプログラミングスタックを開発者に公開し、手動で操作できるようにしています。

## EVMの基本
Solidity にある程度慣れていて、コントラクト、ステート、外部呼び出しなど、Ethereum開発の基本を理解していることを前提にしています。こちらが参考になります。
> https://docs.huff.sh/tutorial/evm-basics/#technical

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/902476/ea8df6a2-bfac-aad0-9ca4-028a8c17a571.png)

## 清算ボットの仕様
清算者は清算されるアカウントの代わりに負債を返済し、報酬として担保の一部を受け取ります。

1. 対象とするレンディング: Aave V3
1. ボットコントラクトは返済するトークンをあらかじめ保有しているとする。
2. オフチェーン側からボットを叩く時に、返済するトークンとその量を指定する。
2. ボットコントラクトから任意のトークンを取り出せるようにする。

## ピュアなSolidityで実装する
清算を行うにはAaveV3の`liquidationCall()`関数を叩くだけです。引数はオフチェーン側から渡せるようにしておきます。
ガスをなるべく節約しつつSolidityで実装します。

ガスを節約するために行ったこと
 - 所有者アドレスの記録に`SSTORE`オペコード(ストレージ)使わない。所有者アドレスは定数にする。
     - 理由：ストレージへの読み書きは最も高価なオペレーションなので、回避する。
 - `require(...)`ではなく`revert Error()`を使う。
     - 理由：カスタムエラーはエラーメッセージに文字列型を使わず4byteのセレクタを使うため、デプロイコストとランタイム時のガスコストが減る。
 - `unchecked{...}`でunderflow/overflowチェックを外す。
 - `payable`にする。
   - 理由：`msg.value`がゼロかどうかをチェックする処理がなくなる分、ランタイム時のガスコストが減る。
 - 微量のトークンをコントラクトに残して残高を0にしない。
   - 理由：ストレージスロットをzeroからnon-zeroに書き換えることはnon-zeroからnon-zeroへ更新することよりもずっと高価である。そのスロットがあとでnon-zeroの値に更新される可能性があるなら、あえてzeroにリセットしない方がいい。

```solidity
// SPDX-License-Identifier: GPL-3.0-or-later
pragma solidity ^0.8.15;

interface IERC20Like {
    function balanceOf(address account) external returns (uint256);
    function transfer(address to, uint256 value) external returns (bool);
    function approve(address spender, uint256 value) external returns (bool);
}

/// @title Aave V3 Pool 
interface IPoolLike {
    /**
     * @notice Function to liquidate a non-healthy position collateral-wise, with Health Factor below 1
     * - The caller (liquidator) covers `debtToCover` amount of debt of the user getting liquidated, and receives
     *   a proportionally amount of the `collateralAsset` plus a bonus to cover market risk
     * @param collateralAsset The address of the underlying asset used as collateral, to receive as result of the liquidation
     * @param debtAsset The address of the underlying borrowed asset to be repaid with the liquidation
     * @param user The address of the borrower getting liquidated
     * @param debtToCover The debt amount of borrowed `asset` the liquidator wants to cover
     * @param receiveAToken True if the liquidators wants to receive the collateral aTokens, `false` if he wants
     * to receive the underlying collateral asset directly
     *
     */
    function liquidationCall(
        address collateralAsset,
        address debtAsset,
        address user,
        uint256 debtToCover,
        bool receiveAToken
    ) external;
}

library SafeERC20 {
    /// @dev relaxing the requirement on the return value: the return value is optional

    // CODE 5: safeTransfer failed
    function safeTransfer(IERC20Like token, address to, uint256 value) internal {
        (bool s,) = address(token).call(abi.encodeWithSelector(IERC20Like.transfer.selector, to, value));
        require(s, "5");
    }
}

contract GrimReaper {
    using SafeERC20 for IERC20Like;

    error OnlyOwner();

    address internal constant OWNER = 0x0000000000000000000000000000000000000003;

    /// @dev The Aave V3 Pool on Optimism
    address internal constant POOL = 0x794a61358D6845594F94dc1DB02A252b5b4814aD;

    /// TODO: change this to the fallback function
    function execute(address collateralAsset, address debtAsset, address user, uint256 debtToCover) external payable {
        if (msg.sender != OWNER) revert OnlyOwner();
        IERC20Like(debtAsset).approve(POOL, debtToCover); // this may not properly work for some kind of tokens like USDT
        IPoolLike(POOL).liquidationCall(collateralAsset, debtAsset, user, debtToCover, false);
    }

    /// @notice Receive profits from contract
    function recoverERC20(address token) public {
        if (msg.sender != OWNER) revert OnlyOwner();
        // ignore overflow/underflow check
        unchecked {
            // left dust in the contract for gas saving
            IERC20Like(token).safeTransfer(msg.sender, IERC20Like(token).balanceOf(address(this)) - 1);
        }
    }
}
```

## さらなる最適化を試みる
 1. tx実行時に渡すデータ(コールデータ)のサイズを小さくする。
 2. Huffを使い手動でメモリとスタックを管理する。

#### ABIエンコーディング
標準のABIエンコーディングではtxのデータ部分は`関数セレクタ＋ABIエンコーディングされた引数`の形式でエンコーディングされます。関数セレクタは`execute(address,address,address,uint256)`をkeccake256でハッシュした最初の4bytes (`0x239aee06`)です。

```
> cast calldata "execute(address,address,address,uint256)" 0xCe71065D4017F316EC606Fe4422e11eB2c47c246 0x794a61358D6845594F94dc1DB02A252b5b4814aD 0x6312a91f7390CAD51772676474a43f9AE94dd60e 1000

0x239aee06
000000000000000000000000ce71065d4017f316ec606fe4422e11eb2c47c246
000000000000000000000000794a61358d6845594f94dc1db02a252b5b4814ad
0000000000000000000000006312a91f7390cad51772676474a43f9ae94dd60e
00000000000000000000000000000000000000000000000000000000000003e8
```
標準のABIエンコーディング方法では32bytes未満の値は32bytesになるように`0`がpaddingされます。さらに、`uint256`型は大きすぎて左側に無駄なゼロがたくさん並んでしまいます。

次の工夫をします。
 1. 関数セレクタを削除して、清算のエントリーポイントを`fallback`関数にする。
 1. 非標準ABIエンコーディング(`abi.encodePacked`)を使って無駄なゼロをなくす。(32bytes未満の値でもpaddingしない)
 1. `uint256`の代わりに`uint128`を使う。

## Huffで実装する
#### mainマクロを定義する
`MAIN`マクロはHuffコントラクトのエントリーポイントの役割があります。コントラクトへの呼び出しは、MAINから開始されます。
大まかな流れとしては、どの関数を呼び出すのかを見つけるため、関数セレクタを総当たり的に比較していきます。
1. コールデータから関数セレクタを読み取る。
1. 最初の関数セレクタと比較する。一致したら、そのバイトコード部分へディスパッチする。一致しなかったら次へ
1. 次の関数セレクタと比較する。一致したら、そのバイトコード部分へディスパッチする。一致しなかったら次へ
1. これを総当たり的に繰り返す。
1. 一致する関数セレクタが見つからなかったら、fallback関数で清算処理を実行する。

```haskell
#define function recoverERC20(address) nonpayable returns ()

#define macro RECOVER_ERC20() = takes (0) returns (0) {}
#define macro EXECUTE_LIQUIDATION() = takes(0) returns(0) {}

#define macro MAIN() = takes(0) returns(0) {
    // Get the function selector
    // Identify which function is being called.
    // load 32 bytes starting from position 0 onto the stack (if the calldata is less than 32 bytes then it will be right padded with zeros). 
    // 0xE0 shr right shifts the calldata by 224 bits,
    // leaving 32 bits or 4 bytes remaining on the stack.

    0x00 calldataload 0xe0 shr          // [func_sig]

    // Dispatcher to determine which function to execute
    dup1 __FUNC_SIG(recoverERC20) eq recover_erc20 jumpi    // [selector]
   
    // If no matching selector was found, call the liquidation function
    EXECUTE_LIQUIDATION()

    recover_erc20:
        RECOVER_ERC20()

    0x00 0x00 revert
}
```

まず、コールデータから関数セレクタを読み取ります。`calldataload`オペコードで`msg.data`の先頭から32bytesを読み取りスタックにPUSHします。
```
    0x00 calldataload // [msg.data[:32bytes]]
```
0xE0(224 bits)だけ右シフトして、32bits(4bytes)をスタックに残します。
```
　　 0xe0 shr          // [func_sig]
```
> `calldataload`オペコードはスタックの上から`offset`を取り出して、`msg.data`を`offset`分だけズレた位置から32bytes読み取りスタックにPUSHします。

次の行で`recoverERC20(address)`の関数セレクタ(`0x9e8c708e`)とスタック上の`func_sig`が一致するか比較して、一致したら`recoverERC20`の実装がある箇所へジャンプします。一致しなかった場合は、fallback関数(`EXECUTE_LIQUIDATION()`マクロ)を実行します。

```haskell
    dup1 __FUNC_SIG(recoverERC20) eq recover_erc20 jumpi    // [selector]
```

今のままでは誰でも関数を実行できる状態になっています。ownerだけがコントラクトを呼び出せるように変えましょう。

```haskell
#define constant OWNER = 0x0000000000000000000000000000000000000003 // your address
// Main
#define macro MAIN() = takes(0) returns(0) {
    0x00 calldataload 0xe0 shr          // [func_sig]

    // Verify that the caller is the OWNER
    caller [OWNER] eq iszero error jumpi                     // [selector]
    ...
    error: 
        WAGMI()
}
/// @notice Revert, but still (3, 3) wgmi I guess
#define macro WAGMI() = takes (0) returns (0) {
    0x03 dup1 revert
}
```
Huffでは定数を
```
#define constant OWNER = 0x0000000000000000000000000000000000000003
```
のように定義し、コード中では`[]`で囲うことでアクセスできます。
`caller`オペコードで`msg.sender`を読み取り、`OWNER`と一致しないならエラー実装の部分へジャンプします。

#### コード
ここまでのコード

```haskell
#define function recoverERC20(address) nonpayable returns ()

#define macro RECOVER_ERC20() = takes (0) returns (0) {}
#define macro EXECUTE_LIQUIDATION() = takes(0) returns(0) {}

/// @notice Revert (3, 3)
#define macro WAGMI() = takes (0) returns (0) {
    0x03 dup1 revert
}
#define constant OWNER = 0x0000000000000000000000000000000000000003

#define macro MAIN() = takes(0) returns(0) {
    // pc = 0 there 100% of the time 
    // so its just a way to save a very very small amount of gas (1 gas)
    // Get the function selector
    // load 32 bytes starting from position 0 onto the stack (if the calldata is less than 32 bytes then it will be right padded with zeros). 
    // 0xE0 shr right shifts the calldata by 224 bits,
    // leaving 32 bits or 4 bytes remaining on the stack.
    pc calldataload 0xe0 shr          // [func_sig]

    // Verify that the caller is the OWNER
    caller [OWNER] eq iszero error jumpi                     // [selector]

    // Dispatcher to determine which function to execute
    dup1 __FUNC_SIG(recoverERC20) eq recover_erc20 jumpi    // [selector]
   
    // If no matching selector was found, call the liquidation function
    EXECUTE_LIQUIDATION()

    recover_erc20:
        RECOVER_ERC20()
    error: 
        WAGMI()

    0x00 0x00 revert
}
```

### 清算を実行するマクロを定義する
次に`EXECUTE_LIQUIDATION`マクロに清算処理を実装します。
マクロの定義には引数に受け取るスタックと出力するスタックを記述します。引数はとらないので、`take(0) returns(0)`とします。

#### コールデータをデコードする

```haskell
#define macro EXECUTE_LIQUIDATION() = takes(0) returns(0) {
    // Unpack the calldata
    // calldata is encoded with abi.encodePacked(address collateralAsset,address debtAsset,address user,uint128 debtToCover)
    //                                      // stack: []
    // msg.dataの先頭(オフセット0)から32bytesを読み取りスタックにPUSHする。
    // 0x00 calldataload
    // Stack after operation: [msg.data[:32]]
    // 0x60をスタックにPUSHして、shrで0x60だけ右シフトして`col`を取り出す。
    // 0x60 shr
    // Stack after operation: [col]
    0x00 calldataload 0x60 shr              // [col] - bytes 20
    // msg.dataの14bytesズレた位置から32bytesを読み取り、0x60だけ右シフトしてアドレス型を取り出す。
    0x14 calldataload 0x60 shr              // [debt, col] - bytes 20
    0x28 calldataload 0x60 shr              // [user, debt, col] - bytes 20
    0x3c calldataload 0x80 shr              // [debtToCover, user, debt, col] - uint128
}
```

#### 外部コントラクトを呼び出す
次に、返済するトークンの使用をAaveV3プールに許可するために`call`オペコードで`debtAsset.approve(pool,debtToCover)`を実行します。
`call`オペコードは次のようなスタックの入力をとります。
```
call(gas,to,value,argsOffset,argsSize,retOffset,retSize)
```
|入力|説明|
|---|---|
|gas|送信するガス|
|to|実行するアカウント|
|value|アカウントに送信するwei|
|argsOffset|calldataを表すメモリ内のバイトオフセット|
|argsSize|コピーするバイトサイズ（calldataのサイズ)|
|retOffset|返り値を格納するメモリ内のバイトオフセット|
|retSize|コピーするバイトサイズ（返り値のサイズ）|

`approve(pool,debtToCover)`のABIエンコードしたデータをメモリ内の`argsOffset(0x00)`から`argsSize(0x44 = 0x04+0x20+0x20)`に保存します。`mstore`は指定されたオフセットの位置に32bytes単位で書き込むオペコードです。

例えば、以下のHuffコードはメモリの`<offset>`の位置に32bytesの`<value>`を書き込みます。
```
<value> <offset> mstore
```

最終的に`approve`のコールデータをメモリに書き込むコードはこのようになります。

```haskell
#define function approve(address spender, uint256 value) nonpayable returns (bool)
#define constant POOL = 0x794a61358D6845594F94dc1DB02A252b5b4814aD
#define macro EXECUTE_LIQUIDATION() = takes(0) returns(0) {
    ...

    // Call debtAsset.approve(pool, debtToCover)
    // e.g. approve(address POOL,uint256 1000)
    // store func sig at 0x00
    __FUNC_SIG(approve) 0xe0 shl 0x00 mstore  // [debtToCover, user, debt, col]
    // after the operation 
    // Memory loc      Data
    // 0x00: 095ea7b300000000000000000000000000000000000000000000000000000000
    
    // store POOL address at 0x04
    [POOL] 0x04 mstore                     // [debtToCover, user, debt, col]
    // after the operation 
    // Memory loc      Data
    // 0x00: 095ea7b3000000000000000000000000794a61358d6845594f94dc1db02a252b
    // 0x20: 5b4814ad00000000000000000000000000000000000000000000000000000000
   
     // store debtToCover at 0x24
    dup1 0x24 mstore                       // [debtToCover, user, debt, col]

    // after the operation 
    // Memory loc      Data
    // 0x00: 095ea7b3000000000000000000000000794a61358d6845594f94dc1db02a252b
    // 0x20: 5b4814ad00000000000000000000000000000000000000000000000000000000
    // 0x40: 000003e800000000000000000000000000000000000000000000000000000000
}
```
`call`は呼び出しが成功したかどうかをスタックに出力します。呼び出しが失敗したならエラー実装箇所へジャンプします。

```
    0x00                    // [retSize, debtToCover, user, debt, col]
    0x00                    // [retOffset, retSize, debtToCover, user, debt, col]
    0x44                    // [argSize, retOffset, retSize, debtToCover, user, debt, col]
    0x00                    // [argOffset, argSize, retOffset, retSize, debtToCover, user, debt, col]
    dup1                    // [value, argOffset, argSize, retOffset, retSize, debtToCover, user, debt, col]
    dup8                    // [to, value, argOffset, argSize, retOffset, retSize, debtToCover, user, debt, col]
    gas                     // [gas, to, value, argOffset, argSize, retOffset, retSize, debtToCover, user, debt, col]
    call                    // [success, debtToCover, user, debt, col]

    // Validate call success
    iszero error jumpi       // [debtToCover, user, debt, col]

    // 続く
```
同様に、`POOL.liquidationCall(collateralAsset, debtAsset, user, debtToCover, false)`を`call`オペコードで呼び出します。`EXECUTE_LIQUIDATION`マクロの完成形は次のようになります。

##### コード

```haskell
#define macro EXECUTE_LIQUIDATION() = takes(0) returns(0) {
    // input stack: []

    // Unpack the calldata
    // calldata is encoded with abi.encodePacked(address collateralAsset,address debtAsset,address user,uint128 debtToCover)
    0x00 calldataload 0x60 shr              // [col] - bytes 20
    0x14 calldataload 0x60 shr              // [debt, col] - bytes 20
    0x28 calldataload 0x60 shr              // [user, debt, col] - bytes 20
    0x3c calldataload 0x80 shr              // [debtToCover, user, debt, col] - uint128

    // Call debtAsset.approve(pool, debtToCover)
    __FUNC_SIG(approve) 0xe0 shl 0x00 mstore  // [debtToCover, user, debt, col]
    [POOL] 0x04 mstore                     // [debtToCover, user, debt, col]
    dup1 0x24 mstore                       // [debtToCover, user, debt, col]

    0x00                    // [retSize, debtToCover, user, debt, col]
    0x00                    // [retOffset, retSize, debtToCover, user, debt, col]
    0x44                    // [argSize, retOffset, retSize, debtToCover, user, debt, col]
    0x00                    // [argOffset, argSize, retOffset, retSize, debtToCover, user, debt, col]
    dup1                    // [value, argOffset, argSize, retOffset, retSize, debtToCover, user, debt, col]
    dup8                    // [to, value, argOffset, argSize, retOffset, retSize, debtToCover, user, debt, col]
    0x1388 gas sub          // [(gas - 5000), to, value, argOffset, argSize, retOffset, retSize, debtToCover, user, debt, col]
    call                    // [success, debtToCover, user, debt, col]

    // Validate call success
    iszero error jumpi       // [debtToCover, user, debt, col]

    // Call POOL.liquidationCall(collateralAsset, debtAsset, user, debtToCover, false)
    __FUNC_SIG(liquidationCall) 0xe0 shl 0x00 mstore   //  [debtToCover, user, debt, col]
    dup4 0x04 mstore                     // [debtToCover, user, debt, col]
    dup3 0x24 mstore                     // [debtToCover, user, debt, col]
    dup2 0x44 mstore                     // [debtToCover, user, debt, col]
    dup1 0x64 mstore                     // [debtToCover, user, debt, col]
    0x00 0x84 mstore                     // [debtToCover, user, debt, col]

    // Execute the call
    0x00                    // [retSize, debtToCover, user, debt, col]
    0x00                    // [retOffset, retSize, debtToCover, user, debt, col]
    0x104                    // [argSize, retOffset, retSize, debtToCover, user, debt, col]
    0x00                    // [argOffset, argSize, retOffset, retSize, debtToCover, user, debt, col]
    dup1                    // [value, argOffset, argSize, retOffset, retSize, debtToCover, user, debt, col]
    [POOL]                    // [to, value, argOffset, argSize, retOffset, retSize, debtToCover, user, debt, col]
    0x1388 gas sub          // [(gas - 5000), to, value, argOffset, argSize, retOffset, retSize, debtToCover, user, debt, col]
    call                    // [success, debtToCover, user, debt, col]

    // Validate call success
    iszero error jumpi stop
}

```

### ガス費用の比較
| Single Liquidation     | Gas Used |Bytecode Size (kB)|
| ---------------------- | -------- |-----|
| Pure Solidity Contract | 34403    |1.105|
| Huff Contract          | 33873    |0.568|

Solidityの段階でそれなりにガスを使わないようにしているので、530 gasほどしか安くなってませんね。

追記：
記事を公開した後、さらに改善できました。
```diff
- | Huff Contract                   | 33873    | 0.568              |
+ | Huff Contract                   | 33861    | 0.552              |
```

### まとめ
非標準エンコーディングでコールデータを与えることで、データサイズを小さくできそう。(どのくらいコストが減るかは未検証...)
Huffコントラクトでミニマムな清算の実装をした。これをベースにしてフラッシュローンなどを組み合わせれば実用性が増すでしょう。

### コード
[massun-onibakuchi/grim-reaper](https://github.com/massun-onibakuchi/grim-reaper)

### 参考

https://docs.huff.sh/

https://www.evm.codes/