使用js实现merkle树

实现 Merkle 树的过程需要以下几个步骤：

1. 定义节点类

首先，我们需要定义一个节点类，该类包含以下属性：

- `left`: 左子树的哈希值
- `right`: 右子树的哈希值
- `parent`: 父节点的哈希值
- `data`: 叶子节点存储的数据

class Node {
  constructor(left, right, parent = null, data = null) {
    this.left = left;
    this.right = right;
    this.parent = parent;
    this.data = data;
  }

  // 计算节点的哈希值
  getHash() {
    return sha256(this.left + this.right);
  }

  // 判断节点是否为叶子节点
  isLeaf() {
    return this.left === null && this.right === null;
  }
}

2. 构建叶子节点

其次，我们需要构建叶子节点，每个叶子节点代表一个数据块，该节点的 `left` 和 `right` 属性均为 `null`。

function buildLeaves(dataList) {
  return dataList.map(data => new Node(null, null, null, data));
}

3. 构建 Merkle 树

接着，我们需要构建 Merkle 树，该过程利用叶子节点逐层向上构建，直到根节点。

function buildTree(leaves) {
  let nodes = leaves;

  // 处理节点数为奇数的情况
  if (nodes.length % 2 !== 0) {
    nodes.push(new Node(null, null, null, null));
  }

  while (nodes.length > 1) {
    const parents = [];

    for (let i = 0; i < nodes.length; i += 2) {
      const left = nodes[i];
      const right = nodes[i + 1];
      const parent = new Node(left.getHash(), right.getHash(), null, null);
      left.parent = parent.getHash();
      right.parent = parent.getHash();
      parents.push(parent);
    }

    nodes = parents;
  }

  return nodes[0];
}

4. 计算 Merkle 树根节点哈希值

最后，我们需要计算 Merkle 树的根节点哈希值，该值即为整个 Merkle 树的哈希值。

function calculateRootHash(leaves) {
  const root = buildTree(buildLeaves(leaves));
  return root.getHash();
}

完整代码如下：

class Node {
  constructor(left, right, parent = null, data = null) {
    this.left = left;
    this.right = right;
    this.parent = parent;
    this.data = data;
  }

  getHash() {
    return sha256(this.left + this.right);
  }

  isLeaf() {
    return this.left === null && this.right === null;
  }
}

function buildLeaves(dataList) {
  return dataList.map(data => new Node(null, null, null, data));
}

function buildTree(leaves) {
  let nodes = leaves;

  if (nodes.length % 2 !== 0) {
    nodes.push(new Node(null, null, null, null));
  }

  while (nodes.length > 1) {
    const parents = [];

    for (let i = 0; i < nodes.length; i += 2) {
      const left = nodes[i];
      const right = nodes[i + 1];
      const parent = new Node(left.getHash(), right.getHash(), null, null);
      left.parent = parent.getHash();
      right.parent = parent.getHash();
      parents.push(parent);
    }

    nodes = parents;
  }

  return nodes[0];
}

function calculateRootHash(leaves) {
  const root = buildTree(buildLeaves(leaves));
  return root.getHash();
}