머클트리(Merkle Tree)

1. 머클트리(Merkle Tree)란?

머클트리는 블록체인내의 각각의 블록에 존재하는 트리이다.

실제 블록체인 블록을 통해 알아보자.

위의 두 사진은 현 시간 필자가 블로그를 작성하는 순간 최근 생성된 블록 정보이다.

거래의 수를 보면 1437개임을 알 수 있는데

머클 트리는 1437개의 Tx들을 각각 해싱하여 2개씩 짝지어서 또 해싱하고... 최종적으로 하나가 남을 때 까지 해싱을 한 트리이다.

위의 그림은 머클트리를 나타내고 있다.

Tx는 트랜잭션 번호를 의미하고 있고

Hxy는 Tx의 x번부터 y번까지 해싱한 것을 의미한다.

즉, 머클 트리를 구성하는 과정은 다음과 같다.

1. 최초 데이터(트랜잭션)를 SHA256 형태의 해시값으로 변환한다.

2. 가장 가까운 노드 2개를 한쌍으로 묶어 합친 후 해시값으로 변환한다.

3. 계속해서 해시값으로 변환하여 마지막 하나가 남을때까지 이 과정을 반복한다.

여기서 알 수 있는 것은 H18이 머클 루트가 되고 제일 위의 사진에서 블록 #518970의 머클 루트는 1437개의 모든 거래를 합친 해시값이 된다.

2. 머클 트리가 필요한 이유

라이트 노드들은 블록체인을 전부 다운받을 여유가 없다. (왜냐면 블록체인 네트워크 정보를 모두 다운받으면 약 130GB정도이기 때문이다.)

따라서 최소한의 정보로 인증할 방법이 필요하다.

라이트 노드들은 거래정보, 머클트리같은 정보들을 하나도 가지지 않고 머클루트 값만 가지고 있다.

만약 이 방법으로 블록이나 거래의 유효성을 검사 할 수 있다면 거래가 100건이든 1000건이든 최종적으로 라이트 노드가 가지는 요약본은 항상 64자로 일정하다.

(위의 사진에서 Merkle Root는 ffdca190de886025420ad410e3d6c57f5a466eff47ca28f92f522d9e5c4c9570로써 64자이다.)

이렇게 용량을 줄이면 다양한 디바이스들의 참여가 가능해지기에 블록체인 네트워크가 더 견고해질 수 있게 된다.

(EX :: 용량이 크지않은 태블릿 PC, 스마트폰 등등)

그리고 머클루트만 있다면 다양한 검증을 빠르고 확실하게 할 수 있다.

그 이유는 머클트리 자체가 해시로 이루어져있기 때문에 하나의 트랜잭션 혹은 블록내 필드값이 변조되면 머클루트 해시 값이 변조가 되기 때문이다.

따라서 이를통해 잘못된 해시값이 검출되면 해당 블록을 거부할 수 있게 되고 블록체인 네트워크를 계속해서 안정적으로 유지 할 수 있게 된다.

아래 그림을 보면 하나의 트랜잭션이 변조되면 머클 루트까지 모든 값이 바뀌게 됨을 알 수 있다.

이러한 현상을 쇄도 효과(avalanche effect)라고 한다.(https://ko.wikipedia.org/wiki/%EC%87%84%EB%8F%84_%ED%9A%A8%EA%B3%BC)

3. 실제 머클경로 그리고 머클루트 이용 방법

머클루트를 이용하여 우리는 블록이 가짜블록인지 진짜 블록인지 판단하기는 쉽다.

해당하는 블록넘버끼리 머클루트를 비교해보면 진짜인지 가짜인지 판단하기가 쉽기 때문이다.

그런데 블록이 아니라 트랜잭션을 검증해달라고 하면 말이 조금 달라진다.

머클루트 해시는 가지고 있으나 개별적인 트랜잭션 해시값들은 없기 때문이다.

하지만 우리는 Full Node에게 머클경로를 받음으로써 검증을 쉽게 할 수 있게 된다.

아래 그림을 보고 이야기해보자.

우리는 Tx7 트랜잭션이 올바른 트랜잭션인지 알고싶다.

그때 Full Node에게 머클경로를 요청하면 첫번째 사진과 같이 경로를 알려준다.

우리는 그럼 모든 머클트리를 받지 않고도 손쉽게 Tx7의 해시값을 이용하여 머클경로를 따라가다보면 머클루트와 결과값이 같은지 알 수 있다.

결과값이 다르면 그 트랜잭션은 잘못된 트랜잭션임이 확실해진다.

---

머클트리가 중요하게 여겨지는 이유는

1. 데이터의 유효성 검증을 O(lgN)만에 할 수 있기 때문이다.(즉,만에 검증이 가능하다.)

2. 모든 데이터를 가지고 있지 않아도 머클루트와 머클경로로 해결 할 수 있다.(용량의 절감이 엄청나다.)

여담으로 펜윅 트리라는 알고리즘이 있다. 매우 유사하고 필자는 알고리즘을 공부했던 사람이라 머클트리가 친근하게 다가왔다.

펜윅 트리 :: http://www.crocus.co.kr/666 

---