Merkle Proofs

Many components of NEAR Protocol rely on Merkle root and Merkle proofs. For an array of sha256 hashes, we define its merkle root as:

CRYPTOHASH_DEFAULT = [0] * 32
def combine_hash(hash1, hash2):
    return sha256(hash1 + hash2)

def merkle_root(hashes):
    if len(hashes) == 0:
        return CRYPTOHASH_DEFAULT
    elif len(hashes) == 1:
        return hashes[0]
    else:
        l = hashes.len();
        subtree_len = l.next_power_of_two() // 2;
        left_root = merkle_root(hashes[0:subtree_len])
        right_root = merkle_root(hashes[subtree_len:l])
        return combine_hash(left_root, right_root)

Generally, for an array of borsh-serializable object, its merkle root is defined as

def arr_merkle_root(arr):
    return merkle_root(list(map(lambda x: sha256(borsh(x)), arr)))

A Merkle proof is defined by:

pub struct MerklePathItem {
    pub hash: MerkleHash,
    pub direction: Direction,
}

pub enum Direction {
    Left,
    Right,
}

pub type MerkleProof = Vec<MerklePathItem>;

The verification of a hash h against a proclaimed merkle root r with proof p is defined by:

def compute_root(h, p):
    res = h
    for item in p:
        if item.direction is Left:
            res = combine_hash(item.hash, res)
        else:
            res = combine_hash(res, item.hash)
    return res

assert compute_root(h, p) == r