December 19, 2021
먼저 문서에 오류가 있을 수 있음을 밝힙니다. 수정 요청 부탁드립니다!
두번째로, 이 문서는 여러 출처의 글을 정리한 글입니다. Geth 코드 레벨 이해를 담고 있지 않습니다.
이더리움은 Account-based 블록체인입니다.
이더리움에서 상태란 Account의 상태입니다. 각 Account는 Balance, Nonce 그리고 Smart Contract의 Data Store를 상태값으로 가집니다. (”배포된” 스마트 컨트랙트도 Account 입니다)
정리해서 Account의 상태란 Balance, Nonce, DataStore (+ Code)를 말합니다. 그리고 이러한 Account State가 모두 모여 거대한 Global State
를 형성합니다. 이런 Global State를 저장하는 가장 이상적인 데이터 구조는 간단한 Key-Value 저장소입니다. 32 byte address
를 Key로, 상태 객체를 값으로 가집니다.
간단한 Key-Value Store의 문제점
이를 해결하기 위해 Merkle Tree
를 도입합니다.
요약하면 작은 변경사항 때문에 전체 데이터를 매번 다시 계산하는게 아니라, 각 Account State를 Leaf Node로 두고, 루트까지의 경로만을 다시 해싱하여 “일정한 실행 시간”이 보장되게 만듭니다. 또한 이러한 “State Root Hash”를 블록헤더에 포함시킵니다. (이제 Merkle Proof가 가능합니다)
그러나 아직 계산에 많은 복잡함이 필요합니다. 이미 존재하는 leaf node(Account)의 수정을 통해 Root Hash변경하는것은 비교적 쉬운 일이지만, 새로운 node를 추가하거나 삭제하는 일은 트리의 정렬을 다시 계산하는 복잡한 작업입니다. (즉 지금까지 만들어진 모든 Hash를 다시 계산해야합니다) 이를 해결하기 위해 Patricia Tree
를 도입합니다.
블록체인에서 Merkle Proof 예시
위 문제점을 개선하기 위해, address의 공통 prefix를 바탕으로 트리를 구성할 수 있습니다. 여전히 Account Data는 leaf node에 존재하지만 내부 노드는 좀 더 복잡한 구조를 가집니다. (이는 Trade-off 관계입니다) 이렇게 하면 삽입과 삭제 작업을 진행할때 모든 노드를 이동하지 않고 leaf node에서 root node까지의 경로(Path)만을 변경합니다
그리고 이 두가지를 합쳐 Merkle Patricia Tree
(MPT)가 완성됩니다. (안정된 생성,수정,삭제,조회 = 검증 시간을 가집니다) 이더리움은 MPT 구조를 사용해, 원하는 작업을 빠르게 사용합니다 (Trade-off)
그러나 이러한 MPT 구조일때도 역시 단계가 깊어지는 문제가 발생합니다. 이는 (getBalance, writeNonce)마다 여러번의 디스크를 읽어야한다는 것을 의미합니다. 또 이는 지속적으로 깊어집니다. (물런 메모리에 저장하긴 하지만 생략하겠습니다) 이러한 문제를 해결하기 위해 Modified Merkle Patricia Tree
를 사용합니다.
아래 사진을 보면 알 수 있듯, 각 노드를 Extension Node, Branch Node, Leaf Node로 구분합니다. 가장 큰 목적은 경로를 압축하는 것이라 생각됩니다. 이러한 지속적인 자료구조의 개선을 통해 안정된 연산시간을 가지게 됩니다. (여전히 Leaf Node는 Account입니다)
좌측 상단을 보면 BlockHeader의 StateRoot가 보인다. 이는 State Trie의 Root Node의 KECCAK256 해시 값이다. 그리고 그 아래로 State Trie 구조가 보이며 Leaf Node는 Account의 State이다. (이는 추상화된 이미지이다)
아래는 (위 자료구조를 사용한) 이더리움의 State Trie를 추상화한 모습입니다.
Leaf Node의 Account가, 블록헤더에 State Root(Hash)가 포함되어 있는것이 확인 가능합니다.
그 옆에 Transactions Root Hash, Receipts Root Hash도 포함되어 있습니다.
이미지를 보면 매 블록마다 모든 State Trie를 다시 생성하는게 아니라, 이어나가는 것을 알 수 있습니다.
저장공간 사용에는 효율적이나 만약 Disk 절약을 위해 과거 State를 정리하고자하면 매우 복잡한 작업입니다. 왜냐하면 정리 알고리즘을 통해 필요 없어진 State를 확인해야 하는데, 이건 모든 Depth를 뒤지며 찾아내야 하기 때문입니다. 이 작업을 Pruning
(State 정리)이라고 합니다 (아직까지 효율적인 상태정리 알고리즘이 없습니다)
이러한 이미지는 추상화된 이미지이고, Geth는 LevelDB를 통해 해당 구조를 구현, 저장합니다.
모든 내용은 요약되었기 때문에, 아래 링크를 통해 자세한 내용을 읽어보는 것을 추천합니다.
추가 학습