블록체인에서 자주 언급되는 머클 트리(Merkle Tree)는 무엇인가?

머클 트리(Merkle Tree)

블록체인에서 이루어지는 모든 거래내역은 블록에 저장됩니다. 이렇게 계속 저장을 하게 되면 데이터의 양이 기하급수적으로 증가하게 된다. 이로 인해 비트코인은 머클 트리(Merkle Tree)를 사용하여 저장소 크기를 줄입니다. 그렇다면 머클 트리를 이용해서 어떻게 저장소 크기를 줄일까요?

 

먼저, 블록에 대해 간단하게 알아보구 저장소 크기를 줄이는 방법에 대해 알아보겠습니다.

 

아래 이미지는 블록체인에서 사용되는 블록에 대해 간단하게 표시한 것입니다. 블록의 헤더에는 이전 블록에 대한 해쉬 값, 다음 블록 해쉬 값, 넌스, 머클 트리 루트 해쉬 값 등이 있습니다. 블록의 바디에는 트랜잭션 정보가 있습니다.

 

 

머클 트리 루트는 이번 글에서 알아보고자 한 머클 트리에서 가장 꼭대기(나무로 비유하면 뿌리)에 해당하는 것입니다. 그리고 이 머클 트리 루트는 바로 블록의 헤더에 위치하는 값입니다.

 

머클 트리 루트란?
블록에 있는 모든 트랜잭션 정보를 요약한 해쉬 값으로 블록 헤더에 존재하는 데이터

 

블록에 모든 트랜잭션 정보가 있음에도 머클 트리 루트 해쉬 값을 가지는 이유는 방대한 양의 정보를 요약해서 작은 사이즈로 만들기 위해서입니다.

 

아래 이미지는 머클 트리입니다. L1, L2, L3, L4 가 거래 정보(트랜잭션 정보)라고 하겠습니다. 각 거래 정보는 SHA-256 알고리즘에 의해 해시값이 됩니다. 예를 들어, 두 개의 트랜잭션 정보 Hash 0-0, Hash 0-1 두 개를 합쳐서 해시값 Hash 0을 만드는 것처럼 가장 위에 Top Hash 꼭대기까지 반복적으로 수행합니다. 트리에서 가장 위에 노드인 Top Hash의 값이 바로 머클 트리 루트 값입니다.

 

 

이 머클 트리 루트 값을 이용해서 중간에 거래 정보(트랜잭션 정보)가 변조 되었는지 쉽게 찾을 수 있습니다. 거래 건수(트랜잭션 건수)가 늘어날수록 해당 거래를 찾는 복잡도는 빅오 표기법으로 log2N 입니다.

 

블록 헤드에 있는 머클 트리 루트 값으로 인해서 성능이 좋지 않은 컴퓨터로도 블록 데이터 일부를 받을 수 있고, 특정 거래를 빠르게 찾을 수 있습니다.

References

• 머클 트리 이미지, 위키피디아