Multi-signature wallet concept in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Multi-signature wallet concept

O(n * m)

Understanding Time Complexity

When using a multi-signature wallet, multiple approvals are needed to complete a transaction.

We want to understand how the time to approve grows as more owners are added.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function executeTransaction(transaction, signatures) {
  let validCount = 0;
  for (let i = 0; i < owners.length; i++) {
    if (signatures.includes(owners[i])) {
      validCount++;
    }
  }
  if (validCount >= requiredSignatures) {
    process(transaction);
  }
}

This code checks how many owners have signed a transaction before executing it.

Identify Repeating Operations

• Primary operation: Loop through all owners to check signatures.
• How many times: Once for each owner in the wallet.

How Execution Grows With Input

As the number of owners grows, the code checks more signatures one by one.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The number of checks grows directly with the number of owners.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to verify signatures grows linearly with the number of owners and the number of signatures.

Common Mistake

[X] Wrong: "Adding more owners won't affect the time because signatures are checked all at once."

[OK] Correct: Each owner must be checked one by one, so more owners mean more checks and more time.

Interview Connect

Understanding how loops grow with input size helps you explain how blockchain wallets handle multiple approvals efficiently.

Self-Check

"What if the signatures were stored in a fast lookup structure like a set? How would the time complexity change?"

Practice

1. What is the main purpose of a multi-signature wallet in blockchain?

easy

A. To require multiple approvals before spending funds

B. To speed up transaction processing

C. To store private keys on a single device

D. To allow unlimited spending by one user

Solution

1. Step 1: Understand the multi-signature wallet concept

   A multi-signature wallet requires more than one person to approve a transaction before it can be executed.

2. Step 2: Identify the main purpose

   This setup protects funds by preventing a single user from spending money alone, increasing security.

3. Final Answer:

   To require multiple approvals before spending funds -> Option A

4. Quick Check:

   Multi-signature = multiple approvals [OK]

Hint: Multi-signature means multiple people must approve [OK]

Common Mistakes:

• Thinking it speeds up transactions
• Believing one user controls all funds
• Confusing it with single-key wallets

2. Which of the following is the correct way to define a multi-signature wallet threshold in Solidity?

easy

A. bool threshold = true;

B. uint8 threshold = '2';

C. string threshold = 2;

D. uint8 threshold = 1;

Solution

1. Step 1: Identify correct data type for threshold

   The threshold is a number representing how many signatures are needed, so an unsigned integer like uint8 is appropriate.

2. Step 2: Check syntax correctness

   Assigning a number directly to uint8 is correct. Using quotes or wrong types causes errors.

3. Final Answer:

   uint8 threshold = 1; -> Option D

4. Quick Check:

   Threshold is a number, use uint8 [OK]

Hint: Threshold is a number, use uint type without quotes [OK]

Common Mistakes:

• Using quotes around numbers
• Assigning string type to threshold
• Using boolean type for threshold

3. Given this Solidity snippet for a multi-signature wallet, what will be the value of isApproved after calling approveTransaction(1, msg.sender) if the threshold is 2 and only one approval is made?

mapping(uint => mapping(address => bool)) approvals;
uint8 threshold = 2;

function approveTransaction(uint txId, address approver) public {
  approvals[txId][approver] = true;
}

function isApproved(uint txId) public view returns (bool) {
  uint count = 0;
  for (uint i = 0; i < owners.length; i++) {
    if (approvals[txId][owners[i]]) {
      count++;
    }
  }
  return count >= threshold;
}

medium

A. true

B. false

C. Compilation error

D. Undefined behavior

Solution

1. Step 1: Understand approval counting logic

   The function counts how many owners approved the transaction and compares it to the threshold.

2. Step 2: Analyze given scenario

   Only one approval is made but threshold is 2, so count is 1 which is less than 2.

3. Final Answer:

   false -> Option B

4. Quick Check:

   Approvals < threshold = false [OK]

Hint: Approval count must meet threshold to be true [OK]

Common Mistakes:

• Assuming one approval is enough
• Ignoring threshold comparison
• Confusing approval mapping structure

4. Identify the bug in this Solidity function for approving transactions in a multi-signature wallet:

function approveTransaction(uint txId) public {
  approvals[txId][msg.sender] = true;
  if (isApproved(txId)) {
    executeTransaction(txId);
  }
}

function isApproved(uint txId) public view returns (bool) {
  uint count = 0;
  for (uint i = 0; i <= owners.length; i++) {
    if (approvals[txId][owners[i]]) {
      count++;
    }
  }
  return count >= threshold;
}

medium

A. Missing event emission after approval

B. approveTransaction should be external, not public

C. Loop condition should be < instead of <=

D. executeTransaction should not be called inside approveTransaction

Solution

1. Step 1: Check the for loop boundary

   The loop uses i <= owners.length, which causes out-of-bounds access because array indices go from 0 to length-1.

2. Step 2: Correct the loop condition

   Changing to i < owners.length prevents accessing invalid index and runtime errors.

3. Final Answer:

   Loop condition should be < instead of <= -> Option C

4. Quick Check:

   Array index out of bounds fixed by < [OK]

Hint: Array loops use < length, not <= length [OK]

Common Mistakes:

• Using <= in loops causing errors
• Ignoring array index limits
• Thinking event emission fixes logic bugs

5. You want to create a multi-signature wallet that requires 3 out of 5 owners to approve a transaction. Which approach correctly enforces this rule in Solidity?

mapping(uint => mapping(address => bool)) approvals;
address[5] owners;
uint8 threshold = 3;

function executeTransaction(uint txId) public {
  uint count = 0;
  for (uint i = 0; i < owners.length; i++) {
    if (approvals[txId][owners[i]]) {
      count++;
    }
  }
  if (count >= threshold) {
    // execute the transaction
  } else {
    revert("Not enough approvals");
  }
}

hard

A. This code correctly enforces the 3-of-5 approval rule

B. The threshold should be set to 5 to require all owners

C. The loop should iterate over approvals, not owners

D. Revert should be replaced with a simple return statement

Solution

1. Step 1: Analyze the approval counting logic

   The code counts how many owners approved the transaction by checking the approvals mapping for each owner.

2. Step 2: Check threshold enforcement

   If the count is at least the threshold (3), the transaction executes; otherwise, it reverts with an error.

3. Final Answer:

   This code correctly enforces the 3-of-5 approval rule -> Option A

4. Quick Check:

   Count approvals >= threshold = enforce rule [OK]

Hint: Count approvals, compare with threshold, revert if not met [OK]

Common Mistakes:

• Setting threshold incorrectly
• Looping over wrong data structure
• Using return instead of revert for errors