[이더리움 Stateless] 4. 버클트리(Verkle Trie) 구조 알아보기

Published in

Decipher Media ｜디사이퍼 미디어

20 min readFeb 14, 2023

서울대학교 블록체인 학회 디사이퍼(Decipher) After the merge 팀에서 이더리움의 로드맵 중 하나인 Stateless에 대한 글을 시리즈로 연재합니다. 본 글은 이더리움 Stateless 시리즈의 세번째 편으로 Stateless와 버클 트리에 대해 설명합니다.

Authors

황수진

Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)

Reviewd by 임요한

[이더리움 Stateless]

[목차]

버클 트리란?
버클 트리 구조
머클 트리 VS 버클 트리

버클 트리는(Verkle Trie)는 stateless 도입을 위한 핵심 변화 중 하나로, 이더리움 재단은 현재 state 저장에 사용되는 MPT(Merkle Patricia Trie)를 대체하기 위한 버클 트리 개발 및 연구를 이어오고 있습니다. 버클 트리 docs는 최근까지 업데이트가 이루어졌으며, 현재 버클 트리를 구현한 구현체는 (python, go, rust)에서 확인하실 수 있습니다. 버클 트리의 검증에 이어 이번 글에서는 버클 트리 구조를 중심으로 버클 트리에 대해 자세히 알아보도록 하겠습니다.

버클 트리(Verkle Trie) 란?

버클 트리는 Vector 와 merkle tree 가 합쳐진 것으로, 기존 머클 트리에서의 keccak256 해시 함수 대신 Vector Commitment를 사용하는 트리입니다. 버클 트리에서 사용하는 VC(Vector Commitment) 스킴은 Pedersen Commitment 로 (Pedersen Hash 라고도 함), polynomial commitment 에 기반합니다. Commitments 사용으로 proof 생성에 형제(sibling) 노드가 요구되지 않으며, 타원 곡선을 기반으로 하여 “연산”이 가능하기 때문에 트리 각 레벨에서 필요한 proof들을 더해(multiproof) proof의 크기를 감소시킬 수 있습니다. 상수 크기의 proof는 블록 헤더에 포함될 수 있고, 이는 weak statelessness를 가능하게 합니다.

버클 트리(Verkle Trie) 구조

2-layer structure(source: ethereum yellow paper, ethereum reddit)

이더리움은 World State Trie, Receipts Trie, Transaction Trie, Account Storage Trie로 총 4개의 트리를 갖습니다. 이때, State 트리의 leaf 노드는 계정(account) 별 데이터 none/balance/codeHash 와 storage 트리의 루트(StorageRoot) 를 갖습니다. 이를 트리가 트리를 갖고 있다고 하여 2-layer 구조 (Tree-inside-a-tree) 라고 합니다. 2-layer 구조는 다음과 같은 문제가 있습니다.

1. 복잡성
2. 불균형
3. 상태 만료와 같은 메커니즘 간의 상호 작용 파악의 어려움

트리가 트리를 가지고 있기 때문에 또 다른 처리를 요구하게 되고, 스토리지(storage)가 아닌 계정(account) 헤더 항목(ie. nonce/balance/code)에 접근하려고 할 때도 마찬가지로 데이터베이스 읽기/쓰기, Merkle proof 구성, Merkle proof 검증, 동기화, 캐싱 등 여러 곳에서 복잡한 처리가 필요해집니다. 또한, World State Trie 는 스토리지 root만을 갖고 있지만 사실 많은 양의 데이터를 의미하기 때문에 이러한 불균형은 state sync 프로토콜에서 상당히 귀찮은 요소입니다.

state trie와 storage trie (soure: cryptoauxiliary)

예를 들어, 기존 state 트리에서 계정 0x58…ae84 키로 할 때 해당 키에 매핑되는 데이터들은 nonce, balance, storageRoot, codeHash 가 됩니다. 여기서 storageRoot 는 실제 데이터가 아닌 루트 값만 가지고 있는 것이고, 스토리지(storage_slot) 에 접근 시에는 계정 0x58…ae84 와 스토리지 슬롯(storage slot) 을 키로 하여 스토리지 트리(Account Storage Trie)에 있는 값을 읽게 됩니다. 스토리지 트리가 업데이트되면 변경된 트리 내용에 따라 state 트리가 갖고 있던 storageRoot 값이 업데이트됩니다. 때문에 2-layer 구조는 account-level 과 storage-slot-level 조작을 위한 별도의 논리가 필요하며, Stateless 를 위해 도입하려는 state expiry 에서도 유사한 문제가 발생합니다. 이러한 비효율적인 문제로 비탈릭은 single-layer 구조를 제안했습니다.

single layer structure (source: ethereum reddit)

이는 단일 key:value 의 구조로 데이터는 state 내 모든 위치에서 32-byte 단일 키로 매핑됩니다. 즉, 같은 키 구조로 nonce, balance 뿐만 아니라 스토리지 슬롯까지 접근이 가능합니다.

eg. (address, storage_slot), (address, NONCE), (address, balance) ..

이에 따라 각 계정의 스토리지는 state 트리 내 하위 트리가 아닌 state 트리 내 다른 부분에 위치하게 되어 tree-inside-tree 구조가 사라집니다. single-layer 구조를 위해 키의 처음 31바이트를 공유하는 값은 동일한 bottom-layer commitment 에 포함됩니다. 이는 많은 헤더 필드, 코드 청크 또는 인접 스토리지 슬롯 검증을 위한 witness 공간을 절약할 수 있습니다. 버클 트리는 Tree Key 를 사용하여 이를 표현하였고 witness 공간을 절약하였습니다.

Tree Keys

Tree Key 의 구조 (source: ethereum foundation youtube)

버클 트리의 트리 키(Tree Key) 는 32 바이트로, 31 바이트의 stem 과 1 바이트의 suffix 로 이루어 집니다. suffix 를 통해 트리 키가 저장하는 state 정보(account header data, code, storage)를 구분할 수 있습니다.

tree key 생성 함수의 파라미터(source: verkle tree eip)

sufiix 값에 따른 해석 (source: verkle block sample)

위의 표 속 *_LEAF_KEY 는 트리 키의 suffix 를 뜻하며, *_OFFSET 은 자식 노드 32 바이트(256 bit) 내 위치를 나타냅니다. 예를 들어 트리 키에서 마지막 1 바이트가 00 이라면 계정 버전을, 01 이라면 계정의 잔고를, 02는 계정의 논스를 나타냅니다. 기존 state 트리가 가지고 있던 논스와 잔고는 suffix 01 , 02 를 가진 트리 키를 키로 하여 저장되고, 스토리지와 코드 해시는 위의 표 속 offset 값에 따라 저장되는 위치가 정해집니다.

def get_tree_key(address: Address32, tree_index: int, sub_index: int):
    # Asssumes VERKLE_NODE_WIDTH = 256
    return (
        pedersen_hash(address + tree_index.to_bytes(32, 'little'))[:31] +
        bytes([sub_index])
    )

위는 버클 트리 eip에 소개된 tree key 생성 함수 입니다.

def get_tree_key_for_version(address: Address32):
    return get_tree_key(address, 0, VERSION_LEAF_KEY)
    
def get_tree_key_for_balance(address: Address32):
    return get_tree_key(address, 0, BALANCE_LEAF_KEY)
    
def get_tree_key_for_nonce(address: Address32):
    return get_tree_key(address, 0, NONCE_LEAF_KEY)

# Backwards compatibility for EXTCODEHASH    
def get_tree_key_for_code_keccak(address: Address32):
    return get_tree_key(address, 0, CODE_KECCAK_LEAF_KEY)
    
# Backwards compatibility for EXTCODESIZE
def get_tree_key_for_code_size(address: Address32):
    return get_tree_key(address, 0, CODE_SIZE_LEAF_KEY)

논스와 잔고의 키는 *_LEAF_KEY 값을 suffix 로하여 생성하는 것을 볼 수 있습니다.

def get_tree_key_for_code_chunk(address: Address32, chunk_id: int):
    return get_tree_key(
        address,
        (CODE_OFFSET + chunk_id) // VERKLE_NODE_WIDTH,
        (CODE_OFFSET + chunk_id)  % VERKLE_NODE_WIDTH
    )

def get_tree_key_for_storage_slot(address: Address32, storage_key: int):
    if storage_key < (CODE_OFFSET - HEADER_STORAGE_OFFSET):
        pos = HEADER_STORAGE_OFFSET + storage_key
    else:
        pos = MAIN_STORAGE_OFFSET + storage_key
    return get_tree_key(
        address,
        pos // VERKLE_NODE_WIDTH,
        pos % VERKLE_NODE_WIDTH
    )

반면, 코드 해시와 스토리지는 offset 을 기반으로 생성되는 것을 볼 수 있습니다. 여기서 VERKLE_NODE_WIDTH 는 256 으로 트리의 자식 노드 크기를 가리킵니다. 기존 MPT의 경우 16 개의 자식 노드를 가졌지만 버클 트리는 256 개의 자식 노드를 가집니다.

몇 가지 tree key 를 예로 살펴보겠습니다.

위는 한 계정이 가지고 있는 트리 키들로, suffix 가 다른 것을 볼 수 있습니다. 각 트리 키들은 서로 다른 value 를 가지고 있으며, 저장된 value 는 suffix 가 의미하는 내용을 담고 있습니다. 트리 키 아래에 저장되는 데이터 역시 32 바이트로 표현됩니다.

예를 들어 위의 키가 0x71562b71999873DB5b286dF957af199Ec94617f7 주소의 트리 키들일 때, 해당 주소의 잔고는 0x274cde18dd9dbb04caf16ad5ee969c19fe6ca764d5688b5e1d419f4ac6cd1601 아래에 저장됩니다. 위의 주소의 경우 code-offset 을 의미하는 128~256(0x80~0xff) 내 suffix 를 갖는 tree key 가 없기 때문에 EOA(Externally Owned Account) 임 을 알 수 있습니다.

위의 트리 키들의 경우 0x80~0xff 내의 suffix를 갖는 것을 볼 수 있습니다. 따라서 위의 트리 키를 갖는 주소는 CA(Contract Account)임을 알 수 있습니다. 컨트랙트가 갖는 잔고와 코드 들은 suffix에 따라 트리 키 아래의 데이터 영역에 저장됩니다.

tree key 와 vekle tree (source: ethereum foundation youtube)

위의 사진과 같이 트리 키만 있으면 바로 leaf 노드(=suffix 노드)에 도달할 수 있음을 보여줍니다. 즉, 같은 stem의 트리 키를 갖는 데이터들은 모두 같은 leaf 노드로 모이게 되고, 그 데이터들은 suffix 아래의 하나의 commitment에 저장됩니다.

이는 leaf 노드에 하나의 데이터만 저장했던 기존 머클 패트리샤 트리와는 상반됨을 알 수 있습니다. 버클 트리에서 leaf 노드는 MPT의 leaf 노드 보다는 브랜치 노드에 더 가깝다고 할 수 있습니다.

Inner Node & Suffix Node(extension node)

버클 트리는 inner node 와 suffix node 두 가지로 이루어져 있습니다.

verkle tree structure (source: ethereum foundation blog)

점선으로 된 박스가 leaf 노드, 즉 suffix 노드입니다. Vector commitment 사용으로 기존 16 개였던 자식노드가 256 개로 확장된 것을 볼 수 있습니다.

Suffix Node

leaf 노드(= suffix 노드, 이해를 위해 leaf 노드로 표현)는 commitment 를 갖고 있으며, commitment 는 다음과 같은 구조로 이루어져있습니다.

1: suffix node marker 로, 타원 곡선 상의 1로 실제 1을 의미하지는 않습니다
Stem: stem 은 트리 키에서의 stem을 가리킵니다.
C1, C2: Pedersen Commiment 입니다.

(source: ethereum foundation blog)

최종적으로 네 가지 값을 commit 한 commitment 값이 leaf 노드의 commitment 로 들어갑니다. 그렇다면 데이터의 commitment 어떠한 형태로 포함되고 있을까요?

같은 stem 을 갖는 value 들은 하나의 leaf 노드로 모입니다. stem이 도달한 leaf 노드는 다른 suffix의 데이터들을 포함하게 되는데, 이때 00 ~ 7F suffix 를 갖는 데이터들의 Pedersen commitment C1, 80 ~ ff suffix 를 갖는 데이터의 Pedersen commitment C2 가 됩니다. 다시 말해 계정 버전, 잔고, 논스…. 코드 해시는 C1에 저장되고, 나머지 데이터는 C2에 저장됩니다. 이렇게 나누어서 저장하는 이유는 Pedersen Commitment 생성에 데이터가 최대 253 bit 크기의 256개 값을 commit 하는 것으로 제한되어 256 bit 값의 경우 데이터 손실이 발생하기 때문입니다.

tree key 아래에 32 바이트 데이터를 저장한다고 할 때 다음과 같은 과정을 거칩니다. (아래 내용은 버클 트리의 go 구현체를 바탕으로 작성되었습니다.)

suffix 에 따라 데이터들은 v0, v1.. v255 가 됩니다. suffix 가 20이라면 value 는 v32 에 위치합니다.
leaf 노드의 commitment 계산을 위해 C1 과 C2 를 계산합니다. 이때 v0~v127 는 C1 으로 v128~v255 는 C2 로 들어갑니다.
C1 에 포함되는 v0~v127 의 각 32 바이트 value를 상위 16 바이트(v1,0) 하위 16 바이트 (v1, 1) 로 나누어 다항식의 계수로 올립니다. 이를 통해128 개의 데이터로 256 차 다항식을 만들 수 있으며 각 계수의 데이터는 16 바이트(128-bit)가 됩니다. C2도 동일하게 구성됩니다.
만들어진 256 차 다항식을 commit 하여, C1 C1 = commit([(v0,0), (v0,1), (v1,0), (v1,1)...(v127,0),(v127,1)]) 과 C2 C2 = commit([(v128,0), (v128,1), (v129,0), (v129,1) ... (v255,0),(v255,1)]) 를 계산합니다. 이때 각 계수는 128 bit 의 256 개의 데이터이기 때문에 데이터 손실이 발생하지 않습니다.
C1과 C2, 1, stem 값을 commit 하여 C c = commit([1, stem, C1, C2])를 구합니다. 해당 C 는 leaf 노드의 commitment 가 됩니다.

때문에 각 노드의 comimtment 는 자식 노드를 포함하게 되며, 이는 머클 트리에서 해시의 역할과 같습니다.

Inner Node

inner node 는 트리 키의 stem 값을 담고 있으며, 하위 노드에 대한 256개의 포인터를 저장합니다. 쉽게 말하자면, root 에서 leaf 노드까지 도달하는 path 를 나타며, path 는 stem 을 기반으로 합니다. 이는 MPT 에서의 branch node 와 비슷합니다.

위의 그림에서 C0, C1 … C255 는 하위 노드의 commitment 로, inner 노드는commitment 를 포함합니다. 버클 트리에 tree key-value 삽입 시 일어나는 inner 노드의 변화를 통해 inner 노드 및 버클 트리 구조를 알아봅시다.

tree key: 0x00..20 [emtpy 삽입]

path “00” 를 갖는 노드가 없기 때문에 empty 에 삽입하여 루트 노드 “00” 밑에 바로 leaf 노드가 생성됩니다. 이때 suffix 는 20 이므로 value 는 leaf 노드의 C1 에 포함됩니다.

2. tree key: 0xdefe…64 [emtpy 삽입]

3번 tree key 가 삽입 되기 전으로, 1번 경우와 같이 “de” 는 empty 상태이기 때문에 루트 노드 “de” 에 leaf 노드가 생성됩니다.

3. tree key: 0xde03a8..02 [leaf 노드 삽입]

3번 삽입 시, “de” 에 leaf 노드가 위치한 상태입니다. 이 경우 기존 leaf 노드의 tree key 와 다른 path 가 나타날 때 까지 새 inner node 를 삽입합니다. 이때 삽입된 inner 노드는 하위 노드의 포인터를 갖습니다. 이에 기존에 있던 2번 노드는 “fe” 에 저장되고, 3번 노드는 “03” 에 저장됩니다.

4. tree key: 0xde03a8..02 [inner node 삽입]

마찬가지로 4번 삽입 시, 3번에서의 새 inner 노드 삽입으로 “de” 에 inner 노드가 위치한 상태입니다. 이 경우 삽입 위치가 하위 노드로(3번에서 새로 삽입한 inner node) 내려가고 path 가 “03” 이 됩니다. “03” 에는 leaf 노드가 위치하기 때문에 3번에서 설명한 설명했던 대로 다른 path 가 나올 때까지 inner 노드를 삽입합니다. 1,2,3,4 번 tree key-value 를 삽입한 버클 트리는 최종적으로 위와 같은 구조를 갖게 됩니다.

tree key 삽입 과정을 통해 inner 노드의 역할과 버클 트리의 구조, leaf 노드의 형태를 알아보았습니다. 버클 트리에 예시 값들을 넣어보면 다음과 같습니다.

버클트리 구조 (source: verkle block sample, 사진을 누르면 크게 확인하실 수 있습니다)

그림 속 I 는 Inner node, L 은 Leaf node, C 는 Commitment 를 의미합니다. 정리하자면, 다음과 같습니다.

버클 트리는 leaf 노드 와 inner 노드 두 가지로 구성됩니다.
tree key 는 stem 과 suffix 를 담고 있습니다.
같은 stem 은 같은 leaf 노드를 갖습니다.
데이터는 tree key 의 suffix 로 구분되어 저장됩니다.
tree key 가 root 로 부터 leaf 노드까지의 경로에 1바이트 씩 인코딩됩니다.
데이터는 leaf 노드의 commitment 에 포함되어 있습니다.

머클 트리(MPT) VS 버클 트리(Verkle Trie)

설명에 앞서, 본 글은 버클 트리에 초점을 두고 있으므로 머클 트리에 대한 자세한 내용은 넘어가도록 하겠습니다. (이더리움 머클 트리의 구조 및 검증 방식은 이전 글을 참고)

유사점

데이터 요소가 key-value 쌍으로 저장되어 있다.
키가 root 로부터 해당 값(value)을 가진 노드까지의 경로에 1바이트 씩 인코딩됩니다.
각 노드에는 하위 노드의 값(value)와 위치(position)를 commit 하는 암호학적 commitment 가 있습니다.
노드 위치(position) 및 암호학적 commitment 는 데이터 내용에만 의존하며, 데이터가 생성되고 업데이트된 순서에는 의존하지 않습니다.

머클 트리의 구조를 알고 있고, 위에서 설명했던 버클 트리의 tree key, inner node, leaf node 를 이해하셨다면 두 트리 구조의 유사점은 쉽게 파악이 되실거라 생각합니다.

차이점

머클 트리는 중첩된 트리 구조(trie-inside-trie)를 갖지만, 버클 트리는 single flat trie 구조를 갖습니다.
머클 트리에서의 keccak256 해시 함수 대신, 버클 트리에서는 Pedersen commitment 를 사용하여 암호학적 commitment 를 생성합니다.
머클 트리에서는 20바이트 키를 사용하지만, 버클 트리에서는 32바이트 키를 사용합니다.
머틀 트리는 16 개의 하위 노드를 갖지만, 버클 트리는 256 개의 하위 노드를 갖습니다.

Pedersen commitment 는 다항식 기반으로 특정 위치(position)에서의 evaluation 을 이용하여 proof 및 commitment 를 생성하기 때문에 sibling 노드를 요구하지 않고 특정 값에서 고유하게 주어지게 됩니다(자세한 내용은 ipa 에서 확인). 이 때문에 트리의 width 가 넓어져도 상수 크기의 proof 사이즈를 유지할 수 있으며, 이더리움이 stateless-client 로 변경에 있어 주요 문제였던 witness 크기 문제를 해결할 수 있습니다.

Reference