안녕하세요. 암호화폐 관한 지적 대화를 위한 넓고 얇은 지식 시리즈를 연재하고 있는 흑두루미 개발자입니다.
요즘 존버하기가 쉽지 않습니다. 매일 탈탈 털리는 멘탈 덕에 스팀잇에 올린 포스트를 한달 가까이 잊어버리고 살다가 지금에서야 포스팅하게 되었습니다.
- 해시 알고리즘
- 머클 트리 (본편)
- 비트 코인, POW의 해답인 Nonce? (예정)
- 암호 알고리즘, 공인 인증서 그리고 전자 서명 (예정)
- 왜 POW, 채굴에는 GPU를 사용하는가? (예정)
이번에 다룰 주제는 해시 알고리즘 응용의 결정체인 머클 트리(Merkle Tree)입니다.
비트코인에서 머클 트리는 한 블럭 안의 모든 거래를 하나의 해시값으로 요약할 수 있게 해주며, 최근 이더리움의 비탈릭 부테린과 EOS의 댄 라리머의 논쟁에서도 등장합니다.
비탈릭은 EOS의 처리속도가 빠른 이유가 중요 프로토콜의 구현을 빠뜨렸기 때문이며, 그 중 대표적으로 빠뜨린 것이 머클 트리라고 댄을 디스하기도 했었습니다.
머클 트리는 가장 말단을 제외한 노드(non-leaf node)들이 자식 노드의 정보를 해시한 값으로 이루어진 이진 트리(Binary Tree)이며, 발명자 랄프 머클(Ralph Merkle)이 1979년에 특허 출원했다고 합니다.
위키 백과에서 발췌한 머클 트리의 정의입니다.
랄프 머클은 발명자 이름이고, 해시라는 용어는 지난 강좌인 해시 알고리즘 편에서 언급했으니 이진 트리라는 용어를 이해하고 넘어가야겠군요.
트리(tree)는 노드(node)라고 부르는 공간에 데이터를 저장하며 이름 그대로 나무의 구조를 본따 만들어서 뿌리(Root Node), 마디(Internal Node) 그리고 잎(Leaf Node)으로 이루어져 있습니다.
그런데 나무는 아래에서 위로 자라지 않나요? 지구는 둥그니까 이렇게 아래로도 자랄 수 있나 봅니다.
그럼 트리는 트리인데, 이진 트리(Binary Tree)라는 것은 무엇일까요?
0 그리고 1, 2개의 기호만 사용하는 이진법(binary)처럼 모든 노드가 자식 노드를 2개만 가질 수 있는 트리를 이진 트리라고 합니다. 왜 자식 노드를 2개만 가지냐 하면 말이죠.
14라는 값을 검색하려면 root(10)에서 시작하여
- 10보다 14가 크기 때문에 오른쪽 node인 17을 선택합니다.
- 17보다 14가 작기 때문에 왼쪽 node인 14를 선택합니다.
- 선택한 14는 검색하려는 14와 같은 값이므로 검색을 완료합니다.
이 이진 트리는 검색 시간을 단축하기 위하여 노드의 값들을 크기 순으로 미리 수평 정렬한 이진 탐색 트리(Binary Search Tree)입니다.
값이 1, 5, 6, 21인 노드들을 배제하고 검색하여 시간을 단축할 수 있으며 이러한 원리는 데이터베이스에서 검색을 최적화하는 인덱싱에 활용되기도 합니다.
드디어 본론인 머클 트리가 등장합니다.
최하단에 위치한 거래 노드(Transaction: Tx0, Tx1, Tx2, Tx3)들을 제외한 모든 노드들이 해시 값을 가지고 있고 또 자식 노드들을 2개씩 가지고 있어서 이진 트리 형식을 만족합니다.
비트 코인에서 한 블럭 안의 모든 거래는 머클 루트라는 하나의 값으로 요약됩니다.
이 머클 루트 값을 구하려면 위 머클 트리에 표시한 Step 1, Step 2, Step 3 순으로 차례대로 해시하면 됩니다. 백문이 불여일타라고 직접 따라해 보시면 이해에 도움이 될겁니다.
Step 1.
앞선 그림에서 거래 노드 중 하나인 Tx0은 철수가 영희에게 1비트 코인을 전송했다는 의미로 “From:철수,To:영희,BTC:1” 라고 표현했습니다.
이러한 거래 내용은 비트 코인에서 스크립트 형식을 사용하는데, 실제로는 이것보다 더 복잡합니다만 쉬운 예를 들기 위해 간략한 형식으로 표현했습니다. 실제 비트 코인에서 사용하는 스크립트를 알아보시려면 https://en.bitcoin.it/wiki/Script을 참고하세요.
http://www.whatsmyip.org/hash-generator/ 사이트로 가서 Input String란에 “From:철수,To:영희,BTC:1” 를 입력하고 Calculate Hashes 버튼을 클릭하면 아래처럼 해시 값들이 출력됩니다. 이왕이면 비트 코인에서 사용되는 sha256 해시 알고리즘으로 진행해보겠습니다.
H0 노드 = sha256(From:철수,To:영희,BTC:1) = e7857935216b41146f9fbabd1a160d3f1bc72df953af73648c4dacd70ac2bc10
같은 방식으로 나머지 Tx1, Tx2, Tx3 노드들도 해시합니다.
H1 노드 = sha256(From:수빈,To:민준,BTC:0.5) = 8806b9cb998d8c4af11eab07edccc4c57b9707d31b5aed8e58fca1dacc4286fcH2 노드 = sha256(From:서현,To:민준,BTC:0.5) = d3a225ad5e015148d258b1c274b88b219d078640e9a378647020d2ecb066894aH3 노드 = sha256(From:영희,To:민준,BTC:1) = 28d2473120a1416808573526f366526d834a39633ff90905bd9570e015638d07
Step 2.
이제 H01 노드와 H23 노드에 들어갈 해시 값을 구해보겠습니다.
H01 노드의 자식 노드는 H0 노드와 H1 노드이므로, H0 노드의 값과 H1노드의 값을 합쳐서 해시하면
H01 노드 = sha256(e7857935216b41146f9fbabd1a160d3f1bc72df953af73648c4dacd70ac2bc108806b9cb998d8c4af11eab07edccc4c57b9707d31b5aed8e58fca1dacc4286fc) = 920ff9d5d117f524a8cae4e946dff5da453af5a7bb4f626765814e06a308aec6
마찬가지로 H23 노드의 자식 노드는 H2 노드와 H3 노드이므로
H23 노드 = sha256(d3a225ad5e015148d258b1c274b88b219d078640e9a378647020d2ecb066894a28d2473120a1416808573526f366526d834a39633ff90905bd9570e015638d07) = b1092378e647e31bf2798600b293199bb0079c7c638435d1beacde341a2caeac
Step 3.
이제 머클 루트 노드만 남았습니다. 루트 노드의 자식 노드는 H01 노드와 H23 노드이므로
머클 루트 = sha256(920ff9d5d117f524a8cae4e946dff5da453af5a7bb4f626765814e06a308aec6b1092378e647e31bf2798600b293199bb0079c7c638435d1beacde341a2caeac) = 4d412dc62c412e9ad3c2d378ddbccf52bbc6438bde2782a2b3702f48b639cf54
지난 강좌인 해시 알고리즘 편에서 언급했듯이 해시 알고리즘은 입력 값의 길이에 상관 없이 출력 값의 길이는 항상 일정합니다. 따라서 최하단의 거래 노드들을 제외한 모든 노드들이 가지는 해시 값 길이는 64문자(16진수)로 모두 같습니다.
수고하셨습니다. 이렇게 구한 머클 루트 값은 아래 비트코인 블럭의 블럭 헤더(Block Header)에 빨간 박스로 표시한 Root Hash(Merkle Root) 영역에 저장됩니다.
(이 구조는 다음 강좌인 “비트 코인, POW의 해답인 Nonce?” 편에 자세히 다룰 예정입니다)
루트 해시 값 하나로 한 블럭에 담겨있는 모든 거래들의 위변조를 검증할 수 있습니다. 최하단의 거래 노드 중 하나만 변조되어도 트리 구조의 특성상 루트 해시 값은 바뀔 수 밖에 없기 때문입니다.
그리고 이렇게 완성된 하나의 블럭은 다른 블럭과 연결됩니다. 다들 아시다시피 이 구조를 블록체인(Blockchain)이라고 부릅니다.
출처: https://bitcoin.org/bitcoin.pdf
다음 편 예고
거래 장부들에 따르면, 철수는 영희에게 소중한 1비트 코인을 선물로 전송했고, 수빈과 서현은 민준에게 0.5비트씩 모두 1비트 코인을 전송했습니다. 그리고 영희는 철수에게 받은 1비트 코인을 민준에게 선물로 전송했습니다.
이 사실을 알고 분노한 우리의 흑우 철수는 능력자 민준에게 복수를 다짐하며 거래 장부 Tx0을 “From:민준,To:철수,BTC:2”로 조작하여 민준이 받은 2비트 코인을 모두 자신에게 전송할 계획을 세웠습니다.
이번 편에서 머클 트리를 학습한 철수는 Tx0 거래 노드에 연결된 모든 노드들(H0, H01, 머클 루트)의 해시 값을 모두 해킹하여 바꾸려고 할 것입니다.
과연 철수의 복수는 이루어질 것인지 아니면 다음에 연재할 “비트 코인, POW의 해답인 Nonce?” 편에서 블록체인의 실체를 마주하고 목이 돌아갈까요? To be continued...
본글의 저작권은 저자에게 있으며, 저자의 허가없는 사용 및 도용을 금지하니 양해 바랍니다.
긴 글 읽어주셔서 감사합니다.
다음편도 기대되네요...철수가 해쉬값을 바꾸려고 하는 노력과 비용이 2BTC보다 훨씬 커서 실패하지 않을까요? 잘모르겠네요 기대됩니다.