跳到主要内容

2. Cryptographic Components (密码学组件)

2. Cryptographic Components (密码学组件)​

2.1. Merkle Hash Trees (Merkle 散列树)​

日志使用二叉 Merkle 散列树 (Merkle Hash Tree) 以实现高效审计. 散列算法为 SHA-256 [FIPS.180-4] (注意在本实验中此算法固定, 但预期每个日志能够指定散列算法). Merkle 树散列 (Merkle Tree Hash) 的输入为数据条目列表; 这些条目将被散列以形成 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)}. (注意叶与内部结点的散列计算不同. 这种域分离 (domain separation) 是为提供第二原像抗性 (second preimage resistance) 所必需的.)

注意我们不要求输入列表长度为 2 的幂. 所得 Merkle 树因此可能不平衡; 然而, 其形状由叶的数量唯一确定. (注: 此 Merkle 树与历史树 (history tree) [CrosbyWallach] 提案基本相同, 只是我们定义处理非满树的方式不同.)

2.1.1. Merkle Audit Paths (Merkle 审计路径)​

Merkle 散列树中某一叶的 Merkle 审计路径 (Merkle audit path) 是为计算该树的 Merkle 树散列所需的最短附加结点列表. 树中每个结点要么是叶结点, 要么由其正下方 (即朝向叶) 的两个结点立即计算得出. 在沿树向上 (朝向根) 的每一步, 将审计路径中的一个结点与迄今计算出的结点组合. 换言之, 审计路径由从某叶到树根所需计算路径上缺失结点列表组成. 若从审计路径计算出的根与真实根一致, 则该审计路径即为该叶存在于树中的证明.

给定树的有序输入列表 D[n] = {d(0), ..., d(n-1)}, 第 (m+1) 个输入 d(m) (0 <= m < n) 的 Merkle 审计路径 PATH(m, D[n]) 定义如下:

单叶树且输入列表 D[1] = {d(0)} 的路径为空:

PATH(0, {d(0)}) = {}

对于 n > 1, 令 k 为小于 n 的最大 2 的幂. n 元列表中第 (m+1) 个元素 d(m) (n > m) 的路径递归定义为

PATH(m, D[n]) = PATH(m, D[0:k]) : MTH(D[k:n]) for m < k; and

PATH(m, D[n]) = PATH(m - k, D[k:n]) : MTH(D[0:k]) for m >= k,

其中 : 表示列表串联, D[k1:k2] 如前表示长度为 (k2 - k1) 的列表 {d(k1), d(k1+1),..., d(k2-1)}.

2.1.2. Merkle Consistency Proofs (Merkle 一致性证明)​

Merkle 一致性证明 (Merkle consistency proofs) 证明树的仅追加属性. Merkle 树散列 MTH(D[n]) 与先前公布的 m 个叶 MTH(D[0:m]) (m <= n) 的 Merkle 一致性证明, 是 Merkle 树中验证两树前 m 个输入 D[0:m] 相同的结点列表. 因此, 一致性证明必须包含一组中间结点 (即对输入的承诺), 足以验证 MTH(D[n]), 且 (其子集) 同一组结点可用于验证 MTH(D[0:m]). 我们定义输出 (唯一) 最小一致性证明的算法.

给定树的有序输入列表 D[n] = {d(0), ..., d(n-1)}, 先前 Merkle 树散列 MTH(D[0:m]) (0 < m < n) 的 Merkle 一致性证明 PROOF(m, D[n]) 定义为:

PROOF(m, D[n]) = SUBPROOF(m, D[n], true)

当 m = n 时, 若 m 为最初请求 PROOF 的值 (表示子树 Merkle 树散列 MTH(D[0:m]) 已知), 则子证明为空:

SUBPROOF(m, D[m], true) = {}

当 m = n 时, 子证明为承诺输入 D[0:m] 的 Merkle 树散列; 否则:

SUBPROOF(m, D[m], false) = {MTH(D[m])}

对于 m < n, 令 k 为小于 n 的最大 2 的幂. 子证明递归定义.

若 m <= k, 右子树条目 D[k:n] 仅存在于当前树中. 我们证明左子树条目 D[0:k] 一致, 并添加对 D[k:n] 的承诺:

SUBPROOF(m, D[n], b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n])

若 m > k, 左子树条目 D[0:k] 在两棵树中相同. 我们证明右子树条目 D[k:n] 一致, 并添加对 D[0:k] 的承诺.

SUBPROOF(m, D[n], b) = SUBPROOF(m - k, D[k:n], false) : MTH(D[0:k])

此处 : 为列表串联, D[k1:k2] 如前表示长度为 (k2 - k1) 的列表 {d(k1), d(k1+1),..., d(k2-1)}.

所得证明中的结点数上界为 ceil(log2(n)) + 1.

2.1.3. Example (示例)​

含 7 个叶的二叉 Merkle 树:

              hash
             /    \
            /      \
           /        \
          /          \
         /            \
        k              l
       / \            / \
      /   \          /   \
     /     \        /     \
    g       h      i      j
   / \     / \    / \     |
   a b     c d    e f     d6
   | |     | |    | |
  d0 d1   d2 d3  d4 d5

d0 的审计路径为 [b, h, l].

d3 的审计路径为 [c, g, l].

d4 的审计路径为 [f, j, k].

d6 的审计路径为 [i, k].

同一棵树分四步递增构建:

      hash0          hash1=k
      / \              /  \
     /   \            /    \
    /     \          /      \
    g      c         g       h
   / \     |        / \     / \
   a b     d2       a b     c d
   | |              | |     | |
  d0 d1            d0 d1   d2 d3

            hash2                    hash
            /  \                    /    \
           /    \                  /      \
          /      \                /        \
         /        \              /          \
        /          \            /            \
       k            i          k              l
      / \          / \        / \            / \
     /   \         e f       /   \          /   \
    /     \        | |      /     \        /     \
   g       h      d4 d5    g       h      i      j
  / \     / \             / \     / \    / \     |
  a b     c d             a b     c d    e f     d6
  | |     | |             | |     | |    | |
 d0 d1   d2 d3           d0 d1   d2 d3  d4 d5

hash0 与 hash 之间的一致性证明为 PROOF(3, D[7]) = [c, d, g, l]. c, g 用于验证 hash0, 此外 d, l 还用于表明 hash 与 hash0 一致.

hash1 与 hash 之间的一致性证明为 PROOF(4, D[7]) = [l]. 可使用 hash1=k 与 l 验证 hash.

hash2 与 hash 之间的一致性证明为 PROOF(6, D[7]) = [i, j, k]. k, i 用于验证 hash2, 此外 j 还用于表明 hash 与 hash2 一致.

2.1.4. Signatures (签名)​

多种数据结构会被签名. 日志必须使用以下之一: 采用 NIST P-256 曲线的椭圆曲线签名 (数字签名标准 (Digital Signature Standard, DSS) [DSS] 第 D.1.2.3 节), 或 RSA 签名 (RSASSA-PKCS1-V1_5 配合 SHA-256, [RFC3447] 第 8.2 节), 密钥长度至少 2048 位.

最后于 更新