在最底层，和哈希列表一样，我们把数据分成小的数据块，有相应地哈希和它对应。但是往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就结婚生子，得到了一个”子哈希“。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希。于是往上推，依然是一样的方式，可以得到数目更少的新一级哈希，最终必然形成一棵倒挂的树,到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 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]
