비트코인의 머클트리(Merkle Tree)

이번 글의 선수지식으로는 해쉬함수, 이진트리(Binary Tree), 그리고 비트코인의 UTXO, SPV Nodes, transaction에 대한 이해가 필요합니다.

비트코인의 UTXO란: up-to-date-items.tistory.com/91

비트코인의 SPV Nodes: up-to-date-items.tistory.com/93

 

비트코인은 각 블록들이 연결되어있는 형태이고 각 블록들은 Block Header에 여러정보를 가지고 있습니다.

그 정보들 중 하나는 Merkle Root로 현재 블록이 가지고 있는 transaction의 요약본이라고 보시면 됩니다.

머클루트를 만들기 위해서는 머클트리를 차근차근 만들어나가면 됩니다.

 

그럼 바로 머클트리가 어떻게 이루어지는지 알아보겠습니다.

4개의 transaction으로 머클트리를 만들어보겠습니다.
(아래 이미지는 해당 링크에서 가져온 그림입니다. medium.com/@garry.passarella/merkle-trees-and-their-use-in-blockchain-transaction-validation-13eafdab6f82)

4개의 transactions를 각각 T1, T2, T3, T4라고 하겠습니다.

Hash1, Hash2, Hash3, Hash4는 각각 T1, T2, T3, T4를 해쉬함수에 넣은 결과값입니다. (머클트리에서 이용되는 해쉬함수는 SHA256입니다.)

Hash5는 (Hash1 + Hash2)의 값을 해쉬함수에 넣은 값입니다. 마찬가지로 Hash6도 (Hash3 + Hash4)의 값을 해쉬함수에 넣은 값입니다.

예를들어 해쉬함수를 f(x)라고 한다면 Hash5 = f(Hash1 + Hash2)입니다.

이제 마지막으로 (Hash5 + Hash6)의 값을 해쉬함수에 넣으면 그 결과 값이 바로 그림에서 HashPointer, 즉, 머클트리의 루트가 됩니다.

 

** 만약 transaction의 개수가 짝수가 아닌 홀수이면 어떻게 될까요?

그 경우에는 제일 마지막 transaction이 복제가 됩니다. 예를들어 transaction이 3개가 있다고 한다면 T3가 복제가 되어서 

Hash6 = f(Hash3 + Hash3)이 됩니다.

 

다시 머클트리의 루트로 돌아와서 머클트리는 Bottom-Up방식으로 계속 SHA256으로 해쉬를 적용하기 때문에 SHA256의 특성상 머클루트역시 32byte로 이루어집니다. 즉, block내의 transactions들을 32byte으로 요약시킬 수 있습니다.

 

이 머클루트는 SPV 노드가 어떠한 transaction이 해당 블록에 포함되어있는지를 확인할 때 사용하게 됩니다.

Full Node는 자신이 모든 블록에 대한 정보를 가지고 있어 누군가의 도움 없이 자신이 직접 확인해볼 수 있지만 SPV 노드는 경량노드로 block header만 갖고 있기 때문에 Full Node의 도움과 Merkle Root를 활용해 확인할 수 있습니다.

위 그림의 머클루트를 100번 블록의 머클루트라고 가정해봅시다.

이제 어떤 SPV노드는 100번 블록에 T3이 포함되는지 궁금합니다. (위에서 말했지만 SPV노드는 block header만 갖고 있기 때문에 100번 블록에 T3가 있는지 없는지 확인하려면 머클루트를 이용해야 합니다.)

SPV 노드는 Full Node에게 Hash4와 Hash5를 요청합니다.
그리고 T3와 Hash4로 Hash6를 만들고
Hash5와 Hash6으로 Merkle Root를 만들고나서 이 값과 100번 블록 block header에 있는 Merkle Root가 일치한다면
T3가 100번 블록에 포함되어 있다는걸 알 수 있습니다.