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.