간략히 알아보는 프루닝

 

 

 

프루닝(Pruning)은 경량화 기법의 하나로 인공지능 분야에서 불필요한 노드를 제거하는 기술이다. 

 

 

 

비트코인 프루닝

 

비트코인이 네트워크 성장과 함께 스토리지도 함께 커지고 있었다. 그래서 이 문제를 지속해서 해결하고자 도입한 것이 

Block file pruning이다. 비트코인 코어 개발팀이 이 기능을 추가했고 비트코인에서 참조할 가능성이 없는 불필요한 데이터를 삭제함으로써 비트코인 레지스터 용량을 최적화했다. 이로써 작은 버전의 Full Blockchain을 실행할 수 있었고 prune mode의 지갑을 실행하면 오래된 체인 기록을 삭제하기 때문에 디스크 공간을 최적화할 수 있었다. 

이렇게 프루닝이 가능했던 이유는 블록을 실행/검증하는데 블록 내 트랜잭션  Input  /  Output만 사용하면 되기 때문이다.

 

 

 

 

이더리움 프루닝 

 

이더리움도 비트코인과 마찬가지로 네트워크성장과 함께 스토리지가 커지고 있었고 프루닝을 진행하게된다. 이더리움에서는 프루닝을 State Trie Pruning이라고 부른다.  State Trie Pruning을 도입함으로서 다음의 2가지 개선이 있었다.

 

• MPT(Modified Merkle Particia Trie)로 인하여 빠른 Hash 계산 
• 새로 삽입되는 노드의 수를 최소화 

 

 

 

 

Modified Merkle Patricia Trie  ===  Modified + Merkle Tree + Patricia Trie

MPT(Modified Merkle Patricia Trie)는 이더리움에서 State 및 Transaction, Receipt를 저장하기 위한 핵심자료구조다.

 

Patricia Trie : Patricia Trie는  prefix tree, radix tree, trie등 다양한 이름으로 불리는 자료구조다. trie는 path에 key를 집어넣어 공통된 prefix를 가지는 노드들은 같은 path를 가진다. 공통된 prefix를 찾는데 가장 빠르고, 적은 메모리로 구현할 수 잇으며 구현도 간단하다.

 

Merkle Tree : Merkle tree는 hash들의 tree다. Leaf노드는 데이터를 보관하고 Leaf의 부모는 leaf의 hash를 가지고 그 부모는 자식들의 hash의 합을 다시 hash한 것을 가지고 있다. 

 

 

MPT는 Merkle Tree처럼 각 노드가 hash를 가짐, 노드의 hash는 노드내용의 sha3 hash함수로 결정된다. 이 hash는 노드를 지칭하는 Key값으로도 사용된다. geth에서는 leveldb를 paritiy에서는 rocksdb라는 key-value-storage에 state를 저장한다.

이 때 스토리지에 저장되는 key와 value는 이더리움의 state의 key-value가 아니다. Key는 이 노드의 hash고 value는 MPT노드의 내용이다.  그리고 이더리움의 state의 key는 MPT에서 path로 사용된다. 

 

MPT에는 그리고 3종류의 노드가 있다.

 

• branch : 하위 16 child 를 연결하고, value 를 가진다. [ v0, ..., v15, value ]
• leaf : Key 에 해당하는 실제 value 를 가집니다. [ encodedPath, value ]
• extension : leaf 가 공통의 prefix 를 가질 경우 사용합니다. [ encodedPath, key ]

 

 

 

 

참고:

https://www.qaupot.com/posts/3b93fea9aaae458b9d91284fdcc16123 

[Structures] 202. Modified Merkle Patricia Trie - Qaupot Blog

https://medium.com/codechain-kr/modified-merkle-patricia-trie-ethereum%EC%9D%B4-%EC%83%81%ED%83%9C%EB%A5%BC-%EC%A0%80%EC%9E%A5%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95-e385f7d6bf84

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