SHA-256 Merkle tree

As described in its documentation, Amazon S3 Glacier requires that all uploaded files come with a checksum computed as a Merkle Tree using SHA-256.

Specifically, the SHA-256 hash is computed for each 1MiB block of the file. And then, starting from the beginning of the file, the raw hashes of consecutive blocks are paired up and concatenated together, and a new hash is computed from each concatenation. Then these are paired up and concatenated and hashed, and the process continues until there is only one hash left, which is the final checksum. The hexadecimal representation of this checksum is the value that must be included with the AWS API call to upload the object (or complete a multipart upload).

Implement this algorithm in your language; you can use the code from the SHA-256 task for the actual hash computations. For better manageability and portability, build the tree using a smaller block size of only 1024 bytes, and demonstrate it on the RosettaCode title image with that block size. The final result should be the hexadecimal digest value a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c.

Go

<lang go>package main

import (

   "crypto/sha256"
   "fmt"
   "io"
   "log"
   "os"

)

func main() {

   const blockSize = 1024
   f, err := os.Open("title.png")
   if err != nil {
       log.Fatal(err)
   }
   defer f.Close()

   var hashes [][]byte
   buffer := make([]byte, blockSize)
   h := sha256.New()
   for {
       bytesRead, err := f.Read(buffer)
       if err != nil {
           if err != io.EOF {
               log.Fatal(err)
           }
           break
       }
       h.Reset()
       h.Write(buffer[:bytesRead])
       hashes = append(hashes, h.Sum(nil))
   }
   buffer = make([]byte, 64)
   for len(hashes) > 1 {
       var hashes2 [][]byte
       for i := 0; i < len(hashes); i += 2 {
           if i < len(hashes)-1 {                
               copy(buffer, hashes[i])
               copy(buffer[32:], hashes[i+1])
               h.Reset()
               h.Write(buffer)
               hashes2 = append(hashes2, h.Sum(nil))
           } else {
               hashes2 = append(hashes2, hashes[i])
           }
       }
       hashes = hashes2
   }
   fmt.Printf("%x", hashes[0])
   fmt.Println()

}</lang>

Output:

a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c

Phix

<lang Phix>include builtins\libcurl.e include builtins\sha256.e

constant ONE_MB = 1024 * 1024

function merkle(string filename, url, integer block_size=ONE_MB)

   if not file_exists(filename) then
       printf(1,"Downloading %s...\n",{filename})
       CURLcode res = curl_easy_get_file(url,"",filename) -- (no proxy)
       if res!=CURLE_OK then
           string error = sprintf("%d",res)
           if res=CURLE_COULDNT_RESOLVE_HOST then
               error &= " [CURLE_COULDNT_RESOLVE_HOST]"
           end if
           crash("Error %s downloading file\n", {error})
       end if  
   end if  
   string data = get_text(filename)
   sequence blocks = {}
   for i=1 to length(data) by block_size do
       blocks = append(blocks,sha256(data[i..min(i+block_size-1,length(data))]))
   end for
   while length(blocks)>1 do
       integer l = 0
       for i=1 to length(blocks) by 2 do
           l += 1
           blocks[l] = iff(i<length(blocks)?sha256(blocks[i]&blocks[i+1])
                                           :blocks[i])
       end for
       blocks = blocks[1..l]
   end while
   return blocks[1]

end function

function asHex(string s) string res = ""

   for i=1 to length(s) do
       res &= sprintf("%02X",s[i])
   end for
   return res

end function

printf(1,"%s\n",asHex(merkle("title.png", "https://rosettacode.org/mw/title.png", 1024)))</lang>

Output:

a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c

Python

This version attempts to combine blocks as soon as possible to minimize the memory footprint.

<lang Python>#!/usr/bin/env python

compute the root label for a SHA256 Merkle tree built on blocks of a given
size (default 1MB) taken from the given file(s)

import argh import hashlib import sys

@argh.arg('filename', nargs='?', default=None) def main(filename, block_size=1024*1024):

   if filename:
       fin = open(filename, 'rb')
   else: 
       fin = sys.stdin
   
   stack = []
   block = fin.read(block_size)
   while block:
       # a node is a pair: ( tree-level, hash )
       node = (0, hashlib.sha256(block).digest())
       stack.append(node)

       # concatenate adjacent pairs at the same level
       while len(stack) >= 2 and stack[-2][0] == stack[-1][0]:
           a = stack[-2]
           b = stack[-1]
           l = a[0]
           stack[-2:] = [(l+1, hashlib.sha256(a[1] + b[1]).digest())]

       block = fin.read(block_size)
   
   while len(stack) > 1:
       # at the end we have to concatenate even across levels
       a = stack[-2]
       b = stack[-1]
       al = a[0]
       bl = b[0]
       stack[-2:] = [(max(al, bl)+1, hashlib.sha256(a[1] + b[1]).digest())]

   print(stack[0][1].hex())

argh.dispatch_command(main) </lang>

Output:

$ sha256tree.py --block-size=1024 title.png
a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c

Raku

<lang perl6>#!/usr/bin/env raku

compute the root label for a SHA256 Merkle tree built on blocks of a given
size (default 1MB) taken from the given file(s)

use Digest::SHA256::Native;

sub MAIN(Int :b(:$block-size) = 1024 * 1024, *@args) {

 my ($block, @blocks);
 my $in = @args ?? IO::CatHandle.new(@args) !! $*IN;
 @blocks.push(sha256($block)) while $block = $in.read($block-size);
 while (@blocks > 1) {
   my @out;
   for @blocks.batch(2) -> @b {
     @out.push( @b > 1 ?? sha256(@b[0] ~ @b[1]) !! @b[0] );
   }
   @blocks = @out;
 }
 say @blocks[0]».fmt('%02x').join;

}</lang>

Output:

$ sha256tree --block-size=1024 title.png
a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c