Merkle-Tree

개요 머클트리는 블록체인에서 거래 집합을 안전하고 효율적으로 요약·검증하기 위해 쓰이는 핵심 자료구조임 블록 헤더에 머클루트가 포함되는 이유는 블록 안의 모든 거래를 고정 크기 해시 하나로 대표해 무결성 확인과 경량 검증을 가능하게 하기 때문임 이 글은 머클트리의 구조와 동작 원리, 블록체인에서의 실무적 의미와 구현 주의사항까지 초보자도 이해할 수 있도록 상세히 설명함 핵심 개념과 구조 머클트리는 보통 이진 트리 형태로 구현함 거래들을 리프(leaf) 로 두고 인접 두 리프의 해시를 이어 붙여 부모 해시를 만들며 이 과정을 반복해 루트 해시를 얻음 해시 함수는 체인별로 다르며 비트코인은 더블 SHA‑256, 이더리움은 트라이 구조에서 Keccak‑256 을 사용함 최상단 해시를 머클루트(Merkle root) 라 부르며 크기는 해시 함수에 따라 고정됨 리프 수가 홀수일 때는 마지막 리프를 복제해 짝을 맞추는 방식이 일반적이며 비트코인은 이 규칙을 사용함 트리 깊이는 리프 수 N에 대해 ⌈log₂ N⌉ 에 비례하므로 대량의 거래를 효율적으로 요약할 수 있음 동작 원리와 장점 인접 노드 해시 H_left || H_right 를 순서대로 연결해 해시를 계산하고 이를 위로 올려가며 루트 해시를 얻음 무결성 검증 단일 거래가 바뀌면 해당 리프에서 루트까지의 모든 경로 해시가 바뀌어 변조를 즉시 탐지할 수 있음 효율적 포함 증명 특정 거래가 블록에 포함되었음을 증명하려면 그 거래와 경로상의 형제 해시들만 있으면 됨 필요한 해시 개수는 O(log N) 으로 작아 대역폭과 검증 비용이 작음 확장성 보조 리프가 1,000,000개여도 증명에 필요한 형제 해시는 약 20개 수준으로 32바이트 해시 기준 약 640바이트에 불과함 블록 헤더와 경량 노드(SPV) 비트코인 블록 헤더는 이전 블록 해시, 머클루트, 난스 등 합의 관련 메타데이터를 포함함 경량 노드(SPV)는 블록 전체가 아니라 헤더 체인만 받아 신뢰성을 확보하고, 개별 거래에 대해서는 풀노드로부터 머클 증명 을 받아 포함 여부를 검증함 이 방식은 모바일·임베디드 환경에서도 실사용이 가능하게 하는 기반이 됨 이더리움은 전통적인 이진 머클트리 대신 머클‑패트리샤 트라이(MPT) 를 사용해 거래·영수증·상태 루트를 헤더에 담아 유사한 목적을 달성함 구현 세부와 체인별 차이 비트코인 ...