MPT 의 구조와 역할

머클 페트리시아 트리(Merkle Patricia Trie)는 이더리움의 핵심 데이터 구조 중 하나로, 상태(state), 거래(transaction), 영수증(receipt) 등을 저장하고 검증 가능한 방식으로 구성하기 위해 사용됩니다. 다음은 그 구조, 특징, 작동방식, 이더리움에서의 역할을 기술 블로그 수준으로 자세히 설명한 내용입니다.

⸻

1. 개요: 왜 머클 페트리시아 트리를 사용하는가?

이더리움은 모든 상태를 블록체인 위에서 신뢰 가능하게 저장하고 검증할 수 있어야 합니다. 이를 위해 사용하는 것이 머클 트리(Merkle Tree)와 패트리시아 트라이(Trie)의 결합 구조인 머클 페트리시아 트리(MPT)입니다.
• 머클 트리: 데이터의 무결성을 해시로 보장.
• 패트리시아 트라이: 키-값 쌍을 압축하여 효율적인 저장을 가능하게 함.
• 머클 페트리시아 트리: 위 두 개의 장점을 결합하여 이더리움의 상태 저장 및 검증에 사용.

⸻

2. 구조: 머클 트리 + 패트리시아 트라이

(1) 기본 구성

MPT는 키-값(key-value) 구조의 데이터를 저장하며 다음 세 가지 노드로 구성됩니다:

노드 타입	설명
Leaf Node	최종 값(계정 정보, 스토리지 값 등)을 저장
Extension Node	중간 경로(prefix)를 저장하여 트리 깊이 축소
Branch Node	16진수(0~f) 기반 16개의 포인터 + 값 필드를 가짐

(2) 키 구조

MPT는 키를 16진수 nibble로 변환한 후 사용합니다. 예:
• 키: 0xa1b3 → nibble: [a, 1, b, 3]

압축 경로(prefix compression)를 통해 중복된 경로는 Extension으로, 분기되는 지점은 Branch로, 최종 값은 Leaf로 표현됩니다.

⸻

3. 작동 방식

(1) 삽입
1. 키를 nibble로 변환하여 경로로 사용.
2. 경로가 겹치는 경우 extension/branch를 만들어 분기.
3. 최종 경로에 값 저장 (Leaf Node).

(2) 조회
1. 루트에서 시작하여 nibble 경로를 따라 노드 순회.
2. Leaf 또는 Branch의 값 필드에서 최종 결과 도달.

(3) 삭제
1. 해당 경로의 Leaf 제거.
2. 경로가 중복되지 않게 되면 Extension/Branch 재구성.

⸻

4. 해시와 머클 구조

각 노드는 RLP(RLP 인코딩)된 형태로 해싱되며, 이 해시들이 상위 노드에 포함되어 루트 해시까지 이어집니다. 이를 통해:
• 전체 트리의 무결성 보장
• 특정 데이터가 존재함을 루트 해시만으로 증명 가능 (Merkle Proof)

⸻

5. 이더리움에서의 역할

이더리움은 3개의 주요 MPT를 유지합니다:

트리 이름	설명	루트 해시 위치
State Trie	주소 → 계정 상태 (Nonce, Balance, CodeHash, StorageRoot)	블록 헤더의 stateRoot
Storage Trie	계정의 스토리지 슬롯 → 값	계정의 storageRoot
Transaction Trie	트랜잭션 인덱스 → 트랜잭션	블록 헤더의 transactionsRoot
Receipt Trie	트랜잭션 인덱스 → receipt	블록 헤더의 receiptsRoot

예: 계정 정보 조회 흐름
1. 상태 루트 (stateRoot)를 통해 State Trie 접근
2. 계정 주소 → RLP → keccak256 → 경로
3. 해당 노드에서 계정 정보 추출 (Balance 등)
4. 스토리지 필요 시, storageRoot를 사용해 Storage Trie 접근

⸻

6. 요약: MPT의 장점

특징	설명
무결성 보장	루트 해시만으로 전체 트리의 정합성 검증 가능
변경 추적	데이터 하나만 바뀌어도 루트 해시가 바뀜 (불변성)
경로 최적화	중복되는 경로는 압축하여 저장 (효율적)
이더리움 적합	블록체인의 탈중앙 상태 검증과 궁합이 뛰어남

⸻

참고: MPT 시각화 예시

        Root Hash
           |
       Branch (a)
      /     |     \
   Ext     ...    Ext
   ("1")         ("3")
     |             |
  Leaf(a1b)     Leaf(a3f)

⸻