Big-O and Gas TODO
Concept
Big-O is an asymptotic upper bound describing how resource usage grows, within a constant factor, as input size grows — by definition it ignores constant multipliers and lower-order terms. Gas is the cost unit assigned to each operation in the EVM, and because transactions and blocks have gas limits, it means "the price tag of finite computation." The decisive difference between the two concepts is that gas is a concrete price list that includes the constants, so operations with large constants — like storage writes or hashing — can dominate total cost even in the small-n regime. Conversely, an O(n) loop over an entire array becomes a DoS vector if an attacker can grow n, since it eventually hits the block gas limit and the function becomes permanently unexecutable. So on-chain cost analysis has to look at both asymptotic order and per-operation constants, and always ask which inputs are under attacker control.
In on-chain code, slow code doesn't just run slowly — it can simply fail to execute at all and lock up funds. An array loop that can grow without bound is a real, documented vulnerability class.
Code & Formula
# Big-O & 가스 — "점근 차수"와 "연산별 상수"는 다르다는 걸 O(n) vs O(1) 조회 비교로 보여준다.
# 참여자 목록을 루프로 순회(O(n))하는 정산과, 매핑으로 바로 조회(O(1))하는 정산을 비교.
import time
GAS_PER_ITER = 3 # 루프 한 바퀴 도는 데 드는 가스(단순화한 상수)
GAS_PER_LOOKUP = 5 # 매핑(dict) 조회 1회 가스
def settle_by_scan(balances: list, target_id: int) -> int:
# O(n): 참여자 수만큼 전부 훑어야 target 을 찾는다 — 공격자가 n 을 키우면 가스가 비례 증가.
gas = 0
for pid, bal in balances:
gas += GAS_PER_ITER
if pid == target_id:
return gas
return gas
def settle_by_map(balance_map: dict, target_id: int) -> int:
# O(1): n 과 무관하게 상수 가스.
_ = balance_map[target_id]
return GAS_PER_LOOKUP
for n in (10, 100, 1_000, 10_000, 100_000):
balances = [(i, 100) for i in range(n)]
balance_map = dict(balances)
target = n - 1 # 최악의 경우: 리스트 맨 끝
gas_scan = settle_by_scan(balances, target)
gas_map = settle_by_map(balance_map, target)
print(f"n={n:>7} scan(O(n)) gas={gas_scan:>7} map(O(1)) gas={gas_map}")
BLOCK_GAS_LIMIT = 30_000_000
n_at_limit = BLOCK_GAS_LIMIT // GAS_PER_ITER
print(f"\n블록 가스 한도 {BLOCK_GAS_LIMIT:,} 기준, scan 방식은 참여자 수가 약 {n_at_limit:,} 명을")
print("넘으면 트랜잭션 하나로 정산이 아예 불가능해진다 — O(1) map 방식은 n 과 무관하게 안전.")
Exercise
Implement the same logic once as an O(n) array scan and once as an O(1) mapping lookup, measure gas as element count grows, and find roughly where n hits the block gas limit.
Practical Connection
If Verex settles by looping over a list of market participants or open orders, the settlement transaction starts failing as participants grow, so it needs to move to a constant-cost design like pull-based claims.
Where it lands in Jayverse
- Verex: audit every loop over an unbounded collection for a gas-limit DoS. Beyond settlement, check order cancellation, fee distribution, and any other function that iterates over participants or orders, and convert each to a pull-based or paginated design before participant count can grow past the block gas limit.
- CI: add a gas-growth test, not just a gas-snapshot test. Run the same function at increasing n (10, 100, 1000 participants) in CI and fail the build if gas grows without bound, rather than only snapshotting gas at a fixed small n.
- Bridge: check the relayer's per-batch mint/unlock loop the same way. If the bridge ever batches multiple lock events into one mint transaction, that loop needs the identical bound check before batch size is attacker- or user-controllable.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| price tag | 가격표, 대가 · 어떤 것에 드는 비용을 비유적으로 말할 때. "the price tag of finite computation" |
| dominate (cost) | 비용을 압도하다, 대부분을 차지하다 · 큰 상수항이 전체 비용을 좌우할 때. "can dominate total cost even in the small-n regime" |
| under attacker control | 공격자가 통제할 수 있는 · 입력값을 악의적으로 조작 가능한 상황. "always ask which inputs are under attacker control" |
| lock up (funds) | 자금을 묶어버리다, 못 쓰게 하다 · 실행 실패로 자산이 인출 불가능해질 때. "fail to execute at all and lock up funds" |
| grow without bound | 한없이 커지다, 무한정 늘어나다 · 값에 상한이 없을 때. "An array loop that can grow without bound" |
| hit (a limit) | 한계에 도달하다 · 값이 임계치에 이를 때. "it eventually hits the block gas limit" |
| within a constant factor | 상수 배 이내로 · 점근적 분석에서 상수를 무시하고 볼 때. "grow, within a constant factor, as input size grows" |
| pull-based claims | 풀 기반 클레임/인출 패턴(pull-based claim pattern) · 루프 대신 각자 인출을 요청하게 해 가스 비용을 상수화하는 설계. "move to a constant-cost design like pull-based claims" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.