메인 콘텐츠로 건너뛰기

​
목적 및 범위

이 문서는 StableNet에서 trie 노드를 저장하는 Merkle Patricia Trie 데이터 구조와 데이터베이스 레이어를 설명합니다.
Trie는 효율적인 검색, 증명 생성, 결정론적 루트 해시 계산을 통해 암호화 인증 키-값 저장소를 제공합니다. 다루는 주요 주제:
  • Trie 구조: 노드 타입(shortNode, fullNode, valueNode, hashNode)와 트리 구성
  • 노드 인코딩: 키 인코딩 스키마(keybytes, hex, compact)와 RLP 직렬화
  • Trie 데이터베이스: 저장소 스키마(해시 기반, 경로 기반)와 노드 영속성
  • Merkle 증명: 증명 생성, 검증 및 사용 사례
StateDB가 상태 관리를 위해 이러한 trie를 사용하는 방법에 대한 정보는 상태 관리을 참조하세요.
스냅샷 기반 최적화는 캐싱 및 스냅샷을 참조하세요.
과거 블록 데이터를 처리하는 ancient store는 고대 저장소 및 데이터 라이프사이클을 참조하세요.

​
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 TypePurposeStructureUsage
shortNode공통 prefix 경로 압축Key []byte, Val node여러 키가 동일한 prefix를 공유할 때
fullNode분기 노드Children [17]node16개의 nibble 분기 + value 슬롯
valueNode리프 값[]byteRLP 인코딩된 실제 값 저장
hashNode축약 참조32-byte hash디스크에 저장된 하위 trie 참조
nodeFlag 구조는 노드의 캐시 상태를 관리합니다: 
type nodeFlag struct {
    hash  hashNode // 노드의 캐시된 해시
    dirty bool     // 노드가 수정되었는지 여부
}

​
키 인코딩 스키마

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

​
인코딩 형식

FormatDescriptionUsageExample (key = 0x123)
keybytes원본 바이트외부 API[0x12, 0x03]
hexnibble 배열 + terminator내부 trie 연산[1, 2, 3, 16]
compactnibble 압축 포맷직렬화 / 증명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)) 
Key:   32-byte hash
Value: RLP-encoded node
특성:
  • 단순한 키-값 구조
  • 경로 정보 미보존
  • 가비지 컬렉션 필요
  • 과거 상태 조회에 불리함

​
경로 스키마(현대)

노드 키: owner_hash + path_from_root 
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는 트랜잭션 실행 중 접근 가능성이 높은 노드를 비동기로 미리 로드하여 지연을 줄입니다. 
- 저장소 trie 단위로 goroutine 생성
- 예상 접근 경로 기반 프리페치
- 트랜잭션 실행 성능 개선

​
노드 반복자

nodeIterator는 전위 순회 방식으로 모든 trie 노드를 탐색합니다. 
- 상태 동기화에 사용
- 증명 생성에 사용
- hashNode를 지연 로딩
- 경로 및 스택 유지

​
Tracer

tracer는 trie 변경 내역을 추적하여 경로 기반 스키마 및 디버깅에 활용됩니다. 
- 삽입/삭제 기록
- 접근 경로 매핑
- path 기반 DB 필수 구성요소
요약:
Merkle Patricia Trie는 StableNet 상태 저장소의 핵심 암호화 구조입니다.
계정/저장소 2-trie 구조와 유연한 저장소 스키마를 통해 과거 상태 조회와 라이트 클라이언트 검증을 모두 안전하고 효율적으로 지원합니다.