Pairings / KZG (Concept) TODO
Concept
A pairing is a bilinear map that takes elements from two elliptic curve groups and produces an element in a third group, letting you check a multiplicative relationship between exponents (scalars) just by looking at the group elements. This makes it possible to verify multiplicative relationships between hidden values, and it's the basis for BLS signatures and the verification equations of several proof systems. A KZG commitment commits a single polynomial to one constant-size group element, and lets you open a claim like f(z) = y at any point z with a proof that is also constant size. The principle is that f(X) − y is divisible by (X − z); submitting a commitment to that quotient polynomial as the proof lets the verifier confirm the division relationship with a single pairing check. The cost is that KZG requires a trusted setup that produces a structured reference string, and the fundamental assumption behind this scheme is that a leak of the secret used in that setup would allow forged proofs.
A significant portion of recent Ethereum infrastructure — blob data commitments, rollup proofs, signature aggregation — is built on pairings and polynomial commitments, so you can't read the design docs without the concept; the trusted-setup assumption is also the system's actual trust boundary.
Code & Formula
# 페어링/KZG(개념) — f(X)-f(z)가 (X-z)로 나누어떨어진다는 인수정리가 KZG 증명의 핵심
# 실제 KZG는 이 몫 다항식을 페어링 기반 커밋먼트로 압축하지만, 여기선 그 대수적 뼈대만 GF(p)에서 재현한다.
p = 101 # 작은 소수 유한체
def poly_eval(coeffs, x):
y = 0
for c in reversed(coeffs):
y = (y * x + c) % p
return y
def poly_sub_const(coeffs, c):
out = coeffs[:]
out[0] = (out[0] - c) % p
return out
def synthetic_division(coeffs, z):
"""(coeffs) / (X - z) 를 합성 나눗셈으로 계산. 몫의 계수와 나머지를 반환."""
n = len(coeffs)
quotient = [0] * (n - 1)
remainder = coeffs[-1]
for i in range(n - 2, -1, -1):
quotient[i] = remainder % p
remainder = (coeffs[i] + remainder * z) % p
return quotient, remainder
# 예시 다항식 f(X) = 5 + 3X + 2X^2 + X^3 (계수: [5,3,2,1], 상수항이 index 0)
f = [5, 3, 2, 1]
z = 7
y = poly_eval(f, z)
print(f"f(X) = 5 + 3X + 2X^2 + X^3, z={z} => y = f(z) = {y}")
# f(X) - y 는 반드시 (X - z)로 나누어떨어진다 (인수정리)
f_minus_y = poly_sub_const(f, y)
quotient, remainder = synthetic_division(f_minus_y, z)
print(f"몫 다항식 q(X) 계수 = {quotient}, 나머지 = {remainder} (0이어야 정상)")
assert remainder == 0
# "증명"이 성립함을 재구성으로 검증: q(X)*(X - z) + y 를 다시 펼치면 f(X)와 완전히 같아야 한다
def poly_mul(a, b):
out = [0] * (len(a) + len(b) - 1)
for i, ai in enumerate(a):
for j, bj in enumerate(b):
out[i + j] = (out[i + j] + ai * bj) % p
return out
reconstructed = poly_mul(quotient, [(-z) % p, 1]) # (X - z) = [-z, 1]
reconstructed[0] = (reconstructed[0] + y) % p
print("재구성한 f(X) 계수:", reconstructed, " 원본:", f, " 일치:", reconstructed == f)
print("\n실제 KZG는 이 q(X)를 SRS로 만든 상수크기 군 원소로 커밋하고, 검증자는 페어링 한 번으로")
print("commit(f) - y*G1 == commit(q) * (tau - z)*G2 관계를 확인한다 (여기선 다항식 자체로 원리만 재현).")
Exercise
Pick a simple polynomial, actually divide f(X) − f(z) by (X − z) to get the quotient, explain using the factor theorem why the remainder is always zero, and write up why that quotient serves as a proof.
Practical Connection
If Verex posts data to an L2 or aggregates multiple signatures, the cost and trust assumptions of that path ultimately come from pairing-based commitment structures.
Where it lands in Jayverse
- Verex: if the market maker or settlement path ever aggregates BLS signatures or posts KZG-style commitments, document the trusted setup's parameters and administrator as part of the resolution methodology. A leaked SRS secret breaks the whole proof silently, so it belongs in the trust-assumption list, not left implicit.
- Auditor: check that verification cost is actually cheaper than re-execution for the specific circuit used. The card's core claim only holds when this is confirmed per use case, not assumed because it's "a pairing-based system."
- Bridge: name the trusted-setup dependency for any blob or commitment structure the Anvil-Sepolia relayer or a future L2 posting relies on. Treat it as a fourth attack surface next to the relayer key and the multisig, not a separate cryptography concern.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| bilinear map | 쌍선형 사상 · 두 입력에 대해 각각 선형인 함수, 페어링의 정의. "a bilinear map that takes elements" |
| just by looking at | ~을 살펴보기만 해도, 간접적으로 확인함으로써 · 직접 계산 없이 원소만 보고 관계를 확인할 때. "just by looking at the group elements." |
| constant-size | 크기가 고정된(입력 크기와 무관한) · 증명·커밋먼트의 크기가 항상 동일할 때. "to one constant-size group element" |
| divisible by | ~로 나누어떨어지는 · 다항식이 특정 인수를 약수로 가질 때. "f(X) − y is divisible by (X − z)." |
| trusted setup | 신뢰된 설정(초기값 생성 과정) · 특정 비밀값이 안전하게 폐기되어야 하는 암호 설정. "requires a trusted setup that produces" |
| forged proofs | 위조된 증명 · 비밀이 유출되면 가짜 증명을 만들 수 있을 때. "would allow forged proofs" |
| trust boundary | 신뢰 경계 · 무너지면 시스템 전체 신뢰가 깨지는 지점. "the system's actual trust boundary" |
| BLS | BLS 서명(Boneh–Lynn–Shacham) · 페어링 기반 서명 방식, 여러 서명을 압축해 집계할 수 있음. "the basis for BLS signatures and the verification equations" |
| KZG | KZG 커밋먼트(Kate–Zaverucha–Goldberg) · 다항식을 상수 크기 원소 하나로 커밋하고 임의의 점에서 여는 증명 스킴. "A KZG commitment commits a single polynomial to one" |
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/.