Merkle Proofs

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:

` #![allow(unused)] fn main() { pub struct MerklePathItem { pub hash: MerkleHash, pub direction: Direction, }

pub enum Direction { Left, Right, }

pub type MerkleProof = Vec; } `

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

CODE3