Blocks, chains, and hashing in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Blocks, chains, and hashing

O(n)

Understanding Time Complexity

When working with blocks and chains in blockchain, it is important to understand how the time to process data grows as the chain gets longer.

We want to know how the time to add or verify blocks changes as more blocks join the chain.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function verifyChain(chain) {
  for (let i = 1; i < chain.length; i++) {
    if (chain[i].previousHash !== hash(chain[i - 1])) {
      return false;
    }
  }
  return true;
}

This code checks if each block correctly links to the previous one by comparing hashes along the chain.

Identify Repeating Operations

• Primary operation: Looping through each block in the chain to check hashes.
• How many times: Once for each block except the first, so roughly the number of blocks (n).

How Execution Grows With Input

As the chain grows, the time to verify it grows in a straight line with the number of blocks.

Input Size (n)	Approx. Operations
10	About 9 hash checks
100	About 99 hash checks
1000	About 999 hash checks

Pattern observation: Doubling the number of blocks roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to verify the chain grows directly with the number of blocks.

Common Mistake

[X] Wrong: "Verifying the chain takes the same time no matter how long it is."

[OK] Correct: Each block must be checked against the previous one, so more blocks mean more checks and more time.

Interview Connect

Understanding how verification time grows helps you explain blockchain efficiency clearly and confidently in real-world discussions.

Self-Check

"What if we stored a summary hash that represents the whole chain? How would the time complexity of verification change?"

Practice

1. What is the main purpose of a hash in a blockchain block?

easy

A. To create a unique fingerprint of the block's data

B. To store the block's timestamp

C. To list all transactions in the block

D. To connect the block to the internet

Solution

1. Step 1: Understand what a hash does

   A hash is a unique code generated from the block's data, like a fingerprint.

2. Step 2: Identify the purpose of the hash in blockchain

   The hash ensures the block's data cannot be changed without detection.

3. Final Answer:

   To create a unique fingerprint of the block's data -> Option A

4. Quick Check:

   Hash = Unique fingerprint [OK]

Hint: Hash = unique code for block data [OK]

Common Mistakes:

• Confusing hash with timestamp
• Thinking hash stores transactions
• Believing hash connects to internet

2. Which of the following is the correct way to represent a block's hash in code?

easy

A. hash = block_data + SHA256

B. hash = SHA256(block_data)

C. hash = SHA256(block_data + hash)

D. hash = block_data.hash()

Solution

1. Step 1: Recognize the correct hash function usage

   SHA256 is a common hash function applied to block data to get the hash.

2. Step 2: Check each option for correct syntax

   hash = SHA256(block_data) correctly applies SHA256 to block_data. Others misuse the function or syntax.

3. Final Answer:

   hash = SHA256(block_data) -> Option B

4. Quick Check:

   Correct hash function call = hash = SHA256(block_data) [OK]

Hint: Hash function called with data inside parentheses [OK]

Common Mistakes:

• Adding hash function as string instead of calling it
• Using incorrect syntax for hash function
• Confusing method call with variable

3. Consider this simplified Python code for creating a blockchain block hash:

import hashlib
block_data = 'Block 1 data'
hash_object = hashlib.sha256(block_data.encode())
block_hash = hash_object.hexdigest()
print(block_hash)

What will be the output type of block_hash?

medium

A. integer

B. bytes

C. string

D. list

Solution

1. Step 1: Understand hashlib.sha256 and hexdigest()

   hashlib.sha256 returns a hash object; hexdigest() converts it to a hex string.

2. Step 2: Identify the output type of hexdigest()

   hexdigest() returns a string representing the hash in hexadecimal form.

3. Final Answer:

   string -> Option C

4. Quick Check:

   hexdigest() output = string [OK]

Hint: hexdigest() returns string, digest() returns bytes [OK]

Common Mistakes:

• Thinking hexdigest() returns bytes
• Confusing output with integer or list
• Ignoring .encode() usage

4. The following code tries to link blocks in a chain by storing the previous block's hash. What is the error?

class Block:
    def __init__(self, data, prev_hash):
        self.data = data
        self.prev_hash = prev_hash

block1 = Block('First block', None)
block2 = Block('Second block', block1.hash)

medium

A. block1.hash is not defined before use

B. prev_hash should be a list, not a single value

C. None cannot be used as prev_hash

D. block2 data should be a number, not string

Solution

1. Step 1: Check block1 attributes

   block1 has data and prev_hash but no attribute named 'hash'.

2. Step 2: Identify usage of undefined attribute

   block2 tries to use block1.hash which does not exist, causing an error.

3. Final Answer:

   block1.hash is not defined before use -> Option A

4. Quick Check:

   Accessing undefined attribute = block1.hash is not defined before use [OK]

Hint: Check if attribute exists before using it [OK]

Common Mistakes:

• Assuming hash attribute exists by default
• Confusing prev_hash type requirements
• Thinking data type causes error

5. You want to create a simple blockchain where each block stores its own hash and the previous block's hash. Which code snippet correctly computes and links the hashes for two blocks?

hard

A. import hashlib

class Block:
def __init__(self, data, prev_hash):
self.data = data
self.prev_hash = prev_hash
self.hash = hashlib.sha256(data.encode()).hexdigest()

block1 = Block('Block 1', '0')
block2 = Block('Block 2', block1.hash)

B. import hashlib

class Block:
def __init__(self, data):
self.data = data
self.hash = hashlib.sha256(data.encode()).hexdigest()

block1 = Block('Block 1')
block2 = Block('Block 2')
block2.prev_hash = block1.hash

C. class Block:
def __init__(self, data, prev_hash):
self.data = data
self.prev_hash = prev_hash
self.hash = data + prev_hash

block1 = Block('Block 1', '0')
block2 = Block('Block 2', block1.hash)

D. import hashlib

class Block:
def __init__(self, data, prev_hash):
self.data = data
self.prev_hash = prev_hash
self.hash = hashlib.sha256((data + prev_hash).encode()).hexdigest()

block1 = Block('Block 1', '0')
block2 = Block('Block 2', block1.hash)

Solution

1. Step 1: Check hash calculation includes previous hash

   The correct implementation computes the hash from both data and prev_hash: self.hash = hashlib.sha256((data + prev_hash).encode()).hexdigest(), ensuring secure linking.

2. Step 2: Verify other options

   B: prev_hash set after hash computation (hash ignores prev_hash); C: no hashing, just concatenation; D: hash ignores prev_hash.

3. Final Answer:

   self.hash = hashlib.sha256((data + prev_hash).encode()).hexdigest() -> Option D

4. Quick Check:

   Hash(data + prev_hash) [OK]

Hint: Hash must include previous hash to link blocks [OK]

Common Mistakes:

• Not including prev_hash in hash calculation
• Assigning prev_hash after block creation
• Using plain concatenation without hashing