Why blockchain exists - Performance Analysis

Time Complexity: Why blockchain exists

O(n)

Understanding Time Complexity

We want to understand how the work done by blockchain systems grows as more data or users join.

Specifically, how does the time to process transactions or add blocks change with size?

Scenario Under Consideration

Analyze the time complexity of the following simplified blockchain block validation process.

function validateBlock(block, blockchain) {
  for (let tx of block.transactions) {
    if (!isValidTransaction(tx, blockchain)) {
      return false;
    }
  }
  return true;
}

function isValidTransaction(tx, blockchain) {
  // Checks if transaction inputs are unspent
  return blockchain.unspentOutputs.has(tx.input);
}
    

This code checks each transaction in a new block to make sure it is valid by looking up unspent outputs in the blockchain.

Identify Repeating Operations

Look for loops or repeated checks in the code.

• Primary operation: Looping through each transaction in the block.
• How many times: Once per transaction in the block.
• Secondary operation: Checking if each transaction input is unspent, which is a quick lookup.

How Execution Grows With Input

As the number of transactions in a block grows, the time to validate grows too.

Input Size (n)	Approx. Operations
10	10 transaction checks
100	100 transaction checks
1000	1000 transaction checks

Pattern observation: The work grows directly with the number of transactions; doubling transactions doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to validate a block grows in a straight line with the number of transactions it contains.

Common Mistake

[X] Wrong: "Validating a block takes the same time no matter how many transactions it has."

[OK] Correct: Each transaction must be checked, so more transactions mean more work and more time.

Interview Connect

Understanding how blockchain validation time grows helps you explain system limits and design choices clearly.

Self-Check

"What if the blockchain stored unspent outputs in a more complex data structure? How would that affect validation time?"

Practice

1. Why was blockchain technology created?

easy

A. To make computers run faster

B. To allow people to trust data without needing a middleman

C. To store large video files efficiently

D. To replace all traditional databases

Solution

1. Step 1: Understand the main purpose of blockchain

   Blockchain was designed to create trust in data without relying on a central authority or middleman.

2. Step 2: Compare options with blockchain's purpose

   Options B, C, and D do not match blockchain's core goal of trust and decentralization.

3. Final Answer:

   To allow people to trust data without needing a middleman -> Option B

4. Quick Check:

   Blockchain = Trust without middleman [OK]

Hint: Blockchain = trust data without middleman [OK]

Common Mistakes:

• Thinking blockchain is just a faster database
• Confusing blockchain with file storage
• Believing blockchain replaces all databases

2. Which of the following is the correct way to describe a blockchain?

easy

A. A chain of blocks where each block links to the previous one

B. A single large block storing all data

C. A random collection of unrelated data blocks

D. A block that changes data easily

Solution

1. Step 1: Recall blockchain structure

   Blockchain is made of blocks linked in order, each pointing to the previous block.

2. Step 2: Eliminate incorrect descriptions

   Options A, B, and D do not describe the linked and secure nature of blockchain blocks.

3. Final Answer:

   A chain of blocks where each block links to the previous one -> Option A

4. Quick Check:

   Blockchain = linked blocks [OK]

Hint: Blockchain links blocks in order securely [OK]

Common Mistakes:

• Thinking blockchain is one big block
• Believing blocks are unrelated
• Assuming blocks can be changed easily

3. Consider this simple blockchain data structure in Python-like pseudocode:

blocks = [
  {'index': 1, 'data': 'A', 'prev_hash': '0'},
  {'index': 2, 'data': 'B', 'prev_hash': 'hash1'},
  {'index': 3, 'data': 'C', 'prev_hash': 'hash2'}
]
print(blocks[1]['data'])

What will be the output?

medium

A. A

B. hash1

C. C

D. B

Solution

1. Step 1: Identify the list index accessed

   blocks[1] accesses the second item in the list, which has data 'B'.

2. Step 2: Access the 'data' key of that block

   blocks[1]['data'] returns 'B'.

3. Final Answer:

   B -> Option D

4. Quick Check:

   blocks[1]['data'] = B [OK]

Hint: List index 1 is second item, data is 'B' [OK]

Common Mistakes:

• Confusing list index starting at 0
• Mixing data and prev_hash values
• Assuming index key affects list indexing

4. This code tries to add a new block to a blockchain list but has an error:

blockchain = [{'index': 1, 'data': 'A', 'prev_hash': '0'}]
new_block = {'index': 2, 'data': 'B', 'prev_hash': blockchain['index']}
blockchain.append(new_block)
print(blockchain)

What is the error?

medium

A. Cannot use blockchain['index'] because blockchain is a list, not a dict

B. Missing 'data' key in new_block

C. append() method does not exist for lists

D. Index value should be a string, not a number

Solution

1. Step 1: Identify the type of 'blockchain'

   blockchain is a list, so blockchain['index'] is invalid syntax.

2. Step 2: Understand correct way to get last block's index

   To get last block's index, use blockchain[-1]['index'], not blockchain['index'].

3. Final Answer:

   Cannot use blockchain['index'] because blockchain is a list, not a dict -> Option A

4. Quick Check:

   List indexing needs integer, not string key [OK]

Hint: List uses numeric indexes, not string keys [OK]

Common Mistakes:

• Using string keys on a list
• Forgetting to access last element with -1
• Confusing append() with other methods

5. You want to create a simple blockchain that stores ownership records. Which feature of blockchain helps ensure records cannot be changed without everyone noticing?

hard

A. Blocks can be edited by anyone at any time

B. Blocks are stored in a single central database

C. Blocks are linked by hashes that depend on previous blocks

D. Blocks are deleted after 24 hours automatically

Solution

1. Step 1: Understand blockchain's security feature

   Each block contains a hash that depends on the previous block's data, linking them securely.

2. Step 2: Explain why this prevents unnoticed changes

   If any block changes, its hash changes, breaking the chain and alerting everyone.

3. Final Answer:

   Blocks are linked by hashes that depend on previous blocks -> Option C

4. Quick Check:

   Hash linking = tamper detection [OK]

Hint: Hash links blocks to detect changes [OK]

Common Mistakes:

• Thinking blockchain is centralized
• Believing blocks can be freely edited
• Assuming blocks are temporary