Building a Merkle tree for data integrity verification

A Merkle tree is a binary tree of hashes that lets you prove a piece of data belongs to a larger dataset without revealing the whole set. Every leaf node holds the hash of a data block, and every internal node holds the hash of its two children concatenated together. The single hash at the top, called the root, summarises the entire structure below it. Change any leaf and the root changes, which makes the structure extraordinarily sensitive to tampering. Engineers reach for it in distributed ledgers, version control systems, certificate transparency logs, and peer-to-peer file sharing because it offers compact proofs that are cheap to verify.

The motivation behind implementing one from scratch is partly pedagogical and partly practical. Off-the-shelf libraries handle the heavy lifting, but a hand-rolled implementation exposes the mechanics that those libraries hide. In Australia, sectors that handle sensitive information such as healthcare providers bound by the My Health Records Act, financial institutions reporting to AUSTRAC, and mining firms operating out of Perth routinely need auditable trails. A correctly built Merkle tree lets an auditor in Sydney or Melbourne confirm that a submitted log file matches what was originally stored, using only a handful of hashes rather than the entire file.

How the tree structure works

At the bottom of the tree, the leaves correspond to the actual data you want to protect. Each leaf is hashed, usually with a cryptographic function like SHA-256, producing a fixed-size fingerprint. Adjacent leaves are paired, their hashes are concatenated, and the result is hashed again to form a parent node. That pairing continues upward, halving the number of nodes at each level, until only one node remains. This single surviving hash is the Merkle root, and it acts as a commitment to every byte in the dataset.

A useful mental model is to imagine the leaves as rows in a spreadsheet exported from a Brisbane-based logistics company's freight manifest. Each row contains shipment identifiers, weights, and timestamps. Hashing each row produces a short, opaque string that uniquely represents that row. Combining rows two at a time mirrors how auditors reconcile adjacent entries, and the root represents the entire reconciled ledger. If anyone edits a single shipment weight in Adelaide, the mismatch propagates upward and the root shifts, immediately flagging the change.

When the number of leaves is odd, the standard trick is to duplicate the last leaf so the tree stays balanced. Some implementations hash the duplicate with itself, others prepend a marker byte before rehashing. Either approach is acceptable as long as it is applied consistently across every tree your system constructs. Inconsistent handling between verifiers and producers is one of the most common sources of subtle bugs that only surface during audits.

Choosing the right hash function

The hash function you pick determines both the security guarantees and the performance characteristics of your tree. SHA-256 remains the workhorse for most applications because it offers strong collision resistance and is hardware-accelerated on modern x86 and ARM processors. SHA-3 and BLAKE2b are reasonable alternatives, with BLAKE2b often outperforming SHA-256 on smaller inputs and being popular in environments where speed matters more than regulatory familiarity.

For an Australian organisation subject to the Australian Signals Directorate's guidance or to APRA's CPS 234 standard on information security, sticking with SHA-256 keeps compliance conversations simple. Auditors recognise the algorithm, and tooling around it is mature. Resist the urge to use a non-cryptographic hash like MD5 or a fast checksum like CRC32; the savings in nanoseconds are not worth the loss of collision resistance, especially when the tree is meant to detect tampering by a determined adversary.

A practical consideration is whether to include a domain separation tag in your hashing step. Concatenating a fixed prefix like "MERKLE_LEAF_V1\0" before hashing prevents an attacker from presenting a hash as both a leaf and an internal node in a forged proof. This kind of structural separation is a small habit that pays off when the tree later gets adapted to new use cases, such as timestamping critical infrastructure logs in remote Western Australian sites.

Building the tree in Python

Python is a natural fit for prototyping Merkle trees because its dictionaries and lists map well to recursive tree structures. A clean implementation starts with a Node class that stores a hash, a left child, a right child, and an optional reference to the original data block. The constructor takes the raw bytes, hashes them with SHA-256, and stores the result as a hex digest for easy printing and comparison.

The core builder function takes a list of data blocks, hashes them into leaf nodes, then iteratively pairs adjacent nodes until only one remains. If the list has an odd length, the final node is duplicated. Each iteration produces the next level of the tree, and the final element is the Merkle root. Returning the root and the full level list makes verification routines easier to write later. Readers who want a deeper dive into Python syntax for this kind of work can browse Python programming tutorials for the language fundamentals.

For a concrete example, imagine a Melbourne-based fintech exporting end-of-day transaction summaries to regulators. Each block contains a timestamp, an account identifier, and a transaction count. Building a tree from these blocks produces a root that the company publishes alongside the file. Regulators at AUSTRAC, or any downstream consumer, can recompute the root from the file and compare it to the published value. A mismatch means either corruption or deliberate alteration, and the discrepancy can be pinpointed using a Merkle proof rather than re-reading every row.

Generating and verifying Merkle proofs

A Merkle proof, sometimes called a Merkle path or audit path, is the sequence of sibling hashes needed to reconstruct the root from a single leaf. Given a target leaf hash, a verifier asks the producer for the hash of its sibling, then the hash of the sibling's parent, and so on, until the root is reached. At each step, the verifier concatenates the sibling hash with the current hash in the correct order, hashes the result, and checks whether it matches the expected parent.

The order matters. If the target hash is the left child, the sibling is concatenated on the right, and vice versa. Many implementations store a single bit alongside each sibling to record which side it came from. A common bug is to assume a fixed concatenation order, which works fine in happy-path testing but fails the moment an odd number of leaves forces duplication. Keeping the side information explicit removes that entire class of defect.

Proof size grows logarithmically with the number of leaves, so for a dataset of one million blocks the proof contains roughly twenty hashes. That makes verification remarkably cheap compared with re-reading the entire dataset. In the context of the Notifiable Data Breaches scheme administered by the Office of the Australian Information Commissioner, an organisation can use such a proof to demonstrate to an assessor that a particular log entry was present at the time of an incident, without surrendering the whole log file. For those exploring how verification logic compares to other statistical checks, the bias-variance tradeoff review offers a useful parallel about balancing precision against complexity.

Recommendations for a clean implementation

A well-engineered Merkle tree implementation balances clarity with correctness, and a few habits make the difference between code that works on day one and code that survives a security review. The following points capture the most common lessons from production deployments across Australian financial services, healthcare, and resources companies.

• Hash each leaf with a domain separation tag to prevent cross-protocol confusion.
• Always handle the duplicate-leaf case explicitly, and store the choice in metadata rather than relying on convention.
• Use SHA-256 unless there is a specific reason to deviate, and document the algorithm version in the code.
• Keep verification code separate from construction code so it can be audited independently.
• Log the algorithm version alongside every root you publish, so future schema changes do not invalidate old proofs.
• Test with adversarial inputs that flip bits in leaves, swap siblings, and reorder proof steps, rather than only happy-path data.
• Consider publishing the root to a second, independent channel such as a notarised email, so a single point of compromise cannot undermine the whole scheme.