검색
색인
머클 트리, -, merkle tree
동의어 : 해시트리, 이진트리, 이진 해시트리
블록체인에서 블록 하나에 포함된 모든 거래 정보를 요약하여 트리(tree) 형태로 표현한 데이터 구조.

블록체인에서 블록의 바디(body)에 포함된 모든 거래 정보를 특정 크기 단위별로 암호화 기법(예: SHA-256)을 적용하여 여러 단계(round)를 거쳐 해시값을 만든다. 이 해시값들이 트리 형태이고, 1979년 고안자 랄프 머클(Ralph Merkle)의 이름에서 따와 머클 트리라고 부른다.
이 머클 트리의 최상위에 위치하는 해시값을 머클 트리 루트(merkle tree root)라고 한다. 기존의 이진 트리 구조가 부모 노드에서 자식 노드로 향하는 구조였다면, 머클 트리는 자식 노드에서 부모 트리로 상향하는 구조이다.

머클 트리 루트를 생성하는 과정은 다음과 같다.
- 먼저 블록 내의 모든 거래 정보들의 해시값을 계산한다. (이 해시값을 리프(leaf) 데이터라고 부른다.)
- 두 개의 리프 데이터를 연결하여 해시값을 구한다. (이 해시값은 리프 데이터에 대한 부모 데이터라고 한다.)
- 쌍을 지을 수 없을 때까지 상향식으로 반복하여 해시값을 구한다. 이때 최종 해시값이 머클 트리 루트이고 블록의 헤더(header)에 포함된다.