[Data-Structure] 머클트리(Merkel Tree)

 

 

---

머클 트리 :

 

머클 트리는 1979년 랄프 머클(Ralph Merkle)에 의해 발명된 이진트리 구조로, 암호학적 해시 함수를 이용하여 대량의 데이터를 효율적으로 검증할 수 있도록 설계되었다.

 

블록체인과 분산 시스템에서 핵심적인 역할을 하며, 데이터 무결성을 보장하는 강력한 도구로 사용된다.

 

 

 

 

머클 트리 구조 :

머클 트리는 다음과 같은 트리 구조를 가지고 있다.

 

[출처 : https://www.banksalad.com/contents/%EC%89%BD%EA%B2%8C-%EC%84%A4%EB%AA%85%ED%95%98%EB%8A%94-%EB%B8%94%EB%A1%9D%EC%B2%B4%EC%9D%B8-%EB%A8%B8%ED%81%B4%ED%8A%B8%EB%A6%AC-Merkle-Trees-%EB%9E%80-ilULl]

 

 

 

 

 

머클 트리가 만들어지는 순서 :

 

1. 해시 계산: 말단의 각 데이터 블록에 대해 암호학적 해시 함수(SHA-256 등)를 적용하여 고정 길이의 해시값을 생성

 

 - 위 사진 기준으로, 거래 (1)과 거래 (2)와 같은 Leaf Node의 해시 값을 생성

 

 

2. 페어링: 인접한 두 해시값을 이용하여 상위 노드를 생성

 

 - 거래 (1)과 거래 (2)에서 생성된 각각의 해시 값을 합치며, 다시 해싱을 하고 해당 값을 상위 노드로 지정한다.

 

 

3. Root Node까지 재귀적 해싱: 연결된 값을 다시 해시하여 상위 레벨의 노드를 생성

 

- 거래 (1+2)의 해시 값과 1,2번의 과정에서 생성된 거래 (3+4)의 해시 값을 활용하여 재귀적으로 상위 노드를 생성한다.

 

 

 

 

주요 특징 :

 

1. 효율적인 검증

• 특정 데이터를 검증하는데, 전체 데이터가 필요하지 않음(일부 브랜치 노드와 리프 노드를 활용하여 검증)
• O(log n) 시간 복잡도로 검증이 가능

 

2. 데이터 무결성 보장

• 단일 비트의 변경도 루트 해시를 변경하여 감지가 가능

 

3. 저장 공간 절약

• 루트 해시만 저장하여 활용이 가능하고, 특정 데이터 검증 시에도 일부 데이터로 검증

 

4. 병렬 처리 지원

• 트리의 각 부분을 독립적으로 계산 가능하여, 대용량 데이터 처리에 유리

 

 

 

 

활용 사례 :

 

- 블록체인: 각 블록의 거래들을 머클 트리로 구성하여 블록 헤더에 머클 루트를 저장

 

- 분산 시스템: Apache Cassandra는 데이터 복제본 간의 불일치를 머클 트리로 검증

 

- 클라우드 스토리지: Aws S3와 같은 Object Storage에서 객체 무결성 검증에 머클 트리를 사용

 

 

---