Skip to content

Instantly share code, notes, and snippets.

@GopherJ
Forked from cf/README.md
Created March 8, 2024 02:37
Show Gist options
  • Save GopherJ/27915a4e763b72a1b97e7dd5ad98a0a1 to your computer and use it in GitHub Desktop.
Save GopherJ/27915a4e763b72a1b97e7dd5ad98a0a1 to your computer and use it in GitHub Desktop.
A Hackers Guide to Layer 2: Zero Merkle Trees from Scratch

A Hackers Guide to Layer 2: Zero Merkle Trees from Scratch

Code Snippets from the Tutorial

This repository contains the code snippets from the tutorial A Hackers Guide to Layer 2: Zero Merkle Trees from Scratch.

Thanks to OAS for sponsoring this tutorial series.

License

Copyright 2023 Carter Jack Feldman

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

import shajs from "sha.js";
type MerkleNodeValue = string;
function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
return shajs("sha256")
.update(leftNode + rightNode, "hex")
.digest("hex");
}
function computeZeroHashes(height: number): MerkleNodeValue[] {
let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
for (let i = 1; i <= height; i++) {
currentZeroHash = hash(currentZeroHash, currentZeroHash);
zeroHashes.push(currentZeroHash)
}
return zeroHashes;
}
function example1(){
console.log("[example1] the first 32 zero hashes are: "+JSON.stringify(computeZeroHashes(32), undefined, 2));
}
example1();
import shajs from "sha.js";
type MerkleNodeValue = string;
function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
return shajs("sha256")
.update(leftNode + rightNode, "hex")
.digest("hex");
}
function computeZeroHashes(height: number): MerkleNodeValue[] {
let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
for (let i = 1; i <= height; i++) {
currentZeroHash = hash(currentZeroHash, currentZeroHash);
zeroHashes.push(currentZeroHash)
}
return zeroHashes;
}
class NodeStore {
nodes: {[id: string]: MerkleNodeValue};
height: number;
zeroHashes: MerkleNodeValue[];
constructor(height: number){
this.nodes = {};
this.height = height;
this.zeroHashes = computeZeroHashes(height);
}
contains(level: number, index: number): boolean {
// check if the node exists in the data store
return Object.hasOwnProperty.call(this.nodes, level+"_"+index);
}
set(level: number, index: number, value: MerkleNodeValue){
// set the value of the node in the data store
this.nodes[level+"_"+index] = value;
}
get(level: number, index: number): MerkleNodeValue {
if(this.contains(level, index)){
// if the node is in the datastore, return it
return this.nodes[level+"_"+index];
}else{
// if the node is NOT in the data store, return the correct zero hash for the node's level
return this.zeroHashes[this.height-level];
}
}
}
class ZeroMerkleTree {
height: number;
nodeStore: NodeStore;
constructor(height: number){
this.height = height;
this.nodeStore = new NodeStore(height);
}
setLeaf(index: number, value: MerkleNodeValue){
// start traversing the leaf's merkle path at the leaf node
let currentIndex = index;
let currentValue = value;
// don't set the root (level = 0) in the loop, as it has no sibling
for(let level = this.height; level > 0; level--){
// set the current node in the tree
this.nodeStore.set(level, currentIndex, currentValue);
if(currentIndex % 2 === 0){
// if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
const rightSibling = this.nodeStore.get(level, currentIndex+1);
currentValue = hash(currentValue, rightSibling);
}else{
// if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
const leftSibling = this.nodeStore.get(level, currentIndex-1);
currentValue = hash(leftSibling, currentValue);
}
// set current index to the index of the parent node
currentIndex = Math.floor(currentIndex/2);
}
// set the root node (level = 0, index = 0) to current value
this.nodeStore.set(0, 0, currentValue);
}
getRoot(): MerkleNodeValue {
return this.nodeStore.get(0, 0);
}
}
function example2(){
const leavesToSet = [
"0000000000000000000000000000000000000000000000000000000000000001", // 1
"0000000000000000000000000000000000000000000000000000000000000003", // 3
"0000000000000000000000000000000000000000000000000000000000000003", // 3
"0000000000000000000000000000000000000000000000000000000000000007", // 7
"0000000000000000000000000000000000000000000000000000000000000004", // 4
"0000000000000000000000000000000000000000000000000000000000000002", // 2
"0000000000000000000000000000000000000000000000000000000000000000", // 0
"0000000000000000000000000000000000000000000000000000000000000006", // 6
];
const tree = new ZeroMerkleTree(3);
leavesToSet.forEach((leaf, index)=>{
tree.setLeaf(index, leaf);
});
console.log("[example2] the root is: "+tree.getRoot());
}
example2();
import shajs from "sha.js";
type MerkleNodeValue = string;
interface IMerkleProof {
root: MerkleNodeValue;
siblings: MerkleNodeValue[];
index: number;
value: MerkleNodeValue;
}
interface IDeltaMerkleProof {
index: number;
siblings: MerkleNodeValue[];
oldRoot: MerkleNodeValue;
oldValue: MerkleNodeValue;
newRoot: MerkleNodeValue;
newValue: MerkleNodeValue;
}
function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
return shajs("sha256")
.update(leftNode + rightNode, "hex")
.digest("hex");
}
function computeZeroHashes(height: number): MerkleNodeValue[] {
let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
for (let i = 1; i <= height; i++) {
currentZeroHash = hash(currentZeroHash, currentZeroHash);
zeroHashes.push(currentZeroHash)
}
return zeroHashes;
}
class NodeStore {
nodes: {[id: string]: MerkleNodeValue};
height: number;
zeroHashes: MerkleNodeValue[];
constructor(height: number){
this.nodes = {};
this.height = height;
this.zeroHashes = computeZeroHashes(height);
}
contains(level: number, index: number): boolean {
// check if the node exists in the data store
return Object.hasOwnProperty.call(this.nodes, level+"_"+index);
}
set(level: number, index: number, value: MerkleNodeValue){
// set the value of the node in the data store
this.nodes[level+"_"+index] = value;
}
get(level: number, index: number): MerkleNodeValue {
if(this.contains(level, index)){
// if the node is in the datastore, return it
return this.nodes[level+"_"+index];
}else{
// if the node is NOT in the data store, return the correct zero hash for the node's level
return this.zeroHashes[this.height-level];
}
}
}
class ZeroMerkleTree {
height: number;
nodeStore: NodeStore;
constructor(height: number){
this.height = height;
this.nodeStore = new NodeStore(height);
}
setLeaf(index: number, value: MerkleNodeValue): IDeltaMerkleProof{
// get the old root and old value for the delta merkle proof
const oldRoot = this.nodeStore.get(0, 0);
const oldValue = this.nodeStore.get(this.height, index);
// siblings array for delta merkle proof
const siblings: MerkleNodeValue[] = [];
// start traversing the leaf's merkle path at the leaf node
let currentIndex = index;
let currentValue = value;
// don't set the root (level = 0) in the loop, as it has no sibling
for(let level = this.height; level > 0; level--){
// set the current node in the tree
this.nodeStore.set(level, currentIndex, currentValue);
if(currentIndex % 2 === 0){
// if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
const rightSibling = this.nodeStore.get(level, currentIndex+1);
currentValue = hash(currentValue, rightSibling);
// add the right sibling to the siblings array
siblings.push(rightSibling);
}else{
// if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
const leftSibling = this.nodeStore.get(level, currentIndex-1);
currentValue = hash(leftSibling, currentValue);
// add the left sibling to the siblings array
siblings.push(leftSibling);
}
// set current index to the index of the parent node
currentIndex = Math.floor(currentIndex/2);
}
// set the root node (level = 0, index = 0) to current value
this.nodeStore.set(0, 0, currentValue);
return {
index,
siblings,
oldRoot,
oldValue,
newValue: value,
newRoot: currentValue,
};
}
getRoot(): MerkleNodeValue {
return this.nodeStore.get(0, 0);
}
}
function computeMerkleRootFromProof(siblings: MerkleNodeValue[], index: number, value: MerkleNodeValue): MerkleNodeValue{
// start our merkle node path at the leaf node
let merklePathNodeValue = value;
let merklePathNodeIndex = index;
// we follow the leaf's merkle path up to the root,
// computing the merkle path's nodes using the siblings provided as we go alone
for(let i=0;i<siblings.length;i++){
const merklePathNodeSibling = siblings[i];
if(merklePathNodeIndex%2===0){
// if the current index of the node on our merkle path is even:
// * merklePathNodeValue is the left hand node,
// * merklePathNodeSibling is the right hand node
// * parent node's value is hash(merklePathNodeValue, merklePathNodeSibling)
merklePathNodeValue = hash(merklePathNodeValue, merklePathNodeSibling);
}else{
// if the current index of the node on our merkle path is odd:
// * merklePathNodeSibling is the left hand node
// * merklePathNodeValue is the right hand node,
// * parent node's value is hash(merklePathNodeSibling, merklePathNodeValue)
merklePathNodeValue = hash(merklePathNodeSibling, merklePathNodeValue);
}
// using our definition, the parent node of our path node is N(level-1, floor(index/2))
merklePathNodeIndex = Math.floor(merklePathNodeIndex/2);
}
return merklePathNodeValue;
}
function verifyMerkleProof(proof: IMerkleProof): boolean{
return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}
function verifyDeltaMerkleProof(deltaMerkleProof: IDeltaMerkleProof): boolean{
// split the delta merkle proof into a before and after merkle proof, reusing the same siblings and index
const oldProof = {
// reuse the same siblings for both old and new
siblings: deltaMerkleProof.siblings,
// reuse the same index for both old and new
index: deltaMerkleProof.index,
root: deltaMerkleProof.oldRoot,
value: deltaMerkleProof.oldValue,
};
const newProof = {
// reuse the same siblings for both old and new
siblings: deltaMerkleProof.siblings,
// reuse the same index for both old and new
index: deltaMerkleProof.index,
root: deltaMerkleProof.newRoot,
value: deltaMerkleProof.newValue,
};
return verifyMerkleProof(oldProof) && verifyMerkleProof(newProof);
}
function example3(){
const leavesToSet = [
"0000000000000000000000000000000000000000000000000000000000000001", // 1
"0000000000000000000000000000000000000000000000000000000000000003", // 3
"0000000000000000000000000000000000000000000000000000000000000003", // 3
"0000000000000000000000000000000000000000000000000000000000000007", // 7
"0000000000000000000000000000000000000000000000000000000000000004", // 4
"0000000000000000000000000000000000000000000000000000000000000002", // 2
"0000000000000000000000000000000000000000000000000000000000000000", // 0
"0000000000000000000000000000000000000000000000000000000000000006", // 6
];
const tree = new ZeroMerkleTree(3);
const deltaMerkleProofs = leavesToSet.map((leaf, index)=>tree.setLeaf(index, leaf));
// verify the delta merkle proofs
for(let i=0;i<deltaMerkleProofs.length;i++){
const deltaProof = deltaMerkleProofs[i];
if(!verifyDeltaMerkleProof(deltaProof)){
console.error("[example3] ERROR: delta merkle proof for index "+deltaProof.index+" is INVALID");
throw new Error("invalid delta merkle proof");
}else{
console.log("[example3] delta merkle proof for index "+deltaProof.index+" is valid");
}
}
console.log("[example3] the delta merkle proofs are:\n"+JSON.stringify(deltaMerkleProofs, null, 2));
}
example3();
import shajs from "sha.js";
type MerkleNodeValue = string;
interface IMerkleProof {
root: MerkleNodeValue;
siblings: MerkleNodeValue[];
index: number;
value: MerkleNodeValue;
}
interface IDeltaMerkleProof {
index: number;
siblings: MerkleNodeValue[];
oldRoot: MerkleNodeValue;
oldValue: MerkleNodeValue;
newRoot: MerkleNodeValue;
newValue: MerkleNodeValue;
}
function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
return shajs("sha256")
.update(leftNode + rightNode, "hex")
.digest("hex");
}
function computeZeroHashes(height: number): MerkleNodeValue[] {
let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
for (let i = 1; i <= height; i++) {
currentZeroHash = hash(currentZeroHash, currentZeroHash);
zeroHashes.push(currentZeroHash)
}
return zeroHashes;
}
class NodeStore {
nodes: {[id: string]: MerkleNodeValue};
height: number;
zeroHashes: MerkleNodeValue[];
constructor(height: number){
this.nodes = {};
this.height = height;
this.zeroHashes = computeZeroHashes(height);
}
contains(level: number, index: number): boolean {
// check if the node exists in the data store
return Object.hasOwnProperty.call(this.nodes, level+"_"+index);
}
set(level: number, index: number, value: MerkleNodeValue){
// set the value of the node in the data store
this.nodes[level+"_"+index] = value;
}
get(level: number, index: number): MerkleNodeValue {
if(this.contains(level, index)){
// if the node is in the datastore, return it
return this.nodes[level+"_"+index];
}else{
// if the node is NOT in the data store, return the correct zero hash for the node's level
return this.zeroHashes[this.height-level];
}
}
}
class ZeroMerkleTree {
height: number;
nodeStore: NodeStore;
constructor(height: number){
this.height = height;
this.nodeStore = new NodeStore(height);
}
setLeaf(index: number, value: MerkleNodeValue): IDeltaMerkleProof{
// get the old root and old value for the delta merkle proof
const oldRoot = this.nodeStore.get(0, 0);
const oldValue = this.nodeStore.get(this.height, index);
// siblings array for delta merkle proof
const siblings: MerkleNodeValue[] = [];
// start traversing the leaf's merkle path at the leaf node
let currentIndex = index;
let currentValue = value;
// don't set the root (level = 0) in the loop, as it has no sibling
for(let level = this.height; level > 0; level--){
// set the current node in the tree
this.nodeStore.set(level, currentIndex, currentValue);
if(currentIndex % 2 === 0){
// if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
const rightSibling = this.nodeStore.get(level, currentIndex+1);
currentValue = hash(currentValue, rightSibling);
// add the right sibling to the siblings array
siblings.push(rightSibling);
}else{
// if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
const leftSibling = this.nodeStore.get(level, currentIndex-1);
currentValue = hash(leftSibling, currentValue);
// add the left sibling to the siblings array
siblings.push(leftSibling);
}
// set current index to the index of the parent node
currentIndex = Math.floor(currentIndex/2);
}
// set the root node (level = 0, index = 0) to current value
this.nodeStore.set(0, 0, currentValue);
return {
index,
siblings,
oldRoot,
oldValue,
newValue: value,
newRoot: currentValue,
};
}
getRoot(): MerkleNodeValue {
return this.nodeStore.get(0, 0);
}
}
function computeMerkleRootFromProof(siblings: MerkleNodeValue[], index: number, value: MerkleNodeValue): MerkleNodeValue{
// start our merkle node path at the leaf node
let merklePathNodeValue = value;
let merklePathNodeIndex = index;
// we follow the leaf's merkle path up to the root,
// computing the merkle path's nodes using the siblings provided as we go alone
for(let i=0;i<siblings.length;i++){
const merklePathNodeSibling = siblings[i];
if(merklePathNodeIndex%2===0){
// if the current index of the node on our merkle path is even:
// * merklePathNodeValue is the left hand node,
// * merklePathNodeSibling is the right hand node
// * parent node's value is hash(merklePathNodeValue, merklePathNodeSibling)
merklePathNodeValue = hash(merklePathNodeValue, merklePathNodeSibling);
}else{
// if the current index of the node on our merkle path is odd:
// * merklePathNodeSibling is the left hand node
// * merklePathNodeValue is the right hand node,
// * parent node's value is hash(merklePathNodeSibling, merklePathNodeValue)
merklePathNodeValue = hash(merklePathNodeSibling, merklePathNodeValue);
}
// using our definition, the parent node of our path node is N(level-1, floor(index/2))
merklePathNodeIndex = Math.floor(merklePathNodeIndex/2);
}
return merklePathNodeValue;
}
function verifyMerkleProof(proof: IMerkleProof): boolean{
return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}
function verifyDeltaMerkleProof(deltaMerkleProof: IDeltaMerkleProof): boolean{
// split the delta merkle proof into a before and after merkle proof, reusing the same siblings and index
const oldProof = {
// reuse the same siblings for both old and new
siblings: deltaMerkleProof.siblings,
// reuse the same index for both old and new
index: deltaMerkleProof.index,
root: deltaMerkleProof.oldRoot,
value: deltaMerkleProof.oldValue,
};
const newProof = {
// reuse the same siblings for both old and new
siblings: deltaMerkleProof.siblings,
// reuse the same index for both old and new
index: deltaMerkleProof.index,
root: deltaMerkleProof.newRoot,
value: deltaMerkleProof.newValue,
};
return verifyMerkleProof(oldProof) && verifyMerkleProof(newProof);
}
function example4(){
const leavesToSet = [
"0000000000000000000000000000000000000000000000000000000000000001", // 1
"0000000000000000000000000000000000000000000000000000000000000003", // 3
"0000000000000000000000000000000000000000000000000000000000000003", // 3
"0000000000000000000000000000000000000000000000000000000000000007", // 7
"0000000000000000000000000000000000000000000000000000000000000004", // 4
"0000000000000000000000000000000000000000000000000000000000000002", // 2
"0000000000000000000000000000000000000000000000000000000000000000", // 0
"0000000000000000000000000000000000000000000000000000000000000006", // 6
];
const tree = new ZeroMerkleTree(3);
const deltaMerkleProofs = leavesToSet.map((leaf, index)=>tree.setLeaf(index, leaf));
// verify the delta merkle proofs
for(let i=0;i<deltaMerkleProofs.length;i++){
const deltaProof = deltaMerkleProofs[i];
if(!verifyDeltaMerkleProof(deltaProof)){
console.error("[example4] ERROR: delta merkle proof for index "+deltaProof.index+" is INVALID");
throw new Error("invalid delta merkle proof");
}else if(i>0 && deltaProof.oldRoot !== deltaMerkleProofs[i-1].newRoot){
// the previous proof's new root should be the same as this proof's old root
console.error(
"[example4] ERROR: delta merkle proof for index "+deltaProof.index +
" has a different old root than the previous delta merkle proof's new root"
);
throw new Error("delta merkle proof root sequence mismatch");
}else{
console.log("[example4] delta merkle proof for index "+deltaProof.index+" is valid");
}
}
console.log("[example4] the delta merkle proofs are:\n"+JSON.stringify(deltaMerkleProofs, null, 2));
}
example4();
import shajs from "sha.js";
type MerkleNodeValue = string;
interface IMerkleProof {
root: MerkleNodeValue;
siblings: MerkleNodeValue[];
index: number;
value: MerkleNodeValue;
}
interface IDeltaMerkleProof {
index: number;
siblings: MerkleNodeValue[];
oldRoot: MerkleNodeValue;
oldValue: MerkleNodeValue;
newRoot: MerkleNodeValue;
newValue: MerkleNodeValue;
}
function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
return shajs("sha256")
.update(leftNode + rightNode, "hex")
.digest("hex");
}
function computeZeroHashes(height: number): MerkleNodeValue[] {
let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
for (let i = 1; i <= height; i++) {
currentZeroHash = hash(currentZeroHash, currentZeroHash);
zeroHashes.push(currentZeroHash)
}
return zeroHashes;
}
class NodeStore {
nodes: {[id: string]: MerkleNodeValue};
height: number;
zeroHashes: MerkleNodeValue[];
constructor(height: number){
this.nodes = {};
this.height = height;
this.zeroHashes = computeZeroHashes(height);
}
contains(level: number, index: number): boolean {
// check if the node exists in the data store
return Object.hasOwnProperty.call(this.nodes, level+"_"+index);
}
set(level: number, index: number, value: MerkleNodeValue){
// set the value of the node in the data store
this.nodes[level+"_"+index] = value;
}
get(level: number, index: number): MerkleNodeValue {
if(this.contains(level, index)){
// if the node is in the datastore, return it
return this.nodes[level+"_"+index];
}else{
// if the node is NOT in the data store, return the correct zero hash for the node's level
return this.zeroHashes[this.height-level];
}
}
}
class ZeroMerkleTree {
height: number;
nodeStore: NodeStore;
constructor(height: number){
this.height = height;
this.nodeStore = new NodeStore(height);
}
setLeaf(index: number, value: MerkleNodeValue): IDeltaMerkleProof{
// get the old root and old value for the delta merkle proof
const oldRoot = this.nodeStore.get(0, 0);
const oldValue = this.nodeStore.get(this.height, index);
// siblings array for delta merkle proof
const siblings: MerkleNodeValue[] = [];
// start traversing the leaf's merkle path at the leaf node
let currentIndex = index;
let currentValue = value;
// don't set the root (level = 0) in the loop, as it has no sibling
for(let level = this.height; level > 0; level--){
// set the current node in the tree
this.nodeStore.set(level, currentIndex, currentValue);
if(currentIndex % 2 === 0){
// if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
const rightSibling = this.nodeStore.get(level, currentIndex+1);
currentValue = hash(currentValue, rightSibling);
// add the right sibling to the siblings array
siblings.push(rightSibling);
}else{
// if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
const leftSibling = this.nodeStore.get(level, currentIndex-1);
currentValue = hash(leftSibling, currentValue);
// add the left sibling to the siblings array
siblings.push(leftSibling);
}
// set current index to the index of the parent node
currentIndex = Math.floor(currentIndex/2);
}
// set the root node (level = 0, index = 0) to current value
this.nodeStore.set(0, 0, currentValue);
return {
index,
siblings,
oldRoot,
oldValue,
newValue: value,
newRoot: currentValue,
};
}
getLeaf(index: number): IMerkleProof {
// siblings array for merkle proof
const siblings: MerkleNodeValue[] = [];
// get value for the merkle proof
const value = this.nodeStore.get(this.height, index);
// start traversing the leaf's merkle path at the leaf node
let currentIndex = index;
let currentValue = value;
// don't set the root (level = 0) in the loop, as it has no sibling
for(let level = this.height; level > 0; level--){
if(currentIndex % 2 === 0){
// if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
const rightSibling = this.nodeStore.get(level, currentIndex+1);
currentValue = hash(currentValue, rightSibling);
// add the right sibling to the siblings array
siblings.push(rightSibling);
}else{
// if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
const leftSibling = this.nodeStore.get(level, currentIndex-1);
currentValue = hash(leftSibling, currentValue);
// add the left sibling to the siblings array
siblings.push(leftSibling);
}
// set current index to the index of the parent node
currentIndex = Math.floor(currentIndex/2);
}
// current value is the root
const root = currentValue;
return {
root,
siblings,
index,
value,
};
}
getRoot(): MerkleNodeValue {
return this.nodeStore.get(0, 0);
}
}
function computeMerkleRootFromProof(siblings: MerkleNodeValue[], index: number, value: MerkleNodeValue): MerkleNodeValue{
// start our merkle node path at the leaf node
let merklePathNodeValue = value;
let merklePathNodeIndex = index;
// we follow the leaf's merkle path up to the root,
// computing the merkle path's nodes using the siblings provided as we go alone
for(let i=0;i<siblings.length;i++){
const merklePathNodeSibling = siblings[i];
if(merklePathNodeIndex%2===0){
// if the current index of the node on our merkle path is even:
// * merklePathNodeValue is the left hand node,
// * merklePathNodeSibling is the right hand node
// * parent node's value is hash(merklePathNodeValue, merklePathNodeSibling)
merklePathNodeValue = hash(merklePathNodeValue, merklePathNodeSibling);
}else{
// if the current index of the node on our merkle path is odd:
// * merklePathNodeSibling is the left hand node
// * merklePathNodeValue is the right hand node,
// * parent node's value is hash(merklePathNodeSibling, merklePathNodeValue)
merklePathNodeValue = hash(merklePathNodeSibling, merklePathNodeValue);
}
// using our definition, the parent node of our path node is N(level-1, floor(index/2))
merklePathNodeIndex = Math.floor(merklePathNodeIndex/2);
}
return merklePathNodeValue;
}
function verifyMerkleProof(proof: IMerkleProof): boolean{
return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}
function verifyDeltaMerkleProof(deltaMerkleProof: IDeltaMerkleProof): boolean{
// split the delta merkle proof into a before and after merkle proof, reusing the same siblings and index
const oldProof = {
// reuse the same siblings for both old and new
siblings: deltaMerkleProof.siblings,
// reuse the same index for both old and new
index: deltaMerkleProof.index,
root: deltaMerkleProof.oldRoot,
value: deltaMerkleProof.oldValue,
};
const newProof = {
// reuse the same siblings for both old and new
siblings: deltaMerkleProof.siblings,
// reuse the same index for both old and new
index: deltaMerkleProof.index,
root: deltaMerkleProof.newRoot,
value: deltaMerkleProof.newValue,
};
return verifyMerkleProof(oldProof) && verifyMerkleProof(newProof);
}
function example5(){
const leavesToSet = [
"0000000000000000000000000000000000000000000000000000000000000001", // 1
"0000000000000000000000000000000000000000000000000000000000000003", // 3
"0000000000000000000000000000000000000000000000000000000000000003", // 3
"0000000000000000000000000000000000000000000000000000000000000007", // 7
"0000000000000000000000000000000000000000000000000000000000000004", // 4
"0000000000000000000000000000000000000000000000000000000000000002", // 2
"0000000000000000000000000000000000000000000000000000000000000000", // 0
"0000000000000000000000000000000000000000000000000000000000000006", // 6
];
const tree = new ZeroMerkleTree(3);
const deltaMerkleProofs = leavesToSet.map((leaf, index)=>tree.setLeaf(index, leaf));
// verify the delta merkle proofs
for(let i=0;i<deltaMerkleProofs.length;i++){
const deltaProof = deltaMerkleProofs[i];
if(!verifyDeltaMerkleProof(deltaProof)){
console.error("[example5] ERROR: delta merkle proof for index "+deltaProof.index+" is INVALID");
throw new Error("invalid delta merkle proof");
}else if(i>0 && deltaProof.oldRoot !== deltaMerkleProofs[i-1].newRoot){
// the previous proof's new root should be the same as this proof's old root
console.error(
"[example5] ERROR: delta merkle proof for index "+deltaProof.index +
" has a different old root than the previous delta merkle proof's new root"
);
throw new Error("delta merkle proof root sequence mismatch");
}else{
console.log("[example5] delta merkle proof for index "+deltaProof.index+" is valid");
}
}
// don't print the delta merkle proofs to avoid clutter
//console.log("[example5] the delta merkle proofs are:\n"+JSON.stringify(deltaMerkleProofs, null, 2));
// verify each leaf's merkle proof
for(let i=0;i<leavesToSet.length;i++){
const proof = tree.getLeaf(i);
if(!verifyMerkleProof(proof)){
console.error("[example5] ERROR: merkle proof for index "+proof.index+" is INVALID");
throw new Error("invalid merkle proof");
}else if(proof.value !== leavesToSet[i]){
console.error("[example5] ERROR: merkle proof for index "+proof.index+" has the wrong value");
throw new Error("merkle proof value mismatch");
}else{
console.log("[example5] merkle proof for index "+proof.index+" is valid");
}
console.log("merkle proof for index "+proof.index+": "+JSON.stringify(proof, null, 2));
}
}
example5();
import shajs from "sha.js";
type MerkleNodeValue = string;
interface IMerkleProof {
root: MerkleNodeValue;
siblings: MerkleNodeValue[];
index: number;
value: MerkleNodeValue;
}
interface IDeltaMerkleProof {
index: number;
siblings: MerkleNodeValue[];
oldRoot: MerkleNodeValue;
oldValue: MerkleNodeValue;
newRoot: MerkleNodeValue;
newValue: MerkleNodeValue;
}
function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
return shajs("sha256")
.update(leftNode + rightNode, "hex")
.digest("hex");
}
function computeZeroHashes(height: number): MerkleNodeValue[] {
let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
for (let i = 1; i <= height; i++) {
currentZeroHash = hash(currentZeroHash, currentZeroHash);
zeroHashes.push(currentZeroHash)
}
return zeroHashes;
}
class NodeStore {
nodes: {[id: string]: MerkleNodeValue};
height: number;
zeroHashes: MerkleNodeValue[];
constructor(height: number){
this.nodes = {};
this.height = height;
this.zeroHashes = computeZeroHashes(height);
}
contains(level: number, index: number): boolean {
// check if the node exists in the data store
return Object.hasOwnProperty.call(this.nodes, level+"_"+index);
}
set(level: number, index: number, value: MerkleNodeValue){
// set the value of the node in the data store
this.nodes[level+"_"+index] = value;
}
get(level: number, index: number): MerkleNodeValue {
if(this.contains(level, index)){
// if the node is in the datastore, return it
return this.nodes[level+"_"+index];
}else{
// if the node is NOT in the data store, return the correct zero hash for the node's level
return this.zeroHashes[this.height-level];
}
}
}
class ZeroMerkleTree {
height: number;
nodeStore: NodeStore;
constructor(height: number){
this.height = height;
this.nodeStore = new NodeStore(height);
}
setLeaf(index: number, value: MerkleNodeValue): IDeltaMerkleProof{
// get the old root and old value for the delta merkle proof
const oldRoot = this.nodeStore.get(0, 0);
const oldValue = this.nodeStore.get(this.height, index);
// siblings array for delta merkle proof
const siblings: MerkleNodeValue[] = [];
// start traversing the leaf's merkle path at the leaf node
let currentIndex = index;
let currentValue = value;
// don't set the root (level = 0) in the loop, as it has no sibling
for(let level = this.height; level > 0; level--){
// set the current node in the tree
this.nodeStore.set(level, currentIndex, currentValue);
if(currentIndex % 2 === 0){
// if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
const rightSibling = this.nodeStore.get(level, currentIndex+1);
currentValue = hash(currentValue, rightSibling);
// add the right sibling to the siblings array
siblings.push(rightSibling);
}else{
// if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
const leftSibling = this.nodeStore.get(level, currentIndex-1);
currentValue = hash(leftSibling, currentValue);
// add the left sibling to the siblings array
siblings.push(leftSibling);
}
// set current index to the index of the parent node
currentIndex = Math.floor(currentIndex/2);
}
// set the root node (level = 0, index = 0) to current value
this.nodeStore.set(0, 0, currentValue);
return {
index,
siblings,
oldRoot,
oldValue,
newValue: value,
newRoot: currentValue,
};
}
getLeaf(index: number): IMerkleProof {
// siblings array for merkle proof
const siblings: MerkleNodeValue[] = [];
// get value for the merkle proof
const value = this.nodeStore.get(this.height, index);
// start traversing the leaf's merkle path at the leaf node
let currentIndex = index;
let currentValue = value;
// don't set the root (level = 0) in the loop, as it has no sibling
for(let level = this.height; level > 0; level--){
if(currentIndex % 2 === 0){
// if the current index is even, then it has a sibling on the right (same level, index = currentIndex+1)
const rightSibling = this.nodeStore.get(level, currentIndex+1);
currentValue = hash(currentValue, rightSibling);
// add the right sibling to the siblings array
siblings.push(rightSibling);
}else{
// if the current index is odd, then it has a sibling on the left (same level, index = currentIndex-1)
const leftSibling = this.nodeStore.get(level, currentIndex-1);
currentValue = hash(leftSibling, currentValue);
// add the left sibling to the siblings array
siblings.push(leftSibling);
}
// set current index to the index of the parent node
currentIndex = Math.floor(currentIndex/2);
}
// current value is the root
const root = currentValue;
return {
root,
siblings,
index,
value,
};
}
getRoot(): MerkleNodeValue {
return this.nodeStore.get(0, 0);
}
}
function computeMerkleRootFromProof(siblings: MerkleNodeValue[], index: number, value: MerkleNodeValue): MerkleNodeValue{
// start our merkle node path at the leaf node
let merklePathNodeValue = value;
let merklePathNodeIndex = index;
// we follow the leaf's merkle path up to the root,
// computing the merkle path's nodes using the siblings provided as we go alone
for(let i=0;i<siblings.length;i++){
const merklePathNodeSibling = siblings[i];
if(merklePathNodeIndex%2===0){
// if the current index of the node on our merkle path is even:
// * merklePathNodeValue is the left hand node,
// * merklePathNodeSibling is the right hand node
// * parent node's value is hash(merklePathNodeValue, merklePathNodeSibling)
merklePathNodeValue = hash(merklePathNodeValue, merklePathNodeSibling);
}else{
// if the current index of the node on our merkle path is odd:
// * merklePathNodeSibling is the left hand node
// * merklePathNodeValue is the right hand node,
// * parent node's value is hash(merklePathNodeSibling, merklePathNodeValue)
merklePathNodeValue = hash(merklePathNodeSibling, merklePathNodeValue);
}
// using our definition, the parent node of our path node is N(level-1, floor(index/2))
merklePathNodeIndex = Math.floor(merklePathNodeIndex/2);
}
return merklePathNodeValue;
}
function verifyMerkleProof(proof: IMerkleProof): boolean{
return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}
function verifyDeltaMerkleProof(deltaMerkleProof: IDeltaMerkleProof): boolean{
// split the delta merkle proof into a before and after merkle proof, reusing the same siblings and index
const oldProof = {
// reuse the same siblings for both old and new
siblings: deltaMerkleProof.siblings,
// reuse the same index for both old and new
index: deltaMerkleProof.index,
root: deltaMerkleProof.oldRoot,
value: deltaMerkleProof.oldValue,
};
const newProof = {
// reuse the same siblings for both old and new
siblings: deltaMerkleProof.siblings,
// reuse the same index for both old and new
index: deltaMerkleProof.index,
root: deltaMerkleProof.newRoot,
value: deltaMerkleProof.newValue,
};
return verifyMerkleProof(oldProof) && verifyMerkleProof(newProof);
}
function example6(){
const tree = new ZeroMerkleTree(50);
const deltaA = tree.setLeaf(999999999999,"0000000000000000000000000000000000000000000000000000000000000008");
const deltaB = tree.setLeaf(1337,"0000000000000000000000000000000000000000000000000000000000000007");
const proofA = tree.getLeaf(999999999999);
const proofB = tree.getLeaf(1337);
console.log("verifyDeltaMerkleProof(deltaA): "+verifyDeltaMerkleProof(deltaA));
console.log("verifyDeltaMerkleProof(deltaB): "+verifyDeltaMerkleProof(deltaB));
console.log("deltaA.newRoot === deltaB.oldRoot: "+(deltaA.newRoot === deltaB.oldRoot));
console.log("verifyMerkleProof(proofA): "+verifyMerkleProof(proofA));
console.log("verifyMerkleProof(proofB): "+verifyMerkleProof(proofB));
console.log("proofA: "+JSON.stringify(proofA, null, 2));
console.log("proofB: "+JSON.stringify(proofB, null, 2));
}
example6();
import shajs from "sha.js";
type MerkleNodeValue = string;
interface IMerkleProof {
root: MerkleNodeValue;
siblings: MerkleNodeValue[];
index: number;
value: MerkleNodeValue;
}
interface IDeltaMerkleProof {
index: number;
siblings: MerkleNodeValue[];
oldRoot: MerkleNodeValue;
oldValue: MerkleNodeValue;
newRoot: MerkleNodeValue;
newValue: MerkleNodeValue;
}
function hash(leftNode: MerkleNodeValue, rightNode: MerkleNodeValue) {
return shajs("sha256")
.update(leftNode + rightNode, "hex")
.digest("hex");
}
function computeZeroHashes(height: number): MerkleNodeValue[] {
let currentZeroHash = "0000000000000000000000000000000000000000000000000000000000000000";
const zeroHashes: MerkleNodeValue[] = [currentZeroHash];
for (let i = 1; i <= height; i++) {
currentZeroHash = hash(currentZeroHash, currentZeroHash);
zeroHashes.push(currentZeroHash)
}
return zeroHashes;
}
class AppendOnlyMerkleTree {
height: number;
lastProof: IMerkleProof;
zeroHashes: MerkleNodeValue[];
constructor(height: number){
this.height = height;
this.zeroHashes = computeZeroHashes(height);
// create a dummy proof of all zero hashes for initialization (before we append any leaves, we know all the siblings will be zero hashes because it is an empty tree)
this.lastProof = {
root: this.zeroHashes[this.height],
siblings: this.zeroHashes.slice(0, this.height),
index: -1,
value: this.zeroHashes[this.height],
};
}
appendLeaf(leafValue: string): IDeltaMerkleProof {
const oldMerklePath = computeMerklePathFromProof(this.lastProof.siblings, this.lastProof.index, this.lastProof.value);
// get the old root and old value for the delta merkle proof
const oldRoot = this.lastProof.root;
// the old value will always be empty, thats why its an append only tree :P
const oldValue = "0000000000000000000000000000000000000000000000000000000000000000";
const prevIndex = this.lastProof.index;
// append only tree = new index is always the previous index + 1
const newIndex = prevIndex+1;
// keep track of the old siblings so we can use them for our delta merkle proof
const oldSiblings =this.lastProof.siblings;
const siblings: MerkleNodeValue[] = [];
let multiplier = 1;
for(let level=0;level<this.height;level++){
// get the index of the previous leaf's merkle path node on the current level
const prevLevelIndex = Math.floor(prevIndex/multiplier);
// get the index of the new leaf's merkle path node on the current level
const newLevelIndex = Math.floor(newIndex/multiplier);
if(newLevelIndex===prevLevelIndex){
// if the merkle path node index on this level DID NOT change, we can reuse the old sibling
siblings.push(oldSiblings[level]);
}else{
// if the merkle path node index on this level DID change, we need to check if the new merkle path node index is a left or right hand node
if(newLevelIndex%2===0){
// if the new merkle path node index is even, the new merkle path node is a left hand node,
// so merkle path node's sibling is a right hand node,
// therefore our sibling has an index greater than our merkle path node,
// so the sibling must be a zero hash
// QED
siblings.push(this.zeroHashes[level]);
}else{
// if the new merkle path node is odd, then its sibling has an index one less than it, so its sibling must be the previous merkle path node on this level
siblings.push(oldMerklePath[level]);
}
}
multiplier = multiplier * 2;
}
const newRoot = computeMerkleRootFromProof(siblings, newIndex, leafValue);
this.lastProof = {
root: newRoot,
siblings: siblings,
index: newIndex,
value: leafValue,
};
return {
index: this.lastProof.index,
siblings,
oldRoot,
oldValue,
newRoot,
newValue: leafValue,
};
}
}
function computeMerklePathFromProof(siblings: MerkleNodeValue[], index: number, value: MerkleNodeValue): MerkleNodeValue[]{
// start our merkle node path at the leaf node
let merklePathNodeValue = value;
let merklePathNodeIndex = index;
const merklePath: MerkleNodeValue[] = [value];
// we follow the leaf's merkle path up to the root,
// computing the merkle path's nodes using the siblings provided as we go alone
for(let i=0;i<siblings.length;i++){
const merklePathNodeSibling = siblings[i];
if(merklePathNodeIndex%2===0){
// if the current index of the node on our merkle path is even:
// * merklePathNodeValue is the left hand node,
// * merklePathNodeSibling is the right hand node
// * parent node's value is hash(merklePathNodeValue, merklePathNodeSibling)
merklePathNodeValue = hash(merklePathNodeValue, merklePathNodeSibling);
}else{
// if the current index of the node on our merkle path is odd:
// * merklePathNodeSibling is the left hand node
// * merklePathNodeValue is the right hand node,
// * parent node's value is hash(merklePathNodeSibling, merklePathNodeValue)
merklePathNodeValue = hash(merklePathNodeSibling, merklePathNodeValue);
}
// using our definition, the parent node of our path node is N(level-1, floor(index/2))
merklePathNodeIndex = Math.floor(merklePathNodeIndex/2);
merklePath.push(merklePathNodeValue)
}
return merklePath;
}
function computeMerkleRootFromProof(siblings: MerkleNodeValue[], index: number, value: MerkleNodeValue): MerkleNodeValue{
// start our merkle node path at the leaf node
let merklePathNodeValue = value;
let merklePathNodeIndex = index;
// we follow the leaf's merkle path up to the root,
// computing the merkle path's nodes using the siblings provided as we go alone
for(let i=0;i<siblings.length;i++){
const merklePathNodeSibling = siblings[i];
if(merklePathNodeIndex%2===0){
// if the current index of the node on our merkle path is even:
// * merklePathNodeValue is the left hand node,
// * merklePathNodeSibling is the right hand node
// * parent node's value is hash(merklePathNodeValue, merklePathNodeSibling)
merklePathNodeValue = hash(merklePathNodeValue, merklePathNodeSibling);
}else{
// if the current index of the node on our merkle path is odd:
// * merklePathNodeSibling is the left hand node
// * merklePathNodeValue is the right hand node,
// * parent node's value is hash(merklePathNodeSibling, merklePathNodeValue)
merklePathNodeValue = hash(merklePathNodeSibling, merklePathNodeValue);
}
// using our definition, the parent node of our path node is N(level-1, floor(index/2))
merklePathNodeIndex = Math.floor(merklePathNodeIndex/2);
}
return merklePathNodeValue;
}
function verifyMerkleProof(proof: IMerkleProof): boolean{
return proof.root === computeMerkleRootFromProof(proof.siblings, proof.index, proof.value);
}
function verifyDeltaMerkleProof(deltaMerkleProof: IDeltaMerkleProof): boolean{
// split the delta merkle proof into a before and after merkle proof, reusing the same siblings and index
const oldProof = {
// reuse the same siblings for both old and new
siblings: deltaMerkleProof.siblings,
// reuse the same index for both old and new
index: deltaMerkleProof.index,
root: deltaMerkleProof.oldRoot,
value: deltaMerkleProof.oldValue,
};
const newProof = {
// reuse the same siblings for both old and new
siblings: deltaMerkleProof.siblings,
// reuse the same index for both old and new
index: deltaMerkleProof.index,
root: deltaMerkleProof.newRoot,
value: deltaMerkleProof.newValue,
};
return verifyMerkleProof(oldProof) && verifyMerkleProof(newProof);
}
function example7(){
const tree = new AppendOnlyMerkleTree(50);
const deltaA = tree.appendLeaf("0000000000000000000000000000000000000000000000000000000000000008");
const deltaB = tree.appendLeaf("0000000000000000000000000000000000000000000000000000000000000007");
console.log(deltaA);
console.log("verifyDeltaMerkleProof(deltaA): "+verifyDeltaMerkleProof(deltaA));
console.log("verifyDeltaMerkleProof(deltaB): "+verifyDeltaMerkleProof(deltaB));
console.log("deltaA.newRoot === deltaB.oldRoot: "+(deltaA.newRoot === deltaB.oldRoot));
console.log("deltaA: "+JSON.stringify(deltaA, null, 2));
console.log("deltaB: "+JSON.stringify(deltaB, null, 2));
for(let i=0;i<50;i++){
console.log("verifyDeltaMerkleProof(delta["+i+"]): "+verifyDeltaMerkleProof(tree.appendLeaf(i.toString(16).padStart(64,"0"))));
}
}
example7();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment