EIP-2584 오버레이 트리 기반 트라이 전환 (Trie format transition with overlay trees)

콜 결정 없음 · 확장성·데이터 · 원문 상태 Stagnant · 2020-04-03 작성

16진 형태인 상태 트라이를 이진 트라이로 바꾸는 과정에서, 새 값은 임시 오버레이 트라이에 쓰고 기존 트라이는 백그라운드에서 변환한 뒤 합치는 4단계 전환 방법을 제안합니다.

왜 필요한가

이더리움은 상태(state)를 16진 머클 패트리샤 트라이(MPT)로 저장하는데, 증명 크기와 저장 크기를 줄이기 위해 이를 이진 트라이로 바꾸려는 논의가 오래 이어져 왔습니다. 전체 상태의 양이 너무 많아서, 블록 생성 주기와 비슷한 시간 안에는 한 번에 변환할 수 없다는 게 문제입니다. 체인을 멈추고 변환하는 '전체 정지' 방식이나, 주소에 접근할 때마다 그 자리에서 변환하는 '쓰기 시 변환' 방식이 논의됐지만 각각 가용성이나 예측 불가능성 문제가 있었습니다. 이 EIP는 체인이 멈추지 않고 정상 동작하면서도, 예측 가능한 시간 안에 트라이 전체를 이진 형식으로 바꾸는 방법을 제시합니다.

무엇이 바뀌나

지금

EIP-2584 이후

누구에게 영향이 있나

심층 설명

왜 오버레이 방식인가

그동안 논의된 방법은 '전체 정지' 방식과 '쓰기 시 변환(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입니다.

EIP 원문 · ← EIPs