머클트리 (Merkle tree)
비트코인 때부터 블록체인과 뗄 수 없는 머클트리는 두가지 역할을 한다. 첫번째는 머클트리의 루트(root)를 비교하여 두 자료가 동일한지 확인할 수 있다. (서로 다른 자료가 동일한 머클트리 루트를 만들 가능성, 즉 해시충돌(hash collision)은 우주에 숨겨둔 어떤 원자를 찾을 확률 정도로 매우 낮다.) 그러나 자료가 동일한지는 굳이 트리를 만들지 않고 자료 전체를 해시해서도 알 수 있다.
머클트리의 더 중요한 두번째 역할은 트리에 어떤 자료가 들어있는지 증명하는 기능이다. 증명하고 싶은 자료부터 위로 올라가며 중간값들을 모으면 머클경로(Merkle path) 혹은 머클증명(Merkle proof)가 된다. 상대방은 머클트리 전체 내용을 몰라도 머클증명으로 다시 머클트리 루트를 계산하고, 자신이 이미 알고 있는 루트와 비교하여 증명을 검증할 수 있다. 해시충돌 확률이 매우 낮기 때문에 실제로 없는 자료가 있다고 속이는 머클증명을 만들 수 없다.
블록체인는 머클트리를 많이 활용한다. 먼저 블록에 담긴 트랜잭션들을 트리로 만들어서 루트를 블록 헤더에 저장한다. 경량 클라이언트(light client)는 블록 내용을 모두 저장하지 않고 크기가 작은 블록 헤더만 저장하여 운영 비용을 줄인다. 블록 헤더에 있는 루트를 알기 때문에 블록을 모두 저장하지 않더라도 어떤 트랜잭션이 블록에 담겨있는지 머클증명으로 (다른 서비스를 신뢰하지 않아도) 안전하게 검사할 수 있다. 토큰을 다른 체인으로 이동하는 브리지도 머클트리를 사용한다. 브리지는 암호화폐가 브리지 계정으로 전송되었는지 확인하고 다른 체인으로 옮긴다. 다른 체인은 브리지 계정으로 전송한 트랜잭션이 존재하는지 머클증명으로 검사한다.
https://en.wikipedia.org/wiki/Merkle_tree
