Merkle Tree Example

merkle_sample.py

from csv import reader
from hashlib import sha512
import sys

# Simple merkle tree example
# Invoke the script by calling "python merkle_sample.py "file1.csv" "file2.csv" to compare two merkle trees
class Merkle:

    def __init__(self, file):
        self.file = file

    def hashMerkle(self):
        hashes = []

        with open(self.file, 'r') as read_obj:
            file_reader = reader(read_obj)
            # Iterate over each row in the file
            for row in file_reader:
                for item in row:
                    # use sha512 (or any other hashing algorithm) to hash the items
                    hashes.append(
                        sha512(str(item).encode('utf-8')).hexdigest())  # utf encoding optional based on the data type

        print("\n########### Hashes for " +
              self.file + " ##################### \n")

        # Since the Merkle is primarily a binary tree, if you have odd number of rows, add another row in the data duplicating the last item
        if (len(hashes) % 2 != 0):
            hashes.append(hashes[-1])

        # generate binary tree
        while (len(hashes) > 1):
            j = 0

            for i in range(0, len(hashes) - 1):
                # hash every leaf and leaf + 1 and concantenate when they are of the same height
                hashes[j] = sha512(
                    (str(hashes[i] + hashes[i+1])).encode('utf-8')).hexdigest()

                i += 2
                j += 1

            lastDel = i - j
            # half the hash every iteration
            # remove all other items in the array to return the root
            del hashes[-lastDel]

        print(hashes)
        return hashes


if __name__ == "__main__":
    # pass in two files that you wish to compare
    file1 = sys.argv[1]
    file2 = sys.argv[2]
    merkle1 = Merkle(file1)
    merkle2 = Merkle(file2)
    # check if the merkle roots match
    assert merkle1.hashMerkle() == merkle2.hashMerkle(), 'Merkle root does not match'