티스토리 뷰

알고리즘

머클트리(merkle tree)

육분이 2015.12.14 00:31


위키백과를 인용하면 "해시 트리(머클트리)는 트리 구조의 일종으로, 잎 노드는 파일 등의 데이터를 가리킨다. 상위 노드는 각각 자식 노드들의 해시 값이 된다"

아래 그림 참조.




사용 용도를 보면

p2p 시스템에서 보낸 자료의 유효성을 검사 할 때 사용한다.

예를 들어  파일을 보내기전에 Top Hash값을 공유한 후  개별 파일이 전송되는 경우 개별 파일로 Top Hash값을 계산하면 보내진 파일의  변조 유무를 검증할 수 있다.


또한 특정 파일의 변조유무를 검증할 수 있다.

예를 들어  Hash 0-0, Hash 1,  Top Hash을 알고 있는 경우 Data2 파일을 전송 받은 경우 

Data2를 이용해서 Hash 0-1의  해시를 만들고

Hash 0-1과 Hash 0-0을 이용해서 Hash 0을 만들고

Hash 0 과  Hash1의 해시 값을 Top Hash값과 비교하면 해당 파일의 변조 유무를 확인할 수 있다.  

참고로  Hash 0-0,  Hash1 를 머클경로(merkle path)하고  Top Hash 값을 merkle root 라고 한다.


https://github.com/vbuterin/pybitcointools/blob/master/bitcoin/blocks.py

https://github.com/ethers/EthereumBitcoinSwap/blob/master/serpent/debug/verifyTxForDebug.se

아래코드는 위에 코드를 사용하여 merkle path로 특정 해쉬값이 유효한지 검증하는 소스이다.
5번째 인덱스의 merkle path :
['fb8b5c47e9693f9834c9704460c4f8358c12ecf8ea2f0322ee2cad4f2a027618', 
'8278e3e47bb6f0e7c0cadfc3ab6f395689251df1e31922f5e7c9851eae356290', 
'aafcb72ae5c43b5ab2e1fd20e91381aee67cc3363f87bc8e4ae2504dc9272316', 
'5e22d508e7ff865131de483a95afc02c75cf0cbeb763b705e4c7d68afa9d7386']


참고:

https://ko.wikipedia.org/wiki/해시_트리

https://en.wikipedia.org/wiki/Merkle_tree

신고

'알고리즘' 카테고리의 다른 글

공인인증서  (0) 2016.03.23
대칭키  (0) 2016.01.03
난수 (random number)  (0) 2015.12.26
entropy (정보 엔트로피)  (0) 2015.12.25
머클트리(merkle tree)  (0) 2015.12.14
블룸필터(Bloom filter)  (0) 2015.12.05
댓글
댓글쓰기 폼
공지사항
Total
12,222
Today
3
Yesterday
39
링크
«   2017/08   »
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    
글 보관함