计算机科学

首页 > 计算机科学

哈希树

2018-08-27 10:37:56     所属分类:散列
二叉哈希树示例。哈希 0-0 和 0-1 分别是数据块 L1 和 L2 的哈希值。哈希 0 是将哈希 0-0 和 0-1 连接后所取得的哈希值。

在密码学及计算机科学中,哈希树hash tree)是一种树形数据结构,每个叶节点均以数据块的哈希作为标签,而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签 。哈希树能够高效、安全地验证大型数据结构的内容,是哈希链的推广形式[1]

哈希树的概念由瑞夫·墨克于 1979 年申请专利[2][3],故亦称墨克树Merkle tree)。

概述

哈希树中,哈希值的求取通常使用诸如SHA-2的加密哈希函数,但如果只是用于防止非故意的数据破坏,也可以使用不安全的校验和取得,比如CRC。

哈希树的顶部为顶部哈希(top hash),亦称根哈希(root hash)或主哈希(master hash)。以从 P2P 网络下载文件为例:通常先从可信的来源获取顶部哈希,如朋友告知、网站分享等。得到顶部哈希后,则整棵哈希树就可以通过 P2P 网络中的非受信来源获取。下载得到哈希树后,即可根据可信的顶部哈希对其进行校验,验证数据是否完整、是否遭受破坏。

参见

  • 二叉树
  • 哈希表
  • 区块链

参考文献

  1. ^ Farooq Anjum,Petros Mouchtaris. 无线Ad Hoc 网络安全. 北京:清华大学出版社. 2009.03: 86. ISBN 978-7-302-19337-1. 
  2. ^ Merkle, R. C. A Digital Signature Based on a Conventional Encryption Function. Advances in Cryptology — CRYPTO '87. Lecture Notes in Computer Science 293. 1988: 369. ISBN 978-3-540-18796-7. doi:10.1007/3-540-48184-2_32. 
  3. ^ US patent 4309569,Ralf Merkle,“Method of providing digital signatures”,发表于Jan 5, 1982,指定于The Board Of Trustees Of The Leland Stanford Junior University 

感谢您的支持,我会继续努力的!

扫码支持
1分,2分不嫌少,钱不钱的无所谓,重要的是你的话语激励我前行!

愿你每天温暖如春!!!

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
无需打赏可直接关闭阅读全文
1分,2分不嫌少,钱不钱的无所谓,重要的是你的话语激励我前行!

愿你每天温暖如春!!!


上一篇:完美散列
下一篇:布隆过滤器
相关推荐