Merkle tree, Merkle Patricia Tree

Hong·2022년 11월 6일

🌲 Merkle tree(머클트리)란?

머클트리는 여러 데이터에 단계적으로 해시함수를 적용하여 결국에 하나의 해시값으로 나타내는 데이터 구조다.
쉽게 말해서, 여러 개의 데이터를 하나의 해시값으로 만드는 데이터 구조다. 해시트리랑 같은 의미로 쓰인다.
이렇게 여러 데이터를 모아 만들어진 하나의 최종 해시값을 "Merkle Root"라고 한다.

🔗 블록체인에서의 머클트리

블록체인에서 머클트리는 블록체인의 무결성을 보장한다.
맨 아래의 원본 데이터가 변경되면 순차적으로 위의 해시값이 바뀌게 되며 결국 맨 위에 존재하는 머클 루트 해시값도 바뀔 것이기 때문이다.
이러한 원리를 통해서 우리는 Merkle Root 해시값만 보더라도 트리 아래의 트랜잭션 데이터가 변경되었는지, 손상되었는지 간편하게 파악할 수 있다.

실제로 어떻게 사용되는지 그림으로 알아보자

맨위를 보면 블록전체의 데이터를 하나의 헤시값으로 나타내고 있고 Header부분에는 이전 블록의 해시값, 버전, 난이도, 트랜잭션 데이터 머클루트, 블록생성시간, 논스 등에 대한 데이터가 들어간다.

Header부분에 들어가는 Merkle Root가 위에서 설명한 머클트리로 만들어진 해시값이다.
결국 블록의 모든 transaction이 블록 Header에 들어가고 이 Header의 정보들이 최종적으로 Block Hash값으로 나타나게되니 이전 블록의 transaction정보가 변경되면 모든 블록의 hash값이 변화하게 될 것이다(쇄도효과라고 한다, avalanche effect). 이러한 방법으로 비트코인은 이전 transaction에 대한 무결성을 증명한다.

하나의 Transaction 데이터가 블록 전역에 영향을 주게되는 경우

🐕 Merkle Patricia Tree(머클 패트리샤 트리)

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

사실 풀어쓰면
"상태전이" + "머클트리" + "확장패트리샤 트리"
= "상태전이 일반 머클 확장 패트리샤 트리" 이다.

왜그런지 알아보자

비트코인 같은 경우는 각 블록마다 고유한 블록 해쉬 값과 머클 루트 값이 존재한다
즉 n-1번째 비트코인 블록의 머클트리와 n번째 비트코인 블록의 머클루트 값이 완전히 다른 것이다

상태전이 트리(non-binary)

하지만 이더리움은 이더리움 네트워크 전체를 나타내는 머클트리가 따로 존재한다.
n-1번째 이더리움 블록의 머클트리와 n번째 이더리움 블록의 머클트리가 완전히 다른 것이 아니고 n-1번째에서 n번째로 넘어갈 때 상태변화가 일어나서 업데이트 된다.
이러한 방식으로 작성된 머클트리의 데이터는 블록체인 네트워크 전체를 보았을 때 데이터의 저장용량이 훨씬 가벼워 진다.
그림을 살펴보자, 그림의 Account 175는 175223번째 블록에서 175224 블록으로 넘어가며 자식노드의 데이터 중 27에서 45로 변화가 일어났다. 이러한 변화는 머클트리의 특성에 따라 위의 노드에 변화를 일으킨다(빨간색으로 동그라미 친 부분이 변화됨). 하지만 옆에 존재하는 다른 노드들에는 영향을 미치지 않는다.
이더리움은 이러한 방식을 적용해서 변화가 일어나지 않는 노드들은 건들지 않고 상태변화가 일어나는 노드들만 업데이트 해준다. 때문에 비트코인의 전체 블록데이터는 100GB가 넘는 반면 이더리움은 10GB정도 된다고 한다.

패트리샤 트리

위에 있는 1번에서 7번까지의 단어를 모두 기록하는 것보다 각 공통되는 부분은 공유하는게 메모리를 절약할 수 있는 효율적인 방법이다.
이더리움에서 사용되는 Account에 State Tree, Transaction Tree등이 이어붙여 질 텐데 공유하는 Account를 기준으로 패트리샤 트리를 만들어 놓으면 메모리가 절약된다.