首页 理论教育哈希树:P2P下载文件认证的重要工具

哈希树:P2P下载文件认证的重要工具

【摘要】:哈希树由Ralph Merkle提出,也称为Merkle树。哈希树的一个主要应用是对P2P网络下载的文件进行认证。接着,从任一不可信源可得到哈希树。若哈希树被破坏或是伪造的,尝试从另一信息源得到另一个哈希树,直到程序找到一个哈希树与主哈希匹配。每次当哈希树的一个分支被下载时,即使完整的哈希树还没得到,也可立即验证每一分支的完整性。对于大文件的情况,其哈希树也相对较大。图9-12 高度为3的哈希树

哈希树由Ralph Merkle提出,也称为Merkle树。哈希树是关于哈希值的树,其中叶节点是数据块(如文件中的数据块或文件集)的哈希值。树中更深的节点是它们子节点的哈希值。在图9-12中,H0是对H0,0H0,1哈希的结果:

H0=hH0,0|H0,1) (9-2)

哈希树常用二叉树实现,即每一节点有两个子节点。然而,每一节点也允许有更多的子节点。通常,密码哈希函数如SHA-1或Whirlpool用于哈希运算。哈希树最顶层有一个顶哈希(Top Hash)或称根哈希(Root Hash)、主哈希(Master Hash)。

哈希树的一个主要应用是对P2P网络下载的文件进行认证。通过P2P网络下载前,从可信源获取文件的主哈希。接着,从任一不可信源(如P2P网络中的任一对等实体)可得到哈希树。用可信的主哈希验证得到的哈希树。若哈希树被破坏或是伪造的,尝试从另一信息源得到另一个哈希树,直到程序找到一个哈希树与主哈希匹配。

每次当哈希树的一个分支被下载时,即使完整的哈希树还没得到,也可立即验证每一分支的完整性。这会成为一种优势,因为分割文件成小的数据块更有效,使得若文件在传输时被破坏,只有小数据块需要重传。对于大文件的情况,其哈希树也相对较大。然而,一个小分支可以快速下载。分支的完整性可以得到验证,然后可以下载其他数据块。

978-7-111-34574-9-Part02-22.jpg

图9-12 高度为3的哈希树