[Blockchain] 블록체인 머클트리(Merkle Tree)란?

블록체인에서 데이터 보안은 가장 중요한 이슈입니다. 다수의 블록들이 체인으로 연결되면서 데이터 무결성을 보장한다는게 블록체인의 강점인데요, 과연 블록체인은 어떻게 해서 데이터들이 위변조되는 것을 막고, 여태껏 비트코인 블록체인을 해킹할 수 없었던 것일까요? 그 중심에 머클트리(Merkle Tree)가 있습니다.

 

머클트리(Merkle Tree)?

 

머클트리는 여러 데이터에 대해 순차적으로 해시 함수를 적용해 하나의 해시값으로 표현하는 데이터 구조입니다. 머클트리를 사용함으로써 블록체인의 데이터 무결성을 보장하고, 위변조를 방지할 수 있게 됩니다. 머클트리의 동작 방식을 이해하면 왜 비트코인을 해킹하는게 불가능에 가까운지 이해하실 수 있습니다.

 

 

머클트리 동작방식

 

머클트리를 구성하기 위해 A,B,C,D 4개의 데이터가 있다고 가정합니다. 각 데이터를 해싱해 해시값을 얻어냅니다. 이제 데이터에는 해시값 hA가 담기게 됩니다.

 

B 데이터를 해시 한 다음 A의 해시값과 연결해줍니다. A와 B를 연결한 후 AB데이터의 해시값을 얻어냅니다. 

 

동일한 과정으로 C와 D데이터도 해시값을 얻은 후 ABCD의 값을 얻어냅니다. 최종적으로 1개의 해시값이 남을 때 까지 과정을 반복하면 최상위 노드에는 모든 데이터를 포함하고 있는 해시값이 담기게 됩니다. 이렇게 마지막으로 1개의 해시값을 가지게 되는 최상위 노드를 머클루트(Merkle Root)라고 합니다. 머클루트에는 모든 데이터를 해시값으로 연결한 최종값이 담기게 됩니다. 

 

 

 

 

 

머클트리의 무결성 보장방법

 

머클트리를 사용해서 블록체인 네트워크에서 데이서 무결성을 보장한다고 말씀드렸는데요, 어떻게 무결성을 보장할 수 있을까요? 눈치가 빠르신 분들이라면 벌써 머클트리의 작동방식을 보고 유추하실 수 있을것입니다. 위의 그림에서 B의 데이터를 악의적인 노드가 변경한다고 가정합니다. 해시함수는 1bit만 변경되어도 전체 출력값이 변경되므로 전혀 다른 해시값으로 바뀌게 됩니다. 

 

 

 

이제 B 데이터의 해시값이 변경되었으니, B와 연결되어 있는 AB 데이터의 해시값도 완전히 변경될 것입니다. 

 

최종적으로는 모든 데이터를 담고 있는 머클루트이 해시값도 변경되게 됩니다. 해시함수의 충돌저항성 성질 덕분에 머클루트를 확인하면 모든 데이터를 다 검토해보지 않아도 데이터 변조 유무를 바로 확인할 수 있게 됩니다.

 

 

머클트리 그리고 블록체인

 

데이터 위변조를 확인할 수 있는 머클트리는 블록체인에서 어떻게 활용될까요? 비트코인을 예로들어 알아보도록 합시다. 비트코인의 블록은 다음과 같은 구조를 가지고 있습니다. 모든 블록들은 고유한 해시값을 가지고 있습니다. Header에는 이전 블록의 해시값과 버전, 머클루트, 시간, 난이도, 논스등의 정보를 담고 있습니다. 그 밑으로 트랜잭션들을 담고 있습니다. 여기서 블록의 고유한 해시값이란 블록 헤더의 모든 값들을 연결해 해싱한 결과값이 담기게 됩니다.

 

 

블록이 Header에 담기는 머클루트는 어떻게 만들어질까요? 블록에 담긴 트랜잭션들을 머클트리를 이용해 최종 머클루트 값을 뽑아내게 됩니다. 

 

즉 하나의 블록내의 1개의 트랜잭션에 담긴 데이터를 1bit라도 변경하면 1번 블록내의 머클루트가 변경되고, 1번 블록의 해시값도 변경됩니다. 1개의 블록 해시값이 변경되면 2번 블록의 Heaer에 있는 이전 블록 해시값도 변경되고, 2번 블록의 해시값도 변경됩니다. 이렇게 연쇄적으로 모든 블록의 고유 해시값이 변경되면서 연결된 블록 이후의 블록들을 모두 수정해야 합니다.

 

 

비트코인의 경우 논스값을 찾아 새로운 블록이 생성되는데 10분이 소요되기 때문에 트랜잭션 1개를 수정하고 이후 블록을 모두 수정하기는 불가능에 가깝습니다. 이런 과정을 거쳐 블록체인에 한번 올라간 데이터를 업데이트 하는 일은 상당히 어려운 일이되었고, 그 결과로 데이터 무결성을 보장할 수 있게 됩니다. 

 

 

정리

 

정의

블록체인 네트워크에서 여러 데이터에 대해 순차적으로 해시값을 적용해 하나의 해시값을 구하는 방식. 블록체인 네트워크의 데이터 무결성을 보장합니다. 

 

적용

비트코인 블록체인 네트워크에서 실제로 사용되며, 매 10분 마다 새로운 블록이 생성되므로 트랜잭션을 변조하기가 어려워 진다는 특징을 가지고 있습니다. 비트코인과 다르게 이더리움에서는 단순 이진 머클트리를 사용하지 않고 조금더 개선된 머클 패트리샤 트리(MPT)를 채택해 사용하고 있습니다. 

 

 

 

[Blockchain] 비트코인 세그윗(SegWit) 이란?

 

[Blockchain] 블록체인 분산 원장 기술이란?

 

[Blockchain] 분산 데이터베이스 투명성 장점 단점 (feat 블록체인)