티스토리 뷰
오늘은 비트코인에서 쓰이는
"머클트리(Merkle tree)" 라는 자료구조에 대해 알아보겠습니다
알고리즘 공부를 하던 저에게는 가장 재밌고 친근한 주제였습니다
공부할 때
를 참고해 공부했습니다! 제목이 한글이라 주소가 좀 길게 나오네요...!
waca님께서 코드를 잘 정리해주셔서 이해하기 쉬웠습니다!
우선 머클트리란 무엇일까요?
위에 그림은 머클트리를 그림으로 표현한 것 입니다
사실 머클트리라는 이름보다 해시트리라는 이름이 더 잘 이해하기 쉽습니다
이 트리를 만든사람 이름이 랄프 머클이라 머클트리라고도 부릅니다!
머클트리는 데이터가 있을 때 해시된 값을 리프 노드로 만들고
계속 2개씩 해시해며 올라가 루트까지 가는 이진트리 입니다
그림으로 보면 이해하기 쉽습니다!
여기에서 루트를 머클루트 라고 부릅니다
그럼 머클트리를 사용했을 때 장점이 무엇일까요?
바로 위변조 검사가 쉽다는 것 입니다
2개씩 짝지어 해시하기 때문에 하나라도 값이 바뀌면
머클루트값이 변하게 됩니다
따라서 위변조를 검사하기가 쉽습니다!
제가 처음보고 든 생각은 알고리즘 공부할 때 배운
세그먼트트리로 구간의 해시값을 구해서 루트만 가져간다~
라는 생각을 했습니다
루트에는 [시작 ~ 끝]범위의 해시값이 들어갑니다!
위의 그림은 블록인포를 통해 블록을 확인한 모습입니다
블록인포를 통해 최근에 생성된 블록을 보시면
머클루트가 기록 되어 있습니다
위 그림은 블록헤더의 구조를 보여줍니다
이 머클루트는 위에 보시는 것처럼 블록헤더에 저장됩니다
그럼 비트코인에서는 어떤식으로 머클트리를 쓸까요?
전체적인 큰 그림을 알려드리겠습니다!
우선 사전지식으로 풀노드와 라이트 노드를 알아야 합니다
풀노드는 말그대로 첫번째블록부터 모든 내용이 저장된 노드입니다
라이트 노드는 특정 거래들만 저장된 노드입니다
라이트 노드는 이웃에 있는 풀노드에게 블롬필터 라는 것을 설치합니다!
그럼 그 필터를 통해 필요한 트랜잭션들만 얻게 됩니다
이때 풀 노드는 트랜잭션과 함께 블록헤더와 머클경로를 넘깁니다
여기서 머클경로는 위 그림의 파란색 노드 이고 필요한 트랜잭션을 초록색
노드로 보시면 이해하기 편합니다
저희는 이 초록색 노드의 위변조 검사를 할 예정입니다
아까 처음에 머클트리는 2개씩 짝을 지어 해시해 나간다고 했는데
이 때 엄청난 공간효율을 얻습니다
위변조 검증을 위해 모든 노드가 필요한 것이 아니라
머클경로(파란노드)만 필요로 합니다
그럼 짝을 지어 해싱해 나갈 수 있고 머클루트를 얻을 수 있습니다
그럼 풀노드가 던져 준 블록헤더에 있는 머클루트와 비교해 볼 수 있습니다!
그리고 일치한다면 위변조가 없고 이 트랜잭션이 블록에 포함된다는 것을
알 수 있습니다!
이게 머클트리 사용의 큰 그림입니다
머클트리는 이진트리이기 때문에 최악의 경우에도 lgN개 만큼의 노드만
있으면 머클루트를 구할 수 있습니다
위의 표를 보시면 머클루트를 사용했을 때 이득을 쉽게 이해할 수 있습니다
트랜잭션이 커져서 16메가의 트랜잭션이 있어도 위변조를 검사할 때는
512바이트의 트랜잭션만 있으면 되는 겁니다!
다들 머클트리를 사용했을 때의 장점을 이해하셨나요
설명이 부족했을 수 있는데
댓글로 틀린내용과 부족한 부분 알려주시면 감사하겠습니다!
아래에서는 waca님이 작성하신 코드를 이용해 머클트리를 이해해봅시다!
먼저 트리를 만드는 코드입니다
벡터에 해쉬된 트랜잭션 값을 다 넣어둡니다
그리고 for문을 통해 2개씩 묶어 해시를 하고
트리의 한층씩 올라가며 반복해 루트까지 올라갑니다
그리고 트리가 비었다면 0 , 아니라면 루트를 리턴합니다
push_back을 하기 때문에 머클루트는 맨 뒤에 있을 것 입니다
그림으로 나타낸다면 이런 모습이 됩니다
0번 인덱스부터 꽉 차서 마지막 13번 인덱스에는 머클루트가 들어갑니다
이 부분은 위변조 검사를 할 때 필요한 노드를 추출하는 코드 입니다
한 마디로 머클경로를 얻는 코드입니다
nIndex^1 이 코드가 보이시나요?
이걸 이용하면 짝수일때 홀수, 홀수일때 짝수가 나옵니다
그러면 나의짝을 계속 저장할 수 있습니다
마지막으로 위변조를 검사하는 코드 입니다
위에서 구한 머클경로를 가져와 계속 해시를 해보느 코드입니다
그리고 마지막에 해시값을 리턴 해 줍니다!
머클트리의 원리를 완벽하게 이해한다면 코드를 이해하기 쉬울 것 입니다!
근데 머클트리에 문제는 없을까요?
머클트리에도 문제는 존재합니다
예를들어 위와같은 트리가 있다고 합시다
머클트리에서 홀 수 일때는 마지막 노드가 자기자신과 해시를 합니다
결국 위에 트리는 F가 1개일 때와 2개일 때 값이 같아지므로
같은 머클루트를 같습니다
이 때 누군가가 고의로 validation이 실패하는 블록을 보낸다면
정상적인 블록을 invalid하다고 판단할 수 있다고 합니다
중복때문에 생기는 문제를 잘 이해하지 못해서 좀 더 공부가 필요합니다..
댓글로 알려주실분..ㅠㅠ 알려주시면 감사하겠습니다
저도 완벽하게 이해를 못하겠습니다..!
위와같이 문제가 생길 수 있기때문에 비트코인에서는 중복을 검사합니다
바로 위 코드는 실제 비트코인 깃허브에서 가져온 코드입니다
처음에 mutated는 null값이지만 만약 중복된 서브트리가 찾아진다면
true로 값을 바꿔 보냅니다
위 코드도 비트코인 깃허브에서 가져온 코드 입니다
만약 mutated가 true로 넘어왔다면 따로 mutation을 검사합니다
그리고 문제가 있다면 mutation을 true로 바꿉니다!
뒤의 코드는 다 보지 못했지만
중복이 있고 없고를 판단해 따로 처리할 것으로 보입니다!
이렇게 머클트리에 대해 알아봤는데 이해가 잘되실지 모르겠습니다!
저도 공부를 하는 사람이라 틀린 내용이 있을 수 있습니다 ㅠㅠ
틀린내용과 보충할 내용 댓글로 알려주시면 감사하겠습니다!
'블록체인' 카테고리의 다른 글
| 머클패트리샤트리(Merkle patricia tree)에 대해 알아보자 (0) | 2018.10.08 |
|---|---|
| 이더리움 스마트 컨트랙트 보안 취약점 (0) | 2018.10.03 |