Data Availability Sampling and Erasure Coding (Reed-Solomon) TODO

Algorithms · Day 61 / 100 · D. Distributed Systems & Consensus (Day 52-68)

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.

Where it lands in Jayverse

• Devnet: since a single-node Anvil fork can't demonstrate data availability sampling, treat "what happens to Verex settlement if DA fails" as a design doc item to write before Devnet moves toward a real L2/OP-Stack.
• Verex: define an explicit halt/fallback state for market settlement when the data-availability check fails, instead of assuming posted data is always available.
• Auditor: if Jayverse adopts an L2 later, require the light-client sampling parameters (sample count vs. target confidence) to be documented and checked, not just "we use an L2."

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

한국어

데이터 가용성 샘플링과 소거부호(Reed-Solomon) TODO

Algorithms · Day 61 / 100 · D. 분산시스템·합의 (Day 52–68)

개념

Reed-Solomon 부호는 k개의 데이터 심볼을 다항식의 계수(또는 평가값)로 보고 서로 다른 n개의 점에서 평가해 n개의 심볼을 만드는 소거부호로, 차수 k-1 다항식은 서로 다른 k개의 점으로 유일하게 복원되므로 임의의 k개 조각만 있으면 원본을 되살릴 수 있다. 데이터 가용성 문제는 블록 생산자가 데이터를 실제로 공개했는지를 전체를 내려받지 않고 확인해야 한다는 데서 생기며, 소거부호로 확장해 두면 '데이터를 감추려면 최소한 상당 비율의 조각을 감춰야 한다'는 성질이 만들어진다. 데이터 가용성 샘플링(DAS)은 이 성질을 이용해 각 라이트 노드가 무작위 위치의 조각 몇 개를 요청하고 모두 받으면 통과시키는 방식이며, 숨겨진 조각의 비율이 일정 이상이므로 샘플 수를 늘리면 감지 실패 확률이 지수적으로 줄어든다. 여기에 각 조각이 약속된 데이터와 일치하는지 검증하는 수단(예: KZG 같은 다항식 약속 또는 사기 증명)이 함께 필요하며, 그렇지 않으면 생산자가 잘못 부호화한 조각을 낼 수 있다.

롤업의 안전성은 결국 '데이터가 공개되었는가'에 달려 있고, 라이트 클라이언트가 풀 노드 없이도 이를 확률적으로 검증할 수 있게 해 주는 것이 DAS이므로 L2 위 서비스의 신뢰 가정을 이해하려면 필수다.

코드 · 수식

# 데이터 가용성 샘플링과 소거부호(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

연습

작은 유한체 위에서 k=4, n=8인 Reed-Solomon 인코딩을 직접 구현해 임의의 4개 조각으로 원본을 라그랑주 보간으로 복원해 보고, 조각 절반이 숨겨졌다고 가정할 때 샘플 s개가 모두 통과할 확률을 계산해 보라.

실무 · Verex 연결

Verex를 L2 위에서 운영한다면 정산 데이터가 DA 레이어에 실제로 게시되었는지가 최종성의 전제이므로, DA 실패 시 마켓 정산이 어떤 상태에 멈추는지 설계 단계에서 정의해 두어야 한다.

Jayverse에서의 위치

• Devnet: 단일 노드 Anvil 포크로는 데이터 가용성 샘플링을 보여줄 수 없으므로, Devnet이 실제 L2/OP-Stack으로 옮겨가기 전에 "DA가 실패하면 Verex 정산이 어떤 상태로 남는가"를 설계 문서 항목으로 미리 적는다.
• Verex: 데이터 가용성 체크가 실패했을 때 마켓 정산을 위한 명시적 정지/폴백 상태를 정의하고, 게시된 데이터가 항상 가용하다고 가정하지 않는다.
• Auditor: 나중에 Jayverse가 L2를 도입한다면 라이트 클라이언트 샘플링 파라미터(샘플 수 대비 목표 신뢰도)를 문서화하고 체크하도록 요구한다. "L2를 쓴다"는 진술만으로는 부족하다.

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