Infrastructure
This repository contains MATLAB scripts for implementing and using a Merkle Directed Acyclic Graph (DAG) data structure.
The Merkle-DAG is a cryptographic data structure used to efficiently verify the integrity and consistency of data blocks.
Construct a Merkle-DAG manually or from data blocks.
Traverse the graph structure and verify the integrity of data blocks.
Multiple hash algorithms for computing node hashes.
Supported algorithms from Java Security (via MATLAB)
import java.security.MessageDigest;
java.security.Security.getAlgorithms('MessageDigest')
MerkleDAGNode.m
Represents a node in the Merkle-DAG, holds data, compute hashes, and manage child nodes.
MerkleDAG.m
Constructs the Merkle-DAG from data blocks, performs integrity verification, and provides traversal methods (DFS & BFS).
Use case: for scenarios where the DAG structure is not strictly determined by the data itself (no specific relationships/dependencies).
node1 = MerkleDAGNode([1 2 3]); % default: SHA-256, if no hash algorithm specified
node2 = MerkleDAGNode([4 5 6]);
node3 = MerkleDAGNode([7 8 9]);
% Add children to node1 (hash recursively updated)
node1.addChild(node2);
node1.addChild(node3);
% Add another child to node2 (hash recursively updated)
node4 = MerkleDAGNode([10 11 12]);
node2.addChild(node4);
% Display the Merkle-DAG structure
DAGGraph = MerkleDAG();
DAGGraph.setRoot(node1)
DAGGraph.traverseDFS(); % Depth-First (DFS) traversal
DAGGraph.traverseBFS(); % Breadth-First (BFS) traversal
Use case: automated, allowing constructing a Merkle-DAG from a matrix of data blocks.
Each row of the matrix represents a data block. The DAG is built by hashing these blocks into the graph. For scenarios where the relationships between data blocks are determined by their positions in the matrix.
dataBlocks = [ // compose data of the MerkleDAG as a matrix
1 2 3;
4 5 6;
7 8 9;
10 11 12;
13 14 15
];
merkleDAG = MerkleDAG(dataBlocks, 'SHA-384');
% Display the Merkle-DAG structure
merkleDAG.traverseDFS(); % Depth-First (DFS) traversal
merkleDAG.traverseBFS(); % Breadth-First (BFS) traversal
The verifyBlock method checks whether a specific data block is part of the Merkle-DAG. Computes the hash of the data block and verifies it against the hashes in the DAG.
% Verify a specific data block
dataBlockToVerify = [4 5 6];
merkleDAG.verifyBlock(dataBlockToVerify);