Lagrange Interpolation + Reed-Solomon (Thread A Payoff) TODO
Concept
Given k distinct points, a polynomial of degree at most k-1 is uniquely determined, and Lagrange interpolation constructs it explicitly by combining basis polynomials that equal 1 at one point and 0 at all the others. Reed-Solomon codes apply this fact directly to encoding: treat k data symbols as the coefficients of a polynomial, evaluate it at n distinct points, and use those values as the codeword — then any k of the n evaluations are enough to recover the original polynomial by interpolation. That makes it an MDS code with minimum distance n-k+1, able to recover from up to n-k erasures, and to correct errors at unknown positions up to half that many. The same structure underlies Shamir's secret sharing: put the secret in the constant term, hand out evaluations of a degree-(k-1) polynomial, and fewer than k shares reveal no information about the secret at all.
Using erasure codes instead of replication gets the same durability at a much lower storage cost, making it a fundamental tool for storage and transmission design; threshold signatures and data availability designs are both built on this same polynomial logic.
Code & Formula
# 라그랑주 보간 + Reed-Solomon — GF(p) 위에서 k=3,n=5 RS 인코딩 후 소실 2개 복구
# k개의 점으로 차수 k-1 다항식이 유일 결정된다는 사실을 그대로 부호화/복호화에 사용한다.
p = 97 # 작은 소수 유한체 GF(97)
def gf_inv(x):
return pow(x, -1, p)
def poly_eval(coeffs, x):
"""coeffs[i]는 x^i의 계수. Horner's method로 f(x) mod p 계산."""
y = 0
for c in reversed(coeffs):
y = (y * x + c) % p
return y
def lagrange_interpolate(points, x_target=0):
"""points = [(x_i, y_i), ...] 로부터 f(x_target)을 복원 (기본: 상수항 f(0))."""
total = 0
for i, (xi, yi) in enumerate(points):
num, den = 1, 1
for j, (xj, _) in enumerate(points):
if i == j:
continue
num = (num * (x_target - xj)) % p
den = (den * (xi - xj)) % p
total = (total + yi * num * gf_inv(den)) % p
return total
# 원본 데이터 3개 심볼(k=3)을 다항식 계수로 삼는다: f(x) = c0 + c1*x + c2*x^2
secret_data = [17, 42, 5] # c0=17(예: 복원 대상), c1=42, c2=5
k, n = 3, 5
# n=5개의 서로 다른 평가점(1..5)에서 계산한 값이 코드워드(RS 부호)
codeword = [(x, poly_eval(secret_data, x)) for x in range(1, n + 1)]
print("Reed-Solomon 코드워드 (x, f(x)):", codeword)
# 5개 중 2개(x=2, x=4)가 소실됐다고 가정 — k=3개만 있으면 복원 가능해야 한다
surviving = [pt for pt in codeword if pt[0] not in (2, 4)]
print("소실 후 살아남은 점:", surviving)
recovered_c0 = lagrange_interpolate(surviving, x_target=0)
print(f"라그랑주 보간으로 복원한 f(0)=c0: {recovered_c0} (원본과 일치: {recovered_c0 == secret_data[0]})")
# 전체 다항식(3개 계수) 자체도 세 점으로 완전히 복원되는지 확인 (x=0,1,2 세 지점에서 값 비교)
for x_check in (0, 1, 2, 3, 4, 5):
original = poly_eval(secret_data, x_check)
via_interp = lagrange_interpolate(surviving, x_target=x_check)
assert original == via_interp
print("모든 x에서 원본 다항식과 보간 결과 일치 (n-k=2개 소실까지 복구 가능, MDS 부호 성질).")
Exercise
Implement a k=3, n=5 Reed-Solomon encoder and a Lagrange-interpolation decoder over a small finite field, erase any two symbols, and confirm the original is recovered.
Practical Connection
Ethereum's blob data availability, KZG polynomial commitments, and threshold signatures for splitting oracle/relayer keys all use this interpolation-and-erasure-code structure, making it directly relevant background for designing Verex's oracle trust model.
Where it lands in Jayverse
- Bridge: split the lock-and-mint relayer's signing key with k-of-n Shamir sharing instead of one key. This directly fixes the single-relayer risk this batch's zkEVM PoC flags — compromising fewer than k shares reveals nothing.
- Verex: use threshold signing for any oracle or resolution-source key, not a single signer. A k-of-n scheme means no single compromised party can forge a resolution or a price feed.
- Number: if readings are ever redundantly distributed, use Reed-Solomon erasure coding instead of plain replication. It gets the same durability at lower storage cost, per this PoC's structure.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| uniquely determined | 유일하게 결정되는 · 조건이 주어지면 다항식이 하나로 정해질 때. "a polynomial of degree at most k-1 is uniquely determined" |
| underlie | ~의 기저를 이루다, 근간이 되다 · 한 구조가 다른 기법의 토대일 때. "underlies Shamir's secret sharing" |
| reveal no information about | ~에 대한 정보를 전혀 드러내지 않다 · 임계값 미만 조각이 비밀을 노출하지 않을 때. "fewer than k shares reveal no information about the secret" |
| fundamental tool for | ~을 위한 근본적인 도구 · 어떤 기법이 특정 분야의 핵심 수단일 때. "a fundamental tool for storage and transmission design" |
| at a much lower cost | 훨씬 낮은 비용으로 · 같은 효과를 더 저렴하게 얻을 때. "durability at a much lower storage cost" |
| directly relevant to | ~와 직접적으로 관련 있는 · 배경지식이 실제 설계와 바로 연결될 때. "directly relevant background for designing Verex's oracle trust model" |
| erasure | 소실, 삭제(데이터 유실) · 일부 조각이 사라진 상황을 가리킬 때. "recover from up to n-k erasures" |
| KZG | 케이트 다항식 커밋먼트(Kate–Zaverucha–Goldberg) · 이더리움 블롭 데이터가용성 등에 쓰이는 다항식 커밋먼트 기법. "blob data availability, KZG polynomial commitments, and threshold signatures" |
| MDS | 최대거리분리부호(Maximum Distance Separable code) · n-k+1의 최소거리를 갖는 부호, 손실 복구 능력을 규정. "That makes it an MDS code with minimum distance n-k+1" |
| Shamir's secret sharing | 샤미르 비밀분산 · 비밀을 상수항에 넣고 다항식 값을 나눠주는 구조, 리드-솔로몬과 같은 원리. "The same structure underlies Shamir's secret sharing" |
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/.