百度解釋
博客解釋
莫科爾樹存儲哈希值
一棵莫科爾樹，樹中每個葉子節點對應一個哈希值。
莫科爾樹的高度為 h，那麼每個莫科爾樹能夠記錄 2**h個完整性摘要值。
每更新一個葉子節點，需要更新從葉子節點到根的這一路徑上所有節點的哈希值。
如圖 ，節點 1 和節點 2 已經存儲了完整性信息，新完整性信息將保存在節點 3，並且由於節點 3 的值發生變化，導致需要重新計算節點 6 和節點 7 的哈希值。
from algorithm.g_hash import G_hash
"""" l左節點 r右節點 p父節點 hash存儲的hash值,每修改一次葉子節點向上更新 data其他數據 """
class Node:
def __init__(self):
self.l=None
self.r=None
self.p=None
self.hash="\\"
self.data="\\"
def change_data(self,data):
self.data=data
self.hash=G_hash(data)
return self.hash
""" init初始化樹 root根節點 h樹的高度，0代表只有根節點 leaf空余的葉子數 add()從root向下遞歸添加h層高的節點 creat()創建h高的樹 （根節點沒算） update() 其實是從左到右向空余葉子添加數據 up_update()向上更新節點知道父節點 show2層次遍歷樹，顯示 show2由show_tree（）調用 sum（）是返回根節點的所有點個數 """
class merkle_tree:
def __int__(self):
self.root = None
self.h=0
self.leaf=0
# 添加 h層樹的節點
def add(self,item,h):
l= Node()
r=Node()
l.p=item
item.l=l
r.p=item
item.r=r
h = h - 1
if h==0:
return
else:
self.add(l,h)
self.add(r,h)
# 莫科爾樹的高度為 h，那麼每個莫科爾樹能夠記錄 2h個電子
# 證據片段的完整性摘要值。
# 除了根節點需要h層
def creat(self,h):
self.root=Node()
self.h=h
self.leaf=2**h
self.add(self.root,h)
return self.root
# 從左到右添加葉子節點
def update(self,data,hash):
if self.leaf==0:
print("本樹已滿")
return
temp=self.root
h=self.h
leaf=self.leaf
# 對於每一個節點p，
# 如果屬與它的剩余葉子節點大於一半，下一個空余葉子就在左邊
# p的左節點的剩余等於 p的所剩葉子節點減去所有葉子節點的一半
# 否則就在右邊
# 葉子節點個數從根節點開始每層分別是 2**（h-1）
# h=1時就是葉子節點那一層
while(h!=0):
if leaf>2**(h-1):
leaf=leaf-2**(h-1)
temp=temp.l
else:
temp=temp.r
h=h-1
self.leaf-=1
temp.data=data
temp.hash=hash
self.up_update(temp)
return temp
def up_update(self,temp):
if temp.p!=None:
temp=temp.p
temp.hash=G_hash(temp.l.hash+temp.r.hash)
self.up_update(temp)
# 左到右 遍歷
def show1(self,root):
if root.l!=None:
print("向左",end="")
self.show(root.l)
print("向右", end="")
self.show(root.r)
if root.l==None:
print(root.hash)
print(root.data)
# 層次遍歷
def show2(self,root):
x=[]
cc=[]
x.append(root)
print("\t",root.hash)
while x!=[]:
if x[0].l==None:
break
for _ in range(len(x)):
print("\t",'%-70s' % x[_].l.hash,end="")
print("\t",'%-70s' % x[_].r.hash,end="")
cc.append(x[_].l)
cc.append(x[_].r)
print("")
x=cc
cc=[]
def show_tree(self):
root=self.root
self.show2(root)
# 除了根節點
def sum(self,root):
if root.l!=None and root.r!=None:
return 2+self.sum(root.l)+self.sum(root.r)
if root.l==None or root.r ==None:
return 0
# test
b=merkle_tree()
b.creat(4)
print(b.sum(b.root))
b.update("1","1.hash")
b.update("2","2.hash")
b.update("3","3.hash")
b.show_tree()
