💹

ブロックチェーン技術で頻出のマークルプルーフを理解しよう

2022/06/17に公開

ブロックチェーン

こんにちは。JPYC研究開発チームのretocroomanです。暗号資産市場が軒並み大暴落している冬の時代を如何お過ごしでしょうか。こういう時こそ基礎理論を学んで、コツコツとレベルアップしませんか？

今回紹介するマークルプルーフはブロックチェーン技術において外せない重要な要素です。マークルプルーフの仕組みを実際のコードを読みながら理解していきましょう。

前提知識

Solidity（前提知識集）

MercleProofの目的

ビットコインのホワイトペーパーにも登場しますが、全てのノードが大量のトランザクション記録を持たなくて済むようにしたり、エアドロップ対象のアドレスリストのデータを圧縮したりするのに使われています。ディスク・スペースの節約の際に活躍し、Ethereumではガス代の削減にも貢献します。

マークルプルーフはデータの圧縮といっても元のデータに復元できるわけではありません。データが正しいかを検証できるだけです。しかし、それだけでリソースの限られたブロックチェーンにおいては十分に重宝されるのです。基本的なマークルプルーフの実践例としては、データをオフチェーンで保存し、マークルプルーフで計算されたルートハッシュをオンチェーンに保存し、オフチェーンの情報が正しいことをオンチェーンで確認するやり方です。マークルプルーフのすごいところはオフチェーンのデータに少しでも間違いがあれば気付くことができるところです。そして検証スピードも比較的早いです。

では、実際に仕組みをみていきましょう。まず下の図をご覧ください。

出典：ウィキペディア
これはマークルツリーと呼ばれるものですが名前の通り木構造をしていますね。このように、検証したいデータ群のハッシュ値を一列に並べて、隣同士を結合させてハッシュ化、さらに隣同士を結合してハッシュ化としていき最後の一つになるまで繰り返します。この図ではHash0-0、Hash0-1、Hash1-0、Hash1-1がデータ群をそれぞれハッシュ化したものです。これらをリーフノードと呼びます。そのハッシュ化されたものの隣同士を結合し、さらにハッシュ化してHash0、Hash1が出てきています。これを繰り返し、最後に残ったTop hashこそがマークルルートと呼ばれるものになります。もしデータ群のうち一つでも中身が違えば、結合されるデータのハッシュ値も異なるのでマークルルートは一致しなくなります。そうしてマークルルートによりデータの整合性を保っています。ちなみに、データ群の数が2の累乗でなく結合相手がいない時は、自分を複製して結合か、何もしないかの2通りの方法があります。ビットコインは前者です。

次に、具体的にデータを検証する際の手順を見ていきます。例えば、上の図でData block001が正しいことを証明するにはHash0-0とHash1のみ必要になります。なぜならHash0-0とData block001のハッシュ値Hash0-1からHash0を求め、Hash0とHash1を結合しハッシュ化すればTop hashが求められるからです。このTop hashが一致すればData block001は正しかったということになります。ここで、出てきたHash0-0とHash1はマークルプルーフと呼ぶことにします。マークルプルーフは検証したいデータのインデックスとマークルツリーから求めることができます。

語句を一旦整理しますと以下の認識で大丈夫だと思います。

マークルツリー : データの要約を格納するツリー状のデータ構造。
マークルルート : 隣同士で結合させハッシュ化を繰り返して最後に残ったハッシュ値。
リーフノード：検証するデータをハッシュ化したもの。マークルルートの計算には全てのリーフノードが必要。
マークルプルーフ : マークルルートを再度計算する際に必要なハッシュ値のリスト。検証するデータのハッシュ値と結合されていく。

openzeppelin-solidity/contracts/MerkleProof.solのコード解説

それではOpenZeppelinのライブラリにあるマークルプルーフの検証コードを解説していきます。

こちらバージョンは違いますが、uniswapのエアドロにも使われたライブラリです。

pragma solidity ^0.8.0;

library MerkleProof {
    function verify(
        bytes32[] memory proof, // マークルプルーフ
        bytes32 root, // マークルルート
        bytes32 leaf // 検証したいデータのハッシュ値
    ) public pure returns (bool) {
        // processProof関数の計算結果が引数のrootと一致しているか確認します。
        return processProof(proof, leaf) == root;
    }

    function processProof(
        byte32[] memory proof, // マークルプルーフ
        byte32 leaf // リーフノード
    ) internal pure returns (byte32) {
    //　結合しハッシュ化されていく変数で最初はリーフノードです。
    bytes32 computedHash = _leaf;

    // マークルプルーフからハッシュ値を一つずつ取り出し、連結していきます。
    for (uint256 i = 0; i < proof.length; i++) {
        // 配列から連結するノードを取り出します。
        bytes32 proofElement = proof[i];
        
        // マークルプルーフから取り出したハッシュ値と計算して出したハッシュ値を大小比較します。
        // 小さい方を左に、大きい方は右に連結させます。
        // encodePacked(AAA,BBB) -> AAABBB
        // encodePacked(AA,ABBB) -> AAABBB
        if (computedHash <= proofElement) {
            // Hash(current computed hash + current element of the proof)
            computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
        } else {
            // Hash(current element of the proof + current computed hash)
            computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
        }
    }
}

このライブラリの使い方は、まず事前に全てのデータ群からマークルツリーを計算しておきます。その後、マークルツリーを格納した配列をデータベースに、マークルルートをコントラクトに保存します。
　データを検証する場合は、まずデータベースに保存されているマークルツリーから、検証したいデータのインデックスでマークルルートを計算するのに必要なマークルプルーフをマークルツリーから抜き出します。その後、マークルルートが保存されているコントラクトに、検証したいデータのハッシュ値とマークルルートとマークルプルーフを渡し、そのコントラクトから上記のライブラリを呼び出します。そうすれば、コントラクトに保存するのはマークルルートのみとなり、かなりガス代を抑えられます。
　マークルルートはbytes32で固定なのでマークルツリーの葉がどれだけ増えようがデプロイ時のガス代は変わりません。また、コントラクトの引数として渡すマークルプルーフは木の深さになるため2の対数になります。例えば、1032個のデータがある場合、マークルツリーの再計算に必要な最小のノード数はたったの10個だけとなります。
　ただ、OpenZeppelinのライブラリではインデックスではなく大小比較で連結する際の順番を決めているため、マークルルートやマークルプルーフを計算する際は注意しなければなりません。npmパッケージのmerkletreejsを使う場合はオプションで{ sortPairs: true }を指定してあげる必要があります。下記のように書いてあげれば大丈夫です。

const { MerkleTree } = require('merkletreejs')
const SHA256 = require('crypto-js/sha256')

const leaves = ['a', 'b', 'c'].map(x => SHA256(x))
const tree = new MerkleTree(leaves, SHA256, { sortPairs: true })
const root = tree.getRoot().toString('hex')
const leaf = SHA256('a')
const proof = tree.getProof(leaf)
console.log(tree.verify(proof, leaf, root)) // true

まとめ

今回は、マークルプルーフの仕組みと使い方について詳しく解説してみました。ブロックチェーンにおいて色々なところで活躍している技術なのできっと知っておくと役に立つはずです。マークルプルーフと一口にいっても色々なマークルルートの算出方法があるのでそこは気を付けなければいけませんが。

ここまでお読みいただきありがとうございます。基礎理論を学び、レベルアップできましたでしょうか？
これからもブロックチェーン等の開発に役に立つ技術的な知見を記事にしていきますのでよろしくお願いします！

日本初のブロックチェーン技術（ERC20）を活用した日本円ステーブルコインJPYCはこちらから購入できます！
JPYC社はブロックチェーンエンジニアを募集中です！こちらからご応募お願いします！(タイミングにより募集を行なっていない場合があります)
また、ラボ形式でブロックチェーンに関する講義をしているJPYC開発コミュニティにも是非ご参加ください！

前提知識

MercleProofの目的

openzeppelin-solidity/contracts/MerkleProof.solのコード解説

まとめ

Discussion