😀

SolidityにおけるMerkle Proofについて

2021/12/09に公開

Solidity

tech

1. Overview

ガイドのターゲット

MarkleProofとは何か、使うことのメリット
Solidity by ExsampleのMerkle Treeの解説
zeppelin-solidity/contracts/MerkleProof.solの解説

必要な知識

Solidityの簡単な文法
ハッシュ関数
木グラフ

2. MerkleProofとは何か、使うことのメリット

こちらの記事が図で分かりやすく解説されていますので参照してください。
マークルツリーのガイド　PRSARAHEVANS

データバリデーション　Symbol From NEM

語句の整理
マークルツリー : ハッシュによってラベル付けされたノードのデータ構造ツリー。
マークルルート : マークルルートの根の部分。
リーフノード：マークルルートの葉の部分。検証するデータをハッシュ化したもの。
マークルプルーフ : マークルルートを再度計算しデータの有効性を証明すること。
注意
マークルルートを計算する際にハッシュの数が奇数だった場合は複製して計算する。

こちらがuniswapがエアドロする時にマークルプルーフを使用した例です。後でこちらが使用しているMerkleProofライブラリのコードの説明を行います。

3. Solidity by ExsampleのMarkle Treeの解説

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.3;

// マークルツリーの再計算に必要な最小のノードの配列、マークルルート、リーフノード、リーフノードのindexを
// 引数として受け取り、検証した結果をbool値で返します。
// indexは葉を左から順番に数えた数−１です。
contract MerkleProof {
    function verify(
        bytes32[] memory proof, // マークルツリーの再計算に必要な最小のノードの配列
        bytes32 root, // マークルルート
        bytes32 leaf, // リーフノード
        uint index // リーフノードのindex、ノードを連結させるときに使用します。
    ) public pure returns (bool) {
        // 計算されていくノードを格納する変数で最初はリーフノードです。
        bytes32 hash = leaf;
        
        // 再計算に必要な最小のノードの配列を一つずつ取り出し、連結していきます。
        for (uint i = 0; i < proof.length; i++) {
            // 配列から連結するノードを取り出します。
            bytes32 proofElement = proof[i];
            
            // 取り出したノードをindexが偶数の場合は右に、偶数の場合は左に連結させます。
            // encodePacked(AAA,BBB) -> AAABBB
            // encodePacked(AA,ABBB) -> AAABBB
            if (index % 2 == 0) {
                hash = keccak256(abi.encodePacked(hash, proofElement));
            } else {
                hash = keccak256(abi.encodePacked(proofElement, hash));
            }
            
            // indexを2で割っていくことで次の深さでの連結方法が求められます。
            // 例）　index = 5;
            // 5,2,1,0,0...
            // 奇数、偶数、奇数、偶数、偶数...
            // 左、右、左、右、右...
            // indexは葉を左から順番に数えた数−１です。
            index = index / 2;
        }
        
        // 最後に出てきたhashノードがマークルルートなので
        // これが引数のrootと一致しているか確認します。
        return hash == root;
    }
}

// 上述のMerkleProofのコントラクトを継承させて新しいコントラクトを作成します。
contract TestMerkleProof is MerkleProof {
    // この配列にマークルツリーのノードを格納させていきます。
    bytes32[] public hashes;

    // デプロイ時にマークルツリーの計算を行います。
    constructor() {
        string[4] memory transactions = [
            "alice -> bob",
            "bob -> dave",
            "carol -> alice",
            "dave -> bob"
        ];
        
        // トランザクションをハッシュ化してリーフノードにし、配列に格納します。
        for (uint i = 0; i < transactions.length; i++) {
            hashes.push(keccak256(abi.encodePacked(transactions[i])));
        }

        // マークルツリーの葉の長さ
        uint n = transactions.length;
        // ある一定の深さまでのノードの数の合計
        uint offset = 0;

        // マークルルートが出てくるまで計算します。
        while (n > 0) {
            // ある深さのノードの数はnです。
            for (uint i = 0; i < n - 1; i += 2) {
                hashes.push(
                    keccak256(
                        abi.encodePacked(hashes[offset + i], hashes[offset + i + 1])
                    )
                );
            }
            
            // 今までのノードの数の合計に今計算したノードの数を足します。
            offset += n;
            
            // 深さが浅くなるにつれノードの数は半分に減っていきます。
            // n = ０になった時に終了します。
            n = n / 2;
        }
    }

    // マークルルートを返す変数です。つまり、hashes[]の最後の要素です。
    function getRoot() public view returns (bytes32) {
        return hashes[hashes.length - 1];
    }

    // こちらに継承したMerkleProofのverify関数を呼び出し検証する関数を記述します。
    
    /* verify
    3rd leaf
    0x1bbd78ae6188015c4a6772eb1526292b5985fc3272ead4c65002240fb9ae5d13

    root
    0x074b43252ffb4a469154df5fb7fe4ecce30953ba8b7095fe1e006185f017ad10

    index
    2

    proof
    0x948f90037b4ea787c14540d9feb1034d4a5bc251b9b5f8e57d81e4b470027af8
    0x63ac1b92046d474f84be3aa0ee04ffe5600862228c81803cce07ac40484aee43
    */
}

上記のサンプルコードはマークルツリーの計算をオンチェーンで行い、その計算結果をチェーン上のストレージに保存しているためこの関数のデプロイにはそれなりにガス代がかかると思われます。また、 MerkleProofコントラクトのverify関数をこのコントラクトに書き込む場合、その度にマークルツリーの全要素がよばれるため、あまりガス代を節約できていません。
　このコントラクトの例ではTestMerkleProofコントラクトがMerkleProofコントラクトを継承していますが、継承せずに読み取り専用にデプロイし、別途、TestMerkleProofコントラクトから呼び出したマークルルートを保持した MerkleProofコントラクトをデプロイすると、検証する際にガス代を大幅に節約できます。その時、MerkleProofコントラクトに渡す引数はマークルルートの計算に必要な最小のノードの配列と、リーフノードと、リーフノードのindexになります。

4. zeppelin-solidity/contracts/MerkleProof.solの解説

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

pragma solidity ^0.8.0;

// マークルツリーの再計算に必要な最小のノードの配列を連結させたもの、マークルルート、リーフノードを
// 引数として受け取り、検証した結果をbool値で返します。
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));
        }
    }
}

上記のコントラクトは先ほど紹介したコントラクトよりもガス代を安く抑えることができています。使い方は、まず事前に全てのデータからマークルツリーを計算しておきます。その後、マークルツリーを格納した配列をデータベースに、マークルルートをコントラクトに保存します。
　データを検証する場合は、まずデータベースに保存されているマークルツリーから、検証したいデータでマークルルートを計算するのに必要な最小のノードの配列を導きます。その後、マークルルートが保存されているコントラクトに、検証したいデータとマークルルートの再計算に必要な最小のノードの配列を引数にして渡し、そのコントラクトから上記のコントラクトを呼び出します。そうすれば、コントラクトに保存するのはマークルルートのみとなりガス代を抑えられます。
　マークルルートはbyte32で固定なのでマークルツリーの葉がどれだけ増えようがデプロイ時のガス代は変わりません。また、コントラクトの引数として渡す最小のノードの配列は木の深さになるため2の対数になります。例えば、1032個のデータがある場合、マークルツリーの再計算に必要な最小のノード数はたったの10個だけとなります。
　さらに、このコントラクトではindexを使わず大小比較で連結方法を決めているため、引数が減り計算もシンプルになるため、ガス代も抑えられていると思われます。