블록체인 검증기술, 머클트리, 머클루트 - 모두의 블록체인 #7

머클트리(merkle tree), 머클루트(merkle root), 머클해시(merkle hash), 해시트리(hash tree) 다 비슷한 용어로 약간의 차이점만 있을 뿐 모두가 뜻하는 바는 동일하다. 우리가 암호화폐에 투자를 하거나 블록체인에 대해서 이해를 하려면 머클트리의 기술 정도는 이해를 할 수 있어야 하며 내용상 이해하기 어려운 것도 아니니 쫄 것도 없다.

 

머클트리, 머클루트 이해하기

 

머클트리는 암호화폐가 나오면서 만들어진 기술이 아니라, 1979년 랄프 머클이라는 사람이 만들어낸 개념으로, 일반적으로 트리 알고리즘들이 검색을 위해서 만들어졌다면 머클트리는 검증을 위해서 만들어진 트리이다. (여기까지 이해가 안되더라도 그냥 넘어가도록 한다)

 

머클트리의 구조

 

머클트리의 구조

 

머클트리는 위와 같은 구조로 되어 있고, 최상위 블록헤더(Block Header)는 무시하고, Root Hash까지만 이해를 하면 된다. 블록의 최상단에 위치한 헤더안에 Root Hash가 있는데 머클트리를 해서 나온 최종 계산값이 여기에 기록되는 것이다. 갑자기 머리가 아프다라고 호소를 하는 분이 있을 수 있는데 사실 매우 간단한 구조이니 조금만 참아주면 매우 짧은 시간에 "나는 머클루트라는 것을 설명할 수 있어"라는 사람이 될 수 있다. 

 

이렇게 생각할 수 있는데 너무 쉬운 개념이니 조금만 참아보면 된다.

 

머클트리의 알고리즘

거래기록들을 리프노드로

거래 기록들을 리프노드로 나열

 

우선 "철수가 영희에게 1000원을 줬다"와 같은 거래 기록들을 쭈욱 나열을 한다. 이때 tx라고 적은 이유는 컴퓨터에서 어떤 작업을 처리하는 단위를 트랜잭션(transaction)이라고 하기 때문이다. 즉 tx1은 우리가 볼 땐 거래기록1이지만 컴퓨터 관점으로는 트랜잭션1이 되는 것이다.

 

트랜잭션은 더이상 작업으로 나눌수가 없는 단위이기 때문에 최하단에 위치한 영역이다. 여기에 짝수 형태로 값이 있어야 하는데 만약 트랜잭션이 홀수로 끝나게 된다면 마지막 트랜잭션은 복사를 한다.

 

트랜잭션의 해쉬값 생성

거래기록들의 해쉬값을 생성

거래기록들을 해쉬값으로 생성한다. 해쉬값(Hash value)을 생성하게 되면 "철수가 영희에게 1000원을 줬다"라는 내용으로 "ab271fde..."와 같은 무슨말인지 이해안되는 값들을 생성할 수 있다. 

 

 

해쉬는 단방향으로 늘 고정적인 크기가 나오게 된다. 예를 들어, 국어대사전의 모든 글자들을 해쉬함수에 던져도 늘 고정적인 짧은 난수값으로 나타난다. 해쉬함수에 대해서 좀 더 자세히 알고 싶으면 아래의 글을 읽으면 도움이 될 것이다.

 

블록체인 핵심기술 - 2. 해시(Hash), 해시함수(Hash Function)

블록체인 핵심기술 - 2. 해시(Hash), 해시함수(Hash Function)

[Java] SHA-256 해싱(Hashing) 알고리즘 사용법

[Java] SHA-256 해싱(Hashing) 알고리즘 사용법

 

참고로 해쉬값의 크기를 줄이고 싶으면 그렇게 하면 된다. 예를 들어 블록의 크기가 너무 커져서 해쉬값을 줄이고 싶을 경우 해쉬값을 줄여 사용할 수 있다. 해쉬값을 확인해 주는 사이트가 있는데 여기에 값을 넣어서 알아보도록 한다.

 

demoblockchain.org/hash

Blockchain Demo

트랜잭션을 해쉬로 변환한 화면

 

위 해쉬를 테스트해볼 수 있는 사이트에서 철수가 영희에게 1000원을 줬다는 내용을 "0d3d2a8833a136f97cf6946b4ae5b957689da7835ec3de08e2ce47027ca41571" 값으로 변환하였다. 우리는 좀 더 개념을 쉽게 파악하기 위해 앞글자 10자만 따오기로 한다. 즉 철수가 영희에게 1000원을 줬다라는 내용은 "0d3d2a8833"로 치환할 수 있다.

 

해시 합치기

8개의 해쉬값을 4개로 합칠 수 있다

 

8개의 해시값들을 다시 2개씩 합쳐서 새로운 해시값을 만들어 낸다. 그러면 4개의 해쉬값이 나오게 되는데 2번째 트랜잭션 즉 tx2가 "영희가 영수에게 5000원을 줬습니다"라는 거래기록이라고 해보자. 마찬가지로 이 값을 해쉬로 변환하면

 

영희가 영수에게 5000원을 준 해쉬

 

804713d022f3af662f703da62f2983a72895eb703b190ad5ceef29a693eebbfd 해쉬값이 생성되고 앞글자 10개만 가지고 오면, "804713d022"값이 된다. 즉 영희가 영수에게 5000원을 줬습니다란 804713d022가 되는 것이다. 그럼 이 2번째 해쉬값과 첫번째 해쉬값을 합쳐보도록 한다.

 

첫번째 해쉬값 : 0d3d2a8833
두번째 해쉬값 : 804713d022

 

0d3d2a8833와 804713d022를 합쳐서 해쉬를 구한다

 

위 2개의 값을 합쳐서 8f84c682e5230e7496a31554d35f28577d3a53b14601fb296364dc5d31ff088d와 같은 해쉬가 나오게 되었고, 여기서 다시 앞글자 10개를 따오면 "8f84c682e5"값이 된다.

 

4개의 해쉬값을 다시 2개로 줄이고

 

2개의 해쉬값을 줄여서 최종 한개로 만든다

 

 

이렇게 계속 합치다보면 최종 1개가 나오게 되는데 이때 나오는 마지막 값이 머클루트(Merkle Root)가 되며 루트 해쉬(Root Hash)라고도 한다. 그리고 이 값은 블록의 헤더에 저장이 되어 블록을 매우 쉽고 빠르게 검증할 수 있게 만들어 준다.

 

 

머클트리를 하는 이유

머클트리는 모든 값들을 해쉬화하며, 이 값들을 모두 합쳐서 하나로 올리기 때문에 누군가가 블록을 조작을 할 경우 쉽게 알 수 있다. 값을 하나만 살짝 바꿔도 상위 해쉬값들이 변형되게 되며, 이를 통해 쉽게 알 수 있다. 

 

만약 영희가 악의적인 의도로 영수에게 5,000원을 줬다는 내용을 500,000원 줬다라고 거짓기록을 했다 가정을 해보자 그러면 tx2 트랜잭션 해쉬값이 바뀌게 된다. 

 

hash값이 바뀌어 버린다

단지 글자는 5000원이 500000만원으로 변경되었을 뿐이지만, 해쉬는 804713d022에서 7cdbc0ab99로 모든 것이 바뀌게 되면서 누가봐도 이 값에 변형이 됐다는 것을 쉽게 알 수 있다.

 

변형된 머클트리

 

위 그림에서 붉은색 해쉬 값이 변형된 해쉬값들이며, 최종 머클루트도 완전히 바뀌게 된다는 것을 알 수 있다. 이를 통해 노드 검증자는 이상이 있는 해쉬값을 선별하여, 찾아내고 위변조가 될 경우 해당 노드에게 패널티 혹은 추방을 하여 악의적인 조작을 할 수 없게 만들 수 있을 것이다.

 

동일한 내용의 영상

 

 

참고자료

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