Merkle Tree

머클트리

머클 트리는 데이터의 위변조를 검사할 때 매우 효율적인 자료구조이다. 머클 트리를 통해 모든 노드가 블록 체인의 모든 정보를 가지있지 않아도 트랜잭션을 확인할 수 있게 되었다.

Merkle 트리의 구

기본적으로 Binary Tree의 구조를 따르기 때문에 부모 노드가 2개의 자식 노드(왼쪽 노드, 오른쪽 노드)를 가진다. 머클 트리는 리프(Leaf) 노드부터 2개씩 짝을 지어 루트(Root) 노드까지 부모노드를 생성한다. 트리를 만드는 과정은 다음과 같다.

리프 노드는 트랜잭션 하나에 대응됩니다. 트랜잭션의 해시값을 데이터로 갖는 리프 노드를 생성합니다.
리프 노드는 형제 노드(sibling)의 해시값과 자신의 해시값을 합쳐서 새로 해시값을 구합니다. 새로 구한 해시값을 갖는 부모 노드를 생성합니다.
하나의 노드만 남을 때까지 이를 반복합니다. 이 노드가 루트 노드입니다.

아래 그림은 트랜잭션 4개로 머클 트리를 구성할 때의 예시이다.

풀 노드와 라이트 노드

비트코인 네트워크에 참여하는 노드는 블록체인의 모든 정보를 저장하는 풀노드와 일부 정보(머클 트리의 루트 포함한 헤더)만을 저장하는 라이트 노드로 구별된다.

저장 공간이 적은 스마트폰의 경우 블록체인 전체를 저장할 수 없으므로 라이트 노드로 사용된다. 라이트 노드는 트랜잭션을 검증하기 위한 정보가 부족하여 풀 노드에게 검증에 필요한 데이터를 추가적으로 요청하여 거래를 검증한다. 이를 단순 지불 검증(Simple Payment Verification, SPV)이라고 부른다.

Merkle Path

라이트 노드가 어떤 트랜잭션이 유효한 트랜잭션인지 검증하려고 한다. 해당 트랜잭션을 검증하기 위해서 풀 노드로 부터 얻어와야하는 값이 무엇일까?

라이트 노드는 머클트리의 루트는 알고있다. 지금 새로 들어온 해시값이 bb인 트랜잭션을 검증하고 싶다. 아래 그림은 현재 라이트 노드가 알고있는 정보를 그림으로 나타낸 것이다.

Hash값이 bb인 이 트랜잭션을 검증하기 위해서 풀 노드로 부터 노드의 정보를 알아와야한다. 하지만 머클 트리의 모든 노드를 알아올 필요는 없고, 루트 노드를 다시 계산 하기 위해 필요한 노드의 정보만 요청하면 된다. 아래 주황색으로 표시된 노드들이 루트를 재구성하는 데 필요한 노드들이다.

위 그림에서 풀 노드로 부터 얻어온 Leaf Node4의 데이터 bc와 검증하고자하는 트랜잭션의 데이터 bb를 통해 그 부모 노드의 데이터 11을 구할 수 있고, 다시 11과 Node1의 데이터 ff를 통해 루트 노드의 데이터 jy를 구할 수 있다. 새로 구한 루트 노드의 데이터가 기존의 루트 노드의 데이터와 일치하므로 트랜잭션은 유효하다.

만약 검증해야할 트랜잭션의 해시값이 bb가 아니였다면 루트 데이터가 달라져서 검증에 실패했을 것이다.

검증에 필요한 최소한의 노드들을 Merkle path라고 부른다.