머클 트리(Merkle Tree)

머클 트리(Merkle Tree)는 블록체인 및 분산 시스템에서 데이터 무결성을 검증하는 데 사용되는 해시 트리(Hash Tree)의 한 종류입니다.

1. 머클 트리 개념

머클 트리는 리프(leaf) 노드에 원본 데이터의 해시 값을 저장하고, 상위 노드(parent node)는 하위 두 개 노드의 해시 값을 다시 해시한 값을 저장하는 방식으로 구성됩니다. 최상위 루트 노드(Merkle Root)는 전체 데이터 세트의 해시를 대표합니다.

2. 머클 트리 구조

        Merkle Root
        /         \
    HashAB       HashCD
    /     \       /     \
 HashA  HashB  HashC  HashD

• 리프 노드: 개별 데이터 블록의 해시 값
• 중간 노드: 하위 두 노드의 해시 값을 결합한 해시 값
• 루트 노드(Merkle Root): 전체 데이터 무결성을 대표하는 최상위 해시 값

3. 머클 트리의 특징

• 효율적인 검증: 루트 해시 값만 검증하면 전체 데이터의 무결성을 확인할 수 있습니다.
• 빠른 검색 및 검증: 특정 데이터 블록의 무결성을 확인할 때 전체 데이터를 다운로드하지 않고도 검증할 수 있습니다.
• 분산 시스템에서 활용: 비트코인, 이더리움 등 블록체인에서 트랜잭션 검증에 사용됩니다.

4. 머클 트리 사용 사례

1. 블록체인: 트랜잭션 무결성 확인 및 블록 검증
2. P2P 네트워크: 비트토렌트 같은 파일 공유 시스템에서 데이터 검증
3. 데이터 무결성 검증: 분산 저장 시스템에서 데이터 변경 감지

5. 머클 트리 구현 코드

다음은 머클 트리(Merkle Tree)의 간단한 Python 구현 코드입니다. 이 코드에서는 SHA-256 해시 함수를 사용하여 머클 트리를 생성하고, 루트 해시 값을 계산하는 과정을 보여줍니다. 또한 특정 데이터가 트리에 포함되어 있는지 검증하는 기능도 포함합니다.

🔹 코드 설명:

1. hash_data: 데이터를 SHA-256 해시로 변환합니다.
2. build_tree: 리프 노드에서 시작해 재귀적으로 머클 트리를 생성하고, 최종적으로 루트 해시를 반환합니다.
3. get_root: 머클 루트 해시 값을 반환합니다.
4. verify_proof: 특정 데이터가 머클 트리에 존재하는지 확인합니다.

import hashlib

class MerkleTree:
    def __init__(self, data_list):
        """
        머클 트리를 초기화하고 루트 해시를 생성합니다.
        :param data_list: 원본 데이터 리스트 (리프 노드)
        """
        self.leaves = [self.hash_data(data) for data in data_list]
        self.root = self.build_tree(self.leaves)
    
    def hash_data(self, data):
        """SHA-256 해시 생성"""
        return hashlib.sha256(data.encode()).hexdigest()
    
    def build_tree(self, nodes):
        """머클 트리를 구축하고 루트 해시 값을 반환합니다."""
        if len(nodes) == 1:
            return nodes[0]  # 루트 노드
        
        if len(nodes) % 2 == 1:
            nodes.append(nodes[-1])  # 노드 개수가 홀수이면 마지막 노드를 복제
        
        parent_nodes = []
        for i in range(0, len(nodes), 2):
            combined_hash = self.hash_data(nodes[i] + nodes[i+1])
            parent_nodes.append(combined_hash)
        
        return self.build_tree(parent_nodes)
    
    def get_root(self):
        """머클 루트 반환"""
        return self.root
    
    def verify_proof(self, target_data):
        """
        특정 데이터가 머클 트리에 존재하는지 검증
        :param target_data: 검증할 데이터
        :return: 존재 여부 (True/False)
        """
        target_hash = self.hash_data(target_data)
        return target_hash in self.leaves

# 테스트용 데이터 리스트
data_list = ["apple", "banana", "cherry", "date"]

# 머클 트리 생성
merkle_tree = MerkleTree(data_list)

# 머클 루트 출력
print("Merkle Root:", merkle_tree.get_root())

# 특정 데이터 검증
print("Is 'apple' in Merkle Tree?", merkle_tree.verify_proof("apple"))
print("Is 'grape' in Merkle Tree?", merkle_tree.verify_proof("grape"))

🔹 실행 결과 예시:

Merkle Root: a3c8f8f7b5d9c2d8b7b9b5c1b6f9a3c...
Is 'apple' in Merkle Tree? True
Is 'grape' in Merkle Tree? False