Ethanos
===

### Title
Ethanos: Efficient Bootstrapping for Full Nodes on Account-based Blockchain

### Abstract
- 이더리움은 account-based blockchain 이다
- EOA (externally owned account) : ether 를 주고 받을 수 있는 지갑의 역할을 하는 account 를 의미함
- Contract: contract 도 account 를 가지고, address 를 가지는데 여기에 해당된다 [1]
- Full node 가 아닌 account 는 tx 의 검증을 다른 full node 에게 부탁해야한다. 그로 인해 보안 이슈가 발생한다
- 가장 큰 오버헤드는 블록의 state trie 에 있는 모든 account 의 state 를 sync 받는것에서 온다 (수십GB)
- 하지만, 95%의 account 는 휴면 account 임.
- Ethanos 는 state optimization technique 임. 주기적으로 state trie 를 비워주고, active account 로만 state trie 를 rebuild 함
- 두 가지 trie 를 관리함. 하나는 current period's state trie 에서 available 한 account 를 활용해서 tx 를 실행시키고, 직전 period 의 state trie 의 end 에서 available 했던 account 도 활용한다. 그리고 이 두 period 에서 available 하지 않았던 account 는 필요시 restore tx 를 통해서 복구시킨다.
- 이 period 는 1주일 간격이고, 이 간격마다 empty trie 를 수행한다. Restore tx 는 작게 발생하면서 state trie 의 크기는 획기적으로 줄였다고 볼 수 있음.

### Introduction
- UTXO 기반의 비트코인 시스템은 암묵적으로 블록체인의 global state 를 유지한다.
- 이더리움은 tx 랑 별개로 명시적으로 account 와 balance 의 global state 를 유지한다. 이를 state-based model 이라고 하는데 이 것은 smart contract 에 적합한 모델이다. 카르다노, 솔라나, 알고랜드, 폴카닷 등 다양한 주류 블록체인이 이러한 state-based model 을 사용하고 있다.
- 증가하는 tx 와 account 는 이더리움 데이터의 크기를 크게 만드는데, 이더리움 블록이 tx 뿐만 아니라 account state 도 저장한다는 것에 있어서 비대화 되는 이더리움의 데이터 크기의 문제를 더 악화시키고 있다.
- Full node 가 아닌 light node 는 스스로 검증할 수 있는 능력이 없기 때문에 validator 에게 의존하는 문제점이 있음. Full node의 수가 적으면 네트워크의 안정성도 부족해지고, miner 의 수가 적으면 보안에 취약할 수 있음.
- 따라서 full node 가 필수적으로 갖고 있어야하는 데이터의 크기가 작아야하는데, 이 논문에서는 state trie 자료 구조가 핵심 bottleneck 이라고 생각함. State trie 는 merkle patrica trie (mpt) 자료구조임. (자세한건 뒤에서)
- 하나의 node 가 full node 가 되기 위해서는 full sync 라는 과정을 거치는데, 이 full sync 라는 과정은 genesis block 부터 현재 block 까지 과거 히스토리부터 지금까지의 모든 state trie 를 재생산하는 과정임.
- Geth (공식 이더리움 클라이언트)는 fast sync 라는 모드를 지원하는데, 이건 pivot block 의 state trie 의 스냅샷만 다운로드 하는 방식이다. Pivot block 이란 현재 block 뒤 64개 block 을 의미하고, pivot block 부터 현재 block 까지의 state trie 만 재생산하는 방식이다. 전체 중에 6.7%만 sync 받는데 이 크기만해도 235 GB 씩이나 된다.
- 235 GB 중에서도 MPT-based state trie 는 70 GB 크기를 가지는데, 이건 hash-based random database access 를 요구한다. Hash based random database access 의 traversing, transferring, rebuilding 과정은 디스크 IO 를 유발하고 이는 fast sync 가 여전히 오래 걸리도록 한다.
- 이 논문에서 제안하는 방법은 95%의 휴면 계정을 없애버리거나 고립시키는 것은 쉽지 않으니, 매 period 시작마다 빈 trie 를 생성하고, period 안에서의 active 계정에 대한 state trie 를 rebuild 한다. 이전 period 의 끄트머리에서 state trie 를 캐싱하고, account 가 현재 state trie 에 정보가 없으면 직전 period 의 캐싱된 state trie 데이터에서 찾도록 한다. 만약 캐싱된 데이터에도 없으면 restore tx 를 통해서 복구한다.
- Account 가 receiver 인 경우에는 account 를 하나 생성한 다음에 sender 가 되었을 때 (crumb account) 진짜 account 랑 merge 한다.
- Restore tx 는 merkle proof, void proof, bloom filter 를 통해서 구현했다.
- 작은 용량의 노드도 Full validation 을 할 수 있다는 것이 장점이고, 실제 이더리움 데이터를 통해서 220MB 까지 줄일 수 있다는 것을 알 수 있었음. 추가적으로 오래된 tx 나 덜 중요한 블록 헤더를 쳐내면 더 최적화 시킬 수 있음.

### 이더리움 과 State Trie 에 대해서

- 이더리움
- Account-based 블록체인
- State 란: Address-account 페어 - tx에 의해서 업데이트됨 -> 업데이트될 때 update state 와 tx 가 블록에 기록됨
- Account 란
- 40글자의 hex 로 구성되어 있는 주소로 접근 가능함
- 4가지의 데이터를 갖고 있음
- Nonce: account 가 생성한 tx 의 수. 동일한 tx 가 두 번 이상 수행되는 것을 방지하기 위함
- Balance: ether 잔고
- StorageRoot: null if EOA, CA (contract account) 인 경우, smart contract 의 state 가 저장되어있는 storage 의 key 를 갖고 있음.
- CodeHash: null if EOA, CA 인 경우 db 에서 contract code 를 갖고오기 위한 hash 값
- Gossip protocol 로 propagate 함 [2]
- Gossip protocol 은 Epidemic protocol 이라고 불리기도 함
- 두 가지 type 의 protocol 이 존재함
- Dissemination protocol: 데이터를 퍼뜨림. 네트워크에 agent 를 flooding 하면서 동작한다. 여기서도 2가지 타입이 있는데, event dissemination protocol 에서 gossip 은 주기적으로 발생하고, 이벤트는 gossip 을 trigger 하지 않음. 노드는 이벤트를 리포팅함. 이 방식의 문제점은 event 발생 지점부터 전달까지 지연시간이 길다는 것이다. Background data dissemination protocol 은 지속적으로 노드들과 관련된 정보를 gossip 한다. 전파 지연 속도는 큰 문제가 되지 않는다. (와닿지 않는다 -> >자세한 내용은 이것 참고 : http://publicatio.bibl.u-szeged.hu/1529/1/gossip11.pdf)
- Protocols that compute aggregate: 잘 이해가 되지 않으니 위 pdf 의 aggregation 을 이해하도록 한다
- 구성 요소
- Block: 매 라운드마다 생성되는 state synchronization
- Miner: 블록을 생성하는 노드
- Transaction: tx 는 sender 계정과 receiver 계정이 있고, 양쪽 계정의 balance 를 변경한다. Tx 의 validity 를 검증하기 위해서 sender 가 충분한 balance 가 있는지 확인해야하고, tx 의 nonce 값이 sender 의 nonce 값과 동일한지 확인해야한다. Tx 는 miner 에게 지급한 tx fee 를 보유하고 있고, 성공적으로 mining 되면 block reward 가 miner 에게 지급된다. 그리고 tx 는 sender 계정이 private key 로 서명한 signature 를 갖고 있다.
- 동작 방식
- 다른 노드는 새로 생성된 블록을 받게 되면 reproduce 하고 현재 state 를 검증하기 위해서 블록에 적혀있는 tx 를 replay 하게 된다
- 대부분의 노드가 sync 받았다고 생각이 들면, 다음 라운드로 넘어간다.
- Miner 는 ethash 라는 알고리즘을 기반으로 pseudo 랜덤하게 결정이 된다. (bitcoin 의 pow 와 비슷한 방식)
- 한 라운드 안에서 두 개 이상의 블록이 생성되었다면 Race condition 을 해결하기 위해서 longest chain rule 을 활용한다
- 이러한 일련의 합의 과정은 모든 노드가 결국에는 single state 의 동일한 블록을 갖고 있도록 보장해준다
- State Trie

참고 자료
---
[1] https://ethereum.org/en/developers/docs/accounts/
[2] https://en.wikipedia.org/wiki/Gossip_protocol