Merkle Tree

A Merkle Tree implementation in Go, built from scratch for learning purposes in the weekend.

What is a Merkle Tree?

Think of it like this: you have a roster of Deadlock heroes and you want a single fingerprint (hash) that represents all of them. If anyone swaps, removes, or adds a hero, the fingerprint changes completely.

Say we have 8 heroes: Haze, Infernus, McGinnis, Wraith, Bebop, Dynamo, Kelvin, Seven.

                                    Root Hash
                                   /         \
                                  /           \
                                 /             \
                    H(Haze+Inf+McG+Wra)    H(Beb+Dyn+Kel+Sev)
                       /         \              /         \
                      /           \            /           \
               H(Haze+Inf)    H(McG+Wra)  H(Beb+Dyn)   H(Kel+Sev)
                /     \        /     \      /     \       /     \
           H(Haze) H(Inf) H(McG) H(Wra) H(Beb) H(Dyn) H(Kel) H(Sev)

Each leaf is the hash of a hero name. Each parent is the hash of its two children combined. You go level by level — leaves, pairs, pairs of pairs — until you get one hash at the top: the root.

That's it. Hash the leaves, pair them up, hash the pairs, repeat until you get one hash.

What if the number of heroes is odd?

If we have 5 heroes, the last one gets duplicated to make an even pair:

                                    Root Hash
                                   /         \
                                  /           \
                                 /             \
                    H(Haze+Inf+McG+Wra)    H(Beb+Beb)
                       /         \              /     \
                      /           \            /       \
               H(Haze+Inf)    H(McG+Wra)  H(Beb)    H(Beb)
                /     \        /     \       |          |
           H(Haze) H(Inf) H(McG) H(Wra)  H(Bebop)  H(Bebop)

This duplication happens at every level where the count is odd, not just at the leaves.

Merkle Proof

Here's where it gets interesting. Say someone gives you the root hash and claims "Dynamo is in this roster." You don't need to know all 8 heroes to verify that — you just need a proof path.

Let's prove Dynamo is in our 8-hero tree. The highlighted nodes show what we need:

                                    Root Hash           <- step 3: compare with known root
                                   /         \
                                  /           \
                                 /             \
                    [H(Haze+Inf+McG+Wra)]  H(Beb+Dyn+Kel+Sev)  <- step 2: combine with left sibling
                                                /         \
                                               /           \
                                        H(Beb+Dyn)      [H(Kel+Sev)]   <- step 1: combine with right sibling
                                         /     \
                                   [H(Beb)]  H(Dyn)   <- start here: hash "Dynamo"

The [brackets] are the sibling hashes we collect — that's the proof path:

1. H(Bebop) — sibling, on the left
2. H(Kel+Sev) — sibling, on the right
3. H(Haze+Inf+McG+Wra) — sibling, on the left

With just these 3 hashes, you can:

1. Hash Dynamo to get H(Dyn)
2. Combine H(Beb) + H(Dyn) to get H(Beb+Dyn)
3. Combine H(Beb+Dyn) + H(Kel+Sev) to get H(Beb+Dyn+Kel+Sev)
4. Combine H(Haze+Inf+McG+Wra) + H(Beb+Dyn+Kel+Sev) to get the root
5. Compare with the known root hash — if it matches, Dynamo is legit

You verified membership with just 3 hashes instead of checking all 8 heroes. In a tree with 1 million leaves, you'd only need ~20 hashes. That's the power of Merkle proofs.

Usage

Not sure why you'd want to use this instead of a battle-tested library, but hey, here you go:

// Build the tree
heroes := []string{"Haze", "Infernus", "McGinnis", "Wraith", "Bebop", "Dynamo", "Kelvin", "Seven"}
root := merkle.BuildMerkleTree(heroes)

// Generate a proof that Dynamo is in the roster
proof := merkle.MerkleProof(heroes, "Dynamo")

// Verify it — returns true if Dynamo is legit
valid := merkle.VerifyProof("Dynamo", proof, root.Hash)

Running Tests

# Run tests with visual output
make test

# Run tests with coverage report
make test-cover

# Run tests with race condition detection
make test-race