• Home
  • About
  • Notes
  • Projects
<- Back to notes
notesalgorithms9/25/2025

머클 트리: 데이터 무결성을 위한 이진 트리 구조

효율적인 데이터 검증과 무결성 확인을 위한 암호학적 해시 트리

머클 트리란?

머클 트리(Merkle Tree)는 완전 이진 트리 구조로, 각 리프 노드는 데이터 블록의 해시를 포함하고, 각 내부 노드는 두 자식 노드의 해시를 연결(concatenate)하여 해싱한 값을 포함한다.

핵심 개념:

  • 리프 노드: 실제 데이터의 해시값
  • 내부 노드: 두 자식 노드 해시의 연결 + 해싱 결과
  • 루트: 전체 데이터 집합을 대표하는 단일 해시값
        Root Hash
       /         \
   Hash(A,B)   Hash(C,D)
    /    \      /    \
  Hash(A) Hash(B) Hash(C) Hash(D)
    |      |      |      |
   Data A Data B Data C Data D

기본 구조와 생성 과정

1. 리프 노드 생성

// 각 데이터를 개별적으로 해싱
let data = vec!["tx1", "tx2", "tx3", "tx4"];
let leaf_hashes: Vec<Vec<u8>> = data
    .iter()
    .map(|tx| sha256(tx.as_bytes()))
    .collect();

2. 트리 구성 (Bottom-up)

// 현재 레벨의 해시들을 두 개씩 묶어서 부모 해시 생성
fn build_parent_level(current_level: &[Vec<u8>]) -> Vec<Vec<u8>> {
    let mut parent_level = Vec::new();

    for i in (0..current_level.len()).step_by(2) {
        let left = &current_level[i];
        let right = if i + 1 < current_level.len() {
            &current_level[i + 1]
        } else {
            &current_level[i]  // 홀수 개면 마지막 노드를 복제
        };

        let parent_hash = sha256(&[left.clone(), right.clone()].concat());
        parent_level.push(parent_hash);
    }

    parent_level
}

3. 루트까지 반복

let mut current_level = leaf_hashes;

while current_level.len() > 1 {
    current_level = build_parent_level(&current_level);
}

let merkle_root = current_level[0].clone();

주요 특성과 장점

효율적인 검증

전체 데이터 없이도 특정 데이터 포함 여부 확인 가능:

  • 전체 데이터 크기: N개 요소
  • 검증에 필요한 해시 개수: O(log N)개

데이터 무결성 보장

루트 해시만으로 전체 데이터 집합의 무결성 확인:

  • 단일 데이터라도 변경되면 루트 해시가 완전히 달라짐
  • 연쇄적 해시 변화로 인한 강력한 변조 탐지

증분 검증

특정 데이터가 트리에 포함되어 있는지 증명 가능:

  • 머클 증명(Merkle Proof)을 통한 부분 검증
  • 전체 트리를 다운로드하지 않고도 검증 가능

머클 증명(Merkle Proof)

특정 데이터가 머클 트리에 포함되어 있음을 증명하는 방법이다.

증명 과정

목표: Data B가 트리에 포함되어 있음을 증명

        Root Hash
       /         \
   Hash(A,B)   Hash(C,D)  <- Hash(C,D) 필요
    /    \      /    \
  Hash(A) Hash(B) Hash(C) Hash(D)
    |      |      |      |
   Data A [Data B] Data C Data D
     ^
  Hash(A) 필요

필요한 정보:

  1. Hash(A) - B의 형제 노드
  2. Hash(C,D) - 부모의 형제 서브트리 루트
  3. 알려진 Root Hash

검증 과정

fn verify_merkle_proof(
    data: &[u8],
    proof: &[Vec<u8>],  // [Hash(A), Hash(C,D)]
    root: &[u8]
) -> bool {
    let mut current_hash = sha256(data);  // Hash(B)

    for (i, sibling_hash) in proof.iter().enumerate() {
        // 현재 노드가 왼쪽인지 오른쪽인지 결정
        if is_left_child(i) {
            current_hash = sha256(&[current_hash, sibling_hash.clone()].concat());
        } else {
            current_hash = sha256(&[sibling_hash.clone(), current_hash].concat());
        }
    }

    current_hash == root
}

실제 활용 사례

블록체인에서의 활용

트랜잭션 무결성 확인:

// 블록 헤더에는 머클 루트만 저장
struct BlockHeader {
    previous_hash: Vec<u8>,
    merkle_root: Vec<u8>,      // 모든 트랜잭션의 머클 루트
    timestamp: u64,
    nonce: u64,
}

// 전체 트랜잭션 데이터 없이도 특정 트랜잭션 검증 가능
fn verify_transaction_in_block(
    tx: &Transaction,
    merkle_proof: &[Vec<u8>],
    block_header: &BlockHeader
) -> bool {
    let tx_hash = tx.get_id();
    verify_merkle_proof(tx_hash, merkle_proof, &block_header.merkle_root)
}

장점:

  • 라이트 노드는 전체 블록 데이터를 다운로드하지 않아도 됨
  • 특정 트랜잭션의 포함 여부만 O(log N) 시간에 확인 가능

Git에서의 활용

버전 관리 시스템에서 변경사항 추적:

Commit Hash = Hash(Tree Hash + Parent + Metadata)
Tree Hash = Merkle Root of all files/directories
  • 파일 하나만 바뀌어도 전체 트리 해시 변경
  • 디렉토리 구조의 무결성 보장
  • 효율적인 차이점(diff) 계산

파일 시스템에서의 활용

대용량 파일의 무결성 검증:

// 파일을 청크 단위로 나누어 머클 트리 구성
fn create_file_merkle_tree(file_path: &str, chunk_size: usize) -> MerkleTree {
    let file_data = read_file(file_path);
    let chunks: Vec<&[u8]> = file_data.chunks(chunk_size).collect();

    let chunk_hashes: Vec<Vec<u8>> = chunks
        .iter()
        .map(|chunk| sha256(chunk))
        .collect();

    MerkleTree::build(&chunk_hashes)
}

구현 시 고려사항

홀수 개 노드 처리

트리를 완전 이진 트리로 만들기 위한 방법:

// 방법 1: 마지막 노드 복제
if nodes.len() % 2 == 1 {
    nodes.push(nodes.last().unwrap().clone());
}

// 방법 2: 빈 해시 추가
if nodes.len() % 2 == 1 {
    nodes.push(vec![0; 32]); // 빈 해시
}

메모리 효율성

// 레벨별 체인 구조로 메모리 사용량 최적화
struct MerkleLevelChain {
    nodes: Vec<Vec<u8>>,
    next_level: Option<Box<MerkleLevelChain>>,
}

해시 함수 선택

일반적으로 사용되는 해시 함수:

  • SHA-256: 비트코인, 가장 널리 사용
  • SHA-3: 차세대 표준
  • Blake2: 빠른 성능이 필요한 경우

성능 최적화

// 병렬 처리로 대용량 데이터 처리 성능 향상
use rayon::prelude::*;

fn parallel_hash_level(nodes: &[Vec<u8>]) -> Vec<Vec<u8>> {
    nodes
        .par_chunks(2)
        .map(|pair| {
            let left = &pair[0];
            let right = if pair.len() > 1 { &pair[1] } else { &pair[0] };
            sha256(&[left.clone(), right.clone()].concat())
        })
        .collect()
}

보안 고려사항

Second Preimage Attack 방지

문제: 리프 노드와 내부 노드의 구분이 모호할 경우 공격 가능

해결책: 노드 타입별 접두사 추가

fn hash_leaf(data: &[u8]) -> Vec<u8> {
    let mut input = vec![0x00]; // 리프 노드 접두사
    input.extend_from_slice(data);
    sha256(&input)
}

fn hash_internal(left: &[u8], right: &[u8]) -> Vec<u8> {
    let mut input = vec![0x01]; // 내부 노드 접두사
    input.extend_from_slice(left);
    input.extend_from_slice(right);
    sha256(&input)
}

트리 깊이 제한

문제: 극도로 불균형한 트리로 인한 DoS 공격

해결책: 최대 깊이 제한 및 균형잡힌 트리 구성

변형과 확장

머클 패트리샤 트리 (Merkle Patricia Trie)

이더리움에서 사용하는 구조:

  • 키-값 저장에 최적화
  • 접두사 압축으로 공간 효율성 향상
  • 상태 트리, 트랜잭션 트리, 영수증 트리에 활용

머클 마운틴 레인지 (MMR)

추가 전용(append-only) 데이터에 최적화:

  • 새 데이터 추가 시 기존 노드 변경 최소화
  • 로그 시스템이나 블록체인에 적합

스파스 머클 트리 (Sparse Merkle Tree)

큰 키 공간을 효율적으로 처리:

  • 대부분이 비어있는 트리 구조
  • 영지식 증명 시스템에서 활용

장단점 분석

장점

  • 효율적 검증: O(log N) 복잡도로 부분 검증 가능
  • 무결성 보장: 강력한 변조 탐지 능력
  • 저장 효율: 루트 해시만으로 전체 데이터 대표 가능
  • 병렬 처리: 트리 구성과 검증을 병렬화 가능

단점

  • 구조 의존성: 트리 구조가 바뀌면 모든 해시 재계산 필요
  • 순서 민감성: 데이터 순서가 바뀌면 루트 해시 변경
  • 추가 오버헤드: 해시 저장을 위한 추가 공간 필요

결론

머클 트리는 효율적인 데이터 무결성 검증을 제공하는 강력한 자료구조다. 특히 분산 시스템과 암호화폐에서 전체 데이터 세트를 다운로드하지 않고도 특정 데이터의 포함 여부를 확인할 수 있는 능력이 핵심 가치다.

블록체인에서는 라이트 노드가 전체 블록 데이터 없이도 트랜잭션을 검증할 수 있게 하고, Git에서는 파일 시스템의 변경사항을 효율적으로 추적할 수 있게 한다.

핵심은 O(log N)의 효율성으로 O(1)의 루트 해시만 가지고도 전체 데이터 집합의 무결성을 보장한다는 점이다.