머클 트리(Merkle Tree)와 구조와 용도

머클 트리란?

암호학이나 컴퓨터 과학에서 머클 트리(Merkle tree) 는 모든 자식 노드들이 암호학적 해시로 이뤄진 데이터 블록을 갖는 트리 형태의 자료 구조로 해시 트리(hash tree)라고도 부릅니다.

랄프 머클(Ralph Merkle) 이 발명했고 79년에 특허를 받았습니다.

머클 트리는 위와 같이 자식 노드의 데이터를 암호학적 해시로 계산한 값을 트리로 만든 데이터로 블록 단위로 빠르게 데이터를 검증하고 이상 유무를 확인할 수 있는 장점이 있으므로 유명한 제품들 내부에서 많이 사용하는 자료 구조입니다.

Bit torrent

그래서 네트워크로 상대방에게 파일을 보낼때 데이터를 블록 단위로 쪼개고 이를 머클 트리로 만든후에 나눠서 보내면 수신한 블록의 이상 유무는 블록의 해시 값을 계산하면 금방 알수 있습니다.

그래서 머클 트리를 사용해서 데이터를 송수신하면 수신한 데이터가 문제있을 경우 전체 데이터를 받지 않고 문제되는 블록 데이터만 받을수 있으므로 전송 속도가 매우 빨라지는 장점이 있습니다.

이때문에 파일 전송 프로토콜인 Bit torrent 에서는 머클 트리를 사용하고 있습니다.

file system

Btrfs 나 ZFS 같은 file system 은 데이터 무결성을 검증하기 위해 머클 트리 자료 구조를 사용합니다.

git

머클 트리를 사용하는 유명한 프로그램은 버전 관리 도구인 git 입니다.

git 에서 브랜치와 머지는 이전 상태를 자식으로 갖고 있는 머클 트리이며 커밋 해시는 자식 노드의 데이터를 해시한 값입니다.

Bit coin

이제는 머클 트리를 사용하는 가장 유명한 제품은 비트 코인이 아닐까 싶습니다.

비트 코인의 원장은 머클 트리 구조로 이전 트랜잭션 데이터를 묶어서 해시한 값을 갖고 있습니다.