离线数据完整性的默克尔证明

1const ethers = require("ethers")

1// 需要我们验证其完整性的原始数据。前两个字节
2// 是用户标识符，后两个字节是该
3// 用户当前拥有的代币数量。
4const dataArray = [
5  0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,
6  0xface0070, 0xbad00080, 0x060d0091,
7]

1// 作为 BigInt 的哈希值数组
2const hashArray = dataArray

1// 在哈希函数所需的字符串与
2// 我们在其他任何地方使用的 BigInt 之间进行转换。
3const hash = (x) =>
4  BigInt(ethers.utils.keccak256("0x" + x.toString(16).padStart(64, 0)))

1// 对称哈希一对值，这样我们就不必关心顺序是否颠倒。
2const pairHash = (a, b) => hash(hash(a) ^ hash(b))

1// The value to denote that a certain branch is empty, doesn't
2// have a value
3const empty = 0n

1// 通过按顺序获取每对值的哈希，
2// 计算哈希数组在树中的上一层
3const oneLevelUp = (inputArray) => {
4  var result = []
5  var inp = [...inputArray] // 避免覆盖输入 // 如有必要，添加一个空值（我们需要所有的叶子都 // 配对）
6
7  if (inp.length % 2 === 1) inp.push(empty)
8
9  for (var i = 0; i < inp.length; i += 2)
10    result.push(pairHash(inp[i], inp[i + 1]))
11
12  return result
13} // oneLevelUp
显示全部

1const getMerkleRoot = (inputArray) => {
2  var result
3
4  result = [...inputArray] // 沿树向上，直到只剩一个值，这个值就是 // 根。 // // 如果某一层有奇数个条目， // oneLevelUp 中的代码会添加一个空值，因此如果我们有（例如） // 10 个叶子，那么第二层将有 5 个分支，第三层 // 有 3 个，第四层有 2 个，根是第五个
5
6  while (result.length > 1) result = oneLevelUp(result)
7
8  return result[0]
9}
显示全部

1// 默克尔证明包含与之哈希的条目
2// 列表的值。因为我们使用了对称哈希函数，我们不
3// 需要条目的位置来验证证明，只需要用它来创建证明
4const getMerkleProof = (inputArray, n) => {
5    var result = [], currentLayer = [...inputArray], currentN = n
6
7    // 直到我们到达顶部
8    while (currentLayer.length > 1) {
9        // 没有奇数长度的层
10        if (currentLayer.length % 2)
11            currentLayer.push(empty)
12
13        result.push(currentN % 2
14               // 如果 currentN 是奇数，则将其之前的值添加到证明中
15            ? currentLayer[currentN-1]
16               // 如果是偶数，则添加其后的值
17            : currentLayer[currentN+1])
18
显示全部

1        // 移动到上一层
2        currentN = Math.floor(currentN/2)
3        currentLayer = oneLevelUp(currentLayer)
4    }   // while currentLayer.length > 1
5
6    return result
7}   // getMerkleProof

1//SPDX-License-Identifier: Public Domain
2pragma solidity ^0.8.0;
3
4import "hardhat/console.sol";
复制

1
2contract MerkleProof {
3    uint merkleRoot;
4
5    function getRoot() public view returns (uint) {
6      return merkleRoot;
7    }
8
9    // 极不安全，在生产代码中，对
10    // 此函数的访问权限必须受到严格限制，可能仅限于
11    // 所有者
12    function setRoot(uint _merkleRoot) external {
13      merkleRoot = _merkleRoot;
14    }   // setRoot
显示全部
复制

1    function hash(uint _a) internal pure returns(uint) {
2      return uint(keccak256(abi.encode(_a)));
3    }
4
5    function pairHash(uint _a, uint _b) internal pure returns(uint) {
6      return hash(hash(_a) ^ hash(_b));
7    }
复制

1    // 验证默克尔证明
2    function verifyProof(uint _value, uint[] calldata _proof)
3        public view returns (bool) {
4      uint temp = _value;
5      uint i;
6
7      for(i=0; i<_proof.length; i++) {
8        temp = pairHash(temp, _proof[i]);
9      }
10
11      return temp == merkleRoot;
12    }
13
14}  // MarkleProof
显示全部
复制