Merkle Root and Proofs (Bitcoin-style)

Given a list of leaves, build a Merkle tree using double SHA-256.

Rules:

• Leaf hash: H(leaf) = SHA256(SHA256(leaf))
• Internal node: H(left || right) (also double SHA-256)
• If a level has an odd number of nodes, duplicate the last hash.
• The Merkle root of an empty list is the all-zero hash.

Types and functions

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

• MerkleProof returns nil if index is out of range or leaves is empty.
• Proof steps are ordered from leaf level to root.
• VerifyMerkleProof returns true if the proof reconstructs root.

Work one path before coding

For five leaf hashes a,b,c,d,e, define:

p=H(a||b), q=H(c||d), r=H(e||e)
u=H(p||q), v=H(r||r)
root=H(u||v)

The proof for the fifth leaf supplies (e,false), (r,false), then (u,true). A true flag means the sibling goes on the left. Steps use raw 32-byte hashes, not hexadecimal text. Inputs must remain unchanged.

For one leaf, the root is its hash and the valid proof has zero steps. This is compatible with invalid indices returning nil: VerifyMerkleProof interprets the supplied path, not the return status of proof generation.

What this API proves

Verification checks that the leaf and ordered proof steps reconstruct the supplied root. It does not receive a leaf count or claimed index, validate transactions, or decide whether the root is trusted.

In particular, [A,B,C] and [A,B,C,C] produce the same root under the required odd-duplication rule. Preserve this format; detecting tree mutation or proving exact list size would require additional protocol information. A one-leaf empty proof verifies only against that leaf's hash.

Constructing a root or a proof from scratch takes O(total leaf bytes + number of leaves) work. Generated proof size is logarithmic. Verification does one parent hash per supplied step, even for a noncanonical proof. Test these independently: a proof generator and verifier can agree while both implement the wrong format.

Lesson and worked proof · Checkpoint