Merkle Root and Proofs

A Merkle tree commits to a list of leaves with a single root hash. Each leaf is hashed, internal nodes hash their children, and a proof is the list of sibling hashes needed to recompute the root.

This problem uses SHA-256 (provided) with domain separation:

• HashLeaf(x) = SHA256(0x00 || x)
• HashNode(l, r) = SHA256(0x01 || l || r)

If a level has an odd number of nodes, duplicate the last node to form a pair.

Types and function signatures

type ProofStep struct {
    Hash [32]byte
    Left bool // true if Hash is the left sibling
}

func MerkleRoot(leaves [][]byte) [32]byte
func MerkleProof(leaves [][]byte, index int) []ProofStep
func VerifyMerkleProof(leaf []byte, proof []ProofStep, root [32]byte) bool

Behavior

• MerkleRoot returns the root hash. If leaves is empty, return zero hash.
• MerkleProof returns nil if index is out of range or leaves is empty.
• VerifyMerkleProof returns true if the proof reconstructs root.

Notes

• Proof steps are ordered from leaf level to root.
• Use the provided SHA-256 implementation (do not import crypto/sha256).