머클의 해시 트리는 소수의 해시만으로 하나의 레코드가 거대한 파일 안에 있음을 증명한다

어떤 레코드가 거대한 데이터셋의 일부임을 증명하는 것은 보통 데이터셋을 전송하는 것을 의미했다. 이는 백업, 트랜잭션 파일, 또는 웹 캐시에는 비현실적이다.

머클의 1979년 박사 학위 논문과 1989년 논문은 모든 블록이 해시되고 해시들이 짝지어져 하나의 루트만 남을 때까지 이어지는 트리를 설명한다. 구성원을 검증하려면 파일이 아니라 경로상의 log n개 해시만 있으면 된다.

이 트리는 멤버십 검사를 루트에 대한 동등성 검사로 바꾸며, 어디서든 변경이 생기면 변경된 경로로 나타난다. 이는 모든 바이트를 보지 않고도 전체 데이터 구조를 보증할 수 있는 방식이다.

짝지어 해시하여 하나의 루트에 이를 때까지 리프에 커밋한다

증명 크기가 로그적이므로, 가장 큰 데이터셋에서도 검증이 저렴하게 유지된다.

루트가 전체 데이터셋에 커밋하므로, 어떤 변조든 탐지된다.

검증자는 서버에 대한 신뢰 없이 루트와 짧은 경로만 있으면 된다.

일방향 해시의 연쇄이므로, 데이터에 대한 어떤 정보도 노출되지 않는다.

거대한 전체에 대한 사실을 증명하려면, 전체를 보내지 말라. 그것을 하나의 다이제스트로 축약한 다음, 그 하나의 주장을 그 다이제스트에 연결하는 짧은 경로만 제공하라.

머클 트리는 Git, 암호화폐 블록체인, 인증서 투명성, 분산 저장소의 기초가 된다. 이는 클라이언트가 하나의 짧은 루트만 신뢰함으로써 크고 인증되지 않은 저장소의 작은 조각을 검증할 수 있게 한다.