Reverse tree construction (with an odd number of children)

Question

I just found out about the Glasier AWS service and wanted to write a small Python application to upload files through the REST API. I looked at the desired headers and came across x-amz-sha256-tree-hash . I need to calculate the SHA-256 hash of the whole file, as well as the hash of the parent element of all the hashes of each block of 1 MB. This leads to the following tree:

(Image taken from here )

I already made a function that reads 1 MB of pieces and a class that calculates their hashes on the fly, but then I completely struggle:

In my application, I created a class called chunk that takes data and computes the hash in the __init__ method, and also contains parent and child elements (like a regular tree). When the user opens the file, these pieces instances will be correctly generated with their corresponding hashes (in this example it will be 7 block instances).

Now I have two big problems that are related to each other:

• How do I build this tree in reverse order? I basically need to make a new chunk for each of the two instances of the chunk on the bottom layer and calculate the hash based on these two hashes. But where can I keep this parent? In the daughters of the parent and do the return trip?
• How does it work with an odd number of children? If I have an algorithm that goes through each parent layer, I would skip the last (0.5 MB) fragment.

I checked this section on SO, but this method only works with an even number of children, which is not always given.

Can you help me find a way / algorithm / approach to solving this problem?

Thanks in advance!

Floor

Answer 1

First calculate the number of levels, then

 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 

Be sure to treat None as the second argument to hashofthem :)