<< 생각의 조각들. | Home | WEKA - Classification, Clustering >>

Merkle trees(Hash trees)

Merkle trees는 NoSQL의 요소 기술 중에 하나입니다. 관련 기술에 대해 정리해 봅니다. 기억을 메모하기 위해...

1. 개요

1979년 Ralph C. Merkle가 최초로 제안한 Merkle trees는 위의 그림과 같이 구성된다. Leaf 노드는 데이터의 블럭(파일이나 파일들의 집합)의 해쉬값이고 각 노드들은 자식의 해시 값을 나타낸다. 부모 노드의 top을 top hash (root hash 혹은 master hash)라고 불린다.
각 노드의 구성은 hash 0 = hash(hash 0-0 || hash 0-1)식으로 되고 '||'는 concatenation을 의미한다.
각각의 속성들을 해쉬하여 이진트리를 생성한 후 top hash를 이용하여 메시지를 검증한다. 이렇게 Hash Tree를 이용한 검증 방법을 Tree Authentication이라고 한다. Tree Authentication에서 가장 중요한 것은 top hash의 인증이다. Merkle은 올바른 top hash값을 검증자가 가지고 있다고 가정하고 메시지 인증을 한다.

2. 작동 방식
위의 그림을 가지고 p2p 네트워크에서 파일을 다운 받는 경우를 가지고 설명하면, 대부분 P2P에서는 파일 다운로드 받기 전에 top hash를 신뢰하는 소스(친구 혹은 추천되는 사이트들)로부터 받는다. top hash가 사용 가능할 때, hash tree리는 신뢰하지 않는 소스로 부터 받을 수 있다. 그때 받은 hash tree는 신뢰된 top hash에 의해 체크 되고 만약에 해시 트리가 손상이 되었을 경우 top hash가 매칭될때까지 다른 소스로 부터 hash tree를 다시 찾는다. hash tree가 해시 리스트와의 가장 큰 차이는 전체 tree가 사용 불가할지라도 hash tree의 한 지점(branch)을 가지고도 각 지점의 무결성을 체크할 수 있다는 것이다.
예로 데이터 블럭 2의 무결성은 데이터 블록을 해싱 및 반복적으로 해쉬 0-0 후 해시 1의 결과를 결합하고 최종적으로 top hash의 결과와 비교함으로써 해당 tree가 hash 0-0과 1을 포함하고 있다면 즉시 확인할 수 있다. 또한, 데이터 블록 3의 무결성은 hash 1-1과 0이 존재하면 바로 확인할 수 있게 된다. 이러한 방식은 파일을 아주 작은 데이터 블록으로 분할 하는데 효율적이기 때문에 작은 블록들이 손상을 받았을 경우엔 재 다운로드 받아야 한다. 해시된 파일이 크다면 해시 리스트나 hash tree도 상당히 커진다. 그러나 그것이 tree라면 작은 branch는 빨리 다운로드 되고, branch의 무결성은 체크되고 그때 데이터의 블록들은 다운로드 된다.

3. 사용 목적
컴퓨터간의 전송이나 트랜젝션에 의해 변형된 데이터들의 누락부분을 감지하고 최신의 상태로 동기화하는데 활용됨.

4. 활용처
  • Dynamo - Node나 key range당 하나의 Merkle Tree 구성. Merkle 트리를 anti-entropy용. Peer단위로 여러 개의 node가 최신 데이터로 복제하게 해 recovery 함.
  • Peer to Peer Communication에서 활용됨 - gnutella, DC++, Lime Wire, SHAERAZAR, Bitcoin peer-to-peer network
  • Cassandra - P2P네트워크 상에서 노드들이 수신하는 데이터 블럭들을 보장하는데 사용됨. Anti-entropy용으로 해당 트리가 다른 노드의 트리와 일치하지 않으면 불일치 해소(혹은 복구)를 해서 모든 노드에 최신 데어터로 유지하게 됨. Column Family당 한개의 Merkle Tree 구성됨.
  • Google BigTable, Hbase, ZFS, Google Wave에서도 사용되고 있음.
  • Git distributed revision control system, Tahoe-LAFS backup system 등에서도 활용됨.
  • SHA-1, Whirlpool, Tiger와 같은  Cryptographic hash function에서도 활용됨.

[참조 사이트]



Add a comment Send a TrackBack