哈希树

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

哈希树的概念由瑞夫·墨克于 1979 年申请专利，故亦称墨克树（）。

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

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

参考文献
延伸閱讀

• explains both the hash tree structure and the use of it to handle many one-time signatures
• [https://web.archive.org/web/20080316033726/http://www.open-content.net/specs/draft-jchapweske-thex-02.html Tree Hash EXchange format (THEX)] a detailed description of Tiger trees

参见

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

外部連結

• [https://github.com/IAIK/merkle-tree A C implementation of a dynamically re-sizeable binary SHA-256 hash tree (Merkle Tree)]
• [https://github.com/richpl/merkletree Merkle Tree implementation in Java]
• [https://www.codeproject.com/articles/9336/thexcs-tth-tiger-tree-hash-maker-in-c Tiger Tree Hash (TTH) source code in C#], by Gil Schmidt
• [http://sourceforge.net/projects/tigertree/ Tiger Tree Hash (TTH) implementations in C and Java]
• [http://rhash.sourceforge.net/ RHash] , an open source command-line tool, which can calculate TTH and magnet links with TTH