머클 트리가 비트코인에서 수천 건의 거래를 단 몇 밀리초 만에 검증하는 방법. 이 우아한 자료구조의 작동 원리와 중요성.
import InfoBox from '@components/shortcodes/InfoBox.astro';
비트코인 블록 하나에는 수천 건의 거래가 담길 수 있습니다. 내 거래가 포함되었는지 확인하려면 블록의 모든 거래를 다운로드해서 하나씩 대조해야 할까요? 그건 느리고, 데이터도 많이 쓰고, 스마트폰에서는 사실상 불가능합니다.
대신 비트코인은 1979년 랄프 머클이 발명한 자료구조를 사용합니다: 머클 트리. 수천 건의 거래를 32바이트 해시 하나로 압축하고, 블록 전체가 아니라 소수의 해시만으로 특정 거래의 존재를 증명할 수 있게 해줍니다.
여러분의 스마트폰 지갑이 600GB 이상의 블록체인을 저장하지 않고도 거래를 검증할 수 있는 이유가 바로 이것입니다.
머클 트리는 해시의 이진 트리입니다.
1단계: 블록의 모든 거래를 SHA-256으로 해싱합니다 (비트코인은 항상 이중 해싱). 이것이 리프(잎) 노드입니다.
2단계: 쌍으로 묶습니다. 각 쌍을 합쳐서 부모 해시를 만듭니다. 홀수 개면 마지막 해시를 복제하여 자기 자신과 쌍을 이룹니다.
3단계: 반복합니다. 꼭대기에 단 하나의 해시가 남을 때까지 쌍을 묶고 해싱합니다.
꼭대기의 해시가 머클 루트입니다. 블록 헤더에 포함되며, 채굴자들이 작업증명을 찾을 때 해싱하는 80바이트 요약본의 일부입니다.
2,000건의 거래가 있는 블록에서 트리는 약 11단계입니다. 특정 거래 하나를 검증하는 데 2,000개가 아니라 11개 해시만 필요합니다.
어떤 레벨에서 거래 수가 홀수이면, 비트코인은 마지막 해시를 복제하여 자기 자신과 쌍을 만듭니다. "bitcoin merkle tree odd number duplicate last hash"는 가장 흔한 기술 질문 중 하나입니다.
답은 간단합니다: 모든 노드가 쌍을 가지도록 하여 이진 트리 구조를 유지합니다. 이것 없이는 홀수 레벨마다 특수 처리가 필요해서 불필요한 복잡성이 추가됩니다.
보안 관련 참고: 이 복제로 인해 이론적으로 서로 다른 거래 세트가 같은 머클 루트를 생성할 수 있습니다(CVE-2012-2459). Bitcoin Core는 중복 거래가 있는 블록을 거부하도록 패치했습니다.
머클 트리의 진짜 힘은 머클 증명(SPV 증명)입니다.
8건의 거래가 있는 블록에서 TX3의 포함을 검증한다고 합시다. 8개 전부 필요 없습니다:
해시 3개입니다. 단계별로 결합하여 블록 헤더의 머클 루트와 일치하는지 확인합니다. 일치하면 TX3은 블록에 있습니다. 거래가 변조되었다면 해시가 맞지 않습니다.
4,000건의 거래가 있는 블록에서도 머클 증명에 필요한 건 약 12개 해시(log2 4,000). 각 해시 32바이트. 수 메가바이트의 블록에서 멤버십을 증명하는 데 384바이트면 됩니다.
블록 헤더. 모든 블록 헤더에 해당 블록 거래들의 머클 루트가 포함됩니다.
SPV 지갑. Electrum, BlueWallet 등 대부분의 모바일 지갑이 머클 증명으로 거래를 검증합니다.
탭루트 (BIP 341). 2021년 업그레이드에서 MAST(Merkelized Abstract Syntax Trees)라는 머클 트리 구조를 사용하여 여러 지출 조건을 커밋합니다.
세그윗. 거래 머클 트리와 별도로 증인 데이터용 두 번째 머클 트리를 도입했습니다.
랄프 머클이 이 구조를 설계한 건 1979년 - 비트코인보다 30년 전입니다. 사토시가 이것을 채택한 이유는 근본적인 확장 문제를 해결하기 때문입니다: 신뢰 없는 시스템에 경량 기기가 어떻게 참여하는가?
답은 전체를 드러내지 않고 멤버십을 증명하는 해시의 트리입니다. 여러분의 폰이 수 밀리초 만에 비트코인 결제를 검증할 수 있는 이유이자, 600GB 데이터를 가진 풀노드가 같은 수학으로 같은 결론에 도달하는 이유입니다.