추상적인
본 연구에서는 샘플링 효율성 측면에서 Celestia, SPAR, Peer/Full DAS와 같은 기존 DAS 방식처럼 고정된 코드 집합에서 샘플링하는 대신, 온디맨드 샘플링 방식을 통해 레이트리스 코드, 특히 랜덤 선형 네트워크 코딩(RLNC)의 사용을 장려하고자 합니다.
고정 금리 코드를 사용하는 이유는 무엇인가요?
DAS에 코딩을 사용하게 된 원래 동기는 익명성 하에서 코딩되지 않은 데이터에서 샘플링할 경우, 1 - s/k 로 선형 k 으로 감소한다는 점이었습니다. 하지만, 예를 들어 (n,k) RS 코드를 적용하면, s 샘플링(비복원 추출)에 대한 오탐 확률은 (k-1/n)^s 보다 더 빠르게 감소합니다.
무율 코딩을 통한 샘플링 효율성 향상
고정 비율 코딩을 사용하면 검증기(라이트 클라이언트)는 본질적으로 미리 코딩된 n 개의 심볼 집합에서 샘플링하는 것으로 제한됩니다. 고정 비율 코딩된 데이터에서 샘플링할 때의 오탐 확률을 위에서 살펴보면 자연스럽게 다음과 같은 질문이 생깁니다. 왜 n 을 가능한 한 크게 만들어 적은 수의 샘플에서도 오탐 확률을 충분히 낮추지 않는 것일까요? 하지만 여기에는 다음과 같은 몇 가지 단점이 있습니다.
여기서 사용되는 코드는 일반적으로
n의 크기와(n,k)의 가능한 조합에 내재적인 제한이 있는 RS 코드와 같은 코드입니다.데이터 생산자의 저장 및 계산 비용은 PeerDAS와 같은 관리 노드로 샘플링 데이터를 분산하는 데 필요한 대역폭 비용과 함께 의도치 않게 증가할 수 있습니다.
이 문제에 대한 자연스러운 해결책은 저장 및 분산 병목 현상을 방지하기 위해 필요에 따라 샘플을 생성하는 것이며, 이는 자연스럽게 레이트리스 코드(rateless code)를 고려하게 만듭니다. 레이트리스 코드는 큰 n 에 대한 극한에서 최대 거리 분리 가능(MDS) 코드로 볼 수 있기 때문입니다. RLNC는 원본 데이터의 무작위 선형 조합을 생성하여 코딩된 패키지를 만드는 레이트리스 코드의 한 예입니다.
RLNC와 같은 코드에서 온디맨드 샘플링을 (1/q)^s 의 오탐지 확률이 발생하는데, 여기서 q 코딩 계수 필드의 크기를 나타냅니다. 이러한 프로토콜에 대한 자세한 설명은 다음 논문에 나와 있습니다. "인덱싱에서 코딩으로: 데이터 가용성 샘플링을 위한 새로운 패러다임 "
코딩된 데이터에서 샘플링할 때 거짓 음성 확률(기본 페이로드의 디코딩 불가능성이 감지되지 않음)(참조 [1],[2]).
진정한 탈중앙화의 가능성
고정율 코딩 데이터의 또 다른 단점은 샘플이 개별화되어 복구 절차에 많은 비용이 소요될 수 있다는 점입니다. 예를 들어 PeerDAS에서 사용되는 1D RS 코드의 경우, RS 코드로 인코딩된 블롭에서 단일 셀이 손실되면 RS 코드의 낮은 지역성 때문에 데이터를 재구성하기 위해 전체 블롭에 해당하는 데이터를 다운로드해야 합니다. 텐서 코드가 도입되면 이러한 문제는 개선되겠지만, RLNC와 같은 비정형 코드 또한 분산형 데이터 관리의 보다 탈중앙화된 버전을 제공할 수 있습니다.
@Nashatyrev 님이 RLNC를 사용하는 분산형 보관 프로토콜을 제안했는데, 이 프로토콜은 복구 대역폭뿐 아니라 배포 및 저장 오버헤드 측면에서도 우수한 특성을 보여줍니다.
참고 자료
[1] Al-Bassam, Mustafa, et al. “사기 및 데이터 가용성 증명: 라이트 클라이언트에서 유효하지 않은 블록 감지.” 국제 금융 암호화 및 데이터 보안 컨퍼런스 . 베를린, 하이델베르크: Springer Berlin Heidelberg, 2021.
[2] Yu, Mingchao, et al. “Coded merkle tree: 블록체인에서 데이터 가용성 공격 해결.” 국제 금융 암호화 및 데이터 보안 컨퍼런스 . Cham: Springer International Publishing, 2020.
