Merkle vs Verkle
무상태 클라이언트의 가능 여부를 가르는 건 해싱 속도가 아니라 증명 크기라는 것.
참조 — docs/knowledge/merkle-vs-verkle.html.
기술 노트
각 항목이 실제로 무엇을 보여주고 어떻게 동작하는지 — 위 카드보다 자세한 기술 설명입니다.
목적: 이 카탈로그가 애플리케이션 쪽에서 계속 부딪히는 상태 팽창 문제를, 프로토콜 쪽에서 본 것입니다. 스토리지 슬롯을 쓰는 여기 모든 카드 — 강제기의 지출 카운터, 토큰 잔고 — 가 모든 노드가 영구히 살려 두는 상태에 더해집니다. Verkle 트리는 그걸 지우지 않습니다. 노드가 그중 한 조각을 *증명*하기 위해 들고 다녀야 하는 양을 바꿀 뿐이고, 그게 "상태가 너무 크다"와 "상태가 너무 커서 동기화가 안 된다" 사이의 차이입니다.
동작 방식: 데모가 아니라 정독 노트입니다: 머클 증명의 크기가 트리 폭에 따라 어떻게 늘어나는지(각 레벨의 형제 노드를 전부 제출해야 한다), 벡터 커밋먼트가 어떻게 폭과 무관한 상수 크기 증명으로 그것을 접는지, 그리고 이더리움 Verge 로드맵이 그 교체로 사려는 것 — 상태를 들고 있지 않고도 검증하는 무상태 클라이언트. 대가도 함께: 더 무거운 암호학, 그리고 상태 트라이 전체의 마이그레이션.
검토 후 보완: ### 증명 크기지, 증명 시간이 아니다 검토 중 계속 돌아온 구분입니다. Verkle 트리는 증명의 **크기**(전송할 바이트)를 줄이지, 증명·검증 **시간**을 줄이는 게 아닙니다. 암호학은 연산당 오히려 *더 무겁습니다* — 단순 SHA-256 해싱이 아니라 타원곡선 위의 벡터 커밋먼트라서, 전체 계산량은 줄지 않고 **늘어납니다**. 카드 부제를 문자 그대로 옮긴 것입니다: 병목은 애초에 해싱이 아니라 **대역폭**이었습니다. ### 폭과 무관하게, 레벨당 오프닝 하나 머클: 각 레벨에서 그룹의 *나머지* 자식을 전부 제출해야 합니다 — `branching − 1`개 형제, 폭에 따라 증가. Verkle: 벡터 커밋먼트가 각 레벨을 폭과 무관한 **상수 크기 오프닝 하나**로 접습니다. 그래서 전체 증명 ≈ (레벨당 상수) × (레벨 수). Related code에서 64개 중 리프 #5를 증명한 수치: | branching | depth | 머클 오프닝 | Verkle 오프닝 | |---|---|---|---| | 2 | 6 | 6 | 6 | | 16 | 2 | 30 | 2 | | 256 | 1 | 255 | 1 | ### Verkle이 일부러 넓게 가는 이유 폭이 **증명 크기 면에서 공짜**이기 때문에, Verkle 설계자는 노드를 넓게 만듭니다 — 이더리움 설계는 **256분기** — 그러면 트리가 **얕아져서** 증명이 두 가지로 동시에 작아집니다: 레벨당 상수 *그리고* 더 적은 레벨. 머클은 이걸 못 합니다: 자식 하나가 늘 때마다 **모든** 증명에 형제가 하나씩 더 붙으므로, 실제 머클 트리는 **이진**을 유지합니다. ### 비용은 사라진 게 아니라 옮겨갔다 Verkle은 값싼 해시 형제 여럿을 **더 적고 크고 암호적으로 무거운** 오프닝과 맞바꿉니다. 크기 **↓**, 암호 계산 **↑**. 이 맞바꿈이 **무상태 클라이언트**를 사옵니다 — 노드가 상태 전체를 들고 있지 *않고도* 블록을 검증합니다. 매 블록 실어 보내는 witness가 드디어 네트워크로 나를 만큼 작아졌기 때문입니다. ### Related code가 하는 일, 그리고 하지 않는 일 머클 절반은 진짜입니다(SHA-256, 형제 계수). Verkle 절반은 그것을 그대로 대응시키되 **증명 *크기*만 모델링**합니다: 커밋먼트가 여전히 해시라 라이브러리 없이 돌아가고, 암호적으로는 **안전하지 않습니다**. 실제 Verkle은 O(1) 오프닝 하나가 임의 위치의 자식을 실제로 *증명*하려면 **IPA/KZG** 벡터 커밋먼트(타원곡선 연산)가 필요합니다.
"""Merkle vs Verkle PoC -- proof size grows with tree width, not with hashing speed.
Illustrates the core mechanism: a Merkle proof needs one sibling hash per level, so
wider trees (more children per node) need more siblings per level to prove membership.
The Verkle half mirrors the Merkle half line-for-line -- same tree, same leaf. The ONLY
thing that changes is how many openings a proof carries per level:
Merkle: (children in the group - 1) siblings per level -> grows with width
Verkle: exactly ONE opening per level -> constant, any width
NOTE: a production Verkle uses an IPA/KZG *vector commitment* (elliptic-curve math) so
that one O(1) opening proves a child at any position. The Verkle commitment below is
still a hash, so the file runs with no libraries -- it only MODELS the proof-*size*
property, and is NOT cryptographically sound. The point is size, not crypto.
"""
import hashlib
def h(*parts: str) -> str:
return hashlib.sha256("|".join(parts).encode()).hexdigest()[:12]
# ── Merkle ────────────────────────────────────────────────────────────────────
def build_tree(leaves: list[str], branching: int) -> list[list[str]]:
"""Builds a Merkle tree with `branching` children per node; returns levels bottom-up."""
levels = [leaves]
while len(levels[-1]) > 1:
cur = levels[-1]
nxt = []
for i in range(0, len(cur), branching):
group = cur[i:i + branching]
nxt.append(h(*group))
levels.append(nxt)
return levels
def proof_size(levels: list[list[str]], leaf_index: int, branching: int) -> int:
"""Count sibling hashes needed to prove one leaf's membership -- (branching - 1) per level."""
siblings = 0
idx = leaf_index
for level in levels[:-1]:
siblings += branching - 1 # every level, you must supply all other children in the group
idx //= branching
return siblings
# ── Verkle (same tree shape; only the proof model differs) ──────────────────────
def verkle_build_tree(leaves: list[str], branching: int) -> list[list[str]]:
"""Same shape as build_tree; commit stands in for a vector commitment over the children."""
levels = [leaves]
while len(levels[-1]) > 1:
cur = levels[-1]
nxt = []
for i in range(0, len(cur), branching):
group = cur[i:i + branching]
nxt.append(h("vc", *group)) # a real Verkle uses an IPA/KZG commitment here
levels.append(nxt)
return levels
def verkle_proof_size(levels: list[list[str]], leaf_index: int, branching: int) -> int:
"""ONE constant-size opening per level, regardless of width -- what a vector commitment buys."""
return len(levels) - 1
if __name__ == "__main__":
leaves = [f"leaf{i}" for i in range(64)]
# bytes per opening: a 32B sibling hash (Merkle) vs one 48B EC opening (Verkle, BLS12-381 G1)
MB, VB = 32, 48
print(f"{'branch':>6}{'depth':>7}{'merkle_open':>13}{'verkle_open':>13}{'merkle_B':>10}{'verkle_B':>10}")
for branching in (2, 4, 8, 16):
mt = build_tree(leaves, branching)
vt = verkle_build_tree(leaves, branching)
mo = proof_size(mt, leaf_index=5, branching=branching)
vo = verkle_proof_size(vt, leaf_index=5, branching=branching)
print(f"{branching:>6}{len(mt) - 1:>7}{mo:>13}{vo:>13}{mo * MB:>10}{vo * VB:>10}")
# why Verkle deliberately picks a WIDE node (Ethereum's design is 256-ary):
# width is free for proof SIZE, so go wide -> shallow tree -> tiny proof.
print("\n--- wide node: free for Verkle, ruinous for Merkle ---")
for branching in (2, 16, 256):
mt = build_tree(leaves, branching)
vt = verkle_build_tree(leaves, branching)
print(f"branch={branching:>3} depth={len(mt) - 1} "
f"merkle openings={proof_size(mt, 5, branching):>3} "
f"verkle openings={verkle_proof_size(vt, 5, branching)}")
print("\nMerkle: wider = bigger proof (siblings pile up), so real trees stay binary.")
print("Verkle: a vector commitment collapses each level's siblings to a constant-size")
print("opening regardless of width -- so go wide, shallow, tiny. The cost did not vanish;")
print("it moved into heavier cryptography (per opening), not into more bytes. That")
print("constant-size property is what makes stateless clients (validate without holding")
print("the whole state) practical.")