머클 트리: 하나의 씨앗에서 천 개의 잎으로

From One Seed to a Thousand Leaves – Merkle's Authentication Tree

1979년 Ralph Merkle이 제안한 디지털 서명 방식인 머클 트리(Merkle Tree)는 Lamport-Diffie 일회용 서명의 저장 공간 문제를 해결합니다. Lamport-Diffie 방식은 메시지의 각 비트에 대해 공개키-개인키 쌍을 생성해야 하므로 많은 저장 공간이 필요합니다. Merkle은 이진 트리를 사용하여 수많은 공개키를 하나의 루트 값으로 압축합니다. 서명자는 루트 값만 공유하면 되고, 수신자는 인증 경로를 통해 서명을 검증할 수 있습니다. 이 방식은 저장 공간을 획기적으로 줄여줍니다.