EIP-8297 구역 분할 이진 상태 트리 (Partitioned Binary Tree)

콜 결정 없음 · 확장성·데이터 · 원문 상태 Draft · 2026-06-11 작성

이더리움 상태 저장 구조를 16진 머클 패트리샤 트라이에서 이진 트리 하나로 교체합니다. 키의 첫 바이트가 계정 헤더·코드·스토리지 구역을 구분하고 컨트랙트 코드도 청크로 나뉘어 트리에 들어갑니다.

왜 필요한가

이더리움의 장기 목표는 블록을 유효성 증명(validity proof)으로 검증해 체인 검증을 최대한 가볍고 빠르게 만드는 것입니다. 그러려면 EVM 실행 중 읽은 상태를 증명해야 하는데, 지금의 머클 패트리샤 트라이(MPT)는 여기에 맞지 않습니다. RLP 인코딩과 증명하기 비싼 Keccak 해시를 쓰고 계정 트리 아래에 스토리지 트리가 따로 달린 '트리 속 트리' 구조이며 코드의 일부만 골라 증명할 수도 없습니다. 증명 크기도 큽니다. 계정 트리 깊이가 약 12일 때 가지 하나가 5760바이트이고 최악의 경우 블록 가스 6000만을 서로 다른 계정 코드를 1바이트씩 건드리는 데 다 쓰면 약 1.8GB가 필요합니다. 코드가 청크로 나뉘어 있지 않으면 1바이트를 증명하는 데도 64KiB 코드 전체를 공개해야 하기 때문입니다. 분기 수가 2인 이진 트리는 머클 증명 크기를 최소로 줄이고 증명 친화적인 해시로 바꾸면 회로 성능도 좋아집니다.

무엇이 바뀌나

지금

EIP-8297 이후

누구에게 영향이 있나

심층 설명

트리 구조: 두 종류의 노드와 유일한 정규형

트리는 키가 1바이트 이상 MAX_KEY_LENGTH(8192바이트) 이하의 가변 길이 바이트열이고 값이 32바이트인 항목을 저장합니다. 어떤 키도 다른 키의 접두사가 될 수 없습니다(prefix-free). 노드는 두 종류뿐입니다. LeafNode는 완전한 key와 value를 갖고 BranchNode는 prefix(비트열), left, right를 갖습니다. 별도의 확장 노드는 없고 BranchNode의 prefix가 그 아래 모든 키가 공유하는 비트 구간을 담습니다. BranchNode는 반드시 비어 있지 않은 자식 둘을 가져야 하므로 prefix는 정확히 공유 구간이 되고 키/값 집합마다 유효한 트리가 정확히 하나 존재합니다. LeafNode는 트리 내 위치에 상대적인 접미사가 아니라 완전한 키를 커밋하므로, 다른 곳에서 분기가 쪼개지거나 합쳐져도 무관한 리프의 해시는 변하지 않습니다.

머클화 규칙과 미확정 해시 함수

리프는 H(LEAF_TAG || key || value), 브랜치는 H(BRANCH_TAG || encode_bit_prefix(prefix) || left_hash || right_hash)로 해시합니다. LEAF_TAG는 0x00, BRANCH_TAG는 0x01, 빈 트리의 해시는 32바이트 0입니다. encode_bit_prefix는 비트 수를 2바이트 빅엔디언으로 적은 뒤 비트를 바이트 경계까지 0으로 채워 붙이며, 이 2바이트 한계(65535비트)에서 MAX_KEY_LENGTH = 8192바이트가 나옵니다. 해시 함수는 아직 확정되지 않았습니다. 참조 구현은 BLAKE3를 쓰고 후보는 BLAKE3(네이티브 성능 좋음), Keccak(이미 이더리움에서 사용, 증명 효율 낮음), Poseidon2(회로 내 성능 강함, EF 암호 이니셔티브가 보안 분석 진행 중)입니다. 트리가 해시 함수에만 의존하고 타원곡선을 쓰지 않아 양자 공격에도 안전합니다. Verkle의 곡선 기반 설계는 그렇지 않으며 NIST 지침은 2030년까지 타원곡선 암호 퇴출을 요구합니다.

구역과 키 임베딩

모든 키의 첫 바이트는 구역 식별자 Z입니다. 0x00은 계정 헤더, 0x01은 코드 청크, 0xFF는 스토리지이고 0x02~0xFE는 미래 범주용으로 예약됩니다. 키는 구역 바이트, 해시로 정해지는 트리 위치, 서브 인덱스 1바이트로 조립되며 구역 바이트와 트리 위치를 합쳐 스템(stem)이라고 부릅니다. 한 스템은 STEM_SUBTREE_WIDTH = 256개의 서브 인덱스를 가집니다. 키 길이는 구역마다 고정으로, ACCOUNT_KEY_LENGTH와 CODE_KEY_LENGTH는 34바이트, STORAGE_KEY_LENGTH는 66바이트입니다. 구역 안에서 길이를 하나로 고정하는 것이 prefix-free를 보장하고 구역이 다른 키는 첫 바이트부터 다릅니다. 주소는 20바이트 앞에 0 12바이트를 붙인 Address32로 전달합니다.

계정 헤더와 위임 리프

계정 헤더 스템은 ACCOUNT_ZONE에 key_hash(address)로 자리 잡아 계정마다 하나입니다. BASIC_DATA_LEAF_KEY(0) 리프 하나에 version(오프셋 0, 1바이트), code_size(4, 4바이트), nonce(8, 8바이트), balance(16, 16바이트)를 빅엔디언으로 묶어, 서너 번 열어야 할 가지를 한 번으로 줄입니다. CODE_HASH_LEAF_KEY(1)에는 Keccak 코드 해시가 들어가고 코드 없는 계정은 빈 바이트코드의 Keccak 해시를 가집니다. EIP-7702 위임 계정은 DELEGATION_LEAF_KEY(2)에 23바이트 지시자 0xef0100 || target 뒤에 0 9바이트를 붙여 저장하고 code_size는 23입니다. 위임 계정은 code_hash 리프와 CODE_ZONE 리프를 갖지 않으며 존재하는 계정은 code_hash와 delegation 리프 중 정확히 하나만 가집니다. 스토리지 슬롯 0~63도 헤더 스템의 서브 인덱스 64 이후에 함께 들어갑니다.

코드 청킹과 콘텐츠 주소화

코드는 31바이트 조각으로 나뉘어 CODE_ZONE에 들어갑니다. 각 청크의 바이트 0은 앞쪽 몇 바이트가 PUSHDATA인지 기록하고 바이트 1~31이 코드 조각입니다. 키는 key_hash(code_hash || tree_index)로 만들어 계정이 아니라 코드 해시로 주소화되므로, 같은 팩토리에서 배포된 수천 개 컨트랙트가 코드 리프를 공유하고 블록 증인에도 공유 청크는 한 번만 들어갑니다. 계정을 지울 때 코드 리프는 같은 code_hash를 가진 계정이 결과 상태에 하나도 없을 때만 제거합니다. 이 판정은 트랜잭션만 보고 가능합니다. 코드가 있는 계정은 자신을 만든 트랜잭션 안의 SELFDESTRUCT로만 지워지므로(EIP-6780), 트랜잭션 이전부터 있던 코드 리프는 항상 남고 트랜잭션이 새로 넣은 리프만 그 트랜잭션 안에서 결정됩니다. 상태 전체의 참조 카운트는 필요 없습니다.

스토리지 배치와 버킷

슬롯 64 이상은 스토리지 구역으로 갑니다. 키는 0xFF || key_hash(address) || key_hash(address || tree_index) || sub_index이고 tree_index = slot // 256, sub_index = slot % 256입니다. 첫 해시 key_hash(address)가 한 계정의 오버플로 스토리지 전체를 하나의 버킷 아래 모으고 두 번째 해시가 버킷 안에서 그룹을 고르게 흩뿌립니다. 두 번째 해시에 주소를 함께 넣는 것은 그라인딩 공격을 공격자 자신의 버킷으로 제한하기 위해서입니다. 인접 슬롯은 같은 그룹에 들어가므로 매핑과 배열처럼 붙어 있는 슬롯 접근이 경로를 공유합니다. 그룹 0은 예외로, 슬롯 0~63이 헤더에 있으므로 스토리지 구역에는 슬롯 64~255만 있습니다. 버킷은 이후 상태 만료나 부분 상태 보유 설계가 잘라 내거나 동기화하는 단위가 됩니다.

0값은 삭제, 삭제는 정규형 복원

상태 전이 함수는 32바이트 0을 쓰는 것을 삭제로 처리해야 합니다. 트리에는 0값을 가진 키가 없고 없는 키를 읽으면 0이 나오므로, 0과 '없음'은 같은 상태이고 같은 루트를 만듭니다. 루트가 쓰기 이력이 아니라 상태만의 함수가 되어, MPT에서 변환한 트리와 증분으로 유지한 트리가 일치합니다. 삭제로 자식이 하나만 남은 브랜치는 그 자식으로 대체해 정규형을 복원해야 하며 이 병합은 한 단계로 끝나고 삽입이 수행한 분할을 되돌립니다. MPT는 storage_root로 EIP-7610 조건(컨트랙트 생성 전에 비어 있지 않은 스토리지 확인)을 검사했지만 이 트리에는 그런 노드가 없으므로 헤더의 스토리지 서브 인덱스나 스토리지 버킷 어딘가에 리프가 있는지로 판정합니다.

보안, 상태, 그리고 일정

키의 해시 성분은 모두 256비트 전체 다이제스트라 충돌을 만들려면 약 2^128의 생일 공격 비용이 들고 구역이 다른 키는 첫 바이트부터 달라 아예 충돌할 수 없습니다. 그라인딩으로 선행 비트 k개가 같은 다이제스트를 모아도 접두사 압축이 그 구간을 BranchNode prefix 약 k/8바이트로 접기 때문에, 실제 노드를 d개 늘리려면 약 2^d의 작업이 필요합니다. 이 EIP는 가스 스케줄을 바꾸지 않고 EVM에는 보이지 않지만 컨트랙트 안에서 MPT 상태 증명을 검증하던 코드는 새 증명 형식으로 바꿔야 합니다. 활성화와 기존 MPT 상태의 이전은 EIP-8347이 별도로 정하며 변환은 합의와 무관한 경로에서 일어나 단일 하드포크에서 새 트리가 정식 상태 커밋이 됩니다. 원문 상태는 Draft라 내용이 바뀔 수 있고 해시 함수도 미정입니다. 콜 기록으로는 09.16 AMA #15에서 논의됐고 결정은 없었습니다.

EIP 원문 · ← EIPs