EIP-2584 오버레이 트리 기반 트라이 전환 (Trie format transition with overlay trees)
콜 결정 없음 · 확장성·데이터 · 원문 상태 Stagnant · 2020-04-03 작성
16진 형태인 상태 트라이를 이진 트라이로 바꾸는 과정에서, 새 값은 임시 오버레이 트라이에 쓰고 기존 트라이는 백그라운드에서 변환한 뒤 합치는 4단계 전환 방법을 제안합니다.
왜 필요한가
이더리움은 상태(state)를 16진 머클 패트리샤 트라이(MPT)로 저장하는데, 증명 크기와 저장 크기를 줄이기 위해 이를 이진 트라이로 바꾸려는 논의가 오래 이어져 왔습니다. 전체 상태의 양이 너무 많아서, 블록 생성 주기와 비슷한 시간 안에는 한 번에 변환할 수 없다는 게 문제입니다. 체인을 멈추고 변환하는 '전체 정지' 방식이나, 주소에 접근할 때마다 그 자리에서 변환하는 '쓰기 시 변환' 방식이 논의됐지만 각각 가용성이나 예측 불가능성 문제가 있었습니다. 이 EIP는 체인이 멈추지 않고 정상 동작하면서도, 예측 가능한 시간 안에 트라이 전체를 이진 형식으로 바꾸는 방법을 제시합니다.
무엇이 바뀌나
지금
- 상태는 16진(hexary) 머클 패트리샤 트라이 형태로만 저장됩니다.
- 트라이 형식을 바꾸려면 체인을 멈추거나 접근 시점마다 변환해야 합니다.
- 전체 상태를 한 번에 변환하기엔 양이 너무 많아 블록 시간 안에 끝낼 수 없습니다.
EIP-2584 이후
- 블록 헤더에 오버레이 이진 트라이의 루트 Hₒ가 새로 추가됩니다.
- 새 상태 쓰기는 오버레이 트라이에 기록되고, 기존 16진 트라이는 백그라운드에서 이진 트라이로 변환됩니다.
- 변환이 끝나면 오버레이의 항목을 매 블록 N개씩 이진 베이스 트라이로 옮겨 합칩니다.
- 오버레이가 완전히 비면 헤더에서 Hₒ 필드가 사라지고 전환이 끝납니다.
누구에게 영향이 있나
- 사용자: 전환 기간 중 오버레이 트라이가 커지는 것을 막기 위해 SSTORE 비용이 오를 수 있지만, 체인 자체는 멈추지 않고 계속 동작합니다.
- 채굴자: 16진 트라이를 이진으로 변환해 루트 Hᵣ²를 계산하는 작업과, 이후 매 블록 오버레이 항목을 베이스 트라이로 옮기는 작업을 수행해야 합니다.
- 클라이언트 개발자: 블록 헤더 포맷, 상태 읽기·쓰기 로직, 계정 삭제 처리를 오버레이/베이스 트라이 이중 구조에 맞게 다시 구현해야 합니다.
- 지갑·앱 개발자: 최종적으로 상태가 이진 트라이로 바뀌면 증명(proof) 크기가 줄어들어 향후 증명 기반 기능에 영향을 줍니다.
심층 설명
왜 오버레이 방식인가
그동안 논의된 방법은 '전체 정지' 방식과 '쓰기 시 변환(copy on write)' 방식이었습니다. 전체 정지는 변환에 필요한 긴 시간 동안 체인을 멈춰야 하고, 쓰기 시 변환은 접근되는 가지(branch)만 그때그때 변환해 완료 시점이 예측되지 않습니다. 이 EIP의 오버레이 방식은 체인이 정상적으로 계속 동작하면서, 트라이 전체가 예측 가능한 시간 안에 완전히 이진 형식으로 바뀐다는 장점이 있다고 설명합니다.
이진 트라이의 정의
이 EIP에서 이진 트라이는 MPT와 같되 다음이 다릅니다. 키 I₀의 바이트 열을 비트 단위로 취급해 I₀[i]가 i번째 비트가 되고, extension이나 leaf 항목의 첫 요소는 니블 대신 비트로 표현됩니다. branch는 두 항목으로 구성되며 각 항목은 그 지점에서 키의 두 가지 비트 값(0 또는 1)에 대응합니다. 형식적으로 c(𝕴,i) ≡ RLP((u(0), u(1))로, u(j)는 I₀[i]=j인 I들의 집합에 대해 i+1에서 재귀적으로 계산됩니다. 16진 트라이를 이 형식으로 바꾸는 함수를 ß로 표기합니다.
1단계: 오버레이 쓰기와 백그라운드 변환
h₁부터 h₂ 전까지, 블록 헤더에 오버레이 이진 트라이 루트 Hₒ가 추가됩니다. 16진 트라이를 이진으로 바꾸는 작업이 백그라운드에서 시작되며, 목표는 Hᵣ² ≡ ß(Hᵣ¹⁶) 계산입니다. 변환이 끝나지 않은 동안 Hᵣ는 부모 블록과 동일하게 유지됩니다. 상태 읽기는 먼저 오버레이 트라이를 보고 없으면 기존 베이스 트라이를 봅니다. 상태 쓰기는 오버레이에만 기록되고 베이스 트라이는 건드리지 않습니다. 계정이 삭제되면 해당 주소에 빈 해시 H(∅)를 기록해 삭제를 표시하며, 이후 그 주소를 읽으면 베이스 트라이 내용과 무관하게 계정이 없는 것으로 취급됩니다. h₂는 채굴자가 변환을 끝낼 충분한 시간을 두고 정해집니다.
2단계: 점진적 병합
h₂에서 ϒ 실행 전에 Hᵣ는 Hᵣ²(변환된 이진 베이스 트라이 루트)로 교체됩니다. Hₒ 필드는 헤더에 남아있지만 오버레이 내용은 읽기와 삭제만 가능합니다. h≥h₂인 매 블록마다 ϒ 실행 전에 오버레이에서 사전순으로 앞선 N개 계정을 골라, 값이 빈 해시면 베이스 트라이에서 같은 주소 계정을 삭제하고, 아니면 그 값으로 베이스 트라이를 삽입·갱신합니다. 이 단계의 상태 쓰기는 베이스 트라이에 바로 반영되며, 같은 키가 오버레이에 남아있으면 오버레이에서 삭제됩니다. 오버레이가 비면 2단계가 끝나고 3단계가 시작됩니다.
3단계: 전환 완료
3단계는 2단계와 동일하게 동작하되, Hₒ 필드만 블록 헤더에서 완전히 제거됩니다. 이로써 트라이는 전부 이진 형식 하나로 통일됩니다.
보안 고려사항
원문은 세 가지 공격 가능성을 지적합니다. 첫째, 특정 공격으로 오버레이 트라이를 비정상적으로 크게 만들면 전환 기간 동안 가스 비용이 오르는 상태가 길어질 수 있어, 1단계 중 SSTORE 비용을 올리는 방식으로 완화할 수 있다고 봅니다. 둘째, h₂가 너무 일찍 오면 대다수 채굴자가 제시간에 올바른 Hᵣ² 값을 만들어내지 못할 수 있습니다. 셋째, 네트워크의 51% 이상을 차지하는 채굴자 그룹이 잘못된 값을 보고하면 아무도 이의를 제기하지 못한 채 자금이 탈취될 위험이 있습니다.
포크와 현재 상태
이 변경은 헤더 포맷과 해시 값이 달라지므로 하드포크가 필요하며, 오버레이 트리를 구현하지 않거나 새 이진 루트를 받아들이지 않는 클라이언트는 포크가 갈립니다. 원문은 이에 대한 완화 조치를 따로 제안하지 않습니다. 커뮤니티 피드백에 따르면 빠른 머신에서 변환 작업이 약 30분 걸린다는 예비 테스트 결과가 있었고, 초기 버전에 있던 '채굴자가 이진 베이스 루트 값에 투표하는' 절차는 복잡도 문제와 '가장 긴 체인' 규칙이 이미 같은 기능을 보장한다는 이유로 제거됐습니다. 이 EIP의 원문 상태는 Stagnant입니다.