Part 7 · 1 chapters · ~8 min

Merkle Trees and Anti-Entropy

Hash trees, comparing replicas in logarithmic steps, anti-entropy repair in Cassandra and Dynamo-style stores, Merkle proofs, tamper-evident logs (Certificate Transparency, audit logs), Git's object model, and hash chains for financial audit trails.

Comparing large datasets cheaply

code

// a hash chain: each audit record commits to the previous one, so any edit breaks every later hash
const h = (prev: string, rec: object) => createHash('sha256').update(prev + JSON.stringify(rec)).digest('hex');
let prev = '0'.repeat(64);
for (const rec of auditRecords) { rec.hash = h(prev, rec.body); prev = rec.hash; }   // store prev hashes; verify by recomputing
// a Merkle tree generalises this: proofs that one record is included need only log2(n) hashes

MERKLE TREES AND ANTI-ENTROPY

compare two replicas by comparing a few hashes

swipe the figure sideways, or tap expand for full screen

1/4

hash ranges

Each replica hashes its key ranges, then hashes pairs of hashes up to a single root. Equal roots mean identical data (with overwhelming probability).

hashes of hashes up to a rootequal roots = equal data