Skip to main content

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