Hash Tree
A hash tree (Merkle tree) organizes hashes of data blocks into a binary tree: leaves are hashes of data blocks, internal nodes hash the concatenation of child hashes, and the root is the overall digest.
Purpose
Efficiently verifies large-data integrity — only O(log n) sibling hashes are needed to verify any leaf, without recomputing the whole tree.
Mechanism
Leaf h_i=H(data_i), internal node h=H(h_left || h_right), root h_root is the overall digest. Verifying leaf i needs the sibling hashes at each level along the leaf-to-root path (the authentication path).
Use cases
- Git commit trees
- Blockchain transaction verification
- P2P file integrity (BitTorrent)