머클 트리

1.개요

머클 트리(Merkle Tree)는 대량의 데이터를 여러 단계의 해시로 묶어 하나의 값으로 압축하는 트리 형태의 자료구조이다. 1979년 랠프 머클(Ralph Merkle)이 고안하여 그의 이름을 땄으며, 해시 트리(hash tree)라고도 한다. 흔히 'Merkel Tree'로 잘못 표기되기도 하지만 정식 철자는 'Merkle Tree'이다.

구조는 이진 트리 형태가 일반적이다. 가장 아래의 잎(leaf) 노드에는 개별 데이터 조각을 SHA 같은 해시 함수로 계산한 값이 들어간다. 그 위의 부모 노드는 두 자식 노드의 해시값을 이어 붙여 다시 해시한 결과가 되고, 이 과정을 반복하면 최상단에 단 하나의 해시값이 남는다. 이 최상위 값을 머클 루트(Merkle Root)라고 부르며, 트리 아래에 있는 모든 데이터를 대표한다. 루트 해시는 마스터 해시(master hash)라고도 한다.

머클 트리의 핵심 성질은 하위 데이터가 단 한 비트라도 바뀌면 그 변화가 상위로 전파되어 머클 루트가 완전히 달라진다는 점이다. 따라서 방대한 데이터를 일일이 비교하지 않고 루트 해시 하나만 대조해도 전체의 무결성을 확인할 수 있다.

2.역사와 유래

머클 트리는 1979년 암호학자 랠프 머클이 창안했다. 그는 여러 개의 램포트(Lamport) 일회용 서명을 하나의 짧은 값으로 효율적으로 묶어 다루기 위한 방법으로 이 구조를 설계했으며, 관련 아이디어는 특허로도 정리되었다. 이름은 고안자의 성(姓)에서 유래했고, 컴퓨터 과학과 암호학 분야에서는 일반적으로 '해시 트리'라는 이름으로도 통용된다.

이후 이 구조는 특정 서명 방식에 국한되지 않고, 여러 조각으로 나뉜 데이터의 무결성을 값 하나로 요약하는 범용 도구로 자리 잡았다. 파일 시스템, 버전 관리, P2P 파일 공유, 그리고 블록체인에 이르기까지 데이터의 위·변조를 검증해야 하는 곳에서 폭넓게 채택되었다.

3.작동 원리

머클 트리는 아래에서 위로 쌓아 올리며 구성된다.

1. 잎 노드 생성: 검증 대상이 되는 각 데이터 조각(파일 블록, 거래 등)을 해시 함수에 넣어 잎 노드의 해시값을 만든다. 2. 부모 노드 결합: 인접한 두 잎 노드의 해시값을 이어 붙인 뒤 다시 해시하여 상위 노드를 만든다. 3. 반복 상향: 이 과정을 층마다 반복해 노드 수를 절반씩 줄여 나가면, 마지막에는 최상단에 단 하나의 머클 루트만 남는다.

결합에 사용하는 해시 함수는 원칙적으로 어떤 것이든 쓸 수 있다. 악의적인 변조를 막는 것이 목적이라면 SHA 계열, 타이거(Tiger), 월풀(Whirlpool) 같은 암호학적 해시 함수를 사용하고, 단순히 전송 오류만 찾으면 되는 경우에는 CRC처럼 암호학적으로 안전하지 않은 함수를 쓰기도 한다. 트리는 이진 형태가 흔하지만, 한 부모가 셋 이상의 자식을 갖는 임의 차수의 트리로도 구성할 수 있다.

4.구조와 성질

머클 트리의 가장 중요한 성질은 무결성의 상향 전파이다. 어떤 잎 노드의 원본 데이터가 조금이라도 바뀌면 그 잎의 해시가 달라지고, 이는 부모 노드를 거쳐 루트까지 연쇄적으로 바뀐다. 반대로 데이터가 그대로라면 루트 해시도 항상 동일하다. 덕분에 검증자는 전체 데이터를 보관하거나 재전송받지 않고 루트 해시 하나만 신뢰하면 된다.

또 다른 성질은 부분 검증이 가능하다는 점이다. 어떤 상위 노드의 해시값을 알면 그 노드 아래에 매달린 모든 하위 데이터를 한꺼번에 검증할 수 있다. 이 성질은 대량 데이터에서 문제 지점을 좁혀 나가는 데도 유용하다.

5.예시

거래 네 건(A, B, C, D)이 담긴 블록을 가정한다.

1. 각 거래를 해시하여 잎 노드 H(A), H(B), H(C), H(D)를 만든다. 2. 인접한 두 값을 묶어 상위 노드를 만든다: H(AB) = 해시(H(A) + H(B)), H(CD) = 해시(H(C) + H(D)). 3. 다시 이 둘을 묶어 머클 루트를 만든다: Root = 해시(H(AB) + H(CD)).

만약 어떤 검증자가 '거래 A가 이 블록에 들어 있는가'를 확인하고 싶다면, A 자신과 함께 H(B), 그리고 H(CD)라는 두 개의 값만 제공받으면 된다. 이 값들로 H(A) → H(AB) → Root를 순서대로 계산해 블록 헤더에 적힌 머클 루트와 일치하는지 보면 되기 때문이다. 거래 수가 아무리 많아져도 필요한 증명 데이터는 트리 높이에 비례해 로그 규모로만 늘어나므로 매우 효율적이다.

6.블록체인에서의 역할

블록체인에서 머클 트리는 한 블록에 담긴 트랜잭션들을 요약하는 데 쓰인다. 블록 안의 모든 거래를 잎 노드로 삼아 머클 트리를 구성하고, 그 결과로 얻은 머클 루트를 블록 헤더에 기록한다. 비트코인의 경우 이 머클 루트는 작업 대상이 되는 헤더의 일부이므로, 작업증명 및 블록 해시와 결합되어 거래 내역의 위·변조를 사실상 불가능하게 만든다. 즉 누군가 블록 안의 거래 하나를 바꾸면 머클 루트가 달라지고, 이는 블록 전체의 유효성을 깨뜨린다.

이 성질은 이중지불과 같은 부정 거래를 막는 토대가 되며, 블록 익스플로러나 노드가 블록의 정합성을 빠르게 확인하는 데도 활용된다.

7.검증 효율과 간편 결제 검증(SPV)

머클 트리의 또 다른 장점은 검증 효율성이다. 특정 거래가 블록에 포함되어 있는지 확인할 때, 전체 블록을 내려받지 않고도 해당 거래에서 루트까지 이어지는 경로상의 해시값(머클 경로 또는 머클 증명)만 있으면 검증할 수 있다.

덕분에 저사양 기기나 경량 지갑도 전체 블록체인을 저장하지 않고 거래 포함 여부를 확인하는 간편 결제 검증(SPV, Simplified Payment Verification)이 가능하다. 풀 노드가 전체 원장을 모두 보관하며 검증하는 것과 달리, 경량 클라이언트는 블록 헤더와 짧은 머클 증명만으로 특정 거래의 존재를 신뢰할 수 있다. 필요한 증명 크기가 거래 수의 로그에 비례해 늘어나므로, 네트워크가 커져도 검증 비용이 급격히 증가하지 않는다.

8.손상 데이터 탐지

머클 트리는 어느 부분이 손상되었는지를 빠르게 특정하는 데도 유리하다. 여러 조각으로 나뉜 데이터 중 일부가 변조되거나 전송 중 오류가 발생하면, 그 조각이 속한 잎 노드부터 루트까지의 경로에 있는 해시값만 달라지고 나머지 값은 그대로 유지된다.

따라서 검증자는 달라진 해시 경로를 따라 내려가며 문제가 된 조각을 좁혀 나갈 수 있고, 해당 조각만 다시 전송받으면 된다. 방대한 데이터 집합에서도 전체를 재검사하지 않고 손상 지점을 효율적으로 찾아낼 수 있다는 점이 이 구조가 널리 쓰이는 이유 중 하나이다.

9.활용 분야

머클 트리는 데이터를 여러 블록으로 나누어 주고받을 때 그 데이터가 변조되지 않았음을 보장하는 용도로 널리 쓰인다. 특히 P2P 망에서 전송받은 데이터에 오류나 악의적 변조가 있는지 검증하는 데 유용하다.

• 파일 시스템: 썬 마이크로시스템즈가 개발한 ZFS 파일 시스템이 데이터 무결성 검증에 해시 트리를 활용한다.
• 버전 관리: 깃(Git) 버전 관리 시스템은 커밋과 객체를 해시로 연결해 이력의 변조를 탐지한다.
• P2P 파일 공유: 비트토렌트 프로토콜에서 내려받은 조각의 무결성을 확인하는 데 쓰인다.
• 협업·통신 프로토콜: 구글 웨이브(Google Wave) 프로토콜 등에서도 사용되었다.
• 분산원장: 비트코인을 비롯한 암호화폐 시스템이 블록 거래를 요약하는 핵심 구조로 채택하고 있다.

10.머클 서명과 양자내성

머클 트리가 처음 고안된 배경에는 전자서명 문제가 있었다. 랠프 머클은 여러 개의 램포트 서명(Lamport signature)을 효율적으로 관리하기 위해 이 구조를 설계했다.

램포트 서명은 양자 컴퓨터가 실용화되더라도 안전할 것으로 기대되는 디지털 서명 방식이지만, 메시지 하나마다 새로운 키를 만들어야 한다는 부담이 있다. 여러 램포트 키를 머클 트리로 묶으면 다수의 공개키를 루트 해시 하나로 대표할 수 있어 관리가 한결 효율적이다. 이렇게 해시 트리를 이용한 서명 방식을 머클 서명(Merkle signature scheme)이라고 부르며, 해시 기반 서명은 오늘날 양자내성 암호 연구에서 주목받는 계열 중 하나이다.

11.한계와 과제

머클 트리는 무결성 검증에는 강력하지만 만능은 아니다. 루트 해시는 데이터가 '바뀌었는지'는 알려주지만 '무엇이 올바른 값인지'는 알려주지 않으므로, 신뢰할 수 있는 루트 해시를 어디서 얻느냐가 여전히 중요하다.

또한 결합에 쓰는 해시 함수의 안전성에 전적으로 의존한다. 오류 탐지만이 목적일 때는 CRC 같은 함수도 가능하지만, 악의적 변조를 막으려면 SHA 계열처럼 충돌 저항성이 검증된 암호학적 해시 함수를 써야 한다. 과거 SHA-1 등 일부 해시 함수의 안전성이 약화된 사례가 있었던 만큼, 시스템 설계 시 해시 함수의 선택과 갱신은 지속적인 과제로 남는다.

12.연표4건

1. 1979설립랠프 머클이 다수의 일회용 서명을 효율적으로 다루기 위한 해시 트리 구조를 고안하고 특허로 정리
2. 2001이정표비트토렌트 프로토콜 등장으로 P2P 조각 전송의 무결성 검증에 해시 트리 계열 기법이 활용됨
3. 2005이정표깃(Git) 버전 관리 시스템이 공개되어 커밋과 객체 무결성 검증에 해시 연결 구조를 채택
4. 2009이정표비트코인이 가동을 시작하며 블록 내 거래를 머클 트리로 요약해 머클 루트를 블록 헤더에 기록