8

我刚刚发现了 AWS Glacier 服务，并想编写一个小型Python 应用程序来通过 REST API 上传文件。我查看了所需的标题并偶然发现了x-amz-sha256-tree-hash. 我需要计算整个文件的 SHA-256 哈希值以及每个 1 MB 块的所有哈希值的父级哈希值。这导致以下树：

AWS 的 SHA-256 树散列程序

（图片取自这里）

我已经制作了一个读取 1 MB 块的函数和一个即时计算其哈希值的类，但后来我完全挣扎：

在我的应用程序中，我创建了一个名为的类chunk，它获取数据并计算__init__方法中的哈希值，并保存父项和子项（如常规树）。当用户打开一个文件时，这些块实例将使用它们各自的哈希正确生成（在这个例子中，这将是 7 个块实例）。

现在我有两个相互关联的大问题：

  1. 如何反向构建这棵树？我基本上需要为最低层上的每两个块实例创建一个新块，并根据这两个散列计算一个散列。但是我在哪里存储那个父母？在父母的孩子和做反向树行走？
  2. 这如何处理奇数个孩子？如果我有一个遍历每个父层的算法，那么我会错过最后一个（0.5 MB）块。

我在 SO 上查看了这个主题，但该方法仅适用于偶数儿童计数，这并不总是给出。

你能帮我找到解决这个问题的方法/算法/方法吗？

提前致谢！

保罗

4

1 回答 1

4

先计算层数，然后

def proclevel(levels):
    if levels > 0:
        generator = proclevel(levels - 1)
        temp = None
        for firsthash, secondhash in generator:
            if not temp: temp = hashofthem(firsthash, secondhash)
            else: yield temp, hashofthem(firsthash, secondhash); temp = None
        #If odd number of packets
        if temp: yield temp, None
    else:
        temp = None
        for chunk in chunks:
            if not temp: temp = hash(chunk)
            else: yield temp, hash(chunk); temp = None
        if temp: yield temp, None

确保将 None 作为 hashofthem 中的第二个参数处理 :)

于 2012-08-21T15:37:15.960 回答