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