反向树建筑(有奇数个孩子)

Question

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

(图片来自这里)

我已经创建了一个读取1 MB块的函数和一个即时计算其哈希值的类,但后来我完全挣扎:

在我的应用程序中,我创建了一个类chunk,它接受数据并计算__init__方法中的哈希值,并保存父项和子项(如常规树).当用户打开文件时,将使用各自的哈希值(在此示例中为7个块实例)正确生成这些块实例.

现在我有两个相互联系的大问题:

1. 如何反向构建这棵树？我基本上需要为最低层上的每两个块实例创建一个新块,并根据这两个哈希值计算哈希值.但是我在哪里存储那个父母？在父母的孩子和反向树行走？
2. 如何与奇数个孩子一起工作？如果我有一个遍历每个父层的算法,那么我会错过最后一个(0.5 MB)块.

我在SO上查看了这个主题但是这个方法只适用于偶数儿童计数,但并不总是这样.

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

提前致谢!

保罗

Answer 1

首先计算层数，然后

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 中的第二个参数处理:)