Advanced Trie Structures TODO
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.
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/.