컴퓨터 科學 과 暗號學 에서 해시 트리 (hash tree)는 모든 非-리프(non-leaf) 노드의 이름이 子息 노드들 이름의 해시 로 構成된 트리 構造 를 가리킨다. 發明者 랄프 머클의 이름을 따 머클 트리 (Merkle tree)라고도 불린다.

救助 [ 編輯 ]

해시 트리는 트리 構造 의 一種으로, 잎 노드는 파일 等의 데이터를 가리킨다. 上位 노드는 各各 子息 노드들의 해시 값 이 된다. 例를 들어 위 그림에서 해시 0은 해시 0-0과 해시 0-1을 連結한 文字列을 다시 해시 函數로 計算한 것이다. 해시 函數는 위 그림처럼 李瑱 트리를 使用할 수도 있지만, 任意의 次數를 가진 트리에서도 使用 可能하다.

해시 函數는 어떤 것이든 使用할 수 있지만, 普通 SHA-1 , 타이거 , 월풀 等의 暗號化 해시 函數 가 使用된다. 그러나 해시 트리를 使用하는 目的이 惡意的인 攻擊者의 데이터 變調를 막으려는 것이 아니라, 單純히 誤謬를 찾기 위한 境遇, CRC 等의 安全하지 않은 函數를 使用할 수도 있다.

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

또한 데이터 全體가 아닌 一部만 檢證하고자 할 때에도 子息 노드 가운데 하나의 해시 값을 알면 그 노드의 모든 子息 노드에 對해 데이터를 檢證할 수 있는 特徵이 있다. 이런 特徵 때문에 萬若 一部 데이터가 損傷될 境遇 어떤 데이터가 損傷되었는지를 쉽게 찾아내어 損傷된 데이터를 다시 電送받을 수 있는 長點이 있다. 例를 들어 위 그림에서 데이터 2番이 損傷되었다면, 해시 0-1과 해시 0, 그리고 루트 해시가 달라지고 다른 값들은 달라지지 않을 것이다. 따라서 大量의 데이터가 있을 境遇에도 損傷된 데이터를 빠르게 찾아낼 수 있다.

用度 [ 編輯 ]

해시 트리는 여러 블록으로 나뉜 데이터를 電送할 때 데이터가 變造되지 않았음을 保障하는 用途로 使用된다. 特히 P2P 網에서 電送받은 데이터에 誤謬가 있거나 惡意的인 데이터 變調가 있는지를 檢證하는 用途로 使用된다. 썬 마이크로시스템즈 에서 開發한 ZFS 파일 시스템에서 해시 트리를 使用한다. ^[1] 또한 구글 웨이브 프로토콜 ^[2] 이나 깃 버전 管理 시스템, 비트코인 暗號 通貨 시스템, ^[3] 비트토렌트 프로토콜 等에서도 使用된다.

發明者 랄프 머클은 여러 個의 램포트 署名 을 效率的으로 다루기 위해 해시 트리를 開發했다. ^[4] 램포트 署名은 兩者 컴퓨터 가 實用化되어도 安全할 것으로 豫想되는 디지털 署名 알고리즘이지만, 한個의 메시지마다 새로운 키를 生成해야 하는 短點이 있다. 여러 個의 램포트 키를 해시 트리로 묶으면 보다 效率的으로 다룰 수 있다. 이런 方式을 머클 署名 이라고 부른다.

같이 보기 [ 編輯 ]

• 李瑱 트리
• 블록체인
• 分散 해시 테이블
• 해시 테이블

參考資料 [ 編輯 ]

• 머클 트리에 關한 特許 - 여러 個의 一回用 署名을 效率的으로 다루는 方法에 對해 說明한다

外部 링크 [ 編輯 ]

• [1] - C#으로 具現한 Tiger Tree Hash
• [2] - C와 Java로 具現한 Tiger Tree Hash
• Series of mini-lectures about cryptographic hash functions - 해시 트리를 保安 分野에 應用하는 法에 關한 動映像 講義