Sidechains in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Sidechains

O(b x t)

Understanding Time Complexity

When working with sidechains, it's important to understand how the time to process transactions grows as more data is handled.

We want to know how the execution time changes when the number of blocks or transactions increases.

Scenario Under Consideration

Analyze the time complexity of the following sidechain block verification process.

function verifySidechainBlocks(blocks) {
  for (let block of blocks) {
    if (!verifyBlock(block)) {
      return false;
    }
  }
  return true;
}

function verifyBlock(block) {
  // Verify transactions inside the block
  for (let tx of block.transactions) {
    if (!verifyTransaction(tx)) {
      return false;
    }
  }
  return true;
}
    

This code checks each block in the sidechain and verifies all transactions inside each block.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each block and then each transaction inside the block.
• How many times: For each block, it loops through all its transactions.

How Execution Grows With Input

As the number of blocks and transactions grows, the total work grows too.

Input Size (blocks x transactions)	Approx. Operations
10 blocks x 10 tx	100
100 blocks x 10 tx	1,000
100 blocks x 100 tx	10,000

Pattern observation: The total operations grow roughly by multiplying the number of blocks by the number of transactions per block.

Final Time Complexity

Time Complexity: O(b × t)

This means the time to verify grows in proportion to the number of blocks times the number of transactions per block.

Common Mistake

[X] Wrong: "Verifying sidechain blocks takes constant time no matter how many blocks or transactions there are."

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

Interview Connect

Understanding how verification time grows helps you explain blockchain performance and scalability clearly, a useful skill in many blockchain roles.

Self-Check

"What if the verifyTransaction function itself loops through a list of signatures? How would that affect the time complexity?"

Practice

1.

What is the main purpose of a sidechain in blockchain technology?

easy

A. To store user passwords securely

B. To replace the main blockchain entirely

C. To mine new cryptocurrencies faster

D. To allow assets to move between blockchains without changing the main chain

Solution

1. Step 1: Understand sidechain function

   Sidechains connect to a main blockchain to move assets safely without altering the main chain.

2. Step 2: Compare options

   Only To allow assets to move between blockchains without changing the main chain describes this purpose correctly; others describe unrelated functions.

3. Final Answer:

   To allow assets to move between blockchains without changing the main chain -> Option D

4. Quick Check:

   Sidechains move assets safely = C [OK]

Hint: Sidechains move assets without changing main chain [OK]

Common Mistakes:

• Thinking sidechains replace main blockchain
• Confusing sidechains with password storage
• Assuming sidechains speed up mining

2.

Which of the following is the correct way to describe the process of moving assets from the main chain to a sidechain?

lockOnMainChain() and issueOnSidechain() are functions.

easy

A. issueOnSidechain(); lockOnMainChain();

B. lockOnMainChain(); issueOnSidechain();

C. burnOnMainChain(); issueOnSidechain();

D. issueOnSidechain(); burnOnMainChain();

Solution

1. Step 1: Understand asset transfer steps

   Assets are locked on the main chain first, then issued on the sidechain.

2. Step 2: Match function order

   lockOnMainChain(); issueOnSidechain(); correctly calls lockOnMainChain() before issueOnSidechain().

3. Final Answer:

   lockOnMainChain(); issueOnSidechain(); -> Option B

4. Quick Check:

   Lock then issue = A [OK]

Hint: Lock assets first, then issue on sidechain [OK]

Common Mistakes:

• Issuing before locking assets
• Using burn instead of lock for main chain
• Mixing function order

3.

Consider this pseudocode for moving assets from a sidechain back to the main chain:

burnOnSidechain()
unlockOnMainChain()

What will be the output if burnOnSidechain() fails?

medium

A. Assets remain locked on the main chain

B. Assets are unlocked on the main chain anyway

C. Assets are burned on the main chain

D. Assets are duplicated on both chains

Solution

1. Step 1: Analyze burn failure effect

   If burnOnSidechain() fails, assets are not removed from the sidechain.

2. Step 2: Understand unlock condition

   unlockOnMainChain() should only run after successful burn; if burn fails, unlock does not happen.

3. Final Answer:

   Assets remain locked on the main chain -> Option A

4. Quick Check:

   Burn must succeed before unlock = D [OK]

Hint: Burn sidechain assets before unlocking main chain [OK]

Common Mistakes:

• Assuming unlock happens even if burn fails
• Thinking assets get duplicated
• Confusing burn with lock

4.

Find the error in this pseudocode for transferring assets to a sidechain:

lockOnMainChain()
issueOnSidechain()
unlockOnMainChain()

medium

A. Unlocking main chain assets immediately after issuing is incorrect

B. Locking assets should happen after issuing

C. Issuing on sidechain should be replaced with burning

D. Unlocking main chain assets is required here

Solution

1. Step 1: Review transfer steps

   Assets must stay locked on the main chain until they are returned from the sidechain.

2. Step 2: Identify incorrect unlock

   Unlocking immediately after issuing breaks asset security; unlock should happen only when assets return.

3. Final Answer:

   Unlocking main chain assets immediately after issuing is incorrect -> Option A

4. Quick Check:

   Unlock only after return = A [OK]

Hint: Don't unlock main chain assets too early [OK]

Common Mistakes:

• Unlocking main chain assets too soon
• Confusing issue with burn
• Reversing lock and issue order

5.

You want to design a sidechain system that allows fast transactions but ensures no asset duplication. Which approach best achieves this?

Choose the correct sequence of actions when moving assets from main chain to sidechain and back.

hard

A. Issue on sidechain -> Lock on main chain -> Unlock on main chain -> Burn on sidechain

B. Burn on main chain -> Issue on sidechain -> Lock on sidechain -> Unlock on main chain

C. Lock on main chain -> Issue on sidechain -> Burn on sidechain -> Unlock on main chain

D. Unlock on main chain -> Burn on sidechain -> Lock on main chain -> Issue on sidechain

Solution

1. Step 1: Understand asset safety steps

   To avoid duplication, assets must be locked on the main chain before issuing on sidechain, and burned on sidechain before unlocking main chain.

2. Step 2: Match correct sequence

   Lock on main chain -> Issue on sidechain -> Burn on sidechain -> Unlock on main chain follows the correct order: lock -> issue -> burn -> unlock, ensuring assets exist only in one place at a time.

3. Final Answer:

   Lock on main chain -> Issue on sidechain -> Burn on sidechain -> Unlock on main chain -> Option C

4. Quick Check:

   Lock, issue, burn, unlock = B [OK]

Hint: Lock before issue; burn before unlock to avoid duplicates [OK]

Common Mistakes:

• Issuing before locking assets
• Unlocking main chain too early
• Burning assets on wrong chain