Merkle(Hash) Tree Implementation

merkle_tree.js

class MerkleTree {
    constructor(leaves, concatHash) {
        this.leaves = leaves;
        this.concatHash = concatHash;
    }
    
    getRoot() {
        return this._buildHashRoot(this.leaves);
    }
    
    getProof(leafIndex) {
      let proof = []
      let layer = this.leaves;
      let index = leafIndex;
      while(layer.length > 1) {
          const indexOfPair = this.getIndexOfPairNode(index);
          if(layer[indexOfPair]) {
              if(this.isLeftNode(index)) {
                  proof.push({data: layer[indexOfPair], left: false})
              }else {
                  proof.push({data: layer[indexOfPair], left: true})
              }
          }
          // build next layer of merkle tree
          layer = this._buildLayer(layer);
          index = Math.floor(index /2);
      }
      return proof;
    }
    
     isLeftNode(index) {
        return index %2 == 0;
    }

    getIndexOfPairNode(index) {
        if(this.isLeftNode(index)) {
            return index+1;
        }
        return index-1;
    }

    _buildHashRoot(leaves) {
        if(leaves.length == 1) return leaves[0];
        const layer = this._buildLayer(leaves);
        return this._buildHashRoot(layer);
    }
    
    _buildLayer(leaves) {
        let result = [];
        for(let i = 0;i < leaves.length;i++) {
            if(i % 2 == 0) {
            const leftNode = leaves[i];
            const rightNode = leaves[i+1];
            if(rightNode) {
                const hash = this.concatHash(leftNode, rightNode);
                result.push(hash);
            } else {
                // move the leaf to the upper layer until we find a pair to combine with
                  result.push(leftNode);
                }
            }
        }
        return result;
    }
}

function verifyProof(node, root, proof, concatHash) {
    let hash = proof[0].left ? concatHash(proof[0].data, node) : concatHash(node, proof[0].data);
    for(let i = 1;i< proof.length; i++) {
        if(proof[i].left) {
            hash = concatHash(proof[i].data, hash);
        } else {
            hash = concatHash(hash, proof[i].data);
        }
    }
    return hash === root
}

module.exports = MerkleTree;