实体与以太不匹配的默克尔树

Question

我正在把我的测试从特弗莱移植到铸造。我正在重新编写以前的JavaScript中的测试。我对merkle有一个问题，特别是对于相同的输入，我得到不同的根，由Solidity和JavaScript计算。

以下是我的JavaScript代码：

addresses.json

{   
    "0x0000000000000000000000000000000000000101": "1",
    "0x0000000000000000000000000000000000000102": "1",
    "0x0000000000000000000000000000000000000103": "2"
}

JavaScript：

const addresses = require('./addresses.json');
const ethers = require('ethers');
const utils = ethers.utils;
const { MerkleTree } = require('merkletreejs');
const { keccak256 } = require('@ethersproject/keccak256');

function initialHashListToken(Address, allowance) {
  return ethers.utils.hexlify(Buffer.from(ethers.utils.solidityKeccak256(['address', 'string'],[Address, allowance]).slice(2),'hex'));
}

const Leaves = Object.entries(addresses).map(([key, value]) => initialHashListToken(key,value));
const Tree = new MerkleTree(Leaves, keccak256, {sortPairs: true});

console.log(Leaves);
console.log(Tree.getHexRoot());

退货:树叶

[
  '0x831692e101b997ce3fafd456dd2860ede5fb83f624c5e38d847b5222684506c4',
  '0xce3e9450596ea34ab931b277b05bd0155f32a0546a166e3952f1bacfb78d5a44',
  '0x7e8fc653196ddb81e205dbea866d82f2cb83d03f8f2f86f65d60bb1b61438b0f'
]

Tree.getHexRoot()

0xa7e0f57b192bf4dea62998b2bad8ff302ed2041d2d6548677af6f6bd4e2727d6

在坚实的环境中，我使用的是模糊库(https://github.com/dmfxyz/murky)。

address alice = address(0x101);
address bob = address(0x102);
address chris = address(0x103);

Merkle m = new Merkle();

bytes32[] memory data = new bytes32[](3);

data[0] = keccak256(abi.encodePacked(alice, Strings.toString(1))); // alice
data[1] = keccak256(abi.encodePacked(bob, Strings.toString(1))); // bob
data[2] = keccak256(abi.encodePacked(chris, Strings.toString(2))); // chris

bytes32 root = m.getRoot(data);

在原木上，我可以看到这棵树坚实的叶子是：

[0x831692e101b997ce3fafd456dd2860ede5fb83f624c5e38d847b5222684506c4, 0xce3e9450596ea34ab931b277b05bd0155f32a0546a166e3952f1bacfb78d5a44, 0x7e8fc653196ddb81e205dbea866d82f2cb83d03f8f2f86f65d60bb1b61438b0f]

根部是

0x1a7a6f178b6dedee79a956c5659034f781fcb3c11875ae4a3d5b56d528c1271e

叶子似乎与JavaScript实现相同，只是它们不是字符串。秩序似乎也是一样的。当我粘贴十六进制值数组并将其作为JavaScript中的树的叶子传递时，就会得到一个与坚固根不匹配的不同的根。

0x631bfae0b985936a3bc7b21125c8a6cb779441ca465f6bdd7135b57a608dfe8c

为什么价值观是不同的？

Answer 1

问题是，在模糊库中，如果叶节点数为奇数，则在末尾添加一个0节点，使节点数为偶数。https://github.com/dmfxyz/murky/blob/103da4902c55353fdd7a7366e057fbacce226d26/src/common/MurkyBase.sol#L84

但是merkletreejs库实现了比特币merkle树(这是稳健merkle树的正确方法)，它复制最后一个叶节点，而不是添加一个0节点。https://github.com/miguelmota/merkletreejs/blob/893ce99a4a98aab8836852bb59cd582afe489193/src/MerkleTree.ts#L136

由于最后一个叶节点不同，根节点也不同。