実用的なコードを通して学ぶSolidity inline assembly入門

メリークリスマス！
25日を担当します、よろしくお願いいたします。

本当は、メリークリスマスということで、Merkle(メリクリ) Patricia Treeについて、Gethのソースコードでも読みながら解説しようと思ったのですが、マークルパトリシア木の記事は結構あるので、やめました、いつか書きたい。

本記事は、以下のライブラリ(BigNumbers.sol)を参考にしながら、inline assemblyについて学ぼうという感じです。以降、こちらのライブラリをsolidity-BigNumbersと記します。

https://github.com/firoorg/solidity-BigNumber


## 概要＆この記事を書こうと思ったきっかけ
本記事ではSolidityのinline assemblyを、[solidity-BigNumbers](https://github.com/firoorg/solidity-BigNumber)を通じて学びたいと思います。

スマートコントラクトで何らかの暗号技術を実装するとき、大きな数での足し算掛け算等が必要になることがあります。例えば、2048ビットで表現される素数は、uint256じゃ足りないわけです。

私は[東京web3ハッカソン](https://tokyo.akindo.io/)で、加法準同型暗号をスマコンで実装することになり、加算準同型暗号×スマートコントラクトについて調べていました([加法準同型暗号って？](#少し脱線加法準同型暗号ってなに))。ググると、以下のような記事とか出てくるのですが、問題が1つあります。セキュリティビットが2048以上でない点です(リンク先いくとわかりますが、uint使っています。uintはuint256のエイリアスです)。

https://kobi.one/2016/04/10/additive-homomorphic-encryption-on-ethereum.html

この問題を解決した実装をしたかったため、セキュリティビット2048以上でも動くように多倍長整数を扱う必要がありました。きっと世界の誰かが、solidityでBignumberを実装しているだろうとGitHubを調べると、[solidity-BigNumbersライブラリ](https://github.com/firoorg/solidity-BigNumber)が見つかり、ハッカソンではセキュリティビットが2048の加法準同型暗号(paillier暗号)を実装できました。このライブラリを理解するにあたり、inline assemblyも少しかじったので、まとめようと思います。


## この記事のゴール
この記事のゴールは、以下のコードが読めるようになることです（コードのコメントで既に何となく読める）。

```solidity
    function _init(
        bytes memory val, 
        bool neg, 
        uint bitlen
    ) private view returns(BigNumber memory r){ 
        // use identity at location 0x4 for cheap memcpy.
        // grab contents of val, load starting from memory end, update memory end pointer.
        assembly {
            let data := add(val, 0x20)
            let length := mload(val)
            let out
            let freemem := msize()
            switch eq(mod(length, 0x20), 0)                       // if(val.length % 32 == 0)
                case 1 {
                    out     := add(freemem, 0x20)                 // freememory location + length word
                    mstore(freemem, length)                       // set new length 
                }
                default { 
                    let offset  := sub(0x20, mod(length, 0x20))   // offset: 32 - (length % 32)
                    out     := add(add(freemem, offset), 0x20)    // freememory location + offset + length word
                    mstore(freemem, add(length, offset))          // set new length 
                }
            pop(staticcall(450, 0x4, data, length, out, length))  // copy into 'out' memory location
            mstore(0x40, add(freemem, add(mload(freemem), 0x20))) // update the free memory pointer
            
            // handle leading zero words. assume freemem is pointer to bytes value
            let bn_length := mload(freemem)
            for { } eq ( eq(bn_length, 0x20), 0) { } {            // for(; length!=32; length-=32)
             switch eq(mload(add(freemem, 0x20)),0)               // if(msword==0):
                    case 1 { freemem := add(freemem, 0x20) }      //     update length pointer
                    default { break }                             // else: loop termination. non-zero word found
                bn_length := sub(bn_length,0x20)                          
            } 
            mstore(freemem, bn_length)                             

            mstore(r, freemem)                                    // store new bytes value in r
            mstore(add(r, 0x20), neg)                             // store neg value in r
        }

        r.bitlen = bitlen == 0 ? bitLength(r.val) : bitlen;
    }
```

bytesであるvalを受け取り、BigNumber構造体を返します。solidityのbytesは可変サイズなので、大きい数（というか、任意長のbit列）を扱えるわけです。BigNumber構造体も、中身はただのbytesです(加えて、符号情報やビット長もある、以下参考)。このライブラリは、init関数によってBigNumber構造体を取得し、その後[加算メソッド](https://github.com/firoorg/solidity-BigNumber/blob/d59a9aa28967f94932a6256370b04865933b3710/src/BigNumbers.sol#L103)や[乗算メソッド](https://github.com/firoorg/solidity-BigNumber/blob/d59a9aa28967f94932a6256370b04865933b3710/src/BigNumbers.sol#L210)を呼びます。詳細はいろいろ追ってみてください。

```solidity
struct BigNumber { 
    bytes val;
    bool neg;
    uint bitlen;
}
```

## （少し脱線）加法準同型暗号ってなに？
暗号化したまま足し算ができる暗号です。例えば、[paillier暗号](https://ja.wikipedia.org/wiki/Paillier%E6%9A%97%E5%8F%B7)や[lifted-elgamal暗号](https://herumi.github.io/ango/)があります。
solidity-BigNumbersを使うと、簡単にpaillier暗号を実装できます（以下が実際のコード、[ref](https://github.com/matsutakk/SecureDataCollect-/blob/master/contracts/EncryptedDataStore.sol#L38)）。
加算だけでもいろんなことができます。例えば、電子投票とか、[画像のエッジ検出](https://qiita.com/herumi/items/10a7179d2d9e65c34b75)とか（私の力不足もあり、一瞬でout of gasになりましたがw）。

```solidity
    /**
    * @dev homomorphic addition by Solidity-BigNumbers since cipher text cannot be represented by uint256
    */
    function _homomorphicAddition(bytes memory a, bytes memory b, bytes memory mod) internal view returns(IBigNumbers.BigNumber memory res){
        BigNumber memory bn_cur;
        bn_cur = BigNumbers.init(a, false);
        BigNumber memory bn_add;
        bn_add = BigNumbers.init(b, false);
        BigNumber memory modulus;
        modulus = BigNumbers.init(mod, false);
        res = BigNumbers.modmul(bn_cur, bn_add, modulus);
        return res;
    }
```

## inline assemblyを読み、学ぶ
では、上から読んでいきましょうか。
```solidity
assembly { .... }
```
inline assemblyはassembly{}内に書くようですね([ref](https://solidity-jp.readthedocs.io/ja/latest/assembly.html#syntax))

```solidity
let data := add(val, 0x20)
```
letで変数を宣言します。add(a,b)でa+bします。valはbytesの先頭アドレスなので、先頭アドレスから1word(32byte, つまり0x20)足して進めます。なぜこんなことをしているかは次の行でわかります。

```solidity
let length := mload(val)
```
mload(p)で、アドレスpから1word(32byte)分、値を読み出します。繰り返しですが、valはbytesで、val自体は先頭アドレスを指しています。bytesの先頭32バイトには、bytes valの長さが格納されています。つまり、以下のようなイメージです。mload(val)で、受け取ったbytesの長さを変数lengthにいれています。先ほどの、let data := add(val, 0x20)のdataは、bytes valの値のスタートを指しているわけですね。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223338/12c67014-438a-c43d-ee88-16bf9a9a51e8.png)

```solidity
let out
```
変数outを宣言。今更ですが、お尻にセミコロンは要りません。

```solidity
let freemem := msize()
```
//todo 要修正
msize()でメモリのサイズが取得できます([ref](https://solidity-jp.readthedocs.io/ja/latest/assembly.html#syntax:~:text=storage%5Bp%5D%20%3A%3D%20v-,msize,-F))。


```solidity
switch eq(mod(length, 0x20), 0)                       // if(val.length % 32 == 0)
    case 1 {
        out     := add(freemem, 0x20)                 // freememory location + length word
        mstore(freemem, length)                       // set new length 
    }
    default { 
        let offset  := sub(0x20, mod(length, 0x20))   // offset: 32 - (length % 32)
        out     := add(add(freemem, offset), 0x20)    // freememory location + offset + length word
        mstore(freemem, add(length, offset))          // set new length 
    }
```
見てのとおり、switch文使えます。eq(x,y)で、if x==yなら1, それ以外は0となります([ref](https://solidity-jp.readthedocs.io/ja/latest/assembly.html#syntax:~:text=in%20two%27s%20complement-,eq(x%2C%20y),-F))。
mod(x,y)はx%yです。つまり、bytes valの長さが0x20倍なら、eq()が1となるので、case 1に飛びます。コードのコメントにある通りですね。1word単位にきちっと収まっているなら(case 1)、outにfreememに1word足したところを格納します。使える個所を指させるわけですね。その後mstore(freemem, length)でfreememを移動させます。switchのdefaultの方は、0x20で割り切れず、はみ出しがある場合ですね。offsetを計算して、1word単位で計算できるようにそろえています。

```solidity
pop(staticcall(450, 0x4, data, length, out, length))  // copy into 'out' memory location
```
staticcallで、アドレス0x4のコントラクトをcallします。call opcodeもありますが、staticと付いているので、こちらは状態を変更しないことを意味します([ref](https://solidity-jp.readthedocs.io/ja/latest/assembly.html#syntax:~:text=staticcall(g%2C%20a%2C%20in%2C%20insize%2C%20out%2C%20outsize)))。んで、0x4はなんやねんってなるわけですが、これはprecompiled contractのアドレスです。読んで字のごとく、事前にコンパイル済みのコントラクトです。precompiled contractにどのようなものがあるかは、[これ](https://ethereum.stackexchange.com/questions/15479/list-of-pre-compiled-contracts)などをチェックしてください。[Gethのソースコード](https://github.com/ethereum/go-ethereum/blob/9d795d0836cb67ac42035c29839500b364ecc64b/core/vm/contracts.go#L46)からももちろんわかります。んで、0x4はデータコピーを提供するprecompiled contractです。これを呼び出し、dataからoutへlength分データコピーします。

```solidity
mstore(0x40, add(freemem, add(mload(freemem), 0x20))) // update the free memory pointer
```
コピー後、mstore(）で、アドレス0x40のデータを更新します。0x40は、free memory pointerと呼ばれ、現在割り当てられているメモリの終端を指しています。以下、[ここ](https://ethereum.stackexchange.com/questions/9603/understanding-mload-assembly-function#:~:text=In%20solidity%2C%20the%200x40%20slot%20in%20memory%20is%20special%3A%20it%20contains%20the%20%22free%20memory%20pointer%22%20which%20points%20to%20the%20end%20of%20the%20currently%20allocated%20memory.)からの引用です。
>In solidity, the 0x40 slot in memory is special: it contains the "free memory pointer" which points to the end of the currently allocated memory.

```solidity
// handle leading zero words. assume freemem is pointer to bytes value
let bn_length := mload(freemem)
for { } eq ( eq(bn_length, 0x20), 0) { } {            // for(; length!=32; length-=32)
 switch eq(mload(add(freemem, 0x20)),0)               // if(msword==0):
        case 1 { freemem := add(freemem, 0x20) }      //     update length pointer
        default { break }                             // else: loop termination. non-zero word found
    bn_length := sub(bn_length,0x20)                          
} 
```
コメントにあるように、bytes valのleading zeroを除きます。まずmload(freemem)でbytes valのlengthを取得＆格納。forループは初期化部分、条件、イテレーション後のパートを含むヘッダを持っている([ref](https://solidity-jp.readthedocs.io/ja/latest/assembly.html#loops))。上の書き方は、初期化部分とイテレーション後の部分は省略されており({})、条件だけなので、while(length!=32)と理解できます。先頭ビットがゼロの部分は飛ばしたいので、eq()で1word分ゼロかどうか判断し、先頭ゼロなら(case1)、lengthを更新していきます。 

```solidity
mstore(freemem, bn_length)                             
mstore(r, freemem)                                    // store new bytes value in r
mstore(add(r, 0x20), neg)                             // store neg value in r
```
最後に、bn_lengthとnegを保存しています。これでinline assemblyをマスターしました！きっと！

[init関数補足]
inline assemblyを抜けた後、bitlenを確定させ、BigNumber構造体 rを返します([ref](https://github.com/firoorg/solidity-BigNumber/blob/d59a9aa28967f94932a6256370b04865933b3710/src/BigNumbers.sol#L908))。

## おわりに
いかがでしたでしょうか。25日になってしまったので、とりあえず公開します。そしてあとできっと更新します（こう表現すると、そのきっとは来ないと思われるようです）。

読んでいただきありがとうございました。メリークリスマス。良いお年を。

## 参考
- Solidity Assembly

https://solidity-jp.readthedocs.io/ja/latest/assembly.html


- EVM opcode

https://ethereum.org/ja/developers/docs/evm/opcodes/

- 中島聡さんのツイート

https://twitter.com/snakajima/status/1587284704239423488