[Celestia Series] 3. Data Availability Problem과 솔루션

Published in

Decipher Media ｜디사이퍼 미디어

20 min readJul 16, 2022

서울대학교 블록체인 학회 디사이퍼(Decipher) Celestia팀에서 최초의 데이터 가용성 네트워크인 Celestia에 대한 글을 시리즈로 연재합니다. 본 시리즈는 모듈러 블록체인을 자세히 설명한 한국어로 된 아티클이 적다는 문제의식에서 출발해, Celestia에 한정짓지 않고 데이터 가용성 및 모듈러 블록체인의 개념을 포괄적으로 설명하였습니다. 글에 들어가기 앞서서, 필자는 Celestia와 아무런 연관이 없음을 밝힙니다.

Celestia Series

1. 모듈러 블록체인이란
2. 연산 레이어와 데이터 저장
3. Data Availability Problem과 솔루션
4. Celestia의 사용 예시
5. Celestia의 특징과 다른 솔루션들

Author

nmlyh of Decipher Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media) Reviewed By 정재환

1. 블록체인 용량 문제와 라이트노드의 필요성.

블록체인의 용량은 시간이 지남에 따라 증가할 수밖에 없고 무거운 용량은 노드 중앙화와 사용성 저하 문제로 이어집니다. 블록체인은 트랜잭션을 기록하는 장부입니다. 시간이 지날수록 더 많은 트랜잭션을 처리할수록 장부는 더 무거워집니다. 장부가 무거워지면 관리하기 힘들어지고 거래를 검증하는데 걸리는 시간도 증가합니다.

이더리움의 모든 데이터를 기록한 장부의 경우 현재 크기가 10TB입니다. 2019년 약 2.5TB에서 3년 만에 4배 증가했습니다. 일반 사용자들의 컴퓨터 스토리지 성장률보다 훨씬 빠르게 증가하고 있습니다. 다행히 트랜잭션을 검증하기 위해 10TB의 데이터가 모두 필요한 것은 아닙니다. 하지만 검증을 위해 노드가 저장해야 하는 데이터는 현재 약 600GB에 달하기 때문에 여전히 일반 사용자가 운용할 수 있는 수준이 아닙니다. 초당 트랜잭션 생산량이 15개인 이더리움이 이 정도인 것을 감안하면 TPS가 100, 1000 혹은 그 이상인 다른 레이어1은 기간이 짧더라도 블록체인 용량이 훨씬 크다는 것을 짐작할 수 있습니다. 높은 확장성을 자랑하는 솔라나의 경우 매년 약 4peta bytes의 데이터를 생성합니다. 이렇듯 대부분의 블록체인은 일반 컴퓨터의 스토리지 용량 증가량보다 훨씬 더 빠르게 데이터를 생성하기 때문에 일반 사용자의 네트워크 참여가 점점 더 힘들어지고 있습니다.

증가하는 블록체인 용량으로 인해 일반 사용자의 풀노드 운영이 힘들어지면서 노드 운영이 중앙화되기 시작했고 이는 사용성 저하로 이어집니다. 블록체인을 사용하기 위해서는 풀노드, 라이트노드, trusted remote node(ex. Infura) 중 하나를 선택해 체인과 통신해야 합니다. 사용자 입장에서 풀노드를 사용하는 것이 블록체인과 직접 상호작용할 수 있고 트랜잭션을 스스로 검증할 수 있어 가장 안전한 방식이지만 용량이 크기 때문에 사용이 힘듭니다. 그 뿐만 아니라 앞서 살펴본 것과 같이 블록체인 용량은 일반 컴퓨터의 스토리지 증가량 보다 훨씬 빠른 속도로 증가하기 때문에 운영 비용이 크고 지속적으로 증가합니다. 때문에 일반 사용자가 풀노드를 운영하는 것은 사실상 불가능합니다. 그 때문에 현재 대부분의 사용자는 Infura와 같은 중앙 집중식 풀노드인프라를 사용합니다. 이런 방식이 효율적일 수 있지만 해당 노드에 문제가 생기면 체인이 정상적으로 작동하지만 dapp을 사용하거나 트랜잭션을 보낼 수 없게 됩니다. ‘어차피 고쳐 줄 텐데 기다리면 되지 뭐’라는 생각을 할 수도 있지만 이것은 긴박한 상황에서 큰 문제로 이어질 수 있습니다. 예를 들어 선물 거래 dapp을 사용하고 있다고 해봅시다. 높은 시장 변동성으로 시장이 급락하면 많은 특정 노드에 트래픽이 급격하게 몰리면서 해당 노드가 다운될 수 있습니다. 그렇게 되면 블록체인이 정상적으로 작동하지만 시장에 대응하지 못해 청산 당할 수도 있습니다. Dex에 큰 규모의 lp를 공급한 경우에도 시장 상황에 대응하는 것이 중요한데 이때 lp를 빼지 못해 큰 손실이 발생할 수 있습니다. 이렇듯 기존의 블록체인에서 풀노드의 중앙 집중화는 필연이고 이는 사용성 악화로 이어질 수 있습니다. 이 문제는 특히 사용자가 급증하는 상황에서 두드러져 블록체인의 mass adoption을 저해하는 요소가 될 수 있습니다.

2. Fraud proof의 한계와 data availability problem.

블록체인 네트워크 모델(출처 : Fraud and Data Availability Proofs)

라이트노드를 사용하면 낮은 컴퓨팅 파워로 블록체인을 사용할 수 있어 노드 중앙화로 인해 발생할 수 있는 문제를 해결할 수 있습니다. 라이트노드는 검증에 필요한 모든 데이터를 저장하는 풀노드와 달리 요약 정보가 담긴 블록 헤더만 저장하기 때문에 낮은 사양으로도 블록체인을 사용할 수 있습니다. 최소한의 데이터로 풀노드에 데이터를 요청하고 블록체인과 상호작용할 수 있고 풀노드가 제공하는 fraud proof를 통해 검증에도 참여할 수 있어 사용자가 분산되고 안전한 방식으로 블록체인에 액세스할 수 있도록 합니다. 그 때문에 사용자 입장에서 라이트노드는 꼭 필요한 선택지입니다. 하지만 데이터를 저장하고 있지 않아 새로 들어온 블록에 대해서 스스로 검증하는 것이 불가능해 보안을 풀노드에 의존해야 한다는 한계가 있습니다.

Fraud proof 시스템 아키텍처(출처 : Fraud and Data Availability Proofs)

풀노드는 Fraud proof를 통해 라이트노드에 보안을 제공합니다. Fraud proof는 블록에 Invalid transaction이 포함됐을 때 풀노드가 생성하는 증명입니다. Fraud proof는 Invalid transaction이 포함된 블록 파트, 해당 파트에 대한 merkle proof 등으로 구성돼있습니다. 라이트노드는 fraud proof를 받으면 VerifyTransitionFraudProof를 통해 fraud proof를 검증하고 참인 경우 해당 블록을 거부합니다. Fraud proof의 이점은 라이트노드가 전체 블록체인 데이터 없이도 블록에 invalid 트랜잭션이 없다고 확신할 수 있다는 점과 모든 상태 전환에 필요한 것이 아니라 문제가 발생한 것으로 추정되는 경우에만 사용할 수 있다는 것입니다. 하지만 이러한 fraud proof에는 한계가 존재합니다. 앞서 살펴보았듯이 fraud proof에는 invalid 트랜잭션이 있는 블록 파트, 해당 파트에 대한 merkle proof 등 블록 데이터가 필요합니다. 만약 해당 데이터가 없다면 증명 생성이 불가능합니다. 공격자는 블록 데이터를 인위적으로 숨겨 fraud proof 생성을 방해할 수 있습니다. 이런 블록을 받은 풀노드 운영자는 숨겨진 데이터가 있다는 것을 확인하고 거부할 수 있습니다. 하지만 숨겨진 데이터로 인해 풀노드는 라이트노드에게 보낼 fraud proof를 생성할 수 없게 되고 블록 검증을 fraud proof에 의존하는 라이트노드는 해당 블록이 사용 가능한 것으로 인식하게 됩니다. 예를 들어 Alice가 tx1(invalid), tx2,,,txn이 포함된 블록을 만들었고 tx1을 숨긴 블록을 브로드 캐스트했다고 해봅시다. 해당 블록을 받은 풀노드는 블록에 숨겨진 정보가 있음을 알고 거부할 수 있습니다. 하지만 해당 트랜잭션 데이터를 알 수 없기 때문에 fraud proof를 생성할 수 없습니다. fraud proof 생성이 불가능하기 때문에 라이트노드는 Alice가 보낸 블록에 잘못된 데이터가 있다는 것을 알 수 없게 됩니다. 이렇듯 fraud proof는 공격자로부터 라이트노드를 보호하는 데 한계가 있습니다.

Data availability problem은 라이트노드가 새 블록을 받았을 때 해당 블록의 모든 데이터가 실제로 네트워크에 게시되었고 유효한지 확신할 수 없기 때문에 발생하는 문제입니다. 앞서 살펴보았듯이 라이트노드는 블록 헤더만 저장하고 있기 때문에 새로 받은 블록을 스스로 검증할 수 없습니다. 이런 문제를 해결하기 위해 fraud proof가 도입됐지만 공격자가 데이터를 숨기면 증명 생성 자체가 불가능하다는 한계가 존재합니다. 이에 따라 라이트노드는 새 블록을 받았을 때 해당 블록이 올바르다고 확신할 수 없게 됩니다. 풀어서 설명하면 라이트노드는 fraud proof를 받지 못한 경우에도 해당 블록에 잘못된 데이터가 포함됐을 가능성이 존재하기 때문에 최신 블록에 대해 확신할 수 없습니다. 이러한 문제를 data availability problem라고 부릅니다. 이에 대한 가장 쉬운 해결책은 라이트 클라이언트가 스스로 검증할 수 있도록 하는 것입니다. 하지만 그렇게 하기 위해서는 라이트노드가 검증에 필요한 데이터를 저장하고 있어야 하는데 이는 풀노드와 같게 되는 것이기 때문에 의미 없는 해결책입니다. 올바른 data availability problem 솔루션은 라이트노드가 작은 리소스로도 data availability 을 확보할 수 있도록 하는 것입니다.

3. Erasure coding과 NMT

Celestia는 2d reed-solomon encoding scheme을 통해 라이트노드가 풀노드에 의존하지 않고 data availability을 확인할 수 있도록 합니다.

3.1 Erasure coding

Erasure coding은 라이트노드가 전체 데이터 없이 data availability problem 를 해결할 수 있도록 하는 핵심 기술입니다. Erasure coding을 이해하기 위해서는 패리티에 대해 알아야 합니다. 패리티는 정보 전달 과정에서 오류가 발생했음을 검증하는데 사용되는 데이터입니다. 예를 들어 0011000 7비트의 데이터를 전송한다고 해봅시다. 데이터를 전송할 때 해당 1의 개수가 짝수임을 나타내는 패리티 비트 1을 추가해 10011000을 전송하면 수신처에서 해당 데이터에 오류가 있는지 없는지 체크할 수 있습니다. 짝수 패리티가 1인데 1의 개수가 홀수라면 해당 데이터 전송 과정에서 오류가 발생했다고 판단할 수 있습니다. Erasure coding은 데이터의 일부로 전체 데이터를 복구할 수 있도록 하는 데이터 확장 방식입니다. 데이터를 여러 조각으로 분할한 다음 데이터 복구에 사용할 수 있는 패리티 데이터를 만듭니다. n 크기의 데이터 중에서 k 크기의 데이터만 있어도 원래 데이터를 복구할 수 있도록 합니다. 이때 k/n을 코드율이라고 부릅니다. 이 값이 작다면 전체 데이터를 복구하는 데 필요한 데이터의 크기가 작아도 된다는 의미입니다. Erasure coding의 간단한 예시는 다음과 같습니다. n = k+1라고 가정 해봅시다. 원본 데이터가 ‘1, -1, 3, -4’입니다. 이때 ‘, -1, 3, -4’가 전송됐다고 해봅시다. 이것을 복원할 수 있는 데이터로는 무엇이 있을까요? 전체 데이터의 합을 추가하면 복원할 수 있습니다. 원본 데이터의 끝에 전체 데이터의 합을 추가해 ‘1, -1, 3, -4, -1’이 되면 ‘, -1, 3, -4, -1’을 보냈을 때 계산을 통해 첫 번째 데이터를 복원할 수 있습니다.

Reed-solomon은 가장 대표적인 Erasure coding 기법으로 네트워크를 통해 전송되는 손상된 데이터를 복구하는 데 사용됩니다. Reed-solomon code는 인코더에서 원래 데이터 비트에 패리티 비트를 추가해 보냅니다. 디코더는 수신된 데이터에서 오류를 찾고 수정합니다. 원본 데이터가 n이라고 했을 때 전송될 때 쓰이는 message bits는 k bits이고 패리티 비트는 t(=n-k) bits입니다. 디코더는 최대 t/2개의 오류를 수정할 수 있고, k bits를 활용해 다항식을 복원하여 n-k개의 데이터를 복원할 수 있습니다.

**2D Reed-Solomon Encoding Scheme자료구조(출처 :** **셀레스티아**)

Celestia는 2d reed-solomon encoding scheme라는 특수 인코딩 체계를 사용합니다. 블록 데이터를 패리티 데이터가 있는 더 큰 정사각형으로 erasure coding을 통해 인코딩합니다. 원본 데이터를 kk 행에 배치하고 각각의 행과 열마다 reed-solomon encoing을 적용해 Q0를 Q1, Q2 행렬로 확장합니다. 즉 각 행과 열을 인코딩합니다. 그런 다음 Q2를 수평으로 인코딩해 Q3를 생성해 2K2K 행렬을 만듭니다. Q1, Q2는 Q0의 패리티 데이터이고 Q3는 Q2의 패리티 데이터로 데이터 복원에 사용됩니다. 이를 통해 데이터를 복원할 뿐만 아니라 Erasure coding된 패리티 데이터 올바른지도 검증할 수 있습니다. Celestia는 2D Reed-Solomon Encoding Scheme를 활용해 data availability sampling을 진행합니다. Data Availability Sampling에 대해서는 ‘Celestia의 라이트노드’에서 알아보도록 하겠습니다.

3.2 NMT

Celestia는 data availability 레이어로 여러 개의 실행 레이어가 올라가고 그들의 데이터를 저장합니다. 각각의 실행 레이어는 자신들의 데이터만 확인하면 되기 때문에 다른 실행 레이어의 데이터는 필요없습니다. 때문에 각각의 레이어가 필요로 하는 데이터에 효율적으로 접근할 수 있도록 해야 합니다. 이를 위해 Celestia는 NMT를 도입했습니다. NMT는 namespaced merkle tree의 약자로, 메시지의 namespace에 따라 리프의 순서가 결정되는 머클 트리입니다. 각각의 실행 레이어는 namespace으로 식별됩니다. 트리의 각 노드는 각 노드의 모든 하위 리프에 있는 메시지의 namespce 범위를 포함하는 순서화된 머클 트리입니다. 트리의 리프 순서는 메시지의 namespace 식별자에 따라 결정됩니다. Namespace ID를 반환하는 함수 ns가 있다고 해봅시다. ID가 nid인 실행 레이어의 클라이언트는 해당 실행 레이어의 상태에만 관심이 있기 때문에 ns = nid인 원장의 메시지를 읽는 것에만 관심이 있습니다. 이를 통해 각각의 실행 레이어는 원하는 데이터에 쉽게 접근할 수 있습니다. 다음과 같은 구조로 이루어져있습니다.

type NamespacedMerkleTree struct {
	// this can be used to efficiently lookup the range for an
	// existing namespace without iterating through the leaves
	namespaceRanges map[string]leafRange
	minNID          namespace.ID
	maxNID          namespace.ID
}

핵심이 되는 부분은 namespaceRanges와 minNID, maxNID입니다. minNID와 maxNID는 해당 노드의 자식 노드들이 갖는 NID의 범위를 나타냅니다. 이를 활용해 탐색의 범위를 효율적으로 조절할 수 있습니다. 예시를 통해 살펴보도록 하겠습니다.

Namespaced merkle tree 예시 (출처 : LazyLedger백서)

N = X, Y에서 X는 minNID, Y는 maxNID입니다. 각 노드의 리프인 M = X에서 X는 해당 메시지가 속하는 실행 레이어의 NID입니다. 노드의 minNID, maxNID이 같아지는 노드의 리프는 해당 NID에 해당하는 메시지가 있습니다. 이런 머클 트리 구조를 사용해 여러 실행 레이어의 데이터를 효율적으로 탐색합니다. NID가 0003인 데이터를 찾는다고 했을 때 N6노드에서 N5의 하위 노드는 살펴볼 필요가 없고 N4의 하위 노드만 살펴보면 됩니다. 탐색의 범위가 크게 줄어드는 것을 알 수 있습니다. minNID와 maxNID가 없었다면 원하는 데이터를 찾기 위해 전체 트리를 탐색해야 하고 그 비용은 상당할 것입니다.

4. Celestia의 라이트노드와 DAS의 경쟁력

Celestia의 라이트노드는 2d reed-solomon encoding scheme을 활용한 das를 통해 블록의 data availability을 풀노드에 의존하지 않습니다. DAS란 블록 데이터의 일부 값을 추출하는 것을 의미합니다. 라이트노드들은 das를 통해 소량의 데이터를 모읍니다. 모인 데이터 블록이 25% 이상이 되면 풀노드는 2d reed-solomon encoding scheme를 통해 원본 데이터를 복구할 수 있습니다. 블록의 내용이 모두 확보됐기 때문에 풀노드는 fraud proof를 라이트노드에게 제공할 수 있습니다. 즉 악의적인 블록 생성자가 블록 데이터를 숨기더라도 2d reed-solomon encoding scheme으로 복구가 가능하기 때문에 data availability problem가 발생하지 않습니다. 만약 악의적인 블록 생성자가 데이터 블록을 제공하지 않는다면 라이트노드는 sampling test에 실패할 것이고 fraud proof 없이 블록 생성자가 악의적이라는 것을 알 수 있습니다. 기존의 블록체인에서는 블록 생성자가 데이터를 숨기면 풀노드는 fraud proof를 생성할 수 없어 라이트노드가 잘못된 블록을 승인할 수 있지만 Celestia에서는 라이트노드가 data availability sampling에 참여하기 때문에 데이터를 숨기면 승인을 거부할 수 있고 데이터를 숨기지 않고 잘못된 데이터를 보내더라도 풀노드가 draud proof를 생성할 수 있기 때문에 악의적인 참여자의 공격으로부터 라이트노드를 안전하게 보호할 수 있습니다.

Celestia의 data availability 네트워크는 라이트, 풀, 브릿지 노드로 구성돼 있습니다. 라이트노드는 앞서 살펴본 것처럼 da 네트워크에서 sampling을 수행해 블록 데이터의 가용성을 확인합니다. 풀노드는 da 네트워크에서 sampling을 통해 가용성 확인을 넘어 블록을 완전히 재구성합니다. 브릿지 노드는 Celestia 합의 네트워크에서 da 네트워크를 이어주는 역할을 수행합니다. 이들의 작동 방식은 다음과 같습니다.

브릿지노드가 header를 네트워크에 전파합니다.
라이트노드는 헤더의 데이터 루트에 대해 data availability sampling 수행합니다.
풀 노드는 라이트노드가 sampling한 데이터를 기반으로 원본 데이터를 복구합니다.

Celestia의 das는 sampling에 참여하는 노드의 숫자가 증가하면 더 큰 블록 생성이 가능합니다. 모놀리식 블록체인에서 블록 크기를 키우면 노드 사양을 높여야 하기 때문에 중앙화 문제가 발생할 수 있습니다. 반면 Celestia는 개별 노드의 사양에 따라 블록의 크기가 증가하는 것이 아니라 데이터 sampling에 참여하는 라이트노드의 숫가자 증가하면 블록의 크기가 커지기 때문에 탈중앙화와 확장성을 함께 확보할 수 있습니다. 이것이 가능한 이유는 das의 특성 덕분입니다. das는 더 많은 데이터 조각이 모일 수록 더 큰 블록 복구가 가능하기 때문에 data availability sampling에 참여하는 라이트노드가 많아질수록 블록의 크기가 커집니다. 다만 블록 사이즈가 커질수록 블록 헤더 사이즈가 커진다는 트레이드 오프가 있습니다. 하지만 그 수준이 제곱근에 비례하는 수준이기 때문에 노드 사양에 직접적인 영향을 주지 않습니다.

5. 마무리

블록체인 용량 증가 문제에 대한 솔루션으로 라이트노드가 있지만 data availability problem을 해결해야 사용이 가능합니다. Celestia는 2d reed-solomon encoding scheme을 활용해 라이트노드가 data availability sampling에 참여하게 함으로써 data availability problem을 해결합니다. 블록체인 mass adoption이 일어날 미래에 Celestia의 솔루션이 주목받을 수 있을지 지켜보는 것은 블록체인 산업을 바라보는중요한 포인트가 될 것입니다. 다음장에서는 Celestia의 사용 예시와 경쟁 솔루션에 대해 알아보도록 하겠습니다.

6. References

디사이퍼 — Celestia 팀 소개

Jason — Decipher Senior Researcher
이건우 — Decipher Junior Researcher
임요한 — Decipher Junior Researcher
장혁수 — Decipher Junior Researcher
홍성수 — Decipher Senior Researcher