Advanced Trie Structures TODO

Algorithms · Day 5 / 100 · A. Advanced Algorithms & Data Structures (Day 1-19)

Concept

A trie represents a key as a path split character by character, and a Patricia trie is a variant that shrinks depth by compressing any run of single-child nodes into one edge (path compression). Ethereum's Merkle Patricia Trie (MPT) layers Merkle hashing on top of that: each node holds the hashes of its children, and a parent re-hashes those hashes, so the entire state gets committed to a single root hash. Because MPT branch nodes fan out by nibble (4 bits), a node can have up to 16 children, so a proof for one node must include all its sibling hashes — proof size grows roughly in proportion to (path depth × branching factor). Verkle tries replace hashing with vector commitments (a polynomial-commitment family), collapsing all of a node's children into one constant-size commitment and making membership proofs close to constant size as well. The cost is that a node update is no longer a single hash but an elliptic-curve operation, so write and reconstruction costs go up — the choice within this family ultimately trades off proof size against update cost.

State proof size directly determines the bandwidth cost for light clients and stateless verification, while update cost determines a full node's block-processing time. Without knowing which side you're trying to shrink, you can't judge the feasibility of a storage-layer design or a proof-based feature.

Code & Formula

# Day 5: 트라이 계열 심화 — 패트리샤(Patricia) 트라이의 경로 압축
# 공통 접두사를 압축해 간선에 저장하는 라딕스 트라이를 구현해 삽입/탐색과 압축 효과를 확인한다.

class PatriciaNode:
    def __init__(self):
        self.children = {}   # edge_label(str) -> PatriciaNode
        self.is_word = False

def common_prefix_len(a, b):
    n, i = min(len(a), len(b)), 0
    while i < n and a[i] == b[i]:
        i += 1
    return i

def insert(root, word):
    node, remaining = root, word
    while remaining:
        for label in list(node.children):
            common = common_prefix_len(label, remaining)
            if common == 0:
                continue
            if common == len(label):
                node, remaining = node.children[label], remaining[common:]
                break
            mid = PatriciaNode()                        # 공통 접두사에서 간선을 분기
            mid.children[label[common:]] = node.children.pop(label)
            node.children[label[:common]] = mid
            node, remaining = mid, remaining[common:]
            break
        else:
            node.children[remaining] = PatriciaNode()
            node, remaining = node.children[remaining], ""
    node.is_word = True

def search(root, word):
    node, remaining = root, word
    while remaining:
        for label, child in node.children.items():
            if remaining.startswith(label):
                node, remaining = child, remaining[len(label):]
                break
        else:
            return False
    return node.is_word

def count_edges(node):
    return sum(1 + count_edges(c) for c in node.children.values())

words = ["romane", "romanus", "romulus", "rubens", "ruber", "rubicon", "rubicundus"]
root = PatriciaNode()
for w in words:
    insert(root, w)

print(f"압축된 간선 수 = {count_edges(root)} (단어 {len(words)}개, 총 문자수 {sum(len(w) for w in words)})")
print("search('romanus') =", search(root, "romanus"))
print("search('roman')   =", search(root, "roman"))
print("search('rubicon')  =", search(root, "rubicon"))

docs/code/algorithms/algorithms-5.py

Exercise

Implement a simple Patricia trie and a nibble-branching MPT with the same set of keys/values, then tabulate the node count and total byte size of a Merkle proof for a given key as you vary the branching factor.

Practical Connection

If Verex ever needs to prove settlement results or position state to the outside world, or have them verified by a light client, the size of a single state proof becomes the client's actual cost — the trie structure choice shows up directly in that number.

Where it lands in Jayverse

• Verex: decide the settlement-proof scheme now, as a written tradeoff. If a light-client verifier for settlement results is ever built, choose between MPT-style branch proofs and a Verkle-style constant-size commitment, and record the proof-size-vs-update-cost tradeoff before writing the contract.
• Devnet: benchmark actual MPT proof sizes for Verex's real state keys before considering Verkle. Anvil and Sepolia already use MPT, so measure the branching-factor-driven proof size for the specific keys Verex would need to prove, turning "when do we need Verkle" into a number.
• gitboard: track settlement-proof byte size as a dashboard metric. Once the exercise's node-count/byte-size table exists, keep the real number on gitboard so a future light-client feature is scoped against data, not assumption.

If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.

한국어

Verkle tree TODO

Algorithms · Day 5 / 100 · A. 고급 알고리즘·자료구조 (Day 1–19)

이더리움의 Merkle-Patricia Trie에서 해시 기반 증명 대신 다항식 벡터 커밋먼트(KZG)를 사용해서, 각 노드가 훨씬 넓은 분기 수를 가지면서도 증명 크기는 작게 유지할 수 있게 한 개선입니다 — 이게 바로 stateless 이더리움 클라이언트를 실용적으로 만드는 핵심입니다

개념

트라이는 키를 문자 단위로 쪼개 경로로 표현하는 자료구조이고, 패트리샤 트라이는 자식이 하나뿐인 연속 구간을 하나의 간선으로 압축(path compression)해 깊이를 줄인 변형이다. 이더리움의 Merkle Patricia Trie(MPT)는 여기에 머클 해시를 얹어, 각 노드가 자식들의 해시를 담고 부모는 그 해시들을 다시 해시하는 방식으로 상태 전체를 하나의 루트 해시로 커밋한다. MPT의 분기 노드는 니블(4비트) 단위라 자식이 최대 16개이므로, 한 노드의 증명에는 형제 해시들이 모두 들어가고 증명 크기는 대략 (경로 깊이 × 분기 폭)에 비례해 커진다. Verkle 트라이는 해시 대신 벡터 커밋먼트(다항식 커밋먼트 계열)를 써서 한 노드의 자식 전체를 상수 크기 커밋먼트 하나로 묶고, 열람 증명도 상수 크기에 가깝게 만든다. 대가로 노드 갱신이 해시 한 번이 아니라 타원곡선 연산이 되어 쓰기·재구성 비용이 올라가므로, 이 계열의 선택은 결국 증명 크기와 갱신 비용 사이의 교환이다.

상태 증명 크기는 라이트 클라이언트와 stateless 검증의 대역폭을 직접 결정하고, 갱신 비용은 풀노드의 블록 처리 시간을 결정한다. 어느 쪽을 깎을지 모르면 스토리지 계층 설계나 증명 기반 기능의 실현 가능성을 판단할 수 없다.

코드 · 수식

# Day 5: 트라이 계열 심화 — 패트리샤(Patricia) 트라이의 경로 압축
# 공통 접두사를 압축해 간선에 저장하는 라딕스 트라이를 구현해 삽입/탐색과 압축 효과를 확인한다.

class PatriciaNode:
    def __init__(self):
        self.children = {}   # edge_label(str) -> PatriciaNode
        self.is_word = False

def common_prefix_len(a, b):
    n, i = min(len(a), len(b)), 0
    while i < n and a[i] == b[i]:
        i += 1
    return i

def insert(root, word):
    node, remaining = root, word
    while remaining:
        for label in list(node.children):
            common = common_prefix_len(label, remaining)
            if common == 0:
                continue
            if common == len(label):
                node, remaining = node.children[label], remaining[common:]
                break
            mid = PatriciaNode()                        # 공통 접두사에서 간선을 분기
            mid.children[label[common:]] = node.children.pop(label)
            node.children[label[:common]] = mid
            node, remaining = mid, remaining[common:]
            break
        else:
            node.children[remaining] = PatriciaNode()
            node, remaining = node.children[remaining], ""
    node.is_word = True

def search(root, word):
    node, remaining = root, word
    while remaining:
        for label, child in node.children.items():
            if remaining.startswith(label):
                node, remaining = child, remaining[len(label):]
                break
        else:
            return False
    return node.is_word

def count_edges(node):
    return sum(1 + count_edges(c) for c in node.children.values())

words = ["romane", "romanus", "romulus", "rubens", "ruber", "rubicon", "rubicundus"]
root = PatriciaNode()
for w in words:
    insert(root, w)

print(f"압축된 간선 수 = {count_edges(root)} (단어 {len(words)}개, 총 문자수 {sum(len(w) for w in words)})")
print("search('romanus') =", search(root, "romanus"))
print("search('roman')   =", search(root, "roman"))
print("search('rubicon')  =", search(root, "rubicon"))

docs/code/algorithms/algorithms-5.py

연습

같은 키/값 집합을 넣은 간단한 패트리샤 트라이와 니블 분기 MPT를 직접 구현해, 임의의 키 하나에 대한 머클 증명의 노드 수와 총 바이트 수를 분기 폭을 바꿔 가며 표로 비교해 보라.

실무 · Verex 연결

Verex가 정산 결과나 포지션 상태를 외부에 증명하거나 라이트 클라이언트에서 검증하게 하려면, 상태 증명 한 건의 크기가 곧 클라이언트 비용이 되므로 트라이 구조 선택의 영향이 그대로 드러난다.

Jayverse에서의 위치

• Verex: 정산 프루프 스킴을 지금 문서화된 트레이드오프로 결정한다. 정산 결과를 위한 라이트클라이언트 검증기를 언젠가 만든다면, MPT 방식 브랜치 프루프와 Verkle 방식 상수 크기 커밋먼트 중 선택하고, 컨트랙트를 쓰기 전에 프루프 크기 대 업데이트 비용 트레이드오프를 기록해둔다.
• Devnet: Verkle을 고려하기 전에 Verex의 실제 상태 키에 대한 실제 MPT 프루프 크기를 벤치마크한다. Anvil과 Sepolia는 이미 MPT를 쓰므로, Verex가 증명해야 할 구체적 키에 대해 분기 계수가 만드는 프루프 크기를 측정해 "언제 Verkle이 필요한가"를 추측이 아니라 숫자로 만든다.
• gitboard: 정산 프루프 바이트 크기를 대시보드 지표로 추적한다. 이 연습문제의 노드 수/바이트 크기 표가 만들어지면 그 실제 숫자를 gitboard에 유지해, 향후 라이트클라이언트 기능이 추측이 아니라 데이터로 범위가 정해지게 한다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.