비트코인이 Merkle Tree를 사용하는 이유

왜 Bitcoin은 Merkle Tree 구조를 사용할까?

Bitcoin은 Transaction을 Merkle Tree 구조로 구성한 다음 Root Node의 해시 값(Merkle Root)를 블록헤더에 넣어서 블록을 만드는 과정을 거친다.

그런데 "왜 비트코인에서 블록헤더에 Transaction 정보들을 Merkle Tree구조로 저장을 할까?"라는 의문이 들었다. 

Why Tree?

Merkle Tree를 알아보기 전 왜 Tree구조를 사용할 까라는 생각이 들었다. 

컴퓨터 자료구조의 큰 관점으로 보면 선형구조(List, Stack, Queue 등), 비 선형구조(Graph, Tree)로 나눌 수 있다.

선형구조와 비 선형구조에서 차이점은 노드 검색속도로 들 수 있다. 

예시를 통해 보면 더 쉽게 이해할 수 있다. 

Linked List array로 저장해둔 과일 목록이 있다고 하자

위 Linked List array에서 Graph를 찾는다고 하면 Apple -> Banana -> Graph 이 순서를 거쳐야 한다. 단순한 예라 금방 찾겠지만 만약 노두가 무수히 많아진다면 검색시간이 정수 배만큼 늘어난다.

Tree의 경우를 살펴보자 13을 검색한다고 했을때 이전 예에서 들었던 선형구조는 1부터 13까지 차례대로 검색해야한다.(오름차순으로 정렬되었다고 가정했을 때)

그러나 Tree구조로 13을 검색한다면 1 -> 6 -> 13으로 단순해진다.

시간복잡도로 표현한다면 O(logN)으로 나타낼 수 있다. 원소가 1024개라고 한다면 10번의 경로 내로 모든 원소를 검색할 수 있다.

선형구조인 경우 시간복잡도는 O(N)이다.

Merkle Tree

이 글에서는 Merkle Tree가 무엇인지에 대해 자세히 다루지 않는다. Why에 초점을 맞춘 글이라 무엇인지는 자세히 설명하지는 않는다.

위의 그림은 Wikipedia Merkle Tree를 검색해보면 볼 수 있는 그림이다. 

각 자식노드의 해시의 합을 합친 뒤 해시한 값이 부모노드이다.

본론으로 돌아가서 왜 Bitcoin은 Merkle Tree구조를 사용하는지에 대해서 설명하고자 한다.

Bitcoin Network의 노드인 Light Node가 일부 블록의 내용 만으로 올바른 정보인지 검증을 해야할 때가 있다. 

Full Node와는 달리 Light Node는 전체 블록정보가 아닌 일부 정보만 가지고 있으므로 이런 경우가 생긴다.

현재 Light Node는 그림에서와 같이 Merkle Tree Root의 해시 값과 L4(Tom -> Jack에게 100BTC를 보냄)만 가지고 있다.

Light Node는 L4를 검증하고 싶은데 Light Node는 전체의 블록정보를 알지못하므로 Full Node에게 정보를 받아야 한다.

이때 Full Node에게 최소한의 Node정보만을 받는 것이 효율적이다.

Merkle Tree는 이 처럼 2개의 Node만을 받는다면 L4의 트랜잭션을 검증할 수 있게된다.

이 외에도 거래정보가 1024개라도 O(logN)의 시간복잡도를 가지고 있기 때문에 log(1024) = 10 즉, 10번의 경로만으로 필요한 모든 노드를 찾을 수 있다.

참고자료

자료구조 - 선형, 비선형 : https://sw-tech.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B01-%EC%84%A0%ED%98%95-%EB%B9%84%EC%84%A0%ED%98%95

해시 트리 - Wikipedia : https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%8A%B8%EB%A6%AC