Merkle tree

해시 트리 또는 머클 트리라고 불리는 자료구조는 모든 리프 노드에 데이터 블록의 암호화 해시가 레이블로 지정되고 리프가 아닌 모든 분기 노드에 해당 하위 노드 레이블의 암호화 해시가 레이블로 지정되는 트리 구조이다. 해시 트리를 사용하면 대규모 데이터 구조의 내용을 효율적이고 안전하게 검증할 수 있다.

리프 노드가 주어진 이진 해시 트리의 일부임을 증명하기 위해선 트리의 리프 노드 수의 log값에 비례하는 해시 수를 계산해야 한다. 반대로 해시 목록에서는 리프 노드 자체의 수에 비례하는 해시 수를 계산한다. 따라서 해시 트리는 트리의 루트가 커미션으로 간주되고 리프 노드가 원래 커미션의 일부인 것으로 증명될 수 있는 암호화 커미션 체계의 효율적인 예이다. 일반적으로 해싱에는 SHA-2와 같은 암호화 해시 함수가 사용된다.

해시 트리는 컴퓨터 내부와 컴퓨터 간에 저장, 처리 및 전송되는 모든 종류의 데이터를 검증하는데 사용할 수 있다. P2P 네트워크에서 다른 피어가 수신한 데이터 블록이 손상되지 않고 변경되지 않았는지 확인하고, 다른 피어가 거짓말을 하거나 위조 블록을 보내지 않았는지 확인하는데 도움이 될 수 있다.