EIP-7748 버클 트리로의 상태 전환 (State conversion to Verkle Tree)
콜 결정 없음 · 확장성·데이터 · 원문 상태 Draft · 2024-07-23 작성
블록마다 정해진 개수의 키-값을 기존 머클 패트리샤 트리(MPT)에서 버클 트리(VKT)로 옮기는 변환 절차를 정의합니다. 변환이 끝나면 오버레이 트리 없이 VKT만으로 상태에 접근할 수 있습니다.
왜 필요한가
이더리움은 모든 계정과 컨트랙트 데이터를 머클 패트리샤 트리(Merkle Patricia Tree, MPT)라는 자료구조에 보관하는데, 이를 버클 트리(Verkle Tree, VKT)라는 새 자료구조로 바꾸는 전환이 준비되고 있습니다. 앞서 EIP-7612는 오버레이 트리(Overlay Tree)라는 중간 장치를 두어 트랜잭션이 새로 쓰는 데이터만 VKT에 기록되도록 했습니다. 그런데 전체 상태가 너무 커서 트랜잭션이 자연스럽게 건드리기만 기다려서는 모든 데이터가 옮겨가지 않습니다. 그래서 이 EIP는 블록마다 정해진 양만큼 옛 트리의 데이터를 기계적으로 새 트리로 옮기는 절차를 제안합니다. 합리적인 시간 안에 변환을 끝내고 완료 후에는 오버레이 트리라는 중간 장치를 걷어내어 모든 상태 접근을 VKT로 직접 하는 것이 목표입니다.
무엇이 바뀌나
지금
- 상태 전체가 MPT에 있고 트랜잭션이 건드린 데이터만 오버레이 트리를 거쳐 VKT에 기록됩니다
- 트랜잭션이 손대지 않는 데이터는 계속 MPT에 남습니다
- 클라이언트는 두 트리를 겹쳐 보는 오버레이 트리 추상화를 유지해야 합니다
EIP-7748 이후
- CONVERSION_START_TIMESTAMP부터 블록마다 트랜잭션 실행 전에 변환 단계가 자동으로 실행됩니다
- 블록당 최대 CONVERSION_STRIDE개의 변환 단위(스토리지 슬롯, 계정 데이터와 코드)가 VKT로 옮겨집니다
- 전체 변환이 끝나면 오버레이 트리를 제거하고 VKT만으로 상태에 접근할 수 있습니다
누구에게 영향이 있나
- 클라이언트 팀: apply_body에 변환 단계를 넣고 변환 진행 상태 추적 구조와 trie_get_next_at_key 같은 새 함수를 구현해야 합니다. 프리이미지 해결 요건도 세 가지 중 하나를 충족해야 합니다.
- 노드 운영자: 변환 기간 동안 블록마다 추가 쓰기 작업이 발생합니다. 플랫 DB가 없는 클라이언트는 변환 시작 전에 배포될 프리이미지 데이터베이스를 내려받아야 할 수 있습니다.
- 사용자와 앱 개발자: 트랜잭션을 보내는 방식은 바뀌지 않습니다. 변환은 프로토콜 내부에서 자동으로 진행되는 절차입니다.
심층 설명
상수와 변환 단위의 정의
두 상수가 정의되지만 값은 모두 TBD입니다. CONVERSION_START_TIMESTAMP는 변환이 시작되는 타임스탬프이고, CONVERSION_STRIDE는 블록당 변환할 수 있는 변환 단위(conversion unit)의 최대 개수입니다. 변환 단위는 두 가지입니다. 컨트랙트 스토리지 슬롯 하나, 그리고 계정 데이터(잔액, 논스, 코드 해시 등)와 코드(있는 경우)입니다. Rationale은 CONVERSION_STRIDE 값을 블록당 추가 부하를 과하게 만들지 않을 것, 감당 가능한 긴 리오그 동안 부하를 관리할 수 있을 것, 변환을 최대한 빨리 끝낼 것 사이의 균형을 맞추는 성능 벤치마크로 정했다고 설명합니다.
변환 단계는 트랜잭션 실행 전에 실행
apply_body(...)에서 블록 타임스탬프가 CONVERSION_START_TIMESTAMP 이상이고 state._conversion_finished가 거짓이면 state_convert(state, CONVERSION_STRIDE)를 호출합니다. 호출 위치는 트랜잭션 실행 전입니다. Rationale에 따르면 변환을 트랜잭션 실행 후에 두면 같은 블록 안에서 트랜잭션의 쓰기와 변환된 키-값이 겹쳐 같은 블록 내 stale 처리를 신경 써야 하지만 제안된 순서에서는 이전 블록의 쓰기로만 stale이 생길 수 있습니다. 또 다음 블록이 오기 전에 변환을 미리 수행하는 것 같은 최적화의 복잡성도 줄일 수 있습니다.
변환 진행 상태를 추적하는 자료구조
State 클래스에 _conversion_curr_account(Optional[CurrentConvertingAccount])와 _conversion_finished(bool) 필드를 추가합니다. CurrentConvertingAccount는 address와 phase를 담고, phase는 StoragePhase 또는 AccountDataPhase입니다. StoragePhase는 next_key 이상의 키를 가진 스토리지 슬롯부터 변환을 이어가고, 그런 슬롯이 없으면 AccountDataPhase로 넘어갑니다. 새 함수 trie_get_next_at_key(trie, key_seek)는 트라이 키가 key_seek 이상인 첫 (키, 값)과 그보다 큰 가장 작은 다음 트라이 키를 반환하며 secured=True인 트라이에서만 사용합니다. 구체 구현은 각 클라이언트 아키텍처에 맡깁니다. 스토리지를 먼저, 계정 데이터를 나중에 처리하는 순서는 여러 실행 클라이언트의 플랫 DB 구조와 맞물려 랜덤 디스크 IO를 최소화한다고 Rationale에 설명되어 있습니다.
state_convert 알고리즘과 stale 값 방지
state_convert는 n < stride이고 변환이 끝나지 않은 동안 반복합니다. 스토리지 변환에는 set_storage에 새로 추가된 only_if_empty 파라미터를 써서 오버레이 트리에 이미 값이 있으면 쓰지 않습니다. 이전 블록의 트랜잭션이 이미 VKT에 기록한 값을 옛 MPT 값으로 덮어쓰는 일을 막는 장치입니다. 계정 데이터는 get_account로 읽어 set_account로 다시 쓰는데, 데이터가 아직 MPT에 있으면 MPT에서 읽어 VKT에 쓰고 이미 VKT에 있으면 같은 값을 다시 쓰는 noop이 되므로 양쪽 모두에서 stale 데이터를 쓰지 않습니다. 코드는 chunkify_code로 청크로 나눠 한 번에 전부 삽입합니다. 청크마다 1단위를 소비하는 CodePhase 대안도 있었지만 알고리즘 복잡성을 줄이려고 채택하지 않았고 현재 최대 코드 크기 기준 최악의 경우 한 블록이 CONVERSION_STRIDE 한도를 24k/31~=793 단위 초과할 수 있다고 설명합니다.
EIP-7610·EIP-161 특수 계정의 처리
EIP-7610이 언급하는 28개 계정은 논스가 0이고 코드가 없는데 비어 있지 않은 스토리지 트리가 있습니다. 이 스토리지 슬롯들은 접근할 수 없으므로 변환 과정에서 제외합니다. 알고리즘에서도 논스가 0이고 코드가 비어 있는 계정은 스토리지 단계를 건너뛰고 바로 AccountDataPhase로 갑니다. 또 EIP-161 대상 계정은 CONVERSION_STRIDE 한도 계산에 포함하지 않는데, 남아 있는 계정들에 대해 EIP-158 방식의 일괄 삭제를 시도하기 때문입니다. 이런 계정 1천 개가 한 블록에 몰리면 한도 계산 없이 반복해야 해 위험해 보일 수 있지만 원문은 삭제할 계정 수가 수십 개 수준으로 매우 적고 연속해 있지도 않아 문제가 되지 않는다고 설명합니다.
프리이미지 요건과 참조 구현
실행 클라이언트는 다음 세 조건 중 최소 하나를 충족해야 합니다. 프리이미지 해결이 필요 없는 제대로 된 플랫 DB 설계를 갖추거나, 트라이 키에서 프리이미지를 찾을 수 있는 전체 프리이미지 데이터베이스를 갖추거나(성능이 나쁠 수 있음), 변환 시작 전에 배포될 프리이미지 데이터베이스 이미지를 내려받아야 합니다. 참조 구현은 gballet의 go-ethereum 저장소 transition-post-genesis 브랜치에 있으며 커맨드라인에서 --override.overlay-stride를 0이 아닌 값으로 설정하면 동작합니다.
Draft 상태와 남은 과제
이 EIP는 Draft 상태라 내용이 아직 바뀔 수 있습니다. 두 핵심 상수 값이 모두 TBD이고 변환 완료 예상 시간은 추정치가 있지만 포크 시점에 가까워지면 최신 상태 크기로 다시 계산할 필요가 있다고 적혀 있습니다. 테스트 케이스는 외부 문서에 있다고만 되어 있고 보안 고려 사항은 논의가 필요하다(Needs discussion)고 명시되어 있습니다. 현재까지 코어 개발자 콜에서 이 EIP의 포크 포함이 결정된 기록은 없습니다.