Ethereum : State Transition / Merkle Patricia Tree

비트코인 공부하다가 본 바이너리 머클 트리는 그럭저럭 이해를 한거 같았는데.. 이더리움 공부 중 머클 패트리샤 트리는 잘 이해가 안돼서 쓰는 글. 바이너리 머클트리 간단하게 정리하고 머클 패트리샤 트리 정리해보겠음 . 

 

우선 "상태전이" 라는 개념에 대해서 알아야 하는데 

상태전이  ( State Transition )

상태 전이란, 특정 시점의 현재 상태 S가 상태 전이 함수(APPLY())에 의해 다른 상태(S’)로 전이되거나 전이에 실패하고 이전 상태로 복귀되는 것을 말한다.

- 상태 전이를 보여주는 사진 

 

단일 상태전이 

이더리움의 State는 복수의 상태 변이를 갖지 못하고 단 하나의 상태 변이만을 가짐.

하나의 상태가 여러개의 상태로 전이 된다면, 채굴자들은 어떤 상태가 맞는 것인지 판단하고 합의할 수 없음.

 

비트코인의 경우 상태를 업데이트 하지 않고 거래내역을 저장하는 구조.. 이더리움은 상태전이의 특징을 갖고 거래내역을 업데이트하지만 , 모든 거래내역을 업데이트하는 것은 아니고, 기존 거래 내역을 저장하고 있다가 블록에 대한 거래에 이상이 없다고 판단되면 상태전이가 진행됨. 

 

Binary Merkle Tree

비트코인에서 사용되는 이진 머클 트리에 대해 알아보자.

머클트리 ( Merkle Tree ) 는 블록에 포함된 거래 내역을 나무 형태로 요약한 것이다. 머클 트리는 블록 내에서 다수의 원장 ( ledger ) 들을 암호화하고 합치는 과정을 반복하여 최종적으로 하나의 유닛 ( Unit ) 으로 암호화하는 방법이다.

머클트리의 형태는 블록이 보유하고 있는 거래 내역들의 해시값을 가장 가까운 거래내역끼리 쌍을 지어 해시화하고, 쌍을 지을 수 없을 때까지 해당 과정을 반복하여 완성. 이 과정을 통해 다수의 데이터를 하나로 묶어 용량을 절약할 수 있다. 

 

결론적으로는 공간을 더 낭비하게 된다는 모순이 존재하는데, 비트코인 네트워크 상에 존재하는 다양한 노드들 중 머클 트리 속 구체적인 정보와 축약된 정보를 모두 가지고 있는 노드들에게는 공간이 낭비되는 것이 맞다고 한다. 그러나 라이트 노드( light node )* 는 단지 블록의 헤더만 가질수 있게 되어 전체적으로 볼 때 공간이 크게 절약된다고 한다. 

 

* 라이트노드 : 블록체인 거래내역 중 일종의 핵심본만 저장하는 노드로, 풀노드에 거래 데이터를 요청하여 개별 거래를 검증하는 기능을 수행한다.  일부 블록만 소유하고 풀 노드에게서 필요한 정보만을 받아서 유지하는 노드이며, 머클 트리는 라이트 노드에서 거래를 검증하기 위해 사용된다. 

 

* 풀 노드 : 풀 노드는 제네시스 블록부터 현재 시점의 형성된 블록이 연결된 블록체인 전체를 유지하는 노드이다. 

 

머클트리의 머클루트가 라이트 노드의 역할을 하는 셈이고, 머클루트값만 알 수 있다면 최소한의 정보로 필요한 정보를 블록에서 가져올 수 있다. 방대한 거래 내역을 조회하지 않고 32바이트에 불과한 값으로 거래내역 검증을 확실하게 할 수 있다는 큰 장점이 있다. 또한 모든 거래내역을 합해 해시화한 값이 머클루트이기 때문에 거래내역에 작은 변화가 생기면 상위 해시값이 모두 변해 위변조를 빠르게 찾아낼 수 있다.

 

위에 설명한 상태 전이랑은 아무런 관련이 없어보이지만 , 비트코인의 경우 이진 머클 트리를 구성하는 내용들이 모두 새롭게 생성된다. 즉 상태 전이는 없다는 말임. 그렇다면 상태를 전이시키는 머클 트리도 있는가? 

 

상태전이 일반(non-binary) 머클 트리

(패트리샤는 아님)

Block 175223 과 Block 175224 2개의 블록이 존재하며, 두 블록은 같은 머클 트리를 공유한다. 

상태전이랑 무슨 관련이 있나? 보면 구성 내용들이 새롭게 생성되는 것이 아닌 공통된 것은 공유하고, 전이(변경) 된 것만 마지막 트리에서는 변경하여 사용하고 있다. -> 공간을 절약할 수 있음 

 

패트리샤 트리

1번부터 7번까지의 단어가 있고, 그 단어를 모두 기록하는 것보다 단어와 단어 사이에 공통적인 부분을 공유함으로써 공간을 절약할 수 있게 된다. r노드가 1~7번 단어에 모두 공통되어 포함돼 있기 때문에 루트 노드가 됨. 이를 이더리움 블록체인에 적용하게 되면 아래 나오게 될 확장 패트리샤 트리와 이어지게 됨.

 

확장 패트리샤 트리

3가지의 노드가 존재한다 . Extension Node (확장 노드), Branch Node (브랜치 노드), Leaf Node (리프 노드)

같은 정보에 대한 노드는 Branch Node 에 저장하고 이를 Leaf Node로 뻗어나가면서 트리에 대한 정보를 최소화한다. 

-> 브랜치 노드를 통해 가지치기가 시작된다고 생각하면 됨. 확장노드를 통해서 공유되어질 키 값들이 저장되고 키 값에 대한 패스가 종결되었을때 리프 노드에 value에 해당 주소에 대한 정보들을 포함하고 있게 됨. (? 사실 잘 이해 안간다)

 

첫째. 리프노드 

 - 이 노드는 키값에 대한 패스가 종결되었을 때 value 에 해당 주소에 대한 정보들을 포함하고 있게 됩니다.
   위의 그림에서는 a77d337 는 value 로 1.00WEI 를 가지고있네요.(실제 이더리움 구조에서는 더 복잡한 value 를 갖게 됩니다)

둘째. 브랜치노드

- 이 노드는 16개의 16진수 값과 value 를 가지고 있게 됩니다. 이 노드를 통해서 가지치기가 시작됩니다.

셋째, 확장노드

- 이 노드를 통해서 공유되어질 키값들이 저장되게 됩니다. 이 노드 자체로는 종결되지 않기 때문에 value 로는 이후의 키 값을 책임질 브랜치 노드를 갖게 됩니다.

 

상태전이 일반 머클 확장 패트리샤 트리 

 

확장 패트리샤 트리에 상태전이 일반 머클트리를 적용한 것. 

"상태전이" + "머클트리" + "확장패트리샤 트리" = "상태전이 일반 머클 확장 패트리샤 트리" 이다.

 

( 27이 삭제되면서 공간을 절약할 수 있다. )