트리

---

IT 세계에서 자료를 얼마나 잘 정리하느냐는 것은
성능, 시간, 돈과 직결된다

자기방처럼 자료를 놓아두다간

(하나님 맙소사.. 이런 곳에 자료가?)

자료하나 찾는데 엄청난 시간과 성능이 필요하게 되고
결국 아무도 안쓰게 된다.

그래서 공학도들은 자료를


최대한 카와이하게 정리하는 방법을 연구했고
그 중 하나가 바로

트리구조이다

저게 어떻게 자료 찾는데 도움이 될까?

쉽게 말하면 우리컴에서 폴더구조를 생각하면 된다
만약 폴더가 없이
모든 파일이 C드라이브에 몽땅 펼쳐져 있다면?

아주 손가락이 부러져라 스크롤 해야할 것이다

하지만 우린 트리구조를 사용해 아주 효율적으로
자료를 정리해놓고 있다.
경로만 알면 곧장 목적지를 찾을 수 있는 것이다.

머클트리의 개념과 생성

---

트리란게.. 그냥 저런식이다 라는 것을 개괄적으로
말하는 것이라 만들기에 따라 여러종류가 있다

그 중에서 비트코인 블록체인에 사용하는 트리는
머클트리라는 것으로
머클이라는 사람이 만들어서 머클트리이다-ㅅ-;

이건 위의 폴더트리와는 또 목적과 사용법이 많이 다르다

머클트리의 목적은 빠른 검색 같은 것이 아니라
데이터의 간편하고 확실한 인증을 위해서 존재한다.

그것을 위해서 해쉬를 사용하는데
해쉬는 이전에도 설명했듯이 디지털 지문을 만드는 행위이다.
🔗해시와 해시함수의 개념

해시함수에 나오는 출력에서 입력을 절대 유추할 수 없지만
입력이 같으면 출력은 같다.
이것을 이용해서 입력이 달라졌는지를
검증할 수 있는 것이 해시함수이다.

머클트리는 수많은 입력을
조금씩 압축해서 최종적으로 하나의 출력만으로도
모든 입력을 개별적으로, 그리고 최소한의 정보로
검증할 수 있게 만드는 기술이다.

그럼 어떻게 만들기에 그게 가능한지 한번 알아보자
머클트리는 다음과 같은 방식으로 만들어진다.

1. 처음자료를 해쉬질한다
2. 2인1조로 둘을 합쳐서 해쉬질한다
3. 해쉬질한 결과물들을 다시 2인1조로 합쳐서 해쉬질한다
4. 마지막 하나가 남을때까지 이 과정을 반복한다.

알기쉽게 그림으로 보면

이렇게 된다.

즉, 거래1과 거래2의 해시값인
Little과 Rain을 더한후 같이 해시상자에 쳐넣어

해시값을 하나로 줄이는 행위를
최후의 한개가 남을때까지 반복하는 것이다.

부전승없는 토너먼트랑도 비슷한데

모든 결과값은 이전의 출력을 해시해서 이뤄졌기에
입력이 하나라도 달라지면 최종결과값도
달라지게 된다.

머클트리의 용도

---

그럼 뭐하러 이런 귀찮은 짓을 할까

그 이유는
라이트노드들은 블록체인을 전부 다운받을 여유가
없기에 최소한의 정보로 인증할 방법이
필요했기 때문이다.

즉, 거래정보들은 물론 머클트리도 하나도 저장하고 있지 않다.
가지고 있는것은 머클트리의 꼭대기 최종 결과값 하나뿐이다.
게다가 이방법이면
거래가 100건이든 1000건이든 최종 요약본은
항상 64자로 일정하다.

이렇게 용량을 줄여버리면
블록체인의 1000분의 1이하로 용량이 줄어들어서
안드로이드 같은 기기도 블록체인에 참여가 가능해진다

그러면서도 검증은 또 검증대로 확실하게 가능한데..
해시함수의 특성상 어느것 하나라도 조작되면
출력값은 달라지기 때문이다

그러면 그 달라진 출력을 입력으로 받는 상위트리는
당연히 완전 다른 출력이 나게 되고
그걸 입력값으로 받는
최종 요약본까지 전혀 다른 값이 되는 것이다.

그러므로 자신이 받은 요약본값과 다른 블록이
날아오면 가짜라고 판명하고 바로 거부할 수 있는 것이다.

머클경로

---

라이트지갑들은 이 머클트리가 있음으로 인해서
블록체인을 통채로 받는 대신
각 블록들의 요약본들만 주루룩 받아서 가지고 있는다.

그리고 날아오는 블록들을 진짜인지 가짜인지
값을 비교해서 검증한다.

한데 블록이 아니라
거래를 검증해달라고 날아오는 경우가 훨씬 많다.
그 경우는 블록전체의 요약본은 있으나
개별거래의 정보는 없으므로
검증이 불가능해보인다.

하지만
풀노드에게 간단한 정보를 받는 것으로
문제를 해결할 수 있다.

예를들면 우린 7번거래가 포함되어 있는지를 알고
싶다고 하자.

이때 단순하게 경로를

리또속->육감->고기

이렇게 가르쳐준다고 생각하지 말자.
왜냐면 우린

머클트리나 각 거래기록을 가지고 있는게 아니라
최종요약본인 폭락과
검증해달라고 받은 7번거래 정보 두가지밖에 없기 때문이다

저런 경로를 보내줘봐야..
아는게 없으니 검증은 불가능하다.

그래서 나온 것이 바로 머클경로이다

풀노드는 저런 경로를 가르쳐주는 것이 아니라
해쉬토너먼트 상대를 가르쳐준다

니가 알아서 해쉬해서 검증하라는 것이다.

이렇게 상대를 알려주면 얘기는 쉬워진다

고기 + 감각 = 육감
가라오케 + 육감 = 리또속
리또속 + 코인원 = 폭락

내가 가진 거래7의 해쉬로부터 받은 머클경로를
차례로 계산해서
토너먼트 해쉬질의 우승자가
내가 알고 있는 요약본 값과 같으면
해당 거래가 블록내에 포함되어 있는 것이 확실한 것이다.
반대로 다른 값이 나오면 해당거래는 가짜로 판명된다.

맺으며

---

머클트리 자체의 개념은 그렇게 어려운게 아닙니다.
하지만 그걸 설명하기 위해 해쉬설명이 필수이고
무엇보다 블록체인에서 왜 쓰는가에
대해서 말할려니
spv노드와 풀노드의 개념이 안들어갈 수 없네요.

결국 3편까지 오게 되었는데-ㅅ-
하루에 하나씩 땜빵하다보니
설명이 좀 불만족스럽군요.

무엇보다 후반부 개그버전이 논리적 오류로 인해
폐기처분되었고 그와함께 저의 개그감각도
절망에 빠져서 후반부는 좀 머리가 아플겁니다-ㅅ-;

그래도 이정도면 어느정도만 공부하면 쉽게
알 수 있을거예요.
EOS 때문에 덴이 논쟁한 것에서도
머클트리에 대한 개념이 들어있죠.
전체를 비교하는게 아니라 요약본만 비교하는거니
스팀같이 고속으로 블록발행하는 블록체인에선
이런 빠른 비교가 가능한 요약본이 필수거든요. :)

그럼 이해안되더라도
걍 요약본이 있구나~ 정도로 생각해주세요+__+/