해시 트리

컴퓨터 과학과 암호학에서 해시 트리(hash tree)는 모든 비-리프(non-leaf) 노드의 이름이 자식 노드들 이름의 해시로 구성된 트리 구조를 가리킨다. 발명자 랄프 머클의 이름을 따 머클 트리(Merkle tree)라고도 불린다.

구조

해시 트리는 트리 구조의 일종으로, 잎 노드는 파일 등의 데이터를 가리킨다. 상위 노드는 각각 자식 노드들의 해시 값이 된다. 예를 들어 위 그림에서 해시 0은 해시 0-0과 해시 0-1을 연결한 문자열을 다시 해시 함수로 계산한 것이다. 해시 함수는 위 그림처럼 이진 트리를 사용할 수도 있지만, 임의의 차수를 가진 트리에서도 사용 가능하다.

해시 함수는 어떤 것이든 사용할 수 있지만, 보통 SHA-1, 타이거, 월풀 등의 암호화 해시 함수가 사용된다. 그러나 해시 트리를 사용하는 목적이 악의적인 공격자의 데이터 변조를 막으려는 것이 아니라, 단순히 오류를 찾기 위한 경우, CRC 등의 안전하지 않은 함수를 사용할 수도 있다.

데이터를 검증하고자 하는 사용자는 루트 노드의 해시 값(루트 해시 또는 마스터 해시라고 부른다)만 알면 데이터가 옳은 데이터인지 검증할 수 있다.

또한 데이터 전체가 아닌 일부만 검증하고자 할 때에도 자식 노드 가운데 하나의 해시 값을 알면 그 노드의 모든 자식 노드에 대해 데이터를 검증할 수 있는 특징이 있다. 이런 특징 때문에 만약 일부 데이터가 손상될 경우 어떤 데이터가 손상되었는지를 쉽게 찾아내어 손상된 데이터를 다시 전송받을 수 있는 장점이 있다. 예를 들어 위 그림에서 데이터 2번이 손상되었다면, 해시 0-1과 해시 0, 그리고 루트 해시가 달라지고 다른 값들은 달라지지 않을 것이다. 따라서 대량의 데이터가 있을 경우에도 손상된 데이터를 빠르게 찾아낼 수 있다.

용도

해시 트리는 여러 블록으로 나뉜 데이터를 전송할 때 데이터가 변조되지 않았음을 보장하는 용도로 사용된다. 특히 P2P 망에서 전송받은 데이터에 오류가 있거나 악의적인 데이터 변조가 있는지를 검증하는 용도로 사용된다. 썬 마이크로시스템즈에서 개발한 ZFS 파일 시스템에서 해시 트리를 사용한다.^[1] 또한 구글 웨이브 프로토콜^[2] 이나 깃 버전 관리 시스템, 비트코인 암호 통화 시스템,^[3] 비트토렌트 프로토콜 등에서도 사용된다.

발명자 랄프 머클은 여러 개의 램포트 서명을 효율적으로 다루기 위해 해시 트리를 개발했다.^[4] 램포트 서명은 양자 컴퓨터가 실용화되어도 안전할 것으로 예상되는 디지털 서명 알고리즘이지만, 한개의 메시지마다 새로운 키를 생성해야 하는 단점이 있다. 여러 개의 램포트 키를 해시 트리로 묶으면 보다 효율적으로 다룰 수 있다. 이런 방식을 머클 서명이라고 부른다.

같이 보기

참고자료

머클 트리에 관한 특허 - 여러 개의 일회용 서명을 효율적으로 다루는 방법에 대해 설명한다

↑ Jeff Bonwick (2005년 12월 8일). “ZFS End-to-End Data Integrity” (영어). 2017년 5월 6일에 원본 문서에서 보존된 문서. 2013년 8월 28일에 확인함.
↑ Lea Kissner; Ben Laurie (2009년 5월 27일). “General Verifiable Federation” (영어). 3쪽. 2013년 9월 28일에 원본 문서 (pdf)에서 보존된 문서. 2013년 8월 28일에 확인함.
↑ Satoshi Nakamoto (2008). “Bitcoin: A Peer-to-Peer Electronic Cash System” (pdf) (영어). 4쪽. 2013년 8월 28일에 확인함.
↑ Merkle, Ralph (1987). “A Digital Signature Based on a Conventional Encryption Function” (PDF). 《Crypto '87》 (영어) (293): 369-378. doi:10.1007/3-540-48184-2_32. 2010년 6월 11일에 원본 문서 (PDF)에서 보존된 문서. 2013년 8월 28일에 확인함.

외부 링크

[1] - C#으로 구현한 Tiger Tree Hash
[2] - C와 Java로 구현한 Tiger Tree Hash
Series of mini-lectures about cryptographic hash functions - 해시 트리를 보안 분야에 응용하는 법에 관한 동영상 강의

[1] Jeff Bonwick (2005년 12월 8일). “ZFS End-to-End Data Integrity” (영어). 2017년 5월 6일에 원본 문서에서 보존된 문서. 2013년 8월 28일에 확인함.

[2] Lea Kissner; Ben Laurie (2009년 5월 27일). “General Verifiable Federation” (영어). 3쪽. 2013년 9월 28일에 원본 문서 (pdf)에서 보존된 문서. 2013년 8월 28일에 확인함.

[3] Satoshi Nakamoto (2008). “Bitcoin: A Peer-to-Peer Electronic Cash System” (pdf) (영어). 4쪽. 2013년 8월 28일에 확인함.

[4] Merkle, Ralph (1987). “A Digital Signature Based on a Conventional Encryption Function” (PDF). 《Crypto '87》 (영어) (293): 369-378. doi:10.1007/3-540-48184-2_32. 2010년 6월 11일에 원본 문서 (PDF)에서 보존된 문서. 2013년 8월 28일에 확인함.

[1]

[2]

[3]

[4]