Michael.W基于Foundry精读Openzeppelin第34期——MerkleProof.sol

  • Michael.W
  • 更新于 2023-09-16 18:35
  • 阅读 2130

MerkleProof库提供了用于验证merkle树proof的工具函数。在生成merkle树和对应proof时应当避免使用64字节长度的leaf（进行hash之前）或避免使用非keccak256的哈希函数（进行leaf的hash计算）。这是因为树中经排序的内部节点的拼接可以被重新解释为leaf值。

0. 版本

[openzeppelin]：v4.8.3，[forge-std]：v1.5.6

0.1 MerkleProof.sol

Github: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/v4.8.3/contracts/utils/cryptography/MerkleProof.sol

MerkleProof库提供了用于验证merkle树proof的工具函数。在生成merkle树和对应proof时，应当避免使用64字节长度的leaf（进行hash之前）或避免使用非keccak256的哈希函数（进行leaf的hash计算）。这是因为merkle树中经过排序的内部节点的拼接可以被重新解释为leaf值。

注：merkle树和对应proof可利用Openzeppelin提供的js库生成，该js库与MerkleProof库配合使用是安全的：https://github.com/OpenZeppelin/merkle-tree

1. 目标合约

封装MerkleProof library成为一个可调用合约：

Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/src/utils/cryptography/MockMerkleProof.sol

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;

import "openzeppelin-contracts/contracts/utils/cryptography/MerkleProof.sol";

contract MockMerkleProof {
    using MerkleProof for bytes32[];
    bytes32 private _root;

    constructor(bytes32 root){
        _root = root;
    }

    function verify(
        bytes32[] memory proof,
        address account,
        uint amount
    ) external view returns (bool) {
        bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(account, amount))));
        return proof.verify(_root, leaf);
    }

    function verifyCalldata(
        bytes32[] calldata proof,
        address account,
        uint amount
    ) external view returns (bool) {
        bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(account, amount))));
        return proof.verifyCalldata(_root, leaf);
    }

    function processProof(bytes32[] memory proof, bytes32 leaf) external pure returns (bytes32){
        return proof.processProof(leaf);
    }

    function processProofCalldata(bytes32[] calldata proof, bytes32 leaf) external pure returns (bytes32) {
        return proof.processProofCalldata(leaf);
    }

    function multiProofVerify(
        bytes32[] memory proof,
        bool[] memory proofFlags,
        address[] memory accounts,
        uint[] memory amounts
    ) external view returns (bool){
        uint len = accounts.length;
        require(len == amounts.length, "length unmatched");
        bytes32[] memory leaves = new bytes32[](len);
        for (uint i = 0; i < len; i++) {
            leaves[i] = keccak256(bytes.concat(keccak256(abi.encode(accounts[i], amounts[i]))));
        }

        return proof.multiProofVerify(proofFlags, _root, leaves);
    }

    function multiProofVerifyCalldata(
        bytes32[] calldata proof,
        bool[] calldata proofFlags,
        address[] calldata accounts,
        uint[] calldata amounts
    ) external view returns (bool) {
        uint len = accounts.length;
        require(len == amounts.length, "length unmatched");
        bytes32[] memory leaves = new bytes32[](len);
        for (uint i = 0; i < len; i++) {
            leaves[i] = keccak256(bytes.concat(keccak256(abi.encode(accounts[i], amounts[i]))));
        }

        return proof.multiProofVerifyCalldata(proofFlags, _root, leaves);
    }

    function processMultiProof(
        bytes32[] memory proof,
        bool[] memory proofFlags,
        bytes32[] memory leaves
    ) external pure returns (bytes32 merkleRoot) {
        return proof.processMultiProof(proofFlags, leaves);
    }

    function processMultiProofCalldata(
        bytes32[] calldata proof,
        bool[] calldata proofFlags,
        bytes32[] memory leaves
    ) external pure returns (bytes32 merkleRoot) {
        return proof.processMultiProofCalldata(proofFlags, leaves);
    }
}

全部foundry测试合约：

Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/test/utils/cryptography/MerkleProof.t.sol

测试数据：

测试数据的生成脚本：

Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/test/utils/cryptography/MerkleProof_test.ts

import * as fs from 'fs'
import {StandardMerkleTree} from '@openzeppelin/merkle-tree'

// 1. build a tree
const elements = [
    ['0x0000000000000000000000000000000000000001', 10000],
    ['0x0000000000000000000000000000000000000002', 20000],
    ['0x0000000000000000000000000000000000000003', 30000],
    ['0x0000000000000000000000000000000000000004', 40000],
    ['0x0000000000000000000000000000000000000005', 50000],
    ['0x0000000000000000000000000000000000000006', 60000],
]

let merkleTree = StandardMerkleTree.of(elements, ['address', 'uint256'])
const output = {
    merkle_root: merkleTree.root,
    merkle_tree: merkleTree.dump(),
}

fs.writeFileSync('test/utils/cryptography/data/merkle_tree.json', JSON.stringify(output))

// 2. get proof
// read json merkle tree from file
const content = JSON.parse(fs.readFileSync('test/utils/cryptography/data/merkle_tree.json', 'utf8'))
merkleTree = StandardMerkleTree.load(content['merkle_tree'])

const arr = []
for (const [i, element] of merkleTree.entries()) {
    arr.push({'account': element[0], 'amount': element[1], 'proof': merkleTree.getProof(i)})
}

fs.writeFileSync('test/utils/cryptography/data/merkle_proof.json', JSON.stringify(arr))

// 3. generate multi proofs
const {proof, proofFlags, leaves} = merkleTree.getMultiProof([0, 2, 4])

fs.writeFileSync('test/utils/cryptography/data/merkle_multi_proof.json', JSON.stringify({
    proof,
    'proof_flags': proofFlags,
    'leaves': leaves.map(item => {
        return {
            'account': item[0],
            'amount': item[1],
        }
    }),
}))

2. 代码精读

2.1 processProof(bytes32[] memory proof, bytes32 leaf) && processProofCalldata(bytes32[] calldata proof, bytes32 leaf)

  • processProof(bytes32[] memory proof, bytes32 leaf)：利用proof（bytes32[] memory）和leaf来计算merkle tree的root。只有使用了有效proof得到的结果才是merkle tree的原始root；
  • processProofCalldata(bytes32[] calldata proof, bytes32 leaf)：利用proof（bytes32[] calldata）和leaf来计算merkle tree的root。只有使用了有效proof得到的结果才是merkle tree的原始root。

注：以上二者在迭代proof时，假定leaves对和pre-images对都是经过排序的。processProofCalldata()可以认为是calldata参数版的processProof()。

    function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32) {
        // 将leaf设置成迭代的computedHash
        bytes32 computedHash = leaf;
        // 遍历proof，迭代计算computedHash与对应proof的哈希值。在每次计算computedHash与对应proof的hash值的过程中会对输入进行排序处理
        for (uint256 i = 0; i < proof.length; i++) {
            computedHash = _hashPair(computedHash, proof[i]);
        }

        // 返回最终迭代计算出的hash值
        return computedHash;
    }

    function processProofCalldata(bytes32[] calldata proof, bytes32 leaf) internal pure returns (bytes32) {
        // 将leaf设置成迭代的computedHash
        bytes32 computedHash = leaf;
        // 遍历proof，迭代计算computedHash与对应proof的哈希值。在每次计算computedHash与对应proof的hash值的过程中会对输入进行排序处理
        for (uint256 i = 0; i < proof.length; i++) {
            computedHash = _hashPair(computedHash, proof[i]);
        }

        // 返回最终迭代计算出的hash值
        return computedHash;
    }

    // 计算1个bytes32对的哈希值
    function _hashPair(bytes32 a, bytes32 b) private pure returns (bytes32) {
        // 如果a<b，计算a.b的哈希值；否则计算b.a的哈希值
        return a < b ? _efficientHash(a, b) : _efficientHash(b, a);
    }

    // 快速计算连接两个bytes32内容(即a.b)的哈希值
    function _efficientHash(bytes32 a, bytes32 b) private pure returns (bytes32 value) {
        /// @solidity memory-safe-assembly
        assembly {
            // 将a存储0x00开始的内存中（占32个字节）
            mstore(0x00, a)
            // 将b存储0x20开始的内存中（占32个字节）
            mstore(0x20, b)
            // 计算从0x00开始，连续64个字节的内存中内容的哈希值
            value := keccak256(0x00, 0x40)
        }
    }

foundry代码验证

contract MerkleProofTest is Test {
    using stdJson for string;

    struct MerkleProofData {
        address account;
        uint amount;
        bytes32[] proof;
    }

    string private _jsonMerkleTree = vm.readFile("test/utils/cryptography/data/merkle_tree.json");
    string private _jsonMerkleProof = vm.readFile("test/utils/cryptography/data/merkle_proof.json");
    bytes32 private _rootHash = _jsonMerkleTree.readBytes32(".merkle_root");
    MockMerkleProof private _testing = new MockMerkleProof(_rootHash);

    function test_ProcessProof() external {
        MerkleProofData[] memory merkleProofData = abi.decode(_jsonMerkleProof.parseRaw(""), (MerkleProofData[]));
        for (uint i = 0; i < merkleProofData.length; ++i) {
            // case 1: correct leaf with correct proof
            bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(merkleProofData[i].account, merkleProofData[i].amount))));
            assertEq(_rootHash, _testing.processProof(merkleProofData[i].proof, leaf));
            // case 2: bad leaf with account or amount are changed
            bytes32 badLeaf = keccak256(bytes.concat(keccak256(abi.encode(merkleProofData[i].account, merkleProofData[i].amount + 1))));
            assertNotEq(_rootHash, _testing.processProof(merkleProofData[i].proof, badLeaf));
            badLeaf = keccak256(bytes.concat(keccak256(abi.encode(address(uint160(merkleProofData[i].account) + 1), merkleProofData[i].amount))));
            assertNotEq(_rootHash, _testing.processProof(merkleProofData[i].proof, badLeaf));
        }

        // case 3: if proof is incorrect
        for (uint i = 1; i < merkleProofData.length; ++i) {
            bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(merkleProofData[i].account, merkleProofData[i].amount))));
            assertNotEq(_rootHash, _testing.processProof(merkleProofData[0].proof, leaf));
        }
    }

    function test_ProcessProofCalldata() external {
        MerkleProofData[] memory merkleProofData = abi.decode(_jsonMerkleProof.parseRaw(""), (MerkleProofData[]));
        for (uint i = 0; i < merkleProofData.length; ++i) {
            // case 1: correct leaf with correct proof
            bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(merkleProofData[i].account, merkleProofData[i].amount))));
            assertEq(_rootHash, _testing.processProofCalldata(merkleProofData[i].proof, leaf));
            // case 2: bad leaf with account or amount are changed
            bytes32 badLeaf = keccak256(bytes.concat(keccak256(abi.encode(merkleProofData[i].account, merkleProofData[i].amount + 1))));
            assertNotEq(_rootHash, _testing.processProofCalldata(merkleProofData[i].proof, badLeaf));
            badLeaf = keccak256(bytes.concat(keccak256(abi.encode(address(uint160(merkleProofData[i].account) + 1), merkleProofData[i].amount))));
            assertNotEq(_rootHash, _testing.processProofCalldata(merkleProofData[i].proof, badLeaf));
        }

        // case 3: if proof is incorrect
        for (uint i = 1; i < merkleProofData.length; ++i) {
            bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(merkleProofData[i].account, merkleProofData[i].amount))));
            assertNotEq(_rootHash, _testing.processProofCalldata(merkleProofData[0].proof, leaf));
        }
    }
}

2.2 verify(bytes32[] memory proof, bytes32 root, bytes32 leaf) && verifyCalldata(bytes32[] calldata proof, bytes32 root, bytes32 leaf)

  • verify(bytes32[] memory proof, bytes32 root, bytes32 leaf)：如果输入的leaf（叶子节点）及对应proof（bytes32[] memory）可以计算得到指定root，其有效性就可被证明返回true。这里的proof可从整棵merkle tree上获得——由leaf到root上所有兄弟节点的hash构成；
  • verifyCalldata(bytes32[] calldata proof, bytes32 root, bytes32 leaf)：如果输入的leaf（叶子节点）及对应proof（bytes32[] calldata）可以计算得到指定root，其有效性就可被证明返回true。这里的proof可从整棵merkle tree上获得——由leaf到root上所有兄弟节点的hash构成。

注：在利用leaf和proof计算root的过程中，假定leaves对和pre-images对都是经过排序的。verifyCalldata()可以认为是calldata参数版的verify()。

    function verify(
        bytes32[] memory proof,
        bytes32 root,
        bytes32 leaf
    ) internal pure returns (bool) {
        // 如果通过proof（bytes32[] memory）和leaf迭代计算出的hash值为root返回true，否则返回false
        return processProof(proof, leaf) == root;
    }

    function verifyCalldata(
        bytes32[] calldata proof,
        bytes32 root,
        bytes32 leaf
    ) internal pure returns (bool) {
        // 如果通过proof（bytes32[] calldata）和leaf迭代计算出的hash值为root返回true，否则返回false
        return processProofCalldata(proof, leaf) == root;
    }

foundry代码验证

contract MerkleProofTest is Test {
    using stdJson for string;

    struct MerkleProofData {
        address account;
        uint amount;
        bytes32[] proof;
    }

    string private _jsonMerkleTree = vm.readFile("test/utils/cryptography/data/merkle_tree.json");
    string private _jsonMerkleProof = vm.readFile("test/utils/cryptography/data/merkle_proof.json");
    bytes32 private _rootHash = _jsonMerkleTree.readBytes32(".merkle_root");
    MockMerkleProof private _testing = new MockMerkleProof(_rootHash);

    function test_Verify() external {
        // case 1: pass
        MerkleProofData[] memory merkleProofData = abi.decode(_jsonMerkleProof.parseRaw(""), (MerkleProofData[]));
        for (uint i = 0; i < merkleProofData.length; ++i) {
            assertTrue(_testing.verify(merkleProofData[i].proof, merkleProofData[i].account, merkleProofData[i].amount));
        }

        // case 2: return false if account or amount are changed
        for (uint i = 0; i < merkleProofData.length; ++i) {
            assertFalse(_testing.verify(merkleProofData[i].proof, merkleProofData[i].account, merkleProofData[i].amount + 1));
            assertFalse(_testing.verify(merkleProofData[i].proof, address(uint160(merkleProofData[i].account) + 1), merkleProofData[i].amount));
        }

        // case 3: return false if proof is incorrect
        for (uint i = 1; i < merkleProofData.length; ++i) {
            assertFalse(_testing.verify(merkleProofData[0].proof, merkleProofData[i].account, merkleProofData[i].amount));
        }
    }

    function test_VerifyCalldata() external {
        // case 1: pass
        MerkleProofData[] memory merkleProofData = abi.decode(_jsonMerkleProof.parseRaw(""), (MerkleProofData[]));
        for (uint i = 0; i < merkleProofData.length; ++i) {
            assertTrue(_testing.verifyCalldata(merkleProofData[i].proof, merkleProofData[i].account, merkleProofData[i].amount));
        }

        // case 2: return false if account or amount are changed
        for (uint i = 0; i < merkleProofData.length; ++i) {
            assertFalse(_testing.verifyCalldata(merkleProofData[i].proof, merkleProofData[i].account, merkleProofData[i].amount + 1));
            assertFalse(_testing.verifyCalldata(merkleProofData[i].proof, address(uint160(merkleProofData[i].account) + 1), merkleProofData[i].amount));
        }

        // case 3: return false if proof is incorrect
        for (uint i = 1; i < merkleProofData.length; ++i) {
            assertFalse(_testing.verifyCalldata(merkleProofData[0].proof, merkleProofData[i].account, merkleProofData[i].amount));
        }
    }
}

2.3 processMultiProof(bytes32[] memory proof, bool[] memory proofFlags, bytes32[] memory leaves) && processMultiProofCalldata(bytes32[] calldata proof, bool[] calldata proofFlags, bytes32[] memory leaves)

  • processMultiProof(bytes32[] memory proof, bool[] memory proofFlags, bytes32[] memory leaves)：通过多个leaves、对应proof（bytes32[] memory）以及proofFlags（bool[] memory）计算merkle tree的root。proofFlags为一个bool数组，用于指导上述过程；
  • processMultiProofCalldata(bytes32[] calldata proof, bool[] calldata proofFlags, bytes32[] memory leaves)：通过多个leaves、对应proof（bytes32[] calldata）以及proofFlags（bool[] calldata）计算merkle tree的root。proofFlags为一个bool数组，用于指导上述过程。

注：并不是所有的merkle tree都可以进行multiproofs的验证。前提是：1. 该merkle tree必须是完全树（complete tree），但不要求是完美树（perfect tree）2. 待证明的leaves的顺序需要与树中的顺序相反，即在最深层开始从右向左看并在下层继续。processMultiProofCalldata()可以认为是calldata参数版的processMultiProof()。

    function processMultiProof(
        bytes32[] memory proof,
        bool[] memory proofFlags,
        bytes32[] memory leaves
    ) internal pure returns (bytes32 merkleRoot) {
        // leavesLen为leaves个数
        uint256 leavesLen = leaves.length;
        // totalHashes为proofFlags长度
        uint256 totalHashes = proofFlags.length;

        // 检查proof有效性，即leaves个数 + proof个数 - 1等于totalHashes。否则revert
        require(leavesLen + proof.length - 1 == totalHashes, "MerkleProof: invalid multiproof");

        // 注：xxxPos变量为指向对应队列下一个消耗元素值的指针。通过xxx[xxxPos++]来返回对应队列中的值并递增指针（由此来模仿队列中的pop操作）
        // 内存中创建hashes动态数组，其长度为totalHashes
        bytes32[] memory hashes = new bytes32[](totalHashes);
        // 初始化三个队列的指针
        uint256 leafPos = 0;
        uint256 hashPos = 0;
        uint256 proofPos = 0;

        // 迭代的每一步中都使用两个值来计算下一个hash值：其中一个值是来自于“主队列”。如果leaves队列中还没有元素没有被使用，那么优先使用leaves队列中的元素。否则我们从hashes队列中获取下一个用于迭代计算的hash值。另一个值由proofFlags来决定是从leaves队列中取还是从proof队列中取
        for (uint256 i = 0; i < totalHashes; i++) {
            // 如果leafPos<leavesLen，说明leaves队列中还有元素未被使用，a为leafPos指向元素并递增指针leafPos。否则说明leaves队列中所有元素都被使用，a为hashes队列中hashPos指向值并递增指针hashPos
            bytes32 a = leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++];
            // 如果proofFlags[i]为false，b为proof队列中proofPos指向值并递增指针proofPos;
            // 如果proofFlags[i]为true且leafPos < leavesLen，b为leafPos指向元素并递增指针leafPos;
            // 如果proofFlags[i]为true且leafPos >= leavesLen，b为hashPos指向元素并递增指针hashPos;
            bytes32 b = proofFlags[i] ? leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++] : proof[proofPos++];
            // 计算bytes32对（a,b）的哈希值并存入数组hashes
            hashes[i] = _hashPair(a, b);
        }

    // 如果totalHashes>0，返回hashes中最后一个元素作为计算后的root
        if (totalHashes > 0) {
            return hashes[totalHashes - 1];
        } else if (leavesLen > 0) {
            // 如果totalHashes==0且leavesLen>0，返回leaves中的第一个元素作为计算后的root
            return leaves[0];
        } else {
            // 如果totalHashes==0且leavesLen==0，返回proof中的第一个元素作为计算后的root
            return proof[0];
        }
    }

    function processMultiProofCalldata(
        bytes32[] calldata proof,
        bool[] calldata proofFlags,
        bytes32[] memory leaves
    ) internal pure returns (bytes32 merkleRoot) {
        // leavesLen为leaves个数
        uint256 leavesLen = leaves.length;
        // totalHashes为proofFlags长度
        uint256 totalHashes = proofFlags.length;

        // 检查proof有效性，即leaves个数 + proof个数 - 1等于totalHashes。否则revert
        require(leavesLen + proof.length - 1 == totalHashes, "MerkleProof: invalid multiproof");

        // 注：xxxPos变量为指向对应队列下一个消耗元素值的指针。通过xxx[xxxPos++]来返回对应队列中的值并递增指针（由此来模仿队列中的pop操作）
        // 内存中创建hashes动态数组，其长度为totalHashes
        bytes32[] memory hashes = new bytes32[](totalHashes);
        // 初始化三个队列的指针
        uint256 leafPos = 0;
        uint256 hashPos = 0;
        uint256 proofPos = 0;

        // 迭代的每一步中都使用两个值来计算下一个hash值：其中一个值是来自于“主队列”。如果leaves队列中还有元素没有被使用，那么优先使用leaves队列中的元素。否则我们从hashes队列中获取下一个用于迭代计算的hash值。另一个值由proofFlags来决定是从主队列中取还是从proof队列中取
        for (uint256 i = 0; i < totalHashes; i++) {
            // 如果leafPos<leavesLen，说明leaves队列中还有元素未被使用，a为leafPos指向元素并递增指针leafPos。否则说明leaves队列中所有元素都被使用，a为hashes队列中hashPos指向值并递增指针hashPos
            bytes32 a = leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++];
            // 如果proofFlags[i]为false，b为proof队列中proofPos指向值并递增指针proofPos;
            // 如果proofFlags[i]为true且leafPos < leavesLen，b为leafPos指向元素并递增指针leafPos;
            // 如果proofFlags[i]为true且leafPos >= leavesLen，b为hashPos指向元素并递增指针hashPos
            bytes32 b = proofFlags[i] ? leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++] : proof[proofPos++];
            // 计算bytes32对（a,b）的哈希值并存入数组hashes
            hashes[i] = _hashPair(a, b);
        }

    // 如果totalHashes>0，返回hashes中最后一个元素作为计算后的root
        if (totalHashes > 0) {
            return hashes[totalHashes - 1];
        } else if (leavesLen > 0) {
            // 如果totalHashes==0且leavesLen>0，返回leaves中的第一个元素作为计算后的root
            return leaves[0];
        } else {
            // 如果totalHashes==0且leavesLen==0，返回proof中的第一个元素作为计算后的root
            return proof[0];
        }
    }

foundry代码验证

contract MerkleProofTest is Test {
    using stdJson for string;

    struct Leaf {
        address account;
        uint amount;
    }

    string private _jsonMerkleTree = vm.readFile("test/utils/cryptography/data/merkle_tree.json");
    string private _jsonMerkleMultiProof = vm.readFile("test/utils/cryptography/data/merkle_multi_proof.json");
    bytes32 private _rootHash = _jsonMerkleTree.readBytes32(".merkle_root");
    MockMerkleProof private _testing = new MockMerkleProof(_rootHash);

    function test_ProcessMultiProof() external {
        bytes32[] memory proof = _jsonMerkleMultiProof.readBytes32Array(".proof");
        bool[] memory proofFlags = _jsonMerkleMultiProof.readBoolArray(".proof_flags");
        (address[] memory accounts, uint[] memory amounts) = _getAccountsAndAmounts();
        bytes32[] memory leaves = new bytes32[](accounts.length);
        for (uint i = 0; i < leaves.length; ++i) {
            leaves[i] = keccak256(bytes.concat(keccak256(abi.encode(accounts[i], amounts[i]))));
        }

        // case 1: correct leaves with correct proof
        assertEq(_rootHash, _testing.processMultiProof(proof, proofFlags, leaves));

        // case 2: bad leaves with account or amount are changed
        bytes32[] memory badLeaves = new bytes32[](leaves.length);
        for (uint i = 0; i < badLeaves.length; ++i) {
            badLeaves[i] = leaves[i];
        }
        badLeaves[1] = keccak256(bytes.concat(keccak256(abi.encode(accounts[1], amounts[1] + 1))));
        assertNotEq(_rootHash, _testing.processMultiProof(proof, proofFlags, badLeaves));
        badLeaves[1] = keccak256(bytes.concat(keccak256(abi.encode(address(uint160(accounts[1]) + 1), amounts[1]))));
        assertNotEq(_rootHash, _testing.processMultiProof(proof, proofFlags, badLeaves));

        // case 3: if proof is incorrect
        proof[1] = bytes32(uint(proof[1]) + 1);
        assertNotEq(_rootHash, _testing.processMultiProof(proof, proofFlags, leaves));

        // case 4: if proof flags are incorrect
        proof = _jsonMerkleMultiProof.readBytes32Array(".proof");
        proofFlags[0] = !proofFlags[0];
        proofFlags[1] = !proofFlags[1];
        assertNotEq(_rootHash, _testing.processMultiProof(proof, proofFlags, leaves));

        // case 5: revert with invalid multiproof
        proofFlags = _jsonMerkleMultiProof.readBoolArray(".proof_flags");
        bytes32[] memory incompleteLeaves = new bytes32[](leaves.length - 1);
        for (uint i = 0; i < leaves.length - 1; ++i) {
            incompleteLeaves[i] = leaves[i];
        }
        vm.expectRevert("MerkleProof: invalid multiproof");
        _testing.processMultiProof(proof, proofFlags, incompleteLeaves);
    }

    function test_ProcessMultiProofCalldata() external {
        bytes32[] memory proof = _jsonMerkleMultiProof.readBytes32Array(".proof");
        bool[] memory proofFlags = _jsonMerkleMultiProof.readBoolArray(".proof_flags");
        (address[] memory accounts, uint[] memory amounts) = _getAccountsAndAmounts();
        bytes32[] memory leaves = new bytes32[](accounts.length);
        for (uint i = 0; i < leaves.length; ++i) {
            leaves[i] = keccak256(bytes.concat(keccak256(abi.encode(accounts[i], amounts[i]))));
        }

        // case 1: correct leaves with correct proof
        assertEq(_rootHash, _testing.processMultiProofCalldata(proof, proofFlags, leaves));

        // case 2: bad leaves with account or amount are changed
        bytes32[] memory badLeaves = new bytes32[](leaves.length);
        for (uint i = 0; i < badLeaves.length; ++i) {
            badLeaves[i] = leaves[i];
        }
        badLeaves[1] = keccak256(bytes.concat(keccak256(abi.encode(accounts[1], amounts[1] + 1))));
        assertNotEq(_rootHash, _testing.processMultiProofCalldata(proof, proofFlags, badLeaves));
        badLeaves[1] = keccak256(bytes.concat(keccak256(abi.encode(address(uint160(accounts[1]) + 1), amounts[1]))));
        assertNotEq(_rootHash, _testing.processMultiProofCalldata(proof, proofFlags, badLeaves));

        // case 3: if proof is incorrect
        proof[1] = bytes32(uint(proof[1]) + 1);
        assertNotEq(_rootHash, _testing.processMultiProofCalldata(proof, proofFlags, leaves));

        // case 4: if proof flags are incorrect
        proof = _jsonMerkleMultiProof.readBytes32Array(".proof");
        proofFlags[0] = !proofFlags[0];
        proofFlags[1] = !proofFlags[1];
        assertNotEq(_rootHash, _testing.processMultiProofCalldata(proof, proofFlags, leaves));

        // case 5: revert with invalid multiproof
        proofFlags = _jsonMerkleMultiProof.readBoolArray(".proof_flags");
        bytes32[] memory incompleteLeaves = new bytes32[](leaves.length - 1);
        for (uint i = 0; i < leaves.length - 1; ++i) {
            incompleteLeaves[i] = leaves[i];
        }
        vm.expectRevert("MerkleProof: invalid multiproof");
        _testing.processMultiProofCalldata(proof, proofFlags, incompleteLeaves);
    }

    function _getAccountsAndAmounts() private view returns (address[] memory, uint[] memory){
        Leaf[] memory leaves = abi.decode(_jsonMerkleMultiProof.parseRaw(".leaves"), (Leaf[]));
        address[] memory accounts = new address[](leaves.length);
        uint[] memory amounts = new uint[](leaves.length);
        for (uint i = 0; i < leaves.length; ++i) {
            accounts[i] = leaves[i].account;
            amounts[i] = leaves[i].amount;
        }

        return (accounts, amounts);
    }
}

2.4 multiProofVerify(bytes32[] memory proof, bool[] memory proofFlags, bytes32 root, bytes32[] memory leaves) && multiProofVerifyCalldata(bytes32[] calldata proof, bool[] calldata proofFlags, bytes32 root, bytes32[] memory leaves)

  • multiProofVerify(bytes32[] memory proof, bool[] memory proofFlags, bytes32 root, bytes32[] memory leaves)：如果通过输入的leaves（叶子节点数组）及对应proof（bytes32[] memory）和proofFlags（bool[] memory）可以计算得到指定root，其leaves有效性就可被证明返回true。注：并不是所有的merkle tree都可以进行multiproofs的验证。具体细节参见函数processMultiProof()；
  • multiProofVerifyCalldata(bytes32[] calldata proof, bool[] calldata proofFlags, bytes32 root, bytes32[] memory leaves)：如果通过输入的leaves（叶子节点数组）及对应proof（bytes32[] calldata）和proofFlags（bool[] calldata）可以计算得到指定root，其leaves有效性就可被证明返回true。注：并不是所有的merkle tree都可以进行multiproofs的验证。具体细节参见函数processMultiProofCalldata()
    function multiProofVerify(
        bytes32[] memory proof,
        bool[] memory proofFlags,
        bytes32 root,
        bytes32[] memory leaves
    ) internal pure returns (bool) {
        // 如果通过proof（bytes32[] memory）、proofFlags（bool[] memory）和leaves（bytes32[] memory）迭代计算出的hash值为root返回true，否则返回false
        return processMultiProof(proof, proofFlags, leaves) == root;
    }

    function multiProofVerifyCalldata(
        bytes32[] calldata proof,
        bool[] calldata proofFlags,
        bytes32 root,
        bytes32[] memory leaves
    ) internal pure returns (bool) {
        // 如果通过proof（bytes32[] calldata）、proofFlags（bool[] calldata）和leaves（bytes32[] memory）迭代计算出的hash值为root返回true，否则返回false
        return processMultiProofCalldata(proof, proofFlags, leaves) == root;
    }
}

foundry代码验证

contract MerkleProofTest is Test {
    using stdJson for string;

    struct Leaf {
        address account;
        uint amount;
    }

    string private _jsonMerkleTree = vm.readFile("test/utils/cryptography/data/merkle_tree.json");
    string private _jsonMerkleMultiProof = vm.readFile("test/utils/cryptography/data/merkle_multi_proof.json");
    bytes32 private _rootHash = _jsonMerkleTree.readBytes32(".merkle_root");
    MockMerkleProof private _testing = new MockMerkleProof(_rootHash);

    function test_MultiProofVerify() external {
        // case 1: pass
        bytes32[] memory proof = _jsonMerkleMultiProof.readBytes32Array(".proof");
        bool[] memory proofFlags = _jsonMerkleMultiProof.readBoolArray(".proof_flags");
        (address[] memory accounts, uint[] memory amounts) = _getAccountsAndAmounts();
        assertTrue(_testing.multiProofVerify(
            proof,
            proofFlags,
            accounts,
            amounts
        ));

        // case 2: return false with account changed
        accounts[0] = address(uint160(accounts[0]) + 1);
        assertFalse(_testing.multiProofVerify(
            proof,
            proofFlags,
            accounts,
            amounts
        ));

        // case 3: return false with account changed
        (accounts, amounts) = _getAccountsAndAmounts();
        amounts[0] += 1;
        assertFalse(_testing.multiProofVerify(
            proof,
            proofFlags,
            accounts,
            amounts
        ));

        // case 4: return false with proof flags changed
        (accounts, amounts) = _getAccountsAndAmounts();
        proofFlags[0] = !proofFlags[0];
        proofFlags[1] = !proofFlags[1];
        assertFalse(_testing.multiProofVerify(
            proof,
            proofFlags,
            accounts,
            amounts
        ));

        // case 5: return false with the order of proof changed
        proofFlags = _jsonMerkleMultiProof.readBoolArray(".proof_flags");
        bytes32 tmpBytes32 = proof[0];
        proof[0] = proof[1];
        proof[1] = tmpBytes32;
        assertFalse(_testing.multiProofVerify(
            proof,
            proofFlags,
            accounts,
            amounts
        ));
    }

    function test_MultiProofVerifyCalldata() external {
        // case 1: pass
        bytes32[] memory proof = _jsonMerkleMultiProof.readBytes32Array(".proof");
        bool[] memory proofFlags = _jsonMerkleMultiProof.readBoolArray(".proof_flags");
        (address[] memory accounts, uint[] memory amounts) = _getAccountsAndAmounts();
        assertTrue(_testing.multiProofVerifyCalldata(
            proof,
            proofFlags,
            accounts,
            amounts
        ));

        // case 2: return false with account changed
        accounts[0] = address(uint160(accounts[0]) + 1);
        assertFalse(_testing.multiProofVerifyCalldata(
            proof,
            proofFlags,
            accounts,
            amounts
        ));

        // case 3: return false with account changed
        (accounts, amounts) = _getAccountsAndAmounts();
        amounts[0] += 1;
        assertFalse(_testing.multiProofVerifyCalldata(
            proof,
            proofFlags,
            accounts,
            amounts
        ));

        // case 4: return false with proof flags changed
        (accounts, amounts) = _getAccountsAndAmounts();
        proofFlags[0] = !proofFlags[0];
        proofFlags[1] = !proofFlags[1];
        assertFalse(_testing.multiProofVerifyCalldata(
            proof,
            proofFlags,
            accounts,
            amounts
        ));

        // case 5: return false with the order of proof changed
        proofFlags = _jsonMerkleMultiProof.readBoolArray(".proof_flags");
        bytes32 tmpBytes32 = proof[0];
        proof[0] = proof[1];
        proof[1] = tmpBytes32;
        assertFalse(_testing.multiProofVerifyCalldata(
            proof,
            proofFlags,
            accounts,
            amounts
        ));
    }
}

ps:\ 本人热爱图灵，热爱中本聪，热爱V神。 以下是我个人的公众号，如果有技术问题可以关注我的公众号来跟我交流。 同时我也会在这个公众号上每周更新我的原创文章，喜欢的小伙伴或者老伙计可以支持一下！ 如果需要转发，麻烦注明作者。十分感谢！

1.jpeg

公众号名称：后现代泼痞浪漫主义奠基人

点赞 2
收藏 1
分享
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。
108 订阅 68 篇文章

0 条评论

请先 登录 后评论
Michael.W
Michael.W
0x93E7...0000
狂热的区块链爱好者

Michael.W

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！