자신이 회사의 주인으로서 한 건물의 일부를 임대하여 사용한다고 해봅시다.
회사의 규모가 커지고 직원이 늘어도 공간을 최대한 활용하면서 늘어난 인원들을 수용하는 것이 목표입니다.
첫 번째 회사(Array List)는 자신의 직원들이 반드시 모두 한곳에 모여 있어야 한다는 원칙하에 사무실이 한 층에 모여 있습니다. 이 경우 회사가 성장해서 공간이 좁아지면 더 이상 새로운 직원을 뽑을 수 없습니다. 건물의 인원이 가득 찰수록 붙어 있는 사무실 한 층을 통째로 빌리기 어렵기 때문이죠.
반면 두 번째 회사(Linked List)에서는 한 회사의 사무실들이 서로 떨어져 있습니다. 덕분에 직원이 늘어나면 건물에서 비어 있는 사무실을 아무 곳이나 임대해서 들어갈 수 있으므로, 큰 걱정이 없습니다.
위의 두 가지 회사는 각각 배열(Array)과 연결 리스트(Linked List)라는 자료 구조(Data structure)를 비유적으로 표현한 것입니다.
이처럼 구현하고자 하는 목표에 따라 자료구조라는 것이 미칠 수 있는 영향력은 매우 크며, 프로그램의 크기가 커질 수록 이는 더욱 커집니다.
(위의 비유가 블록체인 및 아래 기술할 트리 구조들과 구조상으로 유사한 비유는 아닙니다. ‘자료구조'라는 것의 중요성을 역설하기 위한 비유 정도로 받아들여 주시면 될 것 같습니다.)
이어서 설명할 머클트리와 MPT 모두 그러한 자료 구조의 일종입니다. 따라서 블록체인을 이해하고, 보다 효율적이고 효과적인 블록체인 기술을 고안하는 데에 있어서도 앞으로 설명할 개념들을 정확히 이해하고 숙지하는 것이 중요할 것입니다.
머클트리란 무엇인가?
블록체인이란 분산화된 거래 장부로써, 거래에 대한 정보가 모든 참여자에게 투명성 있게 공유됩니다.
그러한 블록체인 자체의 구조 상 거래의 진위 여부를 확인하는 절차가 중요한데, 이를 빠르고 정확하게 하기 위해 사용되는 자료 구조 중 하나가 바로 머클트리(Merkle Tree)입니다.
머클트리란?
머클트리를 사용하는 이유를 한마디로 말하자면, ‘데이터의 무결성을 간편하고 효과적으로 검증하기 위해서' 입니다.
- 최초의 트랜잭션(데이터)를 해시값(SHA256)으로 변환하고,
- 인접한 노드 2개를 한 쌍으로 묶어서 합친 후 이를 다시 해시값으로 암호화한다.
- 마지막 하나(머클 루트)가 남을 때까지 위 과정을 반복한다.
위 과정을 하나씩 풀어서 알아 보겠습니다.
머클트리의 구현 과정
트랜잭션들을 리프(leaf)노드로 나열 & 해시값 생성
우선 “Mj gave Chooble $1,000”와 같은 거래 기록(트랜잭션)들을 쭉 나열합니다. 트랜잭션은 더이상 나눌 수 없는 최소 단위이기 때문에 최하단에 위치한 영역입니다.
그러한 트랜잭션들을 해시 함수를 통해 해시값으로 생성합니다. 해시 함수는 단방향 함수로서, 입력 값에 조그마한 변화만 있어도 출력값의 거의 모든 것이 바뀌게 됩니다.
예컨대 위와 같이 “$1,000”에서 “$1000”으로 고작 “,” 한 글자가 바뀌었음에도 출력값의 모든 부분이 바뀌었습니다. 이 때문에 조금의 변화만 있더라도 누구나 이 값에 변형이 있다는 것을 쉽게 알 수 있습니다.
해시 합치기
이후 해싱된 값들을 각각 2개씩 묶어 다시 해싱하는 과정을 반복합니다.
결국 마지막 해시값 하나만 남게 되며, 이 값을 머클 루트(Merkle root)라고 합니다. 머클 루트가 트랜잭션의 요약본 역할을 하는 셈입니다.
만약 머클 트리에서 트랜잭션이 하나라도 변형된다면, 머클 루트는 전혀 다른 값을 가지게 되므로 데이터가 위변조 혹은 변형되었음을 확신할 수 있습니다.
이러한 현상을 쇄도 효과(Avalanche effect)라고 합니다.
머클트리가 필요한 이유
블록체인 상의 노드는 풀 노드와 라이트 노드로 나뉩니다.
풀 노드(full node)는 제네시스 블록부터 현재 시점의 블록이 연결된 체인 전체를 다운로드해 유지하는 노드입니다. 반면 라이트 노드들은 자세한 거래 정보들은 가지지 않고 머클 루트의 값만 가지고 있습니다. 다른 말로는 SPV(Simple Payment Verification) 노드라고도 합니다.
블록체인 네트워크에 참여하기 위해 모두가 풀 노드를 운영할 필요는 없습니다. 블록체인 상의 모든 정보를 다운받고, 업데이트하고 여러 기능들을 수행하기 위해서는 매우 좋은 성능의 기기들이 필요할 것입니다.
라이트 노드가 가진 트랜잭션들의 요약본(머클 루트)의 크기는 항상 32바이트로 일정합니다. 따라서 머클 루트를 이용해 트랜잭션의 검증이 가능해진다면 검증에 필요한 용량이 대폭 줄어들 것이고, 이로 인해 저사양 PC 및 스마트폰 등 다양한 디바이스들의 참여가 가능해지기에 블록체인 네트워크가 더욱 견고해지고 활성화될 수 있습니다.
실제 머클 루트를 이용한 블록 검증 과정
트랜잭션 hD가 이 블록 안에 포함되어 있는지를 머클트리를 사용해 검증해봅시다.
라이트 노드인 검증자는 검증하고자 하는 hD에 대한 정보와 머클 루트만을 알고 있으므로, 우선 hD와 한 쌍인 hC에 대한 정보를 풀노드에게 요청하여 가져옵니다.
이들을 합쳐 hCD라는 해시값을 만들고, 마찬가지로 hAB를 가져와서 hABCD를 만들고 hEFGH를 가져와서 hABCDEFGH를 만듭니다.
‘hABCDEFGH’의 값이 실제 블록 헤더에 저장된 머클 루트의 값과 같다면, 해당 트랜잭션(hD)이 블록에 포함되어 있다는 것을 의미합니다. 머클 트리가 없다면 7번 진행해야 했을 것을 3번만에 검증한 것입니다.
이 경우 해싱이 되는 과정이 총 3번이었으므로 3번의 경로만 찾아가면 되었습니다.
머클트리는 트랜잭션을 두 개씩 묶어서 올라가므로, 경로를 찾는 경우의 수가 N건의 거래에 대해 log2(N)으로 늘어나게 됩니다. 위와 같이 8개의 거래가 아니라 2048개의 거래라고 하더라도 경로를 찾아가는 연산을 11번만 거치면 특정 거래에 대한 검증을 쉽게 할 수 있습니다.
따라서 거래의 위변조를 쉽고 빠르게 알 수 있으므로 이를 방지할 수 있습니다.
이더리움의 머클패트리샤 트리
한편 이더리움에서는 보다 효율적인 관리를 위해 단순 이진 머클트리가 아닌 ‘머클 패트리샤 트리(Merkle Patricia Tree)’라는 자료구조를 사용합니다.
우선 보다 명확한 이해를 위해, 위에서 서술한 ‘머클 트리'는 ‘바이너리(binary) 머클 트리'라고 말해야 하며 이더리움의 ‘머클 패트리샤 트리'는 ‘상태전이 일반 머클 확장 패트리샤 트리'라고 말해야 합니다.
용어가 좀 긴데, 하나씩 뜯어 보겠습니다.
- 상태 전이
기존 블록체인과 바이너리 머클트리에서는 트랜잭션을 쌓으며 값을 새로운 값으로 교체하되, 수정하지 않습니다. 비트코인의 경우가 그러한데, 100BTC를 가지고 있던 A가 0BTC를 가지고 있던 B에게 50BTC를 주었을때, 비트코인 거래에서는 A의 100BTC의 내용은 수정되지 않고 그대로 있고 A의 잔액 50BTC와 B의 잔액 50BTC의 거래 내역을 저장하는 방식입니다.
이더리움의 경우 상태 전이를 통해 값을 수정(update)하는 방식으로 저장하여 공간을 절약하는 효과가 발생합니다. 물론 모든 값을 즉시 업데이트하는 것은 아니고, 기존 거래 내역을 저장하고 있다가 블록에 이상이 없다고 판단 시 업데이트를 하는 것입니다.
2. 상태 전이 일반(non-binary) 머클 트리
위에서 설명한 상태 전이의 특성을 반영하여, 변경되지 않는 공통의 값들은 공유하며 변경된 것만 추가하여 트리를 만드는 방식입니다.
위 그림의 두 개의 블록은 서로 같은 머클 트리를 공유하고 있습니다. 상태 전이가 일어나고 있으며, 공통된 값들을 서로 공유하고 새로운 값만 마지막 트리에서 추가하여 사용하고 있습니다. 이로인해 공간을 대폭 절약하는 효과가 발생합니다.
3. 확장 패트리샤 트리
위와 같이 각 단어의 공통 부분을 공유하여 공간을 절약하는 방법을 패트리샤 트리라고 합니다.
이더리움은 패트리샤 트리를 좀 더 확장하여 사용합니다.
리프 노드(Leaf Node)는 트리 가지의 끝에서 키 값에 대한 value를 가짐과 동시에, 마지막 주소값(key)을 저장하고 있어 공간을 절약하는 효과를 발생시킵니다(패트리샤 트리 구조)
확장 노드(Extension Node)는 다음 노드를 가리키고, 브랜치 노드는 16개의 16진수 값과 value를 가지며 여기서 가지치기가 시작됩니다.
즉, 그림에선 이전 블록이 나타나지 않았지만 이더리움의 블록은 이전 블록으로부터 상태 전이가 일어난 결과이며, 머클링하는 노드들이 비트코인처럼 굳이 2개씩 쌍을 지을 필요가 없으므로 상태 전이 일반(non-binary) 머클트리입니다. 또한 위와 같은 확장 패트리샤 구조를 가지고 있으므로, 이더리움은 ‘상태 전이 일반 머클 확장 패트리샤 트리' 구조를 가진다고 할 수 있습니다.
지금까지 머클트리와 머클 패트리샤 트리 구조에 대해 알아 보았습니다.
코드 단까지 들여다 보아야 알 수 있는 디테일한 부분까지 글에 다 담지는 못했지만, 두 자료구조가 어떻게 구성되고, 사용되는지에 대한 개념적 이해에 도움이 되셨으면 하는 바람입니다.
긴 글 읽어 주셔서 감사합니다.
.
.
.
참고 문헌
권민재 | Researcher of CURG | kkmj4034@gmail.com
