[블록체인] 머클트리(merkle tree)

머클 트리(Merkle Tree)

-모든 자식 노드들이 암호학적 해시로 이뤄진 데이터 블록을 갖는 트리 형태의 자료 구조

-해시 트리(hash tree)라고도 불림.

머클루트(Merkle Root)

- 블록의 바디 부분에 저장된 트랜잭션(거래정보) 들의 해시트리

- 블록의 바디에 저장된 트랜잭션의 정보들이 유효한지 빠르게 검사하기 위한 역할을 수행

블록의 구성요소

머클트리의 특징

1. 무결성 보장 : Root 노드의 해시 값으로 모든 Leaf 노드의 데이터 변경 확인 가능

2. 동일 해시값 크기 : 해시 함수 기반 데이터 노드 수와 관계없이 동일한 크기

3. 빠른 검증 속도 : 이진 트리 구조 기반 빠른 속도의 검증 가능 O(log N)

 

머클루트 생성 방법

1. 최초 데이터를 SHA256 형태의 해시값으로 변환한다.
2. 가장 가까운 노드 2개를 한쌍으로 묶어 합친 후 해시값으로 변환한다.
3. 계속해서 해시값으로 변환하여 마지막 하나가 남을때까지 이 과정을 반복한다.
4. 하나의 블록의 모든 거래를 합친 마지막 하나인 그 블록을 ‘머클 루트’라 부른다.

 

머클트리의 매커니즘

구분적용	기술세부	동작
생성	SHA-256 해시 함수	– Data a H(a), Data b → H(b) 생성 – H(a) + H(b) → H(ab) 생성 – 머클트리로 머클루트 H(abcd) 생성
검증	Binary Tree 구조 머클패스 탐색	– Data b → Data b1로 변경 – 머클트리로 H(ab1cd) 생성 – 머클루트 불일치 : H(abcd)와 H(ab1cd)

참고

https://steemit.com/kr/@yahweh87/3

http://blog.skby.net/%EB%A8%B8%ED%81%B4%ED%8A%B8%EB%A6%AC-merkle-tree/