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.


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');


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.