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

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

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
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

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