Merkle 树的认证路径
本文章翻译自David Ireland首次发表于Authentication Path for a Merkle Tree的原创文章, 强烈推荐有一定英文基础的小伙伴阅读原文。
本页探讨如何计算和验证 Merkle 树的认证路径（authentication path）。
二叉树中的路径
这是一棵有 8 个节点的树，在每个层级上，节点从左到右编号为0 , 1 , … 0,1,\ldots0,1,…。洋红色标出的数值是该索引的二进制表示。
叶子节点值Y 0 , … , Y 7 Y_0, \ldots, Y_7Y0,…,Y7是私钥（secret keys）。高度为 0 的节点被称为公钥（public keys）。公钥由H ( Y i ) H(Y_i)H(Yi)计算得出，其中H ( ) H()H()为某个哈希函数。
路径上节点（On-path nodes）
对于示例私钥Y 6 Y_6Y6，我们有i d x = 6 idx=6idx=6。使用a aa位二进制数表示该索引：6 = 110 b 6 = 110\text{b}6=110b。我们可以利用这些二进制位，从根节点出发绘制一条到达索引为 6 的叶子节点的路径。
从根节点开始，对于二进制表示中的每一位，如果该位为 0 则向左下移动，如果该位为 1 则向右下移动。按这些二进制数行进，路径为0 + 1 → 1 + 1 → 11 + 0 → 110 0 + \color{blue}{1} \rightarrow \color{magenta}{1} + \color{blue}{1} \rightarrow \color{magenta}{11} + \color{blue}{0} \rightarrow \color{magenta}{110}0+1→1+1→11+0→110。
这样我们就到达了n o d e ( 0 , 6 ) node(0,6)node(0,6)，如下图蓝线所示。路径上的这些节点（蓝色标记）称为路径上节点（on-path nodes）。
计算认证路径
认证路径节点（authentication path nodes）是路径上节点的兄弟节点。如果路径上节点的索引为i d x idxidx，则认证路径节点的索引为i d x ⊕ 1 idx \oplus 1idx⊕1，其中⊕ \oplus⊕是按位 XOR 操作。在 Python 中为idx ^ 1。
操作n ⊕ 1 n \oplus 1n⊕1在n nn为偶数时等于n + 1 n+1n+1，在n nn为奇数时等于n − 1 n-1n−1（即翻转最低有效位）。这正是计算兄弟节点索引所需的方法。
要查找索引为i d x idxidx的节点的父节点，计算⌊ i d x / 2 ⌋ \lfloor idx/2 \rfloor⌊idx/2⌋。在 Python 中为idx // 2或idx >> 1。
如果树的高度为a aa，则认证路径恰好有a aa个值，每个高度0 ≤ h < a 0 \le h \lt a0≤h<a各有一个。
要计算高度大于零的认证节点值，需要递归计算其子节点的值。
注意，这需要计算树中除路径上节点之外的所有节点的值。
要查找上一层级中认证节点的索引，计算⌊ i d x / 2 ⌋ ⊕ 1 \lfloor idx/2 \rfloor \oplus 1⌊idx/2⌋⊕1。在 Python 中：
a=3# Number of levelsidx=6# leaf indexauthpath=[0]*a authpath[0]=idx^1foriinrange(1,a):idx=idx//2authpath[i]=idx^1print(authpath)# [7, 2, 0]Merkle 树示例
这是 Merkle 树的一个简单示例。为使树的表示更易于管理，我们对哈希函数进行了简化，使其仅输出 4 字节的摘要值（见下文）。这显然不安全，但能使结果显示不那么冗长，同时仍然展示出核心概念。
在此示例中，我们有 8 个私钥值Y 0 , … , Y 7 Y_0,\ldots,Y_7Y0,…,Y7，每个 4 字节长，以十六进制表示。这些私钥通过哈希函数
make_sk基于秘密"种子"和密钥在树中的位置计算得到。我们使用符号( h , i ) (h, i)(h,i)表示高度为h hh、索引为i ii的节点，从左到右编号，从 0 开始。
高度为 0 的叶子节点包含每个密钥的 4 字节哈希值，( 0 , i ) = H ( Y i ) (0,i)=H(Y_i)(0,i)=H(Yi)。这些即为公钥。
每个内部节点包含其左右子节点值的哈希值，H ( l e f t ∣ ∣ r i g h t ) H(\mathtt{left} || \mathtt{right})H(left∣∣right)。
Y 6 Y_6Y6的认证路径为( 0 , 7 ) → ( 1 , 2 ) → ( 2 , 0 ) (0,7) \rightarrow (1,2) \rightarrow (2,0)(0,7)→(1,2)→(2,0)。
在本例中，叶子节点Y 6 = 20149512 Y_6=\texttt{20149512}Y6=20149512，认证路径值为：
- ( 0 , 7 ) = 8fc53ad8 (0,7) = \texttt{8fc53ad8}(0,7)=8fc53ad8
- ( 1 , 2 ) = 7890c8b6 (1,2) = \texttt{7890c8b6}(1,2)=7890c8b6
- ( 2 , 0 ) = 076f83f6 (2,0) = \texttt{076f83f6}(2,0)=076f83f6
有了这些值，验证者可以重新计算根节点的值，并将其与已发布的根值进行比较。
计算根节点
使用上述符号表示，根节点为n o d e ( a , 0 ) node(a, 0)node(a,0)。该值作为 Merkle 签名的一部分存储，用于验证已揭示私钥的认证路径。
要计算根节点，我们始终需要计算树中的每一个节点。有不同方法可以实现这一点。可以使用 TreeHash 算法 计算node(a, 0)。或者更简单的方法是，先计算树底部的2 a 2^a2a个节点，然后对每一层进行逐对哈希，直到只剩一个元素。
示例 Merkle 树的计算
我们特殊定义的"弱"哈希函数H HH在 Python 中的实现如下。（注意，哈希摘要是对十六进制字符串解码后的二进制值进行计算然后截断得到的。）
importhashlibdefH(val:str)->str:"""Weak hash function returning hex-encoded 4-byte hash."""returnhashlib.sha256(bytes.fromhex(val)).hexdigest()[:8]伪代码中的一些示例计算。
Revealed secret key, Y_6='20149512' authpath=['8fc53ad8', '7890c8b6', '076f83f6'] node(0,6)=H(Y_6)=H('20149512')='ef137f8f' node(0,7)=authpath[0]='8fc53ad8' node(1,3)=H('ef137f8f'+'8fc53ad8')='e090b2ce' node(1,2)=authpath[1]='7890c8b6' node(2,1)=H('7890c8b6'+'e090b2ce')='009a4350' node(2,0)=authpath[2]='076f83f6' root=node(3,0)=H('076f83f6'+'009a4350')='03583268'Python 代码
我们的简单函数make_sk用于派生私钥值：
defmake_sk(sk_seed,height,index):"""Generate a private key value given a secret key and address. :param str sk_seed: Secret key seed (hex string). :param int height: Height value to encode into address. :param int index: Index value to encode into address. :return: Derived private key value (4-byte hash as hex string). :rtype: str """adrs="{:04x}".format(height)+"{:04x}".format(index)DPRINT("adrs=",adrs,bytes.fromhex(adrs))returnH(seed+adrs)# Generate all keys at leaf level 0sk_seed='900150983cd24fb0'# The first 8 bytes of MD5('abc')keys=[make_sk(sk_seed,0,i)foriinrange(8)]print("keys =",keys)# ['827efcd2', '29bb074b', 'a92eb2d2', 'e411ba45', 'f7d5e02e', 'a1644275', '20149512', '286c0ebd']使用hash_pairwise生成完整树
生成整棵树的一种直接方法是取一个包含2 n 2n2n个节点的数组，将值"逐对"哈希，生成包含n nn个节点的新数组。重复此过程直到只剩下一个节点——即根节点。
defhash_pairwise(hashes):"""Hash 2n hex values pairwise. :param list hashes: Array of 2*n hex strings to be hashed pairwise. :return: Array of n hex-encoded hash strings H(node_{2i} || node_{2i+1}) for 0 <= i < n. :rtype: list """n=len(hashes)//2out=[''forxinrange(n)]foriinrange(n):h=H(hashes[2*i]+hashes[2*i+1])out[i]=hreturnout# Hash the keys to leaf nodeshashes=[H(k)forkinkeys]print("leaf nodes=",hashes)# Compute the Merkle tree nodeswhile(len(hashes)>1):hashes=hash_pairwise(hashes)print(hashes)root=hashes[0]print(f"Root node is{root}")assert(root=="03583268")输出：
keys = ['827efcd2', '29bb074b', 'a92eb2d2', 'e411ba45', 'f7d5e02e', 'a1644275', '20149512', '286c0ebd'] size=8 leaf nodes= ['33d97727', 'cbe3b654', 'db516084', 'c700ae29', '59bb626f', '804c9bdb', 'ef137f8f', '8fc53ad8'] ['9aed1e96', '2da82279', '7890c8b6', 'e090b2ce'] ['076f83f6', '009a4350'] ['03583268'] Root node is 03583268使用 TreeHash 算法生成认证路径
以下 Python 代码演示了使用我们简单哈希函数的 TreeHash 算法。gen_auth_path为给定叶子节点生成认证路径，利用"与 1 异或"技巧向上查找兄弟节点。compute_node递归计算树中某个节点的值及其所有后代。
defcompute_node(sk_seed,i,z):"""Compute a node in the Merkle tree. :param str sk_seed: Secret key seed (hex string). :param int i: Index of the node. :param int z: Height of the node. :return: Hash value of the node. :rtype: str """node=Noneifz==0:sk=make_sk(sk_seed,0,i)node=H(sk)DPRINT(f"node: i ={i}sk={sk}node={node}")else:lnode=compute_node(sk_seed,2*i,z-1)rnode=compute_node(sk_seed,2*i+1,z-1)node=H(lnode+rnode)DPRINT(f"node: ({z},{i}){lnode}||{rnode}={node}")returnnodedefgen_auth_path(sk_seed,a,idx):"""Generate authentication path (AUTH) for a leaf. :param str sk_seed: Secret key seed (hex string). :param int a: Height of the AUTH path. :param int idx: Leaf index for which to generate the AUTH. :return: List of node hashes (hex strings) forming the AUTH path. :rtype: list """auth=[None]*aforjinrange(a):s=idx//(1<<j)^1DPRINT(f"j={j}s={s}")auth[j]=compute_node(sk_seed,s,j)DPRINT(f"auth[{j}]={auth[j]}")returnauth a=3idx=6print(f"leaf_index={idx}")print(f"sk[{idx}]={keys[idx]}")auth=gen_auth_path(sk_seed,a,idx)print("auth =",auth)# auth = ['8fc53ad8', '7890c8b6', '076f83f6']# Compute root nodeDPRINT("Computing root...")root=compute_node(sk_seed,0,a)print(f"root={root}")assert(root=='03583268')输出：
leaf_index=6 sk[6]=20149512 auth = ['8fc53ad8', '7890c8b6', '076f83f6'] root=03583268另外，我们也可以使用hash_pairwise函数，在已知全部 8 个公钥值的情况下计算认证路径：
# Hash the keys to leaf nodeshashes=[H(k)forkinkeys]print("public keys =",hashes)# Compute AUTHPATH given public keys in `hashes`a=3idx=6print(f"leaf_index={idx}")print(f"sk[{idx}]={keys[idx]}")authpath=[''forxinrange(a)]i=idx^1j=0authpath[j]=hashes[i]forjinrange(1,a):hashes=hash_pairwise(hashes)i=(i//2)^1authpath[j]=hashes[i]print("authpath =",authpath)# authpath = ['8fc53ad8', '7890c8b6', '076f83f6']输出：
public keys = ['33d97727', 'cbe3b654', 'db516084', 'c700ae29', '59bb626f', '804c9bdb', 'ef137f8f', '8fc53ad8'] leaf_index=6 sk[6]=20149512 authpath = ['8fc53ad8', '7890c8b6', '076f83f6']验证认证路径
以下展示如何验证上述硬编码的认证路径，已知可信的根节点值和已揭示的私钥。
# Required root value in Merkle treeroot="03583268"# Authentication pathauthpath=["8fc53ad8","7890c8b6","076f83f6",]print("authpath=",[xforxinauthpath])# Known key valuesk="20149512"# Y_6print(f"sk={sk}")# Compute leaf value above skidx=6ht=0node=H(sk)# leaf node (public key)print(f"pk={node}")forapinauthpath:print(f"(ht,idx)={ht},{idx}")# Get last bit of child idxlastbit=idx&1# Move up to next levelidx>>=1ht+=1print(f"child node={node}")print(f"authpath={ap}")# Last bit of child determines left/right order of authpathif(lastbit):print(f"m1,m2={ap}{node}")node=H(ap+node)else:print(f"m1,m2={node}{ap}")node=H(node+ap)print(f"node={node}")print(f"Required root={root}")assert(root==node)输出：
authpath= ['8fc53ad8', '7890c8b6', '076f83f6'] sk=20149512 pk=ef137f8f (ht,idx)=0,6 child node=ef137f8f authpath=8fc53ad8 m1,m2=ef137f8f 8fc53ad8 node=e090b2ce (ht,idx)=1,3 child node=e090b2ce authpath=7890c8b6 m1,m2=7890c8b6 e090b2ce node=009a4350 (ht,idx)=2,1 child node=009a4350 authpath=076f83f6 m1,m2=076f83f6 009a4350 node=03583268 Required root=03583268