> ## Documentation Index
> Fetch the complete documentation index at: https://docs.stablenet.network/llms.txt
> Use this file to discover all available pages before exploring further.

# 데이터베이스 레이어 및 Merkle Patricia Trie

## 목적 및 범위

이 문서는 StableNet에서 trie 노드를 저장하는 Merkle Patricia Trie 데이터 구조와 데이터베이스 레이어를 설명합니다.\
Trie는 효율적인 검색, 증명 생성, 결정론적 루트 해시 계산을 통해 암호화 인증 키-값 저장소를 제공합니다.

다루는 주요 주제:

* **Trie 구조**: 노드 타입(shortNode, fullNode, valueNode, hashNode)와 트리 구성
* **노드 인코딩**: 키 인코딩 스키마(keybytes, hex, compact)와 RLP 직렬화
* **Trie 데이터베이스**: 저장소 스키마(해시 기반, 경로 기반)와 노드 영속성
* **Merkle 증명**: 증명 생성, 검증 및 사용 사례

StateDB가 상태 관리를 위해 이러한 trie를 사용하는 방법에 대한 정보는 [상태 관리](/ko/core-architecture/3.3-state-management)을 참조하세요.\
스냅샷 기반 최적화는 [캐싱 및 스냅샷](/ko/storage-architecture/9.2-caching-and-snapshots)을 참조하세요.\
과거 블록 데이터를 처리하는 ancient store는 [고대 저장소 및 데이터 라이프사이클](/ko/storage-architecture/9.3-ancient-store-and-data-lifecycle)을 참조하세요.

## Merkle Patricia Trie 개요

Merkle Patricia Trie는 Merkle 트리와 Patricia trie(radix tree)의 특성을 결합한 암호화 인증 데이터 구조입니다. 다음을 가능하게 합니다:

* O(log n) 복잡도의 **효율적인 키-값 저장 및 조회**
* Merkle 루트 해싱을 통한 **상태 커밋**
* 전체 상태를 보유하지 않아도 가능한 **상태 증명 생성**
* 모든 노드가 동일한 결과를 얻는 **결정론적 루트 계산**

StableNet은 두 가지 목적을 위해 trie를 사용합니다:

1. **계정 Trie**\
   계정 주소를 계정 상태(잔액, nonce, 저장소 루트, 코드 해시)에 매핑합니다.
2. **저장소 Trie**\
   각 컨트랙트 계정은 저장소 슬롯을 값에 매핑하는 독립적인 저장소 trie를 가집니다.

## Trie 노드 타입

### 노드 타입 설명

| Node Type     | Purpose         | Structure              | Usage                     |
| ------------- | --------------- | ---------------------- | ------------------------- |
| **shortNode** | 공통 prefix 경로 압축 | `Key []byte, Val node` | 여러 키가 동일한 prefix를 공유할 때   |
| **fullNode**  | 분기 노드           | `Children [17]node`    | 16개의 nibble 분기 + value 슬롯 |
| **valueNode** | 리프 값            | `[]byte`               | RLP 인코딩된 실제 값 저장          |
| **hashNode**  | 축약 참조           | 32-byte hash           | 디스크에 저장된 하위 trie 참조       |

`nodeFlag` 구조는 노드의 캐시 상태를 관리합니다:

```text theme={null}
type nodeFlag struct {
    hash  hashNode // 노드의 캐시된 해시
    dirty bool     // 노드가 수정되었는지 여부
}
```

## 키 인코딩 스키마

Trie는 서로 다른 목적을 위해 세 가지 키 인코딩 형식을 사용합니다.

### 인코딩 형식

| Format       | Description            | Usage      | Example (key = 0x123) |
| ------------ | ---------------------- | ---------- | --------------------- |
| **keybytes** | 원본 바이트                 | 외부 API     | `[0x12, 0x03]`        |
| **hex**      | nibble 배열 + terminator | 내부 trie 연산 | `[1, 2, 3, 16]`       |
| **compact**  | nibble 압축 포맷           | 직렬화 / 증명   | nibble + 플래그 비트       |

hex 형식은 각 4비트 nibble을 개별 바이트로 표현하며, 값 `16`은 경로 종료를 의미합니다.\
compact 형식은 nibble을 압축하고 리프/확장 여부와 길이 정보를 플래그로 인코딩합니다.

## 2-Trie 아키텍처

### 계정 Trie

계정 trie는 **Keccak256으로 해시된 주소**를 키로 사용합니다.\
값은 RLP 인코딩된 `types.StateAccount` 구조체입니다.

### 저장소 Trie

각 컨트랙트는 자체 저장소 trie를 가지며 다음과 같이 구성됩니다:

* **Owner**: 계정 주소의 Keccak256 해시
* **Key**: 저장소 슬롯의 Keccak256 해시
* **Value**: RLP 인코딩된 저장소 값(선행 0 제거)

## Trie 작업

### Get 작업

`Trie.get()`은 루트부터 재귀적으로 노드를 탐색하며,\
`hashNode`를 만날 경우 데이터베이스에서 노드를 로드합니다.

### Update 작업

Update는 즉시 해시를 계산하지 않고 노드를 dirty 상태로 표시합니다.\
실제 해싱은 커밋 단계에서 수행되며,`unhashed` 카운터는 해시되지 않은 리프 수를 추적합니다.

### Delete 작업

Delete는 키-값 쌍을 제거하고,\
단일 자식만 남은 분기 노드는 shortNode로 축소됩니다.

## 해싱 및 커밋

### Hasher 구성 요소

`hasher`는 하향식(top-down) 해시 계산을 수행합니다:

1. 자식 노드부터 재귀적으로 해싱
2. RLP 인코딩 크기가 32바이트 이상이면 `hashNode`로 축소
3. 노드 구조를 RLP로 직렬화
4. Keccak256 해시 계산
5. 결과를 `nodeFlag.hash`에 캐시

### Committer 구성 요소

`committer`는 해시가 완료된 trie를 순회하며 dirty 노드를 수집합니다.

**출력:**\
`trienode.NodeSet` – 경로 → 노드 데이터의 집합으로, 데이터베이스 기록에 사용됩니다.

## 상태 루트 계산

상태 루트는 다음 단계를 통해 계산됩니다:

1. **Finalise**\
   dirty 저장소를 pending 상태로 전환하고 저장소 루트 갱신
2. **updateRoot()**\
   계정별 저장소 trie 루트 반영
3. **updateStateObject()**\
   계정 데이터를 계정 trie에 반영
4. **IntermediateRoot()**\
   계정 trie 해싱
5. **Commit()**\
   모든 trie 커밋 및 NodeSet 생성

## 증명 생성 및 검증

### 증명 구조

Merkle 증명은 루트에서 특정 리프까지의 RLP 인코딩된 노드 시퀀스로 구성됩니다.

* **증명 크기:** O(log n)\
  Ethereum 상태 기준 약 500\~2000 바이트

**사용 사례:**

* 라이트 클라이언트 상태 검증
* 상태 동기화
* 크로스체인 브리지용 저장소 증명

## Trie 데이터베이스 레이어

Trie 데이터베이스 레이어는 trie 노드를 디스크에 영속화하고, `hashNode` 또는 경로 기반 참조를 실제 노드로 해석합니다.

StableNet은 두 가지 저장소 스키마를 지원합니다.

### 해시 스키마(레거시)

**노드 키:** `Keccak256(RLP(node))`

```text theme={null}
Key:   32-byte hash
Value: RLP-encoded node
```

**특성:**

* 단순한 키-값 구조
* 경로 정보 미보존
* 가비지 컬렉션 필요
* 과거 상태 조회에 불리함

### 경로 스키마(현대)

**노드 키:** `owner_hash + path_from_root`

```text theme={null}
Key:   owner (32 bytes) + path
Value: RLP-encoded node
```

**특성:**

* 경로 기반 주소 지정
* 상태 히스토리 및 빠른 롤백 가능
* diff 레이어를 통한 변경 추적
* 아카이브 노드에 적합

## 상태 관리와의 통합

### 작업 흐름

**계정 액세스:**

1. StateDB 캐시 확인
2. 스냅샷 또는 계정 trie에서 로드
3. `types.StateAccount` 디코딩
4. `stateObject` 생성

**저장소 액세스:**

1. dirty → pending → origin 순서로 조회
2. 미스 시 저장소 trie 조회
3. RLP 디코딩

**커밋 흐름:**

1. `Finalise()`
2. `updateRoot()`
3. `updateStateObject()`
4. `Commit()`
5. `triedb.Update()`

## 주요 구현 세부사항

### Trie 프리페칭

`triePrefetcher`는 트랜잭션 실행 중 접근 가능성이 높은 노드를 비동기로 미리 로드하여 지연을 줄입니다.

```text theme={null}
- 저장소 trie 단위로 goroutine 생성
- 예상 접근 경로 기반 프리페치
- 트랜잭션 실행 성능 개선
```

### 노드 반복자

`nodeIterator`는 전위 순회 방식으로 모든 trie 노드를 탐색합니다.

```text theme={null}
- 상태 동기화에 사용
- 증명 생성에 사용
- hashNode를 지연 로딩
- 경로 및 스택 유지
```

### Tracer

`tracer`는 trie 변경 내역을 추적하여 경로 기반 스키마 및 디버깅에 활용됩니다.

```text theme={null}
- 삽입/삭제 기록
- 접근 경로 매핑
- path 기반 DB 필수 구성요소
```

**요약:**\
Merkle Patricia Trie는 StableNet 상태 저장소의 핵심 암호화 구조입니다.\
계정/저장소 2-trie 구조와 유연한 저장소 스키마를 통해 과거 상태 조회와 라이트 클라이언트 검증을 모두 안전하고 효율적으로 지원합니다.