IT자격증

머클트리 (Merkle Tree) 의 정의

머클트리(Merkle Tree)는 이진트리(Binary Tree) 의 형태를 띠고 있다.
이진트리는 아시겠지만 아래 그림과 같이 부모노드가 자식노드를 2개만 가지고
있는 트리구조를 말한다. 

그럼 머클트리는 무었이냐?. 머클트리는 맨 마지막 노드 (Leaf Node) 는 값에 대한
Hash값을 저장하고 있고 그 상위 부모노드는 자식노드의 Hash값을  가지고 
다시 Hashing 한 Hash값을 저장하는 방식입니다.
예를 들어 a 에 대한 Hash값을 H(a) 라고 하고, b에 대한 Hash값을 H(b) 라고 하면
그 부모노드는 H(a)+(Hb) 에 대한 Hash값 H(ab)를 저장하고,, 계속 상위 노드로
올라가보면 결국 최상위 노드 즉 Root Node 는 전체  Node에 대한 Hash값을
가지고 있는 머클루트(Merkle Root) 가 되는 것이다.

머클트리(Merkle Tree)의 특징

1. 이진트리와 동일한 방식이지만 노드값이 Hash값으로 이루어져 있으며노
2. Hash값은 항상 동일한 크기의 값을 리턴하기 때문에 머클트리의  모든 노드는
   동일한 크기를 가지게 된다.
3. 따라서 공간절약을 장점으로 꼽을 수 있다. 
4. 일반적인 이진트리(Binary Tree)는 위에서 아래로 트리구조가 만들어지는
   반면 머클트리(Merkle Tree)는 아래에서 위로 올라가면서 노드가 생성되는 구조이다.
5. a,b,c,d 중 어느 값이 하나라도 변경되면 머클루트 도 변경된다.
   이는 곧 특정 노드값의 위변조를 알아차릴수 있다는 뜻으로 머클트리의 탄생배경의
   주된 이유라고 볼수 있을 만큼 제일 중요한 머클트리의 특징이다.

머클트리(Merkle Tree) 의 용도

그럼 이 머클트리는 왜 만들었을까?
요즘 이슈가 되고 있는 블록체인(Block Chain)은 각 블록(노드)마다 원장을 공유함으로써 특정
블록(노드)의 원장의 위변조를 검증할 수 있다는 게 가장 큰 특징이다.
그러면 모든 블록(노드)이 전체 거래원장을 가지고 있다면 어마어마한 용량의 PC가 있어야 하고
스마트폰에서는 블록체인 원장을 가지고 있을 수 도 없을 것이다.
물론 실제 이런 구조로 되어 있지도 않다.
노드(Node)는 크게 풀노드(Full Node)와 SPV노드(Simple Payment Verification)  로 분류할수
있다. 풀노드(Full Node)는 블록체인에 있는 모든 데이터를 자기의 로컬에 저장을 하는 노드
이며, SPV노드는 블록의 헤더값만 저장을 하는 노드입니다. 일반적인 블록체인의 블록들은
이 SPV노드이기 때문에 스마트폰과 같은 저장용량이 적은 경우에도 운용을 할수 가 있는
것이다.  따라서 SPV노드는 특정 거래를 검증을 위해서는 풀(Full Node) 로부터 데이터를
받아와서 비교를 해야 하는데 이때 쓰이는 것이 바로 머클트리(Merkle Tree) 이다.
SPV노드는 블록체인의 전체원장을 가지고 있지 않다고 했고, 대신 블록헤더(Block Header)라는
정보만 가지고 있는데 그 블록헤더에 머클루트(Merkle Root) 값이 저장되어 있다.
예를 들어 어떤 SPV노드가 있는데 이 노드에서 거래 c 에 대해서 진짜 유효한 거래 c 인지 
알고싶을때 SPV노드는 풀노드에게 물어본다. 그러면 풀노드는 SPV노드에게 H(d) , H(ab) 값을
전달해 준다. SPV노드는 H(c)를 만들어서 풀노드가 준  H(d)를 가지고  H(cd)를 만든다.
그리고 H(ab) 와 H(cd)를 가지고 H(abcd)를 만들어서 자기가 갖고 있는 블록헤더에 있는
H(abcd) 와 비교를 해서 같으면 c는 유효한 거래이고, 틀리면 먼가 위조된 거래인 것이다.
(요 방법을  머클패스(Merkle Path)  라고 함)


SPV노드

SPV노드는 위 그림과 같이 Chain으로 묶인 블록헤더(Block Header) 정보만을 가지고 있다.
그 안에  머클루트(Merkle Root) 값 즉, H(abcd) 값이 들어있다.

블록체인(Block Chain)의 용량은 시간이 갈수록 기하급수적으로 늘어나기 때문에  이제는 성능이
좋은 컴퓨터만 모든 블록체인을 다운받는 풀노드(Full Node)가 될수 있는데 이 머클트리(Merkle Tree)
방식은 우리가 들고 다니는 모바일 기기에서도 일부 블록체인만 다운받는 라이트노드(Light Node)
로도 특정 거래를 빠르게 찾을 수있게 해주는 역할을 한다.