준비금 증명에 주로 쓰인 개념, 머클 트리에 대해서 알아보자.

참고 사이트: CertiK 공식 블로그 

머클 트리(Merkle Tree)란?

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

랄프 머클이 발명했고, 79년도에 특허를 받은 개념입니다.

용도

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

최근 암호화폐 시장을 뜨겁게 달구고 있는 FTX 사건으로 인해 불거진 준비금 증명(Proof of Reserve)에 쓰이는 개념이기도 합니다. 

사용 프로젝트

Bit torrent

네트워크로 상대방에게 파일을 보낼 때 데이터를 블록 단위로 쪼개고 이를 머클 트리로 만든 후에 나눠서 보내면, 수신한 블록 이상 유무는 블록의 해시값을 계산하면 금방 알 수 있습니다. 그래서 머클 트리를 사용해서 데이터를 송수신하면, 수신한 데이터가 문제가 있을 경우 전체 데이터를 받지 않고 문제되지 않는 블록 데이터만 받을 수 있으므로 전송 속도가 매우 빨라지는 장점이 있습니다.

이 때문에 파일 전송 프로토콜은 Bit torrent는 머클 트리를 사용하는 프로젝트입니다.

Btrfs, ZFS

파일 시스템은 데이터 무결성을 검증하기 위해 머클 트리 구조를 사용합니다.

git

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

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

머클 트리의 역할

현재 블록체인 시장에서 머클 트리의 역할은 준비금 증명이나 기타 프로젝트에 사용되는 개념 외에도 많은 프로젝트에 기본적으로 쓰이기도 합니다.

예를 들어, 특정 거래를 쉽고 빠르게 찾아가려고 한다면 어떻게 해야할까요? 이 과정을 빠르게 단축해주는 것이 바로 머클 트리입니다.

그림처럼 8개 거래 중 5번 거래를 찾아가려면 해싱이 되는 과정이 총 3번이었으므로 3번의 경로만 찾아가면 됩니다. 하지만 그림처럼 8개의 거래가 아닌 1024개의 거래를 찾아가려면 몇 번의 해싱이 있어야 할까요? 머클 트리에서는 단 10번의 해싱만 있으면 됩니다.

(log2[1024]=10)

따라서 거래 내역을 위조하려는 시도가 있어도 머클 트리의 경로를 따라가면 해시값이 다른 것이 나오게 되어 거래의 위변조도 쉽고 빠르게 알 수도 있고, 이를 방지할 수도 있습니다.

블록체인의 용량은 시간이 지날수록 점점 커집니다. 거래량도, 거래횟수도 점점 많아지게 되고, 데이터 풀도 당연히 그만큼 커집니다. 이런 상황을 사람들인 풀 노드(Full node)로 부르는데, 머클 트리를 사용하면 일부 데이터만 다운 받을 수 있고 사용할 수 있으며, 데이터 풀에서 원하는 정보를 찾는데도 쉬워집니다. 이는 라이트 노드(light node)로 불리며 블록체인의 방대한 용량을 적게 가져갈 수 있습니다.

머클 트리가 블록체인 시장에서 맡은 진정한 역할인 셈입니다.