Polynomial IOPs — the trade-off between proof size and verification time TODO
Concept
A polynomial IOP (Interactive Oracle Proof) is an abstract protocol in which the prover submits polynomials as oracles and the verifier queries their evaluations at random points, reducing the correctness of a computation to a polynomial identity check. This abstraction layer discusses only completeness and soundness without using any real cryptography; once the oracles are replaced with an actual polynomial commitment scheme (PCS) and the protocol is made non-interactive via Fiat-Shamir, it becomes a concrete SNARK or STARK. That's why arithmetization (R1CS, PLONKish, AIR) is decoupled from the commitment scheme, and a system's proof size, verification time, proving time, and whether it needs a trusted setup are mostly determined by the choice of PCS. Pairing-based KZG has constant-size commitments and evaluation proofs with very fast verification, but it requires a structured trusted setup and isn't quantum-resistant. Hash-based FRI needs no trusted setup and relies only on hash assumptions, but trades that off for proof size and verification cost that grow poly-logarithmically.
On-chain verification cost scales almost directly with proof size and verifier computation, so choosing a proof system is really choosing your gas cost and trust assumptions at the same time.
Code & Formula
# 다항식 IOP — Schwartz-Zippel 보조정리: 서로 다른 두 다항식이 랜덤 점에서
# 우연히 같은 값을 낼 확률은 차수/체 크기(p)에 비례해 작아진다 (증명 크기 vs 검증 시간의 근거).
import random
p = 65537 # 작은 소수 유한체 GF(p)
def poly_eval(coeffs, x, p):
# Horner's method, mod p
result = 0
for c in reversed(coeffs):
result = (result * x + c) % p
return result
def collision_rate(deg, trials, p):
f = [random.randrange(p) for _ in range(deg + 1)]
g = f.copy()
g[0] = (g[0] + 1) % p # f - g 는 0이 아닌 차수 deg 다항식
hits = 0
for _ in range(trials):
r = random.randrange(p)
if poly_eval(f, r, p) == poly_eval(g, r, p):
hits += 1
return hits / trials
trials = 20000
for deg in (1, 8, 64):
rate = collision_rate(deg, trials, p)
bound = deg / p # Schwartz-Zippel 상한: 최대 deg/|F| 확률로 충돌
print(f"deg={deg:3d} 관측 충돌률={rate:.6f} 이론 상한(deg/p)={bound:.6f}")
print("\n결론: 차수가 커질수록 충돌 확률 상한이 커지므로, 검증자가 신뢰할 수")
print("있으려면 체 크기 p 를 다항식 차수보다 충분히 크게 잡아야 한다.")
docs/code/algorithms/algorithms-92.py
Exercise
Experiment with the Schwartz-Zippel lemma over a small finite field, and check how the probability that two different polynomials happen to agree at a random point scales with their degree relative to the field size.
Practical Connection
Compressing large volumes of off-chain matching in a prediction market into an on-chain settlement requires rollup-style validity proofs, and choosing between KZG (small proofs, needs trusted setup) and FRI (transparent, larger proofs) simultaneously decides your settlement gas cost and your security assumptions.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-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/.