-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmtree.py
168 lines (143 loc) · 7.01 KB
/
mtree.py
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#**
# * Merkle tree python implementation for cryptographic applications.
# *
# * The main function build_tree() builds a Merkle tree of given text list.
# * The size of text list (leaf_count) must be the powers of 2.
# * The leaf_count can be updated from constant definition.
# *
# *
# * SHA256 (included in hashlib module) is used for hash.
# *
# *
# * Gamze Orhon Kilic.
# * 2021.
# **
import operator
import math
import hashlib
import random
leaf_count = 8
class node:
def __init__(self, node_id, hashval, left_child, right_child, parent):
self.hashval = hashval
self.node_id = node_id
self.left_child = left_child
self.right_child = right_child
self.parent = parent
class tree:
def __init__(self, n, leaves, layers, cntlayers):
self.n = n
self.layers = []
self.leaves = []
self.cntlayers = int(math.log(n,2)+1)
def fill_leaf(self, node):
self.leaves.append(node)
def construct_layers(self):
i = 1
for i in range(self.cntlayers):
self.layers.append([])
def fill_leaves(self):
self.layers = self.layers + [self.leaves]
def build_tree(self):
self.fill_leaves()
self.construct_layers()
#build_tree
len_layer = int(self.n/2)
ctr = self.n #Node ID counter
for i in range(1,self.cntlayers):
if(len_layer==1):# Root Node
ctr = ctr +1 #Node ID counter
self.layers[i].append(node(ctr, 0, 0, 0, 0))
hashv1 = int(''.join(format(ord(x), 'b') for x in self.layers[i-1][0].hashval))
hashv2 = int(''.join(format(ord(x), 'b') for x in self.layers[i-1][1].hashval))
temp = operator.xor(hashv1,hashv2)
self.layers[i][0].hashval = hashlib.sha256(str(temp).encode()).hexdigest()
self.layers[i][0].left_child = self.layers[i-1][0].node_id
self.layers[i][0].right_child = self.layers[i-1][1].node_id
self.layers[i-1][0].parent = ctr
self.layers[i-1][1].parent = ctr
else: # Inner nodes
k=0
rng = len(self.layers[i-1]) # Child layer length
for j in range(len_layer):
if k < rng:
ctr = ctr +1 #Node ID counter
self.layers[i].append(node(ctr, 0, 0, 0, 0))
hashv1 = int(''.join(format(ord(x), 'b') for x in self.layers[i-1][k].hashval))
hashv2 = int(''.join(format(ord(x), 'b') for x in self.layers[i-1][k+1].hashval))
temp = operator.xor(hashv1,hashv2)
# (SHA256.new(str(temp).encode())).hexdigest()
self.layers[i][j].hashval = hashlib.sha256(str(temp).encode()).hexdigest()
self.layers[i][j].left_child = self.layers[i-1][k].node_id
self.layers[i][j].right_child = self.layers[i-1][k+1].node_id
self.layers[i-1][k].parent = ctr
self.layers[i-1][k+1].parent = ctr
k = k+2
len_layer = int(len_layer/2)
def find_root(self):
return self.layers[self.cntlayers-1][0].hashval
def print_tree(self):
for i in range(self.cntlayers):
for j in range(len(self.layers[i])):
print(self.layers[i][j].node_id, self.layers[i][j].hashval, self.layers[i][j].left_child, self.layers[i][j].right_child, self.layers[i][j].parent)
print('*****')
def find_node_from_id(self, node_id):
for i in range(self.cntlayers):
for j in range(len(self.layers[i])):
temp = self.layers[i][j].node_id
if (temp == node_id):
return self.layers[i][j]
def find_path(self, node_id):
path = []
pivot = self.find_node_from_id(node_id)
for i in range(self.cntlayers):
parent = 0
for j in range(len(self.layers[i])):
if(pivot.parent == self.layers[i][j].node_id):
parent = self.layers[i][j]
if parent.left_child == pivot.node_id:
path.append(self.find_node_from_id(parent.right_child).hashval)
else:
path.append(self.find_node_from_id(parent.left_child).hashval)
pivot = parent
return path
def root_from_path(path, node_hash):
root = node_hash
for i in range(len(path)):
hashv1 = int(''.join(format(ord(x), 'b') for x in path[i]))
hashv2 = int(''.join(format(ord(x), 'b') for x in root))
temp = operator.xor(hashv1, hashv2)
root = hashlib.sha256(str(temp).encode()).hexdigest()
return root
tree1 = tree(leaf_count,[],[],0)
for i in range(leaf_count):
tree1.fill_leaf(node(i+1,hashlib.sha256(str(i).encode()).hexdigest(),0,0,0))
tree1.build_tree()
root = tree1.find_root()
node_id = random.randrange(1,leaf_count)
node_hash = tree1.find_node_from_id(node_id).hashval
path = tree1.find_path(node_id)
found_root = root_from_path(path,node_hash)
print("\n************************************************************************************")
print("***************************** Merkle tree with "+ str(leaf_count) +" leaves ****************************")
print("************************************************************************************")
tree1.print_tree()
print("************************************************************************************")
print("************************************************************************************\n")
print("Root of the Merkle tree ************************************************************")
print(root)
print("************************************************************************************")
print("************************************************************************************\n")
print("Node hash of the node with id "+str(node_id)+ " ****************************************************")
print(node_hash)
print("************************************************************************************")
print("************************************************************************************\n")
print("Path of the node with id "+str(node_id)+ " *********************************************************")
for i in path:
print(i)
print("************************************************************************************")
print("************************************************************************************\n")
print("Found root with path and hash of the node with id "+str(node_id)+ " ********************************")
print(found_root)
print("************************************************************************************")
print("************************************************************************************\n")