Cross-chain bridges in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Cross-chain bridges

O(n)

Understanding Time Complexity

When using cross-chain bridges, we want to know how the time to transfer assets grows as more transactions happen.

We ask: How does the work needed change when more users use the bridge?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function processBridgeTransfers(transfers) {
  for (let i = 0; i < transfers.length; i++) {
    verifyTransfer(transfers[i]);
    updateSourceChain(transfers[i]);
    updateDestinationChain(transfers[i]);
  }
}

function verifyTransfer(transfer) {
  // Check signatures and balances
}

function updateSourceChain(transfer) {
  // Lock tokens on source chain
}

function updateDestinationChain(transfer) {
  // Mint tokens on destination chain
}

This code processes a list of transfers by verifying and updating both chains for each transfer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that goes through each transfer in the list.
• How many times: Once for every transfer in the input array.

How Execution Grows With Input

As the number of transfers grows, the work grows in a straight line with it.

Input Size (n)	Approx. Operations
10	About 10 times the work
100	About 100 times the work
1000	About 1000 times the work

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

Final Time Complexity

Time Complexity: O(n)

This means the time to process transfers grows directly with how many transfers there are.

Common Mistake

[X] Wrong: "Processing multiple transfers takes the same time as one transfer."

[OK] Correct: Each transfer requires separate verification and updates, so more transfers mean more work.

Interview Connect

Understanding how work grows with input size helps you explain how blockchain bridges handle many users efficiently.

Self-Check

"What if the verifyTransfer function itself loops over a list of validators? How would the time complexity change?"

Practice

1. What is the main purpose of a cross-chain bridge in blockchain technology?

easy

A. To mine new blocks faster on a single blockchain

B. To increase the block size limit on a blockchain

C. To create new cryptocurrencies from scratch

D. To connect different blockchains and allow asset transfers between them

Solution

1. Step 1: Understand the role of cross-chain bridges

   Cross-chain bridges enable communication and asset transfers between different blockchains.

2. Step 2: Compare options with this role

   Only To connect different blockchains and allow asset transfers between them describes connecting blockchains and transferring assets, which matches the bridge's purpose.

3. Final Answer:

   To connect different blockchains and allow asset transfers between them -> Option D

4. Quick Check:

   Cross-chain bridge = connect blockchains [OK]

Hint: Bridges connect blockchains to move tokens or data [OK]

Common Mistakes:

• Confusing bridges with mining or block creation
• Thinking bridges create new cryptocurrencies
• Assuming bridges only increase block size

2. Which of the following is the correct basic step in a cross-chain bridge operation?

easy

A. Lock tokens on the source chain and mint equivalent tokens on the destination chain

B. Mint tokens on the source chain and burn on the destination chain

C. Burn tokens on the source chain and mine new tokens on the same chain

D. Transfer tokens directly without locking or minting

Solution

1. Step 1: Recall how cross-chain bridges work

   They lock tokens on the source chain to prevent double spending and mint equivalent tokens on the destination chain.

2. Step 2: Match this with the options

   Lock tokens on the source chain and mint equivalent tokens on the destination chain correctly describes locking on source and minting on destination, which is the standard process.

3. Final Answer:

   Lock tokens on the source chain and mint equivalent tokens on the destination chain -> Option A

4. Quick Check:

   Lock then mint = bridge step [OK]

Hint: Tokens are locked first, then minted on another chain [OK]

Common Mistakes:

• Mixing up minting and burning order
• Thinking tokens transfer directly without locking
• Assuming minting happens on source chain

3. Consider this simplified pseudocode for a cross-chain bridge function:

function bridgeTransfer(amount, sourceChain, destChain) {
  lockTokens(sourceChain, amount);
  mintTokens(destChain, amount);
  return 'Transfer complete';
}

What will be the output when calling bridgeTransfer(100, 'ChainA', 'ChainB')?

medium

A. 'Transfer complete'

B. Error: lockTokens undefined

C. 'Tokens locked on ChainA'

D. 100

Solution

1. Step 1: Analyze the function steps

   The function calls lockTokens and mintTokens, then returns the string 'Transfer complete'.

2. Step 2: Determine the output of the function call

   Assuming lockTokens and mintTokens work correctly, the function returns 'Transfer complete'.

3. Final Answer:

   'Transfer complete' -> Option A

4. Quick Check:

   Function returns 'Transfer complete' [OK]

Hint: Look at the return statement for output [OK]

Common Mistakes:

• Confusing function calls with return value
• Assuming intermediate functions print output
• Ignoring the return statement

4. The following code snippet is intended to lock tokens on the source chain and mint on the destination chain, but it has a bug:

function bridgeTransfer(amount, sourceChain, destChain) {
  lockTokens(destChain, amount);
  mintTokens(sourceChain, amount);
  return 'Transfer complete';
}

What is the bug in this code?

medium

A. The function uses incorrect function names

B. The lockTokens and mintTokens calls have swapped chain arguments

C. The function does not return any value

D. The amount parameter is missing

Solution

1. Step 1: Check the order of locking and minting

   Tokens should be locked on the source chain and minted on the destination chain.

2. Step 2: Identify the argument mismatch

   The code locks tokens on destChain and mints on sourceChain, which is reversed.

3. Final Answer:

   The lockTokens and mintTokens calls have swapped chain arguments -> Option B

4. Quick Check:

   Lock on source, mint on destination [OK]

Hint: Lock on source chain, mint on destination chain [OK]

Common Mistakes:

• Swapping source and destination chains
• Forgetting to return a value
• Using wrong function names

5. You want to design a cross-chain bridge that prevents double spending by ensuring tokens are locked before minting on the destination chain. Which approach best achieves this in a smart contract environment?

hard

A. Allow users to mint tokens on destination chain without locking on source chain

B. Mint tokens on destination chain first, then lock tokens on source chain

C. Use an event listener to confirm tokens are locked on source chain before minting on destination chain

D. Transfer tokens directly between chains without any locking or minting

Solution

1. Step 1: Understand double spending prevention

   Tokens must be locked on the source chain before minting on the destination chain to avoid duplicates.

2. Step 2: Evaluate approaches for enforcing this

   Using an event listener to confirm locking before minting ensures the correct order and security.

3. Final Answer:

   Use an event listener to confirm tokens are locked on source chain before minting on destination chain -> Option C

4. Quick Check:

   Confirm lock event before minting [OK]

Hint: Confirm lock event before minting tokens [OK]

Common Mistakes:

• Minting before locking causes double spending
• Allowing mint without lock breaks security
• Skipping locking or minting steps