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

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

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

概要＆この記事を書こうと思ったきっかけ

本記事ではSolidityのinline assemblyを、solidity-BigNumbersを通じて学びたいと思います。

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

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

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

この記事のゴール

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

    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構造体を取得し、その後加算メソッドや乗算メソッドを呼びます。詳細はいろいろ追ってみてください。

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

（少し脱線）加法準同型暗号ってなに？

暗号化したまま足し算ができる暗号です。例えば、paillier暗号やlifted-elgamal暗号があります。
solidity-BigNumbersを使うと、簡単にpaillier暗号を実装できます（以下が実際のコード、ref）。
加算だけでもいろんなことができます。例えば、電子投票とか、画像のエッジ検出とか（私の力不足もあり、一瞬でout of gasになりましたがw）。

    /**
    * @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を読み、学ぶ

では、上から読んでいきましょうか。

assembly { .... }

inline assemblyはassembly{}内に書くようですね(ref)

let data := add(val, 0x20)

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

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の値のスタートを指しているわけですね。

let out

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

let freemem := msize()

//todo 要修正
msize()でメモリのサイズが取得できます(ref)。

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)。
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単位で計算できるようにそろえています。

pop(staticcall(450, 0x4, data, length, out, length))  // copy into 'out' memory location

staticcallで、アドレス0x4のコントラクトをcallします。call opcodeもありますが、staticと付いているので、こちらは状態を変更しないことを意味します(ref)。んで、0x4はなんやねんってなるわけですが、これはprecompiled contractのアドレスです。読んで字のごとく、事前にコンパイル済みのコントラクトです。precompiled contractにどのようなものがあるかは、これなどをチェックしてください。Gethのソースコードからももちろんわかります。んで、0x4はデータコピーを提供するprecompiled contractです。これを呼び出し、dataからoutへlength分データコピーします。

mstore(0x40, add(freemem, add(mload(freemem), 0x20))) // update the free memory pointer

コピー後、mstore(）で、アドレス0x40のデータを更新します。0x40は、free memory pointerと呼ばれ、現在割り当てられているメモリの終端を指しています。以下、ここからの引用です。

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.

// 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)。上の書き方は、初期化部分とイテレーション後の部分は省略されており({})、条件だけなので、while(length!=32)と理解できます。先頭ビットがゼロの部分は飛ばしたいので、eq()で1word分ゼロかどうか判断し、先頭ゼロなら(case1)、lengthを更新していきます。

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)。

おわりに

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

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

参考

Solidity Assembly

EVM opcode

中島聡さんのツイート