밑바닥부터 시작하는 비트코인

밑바닥부터 시작하는 비트코인

284

11.8

머클블록

풀 노드가 포함증명을 보낼 때 함께 보내는 두 가지 정보가 있습니다. 첫째는 머클트리의 구조

에 대한 정보이고, 둘째는 머클트리에서 어떤 해시값이 어느 위치에 있는지에 대한 정보입니

다. 두 정보를 바탕으로 라이트 노드는 머클트리를 부분적으로 재구성하여 머클루트를 계산하

고 포함증명을 확인할 수 있습니다. 풀 노드는 이 두 정보를 포함증명과 함께 라이트 노드에 전

달할 때 구성하는 블록을 머클블록

Merkle

Block

이라고 합니다.

머클블록이 무엇이고 블록 안에 무엇이 있는지 설명하기 위해 먼저 머클트리와 같은 이진트리

자료구조의 노드를 어떻게 순회하는지 알아야 합니다.

5

이진트리의 노드를 순회하는 알고리즘

에는 너비 우선 탐색법이나 깊이 우선 탐색법이 있습니다. 너비 우선 탐색은 [그림

11

-

3

]에서

와 같이 한 레벨의 모든 노드를 방문하고 그다음 레벨의 노드를 방문하는 방법입니다.

그림

11-3

너비 우선 순회

너비 우선 탐색에서 최상단 루트 노드에서 시작하여 다음 레벨을 방문하고 한 레벨에서는 왼쪽

에서 오른쪽으로 방문합니다.

5

순회한다는 뜻은 트리의 모든 노드를 딱 한 번씩 방문한다는 의미다.

11

장

단순 지급 검증

285

깊이 우선 탐색은 [그림

11

-

4

]에서와 같이 순회하는 순서가 앞서 본 방법과 약간