What is a blockchain and how does hash chaining work?
A blockchain is an append-oriented linked list of blocks in which each block stores the cryptographic hash of its predecessor. This hash pointer makes changes to earlier blocks detectable, while consensus rules determine which history the network accepts.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Block Structure and Hash Chaining
A simplified proof-of-work-oriented block commonly contains:
-
Index: The block’s position in the chain.
-
Timestamp: The time the block was created.
-
Data: Transactions or other application-specific content.
-
Previous hash: The digest of the preceding block.
-
Nonce: A value varied while searching for a valid proof-of-work hash.
-
Hash: A digest of the block’s committed fields.
Hash algorithms are protocol-dependent. In this interview model, the hash is SHA-256; Python exposes it through hashlib.sha256(...).hexdigest(), which returns 64 lowercase hexadecimal characters.
-
The genesis block uses a previous-hash sentinel consisting of 64 zero hexadecimal characters, representing 256 zero bits, and computes
H0. -
Block 1 stores
H0as its previous hash and computesH1. -
Block 2 stores
H1as its previous hash and computesH2. -
If block 1’s data is modified, its computed hash differs from its stored
H1. Block 2 therefore references the wrong predecessor unless that descendant is also recomputed.
Hash chaining provides tamper evidence, not absolute immutability. A party controlling enough of the network can construct a replacement chain with internally valid links, so consensus, replication, and finality rules are also required.
Merkle Trees and Merkle Proofs
A Merkle tree organizes transaction hashes into a binary tree:
-
Each leaf contains a transaction hash.
-
Each internal node contains a hash derived from its children using the protocol’s defined encoding and ordering.
-
The root, or Merkle root, summarizes all transactions in the tree.
A Merkle proof contains the sibling hashes on the path from one transaction to the root. A verifier hashes the transaction with each sibling and compares the resulting root with the known Merkle root. This verifies one transaction without receiving every other transaction.
For edge cases, an empty transaction set has no Merkle root unless the protocol defines one; a single leaf may itself be the root; and duplicate transactions remain distinct leaves unless the protocol deduplicates them.
Proof of Work and Consensus
Proof of work is a search problem. Miners repeatedly vary values such as the nonce until the block-header hash satisfies the protocol’s target-difficulty condition. Verification checks the result, while finding an acceptable hash can require many attempts.
Bitcoin uses proof of work. Ethereum transitioned to proof of stake during The Merge in September 2022. Consensus mechanisms determine which transaction history nodes accept and help establish finality; hash chaining alone does not determine the canonical history.
Complexity
Space figures below include the recursion stack. An iterative validator and Merkle builder use an O(1) call stack. The chain and transaction list are excluded unless explicitly stated.
| Operation | Time | Space | Reason |
|---|---|---|---|
| Hash one fixed-size header | O(1) |
O(1) |
Processes a fixed number of bytes |
Validate n fixed-size blocks |
O(n) |
O(1) auxiliary |
Checks each block once; input chain excluded |
Store n fixed-size blocks |
O(n) total; amortized O(1) per append |
O(n) output storage |
Stores each block once |
Build a Merkle root from n fixed-size leaves |
O(n) |
O(n) tree data |
Hashes leaves and internal nodes |
| Verify one Merkle proof | O(log n) |
O(log n) when the proof is retained |
Follows one root-to-leaf path |
Find proof of work with per-attempt success probability p |
Best: O(1); expected: O(1/p); no finite worst-case guarantee without an attempt cap |
O(1) |
Each attempt is constant time; a capped search with m attempts is O(m) worst-case |
Common Pitfalls
-
Off-by-one errors: Define whether the genesis block has index
0or1, and validate the same convention consistently. -
Integer overflow: In fixed-width languages, ensure indices, nonces, and attempt counters cannot overflow.
-
Mutating input: Validation should treat the supplied chain as read-only and return a separate result.
-
Ignoring edge cases: Empty chains, a lone genesis block, duplicate application data, and negative-valued data need protocol-specific handling.
-
Trusting stored hashes: Recompute every block hash and verify every previous-hash link.
-
Forgetting visited state: It is unnecessary for a strictly linear chain, but graph-like traversal of forks or a DAG requires a visited set to prevent cycles.
-
Common follow-up questions: Interviewers may ask about Merkle proofs, fork resolution, finality, transaction ordering, or the difference between proof of work and proof of stake.