[이더리움] Merkle Patricia Tree (MPT) 를 이해하기 위한 여정

 

이더리움에서 활용하고 있는 "머클 패트리샤 트리"를 이해하려다가 주화입마에 빠지신 분들이 꽤 있는거 같은데요. 사실 그것은 당신들의 탓이 아닙니다. 비탈릭이 쓴 머클링 in 이더리움 등의 블로그 글 및 각종 이더리움 책에서 설명된 내용을 읽고 금방 이해하는게 사실상 쉽지 않습니다. 남을 이해시키기 위한 글이 아니라는 생각이 들기도 하는데요.

이 글에서 저는 "이해시켜 드리기 위한 글"을 써보려고 합니다. 만약 또 실패한다면 역시 제가 모자라서 그런것이 겠지요. "개념을 이해시켜 드리기 위한 글" 이기 때문에 아주 디테일한 부분(트리에 대한 구체적 요소,추가,삭제,업데이트 및 블록상세등)을 과감히 생략하였습니다. 지엽적인 오류도 있을 수 있습니다. OTL

머클패트리샤트리를 이해하기 위해서는 먼저 몇가지 짚고 넘어가야 할 것이 있습니다. 먼저 용어의 재정의 인데요.
보다 선명한 이해를 위해서는 비트코인의 "머클 트리"는 "바이너리 머클 트리" 라고 말해야 하며, 이더리움의 "머클 패트리샤 트리" 는 "상태전이 일반 머클 확장 페트리샤 트리" 라고 말해야 합니다. 각각의 단어마다 중요한 의미를 가지고 있으며 본 글을 통해 차차 설명드릴 예정입니다.

이제 시작해 볼까요?

 "상태전이"  "바이너리 머클 트리" "상태전이 일반 머클 트리"  "확장 페트리샤 트리"  각각의 어떤 의미를 가지는지 봅시다. 마지막엔 모두 합쳐서~"상태전이 일반 머클 확장 페트리샤 트리" !!!

1. "상태전이"

먼저 여기 아이언맨이 있습니다. 

"어벤져스 인피니티 워" 의 한장면인데요. 현재 아이언맨의 체력수치는 "100" 입니다.  아이언맨 역할을 한 로버트 다우니 주니어는 체력 "100"으로 역할을 수행하고 있습니다.

하지만 우주가 파멸되는 것을 볼 수 없었던 "타노스" 의 주먹 한방에 체력 50이 고갈됩니다.
이때, 이전의 체력 "100" 이었던 로버트다우니주니어를 영화에서 제외해서 구경시키고, 체력"50"인 이윤석을 투입해서 아이언맨의 역할을 수행하게 합니다. 좀 말이 안되는거 같나요? 즉 어떤 변화가 일어 났을때 "교체" 합니다. 이것은 상태 전이(변화)가 아닙니다. 

프로그래밍적으로 보면 immutable 속성이라고 하며,  

a = 100; 

이런 a 를 100에서 50으로 값을 변경 할 경우 그냥 기존 a 에 50 을 넣어서 변경하는것이 아니라, 기존 100은 놔준채 50을 가진 새로운 a를 만들게 되는 방식입니다. 딱 봐도 먼가 불필요한 공간을 낭비하는것 처럼 보이죠? 하지만 장점도 크기 때문에 현재 프로그래밍 언어에서 주목받는 방식이기도 합니다.

이것이 "비트코인"에서 처리하는 방식입니다. "교체" , "기존 것은 놔두고 새로운것을 만든다" 

근데 이더리움에서는 그냥 상식적인(?)인 방식을 사용합니다. 그냥 체력이 줄어든 기존 아이언맨이 계속 타노스와 싸우는 거죠. 즉 상태가 변경된다는 것이죠. 이것을 고상하게 "상태 전이"라고 합니다. 아무것도 아니죠 사실.

블록체인(비트코인)틱한 예로 들어 볼까요? (디테일은 이렇지 않습니다. 예를 위한 것임) 

철수가 이전에는 100원 이었고 현재는 60원입니다. (영희는 120원, 위에 그림 잘못;) 이전블록에도 있고 현재 블록에도 기록되어 있네요. 다른 사람들 기록도 마찬가지입니다. 먼가 공간을 낭비하는 듯한 느낌입니다.

좀더 구체적으로 보면 

위의 그림에서는 철수의 80이 50으로 교체되고, 영희는 10을 40으로 상태가 변이된 것이 아니라, 30이 새로 생성되었습니다. 즉 비트코인은 "추가,삭제" 방식으로 이루어지고, 이더리움은 아주 상식적인 "변이" 방식으로 이루어집니다. (이더리움의 모든것이 "상태변이"로 이루어지는 것은 아닙니다)

이제 이더리움식 상태전이를 보겠습니다.

33블록과 34블록은 하나를 가르키고 있으며, 철수와 영희에 대한 상태가 변경(전이)되었을 뿐입니다. 공간의 낭비가 줄어 들었습니다.
(* 위는 이해를 위한 예이고 정확히는 이더리움의 state 저장은 항상 최신본만 유지하는게 아니라, history 또한 유지합니다.  과거 데이터를 유지할 이유가 없으면 그냥 update 해도 되지만, 이더리움은 불안요소를 가지고 있습니다. 따라서 실제는 변하지 않은 데이터는 계속 유지하되, 변한 데이터는 update 하지 않고 append 합니다. 남은 데이터는 나중에 삭제합니다. 가지치기(prunning) 이라고 하는데 비탈릭이 한번 개념을 제시했었는데 문제가 있다고 하며, 현재 정확히 어떻게 구현되어 있는지는 확인 안해봤습니다) 

2. "바이너리 머클 트리"

이제 비트코인에서 사용되는 바이너리 머클 트리에 대해서 알아보죠. (디테일은 좀 다릅니다)
일단 바이너리 머클 트리는 누군가는 조금 공간을 더 쓰지만 전체적으로 보면  "공간을 절약" 하기 위해 만들어진 놈입니다. 특히 무엇이 포함되어 있는가? 에 대한 질문에 전체를 가지고 있지 않으면서도 대답을 할 수 있게 해줍니다.

바이너리 머클트리는 구체적인 정보(여기서는 철수100, 영희50등등) 를 가지고, 두개씩 쌍을 이뤄서 축약시키고, 그것을 다시 축약시켜서 하나로 만드는 것을 말합니다. 그림에서 보다시피 2개씩 쌍으로 되어서 바이너리이구요. 반드시 2개씩 쌍을 만들지 않아도 됩니다. (비트코인에서만 2개씩 쌍인 것이구요)

즉 구체적인 정보 + 축약정보의 트리인데요. 결국 공간을 더 낭비하게 됩니다. 잉? 공간을 절약한다매? 
네 비트코인에는 노드들이 다양하게 있는데, 이 구체적인 정보 + 축약정보트리를 모두 가지고 있는 노드에게는 낭비가 맞습니다만, 라이트 노드는 단지 블록헤더만 가질수 있게 되어 전체적으로 보면  획기적인 절약이 됩니다. 

보통 거래를 검증하기 위해서는 위의 그림을 예로들면 정은이가 30을 가지고 있음을 확인해야 하는데요. 블록헤더만 가지고서 그것을 가능하게 합니다. 어떻게 할까요? 새 그림을 보시죠.

실제는 이렇습니다. 위의 그림에서 거래0 이라고만 적혀있지만 데이터가 꽤 많아요. 그 큰 거래데이터를 해쉬하여 해쉬0,1,2,3을 만들고 그것을 또 해쉬 하여 루트해시를 만드는데요.

루트해시만을 가지고 있는 라이트노드는 거래3이 이 블록에 있는지 확인을 받기 위해서 모든것을 가지고 있는 풀노드에게 요청하면 해쉬2와 해시01에 대한 정보만 전달해주는데, 이것을 가지고 순서대로 재계산하여 루트해시를 만들수 있게  되며, 그 루트해시 값이 자신이 가지고 있는 루트해시값과 같으면 "아~ 거래3는 이 블록에 있는게 맞구나" 하고 검증성공하게 합니다.

이게 비트코인에서 사용되는 바이너리 머클 트리인데요. 이제 중요한 포인트가 나옵니다. 위의 "상태전이" 에서 설명했듯이 비트코인 같은 경우는 이 바이너리 머클 트리를 구성하는 내용들이 모두 새로 만들어 집니다. 즉 업데이트(전이) 가 아니라 새롭게 창조됩니다. 따라서 아래와 같은 모습을 띄게 됩니다.

블록마다 새로운 내용을 담고 있습니다. (위의 상태전이에서 설명한 것처럼 상태가 전이되는 방식이 아니라, 새로 생성되는 방식. 아이언맨 100이 아이언맨60이 되는게 아니라, 아이언맨 60이 새로 생성되는 방식)

그럼 상태를 전이 시키려면 어떻게 해야 할까요? 매우 단순합니다. 어찌보면 이게 더 자연스럽구요.

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

(아직까지 "패트리샤" 에 대한 내용은 하나도 안나왔으며, 위의 그림도 그것과는 무관합니다.)

위의 그림을 보면 2개의 블록이 있으며, 두 블록이 동일한 머클 트리를 공유하고 있습니다. 여기서 보시면 트리가 2개씩 뻗어나간게 아니죠? 그래서 일반(non-binary)머클트리라고 칭했으며, 상태전이가 일어나고 있습니다. 즉 블록마다 새로운것만 가지고 있는게 아니라, 공통된것은 공유하고 있으며, 변경(전이) 된 것만 마지막 트리에서는 변경(정확히는 추가)하여 사용하고 있습니다.

이렇기 때문에 공간을 엄청나게 절약할 수 있음을 알수 있습니다. 

(* 다시 말하지만 정확히는 이더리움의 state 저장은 항상 최신본만 유지하는게 아니라, history 또한 유지합니다. 위 그림에서 27이 없어져야 하는데, 사실 일정동안 남겨 두긴 합니다. 이유는 합의가 이루어져서 블록이 만들어 졌다고 해도 확정이 되지 않는 불안 요소가 비트코인이나 이더리움에 있기 때문입니다. bifurcated 이 생기면 state rollback 을 해야 하기 때문. 따라서 시간이 어느정도 흐르면 pruning 과정을 통해 이 history 를 삭제하여 저장 공간을 줄여 줍니다. 실제는 update가 아니라 append 라는 점이죠.) 

4. "패트리샤 트리"

이제 패트리샤 트리에 대한 설명을 시작합니다. 이것도 역시 공간을 절약하기 위함입니다.

인터넷에서 젤 흔히 볼수 있는 그림이며, 이 자체로 아주 명쾌하게 설명해 주고 있습니다.  1번에서 7번까지의 단어를 모두 기록하는 것보다 각 공통되는 부분은 공유하는게 공간을 절약할 수 있게 되겠지요.  r,om, ub, an 이나 ic 처럼 공통되는 부분을 하나의 노드로 공유합니다. 이더리움에서 사용되는 Account 가 State tree, Transactions Tree등에 주렁주렁 달릴텐데...저럴게 매달아 놓으면 중복이 많이 없어지는거죠. 

5. "확장 패트리샤 트리"

이더리움 같은 경우 패트리샤 트리를 좀 다르게 사용하는데요. 이것 역시 그림 그 자체로 이해 할 수 있을 것 입니다.

3개의 특징을 가진 노드가 있습니다.

첫째. 리프노드 

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

둘째. 브랜치노드

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

셋째, 확장노드

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

참고로 이 그림에서는 "머클" 과 "상태전이" 의 모습은 없습니다. 

6. "상태전이 일반 머클 확장 페트리샤 트리" 

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

그림을 다시 봅시다. (다시 언급하지만 정확한 디테일을 담고 있지 않습니다.) 

보다시피 확장 패트리샤 구조를 가지고 있으며, 그 구조에서 각 패트리샤 노드들의 해쉬가 합쳐져서 위쪽을 향하고 있습니다. 즉 머클링을 하고 있는거죠. 비트코인처럼 2개씩 쌍을 지을 필요는 없습니다. 결국 이 머클링이 이어지면 루트해시가 만들어지게 되며, 자식에 어떤 변화가 생기면 루트해시의 값도 바뀝니다. 이 그림에서 "상태전이"가 표현되지 않았지만, 2e: 200원이 이전 블록에서는 2e: 300원이 었으며 300->200으로 "상태전이"가 일어난 후의 모습이라고 생각하시면 될 거 같습니다. 이 상태전이 때문에 새로운 블록의 상태트리의 루트해시 값도 바뀌게 될 겁니다.

* 참고로 이더리움은 1개의 "상태전이 머클 패트리샤 트리(어카운트별 상태(코인 및 코드) 저장용)" 와  2개의 상태전이는 빠진 "머클 패트리샤 트리(트랜잭션,영수증용)" 로 이루어져 있다.

---

이쯤에서 글을 마칠까 합니다. 이 글을 읽고 전반적으로 "아하~~" 라는 느낌을 가질 수 있다면

1) https://steemit.com/cryptocurrency/@nadifsd/merkle-patricia-tree 
2) https://medium.com/coinmonks/data-structure-in-ethereum-episode-3-patricia-trie-b7b0ccddd32f

을 통해서 디테일한 부분은 금방 해소 될 수 있으리라 보여집니다. ^^ 

또한  이더리움은 PBFT 와는 다르게 "Safety" (분산 시스템에서 말하는 Safety vs Liveness)가 약하며 그러기 때문에 history 를 관리해야 하고 pruning 이라는 주제도 나옵니다. 본문에는 모든게 생략되어 있습니다. 다음 여행지를 찾아 떠나세요~~