Data Availability를 이해해보자
Interoperability, Data Availability, Scalability
인트로
Data Availability를 공부하게 된 이유
현재 블록체인 기술에서 가장 중요한 토픽 3가지를 꼽자면, 나는 Interoperability(상호 운용성), Data Availability(데이터 접근성), Scalability(확장성)를 고를 것 같다. 이 중에서 내가 Data Availability에 관심갖게 된 이유는 Celestia라는 프로젝트 때문이다. 내가 팔로우하는 많은 사람들이 Celestia에 대하여 이야기하면서, 나는 자연스럽게 Celestia에 대하여 찾아보았고, Celestia를 이해하기 위해서는 Data Availability를 마스터해야한다는 결론에 이르게 되었다.
Data Availability의 정의
Data Availability는 우리 말로 데이터 접근성, 즉 데이터가 접근가능한지를 말한다. 즉, Data Availability는 새로 생성된 블록의 모든 데이터가 노드들에게 전파되어서 접근가능한지를 말한다.
Data Availability가 왜 중요할까?
그럼 Data Availability는 왜 중요할까? 그 이유는 Data Availability가 보장되어야만 제대로 된 fraud proof를 할 수 있기 때문이다.
Fraud Proof
풀 노드와 라이트 노드
블록체인에는 두가지 종류의 노드들이 있다. 풀 노드는 블록체인 내의 모든 데이터를 다운로드받아서, 직접 transaction의 유효성을 검증한다. 그렇기 때문에, 풀 노드를 운영하기 위해서는 일정 수준 이상의 하드웨어, 저장 공간등을 필요로 한다. 하지만, 모든 노드들이 이 기준을 만족할 수 없기에, 풀 노드가 아닌 라이트 노드가 존재한다. 라이트 노드들은 블록 헤더만을 다운로드한다. 그렇기 때문에, transaction의 유효성은 풀 노드의 검증에 의존한다.
이 때, 라이트 노드들은 어떻게 블록 내에 invalid transaction이 포함되었는지 알 수 있을까?
만약 풀 노드가 블록 A의 트랜젝션을 검증하다가 invalid transaction을 발견하면, fraud proof라는 것을 라이트 노드에게 보낸다. 라이트 노드는 이 fraud proof를 검증하여서 fraud proof가 옳은 경우, 해당 블록 A 내에 invalid transaction이 있는 것으로 판단 후, 블록을 거부한다.
fraud proof를 제출할 때에는 해당 transaction이 담긴 shares, Merkle proof, state witness를 포함시켜야 하는데, 중요한 것은 어쨋든 fraud proof를 제출하기 위해선 해당 transaction의 데이터가 필요하다는 것이다.
Fraud Proof에 문제가 생기는 상황
Fraud proof는 다음과 같은 상황에서 문제가 생길 수 있다.
악의적인 블록 생성자(producer)는 invalid transaction이 담긴 데이터 일부를 숨긴채, 나머지만 블록 헤더와 함께 전파하거나 아예 블록 헤더만 전파할 수도 있다.
이 때, 라이트 노드는 블록 헤더만 다운로드하기 때문에, invalid transaction이 블록 내에 포함되었는지 알 수 없다. 풀 노드들은 모든 데이터를 다운로드하기 때문에, 해당 블록이 invalid하다는 것은 알수는 있지만, 해당 transaction이 invalid하다는 것을 라이트 노드에게 알려줄 fraud proof를 만들 수가 없다. 왜냐하면, fraud proof는 해당 transaction의 데이터가 필요한데, 악의적인 블록 생성자가 이에 해당하는 데이터를 전파하지 않고 숨겼기 때문이다. 결국 fraud proof에 의존하는 라이트 노드들은 fraud proof가 오지 않으니, 이 블록이 valid하다고 판단할 것이고, 결국 invalid transaction이 체인 내에서 존재하게 된다.
추가적으로 블록 중 일부의 데이터가 노드들에게 전파되지 않았을 때, 노드들은 이게 의도적인지, 아니면 네트워크 딜레이와 같은 시스템적 오류때문인지 구별할 수가 없고, 해당 블록 생성자를 처벌할 수도, 그냥 둘 수도 없는 딜레마에 처한다.
우리는 위와 같은 상황을 Data Availability Problem이라고 한다.
Data Availability Problem
Data Availability Problem은 다음과 같이 정의할 수 있다.
- 새로운 블록이 생성되었을 때, 어떻게 우리는 그 블록의 모든 정보가 노드들에게 전파되었다고 확신할 수 있는가?
혹은,
- 새로운 블록이 생성 되었을 때, 어떻게 우리는 블록 생성자가 모든 데이터를 공개, 전파하도록 강요할 수 있는가?
잘못된 솔루션
간단하지만, 잘못된 솔루션은 라이트 노드들도 블록 데이터 전부를 다운로드받게 하는 것이다. 이러면 문제는 해결하지만, 애초에 라이트 노드의 취지에 어긋난다.
Data Availability Proof
Data Availability Proof는 우리가 찾고 있는 해답이다. Data Availability Proof는 라이트 노드들이 블록 데이터의 일부만 다운로드하여서, 블록 데이터 전부가 노드들에게 전파되었는지 검증할 수 있는 기술이다.
Data Availability Proof
Erasure Coding
Erasure coding은 Data Availability Proof에 사용되는 수학적 기법중 하나이다. Erasure coding의 목표는 데이터의 일부가 손실(erased)되어도, 나머지 데이터로 원래의 데이터를 복구할 수 있도록 하는 것이다. 가장 대표적인 erasure coding 기법으로 Reed-Solomon code가 있다.
원래 length k인 데이터를 n>k인 length n으로 만든다. 이 후, n개의 데이터 중 일부만으로도 원래의 length k 데이터를 복구할 수 있다.
아주 간단한 erasure coding의 예시
이 경우는 n = k+1인 특별한 경우의 erasure coding이다. 예를 들어 원래의 데이터가 “2 3 5 8“인 length 4의 데이터라고 하자. 우리는 이 length 4인 데이터를 length 5로 만드는데, 마지막 데이터로 기존 데이터의 합인 2+3+5+8=18을 추가한다. 결국 변환 후 데이터는 “2 3 5 8 18“이 된다.
이 후, 두번째 숫자가 손실되어서 데이터가 “2 ? 5 8 18“이 되었다고 하자. 우리는 18이 앞서 데이터들의 합이라는 것을 알기 때문에, 18-2-5-8=3이여서 손실된 데이터가 3이라는 것을 알 수 있고, 원래 데이터를 복구할 수 있다.
아주 조금 더 복잡한 erasure coding의 예시
이 경우는 k=2인 특별한 경우이다. 예를 들어서 원래의 데이터가 “2 3“이고, n=4라고 하자. 이 때, 우리는 f(0)=2, f(1)=3을 만족하는 일차함수 f(x)를 만들 수 있고, 이 경우에서 f(x) = x+2이다. 기존의 데이터에 f(2)와 f(3)을 추가하였을 때, 최종적으로 변환된 데이터는 “2 3 4 5“가 된다.
이 후, 기존의 첫번째, 두번째 데이터가 손실어서 데이터가 “? ? 4 5”이 되었다고 하자. 우리는 f(0)과 f(1)의 값을 주어진 f(x)를 통하여 구하여서 원래 데이터를 복구할 수 있다.
Data Availability Proof에서 erasure coding
일단 편의를 위하여 n=2k인 경우라고 가정하자. 블록의 transaction 데이터 전부를 일단 k개의 chunks로 나눈 뒤에, erasure coding을 통해 n개의 chunks로 만든다. 이 n개의 데이터 chunks에 대한 Merkle Root가 블록 헤더에 포함된다.
n이 2k이기 때문에, 우리가 원래 데이터를 복구하기 위해서는 최소 k개의 chunks, 즉 최소 50%의 데이터만 있으면 된다. 이 말은 곧 악의적인 블록 생성자가 전체 블록이 복구되는 것을 막기 위해서는 최소 k+1개의 chunks, 약 50% 이상의 데이터를 숨기고, 전파하지 않아야 된다는 것을 의미한다.
상세한 메커니즘
먼저 현재 블록 데이터는 erasure coding된 상태로 기존의 length k의 데이터가 length 2k가 되었고, 노드들은 이 중에서 k개의 chunks만 모아도, 원래에 데이터를 복구할 수 있다. 이 때, 악의적인 블록 생성자가 invalid transaction을 자기가 생성한 블록 내에 포함시키기 위해선 총 2k의 블록 데이터 chunks 중에 k+1개의 데이터를 숨기고, 전파하지 않아야 한다. 이 때 라이트 노드들은 어떻게 일부의 데이터만으로도 이 블록이 invalid하다는 것을 알 수 있을까? 메커니즘은 다음과 같다.
먼저 라이트 노드들은 랜덤하게 chunk 중 일부를 다운로드한다. 만약에 해당 chunk가 블록 생성자가 숨긴 데이터 중 일부라서 unavailable하다면, 해당 블록을 invalid하다고 판단 후 거부한다. 한번에 하나의 chunk만 다운로드한다고 하였을 때, 첫번째 시행에서 해당 블록이 invalid하다고 탐지할 확률은 50%이다. 왜냐하면, 해당 chunk가 블록 생성자가 숨긴 k개 중 하나일 확률이 50%이기 때문이다. 두번 시행에서 탐지할 확률은 75%이고, 세번 시행은 87.5%, 약 15번 시행하였을 때 100%에 수렴한다.
마지막으로 남은 문제
이렇게 우리는 라이트 노드가 풀 노드에 의존하지 않은 채로 직접 데이터의 일부만으로 이용하여 data availability를 직접 검증할 수 있는 메커니즘을 알아보았다. 하지만, 아직 우리가 다루지 않은 문제가 하나 남아있다. 우리는 어떻게 블록 데이터가 올바르게 erasure coding되었는지 검증할 수 있는가? 만약 악의적인 블록 생성자들이 임의로 erasure coding을 마음대로 하게된다면, Data Availability Proof의 메커니즘 자체가 성립하지 않을 것이다.
풀 노드들은 데이터를 전부 다운로드하기 때문에, 블록 생성자가 준 erasure coding된 데이터와 자신이 직접 erasure coding한 것을 비교하여서 검증할 수 있다. 하지만, 라이트 노드는 모든 데이터를 다운로드할 수 없기 때문에, 문제가 발생한다.
결론적으로 말하면 우리는 다차원의 Reed-Solomon code를 사용하여, 일부의 데이터만으로도 erasure coding의 validity를 확인할 수 있다. Reed-Solomon code의 자세한 메커니즘은 이 글의 범위를 넘어서기 때문에 설명하지 않겠지만, 간단하게 2D Reed-Solomon code는 원래의 데이터를 다음과 같이 이차원의 행렬로 변환한다.
데이터를 1차원이 아닌 2차원의 행렬로 나타내면, 원래의 데이터의 크기가 k일 때, 각 모서리의 길이는 k^(1/2)가 된다. 고로 우리는 특정 행이나 열의 erasure coding이 올바르게 되었는지 확인하기 위해서 k가 아닌, k^(1/2)만 필요하다.
복잡도의 측면에서 얘기하면, 기존의 1D Reed-Solomon code는 전체 데이터가 n개의 chunk라고 할 때, O(n)의 시간과 저장 공간 복잡도를 가지지만, 2D Reed-Solomon code는 O(n^(1/2))의 복잡도를 가진다. 하지만, 다차원의 Reed-Solomon code를 사용하면, erasure coded된 데이터의 크기 자체는 훨씬 커진다는 단점이 있다.
더 나아가서
Data Availability 문제에 대하여 관심이 생겼고, 이 글에서 생략된 많은 디테일들이 궁금하다면, 아래의 내용들을 찾아보는 것을 적극 추천한다.
이 fraud proof와 Data Availability 문제를 다룬 근본이기 때문에 한번 읽어보면, Data Availability 문제에 대한 A to Z를 배울 수 있다. 다만 연구 논문이기 때문에, 내용이 길고 어려워서 이해하기가 쉽지 않다(적어도 나는 그랬다).
이 강의는 Celestia의 CRO인 John Adler가 NEAR 블록체인의 Co-Founder인 Alexander Skidanov에게 Data Availability 문제를 소개해주는 영상이다. 이 영상을 추천하는 이유는 위 논문과 거의 같은 내용을 다루지만, 더 쉬운 예제와 함께 설명해주기 때문이다.
Erasure coding과 Reed-Solomon code에 대해서 알고 싶을 때는
나는 Data Availability를 이해할 때, erasure coding과 Reed-Solomon code에서 가장 큰 어려움을 겪었다.
Erasure coding을 이해할 때는 erasure coding의 가장 기초인 Parity check를 통해 이해하는 것이 가장 쉽다. 이 영상은 Parity check를 아주 쉽게 가르쳐준다. 이후, 이 영상과 이 영상도 참고하면 좋을 듯하다. 만약 erasure coding에 대한 가닥이 잡혔다면, Erasure coding의 위키피디아에 이해하는데 도움이 되는 2가지 예제가 나와있어서 참고하면 좋다.
Reed-Solomon code가 정확히 무엇인지 알고 싶다면, 이 영상을 추천하고, 나 역시도 공부중이다.
내가 참고한 Data Availability를 다룬 포스트들
더 많은 정보는
현재 COINEASY 팀의 공식 작가로 활동하고 있습니다! 더 많은 크립토/블록체인 정보는
코인이지 텔레그램 공지방
코인이지 텔레그램 소통방
https://t.me/coineasy_official
에서 확인하세요!
