Polynomial IOPs — the trade-off between proof size and verification time TODO

Algorithms · Day 92 / 100 · F. Cryptography & ZK (Day 82-96)

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.

Where it lands in Jayverse

• Verex: write down which PCS (KZG vs FRI) is chosen for rollup-style settlement proofs, and why, as an Auditor-style methodology note. Gas cost and trust assumptions are one decision — record it, don't just pick it.
• Devnet: prototype the settlement-proof PoC on devnet first, one market's worth of matches, before committing to a PCS. A trusted-setup requirement (KZG) is a one-way door once anything is mainnet-adjacent.
• Auditor: once a PCS is chosen, track proof size and verifier gas cost as a recurring regression check. So on-chain settlement cost doesn't silently drift as the circuit grows.

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/.

한국어

다항식 IOP TODO

Algorithms · Day 92 / 100 · F. 암호학·ZK (Day 82–96)

증명 크기 대 검증 시간 트레이드오프

개념

다항식 IOP(Interactive Oracle Proof)는 증명자가 다항식을 오라클로 제출하고 검증자가 무작위 점에서의 평가를 질의하는 추상 프로토콜로, 계산의 정당성을 다항식 항등식 검사로 환원한다. 이 추상 계층은 실제 암호를 쓰지 않고 완전성·건전성만 논하며, 오라클을 실제 다항식 커밋먼트 스킴(PCS)으로 바꾸고 Fiat-Shamir로 비대화형화하면 구체적인 SNARK/STARK가 된다. 그래서 산술화(R1CS, PLONKish, AIR)와 커밋먼트 방식이 분리되고, 시스템의 증명 크기·검증 시간·증명 시간·신뢰 설정 여부는 대부분 PCS 선택에서 갈린다. 페어링 기반 KZG는 커밋먼트와 평가 증명이 상수 크기이고 검증이 매우 빠르지만 구조화된 신뢰 설정이 필요하고 양자 내성이 없다. 해시 기반 FRI는 신뢰 설정이 필요 없고 해시 가정만 쓰지만 증명 크기와 검증 비용이 로그 제곱 규모로 커지는 트레이드오프를 갖는다.

온체인 검증 비용은 증명 크기와 검증자 연산량에 거의 비례하므로, 어떤 증명 시스템을 쓰느냐가 곧 가스비와 신뢰 가정의 선택이 된다.

코드 · 수식

# 다항식 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

연습

작은 유한체에서 Schwartz-Zippel 보조정리를 직접 실험해, 서로 다른 두 다항식이 랜덤 점에서 우연히 같은 값을 낼 확률이 차수/체 크기에 어떻게 비례하는지 확인해 볼 것.

실무 · Verex 연결

예측시장의 대량 오프체인 체결을 온체인에 압축해 정산하려면 rollup식 유효성 증명이 필요하고, 이때 KZG(작은 증명, 신뢰 설정)와 FRI(투명성, 큰 증명) 중 무엇을 고르느냐가 정산 가스와 보안 가정을 동시에 결정한다.

Jayverse에서의 위치

• Verex: 롤업식 정산 증명에 어떤 PCS(KZG vs FRI)를 선택했는지, 왜 선택했는지를 Auditor 스타일 방법론 노트로 적어둔다. 가스 비용과 신뢰 가정은 하나의 결정이다. 그냥 고르지 말고 기록한다.
• Devnet: PCS를 확정하기 전에 마켓 하나 분량의 매칭으로 정산 증명 PoC를 devnet에서 먼저 시제작한다. 트러스티드 세팅업 요구사항(KZG)은 메인넷에 가까워지는 순간 되돌릴 수 없는 문이 된다.
• Auditor: PCS를 선택한 후에는 증명 크기와 검증 가스 비용을 반복 회귀 검사 항목으로 추적한다. 회로가 커지면서 온체인 정산 비용이 조용히 흘러가지 않도록 한다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.