2.1. Merkle哈希树

2.1. Merkle哈希树

日志使用二叉Merkle哈希树来实现高效审计。哈希算法是SHA-256 [FIPS.180-4] (请注意,这在此实验中是固定的,但预计每个日志都能够指定哈希算法)。Merkle树哈希的输入是数据条目列表;这些条目将被哈希以形成Merkle哈希树的叶子。输出是单个32字节的Merkle树哈希。给定n个输入的有序列表D[n] = {d(0), d(1), ..., d(n-1)},Merkle树哈希(MTH)定义如下:

空列表的哈希是空字符串的哈希:

MTH({}) = SHA-256().

包含一个条目的列表的哈希(也称为叶子哈希)是:

MTH({d(0)}) = SHA-256(0x00 || d(0)).

对于n > 1,设k为小于n的最大2的幂(即k < n <= 2k)。n元素列表D[n]的Merkle树哈希递归定义为:

MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n])),

其中||是连接,D[k1:k2]表示长度为(k2 - k1)的列表{d(k1), d(k1+1),..., d(k2-1)}。(请注意,叶子和节点的哈希计算不同。这种域分离是提供第二原像抵抗所必需的。)

请注意,我们不要求输入列表的长度是2的幂。因此,生成的Merkle树可能不平衡;但是,其形状由叶子数量唯一确定。(注意:此Merkle树本质上与历史树[CrosbyWallach]提案相同,除了我们的定义以不同方式处理非完整树。)