Copy English

Why

The state-bloat problem this catalogue keeps running into from the application side, looked at from the protocol side. Every card here that writes a storage slot — an enforcer's spent counter, a token balance — adds to state that every node keeps live forever. Verkle trees do not delete any of it; they change what a node must carry to prove a piece of it, which is the difference between "state is too big" and "state is too big to sync".

How it works

Reading note, not a demo: how a Merkle proof's size grows with tree width (you must supply every sibling at every level), why vector commitments collapse that to a constant-size proof regardless of width, and what Ethereum's Verge roadmap intends to buy with the swap — stateless clients that validate without holding the state. Also what it costs: heavier cryptography, and a migration of the entire state trie.

Review clarification

Proof size, not proof time

This is the distinction the review kept returning to. A Verkle tree shrinks the proof's size (bytes to transmit), not the time to prove or verify. Its cryptography is heavier per operation — vector commitments over elliptic curves instead of plain SHA-256 hashing — so end-to-end compute goes up, not down. That is the card's subtitle made literal: hashing was never the bottleneck, bandwidth was.

One opening per level, regardless of width

Merkle: at each level you must supply every other child in the group — branching − 1 siblings, which grows with width. Verkle: a vector commitment collapses each level to one constant-size opening, whatever the width. So total proof ≈ (constant per level) × (number of levels). Numbers from the Related code, proving leaf #5 of 64:

Why Verkle deliberately goes wide

Because width is free for proof size, Verkle designers make nodes wide — Ethereum's design is 256-ary — which makes the tree shallow, so the proof is tiny on two counts at once: constant per level and fewer levels. Merkle cannot do this: every extra child costs one more sibling in every proof, which is why real Merkle trees stay binary.

The cost moved; it did not vanish

Verkle trades many cheap hash siblings for fewer, bigger, cryptographically heavier openings. Size down, crypto compute up. That trade is what buys stateless clients — a node validates a block without holding the whole state, because the witness it ships each block is finally small enough to move around the network.

What the Related code does — and does not

The Merkle half is real (SHA-256, counts siblings). The Verkle half mirrors it line-for-line but models proof size only: its commitment is still a hash, so the file runs with no libraries and is not cryptographically sound. A production Verkle needs an IPA/KZG vector commitment (elliptic-curve math) to make one O(1) opening actually prove a child at any position.

Related code

"""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.")

docs/code/pocs/merkle-vs-verkle.py

← All Dev Notes · Workspace Index · Top ↑

Copy 한국어

Merkle vs Verkle

무상태 클라이언트의 가능 여부를 가르는 건 해싱 속도가 아니라 증명 크기라는 것.

참조 — docs/knowledge/merkle-vs-verkle.html.

왜

이 카탈로그가 애플리케이션 쪽에서 계속 부딪히는 상태 팽창 문제를, 프로토콜 쪽에서 본 것입니다. 스토리지 슬롯을 쓰는 여기 모든 카드 — 강제기의 지출 카운터, 토큰 잔고 — 가 모든 노드가 영구히 살려 두는 상태에 더해집니다. Verkle 트리는 그걸 지우지 않습니다. 노드가 그중 한 조각을 증명하기 위해 들고 다녀야 하는 양을 바꿀 뿐이고, 그게 "상태가 너무 크다"와 "상태가 너무 커서 동기화가 안 된다" 사이의 차이입니다.

동작 방식

데모가 아니라 정독 노트입니다: 머클 증명의 크기가 트리 폭에 따라 어떻게 늘어나는지(각 레벨의 형제 노드를 전부 제출해야 한다), 벡터 커밋먼트가 어떻게 폭과 무관한 상수 크기 증명으로 그것을 접는지, 그리고 이더리움 Verge 로드맵이 그 교체로 사려는 것 — 상태를 들고 있지 않고도 검증하는 무상태 클라이언트. 대가도 함께: 더 무거운 암호학, 그리고 상태 트라이 전체의 마이그레이션.

검토 후 보완

증명 크기지, 증명 시간이 아니다

검토 중 계속 돌아온 구분입니다. Verkle 트리는 증명의 크기(전송할 바이트)를 줄이지, 증명·검증 시간을 줄이는 게 아닙니다. 암호학은 연산당 오히려 더 무겁습니다 — 단순 SHA-256 해싱이 아니라 타원곡선 위의 벡터 커밋먼트라서, 전체 계산량은 줄지 않고 늘어납니다. 카드 부제를 문자 그대로 옮긴 것입니다: 병목은 애초에 해싱이 아니라 대역폭이었습니다.

폭과 무관하게, 레벨당 오프닝 하나

머클: 각 레벨에서 그룹의 나머지 자식을 전부 제출해야 합니다 — branching − 1개 형제, 폭에 따라 증가. Verkle: 벡터 커밋먼트가 각 레벨을 폭과 무관한 상수 크기 오프닝 하나로 접습니다. 그래서 전체 증명 ≈ (레벨당 상수) × (레벨 수). Related code에서 64개 중 리프 #5를 증명한 수치:

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.")

docs/code/pocs/merkle-vs-verkle.py

← 전체 개발 노트 · 워크스페이스 인덱스 · 맨 위 ↑