> For the complete documentation index, see [llms.txt](https://whs3-doge5k.gitbook.io/smartcontract-security-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://whs3-doge5k.gitbook.io/smartcontract-security-docs/basics/undefined/merkle-patricia-trie.md).

# Merkle Patricia Trie

### 머클 트리(Merkle tree)란?

해시 값으로 만들어진 이진 트리로, 블록체인의 무결성을 보장해주는 중요한 역할을 담당한다.

간단한 모식도는 다음과 같다.

<figure><img src="https://2462457462-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FLf9vwRuaws92ULgGvzTi%2Fuploads%2FsX2x9jGH7oxkCHEaiOUm%2F1.png?alt=media&amp;token=de8f8abb-c990-4dff-a907-54aca66ce8ba" alt=""><figcaption></figcaption></figure>

만약 트랜잭션이 홀수라면 가장 마지막 트랜잭션을 복제해 해시 값을 생성한다

이러한 구조로 만들어진 머클 루트를 블록 헤더의 구성으로 추가해 블록체인의 무결성을 보장해준다.

***

### 무결성 검증 과정

tx4에 대한 무결성을 검증한다고 할 때, 우리는 전체 트랜잭션에 대한 정보를 필요로 하지 않는다. h1과 tx3의 해시 값만 알고 있다면 tx4에 대한 검증을 수행할 수 있다.

<figure><img src="https://2462457462-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FLf9vwRuaws92ULgGvzTi%2Fuploads%2FEnjYRi2LnG0GAgG4QfA3%2F2.png?alt=media&amp;token=148d5b0a-b43a-43f9-b2ee-6cd5e7b3e525" alt=""><figcaption></figcaption></figure>

***

### **Patricia Trie**

중복되는 데이터를 효율성 있게 저장하기 위해 패트리샤 트리를 사용한다.

패트리샤 트리의 저장 방식은 다음과 같다.

<figure><img src="https://2462457462-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FLf9vwRuaws92ULgGvzTi%2Fuploads%2FxLBT8NDZlvPmHcvhuLlH%2F3.png?alt=media&amp;token=5a295b49-91cc-4511-b036-256d008a7eb3" alt=""><figcaption></figcaption></figure>

#### Extension Patricia Trie

이더리움은 확장 패트리샤 트리 구조를 활용한다.

확장 패트리샤 구조는 다음과 같다.

<figure><img src="https://2462457462-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FLf9vwRuaws92ULgGvzTi%2Fuploads%2F5APXBTmBg8wvEm68ANdr%2Fimage.png?alt=media&amp;token=72dd8989-219e-4a5d-81c2-b25b705c340d" alt=""><figcaption></figcaption></figure>

노드가 가지는 값은 key-value 쌍이다.

확장 패트리샤 구조는 3가지 노드로 구성되어있다.

1. **Extension Node**
   1. 아래 노드와 공유하는 값인 shared nibble
   2. next node(branch node) 포인터
2. **Branch Node**
   1. 0\~F까지 16진수 값을 가지고 가지가 퍼지는 곳
   2. value 값을 가진다 (키가 중간에 끝날 수 있기 때문)
3. **Leaf Node**
   1. key의 잔여 값과 value를 가진다

이러한 구조의 트리는 **동일한 값의 중복 저장을 막을** 뿐만 아니라 **상태 변이(값 변경)에 대해 쉽게 변환할 수 있다는 점**에서 **효율성을 증가**시킬 수 있다.

***

### Merkle Patricia Trie

이더리움은 머클 트리의 무결성 보장 특징과, 패트리샤 트리의 효율적 데이터 저장 방식을 결합한 머클 패트리샤 트리를 사용한다.

<figure><img src="https://2462457462-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FLf9vwRuaws92ULgGvzTi%2Fuploads%2FXXvHMPpZsEFDN2OewevF%2Fimage.png?alt=media&amp;token=014a4cd7-aa52-46e5-8746-5187cc2278c7" alt=""><figcaption></figcaption></figure>

노드를 연결할 때에는 RLP 인코딩과 Hashing을 거쳐 나온 값을 저장한다.

이 머클 패트리샤 트리의 루트 값은 ‘a7’ 값을 저장한 Extension Node의 RLP+Hash 값이다.