Skip to content
Data Structures & Algorithms

Blockchain interview questions and answers

50 questions, 18 with code. About 5 h 5 min to read them all.

By TestLab · Updated

Plan for an interview
50 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

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 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.

  1. The genesis block uses a previous-hash sentinel consisting of 64 zero hexadecimal characters, representing 256 zero bits, and computes H0.

  2. Block 1 stores H0 as its previous hash and computes H1.

  3. Block 2 stores H1 as its previous hash and computes H2.

  4. 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 0 or 1, 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.

2

What is the difference between public and private blockchains

A public blockchain is an open, permissionless network whose ledger anyone can independently validate, while a private blockchain admits only authorized participants and is governed by an organization or consortium. The key distinction is the permission and trust model, not simply whether the data is confidential.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Access, Permission, and Trust

Aspect Public Blockchain Private Blockchain
Participation Anyone may run a node, submit transactions, and independently validate the chain Only authorized organizations or nodes may participate
Identity Participants may be pseudonymous Identities are often known to the network operator, although pseudonyms are possible
Governance Community, protocol developers, miners, validators, and other network participants A single organization or consortium controls membership and policy
Data visibility Published on-chain transactions and state are generally transparent Visibility can be restricted or selectively disclosed; encryption is a separate design choice
Trust Protocol rules and consensus replace the need to trust a central operator Participants trust the operator or consortium to some degree, in addition to trusting the protocol

Consensus, Finality, and Immutability

  • Public consensus: Permissionless networks must resist Sybil attacks. Bitcoin uses Proof of Work (PoW), while Ethereum has used Proof of Stake (PoS) since September 2022.

  • Private consensus: Because membership is controlled, protocols such as Practical Byzantine Fault Tolerance, Raft, or Proof of Authority can provide lower latency and higher throughput. These are options, not requirements.

  • Finality: PoW and many probabilistic systems provide eventual rather than immediate finality. Some permissioned protocols offer deterministic finality under defined failure assumptions.

  • Immutability: Both types use hash chaining: changing an earlier block changes its hash and invalidates every later link. Private systems additionally depend on replicated validation, governance, access controls, and possibly legal agreements.

Blockchain Data Structures

  • A common teaching model represents a blockchain as a hash-linked list of blocks. A minimal block contains index, timestamp, data, previous_hash, nonce, and hash; real systems such as Ethereum use different header and transaction structures.

  • SHA-256 can be calculated with hashlib.sha256(payload).digest(). Hashing s bytes takes O(s) time because the digest algorithm processes the input bytes.

  • Blocks commonly commit to transactions through a Merkle tree. Its leaves are transaction hashes, and each internal node hashes its children. A Merkle proof supplies the sibling hashes on one leaf-to-root path, allowing a verifier to recompute the root and prove inclusion.

  • In PoW, miners perform a search problem: repeatedly change a candidate nonce, hash the block header, and test whether the digest is below the target. The expected number of attempts is inversely proportional to the probability that one candidate succeeds.

Complexity

Let n be the number of blocks or Merkle leaves.

Operation Time Complexity Space Complexity and Reason
Validate n linked blocks Best/average/worst O(n) for fixed-size blocks because every link is checked O(1) auxiliary space excluding the stored chain; O(n) if the chain input is counted
Build a Merkle tree Best/average/worst O(n) because every leaf and internal node is hashed once O(n) for the tree, including an O(log n) recursive stack if implemented recursively
Generate or verify one Merkle proof Best/average/worst O(log n) because only one root-to-leaf path is processed O(log n) for the proof; the verifier uses O(1) additional workspace
Find a valid PoW nonce Best O(1); expected O(1/p) hash attempts for success probability p; worst O(k_max) for a bounded search space O(1) auxiliary space excluding the candidate block

Use Cases and Examples

  • Public chains: Bitcoin and Ethereum are public networks suited to open participation, censorship resistance, global settlement, and applications where protocol-level verification is valuable.

  • Private chains: Supply-chain coordination, interbank settlement, internal auditing, and regulated record-keeping benefit from known participants and controlled governance. Hyperledger Fabric and R3 Corda are permissioned blockchain platforms.

  • Choose a public chain when open participation and independent verification are central. Choose a private chain when membership control, predictable performance, governance rights, or selective disclosure are more important.

Common Pitfalls and Interview Tips

  • “Private” does not automatically mean encrypted, trustless, or decentralized; a single organization may control the entire network.

  • A consortium blockchain is a permissioned/private network governed by several organizations, not a separate fundamental permission category.

  • The longest-chain rule with greatest accumulated work describes Bitcoin-style PoW, not every public chain.

  • A Merkle proof establishes transaction inclusion in a committed tree; it does not by itself establish that the transaction was valid.

  • For validation edge cases, an empty chain has no links to check, a one-block chain checks only its genesis and consensus rules, and duplicate transactions must be rejected by protocol rules rather than by hashing alone.

  • When asked “Why not a database?”, emphasize that a consortium blockchain provides a shared, tamper-evident ledger across organizations without giving one organization exclusive control.

3

What blockchain features provide security and integrity?

Blockchain security and integrity come from cryptographic hash chaining, authenticated transactions, and decentralized consensus. These features make unauthorized changes detectable and make rewriting accepted history costly, although their guarantees depend on the protocol’s consensus and security assumptions.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Security Features

  • Block structure: Conceptually, a blockchain is a linked list of blocks. A typical proof-of-work block contains an index or height, timestamp, transaction data, the previous block’s hash, a nonce, and its own hash.

  • Hash chaining: Each block commits to its predecessor through the previous block’s hash. Changing an earlier block changes its hash and therefore invalidates every subsequent link unless the chain is recomputed.

  • Cryptographic hashing: SHA-256 is a common example. Its preimage and collision resistance make finding a modified block with the required hash computationally expensive. In Python 3.12, hashlib.sha256(payload).digest() returns 32 bytes, while hashlib.sha256(payload).hexdigest() returns 64 hexadecimal characters.

  • Digital signatures: Signatures prove control of a private key and authorize a transaction or message. They do not establish legal ownership or replace consensus.

  • Decentralization: Independently operated participants and replicated ledgers increase the coordination cost of rewriting history and prevent no single operator from freely changing the accepted chain.

  • Consensus: Consensus rules determine which chain participants accept under specified assumptions. Bitcoin uses proof of work, while Ethereum transitioned to proof of stake in 2022.

Hash chaining provides tamper evidence, not absolute immutability. A coordinated rewrite may still be possible, and some protocols provide governance or emergency mechanisms that can change the rules under defined conditions.

Merkle Trees and Cryptographic Proofs

A Merkle tree hashes transaction leaves into a Merkle root stored in a block header. A Merkle proof contains the sibling hashes along a root-to-leaf path and can prove that a transaction belongs to the committed transaction set without revealing every other transaction.

  • Proof size: O(log t) hashes for t transactions.

  • Proof verification: O(log t) time, assuming one hash operation per proof element and constant-size digests.

  • Whole-tree construction: O(t) hash operations and O(t) auxiliary storage when raw transactions are hashed into leaves.

  • Whole-set verification: O(t) hash operations when the tree is constructed directly; separately verifying t independently supplied proofs takes O(t log t) hash operations in the worst case.

These deterministic bounds have the same best, average, and worst-case order. Merkle roots bind transactions to a block, while hash chaining binds blocks to one another.

Proof of Work as a Search Problem

In proof of work, a miner repeatedly changes a nonce until the block hash satisfies a difficulty target. Each attempt has a small probability of succeeding, making mining an expected search problem rather than a direct calculation.

For a simplified target requiring d leading hexadecimal zeroes, the expected number of attempts is approximately 16^d. With b bytes of serialized block input:

  • Best case: O(b) time if the first nonce succeeds.

  • Expected and average case: O(16^d × b) time.

  • Worst case: No finite bound if mining is not capped by an attempt limit.

  • Auxiliary space: O(b) for the serialized input; no recursion stack is used.

Real protocols encode numeric targets rather than only zero prefixes. Network difficulty is adjusted so aggregate network hashrate, rather than one miner’s hashrate, maintains the desired block-production rate.

Complexity of Hash-Chain Operations

For a chain of n blocks, each containing at most b serialized bytes:

  • Append and hash one block: O(b) time and O(b) auxiliary space for serialization; appending to an in-memory list is amortized O(1) and does not dominate hashing.

  • Validate the hash chain: O(nb) time because each block is hashed and checked once.

  • Validation auxiliary space: O(1) beyond the chain.

  • Stored chain size: O(nb), including the input chain itself.

These hash-chain validation bounds are the same in the best, average, and worst cases. When block sizes are treated as fixed, validation is conventionally stated as O(n) time and O(n) total storage. Transaction-signature and application-state validation have additional, scheme-dependent costs.

Common Pitfalls and Interview Tips

  • Hashing is not encryption: SHA-256 does not encrypt transaction data or provide confidentiality.

  • Signatures are not consensus: They authorize actions but do not decide which chain is accepted.

  • Tamper evidence is not immutability: Cryptographic links detect changes; security against sustained rewriting also depends on consensus and network assumptions.

  • A valid local chain may not be the accepted chain: Competing branches require distributed consensus to resolve.

  • Genesis rules are protocol-specific: Some protocols require a genesis block, while others permit an empty starting state; genesis fields and previous-hash conventions also vary.

  • Common follow-ups include Merkle-proof verification, chain forks, transaction signatures, consensus attacks, and the difference between tamper evidence and absolute immutability.

4

How does blockchain hash chaining prevent data tampering?

A blockchain protects data integrity through cryptographic hash chaining: each block contains the hash of the preceding block, so changing one block invalidates every link after it. Proof of work or proof of stake, together with network consensus, makes silently rewriting valid history computationally and economically impractical.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Integrity Mechanisms

A typical block contains:

  • Index: The block’s position in the chain.

  • Timestamp: When the block was created.

  • Data: Transactions or other application data.

  • Previous hash: The preceding block’s hash, acting as a backward-pointing hash pointer.

  • Nonce: A value varied during proof-of-work mining.

  • Hash: The SHA-256 digest of the block’s other fields.

SHA-256 makes accidental modifications easy to detect and makes finding a preimage or collision computationally impractical. If an attacker changes block 4, its stored hash no longer matches its contents. Block 5 also becomes invalid because it references the old hash of block 4.

Hash chaining alone does not make a local blockchain immutable. An attacker controlling enough resources could recompute an entire chain, so decentralized consensus is required to agree on which chain is valid.

Merkle Trees and Proofs

A Merkle tree summarizes a block’s transactions efficiently:

  1. Hash each transaction to create a leaf.

  2. Hash pairs of child nodes to create internal nodes.

  3. Continue until one root hash remains.

The Merkle root can be stored in the block header. A Merkle proof lists the sibling hashes needed to recompute the root for a particular transaction. Including the direction of each sibling is necessary when reconstructing the tree.

This allows a light client to verify that a transaction belongs to a block without downloading every transaction. The proof must also be checked against the trusted block header’s Merkle root.

Proof of Work

Proof of work frames block production as a search problem. A miner varies the nonce until the block hash satisfies a target, such as having a specified number of leading hexadecimal zeros.

  • Search space: Expected to require approximately 16^d hash attempts for d leading hexadecimal zeros.

  • Difficulty adjustment: Networks alter d to maintain a target block-production rate.

  • Consensus: Validators independently verify hashes, chain links, and the proof-of-work target.

Bitcoin uses proof of work. Ethereum moved to proof of stake in 2022, where validators stake funds and are selected to propose and attest to blocks.

Complexity

Let n be the number of blocks, b the encoded size of one block, t the number of transactions, and d the proof-of-work difficulty.

Operation Best case Average case Worst case Space
Hash one block O(b) O(b) O(b) O(b) temporary encoding
Validate a chain O(nb) O(nb) O(nb) O(b) auxiliary; stored input is O(nb)
Mine a block O(b) O(16^d · b) No fixed algorithmic bound O(b) auxiliary
Build a Merkle tree O(t) O(t) O(t) O(t)
Verify a Merkle proof O(log t) O(log t) O(log t) O(log t) for proof and path

The chain validator is iterative, so its recursion stack uses O(1) space. These bounds treat transaction data as fixed-size leaves; very large individual transactions also increase the cost of hashing them.

Code Example

This is a minimal educational implementation, not production-ready blockchain code.

from dataclasses import dataclass, replace
import hashlib
import json
import time


DIFFICULTY = 2
ZERO_HASH = "0" * 64


@dataclass(frozen=True)
class Block:
    index: int
    timestamp: float
    data: str
    previous_hash: str
    nonce: int
    hash: str


def _canonical_bytes(
    index: int,
    timestamp: float,
    data: str,
    previous_hash: str,
    nonce: int,
) -> bytes:
    payload = {
        "data": data,
        "index": index,
        "nonce": nonce,
        "previous_hash": previous_hash,
        "timestamp": timestamp,
    }
    return json.dumps(
        payload, sort_keys=True, separators=(",", ":")
    ).encode("utf-8")


def calculate_hash(
    index: int,
    timestamp: float,
    data: str,
    previous_hash: str,
    nonce: int,
) -> str:
    encoded = _canonical_bytes(
        index, timestamp, data, previous_hash, nonce
    )
    return hashlib.sha256(encoded).hexdigest()


def mine_block(index: int, data: str, previous_hash: str) -> Block:
    timestamp = time.time()
    nonce = 0

    while True:
        block_hash = calculate_hash(
            index, timestamp, data, previous_hash, nonce
        )
        if block_hash.startswith("0" * DIFFICULTY):
            return Block(
                index=index,
                timestamp=timestamp,
                data=data,
                previous_hash=previous_hash,
                nonce=nonce,
                hash=block_hash,
            )
        nonce += 1


def add_block(chain: list[Block], data: str) -> Block:
    if not chain:
        block = mine_block(index=0, data=data, previous_hash=ZERO_HASH)
    else:
        previous = chain[-1]
        block = mine_block(
            index=previous.index + 1,
            data=data,
            previous_hash=previous.hash,
        )

    chain.append(block)
    return block


def validate_chain(chain: list[Block]) -> bool:
    if not chain:
        return False

    for position, block in enumerate(chain):
        expected_previous = (
            ZERO_HASH if position == 0 else chain[position - 1].hash
        )
        if block.previous_hash != expected_previous:
            return False

        expected_hash = calculate_hash(
            block.index,
            block.timestamp,
            block.data,
            block.previous_hash,
            block.nonce,
        )
        if block.hash != expected_hash:
            return False

        if not block.hash.startswith("0" * DIFFICULTY):
            return False

    return True


if __name__ == "__main__":
    chain: list[Block] = []
    add_block(chain, "Genesis transaction")
    add_block(chain, "Second transaction")

    print(validate_chain(chain))  # True

    chain[1] = replace(chain[1], data="Tampered transaction")
    print(validate_chain(chain))  # False

Common Pitfalls

  • Trusting stored hashes alone: A validator must recompute each block hash.

  • Checking only adjacent links: Every block’s fields, hash, proof-of-work target, and previous hash must be checked.

  • Ignoring empty chains: The implementation treats an empty chain as invalid.

  • Assuming immutability is absolute: Consensus and consensus rules provide practical security; a local copy can always be rewritten.

  • Using insecure serialization: Production systems need a precisely defined canonical encoding to prevent ambiguous representations.

  • Assuming Merkle proofs replace consensus: A proof verifies inclusion, but the trusted root must come from an accepted block header.

Interviewers commonly follow up by asking how an attacker could recompute the chain, why Merkle proofs use O(log t) size, or how proof-of-stake prevents history rewriting.

5

What is decentralization in blockchain?

Decentralization in blockchain means that no single authority controls the ledger or determines its final state. Instead, independent nodes exchange transaction data, validate blocks, and reach consensus on the accepted history.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

A blockchain distributes three important responsibilities:

  • Data storage: Full nodes maintain their own copies of transaction history, although pruning and lightweight verification allow some participants to store less.

  • Validation: Nodes independently check transactions and blocks rather than trusting a central server.

  • Consensus: Participants agree on which valid history represents the blockchain, including when participants disagree or some nodes are malicious.

This differs from a conventional database, where one or a small number of servers control storage, permissions, updates, and ordering.

Data Structures Behind Decentralization

A blockchain is essentially a hash-linked list of blocks. A typical block contains:

  • Index: The block’s position or height.

  • Timestamp: When the block was created.

  • Data: Transactions or other block contents.

  • Previous hash: The hash of the preceding block.

  • Nonce: A value used by proof-of-work systems to vary the block hash.

  • Hash: A cryptographic digest computed over the block’s header and contents.

The previous hash acts as a hash pointer. If an older block is modified, its hash changes, which invalidates the next block’s previous_hash reference and creates detectable inconsistencies throughout the chain. For example, hashlib.sha256 can compute SHA-256 digests; Bitcoin uses double SHA-256 for its block-header hash.

Hash chaining provides tamper evidence, not tamper-proofing by itself. Preventing a modified history from becoming accepted also requires distributed consensus and many independent copies of the chain.

Consensus and Network Control

Different systems use different consensus mechanisms:

  • Bitcoin uses proof of work: Miners search for a nonce whose resulting hash satisfies the network’s difficulty target. Finding one valid candidate is expected to require approximately (2^b) hash attempts for a target with (b) leading zero bits.

  • Ethereum moved to proof of stake in 2022: Validators propose and attest to blocks based on staked cryptocurrency. Stake makes dishonest participation economically costly.

Consensus mechanisms limit how much power a participant can acquire. However, decentralization is not automatically perfect: concentration of mining, validation, node hosting, or governance can reintroduce centralized control.

Merkle Trees and Efficient Verification

A Merkle tree summarizes many transactions in a root hash:

  • Leaf hashes represent transactions.

  • Internal nodes hash their children.

  • The root hash commits to the entire transaction set.

A Merkle proof shows that a particular transaction belongs to the committed tree without revealing every other transaction. It contains the required sibling hashes from the leaf level to the root.

The following bounds exclude input storage from auxiliary space unless a row explicitly includes a produced result. The operations can use iterative implementations, so the recursion stack contributes (O(1)) space.

Operation Time complexity Space complexity Reason
Verify a hash-linked chain (O(n)) best, average, and worst (O(1)) auxiliary Each of (n) blocks requires one hash-link check; stored blocks are excluded
Build a balanced Merkle tree (O(n)) best, average, and worst (O(n)) including the tree Each transaction and internal node is processed once; source transactions are excluded
Produce a Merkle proof (O(log n)) best, average, and worst (O(log n)) including the proof A balanced tree has logarithmically many levels
Verify a Merkle proof (O(log n)) best, average, and worst (O(log n)) including the supplied proof Each proof element requires one hash computation
Find a proof-of-work nonce Best (O(1)), expected (O(2^b)), worst unbounded (O(1)) auxiliary Each nonce requires a hash attempt, with no guaranteed finite upper bound

These bounds assume bounded-size block headers and transactions. Arbitrarily large transaction payloads make processing costs depend on their total byte size.

Advantages and Limitations

  • Censorship resistance: A validator can reject a valid transaction, but cannot easily prevent every other node from accepting it.

  • Availability: Multiple independent copies reduce dependence on one server.

  • Auditability: Hash chaining and Merkle roots make historical changes detectable.

  • No single point of failure: The network can continue operating if some nodes fail.

  • Consensus overhead: Communication, consensus, and storage are more expensive than in a centralized database.

  • Remaining trust assumptions: Users still depend on node software, consensus security, key management, and the distribution of network power.

Common Pitfalls

  • Blockchain does not automatically mean anonymous: Pseudonymous addresses and privacy-oriented systems provide different guarantees.

  • Decentralization has degrees: Storage, validation, consensus, and governance may be decentralized to different extents.

  • A hash chain is not consensus: It detects changes but does not decide which competing history is accepted.

  • Merkle proofs prove inclusion: They do not prove that a transaction is valid or that all other included transactions are legitimate.

  • Proof-of-work has probabilistic runtime: The nonce trials follow a deterministic sequence, but the number of trials needed to find a valid hash has no guaranteed finite upper bound.

6

What role does consensus play in blockchain systems?

A consensus mechanism is the protocol through which independent blockchain participants agree on the valid order of transactions and the resulting shared state. It is important because it prevents conflicting histories and double-spending without requiring a central administrator.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Responsibilities

A consensus mechanism lets participants reach agreement despite network delays, crashes, or malicious behavior. Its main goals are:

  • Safety: conflicting finalized histories are not accepted as valid.

  • Liveness: honest participants can eventually make progress.

  • Ordering: transactions receive a consistent sequence.

  • Fault tolerance: the protocol tolerates some degree of Byzantine or dishonest behavior.

  • Finality: participants know when a transaction is sufficiently irreversible.

Consensus does not determine whether a transaction is valid; application rules perform that validation. Consensus agrees on which valid history the network should accept.

Relationship to the Blockchain Structure

A blockchain is effectively a hash-chained linked list. A typical block contains an index, timestamp, data, previous_hash, nonce, and hash.

Each block’s hash is calculated from its contents and the previous block’s hash. Changing an earlier block therefore changes its hash and every subsequent link, making unauthorized modification detectable. A common structure uses SHA-256 with Python’s hashlib, although Bitcoin uses double SHA-256 for transaction and Merkle-node identifiers.

Transactions are commonly organized into a Merkle tree:

  • Leaves represent transaction hashes.

  • Internal nodes hash their two children.

  • A Merkle proof supplies the path needed to prove that a transaction belongs to the block.

  • Verifying one proof requires O(log T) hash operations for a balanced tree containing T transactions.

Hash chaining provides tamper evidence, while consensus determines which chain participants accept when competing chains exist.

Common Consensus Models

Model How agreement is reached Important properties
Proof of Work Miners search for a nonce producing a hash below a target value Requires substantial computation; probabilistic finality
Proof of Stake Validators stake assets and attest or propose blocks Lower energy use; may use economic penalties through slashing
Byzantine Fault Tolerance Validators exchange votes and form quorums Often provides deterministic finality with known validator sets
Proof of Authority Designated validators validate blocks Simple and fast, but trust is concentrated among authorities

Bitcoin uses proof of work. Ethereum transitioned to proof of stake during the Merge in 2022.

Complexity and Resource Requirements

Consensus has no universal Big-O complexity because its cost depends on network latency, validator count, communication rounds, fault assumptions, and finality rules.

For the structures and proof-of-work search:

  • Proof-of-work search: with target difficulty d, the best case is O(1) hash attempts, the expected average case is O(2^d), and the standard random-hash model provides no finite deterministic worst-case guarantee. Each attempt uses O(1) auxiliary space, excluding the input.

  • Hash-chain validation: validating n fixed-size blocks takes O(n) time in the best, average, and worst cases because every block must be checked.

  • Validation space: streaming validation uses O(1) auxiliary space and no recursion stack, excluding the blockchain input. Storing n blocks requires O(n) total space, including the input.

  • Merkle proof verification: for a balanced tree with T ≥ 2, best, average, and worst-case time are O(log T); a single transaction takes O(1). The proof contains O(log T) hashes, so total space is O(log T) when the proof is stored. If it is streamed and treated as input, auxiliary space is O(1). The transaction list and recursion stack are not required.

Common Pitfalls and Interview Tips

  • Consensus and blockchain validation are different: the former agrees on history; the latter checks local rules.

  • Hash chaining detects modification but does not, by itself, stop nodes from following conflicting chains.

  • “Longest chain” is often imprecise; Bitcoin selects the chain with the greatest accumulated proof of work.

  • A Merkle proof proves inclusion, not transaction validity or finality.

  • Avoid claiming that consensus removes every possible attack or that a transaction becomes irreversible immediately.

  • Common follow-up questions ask about finality, Byzantine faults, network partitions, the 51% attack, why proof of stake uses slashing, and how Merkle proofs improve transaction verification.

7

How do blockchain consensus algorithms differ?

Blockchain consensus lets independent nodes agree on valid transactions and the canonical block history. Consensus families differ mainly in block-producer selection, fault assumptions, finality, communication costs, and incentives.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Consensus Families

Algorithm Agreement and finality Complexity
Proof of Work (PoW) Miners search for a nonce whose hash satisfies a difficulty target. Finality is probabilistic and depends mainly on honest hash power. Expected work is O(1/q) hash attempts for success probability q; best case O(1), with no useful worst-case bound from the target alone. Extra space is O(1), excluding the candidate header.
Proof of Stake (PoS) Validators are selected using protocol-specific stake-weighted rules and vote on proposals. Slashing and checkpoints may provide economic finality, but these mechanisms are not universal. A scan of n validators costs O(n) time and O(1) extra space, excluding the validator-set input; full selection and voting costs depend on the protocol.
Delegated Proof of Stake (DPoS) Token holders elect a smaller committee. Finality and decentralization depend on the election and voting rules. A straightforward all-to-all exchange costs O(rn²) message work for r rounds and O(n) working space, excluding validator input and transmitted messages.
Byzantine Fault Tolerance (BFT) Validators exchange proposals, votes, and commits through multiple rounds. Many protocols provide deterministic finality after a commit quorum, subject to network-timing assumptions. All-to-all implementations cost O(rn²) message work for r rounds and O(n) working space, excluding validator input and transmitted messages.
  • Proof of Work: Bitcoin uses PoW and double SHA-256. Discovery is expensive, while verification is cheap.

  • Proof of Stake: Ethereum moved to PoS during the Merge in 2022. Validators bond stake, propose or attest to blocks, and can be penalized for specified protocol violations.

  • Delegated Proof of Stake: A smaller elected committee can improve efficiency but introduces delegation, governance, and concentration risks.

  • BFT consensus: Permissioned networks and some PoS systems use voting-based agreement. Classic Byzantine protocols commonly require n ≥ 3f + 1 to tolerate f Byzantine validators; Tendermint instead states its condition in terms of less than one-third Byzantine voting power.

Blockchain Data Structures

A blockchain resembles a linked list of blocks, although consensus selects which competing chain is canonical. A proof-of-work-style block commonly contains:

  • Index: Position in the chain.

  • Timestamp: Block-creation time.

  • Data: Transactions or other payload.

  • Previous hash: A hash pointer to the preceding block.

  • Nonce: A value varied while searching for a valid PoW hash.

  • Hash: A digest over the block’s protected fields.

SHA-256, available through Python’s hashlib, links these fields. Altering historical data changes that block’s expected hash and all descendant hash links, creating tamper evidence rather than absolute immutability: a network can accept an alternative chain if its consensus rules select it.

Many designs use Merkle commitments for transactions. Bitcoin uses a binary Merkle tree; Ethereum uses a Merkle Patricia trie. Building a balanced binary Merkle tree over n transaction leaves takes O(n) time and O(n) space for the tree, excluding transaction input. A Merkle proof contains O(log n) sibling hashes and takes O(log n) time and proof space to verify when transaction hashes have fixed size.

PoW as a Search Problem

For each candidate header, a miner computes SHA-256 and checks whether the digest meets the target. If each attempt succeeds with probability q, the expected number of attempts is O(1/q). A target requiring approximately k leading zero bits gives q ≈ 2^-k and expected work near 2^k hashes.

Each attempt takes O(1) time over a fixed-size header and O(1) extra space. Difficulty changes q to adjust the expected time between blocks; it does not guarantee an exact production interval.

Trade-offs

  • Finality: PoW generally provides probabilistic settlement; BFT-style protocols can provide deterministic finality after their commit rounds, but network delay still affects wall-clock time.

  • Resources: PoW consumes electricity and mining capacity; PoS consumes bonded capital and validator infrastructure; BFT emphasizes communication and voting.

  • Fault model: PoW relies heavily on honest hash power. BFT explicitly tolerates a bounded Byzantine minority. PoS uses economic penalties and protocol-specific assumptions.

  • Governance: Mining power, stake, delegated votes, and validator identities create different concentration and coordination risks.

  • Performance: Transaction throughput is not determined by consensus family alone; execution, networking, batching, and sharding also matter.

Common Pitfalls

  • Distinguish block validation from consensus: validation checks protocol rules, while consensus selects among competing histories.

  • Hash chaining does not itself prevent forks.

  • Do not describe all BFT systems as immediate or use the one-third threshold universally.

  • Do not claim that every PoS or DPoS implementation has the same finality or communication model.

  • Common follow-ups concern double spending, fork choice, slashing, Merkle proofs, and the distinction between block inclusion and finality.

8

How does blockchain consensus work across distributed nodes?

Consensus is the process through which distributed nodes agree on which transactions and blocks constitute the canonical blockchain. A blockchain combines replicated validation, cryptographic hash chaining, and an agreement mechanism such as proof of work or proof of stake.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Consensus Model

A typical consensus process has four stages:

  1. Proposal: A participant proposes a candidate block containing valid transactions.

  2. Validation: Every node independently checks transactions, block rules, hashes, and the selected consensus rules.

  3. Chain selection: Nodes choose the valid chain with the greatest accumulated consensus weight.

  4. Finality: Additional confirmations or finality checkpoints make transactions increasingly difficult to reverse.

The exact rules depend on the blockchain:

  • Bitcoin uses proof of work. Nodes select the chain with the greatest accumulated proof of work, not necessarily the chain containing the most individual blocks.

  • Ethereum moved from proof of work to proof of stake during The Merge in September 2022. Validators stake assets and attest to blocks.

  • Permissioned blockchains may use Byzantine fault-tolerance protocols such as Practical Byzantine Fault Tolerance.

Consensus therefore comes from the complete protocol, not from hashing alone.

Data Structures and Cryptography

A blockchain behaves like a linked list of blocks. Each block normally contains:

  • index: Its position in the chain.

  • timestamp: When it was created.

  • data: Transactions or other payload.

  • previous_hash: The hash of the preceding block.

  • nonce: A value varied during proof-of-work mining.

  • hash: The hash of the current block’s header and data.

SHA-256, commonly implemented with Python’s hashlib, maps the serialized block to a fixed 256-bit digest. Changing the previous block’s data changes its hash, which changes the next block’s previous_hash. This hash chaining makes modifications detectable.

A Merkle tree is built by hashing transaction pairs repeatedly until one Merkle root remains. The root is stored in the block header. A Merkle proof contains the sibling hashes needed to reconstruct that root, allowing a lightweight client to verify that a transaction is included without receiving the entire block.

Hash chaining provides tamper evidence, while consensus determines which history the network accepts.

Proof-of-Work Search

Proof of work is a computational search problem. A miner repeatedly varies nonce and computes the block hash until it satisfies a target such as:

hash_value < 2^(256 - difficulty)

With difficulty d, a random search requires approximately 2^d attempts on average. Miners gain influence through computational work, while honest nodes independently reject blocks with invalid hashes or transactions.

The code below is a minimal educational implementation. It is not production-ready: it has no networking, persistence, transaction rules, signature verification, resource limits, or fork-selection logic.

Code Example

from dataclasses import dataclass, replace
import hashlib
import json
import time


ZERO_HASH = "0" * 64


@dataclass(frozen=True)
class Block:
    index: int
    timestamp: int
    data: str
    previous_hash: str
    nonce: int
    difficulty: int
    hash: str


def calculate_hash(block: Block) -> str:
    """Calculate a block hash while excluding the hash field itself."""
    header = {
        "index": block.index,
        "timestamp": block.timestamp,
        "data": block.data,
        "previous_hash": block.previous_hash,
        "nonce": block.nonce,
        "difficulty": block.difficulty,
    }
    encoded = json.dumps(
        header, sort_keys=True, separators=(",", ":")
    ).encode("utf-8")
    return hashlib.sha256(encoded).hexdigest()


def mine_block(
    index: int,
    timestamp: int,
    data: str,
    previous_hash: str,
    difficulty: int,
) -> Block:
    """Find a nonce satisfying the proof-of-work target."""
    if not 1 <= difficulty <= 256:
        raise ValueError("difficulty must be between 1 and 256")

    target = 1 << (256 - difficulty)
    nonce = 0

    while True:
        candidate = Block(
            index=index,
            timestamp=timestamp,
            data=data,
            previous_hash=previous_hash,
            nonce=nonce,
            difficulty=difficulty,
            hash="",
        )
        digest = calculate_hash(candidate)

        if int(digest, 16) < target:
            return replace(candidate, hash=digest)

        nonce += 1


def validate_chain(chain: list[Block]) -> bool:
    """Validate hashes, links, indices, and proof-of-work in a chain."""
    if not chain:
        return True

    for position, block in enumerate(chain):
        if not 1 <= block.difficulty <= 256:
            return False

        if block.index != position:
            return False

        expected_previous = (
            ZERO_HASH if position == 0 else chain[position - 1].hash
        )
        if block.previous_hash != expected_previous:
            return False

        if len(block.hash) != 64:
            return False

        if calculate_hash(block) != block.hash:
            return False

        target = 1 << (256 - block.difficulty)
        if int(block.hash, 16) >= target:
            return False

    return True


if __name__ == "__main__":
    genesis = mine_block(
        index=0,
        timestamp=int(time.time()),
        data="hello",
        previous_hash=ZERO_HASH,
        difficulty=10,
    )
    print(validate_chain([genesis]))  # True

    tampered = replace(genesis, data="tampered")
    print(validate_chain([tampered]))  # False

Complexity

Let n be the number of blocks, k the serialized size of one block, m the number of transactions, and d the proof-of-work difficulty.

Operation Time complexity Space complexity Reason
Hash one block Best, average, worst: O(k) O(1) auxiliary SHA-256 processes the serialized input once; time proportional to the size of the block data.
Validate a chain Best: O(k); valid or worst-case: O(nk) O(1) auxiliary Each block is hashed once; the worst case checks the entire chain. Stored chain data occupies O(nk).
Mine proof of work Best: O(1); average: O(2^d); worst: no finite bound O(1) auxiliary The nonce search is probabilistic and has no guaranteed deadline.
Build a Merkle tree Best, average, worst: O(m) O(m) if stored Each transaction and internal node participates in the tree.
Verify a Merkle proof Best, average, worst: O(log m) O(log m) auxiliary A balanced tree requires one sibling hash per level.

Interview Tips

  • Do not equate “longest chain” with Bitcoin’s rule; use greatest accumulated proof of work.

  • A valid hash is not a valid transaction. Consensus requires independent transaction and block validation.

  • The example accepts an empty chain and validates a one-block genesis chain. Duplicate indices, invalid previous hashes, incorrect hashes, failed proof of work, and negative difficulty are rejected.

  • Blockchain structure is linear, so concepts such as already sorted input, disconnected graphs, and graph cycles do not apply.

  • Common follow-up questions ask about fork choice, 51% attacks, transaction finality, Merkle proofs, and the difference between proof of work and proof of stake.

9

What is a blockchain node and what does it do?

A blockchain node is a software participant that maintains blockchain data, validates blocks and transactions, exchanges data with peers, and may participate directly in consensus. Nodes can also provide blockchain state to wallets, explorers, and applications.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Node Types and Responsibilities

A node typically validates protocol rules, stores blockchain data, propagates valid objects, serves queries, and participates in consensus where required. These roles are not mutually exclusive:

Role Data and responsibility
Full node Stores complete blocks and validates and propagates the chain
Archival node Retains the full chain and historical state for old-state queries
Light/SPV client Uses block headers and Merkle proofs rather than the full chain
Miner or validator Performs proof-of-work mining or proof-of-stake attestation duties

Bitcoin primarily uses proof of work, where miners search for a valid nonce. Ethereum transitioned to proof of stake in September 2022, where validators attest to blocks.

Blocks and Hash Chaining

A blockchain is a linked list of blocks. A simplified block contains:

  • index: Its height in the chain.

  • timestamp: Its creation time.

  • data: Transactions or other content.

  • previous_hash: The preceding block’s SHA-256 digest.

  • nonce: A value varied during proof-of-work search.

  • hash: The SHA-256 digest of the block’s other fields.

The previous_hash field is the hash pointer to the preceding block. Changing historical data changes that block’s hash and invalidates subsequent links. This provides tamper evidence, not absolute immutability: consensus rules may eventually accept a different chain.

Merkle Trees and Proofs

A Merkle tree hashes transactions into leaves, hashes pairs into internal nodes, and continues until one Merkle root remains. A light client uses a Merkle proof containing sibling hashes to verify that a transaction belongs to the committed root without downloading every transaction.

The tree requires O(T) additional space for T transactions; the transaction input itself is not counted. Proof generation returns O(log T) data, while verification uses O(log T) time and O(log T) space including the proof.

Consensus and Complexity

Proof of work is a search problem: vary the nonce until the block hash satisfies the difficulty target.

Operation Time Space Reason
Hash one block O(B) O(B) Serializes and hashes at most B bytes
Validate a chain O(nB) O(B) additional Hashes every block, serializing one at a time; input chain is not counted
Store a chain O(nB) O(nB) Stores serialized block data
Build a Merkle tree O(T) O(T) Processes all transaction leaves and internal nodes
Generate a proof O(log T) O(log T) Collects one sibling per tree level
Verify a proof O(log T) O(log T) including proof Hashes once per proof level
Proof-of-work search Best O(B); expected O(2^d × B); worst unbounded O(B) Each attempt hashes B bytes and succeeds with probability approximately 2^-d

All implementations are iterative, so the recursion stack is O(1).

Code Example

This educational in-memory node demonstrates SHA-256 hashing, proof-of-work mining, and hash-chain validation. It is not production-ready and omits transactions, signatures, persistence, peer networking, and consensus-conflict handling.

from dataclasses import dataclass, field
import hashlib
import json
import time

GENESIS_PREVIOUS_HASH = "0" * 64


@dataclass
class Block:
    index: int
    timestamp: int
    data: str
    previous_hash: str
    nonce: int
    hash: str = ""

    def payload(self) -> bytes:
        values = [
            self.index,
            self.timestamp,
            self.data,
            self.previous_hash,
            self.nonce,
        ]
        return json.dumps(values, separators=(",", ":")).encode("utf-8")


def calculate_hash(block: Block) -> str:
    """Return the SHA-256 hash of a block's payload."""
    return hashlib.sha256(block.payload()).hexdigest()


@dataclass
class BlockchainNode:
    """Minimal educational proof-of-work blockchain node."""

    difficulty: int = 4
    chain: list[Block] = field(default_factory=list)

    def __post_init__(self) -> None:
        if not 1 <= self.difficulty <= 16:
            raise ValueError("difficulty must be between 1 and 16")
        if not self.chain:
            self.chain.append(self._mine("genesis", 0, GENESIS_PREVIOUS_HASH))

    def _mine(self, data: str, index: int, previous_hash: str) -> Block:
        target = 1 << (256 - self.difficulty)
        nonce = 0

        while True:
            block = Block(
                index=index,
                timestamp=int(time.time()),
                data=data,
                previous_hash=previous_hash,
                nonce=nonce,
            )
            block.hash = calculate_hash(block)

            if int(block.hash, 16) < target:
                return block

            nonce += 1

    def add_block(self, data: str) -> Block:
        """Mine and append a block referencing the current chain tip."""
        block = self._mine(data, len(self.chain), self.chain[-1].hash)
        self.chain.append(block)
        return block

    def validate(self) -> bool:
        """Return whether the local chain is internally valid."""
        return validate_chain(self.chain, self.difficulty)


def validate_chain(chain: list[Block], difficulty: int) -> bool:
    """Return whether hashes, links, indices, and proof of work are valid."""
    if not chain or not 1 <= difficulty <= 16:
        return False

    target = 1 << (256 - difficulty)

    for index, block in enumerate(chain):
        if block.index != index:
            return False
        if block.hash != calculate_hash(block):
            return False
        if int(block.hash, 16) >= target:
            return False

        if index == 0:
            if block.previous_hash != GENESIS_PREVIOUS_HASH:
                return False
        elif block.previous_hash != chain[index - 1].hash:
            return False

    return True


if __name__ == "__main__":
    node = BlockchainNode(difficulty=4)
    node.add_block("Alice pays Bob 1 BTC")
    print(node.validate())  # True

Common Pitfalls

  • Off-by-one errors: Genesis has index 0; each later block references its immediate predecessor.

  • Empty and one-element chains: An empty chain is invalid; one element is valid only when it is a valid genesis block.

  • Duplicates, negatives, and sorting: This toy chain treats data as an opaque string, so duplicates, negative text, and unsorted data are allowed. Real consensus defines transaction validity separately.

  • Peer graphs: Disconnected components and cycles are peer-topology issues, not chain issues; traverse each component with a visited set.

  • Mutating input and overflow: Validation should not modify blocks, and fixed-width implementations must handle nonces and 256-bit hashes safely.

  • Common follow-up: Interviewers often ask how tampering is detected, how full and light nodes differ, or how proof of work compares with proof of stake.

10

What is a blockchain fork and why does it occur?

A blockchain fork is a divergence in which competing blocks or branches descend from the same ancestor. It can result from miners finding blocks simultaneously or from incompatible protocol changes, and the network’s consensus rules determine which branch becomes canonical.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Structure and Mechanics

In a minimal educational blockchain, a block commonly contains:

  • index: its position in the chain

  • timestamp: when it was created

  • data: the block payload

  • previous_hash: the hash of its predecessor

  • nonce: the value varied during proof-of-work search

  • hash: the digest committing to the other fields

A minimal Python implementation would use SHA-256 from hashlib. Bitcoin block headers use double SHA-256, while Ethereum uses Keccak-256, so the exact hashing scheme is protocol-specific.

A temporary fork occurs when two distinct blocks have the same previous_hash, creating two valid successors of one parent. Each branch remains internally consistent: changing any historical field would change that block’s hash and every descendant hash. This hash chaining provides tamper evidence, although a fork means the network temporarily recognizes competing histories.

Transactions are usually committed through a Merkle tree. A Merkle proof can demonstrate that a transaction belongs to a particular block’s Merkle root, but it does not prove that the block belongs to the canonical branch.

Fork Types and Causes

Fork type Trigger Compatibility Typical outcome
Temporary fork Miners find competing blocks, often because of network latency Same protocol rules Usually resolves as one branch accumulates more work
Soft fork Consensus rules are tightened so new valid blocks remain valid under the old rules Backward-compatible Commonly converges without splitting upgraded and unupgraded networks permanently
Hard fork New rules reject blocks that older rules accept Incompatible Separate chains may coexist until participants coordinate an upgrade

Common causes include:

  1. Simultaneous block discovery: Two proof-of-work miners find valid blocks before either has propagated widely.

  2. Protocol upgrades: Changes to block rules, signatures, consensus logic, or transaction validity can create soft or hard forks.

  3. Consensus bugs or client divergence: For example, Bitcoin’s March 2013 Berkeley DB 5.3 lock-limit outage caused v0.8.0 nodes to fail while some users remained on v0.7.2, temporarily splitting the network.

  4. Malicious behavior: A participant controlling substantial hash power may create a private competing branch, although this does not guarantee a successful reorganization or double spend.

Resolution and Finality

  • Bitcoin: Nodes choose the branch with the greatest cumulative proof of work, not necessarily the greatest number of blocks. A reorganization replaces the local canonical branch with the better branch.

  • Proof-of-work finality: Bitcoin has no deterministic finality threshold. Six confirmations are a common risk heuristic, and the probability of reversal depends on the competing miner’s hash power and progress.

  • Ethereum finality: Since the 2022 proof-of-stake transition, Ethereum uses Gasper finality. A checkpoint can become justified after a supermajority attests to it; it becomes finalized when the finality conditions are satisfied. A conflicting checkpoint can be finalized only by slashing at least one-third of total ETH stake.

  • Transaction handling: Transactions from stale blocks are not necessarily valid or included again. Valid transactions normally return to the mempool and may be included in a later block.

Complexity

  • Detecting a divergence: Comparing two histories up to a common ancestor takes O(n) time in the worst case, where n is the number of compared blocks. It uses O(1) auxiliary space when both chains are already stored and traversed with iterators; materializing the histories requires O(n) additional space.

  • Merkle-proof verification: A proof for m transactions takes O(log m) time and O(log m) proof space, excluding the stored Merkle tree.

  • Proof-of-work search: For a bounded nonce space of N candidates and target-validity probability p, the best case is O(1), the expected case is O(Np), and the worst case is O(N); auxiliary space is O(1). A target requiring approximately b leading zero bits gives an expected O(2^b) hash attempts.

Interview Tips

  • Do not equate fork with corruption: Each branch can be a valid hash chain; disagreement concerns canonical-chain selection.

  • Distinguish soft and hard forks: Soft-fork rules remain compatible with old validation, while hard-fork rules deliberately reject blocks accepted by the old rules.

  • Do not call Merkle proofs a fork detector: They prove transaction inclusion; block headers and consensus work determine the canonical branch.

  • Common pitfall: Saying that the longest block list always wins. Bitcoin uses cumulative proof of work, and other protocols use their own consensus and finality rules.

11

How does cryptography protect blockchain transactions and blocks?

Cryptographic hashing detects unauthorized changes, while digital signatures authenticate transaction senders. Hash chaining links blocks so altering one historical block invalidates every block after it, and consensus makes rewriting the accepted history prohibitively expensive.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Security Roles

  • Transaction authorization: A sender signs the transaction with a private key. The network verifies the signature using the sender’s public key, proving authorization without revealing the private key. Bitcoin uses secp256k1 ECDSA for transaction signatures.

  • Integrity: SHA-256 maps transaction or block data to a fixed-length digest. Even a small change produces a different digest.

  • Hash chaining: Each block stores the previous block’s hash. Recalculating a modified block changes its hash, breaking the link to its successor.

  • Consensus: Proof of work makes finding a valid block costly; proof of stake requires locking economic collateral. Bitcoin uses proof of work, while Ethereum moved to proof of stake in 2022.

Hashing does not encrypt data and does not prove who created a transaction. Signatures provide authentication, while hashing provides integrity.

Merkle Trees and Proofs

A block containing many transactions can store a Merkle root instead of hashing every transaction on every validation.

  1. Each transaction is hashed into a leaf.

  2. Child hashes are paired and hashed to form internal nodes.

  3. The final root is committed in the block header.

  4. A light client receives a Merkle proof containing the sibling hashes along one leaf’s path.

  5. It recomputes the root and compares it with the accepted block’s root.

For t transactions, constructing the tree takes O(t) time and O(t) space. A proof contains O(log t) sibling hashes and takes O(log t) time and space to verify. This allows a client to prove that one transaction is included without downloading the entire block.

Proof of Work as a Search Problem

Proof of work repeatedly changes a nonce and searches for a block hash below a target threshold:

  • Search space: Approximately 2^d candidates for d required leading zero bits.

  • Expected attempts: 2^d.

  • Difficulty adjustment: The target changes over time to control block production rate.

  • Security effect: An attacker must repeat the search to alter history, although consensus also protects the canonical chain.

A small conceptual example:

  1. Alice signs a transaction transferring tokens to Bob.

  2. The transaction becomes a Merkle leaf, and its hash contributes to the Merkle root.

  3. The block header includes the Merkle root, previous block hash, timestamp, and nonce.

  4. Miners vary the nonce until the block hash satisfies the target.

  5. Peers verify the proof, Merkle root, signature, and previous-block link.

Complexity

Operation Time Space Notes
Hash a b-byte block O(b) O(b) temporary Canonical serialization creates temporary bytes
Validate n blocks O(B) O(M) auxiliary B is total serialized bytes; M is the largest block. Input chain is excluded; no recursion stack
Find proof of work O(b · 2^d) expected O(b) Best case is one attempt; there is no finite deterministic worst-case bound
Verify fixed-size signature O(1) relative to chain length O(1) Cost depends mainly on key and signature sizes

Code Example

This educational implementation demonstrates block hashing, hash chaining, proof-of-work search, and validate_chain. It uses one SHA-256 digest and omits transaction signatures, Merkle proofs, distributed consensus, and production validation.

from dataclasses import dataclass
from datetime import datetime, timezone
import hashlib
import json

ZERO_HASH = "0" * 64


@dataclass(frozen=True)
class Block:
    index: int
    timestamp: str
    data: str
    previous_hash: str
    nonce: int
    hash: str


def calculate_hash(block: Block) -> str:
    """Calculate a block's SHA-256 hash without hashing its hash field."""
    payload = {
        "index": block.index,
        "timestamp": block.timestamp,
        "data": block.data,
        "previous_hash": block.previous_hash,
        "nonce": block.nonce,
    }
    encoded = json.dumps(
        payload, sort_keys=True, separators=(",", ":")
    ).encode("utf-8")
    return hashlib.sha256(encoded).hexdigest()


def proof_target(difficulty: int) -> int:
    """Return the target requiring approximately difficulty leading zero bits."""
    if not 0 <= difficulty <= 256:
        raise ValueError("difficulty must be between 0 and 256")
    return 1 << (256 - difficulty)


def has_valid_proof(block: Block, difficulty: int) -> bool:
    """Check whether the block hash satisfies the proof-of-work target."""
    return int(block.hash, 16) < proof_target(difficulty)


def _mine_candidate(
    index: int, data: str, previous_hash: str, difficulty: int
) -> Block:
    """Search nonces until the candidate hash meets the target."""
    target = proof_target(difficulty)
    timestamp = datetime.now(timezone.utc).isoformat()
    nonce = 0

    while True:
        candidate = Block(
            index=index,
            timestamp=timestamp,
            data=data,
            previous_hash=previous_hash,
            nonce=nonce,
            hash="",
        )
        candidate_hash = calculate_hash(candidate)

        if int(candidate_hash, 16) < target:
            return Block(
                index=index,
                timestamp=timestamp,
                data=data,
                previous_hash=previous_hash,
                nonce=nonce,
                hash=candidate_hash,
            )

        nonce += 1


def create_genesis(data: str, difficulty: int = 1) -> Block:
    """Create and mine the first block."""
    return _mine_candidate(0, data, ZERO_HASH, difficulty)


def mine_block(previous_block: Block, data: str, difficulty: int = 1) -> Block:
    """Create and mine a block linked to the previous block."""
    return _mine_candidate(
        previous_block.index + 1,
        data,
        previous_block.hash,
        difficulty,
    )


def validate_chain(chain: list[Block], difficulty: int = 1) -> bool:
    """Validate block hashes, links, indexes, and proof-of-work."""
    if not chain:
        return True

    expected_previous_hash = ZERO_HASH

    for expected_index, block in enumerate(chain):
        if block.index != expected_index:
            return False
        if block.previous_hash != expected_previous_hash:
            return False
        if block.hash != calculate_hash(block):
            return False
        if not has_valid_proof(block, difficulty):
            return False

        expected_previous_hash = block.hash

    return True


genesis = create_genesis("genesis transaction")
second_block = mine_block(genesis, "Alice -> Bob: 1 token")
example_chain = [genesis, second_block]

print(validate_chain(example_chain, difficulty=1))  # True

Common Pitfalls

  • Hashing is not authentication: A valid hash does not prove who created a transaction.

  • Tamper evidence is not absolute immutability: Consensus and economic incentives determine which rewritten chain the network accepts.

  • Missing validation layers: A production blockchain must verify signatures, transaction rules, Merkle proofs, consensus rules, and peer-to-peer message handling.

  • Edge cases: The demonstration accepts an empty chain and a valid one-block chain; duplicate blocks fail index and hash-link checks. Negative transaction amounts require domain validation. Sorting, disconnected graphs, and cycles are not applicable to a linear blockchain.

12

Why are hash functions crucial in blockchain technology?

A cryptographic hash function converts arbitrary data into a fixed-size fingerprint. In blockchain, hashes enable tamper detection, compact commitments, transaction identification, and, in proof-of-work systems, a costly search puzzle.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Hash Functions in Blockchain

A useful cryptographic hash function has these properties:

  • Deterministic: identical input produces an identical digest.

  • Fixed-size output: SHA-256 produces a 32-byte digest, commonly displayed as 64 hexadecimal characters.

  • Avalanche effect: a small input change produces an unrelated output.

  • Preimage resistance: finding an input for a specified digest is computationally infeasible.

  • Collision resistance: finding two different inputs with the same digest is computationally infeasible.

Python 3.12’s standard-library hashlib provides SHA-256. A logical blockchain block commonly contains an index, timestamp, data, previous_hash, nonce, and hash. Its hash acts as a hash pointer to the preceding block. Bitcoin instead hashes a fixed 80-byte block header containing fields such as the previous-block hash, Merkle root, timestamp, difficulty target, and nonce.

Hash chaining provides tamper evidence. Changing an earlier block changes its hash, so each following block’s stored previous_hash no longer matches. Hashing alone does not guarantee immutability: an attacker can recompute a separate chain, so distributed consensus and chain finality are also required.

Merkle Trees and Proofs

A Merkle tree commits to a collection of transactions:

  1. Hash each transaction to obtain a leaf hash.

  2. Hash pairs of child hashes to obtain parent hashes.

  3. Repeat until a single Merkle root remains.

For two transactions, leaf hashes hA and hB produce a root H(hA || hB). A proof for transaction A contains only hB; the verifier recomputes the root and compares it with the trusted block-header value. A balanced Merkle proof therefore requires O(log n) hash operations for n transactions.

Bitcoin uses a binary Merkle tree with double SHA-256, while Ethereum uses Merkle-Patricia tries and Keccak-256 for its state and transaction structures. Edge cases are protocol-specific: an empty transaction set needs a defined empty root, a single transaction can be its own root with an empty proof, odd leaf counts require a defined promotion or duplication rule, and duplicate transactions still occupy distinct positions.

Proof of Work and Hash Chaining

In proof of work, a miner repeatedly varies values such as the nonce until the header hash satisfies a target. This is a probabilistic search problem:

  • If an attempt succeeds with probability p, the expected attempts are 1/p.

  • If the target effectively requires d leading zero bits, expected attempts are approximately 2^d.

  • The best case is one attempt.

  • There is no finite guaranteed worst-case attempt count.

Bitcoin uses proof of work. Ethereum transitioned to proof of stake in 2022, although Keccak-256 remains important in Ethereum’s data structures.

Complexity

Operation Best Average/Expected Worst Space Reason
SHA-256 over m bytes O(m) O(m) O(m) O(1) auxiliary, excluding input and digest Every input byte is processed
Build a Merkle tree from n fixed-size leaf hashes O(n) O(n) O(n) O(n) auxiliary for tree nodes, excluding leaf input There are O(n) hash computations
Verify a Merkle proof O(log n) O(log n) O(log n) O(1) auxiliary, excluding supplied proof, leaf, and root One sibling is processed per level
Proof-of-work search O(1) O(2^d) No finite Big-O bound O(1) auxiliary Success is probabilistic
Validate n fixed-size blocks O(n) O(n) O(n) O(1) auxiliary, excluding the chain input Each block and link is checked once

These iterative or streaming formulations add no recursive stack space. If block payloads vary and have maximum size m, chain validation takes O(nm) time.

Common Pitfalls

  • SHA-256 is not Keccak-256, and Bitcoin’s SHA-256d is not plain single SHA-256.

  • Hashing is not encryption: a hash does not normally reveal or permit decoding of its input.

  • A valid hash chain is not consensus: attackers can recompute hashes, so network rules and finality still matter.

  • Proof-of-work targets require exact encoding: Bitcoin interprets a binary target, unlike simplified hexadecimal-prefix examples.

  • Empty chains and genesis blocks are protocol-specific and should not automatically be considered valid.

  • Common follow-ups concern Merkle-proof verification, hash-pointer tampering, nonce search, and proof of work versus proof of stake.

13

How is asymmetric encryption used in blockchains?

Asymmetric cryptography is used in blockchains primarily for digital signatures: a private key signs transaction or consensus data, and a corresponding public key lets others verify authorization and integrity. Public-key encryption can protect off-chain data or messages, but ordinary public-ledger transactions are signed rather than encrypted.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Digital signature: The private key signs data; the corresponding public key verifies it. This provides authenticity and integrity but does not conceal the signed data.

  • Public-key encryption: A sender encrypts data with the recipient’s public key, and only the recipient’s private key can decrypt it. Blockchains generally avoid encrypting ordinary transactions because nodes must validate and process their contents.

  • Key management: Private keys must remain secret. Their loss can make assets inaccessible, while disclosure permits unauthorized signing.

  • Real systems: Bitcoin uses ECDSA for legacy and base-segwit transactions and Schnorr signatures for Taproot. Standard Ethereum externally owned-account transactions use secp256k1 ECDSA.

Blockchain Role

A didactic blockchain—not the exact format used by Bitcoin or Ethereum—may store these fields per block:

  • index, timestamp, data, previous_hash, nonce, and hash

  • A signature and verification public_key associated with the producer

The transaction flow is:

  1. Compute the SHA-256 digest of the block’s unsigned fields.

  2. Sign the digest with the producer’s private key.

  3. Recompute the digest, verify the signature and proof of work, and check previous_hash.

  4. Accept the block only if all validation and consensus rules pass.

Hash chaining makes history tamper-evident: modifying block 4 changes its hash and invalidates block 5’s stored pointer. Rewriting later blocks remains possible, but requires modifying the chain and defeating the network’s consensus rules.

  • Merkle root: A balanced Merkle tree summarizes transaction hashes; its root can be placed in a block header.

  • Merkle proof: A balanced tree provides O(log n) sibling hashes that let a light client verify transaction inclusion.

  • Proof of work: A miner varies the nonce until the block hash meets the target. If the target requires b leading zero bits, each attempt succeeds with probability 2^-b, giving 2^b expected attempts. Bitcoin uses proof of work; Ethereum moved to proof of stake in 2022.

Complexity

Operation Best Average Worst Space and reason
SHA-256 of k bytes O(k) O(k) O(k) O(1) when streamed; the example’s JSON serialization uses O(k) temporary space
Validate n fixed-size blocks O(n) O(n) O(n) O(1) auxiliary because blocks are processed sequentially; input chain excluded
Build an n-leaf Merkle tree O(n) O(n) O(n) O(n) because the tree and leaves are retained
Verify a Merkle proof O(log n) O(log n) O(log n) O(log n) including one sibling hash per tree level
Find a b-bit proof-of-work nonce O(1) O(2^b) expected Unbounded O(1) auxiliary; chain excluded
Sign or verify a fixed-size digest O(1) O(1) O(1) O(1) for fixed-size keys, signatures, and digest

No recursion is used, so there is no recursion-stack cost.

Code Example

This educational example uses Python 3.12 and cryptography==45.0.7. It demonstrates hash chaining, proof-of-work search, Ed25519 signatures, and chain validation; it is not production-ready.

from dataclasses import dataclass
import hashlib
import json
import time

from cryptography.exceptions import InvalidSignature
from cryptography.hazmat.primitives.asymmetric.ed25519 import (
    Ed25519PrivateKey,
    Ed25519PublicKey,
)
from cryptography.hazmat.primitives.serialization import Encoding, PublicFormat


@dataclass(frozen=True)
class Block:
    index: int
    timestamp: float
    data: str
    previous_hash: str
    nonce: int
    hash: str
    signature: bytes
    public_key: bytes


def target_for(difficulty: int) -> str:
    """Return a target with the requested leading hexadecimal zero digits."""
    if isinstance(difficulty, bool) or not isinstance(difficulty, int):
        raise ValueError("difficulty must be an integer")
    if not 1 <= difficulty <= 4:
        raise ValueError("difficulty must be between 1 and 4")
    return "0" * difficulty


def calculate_hash(
    index: int,
    timestamp: float,
    data: str,
    previous_hash: str,
    nonce: int,
) -> str:
    """Calculate the SHA-256 digest of a block's unsigned fields."""
    payload = {
        "index": index,
        "timestamp": timestamp,
        "data": data,
        "previous_hash": previous_hash,
        "nonce": nonce,
    }
    encoded = json.dumps(
        payload, sort_keys=True, separators=(",", ":")
    ).encode("utf-8")
    return hashlib.sha256(encoded).hexdigest()


def mine_block(
    index: int,
    data: str,
    previous_hash: str,
    private_key: Ed25519PrivateKey,
    difficulty: int = 2,
) -> Block:
    """Create and sign a block after finding a proof-of-work nonce."""
    if index < 0:
        raise ValueError("index cannot be negative")

    target = target_for(difficulty)
    timestamp = time.time()
    nonce = 0

    while True:
        digest = calculate_hash(
            index, timestamp, data, previous_hash, nonce
        )
        if digest.startswith(target):
            signature = private_key.sign(bytes.fromhex(digest))
            public_key = private_key.public_key().public_bytes(
                Encoding.Raw, PublicFormat.Raw
            )
            return Block(
                index,
                timestamp,
                data,
                previous_hash,
                nonce,
                digest,
                signature,
                public_key,
            )
        nonce += 1


def validate_chain(chain: list[Block], difficulty: int = 2) -> bool:
    """Validate hashes, signatures, proof of work, and block links."""
    if not chain:
        return False

    try:
        target = target_for(difficulty)
    except ValueError:
        return False

    previous_hash = "0" * 64

    for expected_index, block in enumerate(chain):
        digest = calculate_hash(
            block.index,
            block.timestamp,
            block.data,
            block.previous_hash,
            block.nonce,
        )
        if block.index != expected_index:
            return False
        if block.previous_hash != previous_hash:
            return False
        if block.hash != digest or not digest.startswith(target):
            return False

        try:
            public_key = Ed25519PublicKey.from_public_bytes(block.public_key)
            public_key.verify(block.signature, bytes.fromhex(digest))
        except (InvalidSignature, ValueError):
            return False

        previous_hash = block.hash

    return True


if __name__ == "__main__":
    private_key = Ed25519PrivateKey.generate()
    genesis = mine_block(0, "Genesis transaction", "0" * 64, private_key)
    chain = [genesis]
    print(validate_chain(chain))  # Expected output: True

Common Pitfalls

  • Signature versus encryption: Signatures authenticate data; they do not hide it.

  • Hash versus signature: SHA-256 provides hashing; a signature proves possession of the signing key.

  • Incomplete validation: Recompute the hash and verify the signature, proof of work, indexes, and previous-hash links.

  • Edge cases: The example rejects an empty chain, negative indexes, duplicate or out-of-order indexes, and invalid difficulty. It supports a one-block chain and permits duplicate transaction data.

  • Production limitations: Consensus rules, transaction validation, persistent storage, secure key management, and reviewed cryptographic protocols are still required.

14

How do digital signatures authenticate blockchain transactions?

Digital signatures authenticate blockchain transactions by proving that the holder of a private key authorized the exact transaction bytes. A node verifies the signature using a public key associated with the sender’s account and detects any modification after signing.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Digital Signatures Work

A signature scheme requires an unambiguous serialization of the transaction. The sender signs those bytes, while verifiers reconstruct exactly the same bytes and check the signature against the sender’s public key:

  1. Serialize the transaction canonically.

  2. Sign the bytes with the private key.

  3. Broadcast the transaction and signature.

  4. Verify the signature with the public key.

  5. Reject the transaction if verification fails.

The public key must be associated with the authorized account. A valid signature provides:

  • Authenticity: the associated private key produced the signature.

  • Integrity: the signed transaction bytes were not modified.

  • Non-repudiation support: the signer cannot credibly deny signing without exposing key control.

It does not prove that the transaction is truthful, confidential, accepted by consensus, or final.

Bitcoin uses ECDSA over secp256k1 for legacy transactions and Schnorr signatures for Taproot transactions.

A concrete trace is:

  1. Alice signs {"to": "bob", "amount": "10"}.

  2. Nodes reconstruct the same canonical bytes and verify the signature with Alice’s public key.

  3. Verification succeeds and the transaction is eligible for consensus.

  4. Changing the amount to 11 produces different bytes, causing verification to fail.

Blockchain Integrity and Merkle Proofs

A minimal proof-of-work block contains an index, timestamp, transaction data or Merkle root, previous-block hash, nonce, and block hash:

  • Previous hash forms the backward-pointing hash chain.

  • Merkle root commits to the block’s transaction hashes.

  • Nonce varies while searching for a proof-of-work solution.

  • Block hash commits to the header and search input.

In a Merkle tree, transaction hashes are paired and hashed repeatedly until one root remains, duplicating an odd leftover when necessary. A Merkle proof supplies the sibling hashes and their positions, allowing a lightweight client to prove that a transaction belongs to a block without downloading the entire block.

Changing a historical transaction changes its Merkle root and block hash. Descendant headers must then change, requiring new proof-of-work and consensus agreement; hash chaining alone does not guarantee immutability.

Bitcoin’s actual block hash is double SHA-256 over its 80-byte header. The educational code below instead uses one SHA-256 over canonical JSON and is not production-ready or a Bitcoin implementation.

Complexity

Space excludes pre-existing input unless stated; candidate bytes, tree storage, and proof output are counted. There is no recursion stack.

Operation Time Space Reason
Sign or verify one bounded-size transaction O(1) best/average/worst O(1) auxiliary Ed25519 keys and signatures are fixed-size; messages can be any length, so this treats the transaction size as bounded
Validate n blocks with bounded transactions O(n) best/average/worst O(1) auxiliary Each block is checked once; chain input excluded
Build a Merkle tree for t transactions O(t) best/average/worst O(t) Each hash level is processed; tree counted
Produce a Merkle proof O(log t) best/average/worst O(log t) One sibling is included per tree level
Search for d leading hexadecimal zeroes Best O(k), average O(k · 16^d), no finite guaranteed worst case O(k) Each attempt processes a k-byte candidate; candidate counted

Code Example

This minimal educational blockchain uses hashlib and dataclasses. Transaction signing requires cryptography 42 or later.

import hashlib
import json
import time
from dataclasses import dataclass

from cryptography.exceptions import InvalidSignature
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric.ed25519 import (
    Ed25519PrivateKey,
    Ed25519PublicKey,
)


def canonical_bytes(value: object) -> bytes:
    """Serialize a JSON-compatible value deterministically."""
    return json.dumps(
        value, sort_keys=True, separators=(",", ":"), ensure_ascii=False
    ).encode("utf-8")


@dataclass(frozen=True)
class Transaction:
    sender_public_key: bytes
    signature: bytes
    payload: dict[str, str]

    def signing_bytes(self) -> bytes:
        """Return the exact bytes covered by the signature."""
        return canonical_bytes(
            {
                "sender": self.sender_public_key.hex(),
                "payload": self.payload,
            }
        )


@dataclass(frozen=True)
class Block:
    index: int
    timestamp: float
    data: tuple[Transaction, ...]
    previous_hash: str
    nonce: int
    hash: str


def sign_transaction(
    private_key: Ed25519PrivateKey,
    payload: dict[str, str],
) -> Transaction:
    """Sign a transaction payload with Ed25519."""
    public_key = private_key.public_key().public_bytes(
        serialization.Encoding.Raw,
        serialization.PublicFormat.Raw,
    )
    signature = private_key.sign(
        canonical_bytes({"sender": public_key.hex(), "payload": payload})
    )
    return Transaction(public_key, signature, dict(payload))


def calculate_block_hash(
    index: int,
    timestamp: float,
    data: tuple[Transaction, ...],
    previous_hash: str,
    nonce: int,
) -> str:
    """Calculate an educational block's SHA-256 hash."""
    header = {
        "index": index,
        "timestamp": timestamp,
        "data": [
            {
                "sender": transaction.sender_public_key.hex(),
                "signature": transaction.signature.hex(),
                "payload": transaction.payload,
            }
            for transaction in data
        ],
        "previous_hash": previous_hash,
        "nonce": nonce,
    }
    return hashlib.sha256(canonical_bytes(header)).hexdigest()


def mine_block(
    index: int,
    data: tuple[Transaction, ...],
    previous_hash: str,
    difficulty: int = 3,
) -> Block:
    """Find a nonce whose block hash has the required zero prefix."""
    if difficulty <= 0:
        raise ValueError("difficulty must be positive")

    target_prefix = "0" * difficulty
    nonce = 0
    while True:
        timestamp = time.time()
        block_hash = calculate_block_hash(
            index, timestamp, data, previous_hash, nonce
        )
        if block_hash.startswith(target_prefix):
            return Block(
                index, timestamp, data, previous_hash, nonce, block_hash
            )
        nonce += 1


def validate_chain(
    chain: list[Block],
    genesis_hash: str,
    difficulty: int = 3,
) -> bool:
    """Validate hashes, proof of work, links, and transaction signatures."""
    if difficulty <= 0:
        return False

    previous_hash = genesis_hash
    target_prefix = "0" * difficulty

    for expected_index, block in enumerate(chain):
        if block.index != expected_index:
            return False
        if block.previous_hash != previous_hash:
            return False
        if not block.hash.startswith(target_prefix):
            return False

        calculated_hash = calculate_block_hash(
            block.index,
            block.timestamp,
            block.data,
            block.previous_hash,
            block.nonce,
        )
        if calculated_hash != block.hash:
            return False

        for transaction in block.data:
            try:
                public_key = Ed25519PublicKey.from_public_bytes(
                    transaction.sender_public_key
                )
                public_key.verify(
                    transaction.signature,
                    transaction.signing_bytes(),
                )
            except (InvalidSignature, ValueError):
                return False

        previous_hash = block.hash

    return True


if __name__ == "__main__":
    private_key = Ed25519PrivateKey.generate()
    transaction = sign_transaction(private_key, {"to": "bob", "amount": "10"})
    genesis_hash = "0" * 64
    chain = [mine_block(0, (transaction,), genesis_hash)]

    print(validate_chain(chain, genesis_hash))  # Expected output: True

Common Pitfalls

  • Treating a hash as a signature: SHA-256 alone does not prove authorization.

  • Changing signed bytes: verifiers must reconstruct the same canonical serialization.

  • Trusting an arbitrary key: production systems bind keys or addresses to authorized accounts.

  • Confusing validity with finality: signature validity, consensus acceptance, and finality are separate.

  • Ignoring consensus differences: Bitcoin uses proof of work, while Ethereum has used proof of stake since 2022.

  • Edge cases: malformed keys or signatures fail validation; an empty chain is structurally valid; one-block chains work; duplicate or negative-value transactions are not rejected because this example performs no semantic transaction validation.

15

How do public and private keys secure blockchain transactions?

A public-private key pair gives blockchain users cryptographic control over their assets. The private key signs transactions, while the corresponding public key lets anyone verify those signatures without revealing the private key.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Public and Private Keys

  • Private key: A secret number used to create signatures. Anyone who obtains it can authorize transactions from the associated account. Real wallets normally derive it and other keys from a seed phrase.

  • Public key: Derived mathematically from the private key using an asymmetric algorithm such as secp256k1 ECDSA. It can be shared publicly and cannot feasibly be used to recover the private key.

  • Address: A shortened, encoded representation of a public key or related account data. For example, Bitcoin encodes the public key into an address, while Ethereum derives an address from the public key using Keccak-256.

  • Signature: Produced from the private key and the transaction or message being signed. Nodes use the public key to verify that the signature is valid and the transaction was authorized.

For example, when Alice sends Bitcoin, her wallet signs the transaction with Alice’s private key. A node verifies the signature using the public key referenced by the transaction, then checks consensus rules such as proof of work.

Keys Versus Block Hashes

Keys authorize transactions; they are not the same mechanism as block hashes.

A typical block contains an index, timestamp, data or transactions, previous hash, nonce, and hash. Each block’s hash commits to its contents and the previous block’s hash, creating a tamper-evident chain.

The block hash does not prove ownership and is not normally created with a wallet’s private key. Transaction signatures perform that role. A transaction can therefore be correctly signed while still being rejected if it violates balance, formatting, smart-contract, or consensus rules.

Hashing, Merkle Trees, and Consensus

  • Cryptographic hashing: SHA-256, available through Python’s hashlib, converts arbitrary data into a fixed 256-bit digest. Changing any input byte normally produces a completely different digest.

  • Merkle tree: Transaction hashes are arranged into a binary tree, and the block commits to the root hash. A Merkle proof can prove that a transaction is included without downloading every transaction.

  • Hash chaining: Each block points backward through previous_hash. Altering an earlier block changes its hash and every later link, making unauthorized changes detectable.

  • Proof of work: A miner searches for a nonce whose resulting block hash satisfies a difficulty target. This is a computational search problem, not encryption or a private-key operation.

Bitcoin uses proof of work. Ethereum transitioned from proof of work to proof of stake in 2022, although transactions on both networks use secp256k1-based signatures.

Complexity

Operation Best time Average time Worst time Space Reason
Fixed-size key generation, signing, or verification O(1) O(1) O(1) O(1) secp256k1 uses fixed-size keys and digests
SHA-256 over m bytes O(m) O(m) O(m) O(m) for encoded input Processes each byte once
Validate a chain of n blocks O(n) O(n) O(n) O(1) auxiliary, excluding stored blocks Single pass through blocks
Build a Merkle tree over n transactions O(n) O(n) O(n) O(n) when storing all levels Each transaction hashed once, combined pairwise
Verify a Merkle proof O(log n) O(log n) O(log n) O(log n) Path length from leaf to root
Toy proof-of-work with d leading hexadecimal zeros O(1) O(16^d) expected hashes Unbounded O(1) for fixed-size blocks Probabilistic search; no guaranteed finite worst case

Key operations are constant relative to blockchain length because secp256k1 uses fixed-size keys and digests. The proof-of-work estimate is probabilistic: there is no guaranteed finite worst-case number of attempts.

Code Example

This educational blockchain uses hashlib and dataclasses. It demonstrates hash chaining and validation, but deliberately does not implement wallet keys or digital signatures; Python’s standard library does not provide an audited secp256k1 implementation.

from dataclasses import dataclass, replace
import hashlib
import json
import time


@dataclass(frozen=True)
class Block:
    """Immutable block in a simple blockchain."""
    index: int
    timestamp: int
    data: str
    previous_hash: str
    nonce: int
    hash: str


def compute_hash(block: Block) -> str:
    """Return the SHA-256 hash of the block's contents (excluding its own hash field)."""
    payload = {
        "index": block.index,
        "timestamp": block.timestamp,
        "data": block.data,
        "previous_hash": block.previous_hash,
        "nonce": block.nonce,
    }
    encoded = json.dumps(payload, sort_keys=True).encode("utf-8")
    return hashlib.sha256(encoded).hexdigest()


class Blockchain:
    """A minimal proof-of-work blockchain with fixed difficulty."""

    def __init__(self, difficulty: int = 4) -> None:
        """
        Initialize the chain with a genesis block.

        Args:
            difficulty: Number of leading zero hex digits required in the block hash.
        """
        if difficulty < 1:
            raise ValueError("difficulty must be positive")

        self.difficulty = difficulty
        self.blocks: list[Block] = []
        # The genesis block is mined too, so it meets the difficulty target.
        self.mine_block("Genesis")

    def mine_block(self, data: str) -> Block:
        """
        Find a nonce that makes the block's hash satisfy the difficulty target.

        Args:
            data: Arbitrary string data to include in the block.

        Returns:
            The newly mined block appended to the chain.
        """
        previous_hash = self.blocks[-1].hash if self.blocks else "0" * 64
        candidate = Block(
            len(self.blocks),
            int(time.time()),
            data,
            previous_hash,
            0,
            "",
        )
        target = "0" * self.difficulty

        while True:
            candidate_hash = compute_hash(candidate)
            if candidate_hash.startswith(target):
                break
            candidate = replace(candidate, nonce=candidate.nonce + 1)

        candidate = replace(candidate, hash=candidate_hash)
        self.blocks.append(candidate)
        return candidate

    def validate_chain(self) -> bool:
        """
        Verify the integrity of the entire chain.

        Returns:
            True if every block links correctly, has a valid hash, and meets the difficulty target.
            Note: This assumes a fixed difficulty for all blocks (toy model).
        """
        if not self.blocks:
            return True

        target = "0" * self.difficulty
        for index, block in enumerate(self.blocks):
            expected_previous = (
                "0" * 64 if index == 0 else self.blocks[index - 1].hash
            )
            if block.index != index:
                return False
            if block.previous_hash != expected_previous:
                return False
            if block.hash != compute_hash(block):
                return False
            if not block.hash.startswith(target):
                return False

        return True


if __name__ == "__main__":
    chain = Blockchain()
    chain.mine_block("Alice pays Bob 1 BTC")
    print(chain.validate_chain())  # Expected output: True

Common Pitfalls

  • Hashing a private key with SHA-256 does not create a secure asymmetric key pair; use an audited secp256k1 library.

  • A public key, address, and public-key hash are related but distinct values.

  • Signing provides authenticity, not confidentiality; transaction contents are generally public.

  • Hash chaining detects modification but does not replace transaction authorization or consensus.

  • The example accepts an empty chain, validates a one-block genesis chain, permits duplicate transaction text, and accepts negative numeric text because data is a string. Sorting, disconnected graphs, and cycles do not apply to this linear structure.

  • Expect follow-up questions about signature verification, Merkle proofs, nonce reuse, and why changing a historical block invalidates all subsequent block hashes.

16

How do smart contracts operate within a blockchain?

A smart contract is deterministic code deployed at an address on a blockchain and invoked by transactions. Nodes execute it in a deterministic environment, while consensus selects the canonical history containing its resulting state changes.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Smart Contracts Execute

  1. A developer submits a deployment transaction containing executable contract code and initialization data.

  2. A transaction calls the contract with arguments, transferred value, and usually a gas limit.

  3. A node processing a candidate block executes its transactions in block order against the pre-transaction state.

  4. Execution can transfer value, update contract storage, emit logs, or make internal calls to other contracts. An internal call is not an independently signed transaction.

  5. Consensus selects the canonical chain, whose transaction order is authoritative; protocol-specific finality rules determine when that history becomes final.

Contracts therefore behave as replicated state machines. Their code is normally immutable unless an upgrade mechanism is provided, while their storage changes over time. Determinism is essential: nondeterministic iteration order, randomness, timestamps, or uncontrolled external calls can make nodes calculate different results.

Bitcoin uses proof of work and restricted scripting rather than general-purpose contract execution. Ethereum moved to proof of stake in 2022; its smart contracts execute through the Ethereum Virtual Machine.

Blockchain Data Structure and PoW

A blockchain resembles a hash-linked linked list:

  • Block structure: index, timestamp, data, previous_hash, nonce, and hash.

  • Hash pointer: Each block stores the preceding block’s hash.

  • Cryptographic hashing: The example uses SHA-256 through hashlib.

  • Immutability detection: Changing a block changes its hash and breaks the link to subsequent blocks.

  • Proof of work: A miner searches for a nonce whose hash satisfies the network’s difficulty target.

Hash chaining detects inconsistency but does not physically prevent rewriting. Replacements also require recomputing subsequent hashes and proof of work, making them impractical on a large proof-of-work network.

The example uses a hexadecimal prefix of d zero characters. A uniform hash succeeds with probability 16^-d, so the expected search cost is O(b · 16^d) hash trials, where b is the serialized block size. The probabilistic worst case has no finite practical bound. Bitcoin instead uses a 256-bit target threshold and double SHA-256.

Merkle Trees and Proofs

A standard Merkle tree commits to a set of transactions:

  • Transaction hashes are leaves; interior nodes hash their children.

  • The Merkle root summarizes the set and can be committed in a block header.

  • A Merkle proof provides the sibling hashes on one leaf’s path.

  • Verification takes O(log n) hashes for n leaves instead of checking every transaction.

Bitcoin uses a Merkle tree for block transactions. Ethereum uses Merkle Patricia Tries for transaction, receipt, and world-state data. These structures prove membership under a trusted root; they do not independently prove that the underlying data is valid.

Complexity

Space includes temporary allocations and the recursion stack. The blockchain implementation is iterative, and the input chain is excluded from auxiliary-space figures.

Operation Best, Average, Worst Time Auxiliary Space Reason
Compute block hash O(b) O(b) Serializes and hashes b bytes
Validate chain O(B) O(M) Processes B chain bytes; largest block is M bytes
Build full Merkle tree O(n) O(n) Hashes leaves and interior nodes
Verify Merkle proof O(log n) O(log n) Processes one hash path
Search proof of work Best O(b); average O(b · 16^d); worst unbounded O(b) Repeatedly hashes candidates
Execute contract O(c) O(k) c is execution work; k is memory and state data touched

Code Example

This educational blockchain uses a zero-hash genesis convention. It is not production-ready and does not implement contract execution, signatures, distributed consensus, or production security.

"""Minimal educational SHA-256 hash-linked blockchain."""

from dataclasses import dataclass, field
from hashlib import sha256
import json


@dataclass
class Block:
    index: int
    timestamp: float
    data: list[str]
    previous_hash: str
    nonce: int = 0
    hash: str = ""
    extra_data: dict[str, str] = field(default_factory=dict)

    def calculate_hash(self) -> str:
        """Calculate this block's SHA-256 hash, excluding the stored hash."""
        payload = {
            "index": self.index,
            "timestamp": self.timestamp,
            "data": self.data,
            "previous_hash": self.previous_hash,
            "nonce": self.nonce,
            "extra_data": self.extra_data,
        }
        encoded = json.dumps(
            payload,
            sort_keys=True,
            separators=(",", ":"),
        ).encode("utf-8")
        return sha256(encoded).hexdigest()


def mine_block(block: Block, difficulty: int = 2) -> Block:
    """Search for a nonce satisfying the simplified hexadecimal prefix."""
    if difficulty < 0:
        raise ValueError("difficulty must be non-negative")

    target = "0" * difficulty
    while True:
        block.hash = block.calculate_hash()
        if block.hash.startswith(target):
            return block
        block.nonce += 1


def validate_chain(chain: list[Block], difficulty: int = 2) -> bool:
    """Validate a zero-hash-genesis chain, its links, indices, and PoW."""
    if difficulty < 0:
        raise ValueError("difficulty must be non-negative")
    if not chain:
        return True

    expected_previous_hash = "0" * 64
    for expected_index, block in enumerate(chain):
        if block.index != expected_index:
            return False
        if block.previous_hash != expected_previous_hash:
            return False
        if block.hash != block.calculate_hash():
            return False
        if not block.hash.startswith("0" * difficulty):
            return False
        expected_previous_hash = block.hash

    return True


genesis = mine_block(
    Block(0, 0.0, ["genesis"], "0" * 64),
    difficulty=2,
)
block_one = mine_block(
    Block(1, 1.0, ["contract call: transfer 1"], genesis.hash),
    difficulty=2,
)
chain = [genesis, block_one]

print(validate_chain(chain))  # Expected output: True

Common Pitfalls

  • Consensus versus hashing: Hash chaining detects inconsistency; consensus and finality determine which history is authoritative.

  • Nondeterminism: Do not rely on unordered iteration, randomness, ambient time, or uncontrolled external responses.

  • Mutation and overflow: mine_block mutates its input, and fixed-width implementations must check nonce and index overflow.

  • Validation gaps: Include replay protection, gas limits, access control, and careful handling of external calls and reentrancy.

  • Proof scope: Merkle proofs establish membership under a trusted root, not transaction validity.

  • Common follow-ups ask about contract storage, finality, proof verification, and why modifying one block requires recomputing later links.

17

Which smart contract platforms exist, and how do they differ?

Smart contract deployment platforms differ mainly in their execution model, programming language, fee mechanism, finality, and network permissioning. Popular choices include Ethereum and its rollups, Solana, Cardano, Cosmos SDK chains, Substrate-based chains, and enterprise systems such as Hyperledger Fabric.

Read full answer

Applies tolanguage-independent

Deployment Options

Platform Languages and runtime Execution and fee model Main characteristics
Ethereum and rollups Solidity, Vyper, EVM Account-based execution; gas fees Mature tooling and broad ecosystem. Ethereum uses proof of stake since 2022; rollups such as Base, Optimism, and Arbitrum execute separately and settle to Ethereum.
Solana Rust or C, Solana Virtual Machine Account-based; compute and prioritization fees Programs can execute in parallel when transactions do not conflict. Uses proof of stake with proof of history. Anchor is the common Rust development framework.
Cardano Haskell, Plutus Extended UTXO model; execution and storage fees Uses stake-based consensus and places a strong emphasis on formal verification. Script execution depends on the transaction’s execution budget.
Cosmos SDK chains Primarily Rust compiled to WebAssembly through CosmWasm Application-specific account or UTXO model; chain-specific fees Each sovereign chain defines its own consensus, governance, and security. Common development environments include Ignite and Cosmos SDK CLI tools.
Substrate-based chains Rust, FRAME runtime, WebAssembly Configurable execution and fee model Provides a framework for building specialized blockchains. Some chains, such as Moonbeam, expose an EVM-compatible environment.
Hyperledger Fabric Go, Java, or Node.js chaincode Permissioned transactions; normally no gas Designed for consortium networks with enterprise identity, channel privacy, and policy-based approvals. Finality follows the network’s consensus configuration.

The deployment process is similar across these systems: compile the contract, deploy its bytecode or program to a test network, test integrations, and publish it to mainnet. EVM contracts can often be deployed unchanged across EVM-compatible chains, but fees, consensus, finality, and security still differ by network.

Blockchain and Merkle Structures

A simplified blockchain is a linked list of blocks. Each block contains an index, timestamp, transaction data, previous block hash, nonce, and current hash:

  • Previous hash: Functions as a hash pointer to the preceding block.

  • Current hash: Cryptographically commits to the block header and data.

  • Hash chaining: Changing an earlier block invalidates every subsequent block hash. Consensus and finality are still required to prevent a rewritten history.

  • Merkle root: Transaction hashes are combined into a Merkle tree, allowing a Merkle root to commit to the complete transaction set with one hash.

SHA-256 processes a block containing (m) bytes in O(m) time. Building a conventional binary Merkle tree takes O(n) hash operations and O(n) space. A Merkle proof contains O(log n) hashes and verifies in O(log n) time with O(1) additional workspace. Bitcoin uses a binary Merkle tree for transactions, while Ethereum uses Merkle-Patricia tries for its state and transaction structures.

Proof of Work

Proof of work is a search problem: miners repeatedly vary a nonce until the block hash falls below a target value. With difficulty (d), the expected work is O(2^d) hash attempts; the worst case is unbounded because a valid nonce might take arbitrarily long. Extra space is O(1) for fixed-size headers, excluding the header input.

Bitcoin uses specialized proof-of-work mining with double SHA-256. Ethereum abandoned proof of work for proof of stake in 2022.

Common Pitfalls and Interview Tips

  • An empty chain is rejected; a valid one-element chain must contain a correctly hashed genesis block. Duplicate transaction data is allowed, and malformed links or negative indexes and nonces are rejected.

  • validate_chain checks structural integrity, not consensus, finality, transaction signatures, or whether a non-genesis hash satisfies the proof-of-work target.

  • Do not treat all EVM networks as having identical fees or security. Rollup operators, bridges, and upgrade mechanisms introduce additional trust assumptions.

  • Test on a test network, audit the contract, protect deployment keys, and consider reentrancy, access control, and integer-overflow risks.

  • Common follow-up questions contrast account-based and UTXO models, proof of work and proof of stake, bridge security, gas calculation, and finality guarantees.

18

How do smart contracts obtain off-chain data through oracles?

Smart contracts cannot directly browse the internet because their execution must be deterministic. They obtain off-chain data through oracles, which authenticate external information and submit it as transaction data, calldata, or cryptographic proofs.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Access Methods

  • Centralized oracle: A trusted service fetches data and sends it to the contract. This is simple but creates a single point of failure.

  • Decentralized oracle network: Multiple independent nodes fetch and validate the same data, then agree on a result. Examples include Chainlink and Pyth.

  • Cryptographic attestation: An oracle signs a value or a Merkle root containing values. The contract verifies the signature or proof before accepting the update.

  • Optimistic oracle: The oracle proposes a value and opens a challenge period. Incorrect proposals can be disputed and rejected.

  • On-chain proof submission: A caller can submit an off-chain value together with a Merkle proof. This reduces the data required, although an oracle must still establish where the root came from.

Data Structures and Verification

A blockchain is a linked list of blocks containing an index, timestamp, data, previous-block hash, nonce, and block hash. Changing an earlier block changes its hash, invalidating every subsequent link.

Off-chain datasets can be represented with a Merkle tree:

  1. Hash each data item with SHA-256.

  2. Pair adjacent hashes and hash each pair to form the next level.

  3. Repeat until one Merkle root remains.

  4. Store or attest that root through an oracle.

  5. Submit a value with its Merkle proof, containing one sibling hash per tree level.

The contract hashes the submitted value and traverses the proof. It matches the calculated root if the value belongs to the committed dataset. A Merkle proof proves consistency with a root, but not that the root is truthful; the oracle or decentralized network must authenticate it.

Code Example

This educational Python example demonstrates a minimal hash-linked blockchain, a Merkle proof, and chain validation. It is not production-ready and does not implement digital signatures or live network access.

from dataclasses import dataclass
import hashlib
import hmac
import json
from typing import Any


def sha256(data: bytes) -> bytes:
    """Return the SHA-256 digest of data."""
    return hashlib.sha256(data).digest()


@dataclass
class Block:
    index: int
    timestamp: str
    data: dict[str, str]
    previous_hash: str
    nonce: int = 0
    hash: str = ""

    def calculate_hash(self) -> str:
        """Calculate this block's hash from its canonical contents."""
        payload = {
            "index": self.index,
            "timestamp": self.timestamp,
            "data": self.data,
            "previous_hash": self.previous_hash,
            "nonce": self.nonce,
        }
        encoded = json.dumps(
            payload, sort_keys=True, separators=(",", ":")
        ).encode("utf-8")
        return sha256(encoded).hex()

    def mine(self, difficulty: int = 2) -> None:
        """Search for a nonce satisfying the proof-of-work target."""
        target = "0" * difficulty
        while True:
            self.hash = self.calculate_hash()
            if self.hash.startswith(target):
                return
            self.nonce += 1


def validate_chain(blocks: list[Block]) -> bool:
    """Validate block links, indexes, hashes, and proof of work."""
    target = "00"

    for index, block in enumerate(blocks):
        expected_previous = "0" * 64 if index == 0 else blocks[index - 1].hash
        if block.index != index or block.previous_hash != expected_previous:
            return False
        if not block.hash.startswith(target):
            return False
        if not hmac.compare_digest(block.hash, block.calculate_hash()):
            return False

    return True


def merkle_root(leaves: list[str]) -> str:
    """Calculate a Merkle root from hexadecimal SHA-256 leaves."""
    if not leaves:
        raise ValueError("At least one leaf is required")

    level = [bytes.fromhex(leaf) for leaf in leaves]
    while len(level) > 1:
        if len(level) % 2:
            level.append(level[-1])
        level = [sha256(level[i] + level[i + 1]) for i in range(0, len(level), 2)]

    return level[0].hex()


def verify_merkle_proof(
    leaf: str,
    proof: list[tuple[str, bool]],
    expected_root: str,
) -> bool:
    """Verify a leaf against a Merkle root; the flag marks left siblings."""
    current = bytes.fromhex(leaf)

    for sibling_hex, sibling_is_left in proof:
        sibling = bytes.fromhex(sibling_hex)
        pair = sibling + current if sibling_is_left else current + sibling
        current = sha256(pair)

    return hmac.compare_digest(current.hex(), expected_root)


leaves = [sha256(f"price:{price}".encode()).hex() for price in ("101", "102", "103")]
root = merkle_root(leaves)
block = Block(0, "2025-01-01", {"oracle_root": root}, "0" * 64)
block.mine()

print(validate_chain([block]))  # True

# Proof for leaves[1]: left sibling leaves[0], then the duplicated last leaf's parent.
proof = [(leaves[0], True), (sha256(bytes.fromhex(leaves[2]) * 2).hex(), False)]
print(verify_merkle_proof(leaves[1], proof, root))  # True

Complexity

  • Merkle root construction: Best, average and worst case are O(n) time because every leaf is hashed, and O(n) auxiliary space for the tree levels.

  • Merkle proof verification: O(log n) time and O(log n) proof space because one sibling is checked per level.

  • Blockchain validation: O(n) time for n blocks and O(1) auxiliary space, excluding the input chain. Storing the chain requires O(n) space.

  • Proof-of-work mining: For a target requiring d leading zero bits, the expected number of hash attempts is O(2^d); the worst case is unbounded. This is separate from oracle verification.

Common Pitfalls

  • A Merkle proof proves membership against a root, not the real-world accuracy of the root.

  • A centralized oracle removes blockchain decentralization from the data-fetching step.

  • Oracle updates should include freshness, source, and signer checks to prevent stale or replayed data.

  • Bitcoin uses proof of work, while Ethereum has used proof of stake since 2022; either consensus mechanism does not replace the need for an oracle.

  • Common interview follow-ups ask how signers are selected, how stale reports are handled, and how a Merkle proof is verified in constant space.

19

How do smart contracts handle exceptions and errors?

Smart contracts use revert semantics to handle failed execution: state changes made by the failed call are rolled back, the error is recorded, and execution continues only if the caller explicitly catches the failure. On Ethereum, an uncaught revert produces a failed transaction receipt rather than corrupting the blockchain.

Read full answer

Applies toSolidity 0.8.x (EVM)

Error-Handling Model

In Solidity 0.8.x, common failure mechanisms are:

  • require(condition, reason): Reverts with a string reason when the condition is false. Suitable for expected input or authorization failures.

  • revert CustomError(): Reverts with a compact, structured error. Custom errors (introduced in Solidity 0.8.4) generally require less gas than string errors.

  • assert(condition): Signals an internal invariant violation. A failed assertion consumes all remaining gas and rolls back state. Use it for bugs that should not normally occur, not for user validation.

  • try/catch: Catches failures from external function calls or contract creation. It can distinguish a string revert, a Panic, and arbitrary low-level revert data.

  • Low-level calls: Calls such as address.call return a success flag instead of automatically bubbling the revert. The caller must check that flag and inspect returned revert data.

If an exception escapes the top-level transaction call, the EVM reverts that call’s state changes and consumes gas. The transaction receipt has a failed status, while the sender’s nonce increment and transaction fee remain recorded. A caller using try/catch may recover and let the outer transaction succeed.

Best Practices

  • Use custom errors for expected failures and reserve assert for internal invariants.

  • Catch a revert only when the caller has a meaningful recovery or reporting strategy.

  • Always check the success flag returned by low-level calls.

  • Keep contract execution deterministic; avoid external network calls and nondeterministic inputs.

Common Pitfalls

  • Assuming a revert only reverses one assignment: all state changes in the failed call frame are reverted.

  • Using try/catch around internal calls, which Solidity does not permit directly.

  • Treating a low-level call’s false result as a successful transaction.

  • Forgetting that a caught revert may allow the outer transaction to succeed.

20

What is a reentrancy vulnerability in smart contracts?

A reentrancy vulnerability occurs when a smart contract transfers control to another contract before updating its own state, allowing the callee to call back into the vulnerable function and violate a contract invariant. The blockchain’s hashes can remain valid even though the contract’s internal accounting is incorrect.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Reentrancy Occurs

A vulnerable function commonly follows an unsafe sequence:

  1. Read and validate the caller’s balance.

  2. Transfer assets or make an external call.

  3. Update the caller’s balance afterward.

During step 2, the recipient can re-enter the vulnerable function. Because the balance has not yet been reduced, the nested call can pass the same check that the original call passed.

This vulnerability contributed to the 2016 Ethereum DAO exploit. The problem was the DAO’s contract logic, not the integrity of Ethereum’s hash chain or cryptographic primitives.

Blockchain Data-Structure Perspective

A simplified blockchain can be modeled as a linked list of blocks. Each block contains an index, timestamp, data, previous hash, nonce, and hash. The previous hash acts as a hash pointer to the preceding block.

  • Cryptographic hashing: SHA-256, available through hashlib.sha256 in Python 3.12, produces a fixed-size digest. Changing a block changes its hash and invalidates the next block’s stored previous-hash pointer unless the chain is recomputed.

  • Merkle trees: Transaction hashes can form leaves whose internal hashes produce a Merkle root. A Merkle proof verifies inclusion using a path of approximately logarithmic length.

  • Immutability through hash chaining: Modifying an earlier block requires recomputing subsequent hashes, making unauthorized historical changes detectable through validation.

  • Proof of work: A miner searches for a nonce or nonce-bearing header satisfying a target condition. Bitcoin uses proof of work; Ethereum transitioned to proof of stake during the Merge in September 2022.

Hash chaining protects the history of transactions and blocks, but it does not establish that the smart contract’s state transitions obey its intended accounting rules.

Reentrancy Walkthrough

Consider a Python-style state model with balance = 100 and a withdrawal amount of 10:

  1. The outer withdrawal reads 100 and passes the balance check.

  2. The contract transfers 10 to the recipient before updating its stored balance.

  3. The recipient re-enters the withdrawal function while the outer call is paused.

  4. The inner call reads the unchanged balance of 100, transfers another 10, and writes 90.

  5. The outer call resumes and writes its stale calculation of 90, overwriting the inner result.

The recipient receives 20, while the contract records a balance of 90 instead of 80. The defect depends on reading stale state and updating it after control leaves the contract.

Complexity

Let r be the number of external calls actually made, R the maximum possible number in the relevant execution, n the number of blocks, t the number of transactions, and N the size of a finite proof-of-work search space.

Operation or scenario Best time Average time Worst time Space Reason
Reentrant callbacks O(1) O® for a workload with r calls; no universal average O® O® call-stack space Every callback adds execution work and a stack frame
Validate an n-block chain O(n) O(n) O(n) O(1) auxiliary; input occupies O(n) Each block is checked once
Verify a Merkle proof O(log t) O(log t) O(log t) O(log t) proof input and O(1) extra workspace One sibling hash is processed per tree level
Proof-of-work search O(1) O(2^b) expected O(N) O(1) working space A b-bit target requires about 2^b attempts on average; all N candidates may be searched

Auxiliary space excludes the input and persistent contract storage unless explicitly stated otherwise.

Common Pitfalls and Mitigations

  • Apply checks-effects-interactions: Validate inputs, update state, and only then make external calls.

  • Use a reentrancy guard: A mutex-like guard prevents nested calls. Guards protecting related public functions must cover cross-function reentrancy as well.

  • Do not rely on gas limits alone: Execution is gas-bounded, but an attacker can still exploit reentrancy within that budget. Cap forwarded gas and handle out-of-gas failures, but also protect state.

  • Check arithmetic safely: Solidity 0.8 and later check arithmetic by default. Earlier Solidity versions commonly used SafeMath or explicit checks.

  • Handle balances consistently: Avoid stale cached balances and account for fee boundaries, off-by-one conditions, and invalid input.

  • Do not treat cycle detection as a defense: A visited set does not replace state protection or a reentrancy guard.

Interviewers commonly ask about checks-effects-interactions, reentrancy guards, cross-function reentrancy, gas exhaustion, and how an exploit violates a state invariant.

21

How does Ethereum differ from Bitcoin in purpose and consensus?

Ethereum is a programmable blockchain platform for smart contracts and decentralized applications, while Bitcoin is primarily a peer-to-peer electronic-cash system. Both use hash-linked blocks, but Ethereum uses an account model and proof of stake, whereas Bitcoin uses an unspent transaction output model and proof of work.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Differences

Area Ethereum Bitcoin
Primary purpose Smart contracts and decentralized applications Digital payments and value transfer
Execution model Ethereum Virtual Machine, or EVM Bitcoin Script
State model Accounts with balances, code, and storage Unspent transaction outputs, or UTXOs
Consensus Proof of stake since 2022 Proof of work
Transaction costs Gas, based on computation and storage Transaction fees based on transaction size and priority
Finality Explicit checkpoint finality under proof of stake Probabilistic finality based on accumulated work and confirmations
Supply policy Protocol-controlled issuance and fee burning Protocol-defined issuance with a 21-million-coin cap

The EVM is Turing-complete when gas is considered: contracts can perform general computation, but every operation consumes gas. Bitcoin Script intentionally supports a narrower, more restricted programming model.

Blockchain Structure, Hashing, and Merkle Proofs

A simplified teaching block contains:

  • Index: Position of the block in the chain.

  • Timestamp: Time associated with block creation.

  • Data: Transactions or a reference to them.

  • Previous hash: Hash pointer connecting the block to its parent.

  • Nonce: Value varied during proof-of-work search; Bitcoin uses this in its block header.

  • Hash: Cryptographic commitment to the block’s header fields.

Actual protocols do not literally store every teaching field in every header. For example, Bitcoin stores a timestamp, previous-block hash, Merkle root, compact difficulty target, and nonce; the block index is normally derived from position. Ethereum’s proof-of-stake blocks do not use mining nonces in the Bitcoin sense.

A common SHA-256 model is hash = SHA256(index || timestamp || data || previous_hash || nonce). Changing the nonce changes the hash. Changing data, a timestamp, or the previous hash also invalidates the computed hash, invalidating any child block that still commits to the old hash. This creates tamper evidence, not absolute immutability: rewriting history still requires overcoming the network’s consensus and coordination rules.

Bitcoin commits to transactions with a standard Merkle tree. A Merkle proof can prove that a transaction belongs to a block using O(log n) hashes. Ethereum uses Merkle Patricia tries for transaction and state commitments; these are different from Bitcoin’s conventional Merkle tree.

Consensus and Finality

Bitcoin miners search for a block header hash below a target determined by network difficulty. This is a proof-of-work search problem: miners vary the nonce and other header fields until a qualifying hash is found. The work makes producing a competing chain expensive.

Ethereum moved to proof of stake during “The Merge” in 2022. Validators stake ETH and participate in proposing or attesting to blocks instead of mining them through proof of work. Consensus selects canonical chain history, while finality describes how strongly that history is expected to remain unchanged.

Neither system provides instant, unconditional finality:

  • Bitcoin: More confirmations increase confidence because a competing chain must replace accumulated work.

  • Ethereum: Finalized checkpoints provide explicit finality guarantees under the protocol’s assumptions.

Complexity

Here, l is the number of Merkle leaves, t is the required number of leading-zero bits, m is the number of bytes in a hash input, b is the number of blocks, and N is the size of a fixed proof-of-work candidate space.

Operation Best Average or Expected Worst Space
SHA-256 hashing O(m) O(m) O(m) O(1) auxiliary when streaming; O(m) for a materialized input
Build Merkle tree O(l) hash operations O(l) hash operations O(l) hash operations O(l) stored digests; input excluded
Verify Merkle proof O(log l) hash operations O(log l) hash operations O(log l) hash operations O(log l) proof records; proof data counted
Proof-of-work search O(m) O(2^t × m) expected O(N × m) for fixed N candidates; no finite bound for an unbounded search O(m) temporary serialization
Validate a chain O(b) hash operations O(b) hash operations O(b) hash operations O(1) auxiliary space; chain input excluded

For Merkle construction, each hash operation processes up to m bytes, giving O(l × m) byte-level work. Proof-of-work’s expected cost assumes a random-oracle model and approximately 2^t independent attempts.

Common Pitfalls

  • Do not describe current Ethereum as proof of work; it has used proof of stake since 2022.

  • Do not claim hash chaining makes data mathematically immutable; it makes unauthorized changes detectable.

  • Do not confuse Bitcoin’s Merkle tree with Ethereum’s Merkle Patricia trie.

  • Remember that O(2^t) proof-of-work cost is expected, not a guaranteed completion time.

  • In validation logic, recompute each block’s hash and compare its previous hash with the parent’s hash.

  • Blockchain hash validation alone does not validate signatures, balances, transaction ordering, or distributed consensus.

22

What is gas in the Ethereum EVM?

Gas is Ethereum’s unit of computation for transactions and smart-contract execution. It meters EVM operations so transactions have declared resource ceilings and execution clients can stop execution when those ceilings are exhausted.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Gas Basics

Each EVM instruction has a protocol-defined gas cost, sometimes depending on inputs such as memory expansion. Gas is charged before or during execution.

  • Gas units: Measure computation, storage access, contract creation, and calldata processing.

  • Gas limit: The maximum gas a transaction may consume. The sender must have enough ETH to cover the limit at the applicable maximum price.

  • Gas used: The gas consumed by execution after applicable refunds are applied.

  • Gas price: The amount of wei charged per gas unit.

  • Ether (ETH): The asset used to pay for gas; gas itself is not ETH.

The transaction fee is:

fee = gas used × effective gas price

If the top-level execution frame exhausts its gas, the transaction fails, its state changes are reverted, and all gas supplied to that attempt is consumed. A nested call can run out of gas and return failure to a parent contract that handles the failure.

Ethereum Fee Model

Since the London upgrade and EIP-1559, Ethereum primarily uses a dynamic base fee plus an optional priority fee.

Component Behavior
Base fee Protocol-set price derived from parent-block gas usage and burned
Priority fee Optional tip paid to the block proposer, which is a validator selected to build the block
Maximum fee Sender’s ceiling on the total gas price, protecting against unexpected base-fee increases

The effective priority fee is the smaller of the requested priority fee and the difference between the maximum fee and base fee. Unused gas is refunded, while protocol execution refunds are capped at one-fifth of the gas used.

A plain ETH transfer with empty calldata normally has an intrinsic cost of 21,000 gas. Smart-contract calls add execution costs, while calldata, contract creation, storage writes, and access lists introduce additional charges.

Blocks, State, and Inclusion

A block’s gas limit bounds the sum of gas used by its transactions. When demand is high, transactions compete for limited block space based on their effective fees.

  • Block headers commit to transaction and receipt collections through Merkle roots.

  • Merkle proofs demonstrate that a transaction or receipt belongs to a committed collection without downloading the entire block.

  • Execution receipts record outcomes such as success, failure, gas used, and logs.

  • Gas does not directly secure the hash chain, but execution outcomes affect receipts and state roots. Altering those outcomes changes the committed roots and invalidates the block’s commitments.

  • Ethereum has used proof of stake since 2022. Gas remains necessary because it meters execution independently of how consensus blocks are produced.

Why Gas Exists

Gas bounds the resources consumed by smart-contract execution and creates a market for prioritizing transactions.

  • Resource control: Loops and expensive operations must pay for every iteration or access.

  • Deterministic charging: Ethereum execution clients independently calculate gas costs from EVM rules.

  • Spam resistance: Transactions require economic value rather than merely occupying block space.

  • Predictable limits: A transaction’s gas limit prevents execution from continuing indefinitely.

  • State-cost accounting: Persistent storage operations are charged separately from inexpensive transient computation.

Gas is not proof of work and is not a mining puzzle. It is an execution-metering mechanism used by Ethereum’s state-transition system.

Complexity

At the protocol-accounting level:

  • Gas calculation: O(1) time and O(1) auxiliary space per opcode lookup and charge calculation. Best, average, and worst cases are the same because the gas schedule is deterministic.

  • Transaction execution: At most O(G) metered EVM steps for a gas budget G. This is a worst-case upper bound, not a guaranteed wall-clock runtime; best and average execution times depend on the client, hardware, state, and workload.

  • Block execution: O(ΣGᵢ + C) as a worst-case upper bound for metered work and input processing, where Gᵢ are transaction gas budgets and C is total input size.

  • Execution space: O(M + C), where M is expanded EVM memory in words and C covers input and code storage. The input itself is counted. The bounded EVM stack and call depth contribute O(1) additional space. Persistent state of size S is O(S) globally but is separate from transient per-transaction execution space.

Common Pitfalls

  • Confusing gas with gas price: one measures metered work, while the other prices that work.

  • Assuming a failed contract call is free: consumed gas is not returned for reverted execution.

  • Forgetting that the sender pays for all gas consumed by a top-level out-of-gas execution, charged at the effective gas price.

  • Assuming gas fees are entirely paid to validators: under EIP-1559, the base fee is burned and only the priority fee is paid to the proposer.

  • Treating gas as a consensus algorithm: Ethereum uses proof of stake for consensus while gas meters EVM execution.

23

What is the Ethereum Virtual Machine and its role?

The Ethereum Virtual Machine (EVM) is Ethereum’s deterministic execution environment for smart-contract bytecode. It runs contract calls and creation code, charges gas, and produces state changes, logs, and receipts used when execution clients assemble Ethereum blocks and execution payloads.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Execution Model

The EVM behaves as a stack-based virtual computer:

  • Bytecode: Compiled instructions containing operation codes for arithmetic, storage access, comparisons, and calls.

  • Stack and memory: The stack holds 256-bit words, while memory is temporary and byte-addressed for the duration of an execution.

  • Persistent storage: Contracts maintain persistent key-value state under their own addresses.

  • Gas: Each operation has a gas cost. This bounds computation and makes fees broadly track resource usage.

  • Determinism: Given the same pre-state, bytecode, transaction order, and execution context, every EVM-compatible client reaches the same result.

A failed transaction still consumes the gas used, but its state changes are reverted. This atomic behavior prevents partially applied contract operations.

Ethereum’s Role

The EVM is responsible for the execution-layer work:

  1. Execution clients validate transaction formats and signatures before invoking EVM execution.

  2. The EVM executes contract calls and contract-creation bytecode.

  3. It charges gas, while clients calculate fees using gas used and the applicable gas prices.

  4. It updates account balances, contract storage, and created contract code.

  5. It emits logs and produces transaction receipts.

  6. Execution clients calculate the state, transaction, and receipt roots committed to blocks.

The EVM is separate from consensus. Ethereum moved from proof of work to proof of stake in 2022, but the EVM remains its execution environment. A proposer orders transactions within an execution payload; validators attest to payload validity, and consensus selects the canonical chain and finalizes checkpoints. Other networks may support EVM-compatible bytecode while using different consensus mechanisms.

Data Structures and Integrity

From a data-structures perspective, a blockchain is a linked sequence in which each block stores a cryptographic commitment to its parent. A simplified block contains an index, timestamp, data, previous hash, nonce, and current hash.

Ethereum’s block header includes its parent hash and roots for transaction, state, and receipt data. These roots use Merkle Patricia tries, which support efficient authenticated proofs. A Merkle proof establishes that a transaction or state entry belongs to a committed root; it does not independently prove that the underlying data is truthful.

SHA-256, available through Python’s hashlib, is commonly used in simplified hash-chain examples. Ethereum’s own block hash uses Keccak-256, not SHA-256. Because a hash covers the parent hash and the current block’s fields, changing historical data changes that block’s hash and consequently every descendant hash. This provides tamper evidence, although it does not replace consensus, network validation, or finality.

Operation Time Space Reason
Hash one fixed-size block O(1) O(1) SHA-256 over a fixed-size input; input counted
Validate n fixed-size blocks O(n) O(1) auxiliary; O(n) including the chain Every block is checked once
Build a complete binary Merkle tree O(n) O(n) including the tree and recursion stack Each leaf is processed
Extract a proof from a built tree O(log n) O(log n) including the proof and recursion stack; O(n) total if the input tree is counted One sibling is selected per level
Verify a binary Merkle proof O(log n) O(log n) including the supplied proof; O(1) auxiliary One hash is checked per level

Proof-of-Work Search

Proof of work searches for a nonce and other header values whose resulting hash satisfies a difficulty target. For a target requiring b leading zero bits, the expected number of hash evaluations is O(2^b). The best case is O(1), the average and expected cases are O(2^b), and there is no finite worst-case bound because the search can continue indefinitely.

Bitcoin uses proof of work based on double SHA-256. Ethereum previously used Ethash but now uses proof of stake. A toy SHA-256 search requiring one leading hexadecimal zero has an expected 16 hash evaluations; it is neither Bitcoin’s exact mining algorithm nor a production blockchain.

Common Pitfalls

  • Confusing execution with consensus: The EVM executes transactions; Ethereum’s proof-of-stake consensus determines the canonical chain and finality.

  • Treating gas and fees as identical: Gas measures execution consumption; fees also depend on the applicable gas prices.

  • Treating hashes as proof of truth: A valid hash provides integrity relative to a trusted commitment, not proof that the original data is correct.

  • Confusing SHA-256 with Ethereum’s block hash: Ethereum block hashes use Keccak-256.

  • Ignoring complexity distinctions: Chain validation is O(n) for fixed-size blocks, whereas proof-of-work has an expected but unbounded search time.

  • Likely follow-up: Explain how gas, calldata, storage writes, the state trie, and finality affect Ethereum execution.

24

How does Ethereum store and commit its canonical blockchain state?

Ethereum commits the canonical blockchain state with a state_root in each execution block header. Execution clients maintain that state in local databases, and every header commits to the exact state produced by executing its block.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

State Representation

Ethereum’s state is effectively a map from addresses to accounts. Its Merkle Patricia Trie (MPT) stores each account using an RLP-encoded value containing:

  • Nonce: the number of transactions sent from the account.

  • Balance: the account balance in wei.

  • Storage root: the root of a separate MPT containing an account’s contract storage.

  • Code hash: the Keccak-256 hash of the account’s contract bytecode.

Contract-storage slots are represented by hashed keys in the storage trie. Ethereum uses Keccak-256, not SHA-256, for its protocol hashes, including the state root, storage roots, and code hashes.

The state is not duplicated inside every block. A block header contains the root that commits to its post-execution state.

Committing and Selecting the Canonical State

Execution follows these steps:

  1. The client obtains the parent state committed by the parent header’s state_root.

  2. It executes the block’s transactions and produces receipts, logs, and updated accounts.

  3. It computes the new state trie root.

  4. The result is placed in the candidate header as state_root in the consensus specification and stateRoot in JSON-RPC.

  5. Proof-of-Stake validators attest to chain progress, and Casper FFG supplies checkpoint finality.

A block hash commits to its header, including state_root. Headers also contain parent_hash, linking the block to its ancestry. Consequently, changing a historical state requires recomputing its state root and updating affected descendants; changing only a header field changes the header’s hash and descendant parent links even if its state root stays unchanged.

The header separately commits to transactions through the transactions root and to receipts through the receipts root. Logs are stored in receipts, so the receipts root also commits to them.

Canonicality comes from Proof-of-Stake consensus and finality, not from state_root alone. A state_root identifies one state snapshot but does not select which competing branch is canonical.

Merkle Proofs and Historical State

An MPT proof contains the path nodes and encoded path information needed to connect a leaf to a trusted root. A verifier recomputes the root and proves either inclusion or non-inclusion. Proving a contract-storage value normally requires both an account proof linking the trusted state root to the storage root and a storage proof for the value itself.

Nodes need not retain every historical state. They normally maintain current and recent state, while archival nodes retain historical data. Snapshots accelerate startup and recovery but are local optimizations; the trie root is the consensus commitment.

Complexity and Proof-of-Work Context

Let k be the trie path length, p the proof size in bytes, s the serialized size, and S the total stored state size. Assuming constant-time database-key lookup:

Operation Time Space
State-trie lookup O(k) worst case O(1) auxiliary if iterative; O(k) recursion stack if recursive
State-trie update O(k) worst-case node visits O(k) newly allocated nodes, excluding the existing trie
Verify an MPT proof O(p) O(1) auxiliary, excluding the proof
Hash a serialized item O(s) O(1) when streamed; O(s) if materialized
Persistent state storage — O(S) total state size

Bitcoin uses proof of work as a search problem. For a target requiring n leading zero bits, the best case is O(1), the expected case is O(2^n), and the worst case is O(2^n) for a fixed candidate set of 2^n nonces under the standard one-success model; auxiliary space is O(1). An unbounded live nonce stream has an expected rather than deterministic first-success bound.

A generic teaching blockchain often uses fields such as index, timestamp, data, previous_hash, nonce, and hash, with SHA-256 through Python’s hashlib. Those are educational proof-of-work fields, not Ethereum’s post-merge execution model. Ethereum moved to Proof of Stake on 15 September 2022 and current execution headers do not contain a proof-of-work mining nonce.

Common Pitfalls

  • Do not confuse parent_hash, which identifies ancestry, with state_root, which commits to state.

  • Do not describe logs as having a separate header root; they are committed through receipts.

  • Do not substitute SHA-256 for Ethereum’s Keccak-256.

  • Do not assume a snapshot, a local database, or the longest branch determines canonicity.

  • Do not assume every node stores complete historical state.

  • Common follow-ups ask how state proofs work, how reorganizations affect state, and how finality limits reorganization risk.

25

What are ERC-20 and ERC-721 token standards?

ERC-20 and ERC-721 are Ethereum token standards with different ownership models: ERC-20 represents fungible tokens whose units are interchangeable, while ERC-721 represents non-fungible tokens identified by unique token IDs within a contract.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

ERC-20: Fungible Tokens

ERC-20 defines a common interface for tokens such as utility tokens, governance tokens, stablecoins, and wrapped assets.

Its required functions are:

  • totalSupply(): total number of tokens in circulation.

  • balanceOf(address owner): an owner’s token balance.

  • transfer(address to, uint256 amount): transfers tokens and returns a Boolean.

  • transferFrom(address from, address to, uint256 amount): spends an allowance.

  • approve(address spender, uint256 amount): sets a spender’s allowance.

  • allowance(address owner, address spender): returns the remaining allowance.

It also defines Transfer and Approval events. Implementations commonly expose optional name, symbol, and decimals values. Decimals affect display conventions; balances and transfers are always represented as integer base units.

Fungibility means units are interchangeable under the contract’s rules. It does not mean tokens must have equal market prices at every moment.

ERC-721: Non-Fungible Tokens

ERC-721 defines a common interface for unique tokens representing artwork, collectibles, game assets, domain names, and tokenized ownership interests.

Its core functions include:

  • balanceOf(address owner): number of tokens owned.

  • ownerOf(uint256 tokenId): owner of a token.

  • transferFrom(address from, address to, uint256 tokenId): transfers a token.

  • Two safeTransferFrom overloads, including one with additional bytes data.

  • approve(address to, uint256 tokenId): approves one token.

  • setApprovalForAll(address operator, bool approved): appoints an operator for all of an owner’s tokens.

  • getApproved(uint256 tokenId) and isApprovedForAll(address owner, address operator).

  • supportsInterface(bytes4) through ERC-165.

The standard defines Transfer, Approval, and ApprovalForAll events. A safe transfer calls onERC721Received when the recipient is a contract and requires the receiver to acknowledge the transfer.

tokenURI(uint256) belongs to the optional ERC-721 Metadata extension and may resolve to JSON metadata. totalSupply(), tokenByIndex(), and tokenOfOwnerByIndex() belong to the optional ERC-721 Enumeration extension.

Key Differences

Aspect ERC-20 ERC-721
Ownership model Fungible balance Unique tokenId
Transfer quantity Integer amount One token ID
Metadata Optional name, symbol, decimals Optional tokenURI extension
Approval Amount-based allowance Per-token or operator approval
Fractional units Possible depending on implementation Not represented by the standard
Discovery No standard enumeration Optional enumeration extension

Token IDs must be unique within their ERC-721 contract, but two different contracts can use the same ID.

Representation, Complexity, and Blockchain Context

The standards specify interfaces and events, not mandatory storage layouts. Common implementations use mappings or persistent tries for balances, allowances, owners, and approvals, but these are implementation choices rather than requirements of ERC-20 or ERC-721.

The standards guarantee no Big-O complexity because execution depends on the implementation. In a conventional hash-map model, a balance, ownership, or allowance lookup and a single-token update take O(1) average time and O(n) worst-case time, with O(1) auxiliary space excluding input and persistent state; storing n accounts, tokens, or allowances takes O(n) space. Scanning all m tokens through an ERC-721 Enumeration implementation is O(m) time with O(1) auxiliary space when indexed directly. Ethereum mappings use persistent trie structures, so actual gas costs depend on trie paths and contract state. No recursion is required, so the recursion-stack cost is O(1).

Token contracts execute as transactions within blockchain blocks. In a typical proof-of-work blockchain, a block contains an index, timestamp, transactions or data, previous-block hash, nonce, and block hash. SHA-256, commonly demonstrated in Python with hashlib.sha256, provides a hash pointer; changing earlier block data changes its hash and invalidates the following chain. Merkle roots commit to transaction or state data, and Merkle proofs can demonstrate inclusion under a trusted root.

Proof-of-work is a search problem: a miner varies a nonce until the block hash satisfies the network’s target condition. Bitcoin uses proof-of-work and double SHA-256; Ethereum moved to proof-of-stake in 2022.

Common Pitfalls and Interview Tips

  • Do not equate ERC-20 fungibility with equal market value or unlimited divisibility.

  • Use safeTransferFrom when the recipient may be a contract that must process the NFT.

  • ERC-20 approvals can have race conditions; changing a nonzero allowance directly can be unsafe.

  • Metadata may be mutable, unavailable, or stored off-chain, so verify the URI and its backing storage.

  • Only callbacks such as ERC-721 safe transfers create recipient-call reentrancy exposure; apply checks-effects-interactions and appropriate guards where relevant.

  • Solidity 0.8 and later check integer overflow by default; older code used libraries such as SafeMath.

  • ERC-1155 can represent multiple fungible and non-fungible token types in one contract, but it does not itself fractionalize an ERC-721.

  • EIP-2612 uses signatures for approvals and can enable gasless approval flows, although the later transaction still consumes gas.

26

What information does a blockchain block contain?

A blockchain block is a container that commits to a batch of transactions and links itself cryptographically to the preceding block. Its hash, Merkle root, transaction data, consensus metadata, and previous-block hash collectively make unauthorized changes detectable.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Block Anatomy

A simplified hash-chain block contains:

Field Purpose
index Identifies the block’s position in the chain. Bitcoin does not store this in its block header; wallets and indexers commonly derive or track it separately.
timestamp Records a block-creation time subject to protocol rules. Bitcoin’s timestamp is miner-supplied and consensus-constrained rather than a trusted wall-clock reading.
data or transactions Contains the transactions or other application payload. In Bitcoin, transactions are stored separately from the header but are committed to by the Merkle root.
previous_hash Acts as a hash pointer to the preceding block. Simplified chains commonly use an all-zero sentinel for genesis, but this is a protocol-specific convention.
merkle_root Commits to transactions through a Merkle tree. Some protocols use commitment schemes other than Merkle trees.
nonce Supplies variable input for proof-of-work search. It is central to Bitcoin mining but is not used for mining under proof of stake.
hash The derived identifier of the block header. Bitcoin uses double SHA-256 (SHA-256d), while many educational chains use a single SHA-256.

Bitcoin’s header specifically contains a version, previous-block hash, Merkle root, timestamp, bits target, and nonce. The block hash is computed from that header rather than stored as an additional header field.

Hash Chaining and Merkle Trees

Each block header normally includes the previous block’s hash:

Block N hash → Block N-1 hash → Block N-2 hash

Changing an earlier transaction changes its Merkle root and therefore the block’s hash. Every subsequent block then references a different previous hash, so the chain must be recomputed and the consensus rules re-established. This provides tamper evidence, not absolute immutability; finality depends on the consensus mechanism.

In a Merkle tree:

  • Transactions or their transaction IDs are hashed to form leaves.

  • Pairwise leaf hashes are hashed repeatedly to form an internal root.

  • The root is stored in the block header.

  • A Merkle proof supplies the sibling hashes needed to verify one transaction against the root.

  • If a level has an odd number of nodes, Bitcoin duplicates the final hash; other protocols may define a different convention.

For n transactions, a proof contains O(log n) sibling hashes. A complete Merkle tree can be constructed in O(n) time and O(n) auxiliary space when transaction representations have fixed size.

In Python, hashlib.sha256(data).digest() computes a SHA-256 digest. Bitcoin applies SHA-256 twice to its serialized header.

Proof of Work and Consensus

Proof of work treats mining as a search problem: miners repeatedly alter candidate inputs, usually the nonce, until the resulting hash satisfies the network’s target difficulty. A candidate succeeds when its hash is below the target or, in a simplified example, has a required number of leading zero hexadecimal digits.

Bitcoin uses proof of work. Ethereum completed its transition to proof of stake in September 2022, replacing mining with validator attestations and stake-based consensus. Both mechanisms provide Sybil resistance, but proof of stake relies primarily on economic security for consensus and finality.

Complexity and Edge Cases

Assume fixed-size headers and transactions, constant-time hash comparisons, and an unbounded nonce search space.

Operation Time Space Reason
Compute one header hash O(1) O(1) The serialized header has fixed size and hashing is constant-time.
Construct a Merkle root for n transactions O(n) O(n) The total number of nodes across the levels is linear, and the level lists are retained during construction.
Verify one Merkle proof O(log n) O(1) auxiliary Each level requires one hash comparison; the supplied proof itself occupies O(log n) space.
Structurally validate N blocks containing T transactions O(N + T) O(max transactions per block) auxiliary Each header and transaction commitment is checked once; Merkle processing temporarily stores one block’s hash levels.
Search for z leading zero hexadecimal digits Best O(1); average O(16^z); no finite worst-case bound O(1) per attempt Each attempt succeeds with probability 16^-z; the nonce space is unbounded.

Space figures exclude the stored input chain and transactions unless explicitly stated otherwise. The Merkle construction requires no recursion-stack space. With variable-size transactions, hashing time scales with the total number of bytes rather than only the transaction count. Full semantic or cryptographic transaction validation also has additional costs.

Common Pitfalls

  • Do not assume every blockchain uses exactly the same fields or a Merkle tree.

  • Do not say Bitcoin stores transactions directly in its block header.

  • Do not confuse a previous-hash pointer with a complete copy of the previous block.

  • Do not describe hash chaining as absolute immutability; it provides tamper evidence, while consensus determines finality.

  • Handle the genesis sentinel and block numbering separately to avoid off-by-one errors.

  • Empty transaction sets, single transactions, duplicate transactions, and odd Merkle levels require explicit protocol rules.

  • Common follow-up questions cover Merkle-proof verification, fork resolution, transaction ordering, and the difference between tamper evidence and finality.

27

What is a Merkle tree in blockchain?

A Merkle tree is a hash-based tree that provides a compact commitment to a collection of transactions. Its root can be stored in a block header, while a Merkle proof allows a client to verify that a particular transaction is included without downloading every transaction.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A typical binary Merkle tree has these components:

  • Leaves: Hashes of the transactions or transaction identifiers being committed to.

  • Internal nodes: Hashes combining two child hashes.

  • Merkle root: The single hash at the top of the tree.

  • Merkle proof: The sibling hashes collected along the path from one leaf to the root.

Let H denote SHA-256 and || denote byte concatenation. For transactions A, B, C, and D, the tree is constructed as follows:

  1. Hash each transaction: hA = H(A), hB = H(B), hC = H(C), and hD = H(D).

  2. Pair adjacent leaves: hAB = H(hA || hB) and hCD = H(hC || hD).

  3. Combine the two internal nodes: root = H(hAB || hCD).

The root commits to the ordering and contents of the entire transaction list. Changing any transaction changes its leaf, its ancestors, and ultimately the root. In Python, SHA-256 is provided by hashlib.sha256; the exact serialization and concatenation rules must remain consistent between root construction and proof verification.

When a level contains an odd number of nodes, a common convention is to duplicate its final node. Other systems can use different rules, so a verifier must know the convention used by the tree.

Merkle Proofs

To prove that transaction B is included, the proof contains the sibling hashes encountered while moving from hB to the root:

  1. At the leaf level, the sibling is hA.

  2. After calculating hAB, the sibling is hCD.

  3. Combining hAB and hCD produces the expected root.

The verifier hashes the transaction, combines it with each sibling in the correct left-or-right order, and compares the result with the expected root. A valid proof normally contains O(log n) sibling hashes for n transactions.

The proof establishes inclusion under the assumed root. The root must itself be obtained from a trusted source or authenticated through block-header validation and consensus. A Merkle proof does not prove that the transaction is valid or authorized.

Block Structure and Hash Chaining

A blockchain is also a hash chain of blocks. A simplified block structure contains:

  • index: The block’s position in the chain.

  • timestamp: The block’s creation time.

  • data: Transactions or a commitment such as a Merkle root.

  • previous_hash: The preceding block’s hash.

  • nonce: A value varied during proof-of-work mining.

  • hash: The resulting hash of the block header.

Each block’s previous_hash acts as a hash pointer to its predecessor. Changing an earlier block changes its hash and every descendant hash, invalidating the affected proof-of-work and requiring the chain’s consensus rules to accept the replacement.

Proof of work is a search problem: miners repeatedly vary a nonce until the block hash satisfies a target. Bitcoin uses proof of work. Ethereum completed its transition to proof of stake in 2022.

Complexity

The following assumes fixed-size transaction inputs and SHA-256 digests. Space is stated relative to the original input; there is no recursion stack because these operations can be implemented iteratively.

Operation Best Average Worst Space Reason
Build a Merkle root O(n) O(n) O(n) O(n) auxiliary beyond the input transactions Every leaf and internal node is hashed once.
Generate a proof from a retained tree O(log n) O(log n) O(log n) O(log n) for the proof; O(1) additional working space Only one root-to-leaf path is followed.
Rebuild a tree from flat leaves and generate a proof O(n) O(n) O(n) O(n) auxiliary beyond the input leaves The tree levels must be reconstructed.
Verify a proof O(log n) O(log n) O(log n) O(log n) including the supplied proof; O(1) auxiliary space One hash is calculated per level.
Validate a chain of k blocks O(k) O(k) O(k) O(k) including the chain; O(1) auxiliary space Each block is hashed and checked once.
Proof-of-work search O(1) O(2^d) expected Unbounded O(1) auxiliary space For a target requiring d leading zero bits, approximately 2^d trials are expected.

Common Pitfalls

  • Empty input: Most Merkle-root algorithms need an explicit convention for an empty transaction set.

  • Single transaction: Its hash becomes the root, and its inclusion proof is empty.

  • Odd levels: Duplicating the final node is a convention, not a universal rule.

  • Wrong proof direction: The verifier must know whether each sibling belongs on the left or right.

  • Duplicate transactions: A proof commits to an occurrence at a particular position; it does not guarantee transaction uniqueness.

  • Root trust: Checking a proof against an untrusted root does not establish inclusion in the canonical blockchain.

  • Overclaiming validation: A Merkle proof does not validate signatures, transaction rules, consensus, or proof-of-work.

28

How do blockchains achieve scalability and high performance?

A blockchain improves scalability by combining compact, independently verifiable data structures with techniques that move computation off-chain or parallelize it. Hash chaining, Merkle trees, and an efficient consensus mechanism preserve integrity while allowing nodes to validate large ledgers efficiently.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Data Structures

A typical block contains:

  • Index: Position of the block in the chain.

  • Timestamp: Creation time, included in the block hash.

  • Data: Transactions or other block content.

  • Previous hash: Hash pointer to the preceding block.

  • Merkle root: Commitment to the transactions without listing every transaction in the block header.

  • Nonce: Value varied during proof-of-work search.

  • Hash: Hash of the block header and its Merkle root.

Hash chaining makes historical modification detectable: changing a transaction changes its block hash, which invalidates every following block. A Merkle tree lets a light client verify one transaction using a Merkle proof containing the transaction hash and its sibling hashes. This proves inclusion without downloading the entire block.

Hash chaining alone does not guarantee finality. An attacker controlling consensus could rewrite history, so nodes must also follow the network’s consensus rules.

Scalability and Performance Strategies

  • Increase block capacity or frequency: More transactions fit into each block, but larger blocks take longer to propagate and validate. Nodes may receive conflicting views and create orphaned blocks.

  • Batch transactions: Grouping transactions reduces per-transaction overhead and is useful when validity is independent.

  • Use rollups or Layer 2 networks: Ethereum rollups execute many transactions off the main chain and submit compressed data or proofs for settlement. Bitcoin uses Lightning Network for off-chain payments.

  • Shard state and execution: Sharding divides work among subsets of validators, but cross-shard transactions and state consistency add complexity.

  • Optimize storage: Full nodes maintain the complete ledger, while pruning, checkpoints, snapshots, and state compaction reduce historical storage requirements.

  • Optimize networking and validation: Compact block representations, efficient gossip, transaction pools, caching, and parallel signature verification reduce propagation and processing overhead.

  • Choose an appropriate consensus mechanism: Bitcoin uses proof of work, where finding a valid hash is a probabilistic search problem. Ethereum transitioned to proof of stake in 2022; validators stake assets instead of searching hashes.

Security and decentralization constrain these optimizations. For example, skipping signature checks might improve throughput, but an invalid transaction could then enter the chain.

Complexity

Let (B) be the number of blocks, (S) the total encoded chain size, (n) the number of transactions in a block, (d) the difficulty measured in bits, and (M) the maximum transactions per block.

Operation Best time Average time Worst time Auxiliary space
Hash a block (O(s)) (O(s)) (O(s)) (O(s)), where (s) is block size
Build a Merkle root (O(n)) (O(n)) (O(n)) (O(n)) for tree levels
Verify a Merkle proof (O(log n)) (O(log n)) (O(log n)) (O(log n)) for the path
Validate a chain (O(S)) (O(S)) (O(S)) (O(s+M)), excluding stored chain
Find proof-of-work nonce (O(1)) (O(2^d)) expected Unbounded probabilistically (O(1))

Chain storage itself is (O(S+B)). Merkle construction is linear because every transaction contributes to the root; the tree improves verification membership, not root construction.

Common Pitfalls

  • Assuming hash chaining prevents all fraud: It detects casual modification, but consensus and economic rules determine whether rewritten history is accepted.

  • Using list.pop(0): It is (O(n)) per removal; use collections.deque for queue-like processing.

  • Ignoring duplicates and empty blocks: Validation should define whether duplicate transactions or empty data are permitted.

  • Forgetting the recursion or stack limit: Deep tree traversals should use an explicit stack or collections.deque.

  • Confusing a valid Merkle root with Merkle-proof verification: Membership still requires a correctly constructed sibling path.

  • Interview follow-ups: Expect questions about fork choice, transaction finality, orphan blocks, reorgs, state growth, and how Layer 2 systems derive security from the base layer.

29

How is a new block added to a blockchain?

Adding a block requires constructing its contents, validating transactions, calculating a Merkle root, and finding a valid proof-of-work nonce. Once accepted by the network’s consensus rules, the block is linked to the previous block through its hash.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Block-Addition Process

  1. Collect and validate data: In a cryptocurrency, this usually means validating transactions, signatures, balances, and consensus rules.

  2. Construct the candidate: Include the block index, timestamp, transaction data, Merkle root, and previous block’s hash.

  3. Calculate the Merkle root: Hash each transaction into a leaf, then hash pairs of leaves until one root remains.

  4. Perform proof of work: Change the nonce until the block hash satisfies the target difficulty.

  5. Broadcast and validate: Other nodes independently recompute the Merkle root and verify the proof of work, timestamp, previous hash, and transaction validity.

  6. Append or select the block: A node appends an accepted block, while competing networks may select the chain with the greatest accumulated proof of work.

Hash chaining provides tamper detection: changing historical data changes that block’s hash and every later hash. It does not make data physically immutable by itself; consensus makes rewriting history economically or computationally difficult.

Block Structure and Merkle Proofs

A typical block contains:

  • Index: The block’s position in the chain.

  • Timestamp: When the block was created.

  • Data: Transactions or other payload.

  • Previous hash: The preceding block’s hash, acting as a backward-pointing link.

  • Merkle root: A compact commitment to all transactions.

  • Nonce: The value varied during proof-of-work mining.

  • Hash: The SHA-256 digest of the block’s canonical contents.

A Merkle proof contains the sibling hashes needed to recompute the root for one transaction. The verifier hashes the transaction, combines it with each sibling in the recorded direction, and compares the final hash with the block’s Merkle root. This lets a lightweight client verify one transaction without receiving the entire block.

Bitcoin uses proof of work. Ethereum moved to proof of stake in 2022, so its consensus mechanism differs significantly from the proof-of-work search described here.

Proof of Work and Complexity

For a proof-of-work target containing d leading hexadecimal zeros, the expected number of hash attempts is approximately 16^d. The search is probabilistic: the best case is one attempt, the average case is approximately 16^d attempts, and the worst case is unbounded.

Let t be the number of transactions, s the serialized block size, d the hexadecimal difficulty, and n the number of blocks.

Operation Time complexity Auxiliary space Reason
Build Merkle root O(t) O(t) Each transaction hashed once; total hashes < 2t
Create Merkle proof O(t) O(t) Builds the tree; proof itself has O(log t) entries
Verify Merkle proof O(log t) O(1) Processes one sibling per tree level
Mine a block O(16^d × s) expected O(s + t) Repeats serialization and SHA-256 hashing
Validate a chain O(n × (s + t)) O(s + t) Validates every block and transaction commitment

All algorithms are iterative, so there is no recursion-stack cost. Auxiliary-space figures exclude the input chain and transaction list. Appending to a Python list is O(1) amortized because occasional list resizing is spread across operations, but mining dominates normal block addition.

Code Example

This is a minimal educational implementation, not production-ready blockchain software.

from __future__ import annotations

from dataclasses import dataclass
from datetime import datetime, timezone
import hashlib
import json

ZERO_HASH = "0" * 64


def sha256(data: bytes) -> bytes:
    """Return a SHA-256 digest."""
    return hashlib.sha256(data).digest()


def canonical_json(value: object) -> bytes:
    """Serialize data deterministically for hashing."""
    return json.dumps(
        value,
        sort_keys=True,
        separators=(",", ":"),
        ensure_ascii=False,
    ).encode("utf-8")


def merkle_root(transactions: list[str]) -> str:
    """Calculate a binary Merkle root, duplicating odd nodes."""
    if not transactions:
        return ZERO_HASH

    level = [sha256(transaction.encode("utf-8")) for transaction in transactions]

    while len(level) > 1:
        if len(level) % 2:
            level.append(level[-1])

        level = [
            sha256(level[index] + level[index + 1])
            for index in range(0, len(level), 2)
        ]

    return level[0].hex()


@dataclass(frozen=True, slots=True)
class Block:
    index: int
    timestamp: str
    data: list[str]
    previous_hash: str
    merkle_root: str
    nonce: int
    hash: str


def calculate_hash(block: Block) -> str:
    """Hash a block's contents without including its stored hash."""
    payload = {
        "index": block.index,
        "timestamp": block.timestamp,
        "data": block.data,
        "previous_hash": block.previous_hash,
        "merkle_root": block.merkle_root,
        "nonce": block.nonce,
    }
    return sha256(canonical_json(payload)).hex()


def mine_block(
    index: int,
    data: list[str],
    previous_hash: str,
    difficulty: int = 2,
) -> Block:
    """Search for a nonce whose block hash starts with target zeros."""
    target = "0" * difficulty
    nonce = 0

    while True:
        timestamp = datetime.now(timezone.utc).isoformat()
        root = merkle_root(data)

        candidate = Block(
            index=index,
            timestamp=timestamp,
            data=data,
            previous_hash=previous_hash,
            merkle_root=root,
            nonce=nonce,
            hash="",
        )
        digest = calculate_hash(candidate)

        if digest.startswith(target):
            return Block(
                index=candidate.index,
                timestamp=candidate.timestamp,
                data=candidate.data,
                previous_hash=candidate.previous_hash,
                merkle_root=candidate.merkle_root,
                nonce=candidate.nonce,
                hash=digest,
            )

        nonce += 1


def add_block(
    chain: list[Block],
    data: list[str],
    difficulty: int = 2,
) -> Block:
    """Mine and append a block to a non-empty chain."""
    if not chain:
        raise ValueError("The chain must contain a genesis block")

    new_block = mine_block(
        index=chain[-1].index + 1,
        data=data,
        previous_hash=chain[-1].hash,
        difficulty=difficulty,
    )
    chain.append(new_block)
    return new_block


def validate_chain(chain: list[Block], difficulty: int = 2) -> bool:
    """Check indexes, links, Merkle roots, hashes, and proof of work."""
    if not chain:
        return False

    target = "0" * difficulty

    for index, block in enumerate(chain):
        expected_previous = ZERO_HASH if index == 0 else chain[index - 1].hash
        if block.index != index or block.previous_hash != expected_previous:
            return False
        if block.merkle_root != merkle_root(block.data):
            return False
        if calculate_hash(block) != block.hash:
            return False
        if not block.hash.startswith(target):
            return False

    return True


if __name__ == "__main__":
    genesis = mine_block(0, [], ZERO_HASH)
    chain = [genesis]

    added = add_block(chain, ["alice -> bob: -1 coin"], difficulty=2)
    print(f"added block index: {added.index}")  # added block index: 1
    print(f"chain valid: {validate_chain(chain)}")  # chain valid: True

Common Pitfalls

  • Off-by-one errors: The genesis block normally has index 0; later blocks use previous.index + 1.

  • Incorrect hashing: Serialize fields deterministically before hashing.

  • Weak validation: Recompute the Merkle root, stored hash, previous hash, and proof of work rather than trusting supplied values.

  • Edge cases: Empty transaction data produces the all-zero Merkle root; with one transaction, the root is that transaction’s hash; duplicate transactions remain separate leaves. Negative transaction values require application-specific validation.

  • Security misconception: SHA-256 and hash chaining detect tampering but do not replace consensus, signatures, or peer-to-peer validation.

30

What factors should designers consider when building blockchain architecture?

Blockchain architecture combines a hash-linked sequence of blocks with distributed consensus, networking, state management, and cryptographic verification. Designers must balance integrity, finality, performance, availability, security, and operations.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Architecture Factors

  • Consensus and finality: Define canonical-history selection, fork handling, and when transactions become irreversible. Bitcoin uses proof of work (PoW) with probabilistic finality; Ethereum transitioned to proof of stake (PoS) in 2022.

  • Data and state: Choose block and transaction formats, state-transition rules, and storage retention. Full nodes maintain current state; pruned nodes discard some history, while archival nodes retain it at higher storage cost.

  • Networking: Specify peer discovery, gossip, block propagation, mempool management, retransmission, and denial-of-service controls.

  • Performance: Measure throughput, latency, block capacity, fees, batching, read scalability, and whether layer-2 or sharding designs are appropriate.

  • Security: Use digital signatures, secure key management, authenticated communications where applicable, and consensus-resistant validation. Hashing provides tamper evidence, not authorization.

  • Operations: Plan monitoring, node upgrades, checkpoints, chain reorganizations, backups, and historical-data retention.

Integrity and Consensus

Conceptually, a blockchain is a linked list of blocks whose links are cryptographic hash pointers. An educational block normally contains index, timestamp, data, previous_hash, nonce, and hash. Changing an earlier block changes its hash and every later previous_hash, providing tamper evidence rather than automatic immutability; consensus power determines which conflicting history is accepted.

A Merkle tree hashes transaction leaves pairwise until it produces a root. A Merkle proof supplies sibling hashes between a leaf and a trusted root, allowing inclusion verification in O(log n) hash operations. Bitcoin uses double SHA-256 for its transaction Merkle tree and block hashing.

For PoW, miners search for a nonce whose canonical block digest satisfies the target:

SHA256(canonical block contents || nonce)

If d denotes required leading zero bits, the expected number of attempts is 2^d. A minimal search proceeds by constructing a candidate, hashing it, testing the target, and incrementing the nonce until it passes.

Complexity

Let n be the transaction count, b the largest serialized block size, d the PoW difficulty in bits, and S the total serialized chain size.

Operation Best Average/expected Worst Space
Hash one candidate O(b) O(b) O(b) O(b) serialization; input excluded
Mine a block O(b) O(b·2^d) Unbounded O(b); input excluded
Build a Merkle tree O(n) O(n) O(n) O(n) including output; input excluded
Produce or verify a proof O(log n) O(log n) O(log n) O(log n) proof; O(1) verification auxiliary space
Validate a chain O(S) O(S) O(S) O(b) auxiliary; O(S) when input is counted

These bounds assume fixed-size transaction hashes. The algorithms are iterative, so recursion-stack space is O(1).

Code Example

This educational implementation demonstrates hash chaining and PoW validation; it is not production-ready.

from dataclasses import dataclass
from datetime import datetime, timezone
import hashlib
import json

ZERO_HASH = "0" * 64


@dataclass(frozen=True, slots=True)
class Block:
    index: int
    timestamp: str
    data: str
    previous_hash: str
    nonce: int
    hash: str


def calculate_hash(
    index: int,
    timestamp: str,
    data: str,
    previous_hash: str,
    nonce: int,
) -> str:
    """Hash a block's canonical serialized fields."""
    contents = {
        "index": index,
        "timestamp": timestamp,
        "data": data,
        "previous_hash": previous_hash,
        "nonce": nonce,
    }
    encoded = json.dumps(
        contents,
        sort_keys=True,
        separators=(",", ":"),
        ensure_ascii=False,
    ).encode("utf-8")
    return hashlib.sha256(encoded).hexdigest()


def meets_difficulty(digest: str, difficulty_bits: int) -> bool:
    """Return whether the digest has the required leading zero bits."""
    if not 1 <= difficulty_bits <= 256:
        raise ValueError("difficulty_bits must be between 1 and 256")
    target = 1 << (256 - difficulty_bits)
    return int(digest, 16) < target


def create_genesis_block() -> Block:
    """Create the first block in an educational chain."""
    timestamp = datetime.now(timezone.utc).isoformat()
    block_hash = calculate_hash(0, timestamp, "", ZERO_HASH, 0)
    return Block(0, timestamp, "", ZERO_HASH, 0, block_hash)


def mine_block(
    previous_block: Block,
    data: str,
    difficulty_bits: int = 2,
) -> Block:
    """Search for a nonce satisfying the PoW target."""
    if not 1 <= difficulty_bits <= 256:
        raise ValueError("difficulty_bits must be between 1 and 256")

    index = previous_block.index + 1
    timestamp = datetime.now(timezone.utc).isoformat()
    nonce = 0

    while True:
        candidate_hash = calculate_hash(
            index, timestamp, data, previous_block.hash, nonce
        )
        if meets_difficulty(candidate_hash, difficulty_bits):
            return Block(
                index,
                timestamp,
                data,
                previous_block.hash,
                nonce,
                candidate_hash,
            )
        nonce += 1


def validate_chain(chain: list[Block], difficulty_bits: int = 2) -> bool:
    """Validate indexes, hash links, stored hashes, and non-genesis PoW."""
    if not 1 <= difficulty_bits <= 256:
        raise ValueError("difficulty_bits must be between 1 and 256")
    if not chain:
        return False

    for position, block in enumerate(chain):
        if block.index != position:
            return False

        expected_previous = ZERO_HASH if position == 0 else chain[position - 1].hash
        if block.previous_hash != expected_previous:
            return False

        calculated_hash = calculate_hash(
            block.index,
            block.timestamp,
            block.data,
            block.previous_hash,
            block.nonce,
        )
        if block.hash != calculated_hash:
            return False

        if position > 0 and not meets_difficulty(block.hash, difficulty_bits):
            return False

    return True


if __name__ == "__main__":
    chain = [create_genesis_block()]
    chain.append(mine_block(chain[-1], "hello blockchain", difficulty_bits=2))
    print(validate_chain(chain, difficulty_bits=2))  # Expected output: True

Common Pitfalls

  • Empty or short chains: This example rejects an empty chain but accepts a valid genesis-only chain. Sequential indexes and links reject disconnected or cyclic histories.

  • Difficulty errors: Negative or greater-than-256-bit difficulties raise ValueError; genesis is exempt from the PoW target.

  • Ambiguous serialization: Hashing inconsistently ordered or encoded fields can produce incompatible hashes.

  • Duplicate transactions: Hash chaining does not reject duplicates; transaction-level validation must apply protocol rules.

  • Weak validation: Checking only previous_hash is insufficient; every stored hash must be recomputed.

  • Production misuse: Real systems additionally require signatures, transaction rules, persistent storage, peer discovery, adversarial protection, and consensus beyond this toy PoW check.

31

What are transactions in a blockchain?

A blockchain transaction is a signed instruction that requests a change to the ledger, such as transferring value or calling a smart contract. Valid transactions are grouped into blocks, cryptographically linked to previous blocks, and independently verified by participating nodes.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Transaction Models

Different blockchains organize transactions differently:

Model How transactions work Example
UTXO Inputs consume previous unspent outputs; outputs create new spendable outputs. Bitcoin
Account-based A transaction targets an account or contract and updates its balance, nonce, or storage. Ethereum

A typical transaction includes a sender, recipient, amount, authorization data, and sometimes a nonce, fees, or contract parameters. A digital signature demonstrates authorization without revealing the sender’s private key. The example below uses a placeholder signature and does not implement real cryptographic verification.

Transactions, Merkle Trees, and Blocks

A block behaves like a linked-list node. It contains an index, timestamp, transactions, Merkle root, previous-block hash, nonce, and block hash.

Transactions are hashed into leaves of a Merkle tree:

  1. Hash each transaction to produce a transaction ID.

  2. Pair adjacent hashes and hash each pair.

  3. Duplicate an odd hash at each level when necessary.

  4. Continue until one Merkle root remains.

The root is stored in the block header. A Merkle proof can then prove that one transaction belongs to the block using only about O(log t) sibling hashes, where t is the number of transactions.

If a transaction changes, its hash changes, causing the Merkle root and block hash to change. Every later block references that block’s hash, so the alteration invalidates the remaining chain unless the attacker also rewrites and re-mines all affected blocks.

Proof of Work and Validation

In proof of work, miners search for a nonce satisfying a target difficulty. For example, a target requiring two leading hexadecimal zeros expects roughly 16² = 256 attempts. Finding a valid hash demonstrates computational effort; it does not validate the transactions themselves.

Bitcoin uses proof of work. Ethereum moved to proof of stake through the Merge in September 2022. Proof of stake selects validators using staked cryptocurrency rather than searching for a nonce.

Complexity

Operation Time Space Reason
Hash one transaction O(1) for bounded-size fields O(1) auxiliary Processes one fixed-size record
Build a Merkle root O(t) O(t) Processes fewer than 2t tree nodes
Generate a Merkle proof O(log t) O(log t) Follows one root-to-leaf path
Validate a chain O(B + T) O(t_max) auxiliary B blocks and T total transactions are checked
Proof-of-work mining Best O(t); expected O(t + 2^d); worst unbounded O(t) auxiliary Merkle construction is linear; nonce search is probabilistic

The validation space excludes the already-stored chain input. If input storage is included, a chain containing B blocks and T transactions requires O(B + T) space. The iterative Merkle implementation has no recursion-stack cost.

Code Example

This educational implementation demonstrates transaction hashing, Merkle roots, proof-of-work mining, and chain validation. It is not production-ready because it lacks signatures, persistence, consensus, networking, and robust transaction validation.

from dataclasses import dataclass
from hashlib import sha256
import json


@dataclass(frozen=True)
class Transaction:
    sender: str
    recipient: str
    amount: int
    signature: str

    def to_bytes(self) -> bytes:
        data = {
            "sender": self.sender,
            "recipient": self.recipient,
            "amount": self.amount,
            "signature": self.signature,
        }
        return json.dumps(data, sort_keys=True, separators=(",", ":")).encode()

    @property
    def transaction_id(self) -> str:
        return sha256(self.to_bytes()).hexdigest()


@dataclass(frozen=True)
class Block:
    index: int
    timestamp: int
    transactions: tuple[Transaction, ...]
    previous_hash: str
    merkle_root: str
    nonce: int
    hash: str

    def header_bytes(self) -> bytes:
        data = {
            "index": self.index,
            "timestamp": self.timestamp,
            "previous_hash": self.previous_hash,
            "merkle_root": self.merkle_root,
            "nonce": self.nonce,
        }
        return json.dumps(data, sort_keys=True, separators=(",", ":")).encode()


def calculate_merkle_root(transactions: tuple[Transaction, ...]) -> str:
    """Return the Merkle root for a nonempty transaction tuple."""
    if not transactions:
        raise ValueError("A block must contain at least one transaction")

    level = [bytes.fromhex(tx.transaction_id) for tx in transactions]
    while len(level) > 1:
        if len(level) % 2:
            level.append(level[-1])
        level = [
            sha256(b"\x00" + left + b"\x01" + right).digest()
            for left, right in zip(level[::2], level[1::2])
        ]
    return level[0].hex()


def mine_block(
    index: int,
    timestamp: int,
    transactions: tuple[Transaction, ...],
    previous_hash: str,
    difficulty: int = 2,
) -> Block:
    """Find a proof-of-work nonce for a block."""
    merkle_root = calculate_merkle_root(transactions)
    nonce = 0

    while True:
        candidate = Block(
            index, timestamp, transactions, previous_hash,
            merkle_root, nonce, ""
        )
        candidate_hash = sha256(candidate.header_bytes()).hexdigest()
        if candidate_hash.startswith("0" * difficulty):
            return Block(
                index, timestamp, transactions, previous_hash,
                merkle_root, nonce, candidate_hash
            )
        nonce += 1


def validate_chain(chain: list[Block], difficulty: int = 2) -> bool:
    """Validate hashes, links, Merkle roots, transactions, and proof of work."""
    if not chain:
        return False

    for position, block in enumerate(chain):
        expected_previous = "0" * 64 if position == 0 else chain[position - 1].hash
        if block.index != position or block.previous_hash != expected_previous:
            return False
        if any(
            tx.amount < 0 or not tx.sender or not tx.recipient or not tx.signature
            for tx in block.transactions
        ):
            return False
        if block.merkle_root != calculate_merkle_root(block.transactions):
            return False

        expected_hash = sha256(block.header_bytes()).hexdigest()
        if block.hash != expected_hash:
            return False
        if not block.hash.startswith("0" * difficulty):
            return False

    return True


transactions = (
    Transaction("alice", "bob", 10, "demo-signature"),
    Transaction("bob", "carol", 5, "demo-signature"),
)
genesis = mine_block(0, 1, transactions, "0" * 64)
chain = [genesis]

print(validate_chain(chain, difficulty=2))  # True

Common Pitfalls

  • A valid hash proves block integrity, not transaction authenticity; real signature verification is separate.

  • Hashing individual transactions is not enough for membership proofs; use the Merkle tree.

  • Validation must check previous hashes, transaction content, Merkle roots, and proof-of-work difficulty.

  • Empty transaction sets require an explicitly defined empty-root convention.

  • Duplicate transactions should be handled by application-specific rules, such as replay protection.

  • Interview follow-ups commonly ask about UTXO versus account models, Merkle-proof efficiency, transaction malleability, confirmations, and chain reorganizations.

32

How does the UTXO model differ from an account balance model?

The UTXO (Unspent Transaction Output) model tracks individual transaction outputs that have not been spent, while an account/balance model directly records account state, including balances. Spending under UTXO consumes complete outputs and creates new outputs; spending under the account model transfers value by updating account balances.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

  • UTXO model: An output is identified by a transaction_id and output_index. A transaction consumes existing outputs and creates new outputs.

  • Change: Because a complete UTXO must be consumed, a payment commonly creates a new output returning the unused amount to the sender.

  • Account model: Global state maps account identifiers to balances and usually nonces. It may also include contract code and storage.

  • Example: If Alice owns a 10-coin UTXO and pays Bob 7 coins, the transaction consumes Alice’s 10-coin output and creates a 7-coin output for Bob plus a 3-coin change output for Alice. In an account model, Alice’s balance becomes 3 and Bob’s becomes 7.

UTXO transactions consuming independent outputs can be processed in parallel. Conflicting account-state transitions are serialized by consensus; nonce-based systems such as Ethereum also order transactions by the sender’s account nonce.

Model Comparison

Aspect UTXO model Account/balance model
Stored state Unspent transaction outputs Balances, nonces, and possibly code or storage
Spending Consumes whole outputs and creates new outputs Decrements one balance and increments another
Recipient value Sum of outputs controlled by the recipient Value read from account state
State growth Based on the number and size of unspent outputs Based on accounts and associated state or storage
Historical data Outputs become spent, while transaction history remains recorded Balances are updated while transaction history remains recorded
Example Bitcoin Ethereum

Blockchain Data Structures

A blockchain behaves like a linked list of blocks, with each block containing the previous block’s hash as a backward hash pointer.

  • Block structure: A typical educational block contains an index, timestamp, transaction data, previous hash, nonce, and current hash.

  • Cryptographic hashing: Block and transaction commitments commonly use SHA-256, available through Python’s hashlib.sha256.

  • Merkle tree: Transaction hashes are leaves, internal nodes combine child hashes, and the root commits to all transactions in a block.

  • Merkle proof: A sibling-hash path proves that a transaction belongs to the committed root without requiring every transaction.

  • Immutability: Changing historical data changes that block’s hash and all descendant hashes. This is tamper-evident, while final immutability still depends on consensus and confirmations.

  • Proof of work: A miner searches for a block hash meeting a target. This is a search problem, not a direct calculation.

Bitcoin uses UTXOs and proof of work. Ethereum uses an account-based state model and moved to proof of stake during the 2022 Merge.

Complexity

These are implementation-dependent rather than defining properties of either model:

  • UTXO membership lookup: With an in-memory hash set, best and average time are O(1) and worst-case time is O(n) under severe collisions. Space is O(u) for u unspent outputs, excluding the rest of the blockchain.

  • Account lookup: With a hash-based account map, best and average time are O(1) and worst-case time is O(n). Space is O(a) for a accounts and their associated state, excluding historical transactions. Persistent trie-based systems have different lookup costs.

  • Merkle tree and proof: Building a balanced tree for t transactions takes O(t) time and O(t) space, including tree storage but excluding the original transactions. Verification takes O(log t) time and O(log t) proof space; an iterative verifier uses O(1) stack space, while a recursive verifier uses O(log t).

  • Chain validation: Validating n fixed-size blocks takes O(n) time in the best, average, and worst cases. Auxiliary space is O(1), excluding the O(n) supplied chain.

  • Proof-of-work search: For d required leading hexadecimal zeros, the best case is O(1), expected time is O(16^d), and the probabilistic worst case has no finite bound. Working space is O(1).

Common Pitfalls

  • Do not describe every account model as nonce-based; nonces are common but not universal.

  • Do not equate account state with balances alone; contract code and storage may also be substantial.

  • A UTXO lookup’s complexity depends on the persistence and indexing implementation, not merely the model.

  • Keep consensus, transaction ordering, fees, and finality distinct from the basic state representation.

33

What determines transaction fees in a blockchain?

Transaction fees are determined by a fee market where users bid for limited block space, and block producers prioritize transactions with higher effective fees per unit of space or computation; the final fee may also include a protocol-set base fee, a priority tip, and burn mechanisms.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Fee Determination Mechanisms

  • Bitcoin-style chains: Senders specify a fee rate (satoshis per virtual byte). The fee equals fee rate × transaction virtual size. Miners prioritize higher fee rates, subject to dependencies and policy.

  • Ethereum-style chains (EIP-1559): The protocol sets a base fee (burned) that adjusts with block fullness. Users set a max fee per gas and a max priority fee (tip to validator). The effective fee per gas is min(max_fee, base_fee + max_priority). The total fee is gas_used × effective_fee.

  • Permissioned or fixed-fee chains: A network operator may set a constant fee via policy rather than an open market.

Fee Components

  • Base fee: Algorithmic, burned, responds to network demand.

  • Priority fee (tip): Paid to block producer for inclusion priority.

  • Fee rate / gas price: Bid per unit of block space (vbyte or gas).

  • Transaction size / gas used: Determines total fee from the rate.

Blockchain Data Structure

A blockchain is a linked list of blocks; each block contains an index, timestamp, transactions, previous hash, nonce, and hash. The hash commits to the block contents and the previous block’s hash, forming a hash pointer.

  • Merkle tree: Transactions are hashed pairwise to a single Merkle root stored in the block header. A Merkle proof (sibling hashes) proves a transaction’s inclusion without downloading the full block.

  • Immutability: Changing a transaction’s fee alters its hash, the Merkle root, the block hash, and all subsequent block hashes, requiring re-mining (proof-of-work) or re-validation (proof-of-stake).

  • Consensus: Bitcoin uses proof-of-work (nonce search for a hash below target). Ethereum uses proof-of-stake (validators propose and attest blocks); fee ordering is still competitive but validators replace miners.

Complexity

Operation Best Average Worst Space
Calculate fee for one transaction O(1) O(1) O(1) O(1)
Order n transactions by fee rate O(n log n) O(n log n) O(n log n) O(n)
Verify a Merkle proof for a transaction O(log n) O(log n) O(log n) O(log n)

Space excludes the stored blockchain; no recursion stack used.

Common Pitfalls

  • A fee bid does not guarantee inclusion; validity, dependencies, and producer policy matter.

  • The base fee is burned, not paid to validators; only the tip goes to the block producer.

  • Fee estimation requires predicting base fee and competition; wallets often use recent block data.

  • Changing a historical fee would break the hash chain, making tampering evident.

  • Interviewers may ask how fee priority affects transaction ordering, why EIP-1559 improves UX, or how Merkle proofs enable light clients.

34

What is the lifecycle of a blockchain transaction?

A blockchain transaction lifecycle moves a user-signed message from local creation through network propagation, validator selection, block inclusion, and finally to a state where the network considers it irreversible. Each stage adds cryptographic guarantees that the transaction is authentic, ordered, and tamper-evident.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Transaction Creation

  • Signing: The sender uses their private key to sign a message containing recipient address, value, nonce, gas limit/fee, and optional data. The signature proves authorization without revealing the private key.

  • Serialization: The signed transaction is encoded (e.g., RLP in Ethereum, custom binary in Bitcoin) into a byte string that can be hashed and transmitted.

  • Hashing: The transaction hash (txid) is computed — SHA-256 double-hash in Bitcoin, Keccak-256 of RLP in Ethereum. This identifier is used for tracking and Merkle tree construction.

Broadcast and Mempool

  • Gossip propagation: The sender pushes the transaction to connected peers; each peer validates basic rules (signature, nonce sequence, sufficient balance, fee above minimum) before relaying further.

  • Mempool entry: Valid transactions enter each node’s memory pool (mempool), a priority queue ordered by fee rate (sat/vB in Bitcoin, gas price in Ethereum). Transactions wait here until a block producer selects them.

  • Replacement and eviction: A sender can replace a stuck transaction by resubmitting with a higher fee (RBF in Bitcoin, same nonce with higher gas in Ethereum). Nodes evict low-fee transactions when memory limits are reached.

Block Inclusion and Consensus

  • Block building: A miner (PoW) or validator (PoS) selects transactions from the mempool, orders them, and constructs a candidate block. The block header contains the Merkle root of all transaction hashes, linking each transaction into the block’s hash.

  • Consensus participation:

  • Proof of Work (Bitcoin): Miners repeatedly hash the block header with different nonces until the hash meets the difficulty target. The first valid block is broadcast.

  • Proof of Stake (Ethereum post-2022): A randomly chosen validator proposes a block; a committee of validators attests to its validity. Finality requires two epochs (≈12.8 minutes) of justified checkpoints.

  • Block propagation: The winning block spreads through the network. Nodes verify the block header, all transactions, and the state transition before appending it to their local chain.

Confirmation and Finality

  • Confirmations: Each subsequent block added on top of the block containing the transaction is one confirmation. More confirmations exponentially reduce reorganization probability.

  • Finality definitions:

  • Probabilistic (Bitcoin): After 6 confirmations (≈1 hour), reorganization is computationally infeasible under honest majority.

  • Economic (Ethereum): After two epochs of attestations, the block is “finalized” — reverting it would require slashing ≥1/3 of all staked ETH.

  • State update: Once finalized, the transaction’s effects (balance changes, contract storage updates, event logs) are part of the canonical state and can be relied upon by applications.

Proof of Work vs Proof of Stake Comparison

Aspect Proof of Work (Bitcoin) Proof of Stake (Ethereum)
Block proposer selection Computational puzzle (hashing) Random selection weighted by stake
Finality type Probabilistic (depth-based) Economic (checkpoint-based)
Typical confirmation time 10 min per block 12 s per slot, ~15 min for finality
Energy cost High (ASIC mining) Low (validator software)
Reorg resistance Cumulative work Slashing penalties on equivocation

Common Pitfalls

  • Assuming mempool inclusion = confirmation: A transaction in the mempool can be dropped, replaced, or never mined if fees are too low.

  • Counting confirmations incorrectly: In Ethereum, a transaction in a “justified” but not “finalized” block can still be reverted by a chain reorganization; only finalized blocks provide economic finality.

  • Ignoring nonce gaps: Submitting a transaction with nonce n+1 while n is pending stalls both; the mempool will not accept out-of-order nonces.

  • Fee estimation errors: Using a fixed fee during congestion causes transactions to stall; production systems use fee oracles (EIP-1559 base fee + priority fee in Ethereum, fee rate estimators in Bitcoin).

  • Double-spend risk on low confirmations: Accepting 0-conf or 1-conf transactions for high-value transfers is unsafe; wait for the confirmation threshold appropriate to the chain and value.

35

What is a mempool in blockchain networks?

A mempool is a node’s collection of transactions that have been received and passed local policy checks but have not yet been included in a confirmed block. It acts as a waiting area from which miners or block proposers select transactions for a candidate block.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. A transaction reaches a node and undergoes local validation, such as checking its format, signature, fee, size, balance or nonce, and conflicts with existing transactions.

  2. The node broadcasts the transaction to neighboring nodes, which apply their own validation and transaction-pooling policies.

  3. Transactions are organized according to node-specific priority rules, commonly considering fees, transaction size, age, dependencies, and conflicts.

  4. A block producer selects transactions and constructs a candidate block.

  5. When the transaction is included in an accepted block, the node normally removes it from its mempool. A reorganization can cause some transactions to return to the pool.

There is no single global mempool. Different nodes may accept, reject, prioritize, or evict different transactions.

  • Bitcoin: The mempool contains unconfirmed transactions competing for limited block space. Miners commonly prioritize transactions by fee rate, while considering package dependencies.

  • Ethereum: Clients maintain pending and queued or future transaction pools, with terminology and policies varying by client. Builders obtain transactions through Ethereum’s block-building infrastructure. Ethereum moved from proof of work to proof of stake in 2022.

  • Remaining in a mempool does not guarantee inclusion in the next block.

Blockchain and Block Structure

A blockchain is a linked sequence of blocks in which each block stores the hash of the preceding block. A typical Bitcoin-style block contains an index, timestamp, transaction data, previous block’s hash, a Merkle root, a nonce, and the block’s own hash.

The previous hash acts as a hash pointer. Changing an earlier block changes its hash and invalidates subsequent links unless an attacker rewrites the later blocks and obtains acceptance of the altered chain.

Bitcoin uses SHA-256-based hashing; Python’s hashlib.sha256 can compute it, although Bitcoin block headers use double SHA-256. Ethereum instead uses Keccak-256 and no longer performs proof-of-work mining.

Proof of work is a search problem: a miner repeatedly changes a candidate header, normally including its nonce, until its hash satisfies the difficulty target. Bitcoin adjusts difficulty periodically to target approximately one block per ten minutes.

Merkle Trees and Immutability

A Merkle tree organizes transaction hashes into a binary tree:

  • The leaves represent transaction hashes.

  • Each internal node hashes its two children.

  • The root summarizes all transactions in the block.

  • A Merkle proof demonstrates transaction membership using O(log t) hashes, where t is the number of transactions.

Ethereum uses a more general Merkle-Patricia trie for transactions and account state. Hash chaining provides tamper evidence, but absolute immutability also depends on consensus, replicated history, validation rules, and the cost of convincing the network to accept a rewritten chain.

Complexity

These are representative complexities; exact behavior depends on the node implementation.

Operation Best Average Worst Space Reason
Add transaction to a hash-indexed mempool O(1) O(1) amortized O(m) O(m) stored plus O(1) auxiliary, excluding transaction payload Hash insertion is normally constant-time, but resizing or rehashing can copy m entries
Look up a transaction by ID O(1) O(1) O(m) O(1) auxiliary, excluding the returned transaction A hash index is normally constant-time; hash collisions cause worst-case linear behavior
Hash a B-byte payload O(B) O(B) O(B) O(B) temporary space, excluding the input SHA-256 processes the input linearly
Search for proof of work requiring d leading hexadecimal zeros O(B) O(B × 16^d) expected O(B × N) for N candidates O(B) temporary space, excluding the candidate set Each attempt hashes B bytes, and approximately 16^d attempts are needed on average
Build a Merkle tree for t transactions O(t) O(t) O(t) O(t) for the tree, excluding transaction payload A binary tree contains a linear number of nodes
Produce one proof from a stored Merkle tree O(log t) O(log t) O(log t) O(log t) auxiliary, excluding the tree The proof follows one root-to-leaf path

Here, m is mempool size, B is payload size, d is the required leading-zero count, N is the candidate-header space searched, and t is the number of transactions.

Common Pitfalls

  • Assuming a global mempool: Each node maintains its own view and policies.

  • Assuming guaranteed inclusion: Transactions can remain pending, be evicted, or be replaced.

  • Ignoring conflicts: Duplicate, conflicting, and fee-bump transactions require explicit policies.

  • Confusing the mempool with the UTXO set: The mempool stores pending transactions; the UTXO set represents unspent outputs.

  • Ignoring reorgs: A transaction removed after confirmation may return to the mempool if the chain reorganizes.

  • Common follow-up questions: Interviewers often ask about double-spending prevention, transaction ordering, dependency handling, fee estimation, and the transaction lifecycle from propagation to confirmation.

36

What is a 51% attack in blockchain?

A 51% attack is an attack on a proof-of-work blockchain in which one entity or coalition controls more than half of the network’s total hash rate. This majority lets the attacker dominate block production and potentially reorganize blockchain history, censor transactions, reverse its own payments, or double-spend coins.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Mechanics

Mining probability is proportional to hash rate, so an attacker controlling 51% of the total hash rate produces approximately 51% of the blocks over many rounds. The attacker can build a competing chain, withhold selected transactions, and attempt to make its fork accumulate more proof-of-work than the public chain.

A majority attacker still cannot:

  • Spend another user’s coins without their private key.

  • Create valid signatures or bypass transaction validation.

  • Make nodes accept invalid blocks merely because the attacker mined them.

  • Alter old blocks without recomputing the affected proof-of-work and downstream hash links.

The danger depends on the attacker’s cost, persistence, transaction-confirmation policy, and the distribution of mining power. A temporary hash-rate advantage is less dangerous than a sustained majority.

Blocks, Hashes, and Merkle Proofs

Conceptually, a blockchain is a linked list of blocks in which each block contains a hash pointer to its predecessor. A generic block structure contains:

  • Index or height: Its position in the chain.

  • Timestamp: When the block was created.

  • Data or transactions: The block’s payload.

  • Previous hash: The hash of the preceding block header.

  • Merkle root: A commitment to the block’s transactions.

  • Nonce: A value varied while searching for valid proof-of-work.

  • Current hash: The digest derived from the block header.

The exact fields vary by protocol. SHA-256 is a standard choice and is available in Python through hashlib.sha256; Bitcoin uses double SHA-256 both for block headers and for its Merkle tree.

Changing an old block changes its hash and therefore every descendant’s hash linkage. This creates hash-chain immutability: the history is computationally expensive to alter, not absolutely immutable.

Transactions are arranged in a Merkle tree, where leaves contain transaction hashes and internal nodes hash their children. A Merkle proof supplies the sibling hashes needed to prove that a transaction belongs to a block in O(log n) time and space, assuming fixed-size hashes. The proof establishes inclusion, not the validity of the surrounding chain.

Proof-of-work is a search problem: a miner varies the nonce until a block header satisfies the target difficulty. If one attempt succeeds with probability 2^-d, the expected number of attempts is O(2^d).

Double-Spend Scenario

  1. The attacker pays a merchant, and the transaction enters block 100.

  2. The merchant observes the payment and applies its confirmation policy.

  3. The attacker privately mines a competing fork from block 99, including a conflicting transaction that spends the same coins.

  4. Because the attacker holds most of the hash rate, its fork accumulates work faster than the public chain.

  5. Nodes select the chain with the greatest cumulative proof-of-work, potentially removing the merchant’s payment from the canonical chain.

Additional confirmations reduce the risk of an ordinary reorganization but cannot eliminate the risk from a sustained majority attacker.

Proof of Work Versus Proof of Stake

Bitcoin uses proof of work, so its 51% threat model is expressed in hash rate. Ethereum transitioned to proof of stake at the Merge in September 2022. In Ethereum’s proof-of-stake system:

  • Roughly one-third of the total effective stake can prevent finality by withholding attestations.

  • Two-thirds is generally required to finalize a conflicting or malicious checkpoint.

  • Consequently, 51% stake does not give an attacker the same unilateral control as 51% hash rate.

  • Slashing penalizes provable protocol violations, while social coordination remains relevant when validators coordinate censorship or other disruptive behavior.

Complexity Perspective

For n fixed-size block headers, a b-byte header, a Merkle tree with n leaves, and proof-of-work success probability 2^-d:

Operation Time complexity Space complexity Reason
Validate headers and hash links O(n) best, average, and worst O(1) auxiliary; supplied chain excluded Each header and link is checked once
Compute a SHA-256 digest O(b) best, average, and worst O(1) auxiliary if bytes are supplied; otherwise O(b) SHA-256 processes the header bytes
Verify a Merkle inclusion proof O(log n) best, average, and worst O(log n) for proof storage One sibling hash is processed per tree level
Search for proof-of-work Best O(1); expected O(2^d); no finite worst-case bound O(1) auxiliary; header excluded Random attempts may take arbitrarily long

These are computational bounds, not estimates of the financial or operational cost of acquiring majority hash power. The operations shown are iterative and require no recursion stack.

Common Pitfalls

  • A 51% hash-rate majority does not mean the attacker owns 51% of the blocks or coins.

  • The attack does not reveal private keys or permit unauthorized spending.

  • Nodes continue to reject cryptographically or transactionally invalid blocks.

  • Deep reorganizations remain possible for a sufficiently sustained attacker, although they require substantial additional work.

  • Bitcoin’s hash-rate thresholds must not be transferred directly to proof-of-stake systems.

  • Interviewers commonly ask about confirmation depth, mining-pool concentration, exchange policies, finality, and the differences between proof of work and proof of stake.

37

How does blockchain consensus prevent double-spending?

Consensus prevents double-spending by making network participants agree on one canonical transaction history while transaction rules reject invalid or conflicting state changes.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Consensus Prevents It

A double-spend attempts to use the same funds or state in two conflicting transactions.

  • Transaction validation: Nodes verify signatures, amounts, account or output state, and authorization before accepting a transaction.

  • UTXO uniqueness: In Bitcoin, each unspent transaction output can fund only one later transaction; reusing an already-spent output is invalid.

  • Account state: In Ethereum, each account has a nonce that orders its transactions. Only one canonical transaction is executed for a given nonce.

  • Canonical history: Consensus orders valid blocks and selects one chain. Conflicting transactions cannot both enter that canonical history, even if both initially appeared valid.

  • Finality: Bitcoin’s proof of work gives probabilistic finality that strengthens with confirmations. Ethereum moved to proof of stake in 2022; validators attest to blocks, and finalized checkpoints provide protocol finality.

Hash chaining detects tampering, but transaction validity rules and distributed consensus are required to prevent double-spending.

Data Structures

A minimal block contains:

  • index: Position in the chain.

  • timestamp: Creation time.

  • data: Transactions.

  • previous_hash: Hash of the preceding block.

  • nonce: Value searched during proof-of-work mining.

  • hash: Digest of the block representation.

SHA-256 through hashlib produces a fixed 256-bit digest. Changing an earlier block changes its hash and every subsequent previous_hash.

Blocks commonly commit to transactions using a Merkle tree. Given a trusted block-level Merkle root, a Merkle proof verifies one transaction’s inclusion using sibling hashes along an O(log n) path.

Proof of Work as a Search

In the toy scheme below, difficulty d requires d leading hexadecimal zeros. Assuming uniformly distributed hashes, each attempt succeeds with probability 1 / 16^d, giving 16^d expected attempts. Mining makes block creation costly; validity rules and consensus determine which spends belong to the canonical history.

Complexity

Input blocks, transaction lists, and Merkle proofs are excluded from auxiliary-space measurements. All algorithms are iterative, so the recursion stack is O(1).

Operation Time Auxiliary space Reason
Mine with difficulty d Best O(B); expected/average O(16^d × B); worst unbounded O(B) B is the serialized candidate size, including transactions. There is no finite worst-case attempt bound.
Validate a chain Best/average O(S); worst O(S + N × A) O(A) S is chain size, N transaction count, and A account count. Dictionary collisions cause the worst case.
Account lookup or update O(1) average; O(A) worst O(A) The account map contains A entries.
Build a Merkle tree O(n) O(n) Every leaf and internal node is hashed.
Verify a Merkle proof O(log n) O(1) One sibling is processed per level; the supplied proof is input.

Code Example

This educational blockchain demonstrates hash chaining, proof-of-work searching, account nonces, balance checks, and chain validation. It omits signatures, networking, and distributed consensus, so it is not production-ready.

from dataclasses import asdict, dataclass
import hashlib
import json
import time


GENESIS_HASH = "0" * 64
GENESIS_BALANCES = {"alice": 100, "bob": 0}


@dataclass(frozen=True)
class Transaction:
    sender: str
    recipient: str
    amount: int
    nonce: int


@dataclass(frozen=True)
class Block:
    index: int
    timestamp: int
    data: tuple[Transaction, ...]
    previous_hash: str
    nonce: int
    hash: str


def calculate_hash(
    index: int,
    timestamp: int,
    transactions: tuple[Transaction, ...],
    previous_hash: str,
    nonce: int,
) -> str:
    """Calculate a SHA-256 hash for a block and its transactions."""
    header = {
        "index": index,
        "timestamp": timestamp,
        "data": [asdict(transaction) for transaction in transactions],
        "previous_hash": previous_hash,
        "nonce": nonce,
    }
    encoded = json.dumps(
        header, sort_keys=True, separators=(",", ":")
    ).encode("utf-8")
    return hashlib.sha256(encoded).hexdigest()


def mine_block(
    index: int,
    transactions: tuple[Transaction, ...],
    previous_hash: str,
    difficulty: int = 2,
) -> Block:
    """Search for a nonce whose block hash satisfies the target."""
    if type(difficulty) is not int or difficulty < 0:
        raise ValueError("difficulty must be a non-negative integer")

    timestamp = int(time.time())
    target = "0" * difficulty
    nonce = 0

    while True:
        digest = calculate_hash(
            index, timestamp, transactions, previous_hash, nonce
        )
        if digest.startswith(target):
            return Block(
                index, timestamp, transactions, previous_hash, nonce, digest
            )
        nonce += 1


def validate_chain(chain: list[Block], difficulty: int = 2) -> bool:
    """Validate hashes, ordering, nonces, balances, and proof of work."""
    if not chain or type(difficulty) is not int or difficulty < 0:
        return False

    balances = dict(GENESIS_BALANCES)
    expected_nonces: dict[str, int] = {}
    target = "0" * difficulty

    for position, block in enumerate(chain):
        expected_previous = (
            GENESIS_HASH if position == 0 else chain[position - 1].hash
        )

        if type(block.index) is not int or block.index != position:
            return False
        if not isinstance(block.previous_hash, str):
            return False
        if block.previous_hash != expected_previous:
            return False
        if type(block.timestamp) is not int or type(block.nonce) is not int:
            return False
        if not isinstance(block.data, tuple):
            return False

        calculated_hash = calculate_hash(
            block.index,
            block.timestamp,
            block.data,
            block.previous_hash,
            block.nonce,
        )
        if block.hash != calculated_hash:
            return False
        if not block.hash.startswith(target):
            return False

        for transaction in block.data:
            if not isinstance(transaction, Transaction):
                return False
            if type(transaction.amount) is not int or transaction.amount <= 0:
                return False
            if not isinstance(transaction.sender, str) or not transaction.sender:
                return False
            if not isinstance(transaction.recipient, str) or not transaction.recipient:
                return False
            if type(transaction.nonce) is not int or transaction.nonce < 0:
                return False

            expected_nonce = expected_nonces.get(transaction.sender, 0)
            if transaction.nonce != expected_nonce:
                return False
            if balances.get(transaction.sender, 0) < transaction.amount:
                return False

            balances[transaction.sender] -= transaction.amount
            balances[transaction.recipient] = (
                balances.get(transaction.recipient, 0) + transaction.amount
            )
            expected_nonces[transaction.sender] = expected_nonce + 1

    return True


if __name__ == "__main__":
    first_block = mine_block(
        0,
        (Transaction("alice", "bob", 30, 0),),
        GENESIS_HASH,
    )
    second_block = mine_block(
        1,
        (Transaction("bob", "carol", 10, 0),),
        first_block.hash,
    )
    double_spend_block = mine_block(
        0,
        (
            Transaction("alice", "bob", 80, 0),
            Transaction("alice", "carol", 80, 1),
        ),
        GENESIS_HASH,
    )

    print(validate_chain([first_block, second_block]))  # True
    print(validate_chain([double_spend_block]))  # False

Common Pitfalls

  • A conflicting transaction may remain pending; it is excluded from the canonical history rather than necessarily becoming invalid immediately.

  • Off-by-one errors in block indexes or previous_hash links break chain validation.

  • Other languages need overflow-safe balance and amount arithmetic.

  • Do not mutate the input chain, and track each consumed UTXO or account nonce exactly once.

  • Empty chains are invalid; a one-block chain can be valid; duplicate nonces, non-positive amounts, and insufficient-balance spends are rejected.

  • A common follow-up asks how proof-of-work finality differs from proof-of-stake finality.

38

What security vulnerabilities threaten blockchain systems?

Blockchain security threats include attacks on consensus, cryptography, network infrastructure, smart contracts, bridges, wallets, and key management. Hash chaining and Merkle trees make unauthorized changes detectable, but they do not prevent attacks that compromise keys, nodes, consensus power, or application logic.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Common Threat Categories

  • Consensus and finality attacks: An attacker controlling a majority of Bitcoin’s proof-of-work hash power can censor transactions, orphan competing blocks, and attempt double spends. Attack feasibility depends on hash rate, revenue, confirmation policy, and finality rules.

  • Smart-contract vulnerabilities: Reentrancy, incorrect access control, unchecked arithmetic, unsafe external calls, and flawed authorization logic can let attackers steal assets or manipulate contract state.

  • Oracle manipulation: Contracts that trust external prices or events can be exploited through delayed, fabricated, or centralized data.

  • Bridge and cross-chain vulnerabilities: Incorrect proof verification, replay, faulty message validation, and wrapped-asset accounting errors can let attackers mint or steal assets.

  • Key and wallet compromise: Stolen private keys, weak randomness, phishing, malware, or insecure backup procedures can lead to account takeover and forged transactions.

  • Network and node attacks: DDoS requests, peer flooding, eclipse attacks, malformed messages, and abusive large blocks can isolate nodes or exhaust resources.

  • Sybil attacks: An attacker creates many identities to gain disproportionate influence. Bitcoin limits this through proof-of-work costs, while Ethereum’s proof-of-stake system uses staked validators, penalties, and slashing.

  • Software and supply-chain attacks: Vulnerabilities in node software, wallet applications, signing tools, dependencies, or update mechanisms can compromise otherwise valid protocols.

Hash Chains and Merkle Trees

A typical proof-of-work block contains an index, timestamp, data or transaction root, previous-block hash, nonce, and its own hash. In the simplified SHA-256 model, changing a block changes its calculated hash, causing the next block’s previous_hash reference to fail validation. Rewriting later blocks requires recomputing their hashes and winning consensus.

In a simple four-leaf SHA-256 Merkle tree, each leaf is a transaction hash:

  1. Calculate pair_0 = SHA256(leaf_0 || leaf_1).

  2. Calculate pair_1 = SHA256(leaf_2 || leaf_3).

  3. Calculate root = SHA256(pair_0 || pair_1).

  4. Prove leaf_2 using leaf_3 and pair_0; the verifier reconstructs the root.

The leaves and intermediate values must have an unambiguous fixed-width encoding. A Merkle proof establishes inclusion in a committed tree, but it does not prove that the transaction was valid. The root must be anchored by consensus, and application-level transaction rules must still be checked.

Consensus and Adversarial Behavior

Proof of work is a search problem: miners try different nonces until the block hash satisfies a difficulty target. For a simplified target requiring b leading zero bits, each attempt succeeds with probability 2^-b, giving an expected 2^b attempts.

  • Bitcoin uses proof of work, so a 51% hash-power attack is costly but not impossible.

  • Ethereum moved to proof of stake in 2022; attacks instead depend on validator stake, coordination, signing-key security, and protocol penalties.

  • Selfish mining and timestamp manipulation can reduce honest miners’ expected rewards or undermine time-dependent logic.

  • Fee-market manipulation can delay important transactions even without controlling consensus.

  • Long-range and finality attacks are especially relevant to proof-of-stake protocols, where network assumptions and checkpoint rules differ from proof of work.

Complexity

For fixed-size blocks and transactions, n is the number of blocks or leaves and b is the number of required leading zero bits.

Operation Best time Average time Worst time Space
Validate n hash-chain links O(n) O(n) O(n) O(1) auxiliary excluding the stored chain; O(n) including it
Build a Merkle tree O(n) O(n) O(n) O(n) tree-node storage; input storage depends on the leaf representation
Verify a balanced-tree Merkle proof O(log n) O(log n) O(log n) O(1) auxiliary excluding the proof; O(log n) including proof storage
Mine proof of work O(1) O(2^b) expected No finite probabilistic bound O(1) auxiliary

Common Pitfalls

  • Tamper evidence is not absolute finality: Consensus rules determine which competing chain or checkpoint is accepted.

  • A valid Merkle proof is not transaction validity: Consensus must commit to the root, and application rules must still pass.

  • Hashing is not authorization: A correct hash chain cannot compensate for compromised keys or incorrect access control.

  • Proof-of-work assumptions vary: Bitcoin’s security cost, finality behavior, and attack incentives differ from proof-of-stake protocols.

  • Minimal models are not secure systems: A toy hash chain omits signatures, peer-to-peer consensus, transaction validation, difficulty adjustment, and key management.

39

How does hash chaining maintain blockchain immutability?

Hash chaining provides tamper evidence: every block commits to its predecessor’s cryptographic hash, so modifying an earlier block invalidates subsequent links unless the attacker rewrites the chain and obtains network acceptance.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Hash Chaining Works

A blockchain is a linked list of blocks connected by hash pointers. A typical proof-of-work block contains:

Field Purpose
index Identifies the block’s position
timestamp Records when the block was created
data Stores transactions or application-specific information
previous_hash Commits to the preceding block’s hash
nonce Supplies a changing value used during mining
hash Identifies the block and commits to its other fields

The genesis block conventionally uses 64 hexadecimal zeros as its previous hash. Each later block stores the preceding block’s hash.

  1. Block 0 produces hash H0.

  2. Block 1 stores previous_hash = H0 and produces H1.

  3. Changing block 0 changes its recomputed hash.

  4. Block 1’s stored previous hash no longer matches, so validation fails.

An attacker can recompute a rewritten chain, but must make it the chain accepted by the network. In Bitcoin, that requires controlling a majority of the proof-of-work hash rate and gaining adoption for the fork.

Cryptographic Hashing and Merkle Trees

SHA-256, available through Python’s hashlib, provides determinism, collision resistance, preimage resistance, and the avalanche effect. It is not encryption and cannot simply be reversed.

A Merkle tree commits to multiple transaction or data leaves with one root hash:

  • Leaves are hashed, then paired and hashed repeatedly.

  • The final Merkle root can be stored in a block header.

  • A Merkle proof provides sibling hashes for verifying one leaf.

  • Verification uses O(log N) steps because each level halves the remaining candidates.

  • Changing a leaf changes its proof path and root, assuming no hash collision.

Bitcoin uses a Merkle tree for transactions and double SHA-256 for block-header hashing. The example below uses single SHA-256 and stores data directly, so it is not Bitcoin-compatible.

Consensus and Proof-of-Work

Hash links detect modifications but do not determine which chain is authoritative; consensus does that.

  • Bitcoin uses proof-of-work: miners vary candidate fields and search for a block hash below the network target.

  • Ethereum moved to proof-of-stake during the 2022 Merge. Validators make attestations and can be penalized for equivocation.

Proof-of-work is a search problem. If the 256-bit target is the integer T, a random candidate succeeds with probability approximately T / 2^256, requiring about 2^256 / T expected attempts. When T is near 2^(256-b), this becomes approximately 2^b expected attempts.

Complexity

Let n be one block’s serialized size, S = Σnᵢ the total size of B blocks, and M the number of candidates in a bounded proof-of-work search. Merkle bounds assume fixed-size leaf digests. No recursion stack is used.

Operation Best Average Worst Space Reason
Hash one block O(n) O(n) O(n) O(n) SHA-256 scans all bytes; serialization creates n bytes
Validate B blocks O(S) O(S) O(S) O(max nᵢ), chain excluded Each block is serialized and hashed once
Build a Merkle tree O(N) O(N) O(N) O(N), tree included Each fixed-size digest is hashed once
Verify a Merkle proof O(log N) O(log N) O(log N) O(log N), including proof One sibling hash is processed per level
Search proof-of-work candidates O(n) Expected O(n × 2^b) O(nM) O(1) beyond candidate Each candidate hash costs O(n)

An unrestricted proof-of-work candidate space has no finite worst-case bound.

Code Example

from collections.abc import Sequence
from dataclasses import dataclass, replace
import hashlib
import json

GENESIS_PREVIOUS_HASH = "0" * 64


@dataclass(frozen=True)
class Block:
    index: int
    timestamp: str
    data: str
    previous_hash: str
    nonce: int = 0
    hash: str = ""


def calculate_hash(block: Block) -> str:
    """Calculate a block hash without including the hash field itself."""
    payload = {
        "index": block.index,
        "timestamp": block.timestamp,
        "data": block.data,
        "previous_hash": block.previous_hash,
        "nonce": block.nonce,
    }
    encoded = json.dumps(
        payload, sort_keys=True, separators=(",", ":")
    ).encode("utf-8")
    return hashlib.sha256(encoded).hexdigest()


def create_block(
    index: int,
    timestamp: str,
    data: str,
    previous_hash: str,
    nonce: int = 0,
) -> Block:
    """Create a block containing the canonical hash of its fields."""
    candidate = Block(index, timestamp, data, previous_hash, nonce)
    return replace(candidate, hash=calculate_hash(candidate))


def validate_chain(chain: Sequence[Block]) -> bool:
    """Check index continuity, previous-hash links, and block hashes."""
    for expected_index, block in enumerate(chain):
        if block.index != expected_index:
            return False

        expected_previous = (
            GENESIS_PREVIOUS_HASH
            if expected_index == 0
            else chain[expected_index - 1].hash
        )
        if block.previous_hash != expected_previous:
            return False
        if calculate_hash(block) != block.hash:
            return False

    return True


def example() -> None:
    """Demonstrate detection of modified block data."""
    genesis = create_block(
        0, "2025-01-01T00:00:00Z", "genesis", GENESIS_PREVIOUS_HASH
    )
    second = create_block(
        1, "2025-01-01T00:01:00Z", "transfer: 1 coin", genesis.hash
    )
    tampered = replace(second, data="transfer: 100 coins")
    print(validate_chain([genesis, tampered]))  # False


example()  # Expected output: False

Common Pitfalls

  • Overstating immutability: Hash chaining detects tampering, but a sufficiently powerful attacker can rewrite history.

  • Limited validation: validate_chain does not verify proof-of-work, signatures, transaction rules, timestamps, or network consensus.

  • Noncanonical serialization: Every validator must hash identical field ordering and byte representation.

  • Edge cases: The implementation accepts an empty chain and a valid one-block genesis chain. Duplicate or negative text inside data is allowed. Sorting, disconnected graphs, and cycles do not apply to this linear structure.

  • Production readiness: This example demonstrates hash-chain validation only; it is not a secure cryptocurrency implementation.

40

How does blockchain consensus resist Sybil attacks?

Sybil resistance prevents an attacker from gaining disproportionate influence by creating many fake identities. Blockchains achieve this through consensus rules that make additional identities ineffective or expensive—not through the hash chain alone.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Sybil Resistance in Consensus

A Sybil attack creates multiple identities or nodes so they can vote, mine, or participate as though they were independent participants. Consensus mechanisms constrain this:

  • Proof of work (PoW): Participants expend computational effort to produce blocks with valid proof of work. Bitcoin uses PoW, so creating thousands of identities does not create additional hashpower; an attacker must control a significant share of the network’s computational resources.

  • Proof of stake (PoS): Validators generally stake assets, and protocol rules determine their voting influence. Misbehavior may cause slashing, which loses part of the stake. Ethereum completed its transition to PoS in 2022, so an attacker cannot obtain extra voting weight merely by creating accounts.

  • Permissioned membership: Known operators join through authentication, credentials, or governance approval. This prevents arbitrary Sybil identities from participating, although administrators and colluding members remain trust assumptions.

  • Reputation and penalties: Some protocols penalize invalid proposals, equivocation, repeated failures, or other abusive behavior.

There is no universal 50% compromise threshold. In simplified PoW analysis, a majority of hashpower can produce a longer competing chain. In Ethereum PoS, roughly one-third of the stake can prevent finality, while at least two-thirds can finalize a conflicting checkpoint. Exact guarantees depend on the protocol.

Blockchain, Hashing, and Merkle Proofs

A minimal PoW-style block contains:

  • index: Position in the chain.

  • timestamp: Creation time.

  • data: Transactions or other payload.

  • previous_hash: The preceding block’s hash, forming a backward-pointing hash pointer.

  • nonce: A value varied while searching for valid proof of work.

  • hash: The SHA-256 digest of the block’s other fields.

SHA-256 is available through Python’s hashlib library. Changing a block changes its hash and therefore the previous_hash recorded by later blocks. This makes unauthorized modifications detectable, although hash chaining alone neither establishes consensus nor makes history absolutely immutable.

Merkle trees summarize a block’s transactions efficiently. Leaf hashes are paired and hashed repeatedly until one Merkle root remains. A Merkle proof provides the sibling hashes needed to demonstrate that a transaction belongs to the tree without downloading every transaction. In designs using a Merkle root, that root is stored in the block header.

Consensus Search and Validation

PoW can be viewed as a search problem:

  1. Start with nonce = 0.

  2. Hash the block’s index, timestamp, data, previous hash, and nonce.

  3. Compare the resulting digest with the target implied by the difficulty.

  4. If the target is not met, increment the nonce and repeat.

  5. Once the target is met, broadcast the block.

Each hash is effectively a pseudo-random trial. Finding a digest with d leading zero bits requires approximately 2^d attempts in expectation. Validation then checks block order, previous-hash links, recomputed hashes, and the PoW condition, allowing a peer to detect altered data without trusting the sender.

Complexity

Operation Best time Average or expected time Worst time Space
Hash one block of m bytes O(m) O(m) O(m) O(m) including serialization; O(1) if streamed
Validate b blocks of at most m bytes O(bm) O(bm) O(bm) O(1) auxiliary when streamed; O(m) if serialization is materialized
Build a Merkle tree with n leaves O(n) O(n) O(n) O(n), including the tree
Verify a Merkle proof O(log n) O(log n) O(log n) O(1) auxiliary, or O(log n) when storing the proof
Find a PoW nonce with d zero bits O(1) trial Expected O(2^d) trials No fixed bound without a search limit O(1) auxiliary

Unless a row states otherwise, stored input chains or trees are excluded from auxiliary space. These operations require no recursion stack.

Common Pitfalls and Interview Tips

  • Hash chaining is not Sybil resistance: It protects historical consistency, while consensus and membership rules constrain identities.

  • Difficulty changes mining cost: The 2^d estimate is probabilistic, not a guaranteed number of attempts.

  • Validate recomputed hashes: Checking only that previous_hash is nonempty does not detect altered data.

  • Relevant edge cases: Empty and one-block chains are structurally valid; duplicate payload entries are not inherently invalid, but two blocks claiming the same index are; negative numeric values require application-specific validation; sorting is not applicable; and disconnected graphs and cycles do not apply to a linear hash chain.

  • Avoid production claims: A minimal educational blockchain lacks networking, signatures, wallets, transaction validation, Merkle proofs, and distributed Byzantine fault tolerance.

41

How can blockchain scalability be improved?

Blockchain scalability can be improved by increasing throughput and reducing latency without weakening security or decentralization. The main approaches are sharding, off-chain execution, parallel transaction processing, consensus improvements, and better block and data designs.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Blockchain Data Structure

A blockchain is conceptually a hash-linked list of blocks. Each block commonly contains:

  • Index: Its position in the chain.

  • Timestamp: When it was created.

  • Data: Transactions or application state.

  • Previous hash: The hash of the preceding block.

  • Nonce: A value varied during proof-of-work mining.

  • Hash: The SHA-256 digest of the block header.

Changing a block changes its hash, which breaks the link to the next block. This makes the chain tamper-evident, not absolutely immutable: an attacker controlling the consensus mechanism could rewrite subsequent blocks. A trusted checkpoint or external anchoring is needed to detect a complete rewrite.

Transactions are usually organized into a Merkle tree. The block header stores the Merkle root, while a Merkle proof verifies one transaction using approximately O(log m) sibling hashes for m transactions.

Scalability Strategies

Strategy How it improves scalability Main trade-off
Sharding Divides transactions or state among shards so validators process only part of the workload Cross-shard communication and security become more complex
Layer 2 systems Execute transactions off-chain and submit batches, compressed data, or proofs to the main chain Requires careful handling of data availability, censorship, and withdrawals
State channels Keep frequent transfers off-chain and periodically settle the resulting state Best for participants with repeated interactions; opening and closing channels has overhead
Optimistic parallel execution Executes non-conflicting transactions concurrently and resolves conflicts afterward Conflict detection and re-execution can reduce performance
Consensus improvements Replace expensive mining search with more efficient finality mechanisms Consensus changes affect decentralization, security, and finality guarantees
Block and batch tuning Larger blocks or batches amortize per-transaction overhead Larger blocks can take longer to propagate and may be orphaned more often
Data compression and availability Reduces bandwidth through aggregation, compression, and specialized data-availability mechanisms Adds proof-processing and data-verification complexity

Bitcoin uses proof of work. Ethereum moved to proof of stake in 2022, removing energy-intensive mining but not automatically increasing transaction throughput.

Complexity

Let n be the number of blocks, k the serialized size of one block, m the number of transactions in a Merkle tree, and b the number of required leading zero bits.

Operation Best Average or expected Worst Space
Hash one block O(k) O(k) O(k) O(k) for serialized input
Validate a chain O(nk) O(nk) O(nk) O(k) extra; stored chain is O(nk)
Append without mining O(k) O(k) O(k) O(k) for the new block
Proof-of-work search O(k) O(k × 2^b) Unbounded O(k) extra
Verify a Merkle proof O(k + log m) O(k + log m) O(k + log m) O(log m) proof storage

Validation is linear because every block must be checked. Proof-of-work is a probabilistic search: with difficulty b, the expected number of attempts is approximately 2^b, but mining has no fixed upper bound.

Common Pitfalls

  • Confusing tamper-evidence with immutability: The hash chain reveals modification but cannot prevent a full rewrite by a malicious consensus majority.

  • Ignoring Merkle proofs: A valid block hash does not by itself demonstrate efficient proof that a particular transaction belongs to the block.

  • Treating expected mining time as guaranteed: Difficulty determines the expected search cost, not a strict completion deadline.

  • Comparing raw TPS across protocols: Block time, transaction format, finality, fees, and security assumptions differ substantially.

  • Missing chain-validation edges: A validator should state how it treats an empty chain and a genesis-only chain, and it must reject incorrect indexes, links, hashes, or difficulty targets.

  • Assuming Layer 2 removes trust: Layer 2 designs must still address operator behavior, data availability, censorship resistance, and secure withdrawals.

Common interview follow-ups include the difference between hash chains and Merkle trees, proof of work versus proof of stake, rollups versus sharding, and the trade-offs between throughput, latency, and finality.

42

How do blockchain networks achieve interoperability?

Blockchain interoperability is achieved through protocols that transfer and verify transactions, events, messages, or state between independent blockchains. Because networks can differ in block formats, consensus rules, finality models, and execution semantics, interoperability requires agreed message definitions and a way to establish that the source network accepted the data.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Mechanism

A cross-chain interoperability protocol generally performs these steps:

  1. The source blockchain records a transaction, event, message, or state change.

  2. The protocol creates evidence that the item was committed by the source chain, often a Merkle proof containing the item and its sibling hashes.

  3. A relayer, oracle, validator, or light client transports that evidence to the destination chain.

  4. The destination verifies the evidence and establishes that the source block is sufficiently finalized under its trust model.

  5. The destination executes a chain-specific action, such as releasing escrowed assets, minting a representation, or updating an application.

A Merkle proof proves that a leaf is included in a tree with a particular root. It does not, by itself, prove that the source chain reached consensus or that the containing block cannot be reorganized.

For example, the Cosmos InterBlockchain Communication protocol uses relayers to carry packets while light clients verify the counterparty chain’s consensus state. Bitcoin and Ethereum assets, by contrast, commonly cross through bridges that use validator sets, custodians, or smart-contract mechanisms rather than directly validating the other network’s entire consensus history.

Chain Structure and Consensus

A blockchain is effectively a linked list of hash pointers. A generic block record contains fields such as an index or height, timestamp, data, previous-block hash, nonce, and current hash. Cryptographic systems commonly use SHA-256; Python exposes it through hashlib.sha256, while Bitcoin uses double SHA-256 for proof-of-work hashing.

Changing an earlier block changes its hash and therefore invalidates the references to it in later blocks. This is the immutability property created by hash chaining. Consensus is still required because participants must agree on which chain is canonical.

  • Proof-of-work chains: Miners search for a nonce, together with other candidate-header fields, until the resulting hash satisfies the target. This is a probabilistic search problem.

  • Proof-of-stake chains: Validators attest to blocks and finalize checkpoints according to the protocol’s finality rules; they do not search for proof-of-work solutions.

  • Bitcoin uses proof of work, while Ethereum completed its proof-of-stake transition in 2022.

  • A destination protocol must therefore understand the source chain’s finality mechanism or rely on an explicit validator, oracle, or bridge trust model.

Interoperability Approaches

Approach Verification or trust model Main benefit Main risk
Light client Directly verifies source-chain consensus headers and proofs Strong trust minimization Complex and potentially expensive to implement
State or validity proof Verifies a cryptographic proof or quorum attestation about source state Compact cross-chain verification Depends on the proof system and its security assumptions
Lock-and-mint bridge A custodian or validator set secures assets locked on the source chain Straightforward asset transfers Custody loss, validator compromise, or censorship
Atomic swap Both chains enforce the same secret through hashlocks or adaptor signatures No shared custody Requires compatible assets and careful timing
Relay or oracle Relays transport messages while an oracle or attestation set reports source events Supports broader messaging Replay, oracle failure, or conflicting execution

Cross-chain messages should identify the source and destination networks, carry a unique identifier or nonce, and use domain separation. A verifier must track consumed message identifiers so that a valid message cannot be executed more than once. Verification of inclusion must also be separated from verification of consensus finality.

Complexity

  • Chain validation: Best case is O(1) time when the first block fails validation; average and worst cases are O(n) time for n blocks because each block may be inspected once. An empty chain takes O(1). Auxiliary space is O(1), with no recursion stack; the input chain occupies O(n) space if input storage is counted.

  • Proof-of-work mining: Best case is O(1) attempts, average expected attempts are O(16^d) for d leading zero hexadecimal digits, and worst case has no deterministic finite bound. Space is O(B) when serializing a candidate block of size B.

  • Merkle-proof verification: Best, average, and worst cases are O(log m + 1) hash operations for m leaves, because only one root-to-leaf path is processed. Space is O(log m + 1) including the proof path; the separately stored tree is excluded.

Common Pitfalls and Interview Tips

  • Confusing inclusion with finality: A valid Merkle proof does not prove that the source block is finalized.

  • Ignoring replay protection: Use unique message identifiers, destination-aware domain separation, and processed-message tracking.

  • Assuming shared formats: Block serialization, transaction semantics, address formats, and finality rules can all differ.

  • Ignoring bridge trust: Custody, validator thresholds, key rotation, upgrade keys, and emergency controls affect the security model.

  • Defining edge-case policy: State whether an empty chain is valid, how a single genesis block is handled, and whether duplicate transaction data is permitted.

  • Mutating shared data: Verification should not alter supplied chains, proofs, or messages.

  • Common follow-up questions ask how finality is established, how bridge assets are secured, and how duplicate execution is prevented.

43

How do sidechains work in blockchain networks?

A sidechain is a separate blockchain that interoperates with a parent blockchain, commonly through a peg mechanism. Assets can be transferred between the two chains, while the sidechain maintains its own blocks, validators and consensus rules.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Sidechains Work

A typical two-way peg operates as follows:

  1. A user deposits assets into a controlled address on the parent chain.

  2. The peg mechanism detects and confirms the deposit.

  3. Equivalent assets are issued on the sidechain.

  4. To return the assets, the sidechain assets are burned or withdrawn.

  5. The parent chain releases the original assets.

The peg can be federated, where appointed guardians approve transfers, or based on cryptographic proofs that allow the sidechain to observe the parent chain independently. Security therefore depends on the selected peg model; a sidechain does not automatically inherit all of the parent chain’s security.

Blocks, Hashing and Proof of Work

A simplified block contains an index, timestamp, data, previous_hash, nonce and hash. Its hash is calculated using SHA-256 over its fields and the previous block’s hash:

block_hash = SHA256(index || timestamp || data || previous_hash || nonce)

Changing an earlier block changes its hash, invalidating every following previous_hash. This creates the blockchain’s immutability through hash chaining.

In proof-of-work systems, miners vary the nonce until the resulting hash satisfies a target difficulty. This is a computational search problem: on average, finding a hash with d leading zero bits requires approximately 2^d attempts. Bitcoin uses proof of work. Ethereum moved its main network to proof of stake in 2022, although individual sidechains may use either consensus model.

Merkle Trees and Proofs

A block’s transactions are summarized in a Merkle tree. Leaves contain transaction hashes, and each internal node hashes its children. The root commits to all transactions in the block.

A Merkle proof contains the transaction hashes and sibling hashes needed to reconstruct the root. A verifier hashes approximately one level per tree height, proving inclusion without receiving the complete block.

  • Duplicate transactions would produce identical leaf hashes, so protocols must prevent them; Bitcoin, for example, enforces unique transaction IDs (BIP 30 and BIP 34).

  • Empty blocks can use a defined empty-tree root.

  • Merkle proof verification must compare the recomputed root with the trusted root in the block header, not with a root supplied alongside the proof.

Security and System Examples

Sidechains have their own consensus and validator set. Many designs use simplified payment verification, or SPV, to monitor the parent chain and submit proof that a deposit occurred.

Examples include Liquid, a federated Bitcoin sidechain, and Polygon PoS, an Ethereum sidechain with its own validator set. A sidechain differs from a layer-2 rollup: a rollup normally posts data or proofs to the parent chain, whereas a sidechain is independently operated and commonly uses a peg mechanism.

Complexity

Let n be the number of transactions or blocks, k the serialized size being hashed, B the total chain size and d the proof-of-work difficulty.

Operation Best time Average time Worst time Extra space
Hash one fixed-structure block O(k) O(k) O(k) O(k)
Build a Merkle tree O(n) O(n) O(n) O(n)
Generate or verify a Merkle proof O(log n + 1) O(log n + 1) O(log n + 1) O(log n + 1)
Validate a chain of fixed-size blocks O(n) O(n) O(n) O(1)
Search for proof of work O(k) O(2^d · k) Unbounded O(1)

Space excludes the input unless stated otherwise. A recursive Merkle implementation additionally uses an O(log n) recursion stack; the iterative validator below uses O(1) auxiliary space apart from its input list.

Code Example

This educational implementation demonstrates SHA-256 hash chaining and chain validation. It is not production-ready, and its hexadecimal-prefix difficulty is much simpler than Bitcoin’s proof-of-work target.

from dataclasses import dataclass
from datetime import datetime, timezone
import hashlib
import json
import re


@dataclass
class Block:
    index: int
    timestamp: str
    data: str
    previous_hash: str
    nonce: int
    hash: str


def calculate_hash(block: Block, nonce: int) -> str:
    """Calculate a deterministic SHA-256 hash for a block and nonce."""
    payload = {
        "index": block.index,
        "timestamp": block.timestamp,
        "data": block.data,
        "previous_hash": block.previous_hash,
        "nonce": nonce,
    }
    encoded = json.dumps(
        payload, sort_keys=True, separators=(",", ":")
    ).encode("utf-8")
    return hashlib.sha256(encoded).hexdigest()


def mine_block(
    index: int,
    data: str,
    previous_hash: str,
    leading_zeroes: int = 2,
) -> Block:
    """Create a block whose hash starts with the requested zero prefix."""
    timestamp = datetime.now(timezone.utc).isoformat()
    nonce = 0

    while True:
        block = Block(index, timestamp, data, previous_hash, nonce, "")
        candidate_hash = calculate_hash(block, nonce)

        if candidate_hash.startswith("0" * leading_zeroes):
            block.hash = candidate_hash
            return block

        nonce += 1


def validate_chain(chain: list[Block], target_zeroes: int = 2) -> bool:
    """Check block indexes, hash links, stored hashes and proof of work."""
    if not chain:
        return True

    expected_previous_hash = "0" * 64

    for expected_index, block in enumerate(chain):
        if block.index != expected_index:
            return False

        if block.previous_hash != expected_previous_hash:
            return False

        if not re.fullmatch(r"[0-9a-f]{64}", block.hash):
            return False

        if calculate_hash(block, block.nonce) != block.hash:
            return False

        if not block.hash.startswith("0" * target_zeroes):
            return False

        expected_previous_hash = block.hash

    return True


if __name__ == "__main__":
    genesis = mine_block(0, "Sidechain genesis", "0" * 64)
    second = mine_block(1, "Transfer to Alice", genesis.hash)
    chain = [genesis, second]

    print(validate_chain(chain))  # True

    tampered = Block(
        index=2,
        timestamp=datetime.now(timezone.utc).isoformat(),
        data="Tampered transaction",
        previous_hash=second.hash,
        nonce=0,
        hash="0" * 64,
    )
    print(validate_chain([*chain, tampered]))  # False

Common Pitfalls

  • Do not treat every layer-2 system as a sidechain; data availability and validation models differ.

  • Do not assume sidechain security equals Bitcoin or Ethereum security; analyze the peg and validator set.

  • Reject malformed hashes, broken previous_hash links and incorrect block indexes.

  • Remember that proof-of-work search has no fixed worst-case attempt count.

  • Interviewers commonly ask how deposits are authenticated, how redemption works, and what happens if the peg guardians or sidechain validators are compromised.

44

What role do Layer 2 protocols play in blockchains?

Layer 2 (L2) protocols process or settle many blockchain operations outside the base layer, often using the base blockchain for settlement, data availability, or security. They can increase throughput and reduce fees, although sidechains and custodial systems do not necessarily inherit the base chain’s security.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Layer 2 Works

A typical Layer 2 system:

  • Executes transactions or state updates away from the base chain.

  • Groups many operations into a batch or aggregate state.

  • Commits relevant data or proofs to the base chain.

  • Uses the base chain for settlement, disputes, withdrawals, or penalties.

The reduction in fees and congestion comes from representing many operations with fewer base-chain transactions. Layer 2 changes where execution occurs; it does not universally replace the base chain’s consensus or security model.

For example, Bitcoin’s Lightning Network uses channels anchored to Bitcoin’s proof-of-work blockchain. Ethereum rollups operate on Ethereum, which moved from proof of work to proof of stake in 2022.

Main Layer 2 Approaches

Approach Validity and security model
Optimistic rollup Publishes transaction data and uses a challenge period during which incorrect state transitions can be disputed
ZK rollup Publishes a cryptographic validity proof that is verified on the base chain
State channel Participants exchange signed updates off-chain and settle the latest valid state on-chain; disputes can proceed after a timeout without counterparty cooperation
Sidechain Uses its own consensus and security and does not automatically inherit the base chain’s security
Federated or custodial system Relies on operators, committee members, or custodians and therefore introduces additional trust assumptions

Evaluate a Layer 2 system by examining its settlement layer, data availability, proof or fraud mechanism, upgrade process, and escape path rather than relying on the “Layer 2” label alone.

Cryptographic Commitments and Merkle Proofs

A blockchain can be modeled as a linked list of blocks. Each block contains an index, timestamp, data, previous-block hash, nonce, and current hash. A generic SHA-256 example can compute these hashes with Python’s hashlib.sha256(), although Bitcoin uses double SHA-256 and Ethereum uses Keccak-256.

Hash chaining makes changes to earlier blocks detectable because each later block commits to the preceding hash. It does not, by itself, prevent a coordinated rewrite supported by the network’s consensus rules.

A Merkle tree hashes transaction leaves pairwise until it produces one root. A Layer 2 batch can commit to that root on the base chain. For four transactions:

  1. Hash transactions A, B, C, and D into leaves.

  2. Combine leaves into H_AB and H_CD.

  3. Combine those values into the root H(H_AB || H_CD).

A proof for A contains its sibling leaf H(B) and the sibling of H_AB, which is H_CD. The verifier combines them in the order specified by the tree’s convention and compares the result with the committed root. The proof establishes inclusion, not the correctness of the batch’s state transition. Empty batches, one-leaf trees, and duplicate transactions also require explicit tree conventions.

Complexity

Proof-of-work is a search problem: a miner repeatedly hashes candidate headers until one satisfies the target difficulty.

Operation Time complexity Space complexity Reason
Build a Merkle root for n transactions O(n) O(n) if all leaves are retained; O(log n) auxiliary when streamed Each transaction contributes to the root
Generate a Merkle proof O(log n) O(log n) for the proof One sibling is needed per tree level
Verify a Merkle proof O(log n) O(1) auxiliary, excluding the O(log n) proof input Each proof level requires one hash
Validate n fixed-size blocks O(n) O(1) auxiliary, excluding the chain Each block and previous-hash link is checked
Validate a chain with total encoded size S O(S) O(1) auxiliary, excluding the chain Hashing processes the encoded block data
Find a proof-of-work nonce for b leading zero bits Best O(1); expected O(2^b); no finite worst-case bound in an unbounded-nonce model O(1) A random candidate succeeds with probability approximately 2^-b
Store n fixed-size blocks O(n) O(n) total, including the chain Each block contributes its payload and hash links

A recursive Merkle traversal uses O(log n) stack space; an iterative traversal uses O(1).

Common Pitfalls

  • Assuming automatic inheritance of Layer 1 security: Sidechains, federated systems, and custodial systems have different trust assumptions.

  • Treating a Merkle proof as execution validation: It proves inclusion, not correct state-transition computation.

  • Losing sibling order: A proof must identify the correct left/right ordering or use a canonical pairing rule.

  • Ignoring data availability and finality: A rollup needs enough published data for independent reconstruction and challenge.

45

How do scalability, security, and decentralization trade off in blockchains?

The core blockchain challenge is balancing scalability, security, and decentralization: increasing transaction capacity can reduce participation or independence, while stronger consensus can limit throughput. These goals can sometimes improve together, but every design makes different compromises.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Trade-Offs

Property What it improves Pressure it creates
Scalability Transaction capacity, fee efficiency, and confirmation throughput More computation, propagation, storage, or coordination
Security Reliable ordering and resistance to double-spending and Byzantine behavior More consensus work, communication, and validation
Decentralization Distributes control among independent participants and resists censorship More nodes must duplicate validation, storage, and consensus work

A larger block can increase throughput, but propagation and validation times may grow. Sharding can increase aggregate capacity, although committee assignment and validator distribution can create concentration risks. Some Layer 2 systems, particularly sequencer-based rollups, move execution away from the base layer but introduce operator or sequencer concentration risks.

Blocks, Hashing, and Immutability

A block normally contains an index, timestamp, transaction data or a Merkle root, previous_hash, consensus-specific fields such as a nonce, and the block hash.

  • Hash pointer: Each block commits to the predecessor’s hash, forming a linked chain.

  • Cryptographic hashing: SHA-256 produces a fixed 32-byte digest. In Python, hashlib.sha256 implements it. Hashing a block of size (B) takes O(B) time because every serialized byte is processed, and O(B) temporary space for the encoded copy; for a fixed-size block, both are conventionally treated as O(1).

  • Tamper evidence: Changing an earlier block changes its hash and requires later blocks to be recomputed. This makes unauthorized changes detectable, but it does not prevent consensus-supported reorganization.

Chain-selection rules determine the current canonical candidate. Finality rules or trusted checkpoints can additionally indicate that a history is unlikely to be reversed.

Merkle Trees and Proofs

A Merkle tree hashes transaction hashes in a balanced tree. Its root commits to the transaction set while allowing logarithmic membership proofs.

  • Building and storing all levels takes O(n) time and O(n) auxiliary space for (n) transaction hashes because it processes and stores (O(n)) nodes, excluding the input.

  • Producing or verifying a proof takes O(log n) time because each tree level contributes one sibling hash.

  • A proof contains O(log n) sibling hashes and therefore requires O(log n) proof space.

  • Recursive construction adds an O(log n) recursion stack; an iterative construction avoids that stack.

A valid proof establishes that a transaction is included under a committed root. It does not independently prove transaction validity or that the root belongs to the accepted blockchain. Duplicate transaction payloads remain distinct leaves, and an empty transaction set requires a protocol-defined root convention.

Proof of Work and Consensus

Proof of work searches for a nonce whose resulting hash has the required leading zero bits. With difficulty (b) and hash rate (h), the expected number of attempts is O(2^b / h). If each attempt hashes (B) bytes, the best case is O(B), the expected time is O(B · 2^b / h), and probabilistic search has no useful finite worst-case bound. Search uses O(B) temporary space for serialization plus O(1) counters, excluding the candidate block.

  • Security benefit: Computational work provides Sybil resistance, while rewriting recent history requires substantial hash power.

  • Scalability cost: Consensus work and block propagation constrain throughput.

  • Decentralization risk: Mining pools, specialized hardware, and inexpensive electricity can concentrate effective control.

Bitcoin uses proof of work. Ethereum transitioned to proof of stake in 2022, where validators commit stake and can be penalized for dishonest behavior. Proof of stake changes the cost model but still depends on validator distribution, protocol design, and finality rules.

Common Pitfalls

  • Treating higher throughput as automatically equivalent to better scalability; latency, cost, and decentralization also matter.

  • Assuming hash chaining prevents history changes rather than merely making unauthorized changes detectable.

  • Confusing Merkle membership with transaction validity or chain acceptance.

  • Ignoring concentration risks from sharding committees, rollup operators, sequencers, bridges, or mining pools.

  • Mistaking a minimal hash chain for production blockchain software; signatures, transaction validation, distributed consensus, persistence, and finality rules are also required.

46

What tools and environments support blockchain development?

Blockchain development environments range from local test chains and smart-contract toolchains to public test networks, wallet simulators, and indexing services. From a data-structures perspective, the core model is a chain of blocks connected through cryptographic hash pointers, usually supplemented by Merkle trees and a consensus mechanism.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Common Tools and Environments

  • Ethereum development: Hardhat, Foundry, Anvil, Ganache, and Remix provide local EVM execution, debugging, testing, and deployment workflows.

  • Bitcoin development: Bitcoin Core supports regtest for deterministic local testing and testnet for a public test network.

  • Public test networks: Ethereum Sepolia and Bitcoin testnet allow testing without using production funds.

  • Programming environments: Solidity is common for EVM contracts; Rust is widely used with Foundry and for blockchain runtimes; Python is useful for scripts, services, analysis, and transaction automation.

  • Supporting services: Wallet simulators, block explorers, RPC endpoints, indexers such as The Graph, databases, Docker, and CI/CD systems form the surrounding development stack.

  • Permissioned systems: Hyperledger Fabric provides tooling for enterprise blockchain projects with different membership and governance requirements.

  • Consensus context: Bitcoin uses proof of work, while Ethereum moved to proof of stake in 2022. Development frameworks often emulate either consensus model locally.

Blockchain Data Structures

A simplified block contains an index, timestamp, data, previous_hash, nonce, and its own hash.

  • Hash chaining: Each block stores the hash of its predecessor, creating a linked list with cryptographic hash pointers.

  • Tamper evidence: Changing an old block changes its hash, which invalidates the previous_hash stored in the next block and propagates through the remaining chain.

  • Merkle tree: Transactions are hashed into leaves, internal nodes hash their children, and the root summarizes the entire transaction set.

  • Merkle proof: A proof contains sibling hashes and their left/right positions. A verifier can confirm one transaction using the proof and a trusted Merkle root.

  • Proof of work: A miner searches for a nonce whose resulting hash satisfies a target such as a required number of leading zero bits. Bitcoin uses proof of work; Ethereum currently uses proof of stake.

Complexity

Operation Best case Average case Worst case Space
Hash a fixed-size block O(1) O(1) O(1) O(1) auxiliary
Validate an n-block chain O(n) O(n) O(n) O(1) auxiliary, excluding the input chain
Mine at difficulty d O(1) O(16^d) expected attempts No finite upper bound O(1) auxiliary
Build a Merkle tree O(n) O(n) O(n) O(n), including stored nodes
Verify a Merkle proof O(log n) O(log n) O(log n) O(log n) for proof and recursion stack

Hashing becomes O(m) for a payload of m bytes. Chain validation is O(n) only when individual blocks have bounded payload sizes; otherwise it is O(total stored bytes).

Common Pitfalls

  • Hashing is not encryption: SHA-256 produces a one-way digest; it does not hide the original data.

  • Serialization matters: Hash the same canonical fields with the same encoding rules every time.

  • Merkle-tree ordering matters: Proof verification must know whether each sibling belongs on the left or right.

  • Proof-of-work is probabilistic: Difficulty affects expected work, while the worst-case search remains unbounded.

  • A local chain is not a production network: Consensus, peer discovery, key management, persistence, transaction validation, and smart-contract execution need additional engineering.

  • Common follow-up questions: Explain why modifying one block breaks the chain, calculate Merkle-proof complexity, or compare proof of work with proof of stake.

47

How do you test smart contracts?

Smart-contract testing combines deterministic unit tests, integration tests, adversarial edge cases, and invariant-based tests. It verifies both intended contract behavior and assumptions about state transitions, ordering, hash chaining, and finality.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Testing Strategy

Use a layered approach:

  • Unit tests: Test individual functions with mocked accounts, state, balances, timestamps, and external calls.

  • Integration tests: Deploy on a local blockchain, execute transactions, and verify emitted events and persistent state.

  • Fork tests: Execute against a snapshot of a live network to test integrations with existing tokens, oracles, and protocols.

  • Property and fuzz tests: Generate many inputs and assert invariants instead of checking one expected result.

  • Security tests: Exercise reentrancy, access control, arithmetic boundaries, price manipulation, denial of service, and upgrade scenarios.

  • Performance tests: Measure execution costs, such as EVM gas, and identify expensive loops, storage writes, and unbounded operations.

Each test should state its precondition, execute one behavior, and assert an observable result such as a return value, event, balance, or revert.

Blockchain-Specific Checks

A blockchain is a linked list of blocks where each block stores the previous block’s hash. A typical block contains:

  • Index: Its position in the chain.

  • Timestamp: When it was created.

  • Data: Transactions or contract-related data.

  • Previous hash: The preceding block’s hash.

  • Nonce: A value varied during proof-of-work search.

  • Hash: The cryptographic digest of its header or encoded contents.

The hash is commonly computed with SHA-256 using hashlib. Changing an earlier field changes that block’s hash and, if the chain is recomputed, every subsequent hash. Hash chaining makes tampering detectable; consensus and finality rules provide network-level immutability.

Merkle trees organize transactions. Leaves contain transaction hashes, and parent nodes hash their children. With an odd number of leaves, the final hash may be duplicated at that level. A Merkle proof supplies the sibling hashes needed to prove that a transaction belongs to the root. Verification takes logarithmic time when the proof includes the required ordering information.

Consensus assumptions should be tested separately:

  • Bitcoin uses proof of work.

  • Ethereum moved to proof of stake in 2022.

  • Proof of work: Mining searches for a nonce whose block hash satisfies the target difficulty.

  • Proof of stake: Tests should cover validator selection, slashing, finality, and fork behavior.

Complexity

Assume fixed-size block payloads and transaction hashes. Otherwise, add the cost of processing the bytes being hashed. Except for proof-of-work search, the best, average, and worst cases have the same bounds.

Operation Time complexity Space complexity Reason
Validate n blocks O(n) O(1) auxiliary Each block is checked once; the O(n) input chain is excluded.
Proof-of-work search Best O(1); average O(2^k); worst case unbounded O(1) auxiliary A k-bit target needs about 2^k trials on average; the unbounded loop has no finite worst-case bound.
Build a Merkle tree O(n) O(n) total Includes the output tree and any O(log n) recursion stack; input transactions are excluded.
Generate a Merkle proof O(log n) O(log n) total Includes the proof and any O(log n) traversal stack; the existing tree is excluded.
Verify a Merkle proof O(log n) O(1) auxiliary Each sibling requires one hash; the supplied O(log n) proof is excluded.

For the code’s 00 prefix, k = 8, so the expected number of mining attempts is about 256. Exact smart-contract test runtime depends on transactions, storage operations, and virtual-machine execution steps.

Code Example

This minimal hash-chained blockchain demonstrates validation and tamper detection. It is not production-ready and does not execute EVM bytecode.

import hashlib
import json
import time
from dataclasses import dataclass


GENESIS_HASH = "0" * 64
TARGET_PREFIX = "00"


@dataclass
class Block:
    index: int
    timestamp: float
    data: str
    previous_hash: str
    nonce: int
    hash: str = ""

    def compute_hash(self) -> str:
        payload = {
            "index": self.index,
            "timestamp": self.timestamp,
            "data": self.data,
            "previous_hash": self.previous_hash,
            "nonce": self.nonce,
        }
        encoded = json.dumps(
            payload,
            sort_keys=True,
            separators=(",", ":"),
        ).encode("utf-8")
        return hashlib.sha256(encoded).hexdigest()


def mine_block(index: int, data: str, previous_hash: str) -> Block:
    """Create a block whose hash satisfies the simplified PoW target."""
    timestamp = time.time()
    nonce = 0

    while True:
        block = Block(index, timestamp, data, previous_hash, nonce)
        candidate_hash = block.compute_hash()

        if candidate_hash.startswith(TARGET_PREFIX):
            block.hash = candidate_hash
            return block

        nonce += 1


def validate_chain(chain: list[Block]) -> bool:
    """Return whether the chain has valid links, hashes, and PoW."""
    if not chain:
        return False

    expected_previous_hash = GENESIS_HASH

    for expected_index, block in enumerate(chain):
        if block.index != expected_index:
            return False

        if block.previous_hash != expected_previous_hash:
            return False

        if block.hash != block.compute_hash():
            return False

        if not block.hash.startswith(TARGET_PREFIX):
            return False

        expected_previous_hash = block.hash

    return True


def example() -> None:
    chain = [mine_block(0, "deploy contract", GENESIS_HASH)]
    chain.append(mine_block(1, "invoke contract", chain[-1].hash))

    print(f"valid={validate_chain(chain)}")

    chain[-1].data = "tampered transaction"
    print(f"valid_after_tamper={validate_chain(chain)}")


if __name__ == "__main__":
    example()
    # Expected output:
    # valid=True
    # valid_after_tamper=False

Common Pitfalls

  • Empty chains: Define whether an empty chain is valid; this example rejects it.

  • Single-block chains: Verify that the first block points to the genesis hash.

  • Duplicates: Identify transactions by IDs rather than assuming their contents are unique.

  • Invalid inputs: Include zero, negative values, maximum integers, malformed addresses, and boundary timestamps.

  • Graph-like logic: Test disconnected components and cycles when contracts traverse user-supplied graphs.

  • Ordering assumptions: Rely on ordering only when the contract defines it.

  • Permissive mocks: Preserve access control, return values, and failure behavior.

  • Weak assertions: Check state transitions and events, not merely that a call did not revert.

  • Shared state: Reset timestamps, randomness, balances, and snapshots between tests.

  • Finality: Remember that a valid hash chain does not by itself guarantee irreversibility.

48

How do blockchain testnets support safe development?

A testnet is a blockchain network that mirrors a production network but uses test tokens and often disposable or low-stakes accounts. It lets developers test transactions, smart contracts, consensus changes, and client software without risking production assets or disrupting live users.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Testnet Types

Environment Isolation Main use
Mainnet Real assets and users Production operation
Public testnet Shared network with test tokens Realistic multi-node testing
Local devnet or private network Developer-controlled Fast, deterministic unit and integration testing

A public testnet provides more realistic network latency, peer discovery, block propagation, and reorg behavior than a local chain. Test tokens normally have no monetary value and may be obtained through a faucet.

Blockchain Data Structures

A blockchain can be viewed as a linked list of blocks. Each block contains:

  • index: Its position in the chain.

  • timestamp: When it was created.

  • data: Transactions or application data.

  • previous_hash: The hash pointer to the preceding block.

  • nonce: A value changed while searching for valid proof of work.

  • hash: The block’s cryptographic identifier.

Changing an earlier block changes its hash. Because the next block stores that hash as previous_hash, the change propagates through every later block. This makes unauthorized modification detectable, although hash chaining alone cannot prevent someone from rebuilding an entire alternative chain; consensus and network finality provide that protection.

Merkle Trees and Proof of Work

A Merkle tree organizes transaction hashes into a binary tree. Leaves contain transaction hashes, internal nodes hash their children, and the root summarizes all transactions. Including the Merkle root in a block header commits the block to its transactions while allowing compact inclusion proofs.

A Merkle proof contains the sibling hashes along the path to the root. A verifier hashes the claimed transaction with those siblings and compares the result with the committed root.

In proof-of-work systems such as Bitcoin, miners search for a nonce whose block hash falls below a target. This is a search problem:

  • Best case: One hash attempt succeeds.

  • Expected case: If the target has probability (p) of acceptance, approximately (1/p) attempts are needed.

  • Worst case: The number of attempts is unbounded.

  • Space: (O(1)) auxiliary space per attempt.

Ethereum moved from proof of work to proof of stake in 2022, so its current consensus does not use Bitcoin-style nonce mining.

Code Example

This simplified blockchain demonstrates SHA-256 hashing, hash-linked blocks, proof-of-work searching, and chain validation. It is educational, not production-ready.

from dataclasses import dataclass, replace
import hashlib
import json
import time

GENESIS_PREVIOUS_HASH = "0" * 64


@dataclass(frozen=True)
class Block:
    index: int
    timestamp: int
    data: tuple[str, ...]
    previous_hash: str
    nonce: int
    hash: str


def calculate_hash(block: Block) -> str:
    """Calculate a deterministic SHA-256 hash for a block."""
    payload = {
        "index": block.index,
        "timestamp": block.timestamp,
        "data": list(block.data),
        "previous_hash": block.previous_hash,
        "nonce": block.nonce,
    }
    encoded = json.dumps(
        payload, sort_keys=True, separators=(",", ":")
    ).encode("utf-8")
    return hashlib.sha256(encoded).hexdigest()


def has_valid_work(block_hash: str, difficulty_bits: int) -> bool:
    """Return whether a hash satisfies the proof-of-work target."""
    if not 0 <= difficulty_bits <= 256:
        return False
    target = 1 << (256 - difficulty_bits)
    return int(block_hash, 16) < target


def mine_block(
    previous_block: Block,
    data: tuple[str, ...],
    difficulty_bits: int = 8,
) -> Block:
    """Mine a block by searching for a valid nonce."""
    if not 0 <= difficulty_bits <= 256:
        raise ValueError("difficulty_bits must be between 0 and 256")

    nonce = 0
    while True:
        candidate = Block(
            index=previous_block.index + 1,
            timestamp=int(time.time()),
            data=data,
            previous_hash=previous_block.hash,
            nonce=nonce,
            hash="",
        )
        candidate_hash = calculate_hash(candidate)
        if has_valid_work(candidate_hash, difficulty_bits):
            return replace(candidate, hash=candidate_hash)
        nonce += 1


def validate_chain(chain: list[Block], difficulty_bits: int = 8) -> bool:
    """Validate block links, stored hashes, indices, and proof of work."""
    if not chain:
        return False

    if chain[0].previous_hash != GENESIS_PREVIOUS_HASH:
        return False

    for expected_index, block in enumerate(chain):
        if block.index != expected_index:
            return False

        if expected_index > 0:
            if block.previous_hash != chain[expected_index - 1].hash:
                return False

        expected_hash = calculate_hash(block)
        if block.hash != expected_hash:
            return False

        # The genesis block is created directly, so it is exempt from proof of work.
        if expected_index > 0 and not has_valid_work(expected_hash, difficulty_bits):
            return False

    return True


genesis = Block(0, int(time.time()), (), GENESIS_PREVIOUS_HASH, 0, "")
genesis = replace(genesis, hash=calculate_hash(genesis))
chain = [genesis, mine_block(genesis, ("Alice", "Bob", 10), 8)]

print(validate_chain(chain, 8))  # Expected output: True

For (n) blocks containing (D) total data, validation takes (O(n + D)) time because every block and its data are hashed, with (O(1)) auxiliary space, excluding the (O(n)) input chain. Building a Merkle tree for (t) transactions takes (O(t)) time and (O(t)) space; producing or verifying a proof takes (O(log t)) time and (O(log t)) proof space because the tree is balanced.

Practical Workflow

Developers commonly:

  1. Run contracts and migrations against a local development network.

  2. Deploy to a public testnet using test tokens.

  3. Exercise multi-user and multi-node behavior.

  4. Test upgrades, forks, migrations, and failure recovery.

  5. Audit results before considering a mainnet deployment.

Testnets are important because they expose problems involving state transitions, serialization, indexing, event handling, consensus, and network latency before production impact. However, they do not perfectly reproduce mainnet traffic, economics, governance, or security. Public testnets can also reset, reorganize, or become unavailable.

Common Pitfalls and Interview Tips

  • Empty chain: The example rejects it because a valid blockchain needs its genesis block.

  • Single block: A genesis block with a correct hash is valid; it is exempt from proof of work.

  • Duplicates: Duplicate transactions are not automatically invalid; applications should define replay or deduplication rules.

  • Negative values and ordering: The toy data field does not impose domain constraints; sorting and graph-specific concepts do not apply to this linear chain.

  • Cycles: The previous_hash links and sequential indices prevent cycles in this model.

  • Production confusion: Never store real secrets or use production private keys in a testnet environment.

  • Consensus accuracy: Bitcoin uses proof of work; modern Ethereum uses proof of stake.

  • Common follow-up: Interviewers often ask how Merkle proofs reduce bandwidth, why hash chaining detects tampering, or why proof of work is probabilistic rather than an absolute security guarantee.

49

What is the difference between on-chain and off-chain development?

On-chain development builds logic whose execution and state transitions are handled by a blockchain network, whereas off-chain development builds applications that run outside the network and use the chain for commitments, authentication, settlement, or proof publication. The distinction is where computation and authoritative state live, not whether an application can use both.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

On-chain programs, commonly called smart contracts, are executed by participating nodes and must behave deterministically so that every validator reaches the same result. Their state and effects are recorded in the ledger, and execution consumes finite network resources such as block space and gas.

Off-chain applications run on external servers, databases, or user devices. They can perform work that would be too expensive or unsuitable for direct execution on the chain. A common commitment pattern is:

  1. Store a document, computation result, or media file off-chain.

  2. Compute its SHA-256 digest, for example with Python’s hashlib.

  3. Put the digest or another commitment on-chain.

  4. Recompute the digest later to check whether the off-chain data matches the commitment.

A matching digest establishes integrity, but not authorship or correctness. Signatures, authorization policies, or proofs are needed when those properties matter.

Blockchain Data Structures

A simplified blockchain is a linked list of blocks, with each block containing a cryptographic hash pointer to its predecessor.

Field Purpose
index Identifies the block’s position in the chain
timestamp Records when the block was created
data Stores transactions or application-specific commitments
previous_hash Points cryptographically to the preceding block
nonce Supplies the varying value used during proof-of-work search
hash Identifies the block and commits to its contents

Changing an earlier block changes its hash and therefore changes the expected previous_hash of subsequent blocks. This creates tamper evidence, although absolute immutability still depends on consensus, finality, and network governance.

Transaction sets can be organized into a Merkle tree. A Merkle proof demonstrates that a transaction belongs to a committed tree root without revealing every other transaction, allowing light clients to verify inclusion efficiently.

Proof of Work and Consensus

Proof of work is a search problem: miners repeatedly vary a nonce until the block hash satisfies a difficulty target. The expected number of attempts grows exponentially as the target becomes more restrictive.

Bitcoin uses proof of work. Ethereum transitioned to proof of stake during the 2022 Merge, where validators are selected using staked collateral rather than computational hash search. Off-chain execution does not remove the need for consensus when an application relies on a layer-one chain for settlement or finality.

On-Chain vs. Off-Chain

Aspect On-Chain Off-Chain
Execution Runs through blockchain validators Runs on external infrastructure
Verification Validators replicate and verify state transitions The chain may verify only a commitment or proof
Cost Consumes gas, fees, and finite execution resources Usually cheaper and more elastic
Performance Constrained by block space and consensus Can use databases, GPUs, and distributed services
Privacy State is usually publicly visible Can use access controls and encryption, but privacy is not automatic
Trust Shared validation depends on consensus and protocol correctness Trust may depend on operators, signatures, or proofs
Failure handling Deterministic replay and protocol-level recovery Application-specific retries and infrastructure handling

Many systems are hybrid. Layer-2 rollups, for example, execute transactions outside the main chain while relying on the main chain for data availability, proofs, or settlement.

Complexity

For n serialized blocks of approximately m bytes each:

  • Block validation: best O(m) when the first block is rejected, and average and worst O(nm) when the complete chain must be validated. Each block is serialized and hashed once.

  • Space: O(m) auxiliary validation space for the temporary serialization, with no recursion stack. The stored chain occupies O(nm) when the input itself is counted.

  • Toy proof-of-work mining: best O(m) if the first nonce succeeds, average or expected O(16^d · m) for a toy target of d leading zero bytes, and no finite deterministic worst-case bound. Auxiliary space is O(m) excluding the chain.

Common Pitfalls

  • An on-chain hash provides integrity, not automatically authorship, authorization, or correctness.

  • Off-chain does not automatically mean decentralized, private, or trustless.

  • Hash chaining makes tampering detectable but does not replace consensus, finality, or governance.

  • Avoid placing large or sensitive payloads directly on-chain merely because the ledger can technically store them.

  • Interviewers commonly ask about off-chain data availability, chain reorganizations, Merkle-proof verification, and the trust assumptions of hybrid designs.

50

How can GDPR compliance coexist with immutable blockchain data?

GDPR compliance depends on data minimisation: personal data should not be placed on an immutable, widely replicated ledger unless a documented legal basis and deletion strategy make that unavoidable. Hashing or pseudonymising information does not automatically make it anonymous or erasable.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

GDPR and Immutable Ledgers

A blockchain provides tamper evidence, not an exemption from data-protection law. Changing an existing block requires invalidating its hash and all descendant blocks, usually through consensus or a chain fork.

For a GDPR assessment:

  • Determine personal data: raw identifiers are personal data, and pseudonymous identifiers remain personal when linkable.

  • Apply lawful basis and purpose limitation: establish an Article 6 lawful basis and a specific processing purpose.

  • Minimise the ledger: avoid names, contact details, document contents, stable user identifiers and unnecessary metadata.

  • Handle Article 17 rights carefully: erasure is not absolute; exceptions include legal obligations, legal claims and certain public-interest grounds.

  • Perform a DPIA: assess profiling, large-scale processing and the consequences of permanent disclosure.

Bitcoin uses proof of work, while Ethereum moved to proof of stake in 2022. Neither consensus design makes stored personal data GDPR-compliant.

Practical Compliance Architecture

A common design keeps sensitive records outside the blockchain:

  • Store records in an encrypted, access-controlled, erasable database.

  • Put only a document identifier or cryptographic commitment in the ledger.

  • Use per-record encryption keys where “crypto-shredding” is appropriate, while addressing backups and metadata.

  • Use zero-knowledge proofs when a user must prove a fact without revealing the underlying record.

  • In a permissioned ledger, define governance for rectification, restriction and deletion; permissioned access alone does not resolve immutability.

  • Implement access requests, correction workflows, retention limits, processor agreements and international-transfer safeguards.

Deleting an off-chain record may make it inaccessible, but its on-chain commitment can remain personal if it can be linked to a person. Known-document hashes are also vulnerable to dictionary attacks.

Hashing, Merkle Proofs and Proof of Work

A minimal block contains an index, timestamp, data, previous hash, nonce and hash. SHA-256, implemented with hashlib, links each block to its predecessor. Changing one block changes its hash and therefore the hashes expected by later blocks.

For many documents, construct a Merkle tree:

  1. Hash each document leaf.

  2. Hash child pairs to produce internal nodes.

  3. Anchor the Merkle root on-chain.

  4. Supply an authentication path containing O(log n) sibling hashes.

A verifier can prove that a document belongs to the anchored root without revealing every other document. The root, transaction metadata and proof context can still be personal data.

Proof of work is a search problem: miners vary the nonce until the block hash satisfies a target. For b required leading zero bits, the expected work is approximately 2^b hash attempts.

Code Example

This educational implementation stores references rather than personal data and is not production-ready.

from dataclasses import dataclass
from hashlib import sha256
import json


@dataclass(frozen=True)
class Block:
    index: int
    timestamp: int
    data: str
    previous_hash: str
    nonce: int
    hash: str


def calculate_hash(
    index: int,
    timestamp: int,
    data: str,
    previous_hash: str,
    nonce: int,
) -> str:
    """Calculate a block's SHA-256 hash using canonical JSON."""
    payload = json.dumps(
        {
            "index": index,
            "timestamp": timestamp,
            "data": data,
            "previous_hash": previous_hash,
            "nonce": nonce,
        },
        sort_keys=True,
        separators=(",", ":"),
    ).encode("utf-8")
    return sha256(payload).hexdigest()


def mine_block(
    index: int,
    timestamp: int,
    data: str,
    previous_hash: str,
    difficulty: int = 2,
) -> Block:
    """Mine a block using a simplified proof-of-work target."""
    if difficulty <= 0:
        raise ValueError("difficulty must be positive")

    target = "0" * difficulty
    nonce = 0
    while True:
        current_hash = calculate_hash(
            index, timestamp, data, previous_hash, nonce
        )
        if current_hash.startswith(target):
            return Block(
                index, timestamp, data, previous_hash, nonce, current_hash
            )
        nonce += 1


def validate_chain(chain: list[Block], difficulty: int = 2) -> bool:
    """Validate block links, stored hashes and proof-of-work targets."""
    if difficulty <= 0:
        raise ValueError("difficulty must be positive")

    previous_hash = "0" * 64
    target = "0" * difficulty

    for expected_index, block in enumerate(chain):
        if block.index != expected_index:
            return False
        if block.previous_hash != previous_hash:
            return False

        calculated_hash = calculate_hash(
            block.index,
            block.timestamp,
            block.data,
            block.previous_hash,
            block.nonce,
        )
        if block.hash != calculated_hash:
            return False
        if not block.hash.startswith(target):
            return False

        previous_hash = block.hash

    return True


def create_demo_chain() -> list[Block]:
    """Create a minimal chain containing non-personal data references."""
    chain: list[Block] = []
    previous_hash = "0" * 64

    for index, data in enumerate(("data-ref:a", "data-ref:b")):
        block = mine_block(
            index=index,
            timestamp=1_700_000_000 + index,
            data=data,
            previous_hash=previous_hash,
        )
        chain.append(block)
        previous_hash = block.hash

    return chain


print(validate_chain(create_demo_chain()))  # True

Complexity

Let m be serialized block size, n the chain length and b the proof-of-work difficulty.

Operation Time Space
Hash one block O(m) O(m) temporary serialization space
Validate n blocks O(nm), or O(n) for fixed-size blocks O(1) auxiliary; O(nm) if stored input is counted
Mine a block Best O(m), expected O(2^b · m), no deterministic worst-case bound O(m) auxiliary
Build a balanced Merkle tree O(n) O(n) storage plus O(log n) recursion stack
Produce or verify a Merkle proof O(log n) O(log n) proof storage

Common Pitfalls

  • Assuming hashes are anonymous: hashes are pseudonymous when linkable and can reveal guessed records.

  • Treating erasure as unconditional: assess Article 17 exceptions and legal-obligation conflicts before designing around deletion.

  • Leaving identifiers in metadata: wallet addresses, timestamps and transaction relationships may reveal personal data.

  • Confusing integrity with compliance: proof of work and hash chaining do not replace encryption, access control, lawful basis or data-subject rights.

  • Trusting timestamps or difficulty blindly: a blockchain timestamp is supplied by a participant, and the example’s difficulty mechanism is intentionally simplified.

  • Overlooking operational requirements: include backup deletion, retention, audit logs, incident response, DPIAs and processor contracts in the design.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 50 Blockchain answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects