머클 트리(Merkle tree)는 이진 해쉬 트리(Binary hash tree) 라고도 하며 해쉬 함수로 암호화된 해쉬값을 이진 트리로 구성되는 데이터 구조로 분산 데이터 구조에 주로 쓰인다.
머클 트리의 구조를 그림으로 보면 다음과 같다.
<출처: Mastering Bitcoin, Andrea M Antonopoulos>
그림에서 보면 각 데이터A, B, C, D의 해쉬값이 환산되고 A해쉬와 B해쉬의 합을 해쉬하여 AB 해쉬를 만들고 C해쉬와 D해쉬의 합을 또 해쉬하여 CD해쉬를 만들어 AB 해쉬와 CD해쉬의 합을 해쉬한 값을 머클 루트 혹은 탑 해쉬라고 부른다. 이 값은 매우 중요한데 데이터가 하나라도 바뀌면 이 값이 변하기 때문에 데이터가 위변조 되거나 데이터가 변환 되었는지 이 값을 비교하여 효울적으로 검증이 가능하다. 머클트리는 비트코인 , 이더리움과 같은 블록체인에도 쓰이는데 이 머클 루트 값은 블록 헤더에 포함되는 중요한 값이다.
데이터가 증가하면 머클 트리의 구조는 다음과 같이 확대 된다.
<출처: Mastering Bitcoin, Andrea M Antonopoulos>
데이터가 늘어나면 이런 방식으로 이진 트리가 확대 되는 것이다. 머클 루트는 이 수많은 데이터를 하나의 해쉬 값으로 나타낼 수 있다. 이러한 데이터 구조(Data Structure)는 다른 데이터 구조에 비해 많은 장점들을 가진다. 우선 데이터를 찾고 처리하는 Look up time 을 낮출 수 있어 효율적이다. 컴퓨터 알고리즘의 효율성을 판별하는 방법 중 시간의 복잡도(Time Complexity) 함수를 기준으로 보면 N을 데이터 처리량 이라고 할때 O(N)에서 O(LogN)으로 줄어든다고 한다. 또한, 머클 루트 해쉬 값으로 데이터 무결성을 효율적으로 검증할 수 있으며 데이터 저장 용량이 중앙 데이터 베이스 구조보다 작기 때문에 확장성 문제 (Scalability)를 해결하는 좋은 방안이다. 블록체인 상에서는 모든 노드들이 모든 블록을 다 받는 것은 용량 상 무리가 있기 때문에 머클 루트와 머클 패스가 포함되어 있는 블록 헤더만을 받고 데이터 베이스에 접근할 수 있는 방법으로 이러한 확장성 문제를 완화 할 수 있다. 이 머클 트리를 변형 하여 이더리움은 머클 패트리샤 트리, IPFS는 머클 DAG 트리 등으로 데이터 구조를 설계하여 사용 중이다.
