EIP-7864 통합 바이너리 상태 트리 (Ethereum state using a unified binary tree)
콜 결정 없음 · 확장성·데이터 · 원문 상태 Draft · 2025-01-20 작성
계정 정보, 컨트랙트 코드, 스토리지를 하나의 바이너리(이진) 트리에 담는 새 상태 트리를 도입합니다. 기존 16진 머클 패트리샤 트라이를 대체해 증명을 작고 만들기 쉽게 하는 것이 목표입니다.
왜 필요한가
이더리움의 장기 목표는 블록이 올바르게 실행됐다는 사실을 유효성 증명(validity proof)으로 간단하고 빠르게 검증하는 것입니다. 그런데 지금의 상태 트리인 머클 패트리샤 트라이(Merkle Patricia Trie, MPT)는 이 목표와 맞지 않습니다. 노드 인코딩에 RLP를 쓰고 증명 회로에 부담이 큰 Keccak 해시를 쓰며 계정 트리 안에 스토리지 트리가 또 들어가는 트리 속 트리 구조인 데다, 계정 코드는 상태 트리에 들어 있지도 않습니다. 증명 크기도 문제입니다. 노드마다 자식이 16개라서 크기 2^32인 트리에서 가지 하나를 증명하는 데 평균 약 3840바이트가 필요하고, 3000만 가스로 서로 다른 계정 코드를 1바이트씩만 읽는 최악의 블록이라면 약 330MB가 필요하다는 계산이 원문에 있습니다. 자식이 2개인 바이너리 트리로 바꾸면 증명이 가장 작아지고, 증명 친화적인 해시 함수로 바꿀 길도 열립니다.
무엇이 바뀌나
지금
- 계정 트리와 각 계정의 스토리지 트리가 분리된 트리 속 트리 구조입니다
- 노드마다 자식이 16개라서 증명에 형제 노드가 15개씩 들어가 크기가 큽니다
- 컨트랙트 코드는 상태 트리에 포함되지 않습니다
- 노드 인코딩에 RLP를 사용합니다
EIP-7864 이후
- 계정 헤더, 코드, 스토리지가 하나의 바이너리 트리에 들어갑니다
- 자식이 2개라 같은 크기 트리에서 증명이 가장 작아집니다 (2^24 트리 기준 768바이트)
- 코드가 31바이트 청크로 잘려 트리에 저장됩니다
- RLP 없이 단순한 해시 규칙만으로 노드를 머클화합니다
누구에게 영향이 있나
- 클라이언트 팀: 상태 트리를 새로 구현해야 합니다. 대신 트리가 단일 key/value 저장소 추상화라서 데이터베이스 읽기·쓰기, 캐싱, 동기화, 증명 생성·검증 코드가 단순해집니다.
- 컨트랙트·앱 개발자: 코드 청크 접근 가스 비용이 달라져 애플리케이션의 경제성에 영향을 줄 수 있습니다. 원문은 가스 한도 상향으로 완화할 수 있다고 적습니다. 또 EVM 안에서 과거 상태를 증명하던 방식은 트리 구조가 바뀌어 이제 동작하지 않습니다.
- 영지식 증명 리서처: 확장 노드 없는 단순한 분기 규칙과 증명 친화적 해시 후보(BLAKE3, Poseidon2 등) 덕에 회로 안에서 상태 증명을 만들기 쉬워집니다.
- 일반 사용자: 당장 바뀌는 것은 없지만 장기적으로 블록 전체를 유효성 증명으로 검증하는 가볍고 빠른 체인 검증의 기반이 됩니다.
심층 설명
트리 구조: 스템과 4가지 노드
트리는 키가 바이트열, 값이 32바이트인 key/value 저장소입니다. 키의 첫 바이트는 저장 종류, 마지막 1바이트를 뺀 앞부분은 스템(stem), 마지막 바이트는 서브인덱스입니다. 같은 스템을 가진 키 256개는 같은 StemNode 아래에 모입니다. 노드는 네 종류입니다. InternalNode는 left_hash와 right_hash를 가집니다. StemNode는 stem, left_hash, right_hash를 가지며 LeafNode는 32바이트 value 또는 empty를 가집니다. EmptyNode는 빈 서브트리를 뜻합니다. 경로는 248비트 전부를 쓰지 않고 같은 접두사를 가진 다른 스템이 있을 때만 필요한 최소한의 InternalNode를 만듭니다. MPT와 달리 경로 중간에 확장 노드(extension node)를 두지 않는 대신 이 방식으로 깊이를 줄입니다.
머클화 규칙
해시 함수 hash에는 두 가지 특례가 있습니다. 64바이트가 전부 0이면 결과는 32바이트 0이고 그 외에는 선택된 암호학적 해시 H(value)를 그대로 씁니다. 입력 길이는 32 또는 64바이트만 허용됩니다. 노드별 규칙은 internal_node_hash = hash(left_hash || right_hash), stem_node_hash = hash(stem || 0x00 || hash(left_hash || right_hash)), leaf_node_hash = hash(value), empty_node_hash = 32바이트 0입니다. 스템 노드 아래 256개 값은 리프 해시들을 둘씩 묶어 올라가는 작은 머클 트리로 접은 뒤 스템과 함께 해시합니다. RLP 인코딩은 쓰지 않습니다.
트리 임베딩과 기본 데이터 패킹
상태는 저장 종류별로 나뉩니다. HEADER_SUBTREE = 0, CODE_SUBTREE = 1, STORAGE_SUBTREE = 255가 키의 첫 바이트가 되어 종류별로 따로 동기화하거나 다르게 다룰 수 있습니다. 계정 헤더 스템에는 기본 데이터(BASIC_DATA_LEAF_KEY = 0), 코드 해시(CODE_HASH_LEAF_KEY = 1), 첫 스토리지 슬롯들, 첫 코드 청크들이 함께 들어가 자주 같이 읽는 데이터의 가지 열기(branch opening)를 줄입니다. 기본 데이터 리프 하나에 version(오프셋 0, 1바이트), code_size(오프셋 5, 3바이트), nonce(오프셋 8, 8바이트), balance(오프셋 16, 16바이트)가 빅엔디언으로 패킹되고 바이트 1..4는 예약입니다. 필드를 따로 둘 때 필요한 3~4번의 가지 열기가 1번으로 줄어 가스 비용과 위트니스 생성이 단순해집니다.
코드 청크화
컨트랙트 코드는 31바이트 조각으로 잘려 트리에 들어갑니다. 각 청크는 32바이트 값으로, 바이트 1~31이 코드의 i번째 31바이트 조각이고 바이트 0은 청크 앞부분 중 PUSHDATA에 속한 바이트 수입니다. 예를 들어 PUSH4의 데이터 중간에서 청크가 끊기면 다음 청크는 2 97 96 PUSH1 128 MSTORE처럼 시작해 앞의 2바이트가 데이터임을 표시합니다. 청크 위치는 chunk_id가 CODE_CHUNKS_IN_HEADER = 16보다 작으면 헤더 스템의 CODE_OFFSET + chunk_id 자리에, 그 이상이면 CODE_SUBTREE에서 hash(address + bytes([high]))를 스템으로 하여 STEM_SUBTREE_WIDTH = 256개 단위로 묶입니다. 코드가 상태 트리에 들어가므로 코드 접근도 머클 증명으로 다룰 수 있게 됩니다.
스토리지 배치와 그라인딩 방지
앞쪽 스토리지 슬롯(STORAGE_CHUNKS_IN_HEADER = 4 기준)은 계정 헤더 스템에 함께 저장되고 나머지는 STORAGE_SUBTREE에 256개 단위로 묶여 들어갑니다. 같은 256 크기 범위에 있는 슬롯들은 같은 스템을 공유하므로 인접 슬롯을 함께 증명하기 쉽습니다. 키 계산에 hash(address) + hash(address + int_to_bytes(high)) 형태를 쓰는 이유도 명시되어 있습니다. 특정 위치에 몰리도록 스토리지 키를 그라인딩해도 다른 컨트랙트 사이에서 재사용할 수 없게 만들어 서비스 거부(DoS) 공격 경로를 막기 위해서입니다. MAIN_STORAGE_OFFSET = 256**31이며 STEM_SUBTREE_WIDTH의 거듭제곱이어야 한다는 불변식이 있습니다.
해시 함수는 미정, 양자 내성 고려
현재 초안과 참조 구현은 BLAKE3를 쓰지만 원문은 이를 최종 결정으로 보지 말라고 명시합니다. 후보는 BLAKE3(회로 밖 성능 좋음, 보안성 검증됨), Keccak(이더리움이 이미 사용, 회로 증명 효율은 낮음), Poseidon2(회로 내 성능 우수, 이더리움재단 암호학 이니셔티브가 보안 분석 진행 중이며 선택 시 필드 선택과 인코딩 명세가 추가로 필요)입니다. 양자컴퓨터가 2030년대에 현실화될 수 있다는 전문가 추정과 2030년까지 타원곡선 암호 사용 중단을 권고하는 NIST 지침도 근거로 듭니다. 타원곡선에 기대는 버클 트리(Verkle Tree)와 달리 이 설계는 해시 함수에만 의존해 양자 내성이 있습니다. 원문은 이 트리가 프로토콜의 최종 상태 트리가 될 가능성이 높다고 적습니다.
전환 방식과 하위 호환성
이 EIP의 새 바이너리 트리는 빈 상태로 시작하고 새 상태 변경만 담습니다. 기존 MPT는 사라지지 않고 동결됩니다. 동결된 MPT 데이터를 새 트리로 옮기는 작업은 별도 하드포크인 EIP-7748이 맡습니다. 포크 적용 방식은 EIP-7612, 접근 이벤트와 가스 규칙은 EIP-4762에 정의되어 있습니다. 호환성 문제는 두 가지입니다. 첫째, 코드 청크 접근 가스 비용이 애플리케이션 경제성에 영향을 줄 수 있는데, 구현 시 가스 한도를 올려 완화할 수 있습니다. 둘째, 트리 구조가 바뀌므로 EVM 안에서 과거 상태를 증명하던 방식은 더 이상 동작하지 않습니다. EIP-7736 같은 상태 만료 전략은 StemNode에 epoch 필드를 더하거나 247비트 스템에 메타데이터 서브트리를 두는 식의 설계 변경으로 적용할 수 있다고 적습니다.
Draft 상태라 바뀔 수 있습니다
이 EIP는 2025년 1월 20일에 만들어진 Draft 상태로, 내용이 아직 바뀔 수 있습니다. 특히 해시 함수는 BLAKE3, Keccak, Poseidon2 중 미정이고 테스트 벡터와 보안 고려 사항(Security Considerations) 절도 아직 비어 있거나 논의가 필요하다고 표시되어 있습니다. 코어 개발자 콜에서 이 EIP를 특정 포크에 포함하기로 한 결정은 현재 기록에 없습니다.