Distributed ledger concept in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Distributed ledger concept

O(n * m)

Understanding Time Complexity

When working with distributed ledgers, it is important to understand how the time to process transactions grows as more participants join the network.

We want to know how the system's work changes when the number of nodes or transactions increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function validateLedger(transactions, nodes) {
  for (let node of nodes) {
    for (let tx of transactions) {
      if (!node.verify(tx)) {
        return false;
      }
    }
  }
  return true;
}

This code checks every transaction on every node to confirm the ledger is valid across the network.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over nodes and transactions.
• How many times: For each node, it checks every transaction once.

How Execution Grows With Input

As the number of nodes or transactions grows, the total checks increase by multiplying both.

Input Size (nodes x transactions)	Approx. Operations
10 nodes, 10 transactions	100 checks
100 nodes, 100 transactions	10,000 checks
1000 nodes, 1000 transactions	1,000,000 checks

Pattern observation: The work grows quickly as both inputs increase, multiplying together.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to validate grows in proportion to the number of nodes times the number of transactions.

Common Mistake

[X] Wrong: "The time only depends on the number of transactions, not nodes."

[OK] Correct: Each node must check all transactions, so more nodes mean more total work.

Interview Connect

Understanding how work scales in distributed ledgers shows you can think about real systems where many computers share tasks.

Self-Check

"What if each node only verified a random subset of transactions? How would the time complexity change?"

Practice

1. What is the main purpose of a distributed ledger in blockchain technology?

easy

A. To store data only on one central computer

B. To share data across many computers to keep it safe and clear

C. To allow only one person to control the data

D. To make data unreadable for everyone

Solution

1. Step 1: Understand the concept of distributed ledger

   A distributed ledger shares data across many computers instead of one central place.

2. Step 2: Identify the main goal

   This sharing keeps data safe and clear for everyone involved.

3. Final Answer:

   To share data across many computers to keep it safe and clear -> Option B

4. Quick Check:

   Distributed ledger = shared safe data [OK]

Hint: Distributed means data is shared, not stored in one place [OK]

Common Mistakes:

• Thinking data is stored on a single computer
• Believing one person controls the ledger
• Confusing encryption with data sharing

2. Which of the following is the correct way to describe a block in a distributed ledger?

easy

A. A software program that controls the network

B. A single piece of data stored only on one computer

C. A secret key used to encrypt data

D. A group of transactions linked together and shared across the network

Solution

1. Step 1: Define what a block is in blockchain

   A block is a group of transactions bundled together.

2. Step 2: Understand its role in the network

   Blocks are linked and shared across the network to keep data consistent.

3. Final Answer:

   A group of transactions linked together and shared across the network -> Option D

4. Quick Check:

   Block = grouped shared transactions [OK]

Hint: Blocks group transactions and share them across the network [OK]

Common Mistakes:

• Thinking a block is just one piece of data
• Confusing blocks with encryption keys
• Believing blocks are software programs

3. Consider a simple blockchain network where each block contains a hash of the previous block. If the first block's hash is 'abc123', and the second block's hash is calculated as hash('abc123' + 'data2'), what happens if someone tries to change 'data2' in the second block?

medium

A. The first block's hash changes automatically

B. Nothing changes because hashes are not linked

C. The hash of the second block changes, breaking the chain

D. The network ignores the change and continues

Solution

1. Step 1: Understand hash linking in blocks

   Each block's hash depends on the previous block's hash and its own data.

2. Step 2: Effect of changing data in second block

   Changing 'data2' changes the second block's hash, which breaks the chain's integrity.

3. Final Answer:

   The hash of the second block changes, breaking the chain -> Option C

4. Quick Check:

   Changing data breaks hash chain [OK]

Hint: Changing block data changes its hash, breaking the chain [OK]

Common Mistakes:

• Thinking hashes are independent
• Believing first block changes automatically
• Assuming network ignores hash mismatches

4. A developer wrote this pseudocode for adding a new block to a distributed ledger:

function addBlock(data) {
  previousHash = getLastBlockHash()
  newHash = hash(data)
  block = { data: data, previousHash: previousHash, hash: newHash }
  ledger.append(block)
}

What is the main error in this code?

medium

A. The new hash should include the previous hash, not just data

B. The previous hash should be ignored when adding a block

C. The block should not store the previous hash

D. The ledger should be cleared before appending

Solution

1. Step 1: Review how block hashes are calculated

   A block's hash must include the previous block's hash and its own data to link blocks securely.

2. Step 2: Identify the mistake in hash calculation

   The code only hashes the data, missing the previous hash, breaking the chain security.

3. Final Answer:

   The new hash should include the previous hash, not just data -> Option A

4. Quick Check:

   Hash must include previous hash + data [OK]

Hint: Hash must combine previous hash and data to link blocks [OK]

Common Mistakes:

• Hashing only data without previous hash
• Ignoring previous hash in block structure
• Clearing ledger unnecessarily

5. You want to design a distributed ledger system where multiple participants can add transactions, but only valid transactions are accepted after consensus. Which approach best ensures data integrity and trust in this system?

hard

A. Use a consensus algorithm that requires agreement from most participants before adding a block

B. Allow any participant to add blocks without checks to speed up the process

C. Store the ledger on a single trusted server controlled by one participant

D. Encrypt all transactions so no one can see the data

Solution

1. Step 1: Understand consensus in distributed ledgers

   Consensus algorithms require most participants to agree on the data before adding it, ensuring trust.

2. Step 2: Evaluate options for data integrity and trust

   Allowing unchecked additions or central control reduces trust; encryption alone doesn't ensure consensus.

3. Final Answer:

   Use a consensus algorithm that requires agreement from most participants before adding a block -> Option A

4. Quick Check:

   Consensus ensures trust and data integrity [OK]

Hint: Consensus means most agree before adding data [OK]

Common Mistakes:

• Skipping consensus to speed up adding blocks
• Centralizing ledger storage
• Relying only on encryption without consensus