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

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

머클 트리란?

머클 트리(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)
}

장점: