elliptictree.js

const crypto = require('crypto');
const EC = require('elliptic').ec;
const ec = new EC('secp256k1');

/**
 * @dev MerkleTree
 */
class MerkleTree {

  /**
   * @dev constructor
   * @param {*} leaves 
   */
  constructor(leaves) {
    if(!Array.isArray(leaves) || leaves.length < 1) {
      throw new Error('invalid leaves');
    }

    const depth = Math.ceil(Math.log(leaves.length) / Math.log(2));
    if(depth > 20) {
      throw new Error('depth must be 20 or less');
    }

    const layer = leaves.concat(
      Array.from(
        Array(Math.pow(2, depth) - leaves.length),
        () => getHash()));

    this.leaves = layer;
    this.layers = [layer].concat(this.createLayers(layer));
  }

  createLayers(nodes) {
    if(nodes.length <= 1) {
      return [];
    }

    const treeLevel = [];
    for(let i = 0; i < nodes.length; i += 2) {
      const left = nodes[i];
      const right = nodes[i + 1];
      treeLevel.push(left.add(right));
    }

    if(nodes.length % 2 === 1) {
      treeLevel.push(nodes[nodes.length - 1]);
    }

    return [treeLevel].concat(this.createLayers(treeLevel));
  }

  getLeaves() {
    return this.leaves;
  }

  root() {
    const rootLayer = this.layers[this.layers.length - 1];
    if(rootLayer.length != 1) {
      throw new Error('invalid root');
    }
    return rootLayer[0];
  }

  proof(index) {
    if(index < 0) {
      throw new Error('invalid leaf');
    }

    const proof = []
    if(index <= this.getLeaves().length) {
      for(let i = 0; i < this.layers.length - 1; i++) {
        let layerIndex = (index % 2 === 0) ? (index + 1) : (index - 1);
        index = Math.floor(index / 2);
        proof.push(this.layers[i][layerIndex]);
      }
    }
    return proof;
  }

  static verify(value, index, root, proof) {
    if(!value || !root) {
      return false;
    }

    let hash = value;
    for(let i = 0; i < proof.length; i++) {
      const node = proof[i];
      const buf = (index % 2 === 0) ? ([hash, node]) : ([node, hash]);
      hash = buf[0].add(buf[1]);
      index = Math.floor(index / 2);
    }

    return hash.eq(root);
  }
}

function sha256(message) {
  const hash = crypto.createHash('sha256');
  hash.update(message);
  return hash.digest();
}

function getHash(l, index) {
  return ec.keyFromPrivate(sha256(Buffer.from([l]))).getPublic().mul(index+1)
}

// coin0 is in
// coin1 is not in
// coin2 is in
// coin3 is not in
const tree1 = new MerkleTree([20, 0, 40, 0].map(getHash));
const tree1Invalid = new MerkleTree([0, 10, 40, 0].map(getHash));
// coin0 is in
// coin1 is not in
// coin2 is in
// coin3 is in
const tree2 = new MerkleTree([22, 0, 41, 60].map(getHash));

function combine(a, b) {
  return (a.add(b));//.mul(2);
}

function getZero(coinId) {
  return getHash(0, coinId);
}

const root1 = tree1.root();
const root2 = tree2.root();
const proof1 = tree1.proof(1);
const invalidProof1 = [root1.add(combine(getZero(0), combine(getHash(40, 2), getHash(0, 3))).neg()) , combine(getHash(40, 2), getHash(0, 3))]
//const invalidProof1 = tree1Invalid.proof(0);
const proof2 = tree2.proof(1);

console.log('tree 1にcoin1は無い')
console.log(MerkleTree.verify(getZero(1), 1, root1, proof1));
console.log('tree 2にcoin1は無い')
console.log(MerkleTree.verify(getZero(1), 1, root2, proof2));
console.log('tree 1にcoin0はある')
console.log(MerkleTree.verify(getZero(0), 0, root1, invalidProof1));

const sumRoot = combine(root1, root2);
const sumProof = proof1.map((p1, index) => {
  return combine(p1, proof2[index]);
})
const invalidSumProof = invalidProof1.map((p1, index) => {
  return combine(p1, proof2[index]);
})

const zeroHash1 = combine(getZero(1), getZero(1))
const zeroHash0 = combine(getZero(0), getZero(0))

console.log('tree 1にもtree 2にもcoin1はない')
console.log('sum verify', MerkleTree.verify(zeroHash1, 1, sumRoot, sumProof));

// should be false
console.log('tree 1かtree 2にcoin0はある')
console.log('sum verify', MerkleTree.verify(zeroHash0, 0, sumRoot, invalidSumProof));