구역 분할 이진 트리, 가볍게 증명하는 새 상태 저장소
Strawmap I* (2028) · partitioned binary tree
이더리움이 계정·코드·스토리지를 저장하는 자료 구조를 지금의 16진 머클 패트리샤 트라이에서 가지가 둘인 이진 트리 하나로 바꿉니다. 블록을 증명으로 가볍게 검증하기 위한 준비 단계입니다.
왜 필요한가
이더리움의 장기 목표는 블록을 유효성 증명(validity proof)으로 검증해 누구나 가볍고 빠르게 체인을 확인하게 하는 것입니다. 그러려면 거래를 실행하면서 읽은 상태를 증명해야 하는데, 지금의 머클 패트리샤 트라이(MPT)는 여기에 맞지 않습니다. 증명하기 비싼 Keccak 해시와 RLP 인코딩을 쓰는 데다 계정 트리 아래 스토리지 트리가 따로 달린 '트리 속 트리' 구조입니다. 컨트랙트 코드의 일부만 골라 증명할 수도 없습니다. 코드 1바이트를 증명하려면 코드 전체를 공개해야 해서 최악의 경우 블록 하나에 약 1.8GB의 증명이 필요합니다. 가지가 둘인 이진 트리는 증명 크기를 최소로 줄입니다. 증명에 유리한 해시로 바꾸면 증명을 만드는 회로의 성능도 좋아집니다. 해시 함수만 쓰고 타원곡선을 쓰지 않아 양자 컴퓨터 공격에도 안전합니다. 다만 해시 함수는 아직 정해지지 않았고 EIP도 초안(Draft) 단계라 세부 내용은 바뀔 수 있습니다.
어떻게 동작하나
- 첫 바이트로 구역을 나눕니다 모든 키의 첫 바이트가 구역을 표시합니다. 0x00은 계정 헤더, 0x01은 코드 조각(청크), 0xFF는 스토리지입니다. 계정 아래 스토리지 트리를 따로 두지 않고 모두 한 트리에 넣습니다.
- 키를 조립합니다 구역 바이트, 해시로 정한 트리 위치, 서브 인덱스 1바이트를 이어 키를 만듭니다. 구역 안에서 키 길이를 하나로 고정해 어떤 키도 다른 키의 앞부분이 되지 않습니다. 컨트랙트 코드도 조각으로 잘라 같은 방식으로 넣습니다.
- 두 종류 노드로 트리를 만듭니다 리프 노드는 완전한 키와 32바이트 값을, 브랜치 노드는 아래 키들이 공유하는 비트 구간과 왼쪽·오른쪽 자식을 갖습니다. 키 집합마다 유효한 트리가 하나뿐이어서 누가 만들어도 같은 트리가 나옵니다.
- 해시로 묶어 루트 하나로 요약합니다 리프와 브랜치에 각각 태그를 붙여 해시하고 위로 올라가 루트 하나로 요약합니다. 리프가 완전한 키를 담으므로 다른 곳의 분기가 바뀌어도 무관한 리프의 해시는 변하지 않습니다. 해시 함수는 BLAKE3, Keccak, Poseidon2 중 미정입니다.
관련 EIP
- EIP-8297 구역 분할 이진 상태 트리