오버레이를 사용하여 Ethereum 상태 트리의 형식 변경

편집자 주: 이 기사의 출처는이더리움 애호가(ID: ethfans)편집자 주: 이 기사의 출처는

이더리움 애호가(ID: ethfans)

계정과 계약이 데이터를 저장하는 방식은 이더리움에 영향을 미치는 많은 문제 중 하나입니다. Ethereum 프로토콜은 Merkle Patricia Tree(MPT, Merkle Patricia Tree)를 사용하여 계정 및 계약 데이터를 구성합니다. 이 데이터 구조는 이론적으로는 잘 작동하지만 실제로는 해결하는 것보다 더 많은 문제를 생성합니다. 핵심 개발자들은 이 데이터 구조를 이진 트리로 대체하기를 원한다고 수년간 논의해 왔으며, 이 기사에서는 이 문제에 대한 나의 견해와 이 변환을 달성하는 방법을 설명할 것입니다.

배경

내가 제안한 접근 방식에는 네트워크가 두 트리 구조를 모두 유지하는 전환 기간이 포함됩니다. 이것의 장점은 트리 구조를 변환하는 프로세스가 체인의 작동에 영향을 미치지 않으며 모든 계정이 바이너리 형식으로 변환되도록 할 수 있다는 것입니다.

배경

현재 이더리움의 상태 트리는 16진수입니다. Hex는 각 노드에 16개의 하위 노드가 있음을 의미합니다. 이론적으로 이것은 괜찮습니다. 자식이 더 많다는 것은 모든 데이터를 저장하는 데 더 적은 "수준"(예: 트리 높이)이 필요하기 때문입니다.

이미지 설명

- 그림 1. 값 v가 해당 키 0xaa에 저장되는 방법을 보여주는 16진수 트리의 예. 이 트리의 키 길이는 2바이트에 불과하며 0xaa를 따라 하위 트리만 표시됩니다. 간결함을 위해 관련 없는 하위 트리는 "..."로 대체됩니다.

위 사진의 나무는 매우 짧고 넓다는 것을 알 수 있습니다. 동일한 키-값 쌍이 주어지면 다음 그림은 이진 트리 저장소의 상황을 보여줍니다. 170은 이진 트리에서 10101010으로 표시됩니다.

이미지 설명

그림에서 알 수 있듯이 이진 트리는 훨씬 더 깊고 좁습니다.

이더리움에서 각 블록은 블록이 처리된 후 이더리움의 글로벌 상태를 나타내는 MPT의 루트 해시 값인 stateRoot 필드를 포함합니다. 일반적으로 이 해시 값은 루트 노드의 16개 자식 노드의 해시 값 목록을 해싱하여 얻습니다. 이러한 자식 노드의 해시 값은 자식의 16개 자식 노드 해시 값 목록을 해싱하여 얻습니다.

패키지 트랜잭션이 새 블록을 생성할 때마다 광부는 계정 트리를 업데이트하고 루트 해시를 다시 계산합니다. 루트 해시는 새 블록의 stateRoot 필드에 저장되고 새 블록이 합의됩니다.

이미지 설명

여기에 문제가 있습니다. 모든 노드가 해시되면 루트 해시를 다시 계산하는 데 너무 오래 걸리므로 루트 노드의 해시를 계산하기 위해 광부는 데이터베이스에서 형제 해시(형제 해시)를 검색합니다. 후자(채굴자가 데이터베이스에서 형제 해시 검색)는 전자(채굴자가 데이터베이스에서 모든 리프 노드를 가져와 해시)만큼 시간이 걸리지 않지만 이 작업은 여전히 ​​시간이 많이 걸립니다. 각 해시는 데이터베이스에서 가져와야 하기 때문입니다.

16진수 트리에서는 일반적으로 각 수준에서 15개의 형제 해시 값을 가져와야 합니다. 위에서 구성한 예(그림 1)에서 (루트 해시를 다시 계산하려면) 30개의 해시가 필요합니다.

이진 트리는 조금 더 깊지만 각 수준에서 하나의 형제 해시만 필요합니다. 위의 예(그림 2)에서는 해시가 8개만 필요합니다! 이것이 이진 트리가 실제로 더 나은 이유입니다.

첫 번째 레벨 제목

불행히도 이진 트리로 변환하는 것은 간단하지 않습니다. 변환할 데이터가 너무 많아 변환을 수행하는 데 15초 블록 생성 시간 이상이 소요됩니다.

게다가, 당신이 5000페이지의 책을 번역하고 있고 저자가 계속해서 이야기에 일부 변경을 가했으며 이러한 변경이 당신이 이미 번역한 페이지에 영향을 미친다고 말한다고 상상해보세요...그러면 프로세스는 끝이 없습니다. 상태 트리의 형식을 변환하는 것도 같은 문제입니다. 주소의 형식 변환을 방금 완료하고 사용자가 주소를 사용하면(따라서 주소의 상태를 업데이트함) 처음부터 다시 변환해야 합니다. (주소 업데이트의 상태가 전체 상태 트리에도 영향을 미치기 때문입니다.)

보조 제목

1단계 - 변환

이 방법에서 블록 높이가 H1일 때 두 개의 상태 루트가 있어야 합니다. 하나는 "기본 레이어" 16진수 상태 루트이고 다른 하나는 "오버레이 레이어" 이진 트리 상태 루트입니다.

이미지 설명

헥스 트리는 읽기 전용이므로 상태에 대한 모든 업데이트는 오버레이 트리에서 이루어집니다.

트랜잭션이 계정을 읽거나 업데이트할 때 시스템은 먼저 오버레이 트리를 검색합니다. 오버레이 트리에서 계정을 찾을 수 없는 경우 이전 16진수 트리에서 값을 검색합니다.

보조 제목

2단계 - 기본 트리 전환

이미지 설명

- 그림 5. 변환의 두 번째 단계에서 채굴자는 블록 헤더에서 변환된 이진 트리의 루트로 16진수 루트를 교체하여 준비가 되었음을 네트워크에 신호합니다.

충분한 일련의 블록이 변환된 이진 기본 트리의 루트에 동일한 값을 제공하면 대부분의 채굴자가 변환을 완료하고 변환된 트리를 승인했음을 의미합니다. 그런 다음 병합 프로세스가 시작됩니다. (번역자 주: 이때 병합은 읽기 전용 바이너리 기본 트리와 읽기-쓰기 바이너리 커버 트리에 대한 것입니다.)

병합 프로세스는 지속적으로 진행됩니다. 새 블록이 생성될 때마다 n개의 키가 오버레이 트리에서 제거되고 이진 기본 트리에 다시 삽입됩니다. 이 프로세스는 오버레이 트리에서 모든 키가 제거될 때까지 계속됩니다. 이 단계에 도달하면 블록 헤더는 더 이상 오버레이 상태 트리의 루트를 보유하지 않습니다.

다음 단계

보조 제목

다음 단계