블록 헤더에 있는 머클 루트와, 머클 트리에 대해서 알아보자.
2025.12.07 - [분류 전체보기] - 비트코인 블록 헤더 구조 분석
비트코인 블록 헤더 구조 분석
비트코인은 블록체인으로 만들어져 있다는 얘기는 이제는 너무 유명하다.블록체인이란 블록을 해싱해서 체인으로 연결했기에 이와 같이 불린다.사토시가 제시한 백서에서는 공식적으로 블록
3min-bitcoin.tistory.com
비트코인 블록 헤더가 뭔지 모르겠다면 위 글 먼저!
머클 트리 (Merkle Tree)
머클 트리는 해시 트리라는 자료구조의 일종인데, 1979년도에 Ralph Merkle이라는 사람이 특허를 내서 이름이 머클 트리가 되었다.
즉, 해시트리와 머클트리는 아예 같은 것이다.
트리구조에서 맨 아래에 있는 노드, 자식이 없는 노드를 리프(leaf)노드라고 한다.
머클 트리에서 리프 노드는 데이터블록이 해시 함수로 해싱되어 해시값으로 라벨링 된다.
리프 노드가 아닌 노드의 경우는 가지 노드, 내부 노드 등으로 불리고 자식 노드들의 해시값으로 또 해시를 해서 라벨링된다.
위 그림을 보면 이해하기 쉬운데, L1이라는 데이터를 가진 리프 노드는 hash(L1)으로 해싱된 라벨값을 갖는다.
그리고 그 L1, L2가 만나는 Hash 0을 보면 두 해시값이 합쳐지고, 또 그 값을 해싱해서 라벨링한다.
머클 트리에서 해시함수는 아무거나 써도 되는데 목적에 따라 나뉜다.
데이터 변조를 막으려면 SHA 계열을, 그냥 데이터 오류 검증을 위한 것이라면 CRC 등
비트코인에서는 데이터 변조를 막아야 하므로 SHA256을 사용한다.
비트코인에서 위 그림의 L1, L2같은 리프노드에는 트랜잭션이 들어가는 것이고,
그 트랜잭션을 해싱해서 라벨값을 붙인게 TXID이다.
머클 루트 (Merkle Root)
머클 루트는 위 과정을 계속 반복하여 최종적으로 남은 최상단 1개를 뜻한다.
그리고 이는 블록 헤더에 들어가서 해싱되기 때문에, 그 안에 포함된 모든 트랜잭션을 더이상 변조될 수 없게 만든다.
과거 데이터 트랜잭션 하나를 수정해서 이중지불 시도를 하려고 한다고 해도
해시의 눈사태 효과로 머클 루트가 변경되기 때문에 절대로 불가능하다.
TXID (Transaction ID)
위 머클 트리의 리프 노드에 들어가는 원천 데이터는 바로 거래내역, 트랜잭션이다.
트랜잭션 데이터를 HASH256을 사용하여 해싱해서 TXID를 뽑아낸다.
HASH256은 SHA256 함수를 두 번 사용하는 경우를 말한다. sha256(sha256(tx))
세그윗 업데이트 이전과 이후로 구분되어 해싱되는 데이터가 약간의 차이가 있지만 이번 포스팅 주제와는 의미 없기에 스킵
그러면 트랜잭션이 홀수개면 어떻게 처리해요?
만약 트랜잭션 개수가 홀수라면 어떻게 처리하게 되는가?
혹은 2의 지수로 떨어지지 않아서 좌우가 불균형한 트리 모양이 되면 어떻게 되는가? (이것도 leaf가 아니라 그 상위 가지에서 결국 홀수개가 되기 때문에 위 문제와 사실상 동일한 문제이다)
라는 궁금증이 생길만 하다.
해답은 간단한데, 머클 트리에서 트랜잭션 개수가 홀수개면 마지막 데이터를 복제해서 해싱한다.
[1, 2, 3, 4, 5, 6, 7] 리스트가 이와 같을 경우
[1, 2, 3, 4, 5, 6, 7, 7] 로 복제해한다는 뜻이다.
CVE-2012-2459 취약점
그런데 복제를 해서 처리하다보면 심각한 결함이 하나 있다.
위 그림에서 F 노드가 복제된건지, 아니면 공격자가 의도적으로 [5, 6]을 추가한건지 파악을 할 수 없다는 문제가 생긴다.
이를 방지하기 위해 시스템에서 마지막 데이터를 복제하기 전에 같은 값이 있으면 공격으로 간주한다.
예를 들어, 복제하기 전에 [6, 6]이 이미 있으면 공격자가 6을 인위적으로 추가했다고 파악을 하는것이다.
혹은 [F, F]가 발생해도 공격자가 [5, 6]을 추가했다고 파악을 해서 유효하지 않은 머클 트리로 간주한다는 것이다.
그렇게 되면 해당 블록은 유효하지 않은 블록이 되어 검증에 실패하고 다른 노드들로 전파되지 않는다.
이는 머클 루트를 계산하는 비트코인 소스코드이다.
mutation 변수가 위조되었는지 체크하는 boolean 값이다.
if (hashes[pos] == hashes[pos + 1]) mutation = true 로 위조되었다고 판단하는 로직으로 취약점을 방어했다.