Merkle树遍历技术的研究

《Merkle树遍历技术的研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、http://www.elecfans.com电子发烧友http://bbs.elecfans.com电子技术论坛Merkle树遍历技术的研究朱娟，金德强，莫思泉（华南理工大学，广东广州510006）摘要：Merkle树应用于数字加密技术。它的遍历技术主要包含树的根节点生成和认证路径的生成。本文主要比较各种Merkle树的遍历技术，提出自己的遍历方法，并进行了实验仿真和对实验结果的分析。关键字：Merkle树；哈希；遍历TheResearchofTraverseofMerkleTreeZHUJuan,JINDe-qiang,MOSi-qu

2、an（SouthChinaUniversityofTechnology,Guangzhou,510006,China）Abstract：Merkletreeisusedindigitalencryptiontechnology.ThetraversaltechnologyofMerkletreeincludesthegenerationoftherootnodeoftreeandthecertificationpaths.Inthispaper,wecomparecomparathedifferenttraversalmethodsofM

3、erkletree,addressourowntraversalmethod,andanalyzetheexperimentalresault.Keywords：Merkletree;hash;traverse中图分类号:TP391.9文献标识码:A1引言[1]Merkle树又称哈希树，由RalphMerkle在1972年发明的，是指这样一个数据结构：树的每一个叶结点是一块数据的哈希值构成、每个父结点下面的所有子结点的哈希值组合到一起再进行哈希运算就得到它们的父结点；这个过程一直进行下去直至得到树的根结点。其主要优点是仅需通过对树根结点的

4、一次签名运算就可以对树上所有的叶结点独立地提供完整性认证。TophashHash0Hash1Hash0-0Hash0-1Hash1-0Hash1-1DataDataDataDatablock0block1block2block3图1Merkle树http://www.elecfans.com电子发烧友http://bbs.elecfans.com电子技术论坛Merkle树是一种满二叉树，使用多次哈希函数产生一个公钥。经常用于数字签名，因为它的每一个叶子节点的密钥都可以通过一定的认证路径被求出，再比较是否于公钥一致。认证路径是由树的每一层上

5、的一个节点组成，这些节点是由该叶子路径上的兄弟节点直到根节点的下一层节点为止，例如图1中block1的认证路径就是节点哈希0-0和哈希1。Merkle树的遍历问题是找到一个有效的算法按顺序输出每一个叶子节点的和其相应的认证路径的数据。[4]Merkle树在数据加密技术和分布式存储领域已经得到了广泛的应用,根节点的哈希值可以做为公钥,认证路径用来检测相应数据的合法性。2相关工作[1]中提出Merkle树的遍历目的是为了按顺序输出每一个叶子节点的和其相应的认证[1]路径的数据。目前有三种算法，第一个算法是Classic算法，第二个算法是FRA

6、CTAL算法[2][3]，第三个算法是LOG算法。通常整个遍历算法分为两步，第一步是生成Merkle树的根节点数据，通常使用TREEHASH算法，如下所示:f()表示相容性哈希算法，如SHA1。N1N2表示N1和N2连接为一个新的字符串。1.设leaf=start并且建立一个空栈2.如果栈顶的两个节点高度不相同，跳至4，否则进入33.合并：出栈一个节点，设为Nright出栈一个节点，设为Nleft计算Nparent=f(NleftNright),设Nparent的高度为Nleft的高度+1如果Nparent的高度为最大高度，则输出Npar

7、ent为树的根节点，并退出否则将Nparent进栈，返回24.计算新的叶子节点：N=f(leaf)，高度为零将N进栈leaf指向下一块数据跳至2第二步是输出每一个叶子节点的认证路径。Classic算法是基于堆栈和异或来实现，在TREEHASH的过程中把各层的堆栈初始值设置好，递增叶子节点的计数为leaf，在顺序计算hh(leaf+1+2)⊕2认证路径时，输出栈中的数据，再计算节点，重新设置各层的堆栈。2logNlog(2N/2)该算法每轮需要调用次哈希函数，并且需要最大为2个哈希值为存储空间。LOG算法跟Classic算法只有在输出阶段不

8、同，主要是在堆栈的重新设置方法上，对于2logN3logN每一个层次的堆栈采用不同的更新方法，需要调用次哈希函数，占用最大为个哈希值的存储空间。FRACTAL算法则是利用子树的移动实现遍历，在