디지털 시대에는 대규모 데이터 무결성 및 검증을 보장하는 것이 분산 시스템의 핵심 과제가 되었습니다. 해시 트리라고도 알려진 머클 트리는 단순한 수학적 데이터 구조일 뿐만 아니라 분산형 네트워크가 효율적이고 안전하게 작동할 수 있게 해주는 암호화 "백본"이기도 합니다. 1979년 Ralph Merkle이 발명한 이 구조는 네트워크에 참여하는 주체가 전체 거대한 데이터베이스를 보유하지 않고도 정보를 확인할 수 있도록 하여 데이터 검증 프로세스 최적화의 획기적인 발전을 나타냅니다.
Tan Phat Digital 전문가 팀의 이 보고서는 비트코인 및 이더리움과 같은 블록체인 프로토콜의 기술적 특성, 고급 변형, 전략적 역할은 물론 최신 Web3의 확장된 애플리케이션을 자세히 분석합니다. 생태계.
해시 트리의 역사적 기원과 진화
머클 트리의 개념은 Ralph Merkle 박사의 "A Digital Signature Based on a Conventional Encryption Function"이라는 과학 논문에서 처음 소개되었습니다. 당시 Merkle의 목표는 디지털 서명을 처리하고 공개 키를 안전하게 배포하는 효율적인 방법을 찾는 것이었습니다. 해시 트리가 출현하기 전에는 데이터 세트의 무결성을 검증하려면 모든 데이터 조각을 순차적으로 해싱하고 비교해야 하는 선형 방법이 필요한 경우가 많았으며, 이로 인해 데이터 규모가 증가함에 따라 계산 리소스와 대역폭이 낭비되었습니다.
머클 트리는 해시 함수를 계층 구조로 구성하여 게임을 완전히 바꿔 놓았습니다. 이 혁신을 통해 n 크기의 데이터 목록을 깊이가 log2(n)인 트리 구조로 변환할 수 있어 검증 문제를 선형 부담에서 매우 빠른 로그 연산으로 전환할 수 있습니다. 보안 파일 시스템과 P2P(Peer-to-Peer) 네트워크의 초기 적용부터 40년이 넘는 시간 동안 Merkle Trees는 2008년 비트코인 설계의 필수 요소가 되었으며 Ethereum과 같은 최신 네트워크의 Merkle Patricia Tries 또는 Verkle Trees와 같은 더 복잡한 구조로 계속해서 발전했습니다.
자세히 보기: 블록체인은 어떻게 작동하나요?
머클 트리의 기술적 메커니즘 및 구조
기술적으로 머클 트리는 각 리프 노드에 다음과 같은 라벨이 붙은 이진 트리 유형입니다. 데이터 블록의 해시 함수이며, 리프가 아닌 각 노드는 하위 노드 레이블의 암호화 해시로 레이블이 지정됩니다.
머클 트리의 핵심 구성 요소
이 구조가 모바일 기기에서 어떻게 작동하는지 이해하기 위해 Tan Phat Digital은 트리의 세 가지 주요 계층을 다음과 같이 요약합니다.
리프 노드: 각 노드에는 원시 데이터 단위(예: 블록체인 트랜잭션)의 해시가 포함되어 있는 트리의 가장 낮은 수준입니다. 데이터가 L1,L2인 경우 해당 리프 노드는 H1=Hash(L1),H2=Hash(L2)가 됩니다.
중간 노드: 이 노드는 리프 노드를 쌍으로 연결하고 서로 해싱하여 생성됩니다. 예를 들어, nodeH12는 Hash(H1+H2)의 결과입니다. 이 프로세스는 상단에 도달할 때까지 계단식으로 반복됩니다.
머클 루트: 이는 트리 상단에 있는 단일 노드로, 전체 데이터 세트를 고정 길이의 해시 문자열로 나타냅니다. 이는 고유한 "디지털 지문" 역할을 합니다. 리프 수준의 데이터 중 단 한 비트라도 변경되면 연쇄 효과로 인해 머클 루트가 완전히 변경됩니다.
암호적 의미 계층 구조:
피크(레벨 0) - 머클 루트: 전체 데이터 세트에 대한 약속, 측정 단위 레이어 하단의 해시(Hleft+Hright).
중간 - 내부 노드: 루트로 이어지는 구조적 링크, Hash(Pair of child nuˊt)로 계산.
하단 - 리프 노드: 다음에서 계산된 각 개별 요소를 나타냅니다. Hash(Data thoˆ).
암호화 해시 함수의 역할
해시 함수는 머클트리의 보안을 구동하는 엔진입니다. SHA-256과 같은 널리 사용되는 해시 함수는 결정성, 사전 이미지 저항 및 충돌 저항과 같은 중요한 속성을 가지고 있습니다. 머클 트리에서 충돌 저항은 머클 루트를 보존하면서 누구도 유효한 거래를 가짜 거래로 대체할 수 없도록 보장합니다.
바이너리 구조에서 홀수 데이터 처리
머클 트리는 일반적으로 리프 노드 수가 2의 거듭제곱이 되도록 요구하므로 데이터 수가 홀수인 경우 대부분의 구현에서는 마지막 요소를 두 배로 늘려 완전한 쌍을 형성합니다. 예를 들어, 트랜잭션 A, B, C가 있는 경우 트리는 HAB를 얻기 위해 A와 B를 해시하고 HCC를 얻기 위해 C 자체를 C와 해시합니다.
블록체인 무결성 및 효율성의 중요성
Merkle Tree는 Tan Phat Digital이 분석하는 두 가지 핵심 개념을 통해 확장성 문제를 해결합니다. 아래는 여기입니다:
머클 증명: 로그 검증 메커니즘
머클 증명을 사용하면 전체 세트를 로드하지 않고도 데이터 조각이 커밋된 세트에 있는지 여부를 확인할 수 있습니다. 사용자는 해당 트랜잭션에서 루트까지의 경로를 따라 "형제 해시"를 제공하기만 하면 됩니다. 예를 들어, 1백만 개가 넘는 거래의 경우 사용자는 거래를 검증하는 데 20개의 중간 해시만 필요합니다.
라이트 클라이언트에 최적화
라이트 노드는 매우 작은 블록 헤더(비트코인의 경우 80바이트)만 다운로드합니다. 지불 확인이 필요할 때 라이트 노드는 풀 노드에 Merkle Proof를 요청합니다. 최종 해시 결과를 저장된 머클 루트와 일치시킴으로써 라이트 노드는 거래의 유효성에 대해 완전한 확신을 가질 수 있습니다.
선형 대 머클 트리 확인 비교:
복잡성: 선형은 O(n)인 반면, 머클 트리는 O(logn).
데이터 전송: 선형은 전체 목록이 필요하고 Merkle Tree는 경로의 자매 노드만 필요합니다.
병렬성: 선형은 매우 낮고 Merkle Tree는 매우 높습니다.
영향력 변경: 선형은 전체 재해시가 필요하며, 머클 트리는 단순히 영향을 받은 분기를 업데이트합니다.
비트코인과 이더리움의 머클 트리
비트코인: 간단한 이진 구조
비트코인은 간단한 이진 머클 트리를 사용합니다. 머클 루트는 블록 헤더에 직접 배치되어 깨지지 않는 결합을 생성합니다. 그러나 이 구조는 정적입니다. 블록이 채굴되면 거래 목록은 절대 변경되지 않습니다.
Ethereum: Merkle Patricia Trie(MPT)
Ethereum은 MPT를 사용하여 거래뿐만 아니라 전체 네트워크 상태(계정 잔액, 계약 코드)도 저장합니다. MPT를 사용하면 공통 접두사 경로를 효율적으로 업데이트하고 압축하여 저장할 수 있습니다. 이더리움 블록에는 네 가지 유형의 머클 루트가 포함되어 있습니다.
상태 루트: 각 블록과 함께 지속적으로 변경되는 모든 계정에 대한 전역 정보를 포함합니다.
트랜잭션 루트: 현재 블록의 로컬 트랜잭션을 포함합니다.
수신 루트: 트랜잭션 영수증, 실행 결과 및 log.
스토리지 루트: 각 스마트 계약마다 별도로 해당 계약의 내부 데이터를 저장합니다.
자세히 보기: 블록체인의 체인이란 무엇인가요?
고급 변형: 희소 머클 트리 및 MMR
희소 머클 트리(SMT)
SMT 대규모 주소 공간(2256개 카드)을 위해 설계되었지만 대부분의 카드가 비어 있습니다. 빠른 계산이 가능하고 "비존재 증명"을 지원하여 트랜잭션이 발생하지 않았음을 증명합니다.
머클 산맥(MMR)
MMR은 기존 노드를 변경하지 않고 새 요소를 추가할 수 있는 트리 구조입니다. 이는 추가 전용 데이터 및 SSD에 대한 데이터 쓰기 최적화에 적합합니다.
Verkle Tree: 무상태의 혁명
Verkle Tree는 단순 해싱 대신 다항식 커밋먼트를 사용하여 기존 Merkle Tree에 대한 더 효율적인 대안입니다.
MPT와 비교하여 Verkle Tree의 뛰어난 기능:
구조: MPT는 이진 해시 트리이고 Verkle은 다항식 커밋 트리입니다.
너비: MPT는 너비가 2 또는 16이고 Verkle은 너비가 최대 256 또는 1024입니다.
증명 크기: MPT는 약 150KB, Verkle은 1~2KB에 불과합니다(50~100배 더 작음).
저장소: Verkle은 "상태 비저장" 작업을 허용하여 노드가 전체 거대한 상태 데이터를 저장할 필요가 없도록 돕습니다.
계산: MPT는 계산이 간단하지만 Verkle은 복잡한 타원 곡선 계산이 필요합니다. more.
암호화 보안 및 취약점
머클 트리는 강력하지만 비트코인에서 발견된 거래 복제 공격(CVE-2012-2459)이나 2차 사전 이미지 공격과 같은 약점을 여전히 갖고 있습니다. 예방 조치로 Tan Phat Digital은 개발자가 OpenZeppelin에서 제안한 이중 리프 해시 방법이나 도메인 분리를 사용할 것을 권장합니다.
확장 Web3 애플리케이션
예비 증명(PoR): Binance와 같은 거래소는 Merkle Tree와 zk-SNARK를 결합하여 고객 자산을 보호하면서도 충분한 리소스를 보유하고 있음을 입증합니다. 개인 정보 보호.
에어드롭 배포: 프로젝트는 Merkle 출처만 발표하면 되며, 사용자는 증거와 함께 청구 요청을 직접 제출하여 가스 비용을 99% 절약할 수 있습니다.
파일 시스템(IPFS/BitTorrent): Merkle Tree를 사용하여 콘텐츠를 식별하고 다양한 소스에서 다운로드한 데이터 조각이 손상되지 않았는지 확인하세요. 손상되었습니다.
Celestia: NMT(Namespaced Merkle Tree)를 사용하여 각 애플리케이션에 따라 데이터를 정렬하므로 롤업에서는 관련 데이터만 다운로드하면 됩니다.
10 Merkle Tree 애플리케이션의 일반적인 사례 연구
실제 적용 가능성을 입증하기 위해 Tan Phat Digital은 10개를 합성합니다. 가장 대표적인 사례:
Bitcoin(Simplified Payment Verification): Electrum과 같은 경량 모바일 지갑을 사용하여 500GB 이상의 체인 데이터, 80바이트 블록 헤더 및 약 12-20개의 증명 해시를 다운로드하지 않고도 거래를 검증할 수 있습니다.
Ethereum(상태 관리): Merkle 사용 Patricia Trie는 수백만 개의 자산 계정과 잔액을 저장합니다. 잔액이 변경되면 시스템은 전체 데이터베이스를 다시 구축할 필요 없이 해당 지점만 업데이트합니다.
Binance(예비 증명): FTX 이벤트 후 Binance는 zk-SNARK를 결합한 Merkle Tree를 배포하여 1:1 자산 준비 비율을 증명하여 사용자가 신원을 공개하지 않고 자신의 돈을 확인할 수 있도록 돕습니다.
Celestia(모듈식 블록체인): 네임스페이스 머클 트리를 사용하여 분류합니다. 각 프로젝트에 따른 데이터(Rollup) 이를 통해 애플리케이션은 "자신의" 데이터만 다운로드하면 되므로 시스템 리소스에 대한 부하가 줄어듭니다.
Git(버전 관리 시스템): Git의 모든 "커밋"은 실제로 Merkle Tree(트리 개체)입니다. 이는 Git이 수백만 줄의 코드를 비교하고 변경 사항이나 중복 파일을 즉시 감지하는 데 도움이 됩니다.
BitTorrent(Peer-to-Peer 파일 공유): 영화를 다운로드할 때 Merkle Tree는 다양한 소스에서 다운로드한 각 데이터 조각(청크)을 확인하는 데 도움이 됩니다. 조각이 손상된 경우 시스템은 전체 파일 대신 해당 조각만 다시 로드합니다.
IPFS(분산 파일 시스템): Merkle DAG를 사용하여 콘텐츠를 식별합니다. 동일한 콘텐츠를 포함하는 두 파일은 동일한 주소(CID)를 갖게 되므로 시스템이 네트워크 전체에서 중복 데이터를 자동으로 제거하는 데 도움이 됩니다.
Apache Cassandra(데이터베이스 복제): Merkle Tree를 사용하여 복제본 서버(복제본) 간의 불일치를 감지합니다. 비교를 위해 전체 데이터를 보내는 대신 서버는 왜곡된 데이터 영역을 찾기 위해 Merkle Root만 교환합니다.
Starknet(ZK-Rollup Airdrops): Merkle Tree 및 Cairo 언어를 사용하여 수백만 명의 사용자에게 토큰을 배포합니다. 프로젝트는 전체 보상 이벤트를 수행하기 위해 단일 32바이트 루트 해시를 온체인에 저장하면 됩니다.
인증서 투명성: 인증 기관(CA)이 탐지 없이 웹사이트에 가짜 인증서를 발급하는 것을 방지하기 위해 Merkle Tree를 사용하는 SSL/TLS 인증서용 공용 저장 시스템입니다.
자주 묻는 질문(FAQ)
다음은 Tan Phat이 편집한 Merkle Tree에 관한 가장 인기 있는 질문 10가지입니다. 디지털:
블록체인이 단순 해시 목록 대신 머클 트리를 사용하는 이유는 무엇입니까?
머클 트리를 사용하면 O(n) 대신 O(log n) 복잡성으로 특정 거래를 확인할 수 있습니다. 즉, 100만 건의 트랜잭션에 대해 100만 단계가 아닌 약 20개의 확인 단계만 필요하므로 상당한 대역폭과 리소스가 절약됩니다.
블록의 트랜잭션 수가 홀수이면 어떻게 되나요?
균형 이진 트리 구조를 유지하기 위해 목록의 마지막 트랜잭션이 복제되고 자체적으로 해시되어 완전한 쌍을 형성합니다.
차이점의 차이점은 무엇인가요? 머클루트와 머클 증명?
머클루트는 전체 데이터 세트를 대표하는 트리 상단에 위치한 고유한 해시입니다. Merkle Proof는 사용자가 특정 데이터에서 Merkle Root를 수동으로 다시 계산하는 데 필요한 중간 해시(경로) 세트입니다.
공격자가 Merkle Root를 변경하지 않고 데이터를 변경할 수 있습니까?
이론적으로는 암호화 해시 함수의 충돌 방지 특성으로 인해 불가능합니다. 리프 노드에 작은 변화라도 생기면 루트의 해시 코드가 완전히 바뀌는 체인 효과가 발생합니다.
이더리움이 Verkle Tree로 이동하는 이유는 무엇인가요?
이더리움에서 Merkle Tree의 가장 큰 문제는 증명 크기(증인)가 너무 크다는 것(약 150KB)입니다. Verkle Tree는 이 크기를 1~2KB로 줄이는 데 도움이 되므로 네트워크 노드가 "상태 비저장" 모드에서 더 효과적으로 작동할 수 있습니다.
계정이 시스템에 존재하지 않는다는 것을 어떻게 증명할 수 있나요?
이 작업은 Sparse Merkle Tree(SMT)를 통해 수행됩니다. SMT에는 고정된 주소 공간이 있으므로 값이 0인 리프 노드로 이어지는 머클 증명을 제공하여 해당 데이터가 없음을 증명할 수 있습니다.
머클 트리가 개인 정보 보호에 도움이 됩니까?
예. Merkle Proof를 사용하면 해당 블록의 다른 거래를 공개하지 않고도 해당 블록에 거래가 존재한다는 것을 증명할 수 있습니다. ZK-SNARK와 결합하면 교환 보유량 증명과 같은 매우 높은 보안 시스템을 생성합니다.
비트코인은 왜 이더리움의 Merkle Patricia Trie와 같은 복잡한 구조를 사용하지 않습니까?
비트코인은 정적 원장(UTXO 모델)이기 때문입니다. 블록이 채굴되면 거래는 절대 변경되지 않습니다. 이더리움은 각 거래 후 계정 잔액과 계약 코드가 지속적으로 변경되는 동적 상태 머신이기 때문에 MPT가 필요합니다.
머클 트리의 "두 번째 사전 이미지" 공격이란?
이는 공격자가 리프 노드 위치에 내부 노드를 주입하여 시스템을 속이는 취약점입니다. 이를 방지하기 위해 OpenZeppelin과 같은 라이브러리는 종종 리프($H(H(\text{data}))$)를 두 배로 해시하거나 레이어를 구별하기 위해 접두사를 추가합니다.
머클 트리는 블록체인 외에 어디에 사용됩니까?
Git에서 소스 코드 버전 관리를 위해, ZFS/Btrfs에서 하드 드라이브 데이터 손상을 방지하기 위해, BitTorrent 및 IPFS와 같은 P2P 네트워크에서 무결성 확인을 위해 널리 사용됩니다. 많은 소스에서 다운로드된 파일 조각의 수입니다.
Tan Phat Digital에 따르면 Merkle Tree는 수학 단순성의 힘을 입증합니다. 이는 데이터 변조를 방지할 뿐만 아니라 취약한 장치에 대한 네트워크 액세스를 확장하는 도구이기도 합니다. Verkle Tree의 진화는 블록체인 기술이 글로벌 규모의 문제를 해결하기 위해 지속적으로 노력하고 있음을 보여줍니다. 머클 루트는 사용자가 인간 대신 수학 법칙을 신뢰하는 분산화된 세계에서 계속해서 "신뢰의 지렛대"가 될 것입니다.
공유
