A DAG Example in Javascript

One thing I've learned is to really understand something you have to do it. More times going over something = certainty. So if you forget the deets of something you read two weeks ago, thats totally understandable. Use it or loose it. Anyway I digress.

This is a series of data strucutures, working up to Merkle Binary Tree, Patricia Merkle Tree, Merkle DAG etc. Starting with the simplest first. Checkout the git repo.


Directionally Acyclic Graph
Merkle tree
A tree made from hashing paired data (the leaves), then pairing and hashing the results until a single hash remains, the merkle root. In Bitcoin, the leaves are almost always transactions from a single block.


class Graph {

constructor () { this.nodes = {}; }

getNode (value) { return this.nodes[value]; }

addNode (node) { this.nodes[node] = this.nodes[node] || { edges: {} }; }

removeNode (node) { delete this.nodes[node]; }

contains (node) { return this.nodes.hasOwnProperty(node); }

addEdge (node1, node2) { this.nodes[node1].edges[node2] = this.nodes[node2]; this.checkCyclic(node1, node2); }

removeEdge (node1, node2) { delete this.nodes[node1].edges[node2]; }

hasEdge (node1, node2) { return this.nodes[node1].edges.hasOwnProperty(node2); }

checkCyclic (parent, target) { const cyclic = (node) => { Object.keys(node.edges).forEach(edge => { if (edge === parent) { this.removeEdge(parent, target); throw new Error('Graph is cyclic'); }
cyclic(this.getNode(edge)); }); } cyclic(this.getNode(parent)); }


module.exports = Graph;

DAG and Merkle Tree

A Merkle DAG is a Merkle directed acyclic graph. That is a data structure similar to a Merkle tree but not so strict: such DAG does not need to be balanced and its non-leaf nodes are allowed to contain data.