zk proof of a leave

gistfile1.txt

#!python3

import hashlib
import math
import sys
from base64 import b64decode, b64encode

prooffile = "proof.txt"  # File where Merkle proof will be written.

MAXHEIGHT = 20  # Max height of Merkle tree


class MerkleProof:
    def __init__(self, leaf, pos, path):
        self.leaf = leaf  # data of leaf being checked
        self.pos = pos  # the position in the tree of the leaf being checked
        self.path = path  # the path of hashes, from bottom to the top of tree


def hash_leaf(leaf):
    """hash a leaf value."""
    sha256 = hashlib.sha256()
    sha256.update(b"leaf:")  # hash prefix for a leaf
    sha256.update(leaf)
    return sha256.digest()


def hash_internal_node(left, right):
    """hash an internal node."""
    sha256 = hashlib.sha256()
    sha256.update(b"node:")  # hash prefix for an internal node
    sha256.update(left)
    sha256.update(right)
    return sha256.digest()


##  The prefixes in the two functions above are a security measure.
##  They provide domain separation, meaning that the domain of a leaf hash
##  is seperated from the domain of an internal node hash.
##  This ensures that the verifier cannot mistake a leaf hash for 
##  an internal node hash, and vice versa. 


def gen_merkle_proof(leaves, pos):
    """Takes as input a list of leaves and a leaf position (pos).
       Returns the Merkle proof for the leaf at pos."""

    height = math.ceil(math.log(len(leaves), 2))
    assert height < MAXHEIGHT, "Too many leaves."
    # hash all the leaves
    state = list(map(hash_leaf, leaves))

    print("state"+str(state))
    # Pad the list of hashed leaves to a power of two
    padlen = (2 ** height) - len(leaves)
    state += [b"\x00"] * padlen

    # initialize a list that will contain the hashes in the proof
    path = []

    level_pos = pos  # local copy of pos
    initalhash = 0
    proof = []
    if pos % 2 == 0:
        initalhash = hash_internal_node(state[pos], state[pos + 1])
    else:
        initalhash = hash_internal_node(state[pos + 1], state[pos])
    proof.append(initalhash)
    print("(len(state)/2) - 1  "+str((len(state))))
    print("INITAL PROOF", str(proof))
    for level in range(height):
        path.clear()
        print("STATE=====initial " + str(state))
        for index in range(0,(len(state)),2):
            if(level==1):
                print("state===", str(index), state)
            else:
                # print("state===   ", str(level) + "  " + str(index) )
                root = hash_internal_node(state[index], state[index + 1])
                path.append(root)
        state.clear()

        state = path

        print("LEVEL "+str(level))
        print("STATE LEN "+str(len(state)))
        print("state value  "+str(state))
        # for pos in range(len(state) - 1):
        #     print("POS"+str(pos)+ str(state[pos]))
        #     if state[pos] == initalhash:
        #         print("HERE",str(state[pos]))
        #         print("HERE",str(initalhash))
        #         if pos % 2 == 0:
        #             initalhash = hash_internal_node(state[pos], state[pos + 1])
        #         else:
        #             initalhash = hash_internal_node(state[pos+1], state[pos])
        #     proof.append(initalhash)
        # if path:
        #     for index in range(len(path) - 1):
        #         if pos % 2 == 0:
        #             root = hash_internal_node(state[index], state[index + 1])
        #             path.append(root)
        #             if(pos==index+1):
        #                 path.append()
        #
        #         else:
        #             root = hash_internal_node(state[index + 1], state[index])
        #             path.append(root)
        # else:


#
# #######  YOUR CODE GOES HERE                              ######
# #######     to hash internal nodes in the tree use the    ######
# #######     function hash_internal_node(left,right)       ######

#
#
#     # return a list of hashes that makes up the Merkle proof
    return proof


### Helper function
def write_proof(filename, proof: MerkleProof):
    fp = open(filename, "w")
    print("leaf position: {pos:d}".format(pos=proof.pos), file=fp)
    print("leaf value: \"{leaf:s}\"".format(leaf=proof.leaf.decode('utf-8')), file=fp)
    print("Hash values in proof:", file=fp)
    for i in range(len(proof.path)):
        print("  {:s}".format(b64encode(proof.path[i]).decode('utf-8')), file=fp)
    fp.close()


### Main program
if __name__ == "__main__":
    # Generate 1000 leaves
    leaves = [b"data item " + str(i).encode() for i in range(1000)]
    print('\nI generated 1000 leaves for a Merkle tree of height 10.')
    # Generate proof for leaf #743
    print("leaves[pos]"+str(leaves[743]))
    pos = 743
    path = gen_merkle_proof(leaves, pos)
    print("path===="+str(path))
    # proof = MerkleProof(leaves[pos], pos, path)
    #
    # # write proof to file
    # write_proof(prooffile, proof)
    # root = hash_leaf(leaves[743])
    # print(hash_internal_node(root,hash_leaf(leaves[743])))
    # print('I generated a Merkle proof for leaf #{} in file {}\n'.format(pos,prooffile))
    sys.exit(0)