---
title: Data Availability Problem
tags: security, data availability, erasure coding, reed-solomon code, hamming code
image: https://i.imgur.com/3ljnmZc.png
---

<style>

html, body, .ui-content {
background-color: #333;
color: #ddd;
}

.markdown-body h1,
.markdown-body h2,
.markdown-body h3,
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
color: #ddd;
}

.markdown-body h1,
.markdown-body h2 {
border-bottom-color: #ffffff69;
}

.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
color: #fff;
}

.markdown-body img {
background-color: transparent;
}

.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
color: white;
border-left: 2px solid white;
}

.expand-toggle:hover,
.expand-toggle:focus,
.back-to-top:hover,
.back-to-top:focus,
.go-to-bottom:hover,
.go-to-bottom:focus {
color: white;
}

.ui-toc-dropdown {
background-color: #333;
}

.ui-toc-label.btn {
background-color: #191919;
color: white;
}

.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
color: white;
border-left: 1px solid white;
}

.markdown-body blockquote {
color: #bcbcbc;
}

.markdown-body table tr {
background-color: #5f5f5f;
}

.markdown-body table tr:nth-child(2n) {
background-color: #4f4f4f;
}

.markdown-body code,
.markdown-body tt {
color: #eee;
background-color: rgba(230, 230, 230, 0.36);
}

a,
.open-files-container li.selected a {
color: #5EB7E0;
}

img[src$="centerme"] {
display:block;
margin: 0 auto;
}

</style>

# Data Availability Problem: 해결

이 글은 *Mustafa Al-Bassam, Alberto Sonnino, Vitalik Buterin*이 작성한 *[Fraud and Data Availability Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities](https://arxiv.org/pdf/1809.09044.pdf)* 논문을 기반으로 작성되었음.

Data Availability Problem
---
- [이전 글](/B1mdW9hYq)에서는 `Data Availability Problem`이 발생하는 배경과 원인에 대해서 알아보았다. 간단히 정리해보자면, 블록체인의 확장성 개선을 위해서 제안되는 방식(*라이트 노드, 롤업과 샤딩*)을 위해서는 Data Availability Problem 이 고려되어야 한다. Data Availability Problem은 올바른 블록체인 검증을 하기 위해서 데이터를 충분히 확보하지 못하는 문제를 의미한다. 구체적으로 다음의 두 가지 경우에 문제가 발생한다.
1) 악의적인 블록 생성자가 블록을 전파하지 않고 바로 블록체인에 등록하는 경우
2) 악의적인 노드가 일부분의 데이터만 다른 노드에게 전파했지만, 다른 노드에서 데이터의 진위 여부를 확인할 수 없는 경우
- 이 두 가지 문제는 다른 의미로, **어떻게 하면 블록체인에 참여한 노드들이 강제로 데이터를 전달하게 할 수 있을까** 또는 **몇몇의 악의적인 노드가 있어도 검증에 필요한 충분한 데이터를 얻을 수 있을까** 에 대한 문제가 된다. 이에 대해서 송신자에 의한 데이터의 전파가 **자율이 아닌 요청(request)에 기반하여 작동**하도록 하고, 조작된 데이터가 전파되더라도 데이터 수신자 노드가 **자율적으로 정정**할 수 있도록 함으로써 이 문제를 해결하려고 했다. 이 방법은 `Reed-Solomon Erasure Code`를 바탕으로 제안되었다.

배경
---
- `Reed-Solomon Erasure Code`의 개념은 **오류를 어떻게 검출하고 정정할 것인가** 라는 문제에서 시작하기 때문에 `Error Correction Code (ECC, 오류 정정 코드)`의 배경을 살짝 이해하고 넘어가면 도움이 된다.

#### Error Correction Code (오류 정정 코드)
- ECC는 컴퓨터 과학과 통신 분야, 정보 이론에서 오래 전부터 연구되었던 분야이다. 네트워크 통신에서 노이즈가 있는 패킷을 복구할 때나 물리적으로 손상된 디스크에서 데이터를 복구를 할 때 사용하는 방법으로, 요즘은 우리가 피부로 느끼진 못하지만 삶 속에 스며들어있는 기술이다.
- 네트워크와 디스크 외에도 최근 주목받고 있는 인공지능 분야에서도 ECC의 개념이 들어간다. 예를 들어, 품질이 낮은 이미지나 음성 신호를 좀 더 선명하게 개선 시켜줄 때도 ECC의 개념이 들어간다. Interpolation 이라는 개념이 비어있는 값에 대한 보정을 하기 위한 방법이니, ECC 와 인공지능 기술은 무관하다고 보기는 어렵다. ECC 대한 내용을 다루기에는 너무 많으니 여기서는 간단히만 알아보도록 한다.
- ECC에서는 손상된 데이터에서 에러를 검출하고 정정하는 방법으로 **기존 데이터에 '추가 데이터(비트)'를 보내는 방법**으로 해결해왔다. 예를 들어, A 와 B 가 "hello world"라는 메시지를 주고 받을 때, 송신자가 '안녕하세요'라는 추가적인 데이터를 전송하게 되면, 수신자는 '안녕하세요' 라는 말과 'hello world' 라는 말을 비교함으로써 데이터가 정상적으로 보내졌는지 확인할 수 있다. 만약에 'hello world'가 아니라 'helli world'라고 손상된 메시지가 전송되면, 'i'가 잘못되었다는 것을 인지하고, 'o'로 변환시켜 줄 수 있다.
- 오류를 검출하고 정정하는 방법에는 크게 `Linear Block Code`와 Convolution Code가 있는데, 여기서는 Linear Block Code 에 대해서만 알아보도록 하겠다.

> **Error Detection vs Error Correction**
>
> Error Correction 외에 Error Detection 이라는 개념이 있다. Error Detection 은 데이터에 오류가 생겼는지 알아내는 방법으로 간단히 에러 유무만 체크하고 몇 개의 에러, 몇 개의 bit 에 오류가 있는지 알 수 없다. 반면에 Error Correction 은 정확하게 몇 개의 에러가 있고, 몇 개의 bit에 오류가 있는지 알 수 있다. 일반적으로 Error Detection 하는 것은 Error Correction보다 더 적은 양의 비트를 필요로 한다.

[Error Correction Code의 분류](https://www.geeksforgeeks.org/difference-between-linear-block-codes-and-convolutional-codes/)

#### Linear Block Code
- Linear Block Code 은 원본 데이터를 k 비트 크기의 `dataword` 로 구분하고, 각 dataword에는 $r$ 비트 크기의 중복 비트를 더하여 총 $n = k + r$ 크기의 블록을 생성한다. 이 블록을 `codeword`라고 부른다. 쉽게 이야기하자면, **원본 데이터에 오류 검출 및 정정에 필요한 추가 데이터를 합쳐서 보내는 것이 Linear Block Code**라고 보면 된다. 여기서 추가 데이터는 `parity bit`이라고도 부른다.
- Linear Block Code 에도 다양한 방법들이 존재한다. 대표적으로 *Hamming Code, Parity Check Code, BCH Code, Cyclic Code*가 있고, Reed-Solomon Code도 Linear Block Code 중 하나이다. Reed-Solomon Code는 복잡한 수학적 수식이 있기 때문에, 조금 더 이해하기 쉬운 Hamming Code로 Linear Block Code를 이해해보자.

#### Hamming Code
- `Hamming Code`는 Linear Block Code의 종류 중 하나로, **1비트 오류 검출 및 정정은 가능하고, 2비트의 경우 오류 검출은 가능하지만, 정정은 불가능한 방법**이다.
- 데이터를 보내는 송신자는 원본 데이터를 그대로 보내지 않고, 원본 데이터에 추가 데이터를 합친 Hamming Code로 인코딩하여 보낸다. Hamming Code를 만드는 방법은 다음과 같다.
1. $2^p \geq p + n + 1$를 만족하는 최소 p 값을 구한다. 여기서 p는 추가할 parity 수, n 은 데이터의 비트 수를 의미한다.
2. $2^{k-1}$ 번째 자리마다 자신의 범위에 대한 추가 데이터인 parity bit를 추가한다. 예를 들어, $1010$ 이라는 4bit 의 메시지를 보내기 위해서 $2^p \geq p + 4 + 1$ 를 만족하는 최소의 p는 3이다. parity bit의 개수는 3이고 이들이 들어갈 위치는 1, 2, 4번째 bit 이다.
3. Parity bit에 들어갈 값 (0또는 1) 은 parity bit의 '범위'에 들어오는 원소의 인덱스 값들의 $XOR$ 연산으로 결정한다. parity bit의 범위가 결정되는 기준은 $i$번째 원소 포함하고 $i$ bit 만큼을 포함한 원소들을 $i$ bit 건너뛴 대상을 의미한다. 위의 예시를 들면, 첫번째 ($i=1$) parity bit (p1) 의 범위는 1,3,5,7이 범위에 포함된다. 두번째 ($i=2$) parity bit (p2)는 자기 자신을 포함하여 2 bit 만큼이 범위에 포함된 2,3,5,6이 되고, 마지막으로 세번째 parity bit ($i=4$)는 4,5,6,7이 범위안에 들어온다. 이렇게 범위 안에 있는 각각의 element를 $XOR$ 하면 나오는 값이 parity bit 의 값이 된다. (아래 그림를 보면 조금 이해가 쉽다)
- 이렇게 인코딩된 Hamming code를 받은 수신자는 먼저 데이터에 오류가 있는지 확인하기 위해서 비트 검사를 한다. 송신자와 수신자 사이에 몇 번째 비트가 parity 인지 약속을 했기 때문에, 수신자는 parity bit를 제외하고 dataword를 통해서 Hamming code 를 만들 수 있다. 위 예시에서는 1,2,4 번째 bit가 parity bit였기 때문에 parity bit를 제외한 3,5,6,7번째 bit가 데이터 비트임을 알 수 있다. 이 과정을 통해 데이터가 정상적으로 전달되었는지 확인할 수 있고, 오류가 있었다면, 비트를 반전시킴으로써 오류 비트를 정정할 수 있다.

[Hamming Code에서의 parity bit 위치와 범위 (Yes가 유효한 범위)](https://en.wikipedia.org/wiki/Hamming(7,4))

Reed Solomon Erasure Code
---
- *주의) 이 부분은 복잡하기 때문에 넘어가도 됨.*
- `RS Erasure Code` (RS Code)는 Linear Block Code 이면서 BCH Code 의 부분 집합으로 **데이터가 손상되었을 때, 데이터에 발생한 오류를 검출하고 정정할 수 있는 ECC 알고리즘**이다. RS Code는 CD, DVD, 바코드, QR 코드 뿐만 아니라 HDFS (Hadoop File System), 무선 통신, 인공위성 통신 등에 사용된다.
- RS Code의 **가장 큰 특징은 bit error 에만 국한된 것이 아니라 여러 비트에 오류가 있는 burst error에 대한 오류 검출과 정정에 유용하게 사용**될 수 있다는 것이다. 전체 블록의 길이가 $n$ 이고 그 중 원본 메시지 (payload)의 크기가 $k$ 일 때, $RS (n, k)$라고 표현한다. $RS (n, k)$라는 의미는 $t=n-k$ 크기의 공간을 `parity symbol`로 사용하여 오류의 검출과 정정에 사용한다는 의미이다. 좀 더 정확히 이야기하면, $t$ symbol 크기의 오류를 검출할 수 있고, $t$ symbol 만큼의 known 오류를 정정할 수 있으며, $t/2$ symbol 만큼의 unknown 오류를 정정할 수 있다.
- 또한, $n$ 과 $k$ 는 symbol ($s$) 단위에 따라 몇 비트일지 결정되는데, 많이 사용하는 $s = 8$ (8 bit) 을 사용하면 255와 223은 각각 255 byte 와 223 byte 를 의미한다. 예를 들어, 많이 사용하는 RS (255, 223)의 경우 전체 블록의 사이즈는 255 byte 이고 이 중 실제 메시지는 223 byte, 남은 32byte 는 parity symbol로 사용이 된다. 위에 언급한 내용을 대입하면 총 32 byte 크기의 데이터 오류를 검출해낼 수 있고, 16 byte 크기의 unknown 데이터 오류를 정정할 수 있다.
- RS Code는 몇가지 값을 설정해야 한다.
1. *Symbol size (s)*: 심볼 하나의 크기 (보통 8bit 임)
2. *Parity symbol 의 개수 (t)*: 위의 경우 32
3. *Extended Galois field generator polynomial coefficient*
4. *Reed Solomon code generator polynomial 을 생성하기 위한 Galois field에서의 primitive element*
5. *첫 consecutive root of Reed Solomon code generator polynomial*
- 1~3은 (255, 223) 과 같은 값으로 자동 설정되지만, 나머지는 직접 설정해줘야한다. 4의 경우 보통 11을 많이 선택하는데 3,5,17 로 나눠지지 않는 255 이하의 수를 고르면 되고 5는 121을 많이 선택하는데 NASA Voyager 미션에서 사용해서 그런 것으로 추정된다고 한다.

[RS Code의 field 구성 예시](https://berthub.eu/articles/posts/reed-solomon-for-programmers/)
- RS Code 는 수학적으로 복잡하게 되어있어서 간단히 이야기하면 다음과 같은 인코딩과 디코딩 과정을 거친다.
- 인코딩
1) `Generator polynomial` 을 생성한다
2) 원본 메시지에 대해서 1)에서 반환된 generator polynomial로 `polynomial division` 을 수행한다
3) 원본 메시지와 2)의 반환값 (remainder)를 이어붙이면 인코딩 된 RS Code 가 된다.
- 디코딩
1) 인코딩된 메시지에 대해서 `syndrome polynomial` 을 계산한다. 이 과정은 원본 메시지에 오류가 있는지 여부를 빠르게 확인하는 방법이다.
2) 1)에서 오류가 있다고 판단되면 `locator polynomial` 을 통해서 메시지의 어떤 부분에 오류가 있는지 확인한다.
3) `evaluator polynomial`을 통해서 오류의 정도가 얼마나 큰지 확인한다.
4) `magnitude polynomial`을 통해서 오류의 위치와 정도에 기반해서 오류를 정정한다. 이 결과를 기반으로 수신한 메시지를 정정하면 최종적으로 오류를 수정한 원본 메시지가 나온다.

RS Erasure Code를 활용한 Data Availability Proof
---
- 다시 블록체인 이야기로 돌아와, 어떻게 하면 Data Availability Problem 을 해결하고 있는지 알아보자. 앞서 이야기한 내용을 상기시켜보면, Data Availability Problem 은 두가지 경우에 발생할 수 있었다. 1) 악의적인 블록 생성자가 블록을 전파하지 않는 경우와 2) 충분히 검증할 수 있는 데이터를 전파하지 않는 경우가 있다.
- 첫번째 문제를 해결하기 위해서, 네트워크에 참여한 노드들은 데이터를 전파할 때까지 기다리는 것이 아니라 데이터를 요청(request)을 한다. 풀노드의 경우 모든 tx 데이터를 갖고 있기 때문에 전파 받은 데이터를 기반으로 직접 시뮬레이션 할 수 있다. 좀 더 자세히 보면, 블록이 갖고 있는 정보에는 `dataRoot`, `stateRoot` 라는 Merkle Root 정보가 있는데, 블록에 포함되어있는 tx를 직접 수행해보면서 변수들의 state들을 기반으로 stateRoot를 생성하고 tx 들을 기반으로 dataRoot를 생성한다. Merkle Root 값을 비교했을 때 일치하면 데이터가 조작되지 않았음으로 검증할 수 있고, 일치하지 않으면 데이터가 조작되었다는 사실을 알 수 있다. 이러한 과정을 `Fraud Proof` 라고 부른다.
- 그렇다면 라이트 노드의 경우 어떻게 Fraud Proof 를 할 수 있을까? 라이트 노드는 블록 헤더 정보만 있고, 전체 tx에 대한 정보가 없기 때문에 Fraud Proof 를 풀노드에게 요청해야한다. 요청을 받은 풀노드는 Fraud Proof를 진행하고 결과를 라이트 노드에게 전송하면, 라이트 노드는 그 결과를 전적으로 믿는다.

[라이트 노드의 Request와 풀 노드의 Response](https://arxiv.org/pdf/1809.09044.pdf)

- 여기서 두번째 문제가 발생하는데, Fraud Proof를 진행한 풀노드가 악의적인 의도를 갖고 tx를 조작한 결과를 라이트 노드에게 알려주면 어떻게 해야할까? 이 문제를 해결하기 위해서 **RS Code 에 기반한 Data Availability Proof**를 진행한다.
- 이 방법은 기본적으로 네트워크 상에 선의를 갖고 있는 다른 라이트 노드와 풀노드가 충분히 있다고 가정한다. 먼저, 송신자인 풀노드는 원본데이터인 블록 정보를 그냥 보내는 것이 아니라 2배로 부풀린다 ($n = k + t; t = k)$ 이 말은 즉, **데이터의 50%에 오류 또는 조작이 있어도 오류를 정정할 수 있다는 의미**이다. 수신자인 라이트 노드는 무작위로 여러 노드들에게 RS 인코딩된 데이터를 요청하는데, 요청 받은 데이터를 디코딩한 후 데이터의 50% 이상에 오류가 있다고 판단되면 그 데이터는 검증에 포함시키지 않는다.
- 첫번째 시도에는 50%의 확률로 오류를 정정할 수 없는 데이터를 가져온다. 하지만 두번째 시도에는 검증할 수 있는 데이터를 가져올 확률이 25%로 줄어들고, 3번째 시도에서는 12.5%가 된다. 7번의 시도를 하면 확률은 1%미만으로 떨어진다. 이 말은 즉, 라이트 노드가 여러 번 요청을 하면 왜곡된 데이터를 받을 확률이 떨어지고, 라이트 노드는 여러 번의 시도를 통해서 검증을 할 수 있는 유효한 데이터를 받을 수 있게 된다. 이러한 과정은 단순히 한 노드에서만 그치는 것이 아니라 다른 노드들에게도 전파가 되기 때문에 오류가 있는 데이터들은 모두 정정이 된다고 볼 수 있다.
- 여기서 추가적으로 `1D RS Code`를 사용하는 것을 개선하여 `k-D RS Code (k는 k차원을 의미)` 를 사용하는 방법이 있는데, 탐색 시간을 줄여주는 훨씬 효율적인 방법이어서 사용한다고 한다. 내용이 많고 복잡하기 때문에 자세한 내용은 논문을 참고하면 될 것 같다.

[RS Code 개요](https://www.schifra.com/example.html)

[RS Code 과정](https://www.schifra.com/example.html)

요약
---
- 깊게 파고 들면 ECC의 개념부터 RS Code에 대한 복잡한 내용을 다루었는데, 요약하자면 RS Erasure Code 를 사용하여 Data Availability Problem 을 해결했다고 말할 수 있다. RS Erasure Code는 오류 검출 및 정정 알고리즘 중 하나로, **전체 데이터를 똑같이 갖고 있지 않고 더 적은 양의 데이터를 갖고도 손상된 데이터를 복구할 수 있다는** 특징이 있다. 이 점이 블록체인의 확장성 솔루션에도 적용되어 활용이 되었다.
- 이 방법은 또한, 네트워크에 악의적인 사용자가 있다고 가정했을 때에도 악의적인 사용자의 공격에도 안전하게 대응할 수 있는 시스템을 만들 수 있는 개념을 제안했다는 측면에서 의의가 있다.
- 이번 글을 작성하면서 정보 이론, 통신 이론, 부호 이론에 걸친 ECC 개념에 대해서 공부를 할 수 있는 기회였고, 이 내용이 블록체인과 결합하여 얼마나 블록체인을 빠르고 효율적이고 악의적인 사용자나 오류에도 안전한 시스템으로 만들 수 있는지에 대한 것을 알 수 있었다.

참고자료
---

1. https://gusdnd852.tistory.com/80
2. https://slidesplayer.org/slide/14076058/
3. https://www.geeksforgeeks.org/difference-between-linear-block-codes-and-convolutional-codes/
4. https://www.cs.cmu.edu/~guyb/realworld/reedsolomon/reed_solomon_codes.html
5. https://www.koreascience.or.kr/article/JAKO199811920562427.pdf
6. https://homes.cs.washington.edu/~jrl/teaching/cseP531sp16/presentations/pres4.pdf
7. https://berthub.eu/articles/posts/reed-solomon-for-programmers/
8. https://unfunhy.tistory.com/116
9. https://towardsdatascience.com/erasure-coding-for-the-masses-2c23c74bf87e
10. https://medium.com/coinmonks/data-availability-on-ethereum-2-0-light-node-en-aec1ce6ac17c