작성자 : 
PROBLEM
- 블록의 크기가 점점 증가함에 따라 메모리 부담
- 사용되지않는 account가 차지하는 비율이 높음. 특히 contract account
IDEA
- 일정기간 동안의 최신 거래내역이 없는 account, 사용되지않는 account를 따로 압축 보관하여 관리하자.
- Garbage Collection
KEYWORD: zero-balance account, old account, dust account, freezed account, state-bloat
PREVIOUS WORK
- EIP 168
→채택 안됨.
이더리움의 머클 패트리샤 트리
State Trie, Storage Trie, Transactions Trie, Receipts Trie
이번에 알아볼것은 위의 파란글씨 두가지.
State Trie
블록헤더에 stateRoot가 저장
블록마다 존재하므로 트랜잭션에 의해 state가 변경될때마다 루트해시값이 달라짐.
State정보가 담겨 있다.
- key값(path)은 항상 sha3(Address) 이고 value 값은 항상 rlp(Account)
- value 값에 쓰인 Account은 [nonce, balance, storageRoot, codeHash]
*rlp : 임의의 깊이와 개수로 중첩된 배열을 binary data로 표현하는 인코딩 방식
- Account
Nonce : 0부터 시작되는 값으로 EOA인 경우에는 해당 어카운트에서 수행된 트랜잭션의 수, CA인 경우에는 해당 어카운트에서 만들어진 컨트랙트의 수
Balance : 해당 어카운트의 이더 잔액(Wei 단위 기준)
Root : 해당 어카운트의 state가 저장된 State trie의 root
CodeHash : 해당 어카운트의 스마트 컨트랙트 바이트 코드의 해시로 이 코드값이 nil 로 비어있으면 해당 어카운트는 EOA
Storage Trie
Account 배열 안에 storageRoot에 root 값이 들어감. key 값(path)은 약간의 계산 과정을 거친다. 아래 링크에 보다 상세한 설명이 있음.
Transactions Trie
블록헤더에 transaction의 merkleRoot가 저장
key 값(path)은 rlp(transactionIndex) 가 되는데 transactionIndex는 블록안 tx의 index 값이다.
블록이 채굴된 후에는 바뀌지 않습니다.
Receipts Trie
블록헤더에 receiptRoot가 저장
부가적인 거래 정보 (누적 가스 사용량, 로그등) 가 담겨 있습니다. key 값(path)은 rlp(transactionIndex) 가 됩니다. 블록이 채굴된 후에는 바뀌지 않습니다.
secure tree
이더리움의 MPT는 자식이 하나인 branch만 extension으로 압축하므로 임의로 두개의 자식을 만드는 branch노드를 만들수 있다면 적은 비용으로 공격 가능하다.
그래서 secure tree사용
- Secure tree : Account의 address(160bit, 40nibble)를 바로 mpt의 key로 사용하지 않고 keccak256으로 hash 한값(256bit, 64nibble)을 사용하는것.
- State, storage trie만 secure tree를 사용함
(Tx, receipt trie의 키는 각 tx와 receipt의 인덱스기 때문에 어짜피 조작 불가하여 사용하지 않는다.)
- 깊이가 64이하라는게 보장됨(즉 root부터 64nibble의 경로를 따라가면 leaf노드가 나온다.)
따라서 같은 트랜잭션이면 값을 변경하는데 드는 최대비용이 같다. 최대비용이 보장됨
[key, value]: [address(256bit), Account]
State trie
state transition
비트코인은 거래가 일어나면 새로운 UTXO를 생성하거나 삭제하는 방식이지만, 이더리움은 state가 변경되는 방식
이더리움은 이전의 블록과 공통된것은 공유하며, 변경된 것만 추가한다. 하지만, 이전의 블록에 있던 state를 삭제하지는 않는다.
실제로는 append되는 형식이라 결국 history가 남게되어 많은 공간을 차지하고, state pruning이 필요하다는 이야기가 나오게됨
*비트코인은 binary merkle tree 를 사용하여 매 블록마다 거래를 저장한다.
3가지 노드
- 확장노드(expansion)
- key : 공통의 키 값(encodedPath)
- value는 branch node를 가리킴
- Patricia를 그대로 사용하지 않고 수정하여 사용한 결과. 자식이 하나인 노드들을 압축
2. 브랜치 노드(branch)
- 16개(16 children)의 16진수 값 : 0부터 f까지
- value [17] : 자식노드를 가리킴
3. 리프노드(leaf)
- key : 키 값이 종결(encodedPath)
- value : 주소에 대한 거래 정보포함
- 끝에 terminator(0x10)가 붙음
- nibble : 4bit(1/2 byte), key를 나타내기위한 단위. 16진수, 예를 들어 0x1, 0x4, 0xf 등
- Hex-Prefix encoding(HP encoding)
- hex 값을 key앞에 붙여서terminator(leaf노드 끝에 있는 0x10)없이도 node의 종류를 식별하는 목적으로 쓰인다.(leaf와 extension을 식별)
- 키의 nibble이 홀수인지 짝수개인지에따라 1개, 2개의 nibble을 prefix로 붙여 항상 바이트가 되게 만든다.
- prefix이해를 위한 예제 (참고하세요)
prefix가 0, 1 으로 시작-> extension node
0x0 : shared nibble의 개수가 even(짝수)
0x10: shared nibble의 개수가 odd(홀수)
prefix가 2, 3 으로 시작 -> leaf node
0x2 : key-end의 nibble의 개수가 even
0x30: key-end의 nibble의 개수가 odd
selfdestruct(owner)
계약을 삭제
owner에게 contract account의 모든 balance를 전송한다.
그러나 여전히 history에 있으며, 대부분의 노드에서 존재한다. 그러므로 하드디스크에서 데이터를 삭제하는 것과는 다르다.
state trie에서는 삭제되지만 db에는 남는다.
suicided가 true인 경우 삭제된다.
REFERENCES
- GC