머클 트리(Merkle tree), 이진 해시 트리(binary hash tree)라고도 알려져 있으며, 컴퓨터 과학 응용 프로그램에서 사용되는 데이터 구조입니다. 블록체인 기술의 맥락에서 머클 트리는 블록체인 데이터를 보다 효율적이고 안전하게 인코딩하는 데 사용됩니다.^[1]

개요

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

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

머클 트리의 주요 목적은 데이터 무결성을 검증하는 것입니다. 머클 트리는 블록체인 기술의 보안 및 효율성을 보장하는 데 기본적입니다. 블록체인 기술의 맥락에서 여러 가지 중요한 목적을 제공합니다.

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

역사

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

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

머클 트리의 종류

각 부모 노드가 가질 수 있는 자식 노드의 수에 따라 여러 유형의 머클 트리가 있습니다.^[8]

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

사용 사례

머클 트리는 데이터 무결성 검사가 필요한 시스템에서 광범위하게 응용됩니다. 다음은 주목할 만한 응용 프로그램이며, 머클 트리의 응용 프로그램은 다른 많은 영역으로도 확장됩니다.^[2][7][10]

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

예시

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

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