Data Availability Sampling and Erasure Coding (Reed-Solomon) TODO
Concept
Reed-Solomon codes are erasure codes that treat k data symbols as the coefficients (or evaluations) of a polynomial, then evaluate that polynomial at n distinct points to produce n symbols. Because a degree-(k-1) polynomial is uniquely determined by any k distinct points, the original data can be reconstructed from any k of the n encoded pieces. The data availability problem arises because a block producer must be shown to have actually published its data, without every verifier downloading the whole thing. Extending the data with an erasure code creates a useful property: to hide the data, the producer must withhold a substantial fraction of the encoded pieces. Data availability sampling (DAS) exploits this: each light node requests a handful of pieces at random positions and accepts the block only if all of them arrive. Since a fixed fraction of pieces must be missing for the data to actually be unavailable, increasing the number of samples drives the probability of missing that unavailability down exponentially. This also requires a way to verify that each piece matches the committed data — for example a polynomial commitment scheme like KZG, or a fraud-proof mechanism — otherwise the producer could hand out pieces that were encoded incorrectly.
A rollup's safety ultimately comes down to whether its data was actually published, and DAS is what lets a light client verify that probabilistically without running a full node — so understanding it is essential to understanding the trust assumptions behind any service built on an L2.
Code & Formula
# 데이터 가용성 샘플링과 소거부호(Reed-Solomon) — k=4,n=8 시스터매틱 RS 부호로 조각 4개만으로 원본 복원.
# 원본 데이터를 다항식 평가값으로 삼아 보간한 뒤 8개 지점에서 평가해 조각을 만들고, 임의의 4조각으로 라그랑주 보간해 되살린다.
P = 257 # 8비트 심볼보다 큰 소수 (GF(p) 산술)
def lagrange_interpolate(xs, ys, x, p=P):
total = 0
n = len(xs)
for i in range(n):
xi, yi = xs[i], ys[i]
num, den = 1, 1
for j in range(n):
if i == j:
continue
num = (num * (x - xs[j])) % p
den = (den * (xi - xs[j])) % p
total = (total + yi * num * pow(den, p - 2, p)) % p
return total % p
k, n = 4, 8
data = [65, 66, 67, 68] # 원본 데이터 심볼 (예: 'A','B','C','D')
xs_known = list(range(k)) # 0,1,2,3 지점에 원본을 심는다 (systematic 배치)
# 원본 4점을 지나는 차수<=3 다항식을 8개 지점(0..7)에서 평가해 소거부호 조각을 만든다
shares = [lagrange_interpolate(xs_known, data, x) for x in range(n)]
print("원본 데이터:", data)
print("소거부호 조각 8개:", shares)
# 원본 조각(0~3)이 전부 사라지고 패리티 조각(4~7)만 남았다고 가정
available = [4, 5, 6, 7]
recovered = [lagrange_interpolate(available, [shares[i] for i in available], x) for x in range(k)]
print("원본 조각 전부 소실, 패리티 4개로만 복원:", recovered)
print("복원 성공 여부:", recovered == data)
def sampling_pass_prob_hidden_undetected(n, hidden, s):
"""숨겨진 조각을 표본 s개가 하나도 건드리지 못할 확률 (=DAS가 은닉을 놓칠 확률)."""
visible = n - hidden
if s > visible:
return 0.0
prob = 1.0
for i in range(s):
prob *= (visible - i) / (n - i)
return prob
print()
for s in (1, 2, 4, 8):
p_miss = sampling_pass_prob_hidden_undetected(n=8, hidden=4, s=s)
print(f"조각 절반이 숨겨졌을 때 샘플 {s}개로 은닉을 놓칠 확률: {p_miss:.4f}")
docs/code/algorithms/algorithms-61.py
Exercise
Implement a k=4, n=8 Reed-Solomon encoding over a small finite field, reconstruct the original data from any 4 pieces using Lagrange interpolation, and then calculate the probability that s random samples all succeed when half of the pieces are assumed to be withheld.
Practical Connection
If Verex runs on an L2, finality depends on settlement data actually being posted to the DA layer, so the design should define upfront what state market settlement is left in if data availability fails.
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/.