Time Complexity: Rollups (Optimistic vs ZK)
O(n) for Optimistic, O(1) for ZK
0
0
Rollups (Optimistic vs ZK) in Blockchain / Solidity - Performance Comparison
Understanding Time Complexity
When working with rollups in blockchain, it's important to understand how the time to process transactions grows as more data is added.
We want to know how the cost of verifying transactions changes with the number of transactions.
Scenario Under Consideration
Analyze the time complexity of verifying transactions in Optimistic and ZK Rollups.
// Simplified verification process
function verifyOptimistic(transactions) {
// Wait for challenge period
for (let tx of transactions) {
// Verify if any fraud proof submitted
}
return true;
}
function verifyZK(proof) {
// Verify zero-knowledge proof once
return verifyProof(proof);
}
This code shows how Optimistic Rollups verify by checking transactions after a delay, while ZK Rollups verify with a single proof.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: In Optimistic Rollups, verifying each transaction during the challenge period.
- How many times: Once per transaction, so as many times as there are transactions.
- In ZK Rollups: Verifying a single zero-knowledge proof regardless of transaction count.
- How many times: Only once per batch of transactions.
How Execution Grows With Input
As the number of transactions grows, Optimistic Rollups check each transaction, so work grows with the number of transactions.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 checks |
| 100 | 100 checks |
| 1000 | 1000 checks |
In ZK Rollups, verification is done once per batch, so operations stay about the same no matter how many transactions.
Final Time Complexity
Time Complexity: O(n) for Optimistic Rollups, O(1) for ZK Rollups
This means Optimistic Rollups take longer as transactions increase, while ZK Rollups keep verification time steady.
Common Mistake
[X] Wrong: "Both rollups verify transactions one by one at the same speed."
[OK] Correct: ZK Rollups verify all transactions together with one proof, so their verification time does not grow with more transactions.
Interview Connect
Understanding how different rollups handle verification helps you explain blockchain scaling clearly and shows you can think about efficiency in real systems.
Self-Check
"What if Optimistic Rollups used batch fraud proofs instead of per-transaction checks? How would the time complexity change?"