EIP-3102 이진 트라이 구조 (Binary trie structure)

콜 결정 없음 · 확장성·데이터 · 원문 상태 Stagnant · 2020-09-01 작성

계정 트라이와 스토리지 트라이를 하나로 합치고, 16진 구조를 이진 구조로 바꾸고 해시 함수를 blake2b로 교체해 증명 크기를 줄이는 제안입니다.

왜 필요한가

지금 이더리움 상태 저장 구조는 머클 패트리샤 트라이(MPT)라는 16진 트리입니다. 16진 트리는 깊이가 얕아 해시 계산 횟수가 적다는 장점이 있지만, 실제 운영에서는 해싱보다 디스크 접근이 더 큰 병목으로 드러났습니다. 이 때문에 클라이언트들은 모든 내부 노드를 디스크에 저장하는 대신, 값만 평면적으로 저장하고 내부 노드는 필요할 때 다시 계산하는 방식으로 옮겨가고 있습니다. 또한 블록을 다운로드하지 않고도 상태를 증명으로 확인하는 스테이트리스 방식을 쓰기 쉽게 만들려는 요구가 있는데, 이진 트리는 16진 트리보다 증명 크기가 약 4배 작아 이 목적에 유리합니다. 여기에 더해 MPT는 RLP 인코딩과 작은 노드를 부모에 끼워 넣는 최적화 등 복잡한 장치가 많아 버그가 날 위험이 크고, 그 최적화로 아끼는 디스크 용량도 1MB 정도로 풀싱크에 필요한 300GB에 비하면 미미합니다.

무엇이 바뀌나

지금

EIP-3102 이후

누구에게 영향이 있나

심층 설명

트라이 구조와 노드

트라이는 노드 N=(N_l, N_r, N_p, N_v)로 구성됩니다. N_l과 N_r은 각각 왼쪽, 오른쪽 자식의 해시이고 자식이 없으면 empty_hash(빈 문자열의 해시)를 넣습니다. N_p는 선택적인 접두사(prefix)로, 이 노드 아래 모든 키가 공통으로 가지는 비트열입니다. N_v는 값이며 리프 노드에만 존재합니다. 양쪽 자식이 모두 empty_hash인 노드가 리프, 나머지가 내부 노드입니다. 기존 MPT에 있던 '리프 마커' 비트는 자식이 없는 노드를 리프로 보는 방식으로 대체되어 사라집니다.

계정 필드와 키 구조

계정 A=(A_b, A_n, A_c, A_s)의 각 필드는 hash(A_a)의 앞 254비트(hash(A_a)[0..253])에 2비트를 붙여 키를 만듭니다. 잔액 A_b는 ...++0b00, 논스 A_n은 ...++0b01, 코드 A_c는 ...++0b10, 스토리지 루트 A_s는 ...++0b11입니다. 스토리지 슬롯 k는 ...++0b11++hash(k)로 찾습니다. EIP-2926이 적용되면 A_c는 코드를 조각(chunk)으로 쪼갠 머클 트리의 루트가 되고, 코드 조각 c는 ...++0b10++u256(c)로 접근합니다. 계정 단계에서 항목이 더 필요해지면 세 번째 비트를 예비로 쓸 수 있다고 적혀 있습니다.

머클화(해시) 규칙

접두사가 없는 노드는 internal_hash = hash(left_child_hash || right_child_hash), leaf_hash = hash(hash(key) || hash(leaf_value))로 해시합니다. 접두사가 있는 노드는 루트부터 그 노드까지 경로 길이(path_length)를 u256으로 바꿔 앞에 붙이고 다시 한 번 해시합니다: internal_hash_with_prefix = hash(u256(path_length-1) || internal_hash), leaf_hash_with_prefix도 같은 방식입니다. 리프의 값은 코드처럼 32바이트를 넘는 경우를 대비해 항상 hash(value) 형태로 넣습니다.

해시 함수로 blake2b를 고른 이유

이진 트리는 16진 트리보다 노드 수가 약 4배 늘어 해싱 횟수도 그만큼 늘어납니다. 이 성능 손실을 보완하려고 keccak256 대신 더 빠른 blake2b를 선택했습니다. BLAKE3가 더 빠르지만, 문서 작성 시점에 공식 golang 구현이 없어 보안 위험으로 보고 blake2b를 대신 채택했습니다.

16진 대신 이진 트리를 고른 이유

N개 리프, 자식 k개짜리 트리의 평균 증명(브랜치) 길이는 대략 32*(k-1)*log(N)/log(k) 바이트이고, 이 식은 k=2일 때 최소가 됩니다. N=2^24 기준으로 비교하면 k=2일 때 768바이트, k=4일 때 1152바이트, k=8일 때 1792바이트, k=16일 때 2880바이트입니다. 원래 16진 구조를 쓴 이유는 디스크 읽기 횟수를 줄이려는 것이었지만, 이진 트리라도 데이터베이스 계층에서는 16진처럼 '흉내' 내어 저장할 수 있다는 점이 밝혀져 그 이유가 더 이상 유효하지 않다고 설명합니다. 또한 Eth2(합의 레이어)에서도 이진 트리를 널리 쓸 예정이어서 호환성 측면에서도 유리하다고 덧붙입니다.

접두사 비트열 대신 경로 길이를 쓰는 이유

바이트 조작의 복잡함을 줄이려고, 접두사 노드를 해시할 때는 접두사 비트열 자체가 아니라 루트부터 그 노드까지의 비트 길이(path length)만 사용합니다. 접두사 길이 대신 루트 기준 경로 길이를 쓰면, 리프를 하나 지웠을 때 형제 노드를 다시 해시하지 않아도 되는 장점이 있다고 설명합니다.

계정과 스토리지 트라이 병합

클라이언트들이 키·값을 '평면(flat)' 데이터베이스에 저장하는 추세이기 때문에, 스토리지 슬롯 키 앞에 그 계정의 주소 해시를 붙여 한 계정의 모든 데이터가 디스크에서 모이게 하고, 증명 구조도 단순해지도록 account 트라이와 storage 트라이를 하나로 합쳤습니다.

전환 위험과 현재 상태

본문은 이 구조로 넘어가려면 하드포크가 필요하다고 명시하고, 전환 과정에서 모든 상태를 새 구조로 바꾸는 작업이 무거워 일부 클라이언트가 전환을 미루려는 동기가 생길 수 있고 이것이 전환 시점에 네트워크 보안을 낮출 수 있다고 적습니다. 이를 위한 전환 절차로 EIP-2584가 제안되었다고 언급합니다. 이 EIP의 상태는 Stagnant(정체)로, 현재 활발히 진행되고 있지 않습니다.

EIP 원문 · ← EIPs