라벨이 state trie인 게시물 표시

Secure Tree - state trie의 키가 256 bit인 이유

지난번 글에서 설명했듯이 ethereum의 상태는 modified Merkle Patricia Trie(a.k.a. MPT)에 저장된다. Ethererum에서 값은 nonce, balance 등 account의 상태고, 그 키는 account의 주소다. 이 Account의 주소는 160bit이기 때문에, MPT의 root에서부터 40 nibble의 경로를 타고 가면 account의 상태가 나와야 한다. 하지만 실제로 ethereum의 상태가 저장된 MPT에서 account의 주소를 키로 가지는 노드를 찾으면, leaf node가 아닌 branch nodeextension ndoe가 나온다.이는 ethereum이 account를 MPT에 집어넣을 때, account의 주소를 바로 키로 사용하는 것이 아니라, 주소의 keccak-256 hash를 키로 사용하기 때문이다. 즉, 40 nibble의 account 주소를 따라가는 것이 아니라, 64 nibble의 hash를 따라가야 원하는 account를 찾을 수 있다. 이렇게 account의 주소를 바로 경로로 사용하는 것이 아니라, 주소의 hash를 경로로 사용하는 것을 ethereum은 secure tree라고 부른다.Secure tree에 대해 자세히 설명하기 전에 ethereum이 사용하는 MPT에 대해서 더 알아야할 것이 있다. Ethereum에 있는 MPT는 state trie만이 아니다. Ethereum은 총 네 종류의 MPT가 있다.첫 번째는 state trie다. 여기에는 ethereum의 account 정보가 저장된다. 여기서 account 정보는 account의 nonce, balance, storage root의 hash, code의 hash다. 만약 계정이 smart contract라면 storage root에는 smart contract의 state를 가지는 MPT의 root가 저장되고, code에는 evm bytecode의 hash 값이 저장된다.두 번째는 storage trie다. …

Modified Merkle Patricia Trie - ethereum이 상태를 저장하는 방법

이미지
Ethereum에서 네트워크 부분을 빼고 보면, Ethereum은 하나의 state machine이고, transaction은 ethereum의 state를 변경시키는 것이다. 이 state는 key-value pair로 표현된다. Key-value pair를 저장하는 방법은 여러 가지 있지만, ethereum에서는 state를 저장하기 위해 Modified Merkle Patricia Trie(a.k.a. MPT)라는 특수화된 방법을 사용하도록 스펙에서 정의하고 있다.MPT는 기본적으로 Patricia trie와 Merkle tree를 합친 것이다. 여기에 추가로 ethereum의 특성에 맞게 몇 가지 최적화를 했다. 따라서 MPT를 쉽게 이해하기 위해서는 Patricia trie와 Merkle tree를 아는 것이 좋다.Patricia TriePatricia trie는 Prefix tree, radix tree, trie 등 다양한 이름으로 불리는 자료구조다. Trie는 path에 key를 집어넣어 공통된 prefix를 가지는 노드들은 같은 path를 가진다. 공통된 prefix를 찾는데 가장 빠르고, 적은 메모리로 구현할 수 있으며, 구현도 간단하다. 그래서 router 등 낮은 사양의 기계에 들어가는 routing table의 구현체로 많이 사용된다.Merkle TreeMerkle tree는 hash들의 tree다. Leaf 노드에는 데이터를 보관한다. Leaf의 부모는 leaf의 hash를 가지고, 그 부모는 자식들의 hash의 합을 다시 hash 한 값을 가진다. Merkle tree는 leaf 노드를 제외한 노드들은 전부 hash를 가지고 있기 때문에 hash tree라고도 불린다.Merkle tree를 사용하면 서로 다른 두 노드가 같은 데이터를 가졌는지 효율적으로 비교할 수 있다. 예를 들어 위와 같은 L1, L2, L3, L4가 있을 때, 같은 Top Hash를 가졌는지만 비교하면 된다. 만약 Top Hash가 다르고, 어떤 데이터가 다른지…

Ethereum의 state trie pruning

이미지
Ethereum은 현재 상태를 prefix tree의 일종인 modified merkle patricia trie(a.k.a. MPT)로 저장한다. MPT는 state root의 hash를 계산하기 위해 state trie 전체를 볼 필요가 없이, 수정된 branch의 hash만 다시 계산하면 되기 때문에 빠르게 root hash를 찾을 수 있다.
MPT를 이용하면 새로 추가되는 노드의 수도 최소화할 수 있다. 예를 들어 위의 그림에서 block N과 block N + 1의 차이는 A의 오른쪽 자식의 값이 10에서 20으로 변경된 것뿐이다. 이 경우 10에서 20으로 변경된 노드의 부모 외의 다른 노드는 전부 기존의 노드를 재활용할 수 있다. 따라서 푸른색으로 그려진 3개의 노드만 새로 추가하면 된다.그렇다면 더는 접근할 필요가 없는 노드들은 어떻게 되는가? 위의 예제에서 붉은색으로 표시된 3개의 노드는 block N + 1에서는 필요 없는 노드다. 그렇다면 이 3개의 노드는 3개의 푸른색 노드가 추가되고 나면 바로 지워도 될까? 그랬으면 문제가 쉬웠겠지만 아쉽게도 그렇지 않다. Ethereum은 block의 finality를 보장하지 않는다. 다른 말로 언제든지 block N + 1이 block N으로 retract 될 수 있다는 것이다. 게다가 Web3 API를 통해서 과거의 state에 접근하는 것도 가능하기 때문에 현재 상태에서 안 쓰이는 노드를 바로 지울 수는 없다.그렇다고 영원히 남겨둘 수는 없다. 현재 ethereum에서 최신 state의 크기는 약 25GB 정도지만, 과거 state를 전부 저장하면 300GB를 넘어간다. 게다가 이 크기는 점점 커질 것이기 때문에 이를 전부 저장하는 것은 현실적이지 않다. Ethereum은 접근할 수 있는 과거 state를 127개로 제한하여 그보다 오래된 state에만 포함된 노드는 지워도 되도록 하였다. 하지만 지워도 된다는 것과 지울 수 있다는 것은 별개의 문제다. DB에 저장돼있는 노드 중 최근 127개의…