머클 트리(Merkle tree)는 이진 해시 트리라고도 하며, 컴퓨터 과학 애플리케이션에서 사용되는 데이터 구조입니다. 블록체인 기술의 맥락에서 머클 트리는 블록체인 데이터를 보다 효율적이고 안전하게 인코딩하는 데 사용됩니다.^[1]

개요

비트코인의 블록체인에서 트랜잭션 블록은 알고리즘을 거쳐 해시를 생성합니다. 해시는 주어진 데이터 세트가 원래 트랜잭션 세트와 동일한지 확인하는 데 사용할 수 있는 숫자와 문자의 문자열입니다. 각 트랜잭션은 해싱되고, 각 트랜잭션 쌍은 연결되어 함께 해싱되는 과정을 전체 블록에 대한 해시가 하나가 될 때까지 반복합니다. 이 구조는 트리를 닮았으며, 하단 행의 해시를 "리프(leaves)", 중간 해시를 "브랜치(branches)", 상단의 해시를 "루트(root)"라고 합니다.

주어진 블록의 머클 루트는 헤더에 저장됩니다. 머클 트리를 통해 사용자는 전체 블록체인을 다운로드하지 않고도 특정 트랜잭션을 확인할 수 있습니다. 예를 들어, 특정 트랜잭션이 블록에 포함되어 있는지 확인하려면 해당 트랜잭션의 해시에 대해 네트워크에 쿼리하면 모든 것이 설명되었는지 확인하는 데 필요한 해시가 반환됩니다.^[1][4][7]

머클 트리의 주요 목적은 데이터의 무결성을 확인하는 것입니다. 머클 트리는 블록체인 기술의 보안과 효율성을 보장하는 데 기본적입니다. 블록체인 기술의 맥락에서 다음과 같은 중요한 목적을 수행합니다.

• 효율적이고 안전한 데이터 검증: 머클 트리를 사용하면 대규모 데이터 세트를 효율적이고 안전하게 검증할 수 있습니다. 이는 데이터 양이 상당히 크고 지속적으로 증가할 수 있는 블록체인 기술에서 매우 중요합니다.
• 트랜잭션 검증: 예를 들어 비트코인 블록체인에서 머클 트리를 사용하면 사용자가 전체 블록체인을 다운로드하지 않고도 특정 트랜잭션을 확인할 수 있습니다. 이는 트랜잭션 확인을 위해 블록체인의 하위 집합만 다운로드하는 경량 SPV(Simplified Payment Verification) 클라이언트에 특히 유용합니다.
• 데이터 무결성 및 일관성: 블록 헤더에 저장된 머클 루트는 블록의 모든 트랜잭션의 무결성 및 일관성을 보장하는 데 도움이 됩니다. 단일 트랜잭션이라도 변경되면 다른 머클 루트가 생성됩니다.
• 이중 지불 방지: 각 트랜잭션 블록이 이전 블록을 참조하도록 함으로써 머클 트리는 사용자가 동일한 돈을 두 번 이상 사용할 수 있는 디지털 현금 체계의 잠재적인 결함인 이중 지불을 방지하는 데 도움이 됩니다.

역사

머클 트리 개념은 1987년 랄프 머클(Ralph Merkle)이 발표한 "기존 암호화 함수 기반의 디지털 서명(A Digital Signature Based on a Conventional Encryption Function)"이라는 논문에서 처음 제안되었습니다. 그는 또한 암호화 해싱을 발명했습니다. 머클 트리 기술은 1989년에 특허를 받았습니다.

비트코인 발명 이전에는 소프트웨어 개발에서 암호화가 데이터를 보호하는 데 사용되었습니다. 공개 키 암호화로 유명한 머클은 피어 투 피어 네트워크에서 데이터 무결성을 확인하기 위해 머클 트리를 도입한 후 새로운 검증 방식으로 해싱 개념을 도입했습니다. 머클 트리는 현재 피어 투 피어 네트워크, 분산 시스템 및 블록체인 기술을 포함한 다양한 애플리케이션에서 사용됩니다. 이는 비트코인 및 이더리움과 같은 암호화폐 운영의 기본입니다.^[1][5][9]

머클 트리 유형

각 부모 노드가 가질 수 있는 자식 노드 수에 따라 다양한 유형의 머클 트리가 있습니다. 몇 가지 예는 다음과 같습니다.^[8]

• 이진 머클 트리: 이는 가장 간단하고 일반적인 유형의 머클 트리로, 각 부모 노드에는 두 개의 자식 노드만 있습니다. 이는 파일 또는 트랜잭션과 같은 대규모 데이터 세트를 효율적으로 요약하고 확인하는 데 사용됩니다.
• 패트리샤 트리: 이는 이더리움에서 스마트 계약에 대한 트랜잭션을 처리하는 데 사용되는 더 복잡한 유형의 머클 트리입니다. 패트리샤 트리는 부모당 더 많은 자식 노드를 가질 수 있으므로 더 복잡한 작업에 적합합니다.

사용 사례

머클 트리는 특히 데이터 무결성 검사가 필요한 시스템에서 광범위한 애플리케이션을 가지고 있습니다. 다음은 몇 가지 주목할 만한 애플리케이션이며 머클 트리의 애플리케이션은 다른 많은 영역으로 확장됩니다.^[2][7][10]

• 암호화폐: 머클 트리는 비트코인 및 이더리움과 같은 암호화폐 운영의 기본입니다. 이는 블록에서 트랜잭션을 효율적으로 저장하고 확인하는 데 사용됩니다.
• 분산 시스템: 피어 투 피어 네트워크와 같은 분산 시스템은 머클 트리를 사용하여 다른 피어로부터 수신된 데이터 블록이 손상되지 않고 변경되지 않은 상태로 수신되었는지 확인합니다.
• 파일 시스템: IPFS(InterPlanetary File System), Btrfs 및 ZFS와 같은 파일 시스템은 머클 트리를 사용하여 데이터 손상을 방지합니다.
• 데이터베이스: Dynamo DB 및 Apache Cassandra와 같은 확장 가능한 데이터베이스는 머클 트리를 사용합니다.
• 인증서 투명성: 인증 기관은 인증서 투명성 확인을 위해 머클 트리를 사용합니다.
• 디지털 서명: 머클 트리는 디지털 서명에 사용됩니다.
• 데이터 무결성 검사: 불일치를 확인해야 하는 모든 시스템은 머클 트리를 사용할 수 있습니다.
• 주식 거래: 일일 주식 거래 활동을 추적해야 하는 애플리케이션은 머클 트리가 유용할 수 있는 완벽한 예입니다.

예

머클 트리 구현의 몇 가지 예는 다음과 같습니다.^[7]

• IPFS: IPFS는 분산 파일 시스템에서 파일을 저장하고 공유하기 위한 피어 투 피어 프로토콜입니다. IPFS는 머클 트리를 사용하여 파일과 디렉토리를 머클 DAG(방향성 비순환 그래프)로 나타냅니다. DAG의 각 노드는 고유한 해시로 식별되며 다른 노드에 대한 링크는 데이터의 일부로 인코딩됩니다. 이를 통해 네트워크 전체에서 데이터의 효율적인 중복 제거, 검증 및 동기화가 가능합니다.
• ZFS: ZFS는 데이터 무결성, 압축, 암호화 및 스냅샷과 같은 기능을 제공하는 파일 시스템입니다. ZFS는 머클 트리를 사용하여 파일 이름, 크기, 권한 및 체크섬과 같은 파일 시스템의 메타데이터를 저장합니다. 각 데이터 블록에는 부모 블록에 저장된 체크섬이 있어 루트 블록에서 끝나는 트리를 형성합니다. 이를 통해 데이터 손상을 감지하고 수정할 수 있을 뿐만 아니라 스냅샷 및 백업의 일관성을 확인할 수 있습니다.
• 이더리움: 이더리움은 스마트 계약 및 분산 애플리케이션을 지원하는 블록체인 플랫폼입니다. 이더리움은 머클 트리를 사용하여 계정, 잔액, 트랜잭션 및 계약 코드와 같은 네트워크 상태를 저장합니다. 이더리움은 부모 노드당 두 개 이상의 자식 노드를 가질 수 있고 키-값 쌍을 효율적으로 저장할 수 있는 패트리샤 트리라는 머클 트리의 변형을 사용합니다. 패트리샤 트리를 사용하면 데이터의 존재 및 부재에 대한 빠른 증명과 경량 클라이언트 프로토콜이 가능합니다.