머클트리(merkle tree)란?

머클트리란?

머클트리(Merkle Tree) 혹은 '해시트리(Hash Tree)'라는 구조는 Ralph Merkle이라는 사람이 1979년에 만들어 낸 개념입니다. 다른 트리 알고리즘과는 다르게 머클트리의 목적은 빠른 검색이 아니라 데이터의 간편하고 확실한 인증을 위해 사용합니다. 머클트리의 최상위 부모노드(혹은 루트)는 머클루트라 부르며 블록체인의 원소역할을 수행하는 블록에서 저장된 트랜잭션들의 해시트리라 볼 수 있습니다.

머클트리는 데이터의 간편하고 확실한 인증을 위해서 SHA-256 암호화 기술(해시함수)를 사용하고 있습니다. 자세한 내용은 아래 머클트리 그림과 같이 설명하겠습니다.

SHA-256 암호화 (해시함수)란?

SHA-256은 암호화 기술로서 복호화가 되지 않는 단방향 암호화 기술입니다. 암호화된 결과는 16진수로 어떠한 수를 암호화 하더라고 결과의 크기는 64자입니다.  http://www.convertstring.com/ko/Hash/SHA256 해당 사이트에 들어가 abcd 라는 값을 SHA256 암호화 하면 88D4266FD4E6338D13B845FCF289579D209C897823B9217DA3E161936F031589 라는 값이 나오게 됩니다. 만약 abcd가 아닌 aacd라는 값을 SHA256으로 암호화 하면 전혀 다른 값이 나오게 됩니다.  이와 같이 입력된 값이 1개라도 다를 경우, 결과는 전혀 유추할 수 없습니다. 또한 입력할 글자의 수에 상관없이 결과의 크기는 64자입니다.

머클트리 구조

위 그림에서는 해시함수 64자를 전부 입력하기 힘들어 길이가 4인 값으로 대체했습니다. (원래는 4자가 아닌 64자입니다.)

블록체인에서는 먼저 각 트랜잭션(이하 TX1, TX2, ..., TXn)들을 SHA-256으로 암호화해 64자의 해시결과를 만들어 냅니다. 다음 각 인접한 노드들을 합한 다음, 다시 SHA-256으로 암호화해 해시결과를 만들어 냅니다. 이러한 과정을 단 1개의 해시가 나올때까지 반복합니다.

한마디로 수많은 거래내용들을 해시함수를 통해 압축하고 인접한 노드끼리 더한다음 다시 압축 과 같은 과정을 반복해 나갑니다. 모든 결과 값은 이전 출력들을 해시함수를 거쳤기 때문에 입력이 하나라도 달라지면 최종결과인 머클루트가 달라지게 됩니다.

이러한 특성으로 블록에서 거래변조가 일어났는지를 확인할 수 있으며, 거래내용이 아무리 길어도 해시함수를 거친 결과는 64자이므로 블록의 용량을 획기적으로 줄일 수 있게 됩니다.

머클트리를 사용한 검증법

지금부터 비트코인을 예를 들어 검증하는 방법을 설명하겠습니다. 머클트리 검증에 앞서 풀 노드와 라이트 노드라는 개념이 나오는데 풀노드는 제네시스 블록부터 지금까지의 블록 즉, 블록체인 전체를 가지고 유지하는 노드입니다. 라이트 노드는 블록체인 전체가 아닌 몇몇 블록만 가지고 있으며 풀노드에게서 필요한 정보를 받아서 유지하는 노드입니다.

만약 아래의 그림과 같이 라이트 노드에서 가장 마지막 값인 1e3a 해시값과 머클루트인 af3d 해시값만 가지고 있다고 가정하고 1e3a라는 거래내역이 진짜인지 확인을 어떻게 할까요?

방법은 풀노드로 부터 검은 네모박스인 43bc, 143c, 89fe의 정보를 받아 해시 함수에 차례대로 넣어 계산을 진행합니다. 아래의 그림과 같이 검은 네모박스를 알게되면 인접한 노드끼리 더한 뒤 해쉬를 통해 상대값을 알게되어 머클트리를 진행해 나갈 수 있게 됩니다. 이와 같은 경로를 머클경로라 합니다.

만약 검은 네모박스가 아닌 파란 네모박스를 알게 된다면 해시경로를 진행해 나갈 수 없어 머클루트가 진짜인지 알 수 없게 됩니다. 이러한 과정을 통해 도출된 결과가 머클루트인 af3d의 값과 동일하지 않다면 1e3a 해시값은 거짓거래로 판명이 납니다.

요약

• 머클트리는 SHA-256 암호화 (해시함수)를 사용
• 머클트리를 이용하면 빠르게 데이터 검증을 할 수 있고 트리 저장 용량도 줄일 수 있음
• 머클트리는 라이트 노드에서 거래를 검증하기 위해 사용됨