머클 트리는 여러 데이터를 해시로 묶어서 하나의 루트 해시를 만드는 구조입니다.

해시 글에서 봤던 핵심은 이것이었습니다.

여러 데이터
-> 각각 해시
-> 해시들을 다시 묶어 해시
-> 마지막에 Root 하나가 남음

머클 트리는 이 과정을 트리 구조로 정리한 것입니다.

왜 트리로 묶을까

거래가 아주 많다고 해보겠습니다.

어떤 거래가 블록에 포함되어 있는지 확인하려면 가장 단순하게는 블록 안의 모든 거래를 받아서 직접 찾아볼 수 있습니다.

하지만 이 방식은 무겁습니다.

Tx1
Tx2
Tx3
...
Tx1000

내가 확인하고 싶은 거래가 Tx723 하나뿐이어도 전체 거래 목록을 다 받아야 합니다.

머클 트리는 이 문제를 줄이기 위해 씁니다. 전체 거래 목록 대신, 확인하려는 거래에서 루트 해시까지 올라가는 데 필요한 주변 해시만 받습니다.

4개 거래 예시

거래가 4개 있다고 하겠습니다.

Tx1  Tx2  Tx3  Tx4

먼저 각 거래를 해시합니다.

H1 = hash(Tx1)
H2 = hash(Tx2)
H3 = hash(Tx3)
H4 = hash(Tx4)

그 다음 두 개씩 묶어 다시 해시합니다.

H12 = hash(H1 + H2)
H34 = hash(H3 + H4)

마지막으로 위쪽 해시를 다시 묶습니다.

Root = hash(H12 + H34)

그림으로 보면 이렇게 됩니다.

Tx1  Tx2  Tx3  Tx4
 |    |    |    |
H1   H2   H3   H4
  \  /      \  /
  H12      H34
     \    /
      Root

여기서 Root는 전체 거래 묶음의 대표값입니다.

Tx2가 바뀌면 아래에서 위로 이어지는 값들이 모두 바뀝니다.

Tx2 변경
-> H2 변경
-> H12 변경
-> Root 변경

그래서 루트 해시가 같다는 것은, 같은 규칙으로 계산했을 때 아래 데이터 묶음도 같다고 볼 수 있다는 뜻입니다.

Merkle proof

이제 내가 Tx2가 블록에 포함되어 있는지 확인하고 싶다고 해보겠습니다.

나는 전체 거래 목록을 받지 않습니다. 대신 풀 노드에게 Tx2가 포함되어 있다는 증거를 요청합니다.

풀 노드는 이런 값들을 줄 수 있습니다.

Tx2
H1
H34

이 값들을 보통 Merkle proof라고 부릅니다. 정확히는 Tx2에서 Root까지 다시 계산하는 데 필요한 주변 해시들입니다.

검증자는 이 값을 믿지 않습니다. 직접 다시 계산합니다.

H2 = hash(Tx2)
H12 = hash(H1 + H2)
Root' = hash(H12 + H34)

그리고 자신이 이미 알고 있던 블록 헤더의 Root와 비교합니다.

Root' == Root ?

같으면 Tx2가 그 루트 해시가 대표하는 거래 묶음 안에 포함되어 있다고 검증할 수 있습니다.

다르면 증거가 틀렸거나, Tx2가 그 블록에 포함되어 있지 않은 것입니다.

검증자는 무엇을 믿는가

검증자는 풀 노드가 준 값을 그대로 믿지 않습니다.

검증자가 기준으로 삼는 것은 자신이 이미 알고 있는 루트 해시입니다. 블록체인에서는 이 루트 해시가 블록 헤더에 들어 있습니다.

그래서 구조를 이렇게 나눠서 보면 이해하기 쉽습니다.

풀 노드가 주는 것:
Tx2, H1, H34

검증자가 이미 알고 있는 것:
Root

검증자가 직접 하는 것:
Root'를 다시 계산해서 Root와 비교

핵심은 이 문장입니다.

증거는 다른 노드에게 받지만, 증거가 맞는지는 내가 가진 루트 해시로 직접 계산해서 확인한다.

이더리움에서는 어떻게 쓰이나

이더리움은 단순한 머클 트리만 쓰지는 않습니다. 실행 레이어에서는 Merkle Patricia Trie라는 변형된 구조를 사용합니다.

Ethereum.org 문서에 따르면 이더리움 블록 헤더에는 세 가지 트리 루트가 있습니다.

  • stateRoot
  • transactionsRoot
  • receiptsRoot

각 루트는 서로 다른 데이터 묶음을 대표합니다.

transactionsRoot는 블록 안의 트랜잭션 묶음과 연결되고, receiptsRoot는 트랜잭션 실행 결과 묶음과 연결됩니다. stateRoot는 계정, 잔액, 컨트랙트 상태 등 이더리움 전체 상태와 연결됩니다.

이 구조 덕분에 어떤 데이터가 특정 루트에 포함되는지 증명할 수 있습니다. 라이트 클라이언트는 모든 데이터를 직접 저장하지 않고도, 블록 헤더와 증명을 이용해 필요한 데이터를 검증할 수 있습니다.

정리

머클 트리는 많은 데이터를 하나의 루트 해시로 요약하는 구조입니다.

검증자는 전체 데이터를 다 받지 않아도 됩니다. 필요한 데이터와 주변 해시만 받아서 루트 해시를 다시 계산합니다.

오늘 기준으로는 이렇게 정리합니다.

머클 트리는 전체 데이터 묶음을 루트 해시 하나로 대표하게 만들고, Merkle proof는 특정 데이터가 그 묶음 안에 들어 있다는 것을 다시 계산으로 확인하게 해준다.

참고 자료