-
Notifications
You must be signed in to change notification settings - Fork 0
/
MerkleDAG.m
145 lines (123 loc) · 5.15 KB
/
MerkleDAG.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
classdef MerkleDAG < handle
properties
Root % Root node of the Merkle-DAG
Nodes % Cell array to store all nodes in the DAG
HashAlgorithm % Hashing algorithm (default: 'SHA-256')
end
methods
function obj = MerkleDAG(dataBlocks, hashAlgorithm)
if nargin > 0
if nargin < 2 || isempty(hashAlgorithm)
hashAlgorithm = 'SHA-256';
end
obj.HashAlgorithm = hashAlgorithm;
obj.Nodes = obj.buildDAG(dataBlocks);
obj.setRoot(obj.Nodes{end});
else
obj.Root = [];
obj.Nodes = {};
end
end
%% Set the root node of the Merkle-DAG
function setRoot(obj, rootNode)
obj.Root = rootNode;
end
%% Build a Merkle-DAG from data blocks
function nodes = buildDAG(obj, dataBlocks)
numBlocks = size(dataBlocks, 1);
nodes = cell(numBlocks, 1);
% Create leaf nodes
for i = 1:numBlocks
nodes{i} = MerkleDAGNode(dataBlocks(i, :), obj.HashAlgorithm, []);
end
% Build parent nodes iteratively until a single root node is created
while numel(nodes) > 1
newSize = ceil(numel(nodes) / 2); % Preallocate to half of the size of the current nodes (enhances performance)
level = cell(newSize, 1);
index = 1;
for i = 1:2:numel(nodes)
if i == numel(nodes)
level{index} = nodes{i};
else
combinedHash = obj.computeHash([nodes{i}.Hash, nodes{i+1}.Hash]);
parentNode = MerkleDAGNode([], obj.HashAlgorithm, combinedHash);
parentNode.addChild(nodes{i});
parentNode.addChild(nodes{i+1});
level{index} = parentNode;
end
index = index + 1;
end
nodes = level;
end
% Store all nodes, including intermediate nodes
obj.Nodes = nodes;
end
%% Verify the integrity of a specific block in the Merkle-DAG
function isVerified = verifyBlock(obj, dataBlock)
targetHash = obj.computeHash(dataBlock);
isVerified = obj.verifyNode(obj.Root, targetHash);
end
%% Compute the cryptographic hash of the data: to verify the overall integrity of the DAG
function hash = computeHash(~, data)
persistent hasher;
if isempty(hasher)
hasher = java.security.MessageDigest.getInstance('SHA-256');
end
% Convert data to uint8
if isnumeric(data)
serializedData = typecast(data(:), 'uint8');
else
serializedData = uint8(data(:)');
end
hasher.update(serializedData(:));
hash = char(reshape(dec2hex(typecast(hasher.digest(), 'uint8'))', 1, []));
end
%% Traverse Depth-First Search (DFS)
function traverseDFS(obj)
if isempty(obj.Root)
disp('The DAG is empty.');
return;
end
obj.traverseNodeDFS(obj.Root, 0);
end
%% Traverse Breadth-First Search (BFS)
function traverseBFS(obj)
if isempty(obj.Root)
disp('The DAG is empty.');
return;
end
queue = {obj.Root};
levels = 0;
while ~isempty(queue)
node = queue{1};
queue(1) = [];
level = levels(1);
levels(1) = [];
indent = repmat(' ', 1, level);
disp([indent, 'Node Data: ', mat2str(node.Data), ', Hash: ', node.Hash]);
for i = 1:numel(node.Children)
queue{end+1} = node.Children{i};
levels(end+1) = level + 1;
end
end
end
end
methods (Access = private)
%% Recursivly traverse each node
function traverseNodeDFS(obj, node, level)
indent = repmat(' ', 1, level);
disp([indent, 'Node Data: ', mat2str(node.Data), ', Hash: ', node.Hash]);
for i = 1:numel(node.Children)
obj.traverseNodeDFS(node.Children{i}, level + 1);
end
end
%% Recursively verify the integrity of a node and its children
function isVerified = verifyNode(obj, node, targetHash)
if isempty(node.Children)
isVerified = isequal(node.Hash, targetHash);
else
isVerified = any(cellfun(@(child) obj.verifyNode(child, targetHash), node.Children));
end
end
end
end