A sketch of the Merkleization logic used for the Eth1.0 deposit contract and the verification logic used in the Eth2.0 beacon chain.

merkle.py

import hashlib

def version_check():
    import sys
    assert sys.version_info.major >= 3
    assert sys.version_info.minor >= 6
    assert sys.version_info.micro >= 5


version_check() # using hashlib features from 3.6.5


# DEPTH can be changed but should be large enough so
# that the tree should contain no more than FIRST_LEAF values
DEPTH = 8
FIRST_LEAF = 2**DEPTH
ZERO_HASH = b'\0' * 32


def hash(data):
    m = hashlib.sha3_256()
    m.update(data)
    return m.digest()


def add_to_tree(tree, leaf_index, data):
    """
    Inserts ``data`` at ``leaf_index`` into the Merkle ``tree``.
    Note that nodes are 1-indexed, not 0-indexed; e.g. the root is at tree[1].
    """
    index = leaf_index + FIRST_LEAF
    tree[index] = hash(data)
    for i in range(DEPTH):
        index //= 2
        left = tree.get(index * 2, ZERO_HASH)
        right = tree.get(index * 2 + 1, ZERO_HASH)
        tree[index] = hash(left + right)
    return tree


def build_tree(values):
    """
    Build the full tree as if a validator called ``deposit`` for each value in ``values``.
    Mirrors the relevant logic from the Vyper contract.
    """
    deposit_count = 0
    tree = {}
    for value in values:
        tree = add_to_tree(tree, deposit_count, value)
        deposit_count += 1
    return tree


def generate_proof(tree, leaf_index, depth):
    """
    Returns a Merkle branch from ``tree`` attesting to the inclusion of the value at ``leaf_index``.
    """
    index = leaf_index + FIRST_LEAF
    proof = []
    for _ in range(depth):
        if index % 2:
            next_index = index - 1
        else:
            next_index = index + 1
        next_node = tree.get(next_index, ZERO_HASH)
        proof.append(next_node)
        index //= 2
    return proof


def verify_proof(leaf, branch, depth, index, root):
    """
    Ensure that reconstructing the path up the Merkle tree using nodes from ``branch`` starting at ``leaf`` yields the expected ``root``.
    """
    value = leaf
    for i in range(depth):
        if (index // (2**i)) % 2:
            value = hash(branch[i] + value)
        else:
            value = hash(value + branch[i])
    return value == root


def run():
    """
    Run a demo where we build a tree, generate a proof for each value and then verify the proof.
    """
    values = [x.to_bytes(32, byteorder='big') for x in range(FIRST_LEAF)]
    tree = build_tree(values)
    root = tree[1]

    proofs = [generate_proof(tree, i, DEPTH) for i in range(len(values))]
    for (i, (value, proof)) in enumerate(zip(values, proofs)):
        try:
            tree_index = i + FIRST_LEAF
            assert verify_proof(hash(value), proof, DEPTH, tree_index, root)
        except AssertionError:
            print('FAILED: index: {}, proof: {}'.format(tree_index, list(elem.hex() for elem in proof)))


run()