Skip to content

Instantly share code, notes, and snippets.

@johnnieskywalker

johnnieskywalker/index.js

Last active March 27, 2024 18:00
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save johnnieskywalker/12b879a602ef33334d51e9cfa545c7f3 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save johnnieskywalker/12b879a602ef33334d51e9cfa545c7f3 to your computer and use it in GitHub Desktop.
Download ZIP
Merkle with proofs
Raw
index.js
class MerkleTree {
constructor(leaves, concat) {
this.leaves = leaves;
this.concat = concat;
this.tree = [];
this.buildTree();
}
buildTree() {
let currentLevel = this.leaves;
while (currentLevel.length > 1) {
const nextLevel = [];
for (let i = 0; i < currentLevel.length; i += 2) {
const left = currentLevel[i];
const right = i + 1 < currentLevel.length ? currentLevel[i + 1] : null;
if (right) {
nextLevel.push(this.concat(left, right));
} else {
nextLevel.push(left);
}
}
this.tree.push(currentLevel);
currentLevel = nextLevel;
}
this.tree.push(currentLevel); // Add the root
}
getRoot() {
return this.tree[this.tree.length - 1][0];
}
getProof(index) {
let proof = [];
// Iterate through each layer to construct the proof.
for (let layer = 0; layer < this.tree.length - 1; layer++) {
const layerNodes = this.tree[layer];
// Determine the sibling's index: if our node is at an even index, its sibling is at index + 1, otherwise index - 1.
const pairIndex = (index % 2 === 0) ? index + 1 : index - 1;
if (pairIndex < layerNodes.length) {
proof.push({
// Include the sibling's data.
data: layerNodes[pairIndex],
// If our node is at an even index, then it is a left node, and its sibling is right (left: false).
// If our node is at an odd index, then it is a right node, and its sibling is left (left: true).
left: index % 2 !== 0,
});
}
// Move up to the parent node in the next layer.
index = Math.floor(index / 2);
}
return proof;
}
}
module.exports = MerkleTree;
Raw
testProof.js
const {assert} = require("chai");
const {hashProof, sha256, concatHash, concatLetters} = require('./testUtil');
const MerkleTree = require('../index');
describe('merkle proof', function() {
const leaves = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'];
const root = 'eb100814abc896ab18bcf6c37b6550eeadeae0c312532286a4cf4be132ace526';
const hashTree = new MerkleTree(leaves.map(sha256), concatHash);
const lettersTree = new MerkleTree(leaves, concatLetters);
describe('for each leaf', function() {
leaves.forEach((leaf, i) => {
it(`should return a proof that calculates the root from leaf ${leaves[i]}`, function() {
const proof = hashTree.getProof(i);
const hashedProof = hashProof(leaf, proof).toString('hex');
if(hashedProof !== root) {
const lettersProof = lettersTree.getProof(i);
console.log(
"The resulting hash of your proof is wrong. \n" +
`We were expecting: ${root} \n` +
`We received: ${hashedProof} \n` +
`In ${leaves.join('')} Merkle tree, the proof of ${leaves[i]} you gave us is: \n` +
`${JSON.stringify(lettersProof, null, 2)}`
);
}
assert.equal(hashedProof, root);
});
});
});
});
Raw
testUtil.js
const crypto = require("crypto");
const {assert} = require("chai");
// use the crypto module to create a sha256 hash from the data passed in
function sha256(data) {
return crypto.createHash('sha256').update(data).digest();
}
// the concat function we use to hash together merkle leaves
function concatHash(left, right) {
if (!left) throw new Error("The concat function expects two hash arguments, the first was not received.");
if (!right) throw new Error("The concat function expects two hash arguments, the second was not received.");
return sha256(Buffer.concat([left, right]));
}
// the concat function we use to show the merkle root calculation
function concatLetters(left, right) {
return `Hash(${left} + ${right})`;
}
// given a proof, finds the merkle root
function hashProof(node, proof) {
let data = sha256(node);
for (let i = 0; i < proof.length; i++) {
const buffers = (proof[i].left) ? [proof[i].data, data] : [data, proof[i].data];
data = sha256(Buffer.concat(buffers));
}
return data;
}
module.exports = {concatHash, concatLetters, hashProof, sha256}
Raw
testVerify.js
const {assert} = require("chai");
const MerkleTree = require('../index');
const verify = require('../verify');
const concat = (a, b) => `Hash(${a} + ${b})`;
describe('merkle proof verification', function() {
describe('a given merkle tree', function() {
const leaves = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'];
const root = "Hash(Hash(Hash(Hash(A + B) + Hash(C + D)) + Hash(Hash(E + F) + Hash(G + H))) + Hash(Hash(I + J) + K))";
let tree;
beforeEach(() => {
tree = new MerkleTree(leaves.slice(0), concat);
});
describe('untampered proofs', function() {
leaves.forEach((_, i) => {
it(`should verify the proof for leaf index ${i}`, function() {
const proof = tree.getProof(i);
assert.equal(verify(proof, leaves[i], root, concat), true);
});
});
});
describe('tampered proofs', function() {
describe('verifying a different node with a proof', function() {
it('should not verify the proof', function() {
let proof = tree.getProof(2);
assert.equal(verify(proof, leaves[3], root, concat), false);
});
});
describe('verifying a different root', function() {
it('should not verify the proof', function() {
let proof = tree.getProof(2);
const badRoot = "Hash(Hash(Hash(Hash(A + C) + Hash(C + D)) + Hash(Hash(E + F) + Hash(G + H))) + Hash(Hash(I + J) + K))";
assert.equal(verify(proof, leaves[2], badRoot, concat), false);
});
});
describe('flipping a nodes position', function() {
it('should not verify the proof', function() {
let proof = tree.getProof(3);
proof[1].left = !proof[1].left;
assert.equal(verify(proof, leaves[3], root, concat), false);
});
});
describe('editing a hash', function() {
it('should not verify the proof', function() {
let proof = tree.getProof(5);
proof[2].data = "Q";
assert.equal(verify(proof, leaves[5], root, concat), false);
});
});
});
});
});
Raw
verify.js
function verifyProof(proof, node, root, concat) {
let currentNode = node;
for (let i = 0; i < proof.length; i++) {
const proofElement = proof[i];
// If the current node is a left child, concatenate it with the proof data
// If the current node is a right child, concatenate the proof data with it
currentNode = proofElement.left ? concat(proofElement.data, currentNode) : concat(currentNode, proofElement.data);
}
// Return whether the final node equals the root
return currentNode === root;
}
module.exports = verifyProof;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment