머클 트리(Merkle tree)의 개념은 80년대 초 공개 키 암호방식 연구 결과로 잘 알려진 컴퓨터 과학자 랄프 머클(Ralph Merkle)이 제안했습니다.
머클 트리는 일련의 데이터 온전성을 효과적으로 검증하는 데 사용되는 구조입니다. 이는 특별히 피어 투 피어 네트워크 맥락에서 참가자가 정보를 공유하고 독립적으로 검증해야 하는 경우와 관련됩니다.
머클 트리 구조의 핵심에는 해시 함수가 있습니다.
머클 트리는 어떻게 작동하나요?
여러분이 커다란 파일을 다운로드하고 싶다고 해보겠습니다. 여러분은 보통 오픈 소스 소프트웨어를 통해 다운로드하고자 하는 파일의 해시가 개발자에 의해 공개된 것과 일치하는지 확인할 것입니다. 두 해시가 일치한다면 여러분은 컴퓨터에 존재하는 파일이 개발자들의 것과 정확히 일치한다는 것을 알 수 있습니다.
해시가 일치하지 않는다면 문제가 있는 것입니다. 여러분은 소프트웨어로 가장한 악성 파일을 다운로드 했거나, 혹은 파일이 제대로 다운로드 되지 않았을 수 있으며, 때문에 이는 제대로 작동하지 않을 것입니다. 후자의 경우 파일을 다운로드 때까지 기다렸다면 기분이 그리 좋지도 않을 것입니다. 이제 여러분은 해당 과정을 다시 진행하며 오류가 생기지 않기를 바랍니다.
이 문제를 보다 쉽게 해결할 수 있는 방안이 있다면 좋을 텐데, 하고 여러분은 생각할 수 있습니다. 다행히도 우리에게는 머클 트리가 있습니다. 이를 통해 여러분의 파일은 덩어리로 분리될 것입니다. 파일이 50GB였다면, 이는 100개의 조각으로 나뉠 수 있으며, 따라서 크기는 각 0.5GB가 될 것입니다. 이후 파일은 조각별로 다운로드될 것입니다. 이는 기본적으로 여러분이 토렌트에 파일을 공유할 때 진행하는 일입니다.
이 경우 여러분의 자료는머클 루트(Merkle root)라 하는 해시를 제공할 것입니다. 해당 단일 해시는 여러분의 파일을 구성하는 모든 데이터 덩어리를 나타냅니다. 그러나 머클 루트를 사용하면 훨씬 간단하게 데이터를 검증할 수 있습니다.
보다 원활한 이해를 위해 우리가 8GB 파일을 여덟 조각으로 나눠 사용하는 경우를 살펴보도록 하겠습니다. 서로 다른 조각들에A부터H까지 이름을 붙이겠습니다. 이후 각 조각들은 해시 함수를 통과하여 8개의 다른 해시를 제공합니다.
여덟 개 조각들의 해시들을 얻기 위해 이를 해시 함수에 통과시킵니다.
좋습니다. 우리는 보다 실용적인 무언가를 갖게 되었습니다. 우리는 모든 조각의 해시를 갖고 있으며, 하나에 결점이 있는 경우 이를 다른 자료의 것과 비교해 알아낼 수 있습니다. 그렇죠? 가능한 일이지만 이는 무척이나 비효율적입니다. 여러분의 파일이 수 천개의 조각으로 이뤄져 있다면, 이를 모두 해시화하여 결과를 꼼꼼하게 비교할 수 있을까요?
그렇지 않을 것입니다. 대신 우리는 각 해시 쌍을 취해 이를 조합한 다음 함께 해시화할 것입니다. 우리는hA + hB,hC + hD,hE + hF,hG + hH를 해시화할 것입니다. 우리는 네 개의 해시를 갖게 됩니다. 이후 두 개의 해시를 갖기 위해 또 다른 해시화를 진행합니다. 최종적으로 나머지 두 해시를 해시화하여 마스터 해시,머클 루트(또는 루트 해시)를 얻습니다.
해당 구조는 거꾸로 뒤집힌 나무(tree)처럼 보입니다. 아래 열에는 마디와 최종적으로 뿌리(root) 를 생성하기 위한 나뭇잎이 존재합니다.
이제 우리는 다운로드한 파일을 나타내는 머클 루트를 갖게 되었습니다. 우리는 해당 루트 해시를 자료에서 제공하는 해시와 비교할 수 있습니다. 해시가 일치한다면, 완벽하겠죠! 그러나 해시가 서로 다르다면 데이터가 수정되었음을 확신할 수 있습니다. 즉, 하나 혹은 그 이상의 조각이 서로 다른 해시를 생성했다는 것입니다. 따라서 데이터를 아주 조금만 수정하더라도 머클 루트는 완전히 달라지게 됩니다.
다행스럽게도 조각의 결점을 쉽게 확인할 수 있는 방법이 있습니다. 여기서는hE에 결점이 있다고 해보겠습니다. 여러분은 여러분의 피어(peer)에게 머클 루트(hABCD와hEFGH)를 생성하는 두 개의 해시를 요청할 수 있습니다. 여러분의 값hABCD는 다른 이의 것과 일치해야 하는데 종속 트리에 아무런 오류가 없었기 때문입니다. 그러나hEFGH가 일치하지 않을 것이며, 이를 확인해 봐야 한다는 것을 알 수 있습니다. 이제 여러분은hEF와hGH를 요청하여 이를 여러분의 것과 비교합니다.hGH은 괜찮을 것이므로, 문제를 일으킨 장본인은hEF임을 알 수 있습니다. 마지막으로hE와hF해시를 비교합니다. 여러분은hE가 일치하지 않는다는 걸 알 수 있으며, 해당 덩어리를 다시 다운로드할 수 있습니다.
요약하자면 머클 트리는 데이터를 여러 조각으로 나누며 생성되며, 머클 루트를 형성하기 위해 반복적으로 해시화됩니다. 이후 데이터 조각이 잘못된 경우 여러분은 이를 효과적으로 검증할 수 있습니다. 다음 섹션에서 볼 수 있듯 흥미로운 다른 적용 예시도 존재합니다.
머클 트리가 비트코인에 사용되는 이유는 무엇인가요?
머클 트리를 활용하는 몇 가지 경우가 존재하지만, 여기서는 블록체인에서의 중요성에 초점을 맞추도록 하겠습니다. 머클 트리는 비트코인과다른 많은 암호화폐에 필수적인 것입니다. 이는 블록 헤더에서 찾을 수 있는 각 블록의 필수 요소입니다. 트리의 나뭇잎을 얻기 위해 우리는 블록에 포함된 모든 트랜잭션의 트랜잭션 해시(TXID)를 사용합니다.
이러한 경우 머클 루트는 몇 가지 목적을 수행합니다. 이것이 암호화폐 마이닝과 트랜잭션 검증에 어떻게 적용되는지 살펴보도록 하겠습니다.
마이닝
블록체인은 두 가지 요소로 구성되어 있습니다. 하나는 블록 헤더이며, 이는 블록의 메타데이터를 포함하는 고정된 크기 요소입니다. 다른 하나는 사이즈가 가변적인 트랜잭션 목록이며, 보통 헤더보다 더 큰 경향이 있습니다.
마이너는 유효한 블록을 마이닝하기 위해 특정 조건에 부합하는 결괏값을 생성하기 위해 데이터를 반복적으로 해시화해야 합니다. 마이너들은 이를 찾기 위해 수 조 번의 시도를 할 수 있습니다. 각각의 시도마다 마이너들은 블록 헤더의 임의의 숫자(논스, nonce)를 변경합니다. 그러나 블록의 다른 부분은 동일하게 유지됩니다. 수천 개의 트랜잭션이 존재할 수 있으며, 여러분은 매번 이를 해시화해야 합니다.
머클 루트는 이러한 과정을 크게 간소화시킵니다. 마이닝을 시작할 때, 여러분은 머클 트리에 포함하고 구성하려는 모든 트랜잭션을 정렬합니다. 여러분은 루트 해시(32바이트) 결과를 블록 헤더에 집어넣습니다. 이후, 블록을 마이닝할 때는 전체 블록 대신 블록 헤더만 해시화하면 됩니다.
이는 쉽게 변경할 수 없는 것이기 때문에 가능한 일입니다. 여러분은 모든 블록 트랜잭션을 효과적으로 압축된 형식으로 요약할 수 있습니다. 유효한 블록 헤더나 이후에 변경한 트랜잭션 목록을 발견할 수는 없는데, 그렇게 되면 머클 루트가 변경될 것이기 때문입니다. 다른 노드에 블록이 전송되면, 이들은 트랜잭션 목록에서 루트를 계산합니다. 이것이 헤더에 있는 것과 일치하지 않는다면, 노드는 블록을 거부합니다.
검증
우리가 사용할 수 있는 머클 루트의 또 다른 흥미로운 특성이 있습니다. 이는 라이트 클라이언트(블록체인의 전체 사본을 보유하지 않은 노드)와 관련됩니다. 여러분이 한정된 자원을 가진 기기로 노드를 운영할 경우, 모든 블록의 트랜잭션을 다운로드하고 해시화하고 싶지 않을 수 있습니다. 그 대신 여러분은 단순히 풀 노드로부터 여러분의 트랜잭션이 특정 블록 안에 있음을 입증하는 증거인 머클 증명을 요청할 수 있습니다. 이를 보통 단순화된 결제 검증(Simplified Payment Verification) 또는 SPV라 하며, 사토시 나카모토는 이를 비트코인 백서에 상세히 기술했습니다.
hD를 확인하려면 빨간색으로 표시된 해시만 있으면 됩니다.
TXID가hD인 누군가의 트랜잭션 정보를 알고 싶다고 해보겠습니다. 우리에게hC가 제공될 경우, 우리는hCD를 작업할 수 있습니다. 다음으로hABCD를 계산하기 위해hAB가 필요합니다. 마지막으로hEFGH를 통해 블록 헤더와 일치하는 머클 루트 결과를 확인할 수 있습니다. 만약 일치한다면, 이는 해당 트랜잭션이 블록에 포함되어 있었음을 증명합니다. 다른 데이터를 가지고 동일한 해시를 생성하기란 거의 불가능합니다.
위의 예시에서 우리는 단 세 번만 해시화를 진행했습니다. 머클 증명이 없다면 일곱 번을 진행해야 했을 것입니다. 오늘날의 블록에는 수천 개의 트랜잭션이 포함되기 때문에, 머클 증명을 사용하면 상당한 시간과 컴퓨터 자원이 절약됩니다.
마치며
머클 트리는 다양한 컴퓨터 과학 애플리케이션에서 상당히 유용한 것으로 증명되었으며, 우리가 살펴본 것처럼 블록체인에서 무척이나 중요한 것입니다. 분산화된 시스템에서 머클 트리를 사용하면 불필요한 데이터로 네트워크를 혼잡하게 하지 않으며 간단히 정보를 검증할 수 있습니다.
머클 트리(그리고 머클 루트)가 없다면 비트코인과 다른 암호화폐블록은 오늘날처럼 압축될 수 없을 것입니다. 라이트 클라이언트는 개인 정보 보호 및 보안 측면에 부족함이 있지만, 사용자는 머클 증명을 사용해 최소한의 간접 비용으로 트랜잭션이 블록에 포함되어 있었는지 확인할 수 있습니다.
