Image Title

哈希树的特点很鲜明: 叶子节点存储的是数据文件,而非叶子节点存储的是其子节点的哈希值(称为MessageDigest) 这些非叶子节点的Hash被称作路径哈希值, 叶子节点的Hash值是真实数据的Hash值. 因为使用了树形结构, MT的时间复杂度为 O(logn)

比如下图中, 我们如果使用SHA1算法来做校验值, 比如数据块8对应的哈希值是H23, 则按照这个路径来看 应该有

H11=SHA1(H23∥H24)
H5=SHA1(H11∥H12)
H2=SHA1(H5∥H6)
H0=SHA1(H1∥H2)

其中∥是表联接的意思.

Image Title

应用举例

BitTorrent中应用[3,7]

在BT中, 通常种子文件中包含的信息是Root值, 此外还有文件长度、数据块长等重要信息. 当客户端下载数据块8时,在下载前,它将要求peer提供校验块8所需的全部路径哈希值:H24、H12、H6和H1. 下载完成后, 客户端就会开始校验, 它先计算它已经下载的数据块8的Hash值23, 记做H23′, 表示尚未验证. 随后会按照我在上一小节中给出的几个公式, 来依次求解 直到得到H0′并与H0做比较, 校验通过则下载无误. 校验通过的这些路径哈希值会被缓存下来, 当一定数量的路径哈希值被缓存之后,后继数据块的校验过程将被极大简化。此时我们可以直接利用校验路径上层次最低的已知路径哈希值来对数据块进行部分校验,而无需每次都校验至根哈希值H0.