이 문서는 Blockchain 에 있는 문서와 동일합니다.
Merkle Tree
Merkle Tree 혹은 Hash Tree 로 불리는 자료구조는 주로 데이터 변조가 발생했는지 확인하는 용도로 사용됩니다.
- Block 에 포함된 Transaction 의 Hash 를 구합니다.
- 2개 씩 Hash 를 묶어 새로운 Hash 를 구합니다. (짝이 맞지 않다면 마지막 Hash 를 복제합니다.)
- (2)의 결과에 다시 2개 씩 Hash 를 묶어 새로운 Hash 를 구합니다. 이를 반복하여 Hash Tree 를 구성합니다.
Tx3 이 블록에 포함되어 있는지 확인하려면, 아래 과정을 거칩니다.
- Hash AB 와 Hash D, 그리고 Merkle Root 인 Hash ABCD 를 전체 데이터를 가지고 있는 Full Node 로 부터 받습니다.
- 서로 다른 Full Node 에서 데이터를 교차 전송 받아 Hash 의 진실 여부를 검증할 수도 있습니다.
- Tx 3을 Hash 한 뒤, Hash D와 묶어 Hash 합니다. 결과는 Hash CD 가 됩니다.
- Hash AB와 Hash CD를 Hash 하여 Hash ABCD 를 얻습니다. Hash ABCD 가 Merkle Root 와 다르다면, Tx 3은 이 블록에 포함되어 있지 않습니다.
블록 내 모든 Tx 를 한번에 Hash 하는 것에 비해 과정은 더 복잡 할 수 있지만, 한번에 Hash 를 취하면, 검증을 하기 위해 블록 내 모든 Transaction 데이터가 필요하게 됩니다.
Merkle Tree 의 특성을 활용하면 Full Node 가 아니어도 적은 비용으로 Transaction 의 검증을 수행할 수 있으며, 일부 데이터만을 가지고 있는 Light Node 가 존재할 수 있도록 합니다.
Bitcoin White Paper 에서는 Reclaiming Disk Space 및 Simplified Payment Verification (SPV) 를 Merkle Tree 를 이용해 제안하고 있습니다.
Reference
- Bitcoin: A Peer-to-Peer Electronic Cash System
- Merkle, Ralph (1987). "A Digital Signature Based on a Conventional Encryption Function"