이미 많은 글들을 통해 이더리움이 머클 패트리샤 트리를 사용하는 것을 다들 아실 것입니다. 간단히 요약하자면 블록의 헤더를 구성하는 3개의 머클 패트리샤 트리의 루트 해시( 상태루트, 트렌젝션루트, 영수증 루트)로 헤더만으로도 블록이 위조되었는지 검증이 가능하다 정도일것입니다.
오늘은 머클 패트리샤 트리를 어떻게 생성하고 관리하는지 알아보려고 합니다.
우선 머클 패트리샤 트리의 정의를 이더리움 wiki에서 확인해 봅니다.
머클 패트리샤 트리는 보안성이 증명된 데이터 구조로서 (키,값) 형태로 엮인 모든 값이 저장가능한 자료구조이고, 이더리움에서는 키, 값으로서 문자열만을 사용한다.
동일한 키,값 쌍은 마지막 바이트까지 정확히 동일하기 때문에 동일한 루트해시를 가진다
https://github.com/ethereum/wiki/wiki/Patricia-Tree#modified-merkle-patricia-trie-specification-also-merkle-patricia-tree
이더리움의 키/값 쌍의 종류는 다음과 같습니다.
- 상태 트라이의 [키/값] 쌍: [주소 / 계정(논스, 잔고, 스토리지 루트, 코드해시)], 네트워크 상에 하나의 트라이만 존재. (스토리지 트라이는 계약관련 정보를 다루고 있어서, 다음 기회에 좀더 명확하게 따로 보는게 좋겠네요)
- 트렌젝션 트라이: 블록상의 트렌젝션 번호/ 트렌젝션
- 영수증 트라이: 블록상의 영수증 번호/ 트렌젝션
아무튼 저런 정보들이 담기는데, 우리는 string/string만 다룬다고 했으니
저값들을 어떤식으로든 string으로 변환해서 저장할거라 가정만 해두고,
소스코드의 trie패키지를 분석해보겠습니다.
워낙 당연한 말씀이지만 트라이도 트리이기 때문에 노드가 있습니다. 이더리움 트라이의 노드는 크게 3가지 타입인데요
- shortNode는 키/값쌍 하나를 가진 형태입니다.
- full은 자식노드를 17개까지 가지는 형태입니다.
- value node는 데이터 그자체만을 가진 노드입니다
shortNode는 트라이에 노드가 딱하나만 있을때 사용하고, 이후부터는 fullNode를 사용합니다. value node는 full node의 맨끝에 leaf로서 붙는 값 자체이기 때문에 사실은 2가지 타입이라고 봐도 무방하죠
위 그림에서 보다시피 노드는 full/short중 하나일테니 가장 복잡한
FullNode의 17개의 자식노드가 모두 full노드 라고 생각하고 시작해 볼께요.
node들은 자식 노드들을 구분하기 위한 인덱스로 아래와 같은 정의를 사용합니다.
var indices = []string{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f", "[17]"}
스트링으로 자식 노드의 인덱스를 표현하게 되면 장점이 생기는데요, 바로 "노드간의 연결선에 문자를 표현할수 있다"는 것이고요. 값이 16진수를 모두 표현할수 있으니 우리가 아까 이더리움에서 사용했던 문자열 키값을 표현할수 있게 되는 것입니다.
문자열키를 트리의 간선을 이용해서 표현한것을 "PATH"라고 하는데, 우리는 PATH에서 주로
계정의 주소나 트렌젝션/영수증의 번호를 표현하니까, 16개의 값으로 가능한것이죠.
만약 0x12e/0x8282가 키/값 쌍이라면 아래와 같이 표현될것입니다.
짜잔, 이제 우리는 트라이를 이해할수 있을것 같습니다.
이렇게 트라이를 생성한 후에 자녀들의 해시를 계산하는 형태를 반복하면
결국 루트 해시가 나오겠네요.
사실 니블(4bit)단위의 오퍼레이션에 대한 설명도 빠졌고, 해시를 어떻게 계산하는지도 다뤄야 하지만, 위 그림의 트라이의 구조를 알고 있다면 충분히 쉽게 풀어나갈수 있는 부분이라 이번글에서는 제맘대로 건너뜁니다.ㅎㅎ
*지극히 개인적으로 이더리움 주석 한글화 프로젝트를 진행하고 있습니다.
https://github.com/NAKsir-melody/go-ethereum *
주석을 한글화 하다보니 bmt라고해서 바이너리 머클트리 패키지도 있더라구요. bmt패키지는 swarm에서만 사용하는것으로 파악됩니다. 그러니까 이더리움 코어에서는 우선 머클 패트리샤 트리만 사용한다고 보면 되겠네요.