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 idx6idx6。使用a aa位二进制数表示该索引6 110 b 6 110\text{b}6110b。我们可以利用这些二进制位从根节点出发绘制一条到达索引为 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}01→11→110→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 n1n1在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≤ha各有一个。要计算高度大于零的认证节点值需要递归计算其子节点的值。注意这需要计算树中除路径上节点之外的所有节点的值。要查找上一层级中认证节点的索引计算⌊ i d x / 2 ⌋ ⊕ 1 \lfloor idx/2 \rfloor \oplus 1⌊idx/2⌋⊕1。在 Python 中a3# Number of levelsidx6# leaf indexauthpath[0]*a authpath[0]idx^1foriinrange(1,a):idxidx//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_620149512 authpath[8fc53ad8, 7890c8b6, 076f83f6] node(0,6)H(Y_6)H(20149512)ef137f8f node(0,7)authpath[0]8fc53ad8 node(1,3)H(ef137f8f8fc53ad8)e090b2ce node(1,2)authpath[1]7890c8b6 node(2,1)H(7890c8b6e090b2ce)009a4350 node(2,0)authpath[2]076f83f6 rootnode(3,0)H(076f83f6009a4350)03583268Python 代码我们的简单函数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(seedadrs)# Generate all keys at leaf level 0sk_seed900150983cd24fb0# 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_{2i1}) for 0 i n. :rtype: list nlen(hashes)//2out[forxinrange(n)]foriinrange(n):hH(hashes[2*i]hashes[2*i1])out[i]hreturnout# Hash the keys to leaf nodeshashes[H(k)forkinkeys]print(leaf nodes,hashes)# Compute the Merkle tree nodeswhile(len(hashes)1):hasheshash_pairwise(hashes)print(hashes)roothashes[0]print(fRoot node is{root})assert(root03583268)输出keys [827efcd2, 29bb074b, a92eb2d2, e411ba45, f7d5e02e, a1644275, 20149512, 286c0ebd] size8 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 nodeNoneifz0:skmake_sk(sk_seed,0,i)nodeH(sk)DPRINT(fnode: i {i}sk{sk}node{node})else:lnodecompute_node(sk_seed,2*i,z-1)rnodecompute_node(sk_seed,2*i1,z-1)nodeH(lnodernode)DPRINT(fnode: ({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):sidx//(1j)^1DPRINT(fj{j}s{s})auth[j]compute_node(sk_seed,s,j)DPRINT(fauth[{j}]{auth[j]})returnauth a3idx6print(fleaf_index{idx})print(fsk[{idx}]{keys[idx]})authgen_auth_path(sk_seed,a,idx)print(auth ,auth)# auth [8fc53ad8, 7890c8b6, 076f83f6]# Compute root nodeDPRINT(Computing root...)rootcompute_node(sk_seed,0,a)print(froot{root})assert(root03583268)输出leaf_index6 sk[6]20149512 auth [8fc53ad8, 7890c8b6, 076f83f6] root03583268另外我们也可以使用hash_pairwise函数在已知全部 8 个公钥值的情况下计算认证路径# Hash the keys to leaf nodeshashes[H(k)forkinkeys]print(public keys ,hashes)# Compute AUTHPATH given public keys in hashesa3idx6print(fleaf_index{idx})print(fsk[{idx}]{keys[idx]})authpath[forxinrange(a)]iidx^1j0authpath[j]hashes[i]forjinrange(1,a):hasheshash_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_index6 sk[6]20149512 authpath [8fc53ad8, 7890c8b6, 076f83f6]验证认证路径以下展示如何验证上述硬编码的认证路径已知可信的根节点值和已揭示的私钥。# Required root value in Merkle treeroot03583268# Authentication pathauthpath[8fc53ad8,7890c8b6,076f83f6,]print(authpath,[xforxinauthpath])# Known key valuesk20149512# Y_6print(fsk{sk})# Compute leaf value above skidx6ht0nodeH(sk)# leaf node (public key)print(fpk{node})forapinauthpath:print(f(ht,idx){ht},{idx})# Get last bit of child idxlastbitidx1# Move up to next levelidx1ht1print(fchild node{node})print(fauthpath{ap})# Last bit of child determines left/right order of authpathif(lastbit):print(fm1,m2{ap}{node})nodeH(apnode)else:print(fm1,m2{node}{ap})nodeH(nodeap)print(fnode{node})print(fRequired root{root})assert(rootnode)输出authpath [8fc53ad8, 7890c8b6, 076f83f6] sk20149512 pkef137f8f (ht,idx)0,6 child nodeef137f8f authpath8fc53ad8 m1,m2ef137f8f 8fc53ad8 nodee090b2ce (ht,idx)1,3 child nodee090b2ce authpath7890c8b6 m1,m27890c8b6 e090b2ce node009a4350 (ht,idx)2,1 child node009a4350 authpath076f83f6 m1,m2076f83f6 009a4350 node03583268 Required root03583268