在最底層，和哈希列表一樣，我們把數據分成小的數據塊，有相應地哈希和它對應。但是往上走，并不是直接去運算根哈希，而是把相鄰的兩個哈希合并成一個字符串，然后運算這個字符串的哈希，這樣每兩個哈希就結婚生子，得到了一個”子哈希“。如果最底層的哈希總數是單數，那到最后必然出現一個單身哈希，這種情況就直接對它進行哈希運算，所以也能得到它的子哈希。于是往上推，依然是一樣的方式，可以得到數目更少的新一級哈希，最終必然形成一棵倒掛的樹,到了樹根的這個位置，這一代就剩下一個根哈希了，我們把它叫做 Merkle Root。
Merkle Tree的葉子節點的value是數據集合的單元數據或者單元數據HASH。
非葉子節點的value是根據它下面所有的葉子節點值，然后按照Hash算法計算而得出的。
對于OSNMA來說，選擇了一個16個葉子節點的特殊默克爾樹，16個葉子節點分別對應m0~m15，對mi進行一次哈希，則得到X(0,i),所以樹從底往上，第0層的節點數目為16，第1層的節點數為8，第2層的節點數為4，第三層的節點數為2，第四層節點數為1，也是根節點。往上一層，節點數少半是因為選擇的是一個完全二叉樹。其中mi的值是由公鑰類型+公鑰編號+公鑰組成，這也就關聯到了osnma電文中使用的加密算法的驗證。
OSNMA中利用默克爾樹對接收到DSM-PKR中公共秘鑰的驗證，是通過hash不可逆和只需要播發四個節點加上公共秘鑰自己生成一個節點，組成5個節點即可完成對根節點的校驗。實際舉一個例子就很容易明白了。
ICD中，MID是用來指示當前播發的DSM-PKR中的公共秘鑰的對應關系，例如MID=0的時候，mi=公鑰類型+0+公鑰，另外再播發了X(0,1),X(1,1),X(2,1),X(3,1)。校驗流程是這樣的，
第一步mi進行sha-256得到X(0,0)
第二步將X(0,0)+X(0,1)，然后對相加的數據進行sha-256操作，所得結果標記為X(1,0)
第三步將X(1,0)+X(1,1)，然后對相加的數據進行sha-256操作，所得結果標記為X(2,0)
第四步將X(2,0)+X(2,1)，然后對相加的數據進行sha-256操作，所得結果標記為X(3,0)
第五步將X(3,0)+X(3,1)，然后對相加的數據進行sha-256操作，所得結果標記為X(4,0)
X(4,0)即是根節點，與從服務下載的根節點進行比較即可知道校驗是否能夠通過。
對應其他的MID，只需要將步驟中的下表按照對應表格中列出的進行替換，流程是一致的。
python實例
'''實際使用的時候，不需要考慮那么復雜，直接做一個簡化的merkleTree，即可用于OSNMA的工作。因為OSNMA的merkleTree的層數和節點數是固定的
'''
class OSNMAMerkleTree:
def __init__(self,hashFun):
self.hashFun = hashFun
self.allNodes=dict()#所有節點的數據使用兩個數字表示，第一個表示層，第二個表示這一層的第幾個
self.leafm0_15=[]
self.InterNode=[[(0,1),(1,1),(2,1),(3,1)],#m0
[(0,0),(1,1),(2,1),(3,1)],#m1
[(0,3),(1,0),(2,1),(3,1)],#m2
[(0,2),(1,0),(2,1),(3,1)],
[(0,5),(1,3),(2,0),(3,1)],
[(0,4),(1,3),(2,0),(3,1)],
[(0,7),(1,2),(2,0),(3,1)],
[(0,6),(1,2),(2,0),(3,1)],
[(0,9),(1,5),(2,3),(3,0)],
[(0,8),(1,5),(2,3),(3,0)],
[(0,11),(1,4),(2,3),(3,0)],#m10
[(0,10),(1,4),(2,3),(3,0)],#m11
[(0,13),(1,7),(2,2),(3,0)],
[(0,12),(1,7),(2,2),(3,0)],
[(0,15),(1,6),(2,2),(3,0)],
[(0,14),(1,6),(2,2),(3,0)],#m15
] #只需要的節點表
def AddLayer(self,floorindex,nodeSize):
index =0
indexkey = 0
for i in range(nodeSize):
leftNodeValue=self.allNodes[(floorindex,index)] #取得左邊子節點數據
rightNodeValue=self.allNodes[(floorindex,index+1)]#取得右邊子節點數據
blocktmp=leftNodeValue+rightNodeValue
self.allNodes.update({(floorindex+1,indexkey):self.hashFun(blocktmp).digest()})#計算父節點的數據
index+=2
indexkey+=1
def GeneratorMerkleTree(self,data_blocks):
if not data_blocks:
return None
self.leafm0_15 = data_blocks
self.allNodes.clear()
floorindex=0
index =0
for block in data_blocks:
self.allNodes.update({(floorindex,index):self.hashFun(block).digest()})
index+=1
self.AddLayer(0,8)
self.AddLayer(1,4)
self.AddLayer(2,2)
self.AddLayer(3,1)
#取得對應的節點
def GetNodeValue(self,floor,index):
return self.allNodes[(floor,index)]
#獲得mi對應的四個節點
def GetMiNodes(self,miIndex=0):
Nodes=[]
for i in range(4):
tmp=self.InterNode[miIndex][i]
nodedata=self.GetNodeValue(tmp[0],tmp[1])
Nodes.append(nodedata)
return Nodes
def verifyRoot(self,mid,ITNS,leaf):
node = self.hashFun(leaf).digest()
for it_node in ITNS:
if mid % 2 == 0:
node = self.hashFun(node + it_node).digest()
else:
node = self.hashFun(it_node + node).digest()
mid = mid // 2
return node==self.allNodes[(4,0)]
#index為MID,mi為葉子節點
def verifycalRoot(self,MID,mi):
x0i=self.hashFun(mi).digest()
for item in self.InterNode[MID]:
ifMID%2==0:
x0i=x0i+self.allNodes[item]
else:
x0i=self.allNodes[item]+x0i
MID =MID // 2
x0i=self.hashFun(x0i).digest()
return x0i
def showallnodes(self):
for i, v in self.allNodes.items():
print(i,v)
def getAllNodes(self):
return self.allNodes
def getleafi(self,i):
return self.leafm0_15[i]
