머클 트리의 개념은 80년대 초 공개 키 암호방식 연구 결과로 잘 알려진 컴퓨터 과학자 랄프 머클이 제안했다.
머클 트리는 일련의 데이터 온전성을 효과적으로 검증하는데 사용되는 구조이다.
이는 특별히 P2P 네트워크 맥락에서 참가자가 정보를 공유하고 독립적으로 검증해야 하는 경우와 관련된다.
머클 트리 구조의 핵심에는 해시 함수가 있다.
머클 트리의 동작 원리
커다란 파일을 다운로드하려고 한다고 가정하자.
오픈 소스 소프트웨어를 통해, 다운로드하고자 하는 파일의 해시가 개발자에 의해 공개된 것과 일치하는지 확인해야 한다.
두 해시가 일치한다면, 컴퓨터에 존재하는 파일이 개발자들의 것과 정확히 일치한다고 말할 수 있다.
만약 해시가 일치하지 않는다면, 무언가 문제가 있는 것이다.
소프트웨어로 가장한 악성 파일을 다운로드 했거나, 혹은 파일이 제대로 다운로드 되지 않았을 수 있으며, 때문에 이는 제대로 동작하지 않는다.
다행히, 머클 트리를 이용하면 보다 효율적으로 이 문제를 해결할 수 있다.
1. 머클 트리로 파일을 덩어리로 분리한다.
파일이 50GB였다면, 100개의 조각으로 나뉠 수 있다. 이렇게 조각낸다면 한 조각의 크기는 각 0.5GB가 된다.
이후 파일은 조각별로 다운로드된다.
이런 형태의 다운로드는 토렌트에 파일을 공유할 때도 사용된다.
2. 이렇게 파일을 다운로드 하면, 이 자료는 머클 루트(Merkel Root)라는 해시를 제공한다.
이 단일 해시는 파일을 구성하는 모든 데이터 덩어리를 나타낸다.
그리고 머클 루트를 사용하면, 훨씬 간단하게 데이터를 검증할 수 있다.
보다 원활한 이해를 위해 8GB 파일을 여덟 조각으로 나눠 사용하는 경우를 살펴보자.
서로 다른 조각들에 A부터 H까지 이름을 붙여보자. 이후 각 조각들은 해시 함수를 통과하여 8개의 다른 해시를 제공한다.
여덟 개 조각들의 해시들을 얻기 위해 이를 해시 함수에 통과시킨다.
이렇게 생성된 8개의 해시를 다시 2개씩 묶어 해싱한다.
hA + hB, hC + hD, hE + hF, hG + hH를 해싱하면, 네 개의 해시 hAB, hCD, hEF, hGH를 가지게 된다.
이 방식을 반복해 마지막 하나의 해시, 머클 루트(또는 루트 해시)를 얻을 수 있다.
이 방식대로 생성한 머클 루트를 이용하면, 다운로드한 파일이 나타내는 머클 루트와 자료를 제공하는 사람이 함께 담아 보낸 머클 루트를 비교할 수 있다.
두 머클 루트의 해시값이 동일하다면, 모든 파일을 안전하게 전달받았다고 할 수 있다.
만약 두 해시값이 다르다면, 데이터가 위변조되었을 수 있다고 확신할 수 있다.
만약 파일을 전송받는 과정에서 데이터에 변경이 생겼다면, 모든 파일 조각을 처음부터 다시 다운로드해야 할까?
머클 트리를 사용하면, 데이터에 변경이 일어난 파일 조각을 찾고, 그 파일만 새롭게 다운로드 받을 수 있다.
위 그림에서 hE에 결점이 있다고 가정하자.
한 부분에 결점이 있으므로, 파일을 다운로드 한 뒤 생성한 머클 루트와, 전달받은 머클 루트의 해시값이 다를 것이다.
이 경우, 파일을 전달한 피어(Peer)에게 머클 루트를 생성하는 두 개의 해시(hABCD & hEFGH )를 요청할 수 있다.
전달받은 두 개의 해시값 중, hEFGH에 문제가 있다는 것을 확인할 수 있고, 이런 방식을 반복해 hE의 데이터에 변경이 있었다는 것을 확인할 수 있다.
마지막으로 hE를 해시한 파일 조각만 다시 다운로드하면, 파일 전송을 보다 효율적으로 할 수 있게 된다.
요약:
머클 트리는 데이터를 여러 조각으로 나눈 후 여러 조각을 합쳐 해싱, 그렇게 생성된 해시값들을 합쳐 다시 해싱하는 과정을 반복한다.
그리고 최상단에는 머클루트라는 최종 해시값이 생성되고 이를 활용하여 데이터 위변조를 판별할 수 있다.
머클 트리는 데이터의 무결성을 증명하는데 사용되기에 비트코인을 비롯한 많은 암호화폐에 필수적인 요소이다.
따라서 일반적인 블록체인의 블록 헤더에는 머클 루트 값이 필수적으로 들어간다.
머클 트리의 잎(Leaf: 트리의 종단)을 얻기 위해, 블록에 포함된 모든 트랜잭션의 트랜잭션 해시(TXID)를 사용한다.
