머클트리 (Merkle Tree)
Ralph Merkle이라는 사람이 고안해 낸 자료구조이며, 쉽게 표현하면 Hash + Binary Tree 라고 생각하면 편하다.
만약 본인이 Tree 자료구조의 개념을 잘 숙지하지 못하고 있다면, 이 포스팅이 별로 도움이 안될지도 모르겠다. 트리 자료구조에 대해 먼저 숙지를 해야 될 것이다.
Tree 자료구조란, 아래 그림과 같이 데이터를 나름의 규칙을 이용해 계층적으로 저장하는 형태를 의미한다. http://monsieursongsong.tistory.com/6 를 참조하면 되겠다.
그렇다면 Binary Tree 란? 모든 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조이다. 위의 일반 트리와 다르게 아래는 자식 노드가 모두 2개인것을 확인할 수 있다.
이 Binary Tree 에 Hash를 결합한 것이 바로 머클트리라고 한다.
해시를 사용하는 이유는 특정데이터를 일정한 길이의 데이터로 바꾸어 줄수 있기때문에 사용하게 되며, 블록체인을 공부하다보면 자주 볼수 있는 SHA256은 어떤 데이터가 오던지 256비트(32바이트) 데이터로 바꾸어 줄수있다.
비트코인 역시 SHA256해시를 사용하고 있다. 아래 머클트리 그림을 볼수 있는데 모든 노드가 왼쪽과 오른쪽 자식노드를 Hash한 값을 가지고 있다.
그렇다면 이 머클트리를 어떤식으로 사용될 수 있는지 궁금할 것이다.
일반 트리와 2진트리는 선형적 자료구조인 스택, 큐, 배열, 리스트와는 다른 비선형적 계층구조라고 했다. 그래서 얻을수 있는 장점은 데이터를 찾기위해 걸리는 시간은 트리의 높이 만큼의 시간이며, O(logN) 의 속도 (증명 링크 http://jwoop.tistory.com/9 )를 갖는다.
O(N) 의 속도를 갖는것 선형적 자료구조보다 유리하기 때문에 데이터 검색 및 삽입, 삭제 작업이 빈번한 데이터베이스에서 트리자료구조를 많이 활용하고있다.
머클트리는 데이터 검색, 삭제등의 일과는 적합하지 않다. 이유는 모든 데이터를 Hash하여 결과적으로 Top Hash 한개 만을 가지고 있을 것이기 때문이다.
특징은 아래와 같다.
1. 모든 데이터를 일정한 길이의 데이터 1개 (Top Hash) 만을 가지고 있다.
2. Hash특성상 하위 블록데이터가 달라지면 Top Hash값도 달라진다.
2번을 한번 확인해 보자.
SHA256 ( DATA1 + DATA2) 예시다.
결과는 아래와 같이 완전히 엉뚱한 값이 산출되게 된다.
하위의 데이터 한개만 달라져도 최종적으로 나오는 Top Hash값이 달라진다는 점이 매우 중요하다.
이 두가지의 특징으로 사용할 수 있는 용도로는 기존 데이터가 유효한지 검증하는 것이다. 그리고 이 데이터 검증을 할수 있는 주체는 굉장히 다양해진다. 모든데이터가 아닌 Top Hash만을 소유하고 있기때문에 데이터 공간의 부담이 없기 때문이다.
머클트리에 대한 설명은 여기까지 진행하겠다.
이 포스팅은 현재 진행하고 있는 비트코인 P2P네트워크 포스팅을 위한 머클트리 개념에 대한 설명으로, 비트코인 블록체인 노드에서 이를 어떻게 활용 하는지는 나의 다른 포스팅을 참고하기 바란다.
궁금한 부분이나 지적은 댓글 부탁한다.
[출처 위키피디아 https://en.wikipedia.org/wiki/Merkle_tree]