Reentrancy attacks in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Reentrancy attacks

O(n)

Understanding Time Complexity

When analyzing reentrancy attacks, we want to understand how the number of repeated calls affects the execution time.

We ask: How does the cost grow as the attacker repeatedly calls back into the contract?

Scenario Under Consideration

Analyze the time complexity of the following vulnerable Solidity function.

function withdraw(uint amount) public {
  require(balances[msg.sender] >= amount);
  (bool success, ) = msg.sender.call{value: amount}();
  require(success);
  balances[msg.sender] -= amount;
}
    

This function sends Ether to the caller before updating their balance, allowing repeated calls before state changes.

Identify Repeating Operations

Look for repeated calls that cause the function to run multiple times.

• Primary operation: Recursive external calls triggered by the attacker.
• How many times: Up to the attacker's balance, potentially many times.

How Execution Grows With Input

Each recursive call repeats the withdrawal until the balance is drained.

Input Size (balance n)	Approx. Operations
10	About 10 calls
100	About 100 calls
1000	About 1000 calls

Pattern observation: The number of calls grows linearly with the attacker's balance.

Final Time Complexity

Time Complexity: O(n)

This means the execution time grows directly with the number of repeated calls made by the attacker.

Common Mistake

[X] Wrong: "The function runs only once per withdrawal call."

[OK] Correct: Because the attacker can reenter the function multiple times before the balance updates, causing many executions.

Interview Connect

Understanding how repeated calls affect execution helps you spot vulnerabilities and reason about contract safety in real projects.

Self-Check

What if the balance was updated before sending Ether? How would the time complexity change?