Skip to main content

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.

Definitions

DAG
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.

The DAG

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.

References