algorithm - 树哈希 : How to verify if a range is tree-hash-aligned?

Question

“Tree Hash”是一个类似于 Merkle Tree/Tiger Hash Tree 的概念，Amazon Glacier 使用它来验证给定数据流的子集的数据完整性。

为了在检索数据时从 Amazon Glacier 接收树哈希，指定的字节范围必须“树哈希对齐”。

The concept of "tree hash aligned" is described here.

引用自开发者文档:

A range [A, B] is tree-hash aligned with respect to an archive if and only if when a new tree hash is built over [A, B], the root of the tree hash of that range is equivalent to a node in the tree hash of the whole archive. [...]

Consider [P, Q) as the range query for an archive of N megabytes (MB) and P and Q are multiples of one MB. Note that the actual inclusive range is [P MB, Q MB – 1 byte], but for simplicity, we show it as [P, Q). With these considerations, then

• If P is an odd number, there is only one possible tree-hash aligned range—that is [P, P + 1 MB).
• If P is an even number and k is the maximum number, where P can be written as 2k * X, then there are at most k tree-hash aligned ranges that start with P. X is an integer greater than 0. The tree-hash aligned ranges fall in the following categories:
  • For each i, where (0 <= i <= k) and where P + 2i < N, then [P, Q + 2i) is a tree-hash aligned range.
  • P = 0 is the special case where A = 2[lgN]*0

现在的问题是:如果给定范围 [startByte, endByte] 是树哈希对齐的，我如何以编程方式验证？编程语言无关紧要。

测试用例:

[0,0) => true
[0,1) => true
[0,2) => false
[0,3) => true
[1,2) => false
[4,5) => true

Answer 1

这里是 is_treehash_aligned 函数在 Python 中的基本实现:

import math

def max_k(x):
    return 1 + max_k(x/2) if x % 2 == 0 else 0

def is_treehash_aligned(P, Q):

    if (Q < P):
        return False
    elif (P % 2 == 1):
        return Q == P
    else:
        ilen = Q - P + 1    # size(interval)
        if  not (((ilen & (ilen - 1)) == 0) and ilen != 0):
            return False    # size(interval) ~ not power of two
        if P == 0:
            return True
        else:
            k = max_k(P)
            i = int(math.log(ilen, 2))
            return i <= k

if (__name__ == "__main__"):
    ranges = [(0, 0), (0, 1), (0, 2), (0, 3), (1, 2), \
              (4, 5), (6, 7), (2, 4), (6, 8), (5, 6), \
              (4, 4), (1, 1), (4194304, 5242879), \
              (4194304, 5242880), (4194304, 5242881)]

    for r in ranges:
        ret = is_treehash_aligned(*r)
        print("[" + str(r[0]) + ", " + str(r[1]) + ") => " + str(ret))

输出是:

[0, 0) => True
[0, 1) => True
[0, 2) => False
[0, 3) => True
[1, 2) => False
[4, 5) => True
[6, 7) => True
[2, 4) => False
[6, 8) => False
[5, 6) => False
[4, 4) => True
[1, 1) => True
[4194304, 5242879) => True
[4194304, 5242880) => False
[4194304, 5242881) => False

注意:

• 我采用了您的符号来表示间隔，而不是说明提供的符号。因此，可以假设每个间隔都是兆字节对齐。
• 测试用例 [4194304, 5242880) 的结果与您在原始问题中提出的不同，尽管我仔细检查了它并且我有点相信它是正确的。
• 如果 N 是已知的，但在您的测试用例中不是这种情况，那么当 P == 0 时，也应该接受任何范围 s.t. Q >= floor(N)，而且不仅仅是大小为2 的幂 的那些。对于子树，右边没有其他东西，可以进行类似的论证。这两种情况都符合给定 here 的树哈希对齐的定义 ，但不是用于识别它的说明。

---

注意:问题和description问题似乎令人困惑。

1. 测试用例用符号[A, B)给出，其中A是起始 block 的索引，B 是结束 block (包括) 的索引，假设整个存档由一个数组组成——从N< 的0-- 开始索引/em> 每个 block 大小 1 MB(可能最后一个除外)。例如:

   [0,0) => true
   [0,1) => true
   [0,2) => false
   [0,3) => true
   [1,2) => false
   [4,5) => true
   

   但是，说明假定范围是用符号[P MB, Q MB – 1 byte]给出的。

2. 说明具有误导性。

   例如，这里说:

   If P is an even number and k is the maximum number, where P can be written as 2k * X, then there are at most k tree-hash aligned ranges that start with P

   power 符号似乎被省略了，可能是由于错误的 HTML 代码，因为句子应该是 "the largest k s.t. P = (2^k)*X"。

   另一个例子是:

   For each i, where (0 <= i <= k) and where P + 2i < N, then [P, Q + 2i) is a tree-hash aligned range.

   假设 Q = P + 1、i > 0 和 k > 0。那么区间 [P, Q + 2^i) 的大小为 = Q + 2^i - P = P + 1 + 2^i - P = 2^i + 1 > 1 。但是，根据构造，不存在这样的树哈希对齐范围，其奇数大小大于 1。命题应该是:“[...]，那么 [P, P + 2^i) 是一个树哈希对齐的范围”。