머클 트리(Merkle Tree)란?

머클 트리(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 트리 등으로 데이터 구조를 설계하여 사용 중이다.