머클 트리와 머클 루트란 무엇인가요?

머클 트리는 데이터를 해시 쌍으로 구성하고, 이를 위로 결합해 최종적으로 하나의 해시값인 머클 루트가 전체 데이터셋을 대표하도록 만드는 암호학적 데이터 구조입니다.

머클 루트는 블록체인 네트워크가 전체 블록을 다운로드하지 않고도 특정 트랜잭션이 블록에 포함되어 있는지 검증할 수 있게 합니다. 이때 사용되는 압축된 증명 방식인 머클 증명은 트랜잭션 수가 늘어나도 로그 단위로만 커집니다.

비트코인은 모든 블록 헤더에 머클 루트를 포함합니다. 이를 통해 라이트 클라이언트는 전체 블록체인이 아니라 블록 헤더만으로도 트랜잭션을 검증할 수 있습니다.

이더리움은 계정 잔액과 스마트 컨트랙트 상태를 저장하기 위해 더 복잡한 구조인 머클 패트리샤 트라이를 사용합니다. 이를 통해 라이트 클라이언트와 레이어2 롤업을 위한 상태 증명이 가능해집니다.

소개

머클 트리는 블록체인 시스템이 대규모 환경에서도 효율적이고 검증 가능하게 작동하도록 만드는 핵심 개념 중 하나입니다. 머클 트리는 전체 데이터셋을 하나의 암호학적 지문으로 요약하면서도, 특정 트랜잭션이나 정보가 그 안에 포함되어 있음을 증명할 수 있게 합니다. 머클 트리가 블록체인 설계에서 왜 중요한지 이해하기 위해, 작동 방식과 여러 네트워크에서의 활용 방식, 그리고 향후 버클 트리와 같은 새로운 구조가 어떻게 이를 개선할 수 있는지 살펴보겠습니다.

머클 트리의 작동 방식

머클 트리는 1979년 이 개념을 특허로 등록한 컴퓨터 과학자 랄프 머클의 이름을 따서 명명되었습니다. 머클 트리는 대규모 데이터셋의 무결성을 효율적으로 요약하고 검증하기 위해 사용되는 데이터 구조입니다. 블록체인에서 머클 트리는 수천 개의 트랜잭션을 블록 헤더에 저장되는 하나의 압축된 값으로 압축합니다.

트리는 암호학적 해시 함수를 사용해 아래에서 위로 구성됩니다. 각 리프 노드는 트랜잭션과 같은 단일 데이터 조각의 해시값을 포함합니다. 이후 이러한 리프 해시들은 쌍을 이루고, 두 자식 해시를 이어 붙인 뒤 다시 해싱해 각 쌍의 해시를 계산합니다. 이 과정은 위쪽으로 한 층씩 반복되며, 최종적으로 맨 위에 하나의 해시값만 남게 됩니다. 이것이 머클 루트입니다.

각 부모 노드는 두 자식 노드 모두에 의존하기 때문에, 하나의 리프에 변화가 생기면 그 변화가 위쪽으로 연쇄적으로 반영되어 완전히 다른 머클 루트가 생성됩니다. 이러한 특성 덕분에 머클 트리는 데이터 변조를 감지하는 데 효과적인 도구가 됩니다. 두 데이터셋의 머클 루트가 같다면, 극히 높은 확률로 두 데이터셋은 동일하다고 볼 수 있습니다.

머클 루트

머클 루트는 고정된 크기의 해시값입니다. 블록체인 애플리케이션에서는 일반적으로 32바이트, 즉 256비트 크기를 가집니다. 머클 루트는 전체 데이터셋을 대표하는 디지털 지문 역할을 합니다. 대부분의 블록체인 네트워크에서 블록 헤더는 타임스탬프, 이전 블록 해시 등 다른 메타데이터와 함께 머클 루트를 포함합니다. 이를 통해 헤더는 작게 유지하면서도, 블록 안에 포함된 전체 트랜잭션 집합에 암호학적으로 커밋할 수 있습니다.

간단한 예시로, 8GB 파일을 여덟 조각으로 나눈다고 가정해 보겠습니다. 각 조각을 A부터 H까지라고 부릅니다. 그런 다음 각 조각을 해시 함수에 통과시키면 여덟 개의 서로 다른 해시값이 나옵니다.

A-H 조각과 각각의 해시값
여덟 개의 조각 각각을 해시 함수에 통과시켜 해시값을 얻습니다.

모든 조각의 해시값이 있다면, 어느 하나가 잘못되었을 때 원본의 해시값과 비교해 확인할 수 있을 것입니다. 가능은 하지만, 이 방식은 매우 비효율적일 수 있습니다. 파일이 수천 개의 조각으로 이루어져 있다면, 모든 조각을 해싱하고 그 결과를 하나하나 꼼꼼히 비교해야 할까요?

머클 루트는 더 우아한 해결책을 제공합니다. 각 해시값을 쌍으로 묶고 결합한 뒤, 다시 함께 해싱합니다. 그러면 hA + hB, hC + hD, hE + hF, hG + hH에 해당하는 해시값을 얻고, 총 네 개의 해시값이 남게 됩니다.

머클 루트의 첫 번째 및 두 번째 해시 라운드
이 구조는 거꾸로 뒤집힌 나무처럼 보입니다. 맨 아래 줄에는 리프가 있고, 이 리프들이 결합되어 노드를 만들며, 최종적으로 루트가 생성됩니다.

이후 또 한 번 해싱을 거치면 hABCD와 hEFGH, 두 개의 해시값이 남습니다. 마지막으로 이 두 값을 해싱하면 최상위 해시값, 즉 머클 루트 또는 루트 해시인 hABCDEFGH가 만들어집니다.

머클 증명과 검증

머클 트리의 가장 실용적인 특징 중 하나는 전체 데이터셋을 공개하지 않고도 특정 데이터가 그 데이터셋에 포함되어 있음을 증명할 수 있다는 점입니다. 이를 머클 증명이라고 합니다. 특정 트랜잭션이 블록에 포함되어 있는지 검증하려면, 라이트 클라이언트는 해당 트랜잭션 자체, 루트까지 이어지는 경로상의 소수의 형제 해시값, 그리고 블록 헤더에 있는 머클 루트만 있으면 됩니다. 검증자는 경로를 따라 해시를 다시 계산한 뒤, 그 결과가 알려진 루트와 일치하는지 확인합니다. 일치한다면 해당 트랜잭션이 블록에 포함되어 있음이 수학적으로 증명됩니다.

머클 검증 예시, 세 번의 해시 라운드
hD를 확인하려면 빨간색으로 표시된 해시값만 필요합니다.

TXID가 hD인 트랜잭션을 검증하려는 상황을 보겠습니다. hC가 제공되면 hCD를 계산할 수 있습니다. 그런 다음 hAB를 사용해 hABCD를 계산합니다. 마지막으로 hEFGH를 이용해 계산된 머클 루트가 블록 헤더의 머클 루트와 일치하는지 확인합니다. 일치한다면 해당 트랜잭션이 블록에 포함되었다는 증거가 됩니다. 서로 다른 데이터로 동일한 해시값을 만들어내는 것은 사실상 거의 불가능합니다.

위 예시에서는 세 번만 해싱하면 됩니다. 머클 증명이 없다면 일곱 번의 해싱이 필요합니다. 오늘날 블록에는 수천 개의 트랜잭션이 포함되기 때문에, 머클 증명은 많은 시간과 컴퓨팅 자원을 절약해 줍니다.

증명 크기는 리프 수에 대해 로그 단위로 증가합니다. 예를 들어 트랜잭션이 100만 개 있는 경우, 깊이 20의 이진 트리가 되며 약 20개의 해시값만 필요합니다. 이는 대략 640바이트에 해당합니다. 이 덕분에 단순 결제 검증, 즉 SPV 클라이언트라고도 불리는 라이트 노드는 전체 블록체인을 다운로드하지 않고도 트랜잭션을 검증할 수 있습니다. 전체 블록체인을 다운로드하려면 수백 기가바이트의 데이터가 필요할 수 있습니다.

블록체인 네트워크에서의 머클 트리

비트코인과 트랜잭션 검증

비트코인에서는 각 블록 헤더가 해당 블록 안의 모든 트랜잭션에 커밋하는 32바이트 머클 루트를 포함합니다. 비트코인 채굴자는 자신이 포함한 트랜잭션들로 머클 트리를 구성하고, 그 결과로 나온 루트를 작업증명 솔루션과 함께 블록 헤더에 삽입합니다. 이 설계 덕분에 일반적으로 약 80바이트 크기인 블록 헤더만으로도, 다른 트랜잭션을 확인하지 않고 특정 트랜잭션이 블록에 포함되었는지 검증할 수 있습니다.

비트코인은 MAST, 즉 머클화 추상 구문 트리 제안에서도 머클 트리를 사용합니다. MAST는 비트코인 스크립트의 복잡한 지출 조건을 머클 트리 형태로 표현할 수 있게 합니다. 실제로 실행된 스크립트 분기만 공개하면 되므로, 사용되지 않은 조건은 비공개로 유지되고 트랜잭션 크기도 줄어듭니다.

이더리움과 상태 증명

이더리움은 머클 패트리샤 트라이라고 불리는 더 정교한 변형 구조를 사용합니다. 이는 계정 잔액, 컨트랙트 코드, 스토리지 데이터를 저장하는 16진, 즉 16방향 트리 구조입니다. 비트코인 트랜잭션에 사용되는 단순한 이진 머클 트리와 달리, 머클 패트리샤 트라이는 상태의 빈번한 업데이트를 지원하도록 설계되었습니다. 계정 잔액이 변경되면 전체 트리를 다시 구성할 필요 없이, 해당 리프에서 루트까지의 경로만 다시 계산하면 됩니다.

머클 패트리샤 트라이에서 생성된 상태 증명은 이더리움 라이트 클라이언트와 레이어2 롤업이 풀 노드를 실행하지 않고도 계정 잔액과 컨트랙트 스토리지를 검증할 수 있게 합니다. 이러한 증명은 한 체인의 이벤트를 다른 체인에서 검증해야 하는 크로스체인 브리지에도 필수적입니다.

한계와 향후 발전

머클 트리는 효율적인 검증을 제공하지만, 증명 크기는 여전히 데이터셋 크기에 따라 로그 단위로 증가합니다. 이더리움의 경우 상태가 커질수록 블록 위트니스, 즉 블록 검증에 필요한 증명이 수 메가바이트에 이를 수 있습니다. 이는 스테이트리스 클라이언트에게 확장성 문제를 야기합니다. 스테이트리스 클라이언트는 모든 블록에 대해 이러한 증명을 전달받고 검증해야 하기 때문입니다.

버클 트리는 이에 대한 잠재적 해결책을 제공합니다. 버클 트리는 기존 해싱 대신 다항식 기반 벡터 커밋먼트인 KZG, 즉 Kate-Zaverucha-Goldberg 커밋먼트를 사용합니다. 각 노드 아래에 많은 자식을 묶는 방식, 예를 들어 분기 계수 256을 사용함으로써, 버클 트리는 데이터셋이 아무리 커져도 거의 일정한 크기의 증명을 생성할 수 있습니다. 그 크기는 대략 170바이트 수준입니다. 이더리움은 버클 트리 통합을 적극적으로 개발하고 있으며, 향후 업그레이드에서 배포될 것으로 예상됩니다. 이러한 전환은 라이트 클라이언트의 데이터 부담을 크게 줄이고, 전반적인 네트워크 확장성을 개선할 수 있습니다.

FAQ

머클 트리를 쉽게 설명하면 무엇인가요?

머클 트리는 하나의 작은 정보 조각, 즉 머클 루트가 대규모 데이터 집합을 대표할 수 있도록 데이터를 구성하는 방식입니다. 데이터 쌍을 반복적으로 해싱해 하나의 해시값만 남기는 방식으로 작동합니다. 이를 통해 모든 항목을 하나하나 확인하지 않고도 특정 항목이 그 집합에 포함되어 있는지 검증할 수 있습니다.

머클 루트란 무엇인가요?

머클 루트는 머클 트리 맨 위에 있는 단일 해시값입니다. 아래에 있는 모든 데이터를 대표하는 압축된 디지털 지문 역할을 합니다. 블록체인 네트워크에서는 머클 루트가 블록 헤더에 저장되며, 해당 블록의 모든 트랜잭션에 커밋합니다. 이를 통해 특정 트랜잭션이 블록의 일부인지 효율적으로 검증할 수 있습니다.

머클 증명은 어떻게 작동하나요?

머클 증명은 특정 트랜잭션과 함께, 그 트랜잭션에서 머클 루트까지의 경로를 다시 계산하는 데 필요한 최소한의 형제 해시값을 제공합니다. 검증자는 트랜잭션을 해싱하고, 제공된 형제 해시값들과 올바른 순서로 결합한 뒤, 최종 결과가 블록 헤더에 있는 알려진 머클 루트와 일치하는지 확인합니다. 일치한다면 해당 트랜잭션이 포함되어 있음이 증명됩니다.

머클 트리가 블록체인에서 중요한 이유는 무엇인가요?

머클 트리는 블록체인 네트워크가 블록 헤더와 전체 트랜잭션 데이터를 분리할 수 있게 합니다. 라이트 클라이언트는 블록당 약 80바이트 수준의 블록 헤더만 다운로드하고도, 압축된 머클 증명을 사용해 특정 트랜잭션이 포함되었는지 검증할 수 있습니다. 머클 트리가 없다면 트랜잭션 검증을 위해 전체 블록 또는 전체 체인을 다운로드해야 합니다.

머클 트리와 버클 트리의 차이는 무엇인가요?

둘 다 데이터 포함 여부를 증명하는 데 사용되는 암호학적 누산기이지만, 사용하는 수학적 방식이 다릅니다. 머클 트리는 해시 함수를 사용하며, 증명 크기가 데이터셋 크기에 따라 로그 단위로 증가합니다. 즉 O(log n)입니다. 반면 버클 트리는 다항식 기반 KZG 커밋먼트를 사용하며, 데이터셋 크기와 관계없이 수백 바이트 수준의 거의 일정한 크기의 증명을 생성합니다. 따라서 대규모 블록체인 상태 증명에 더 적합합니다.

마무리

머클 트리는 블록체인 아키텍처의 핵심 구성 요소입니다. 신뢰 없는 환경에서도 대규모 검증을 가능하게 합니다. 전체 트랜잭션 블록을 하나의 32바이트 해시로 압축함으로써, 참여자들은 모든 데이터를 다운로드하지 않고도 데이터를 검증할 수 있습니다. 이 원리는 비트코인 SPV 월렛부터 이더리움 상태 증명, 크로스체인 브리지에 이르기까지 다양한 시스템의 기반이 됩니다. 블록체인 네트워크가 계속 성장함에 따라, 버클 트리와 같은 새로운 암호학적 구조가 결국 머클 트리를 보완하거나 대체할 수 있습니다. 그러나 효율적인 해시 기반 데이터 무결성이라는 근본 개념은 앞으로도 오랫동안 분산 시스템의 핵심 빌딩 블록으로 남을 가능성이 높습니다.