MerkleProof库提供了用于验证merkle树proof的工具函数。在生成merkle树和对应proof时应当避免使用64字节长度的leaf(进行hash之前)或避免使用非keccak256的哈希函数(进行leaf的hash计算)。这是因为树中经排序的内部节点的拼接可以被重新解释为leaf值。
[openzeppelin]:v4.8.3,[forge-std]:v1.5.6
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
封装MerkleProof library成为一个可调用合约:
// 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测试合约:
测试数据:
测试数据的生成脚本:
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],
}
}),
}))
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));
}
}
}
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));
}
}
}
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);
}
}
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神。 以下是我个人的公众号,如果有技术问题可以关注我的公众号来跟我交流。 同时我也会在这个公众号上每周更新我的原创文章,喜欢的小伙伴或者老伙计可以支持一下! 如果需要转发,麻烦注明作者。十分感谢!
公众号名称:后现代泼痞浪漫主义奠基人
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!