머클 트리 (Merkle tree)

  • 머클 트리는 일련의 ‘데이터 무결성’을 효과적으로 검증(증명)하는 데 사용되는 구조이다

  • 머클 트리 구조의 핵심에는 ‘해시 함수’가 있다

  • 머클 트리는 데이터를 여러 조각으로 나누며 생성되며,

  • ‘머클 루트’를 형성하기 위해 반복적으로 해시화된다

  • 이후 데이터 조각이 잘못된 경우, 이를 효율적으로 검증(수정)할 수 있다

  • 큰 장점은 하위 트리를 분석하여 데이터가 트리 내에 있는지 쉽게 확인할 수 있다

  • 거래내역을 확인하기 위해 전체 정보를 비교하며 특정 트랜잭션이 위변조 되었는지 확인하는 것은 비효율적이므로 ‘머클트리’ 를 이용해 신속하고 효율적으로 조회한다

머클 트리의 동작 원리

  • 머클 트리로 파일을 ‘덩어리로 분리’ 한다

  • ex) 파일이 50GB였다면, 100개의 조각으로 나뉠 수도 있다

  • 이렇게 조각낸다면 한 조각의 크기는 각 0.5GB 가 된다

  • 이후 파일은 ‘조각별로 다운로드’ 된다
    👉 이런 형태의 다운로드는 토렌트에 파일을 공유할 때도 사용된다

머클 루트(Merkle Root)

이렇게 파일을 다운로드 하면,
이 자료는 ‘머클 루트(Merkle Root)’ 라는 해시를 제공한다

  • 다운로드 하고자 하는 파일의 해시가 개발자에 의해 공개된 것과 일치하는지 확인해야 한다

  • 두 해시가 일치한다면, 컴퓨터에 존재하는 파일이 개발자들의 것과 정확히 일치한다고 말할 수 있다

  • 머클루트가 중요한 이유는 데이터 유효성의 검증 때문이다 (유효성 검증 속도는 OLog₂N)
    👉 ‘머클 루트’ 를 사용하면, 훨씬 간단하게 데이터를 검증할 수 있다

  • 8GB 파일을 여덟 조각으로 나눠 사용하는 경우

  • 각 조각들은 ‘해시 함수’ 를 통과하여 8개의 다른 ‘해시를 제공’한다 👆

  • 여덟 개 조각들의 해시들을 얻기 위해 이를 해시 함수에 통과시킨다 👆

  • 이렇게 생성된 8개의 해시를 다시 2개씩 묶어 해싱한다

👉 hA + hB / hC + hD / hE + hF / hG + hH 를 해싱하면,
👉 4 개의 해시 hAB / hCD / hEF / hGH 를 가지게 된다
👉 이 방식을 반복해 마지막 하나의 해시, 머클 루트(루트 해시) 를 얻을 수 있다

만약 해시값이 하나라도 다른 값을 나타낸다면,
데이터가 ‘위변조’되었을 수 있다고 확신할 수 있다
(데이터를 조금만 수정하더라도 전혀 다른 머클 루트를 가지게 됨)

‘머클 트리’ 를 사용중에 파일을 전송받는 과정에서 ‘데이터에 변경’이 생겼다면,
데이터에 변경이 일어난 파일 조각을 찾고,
그 파일만 새롭게 다운로드 받을 수 있다

👉 ex) 위 그림에서 ‘hE’ 에 결점이 있다고 했을때,

전달받은 두 개의 해시값(hABCD / hEFGH) 중에서,
‘hEFGH’ 에 문제가 있다는 것을 확인할 수 있고,
마지막으로 ‘hE’ 를 해시한 파일 조각만 다시 다운로드하면,
파일 전송을 보다 효율적으로 할 수 있게 된다

쇄도 효과(avalanche effect)

하나의 트랜잭션이 변조되면 머클 루트까지 모든 값이 바뀌게 된다

이러한 현상을 ‘쇄도 효과(avalanche effect)’라고 한다

트랜잭션 검증

모든 블록의 트랜잭션을 다운로드하고 ‘해시화’ 하고 싶지 않을 수 있다

  • 풀 노드로부터 트랜잭션이 특정 블록 안에 있음을 입증하는 증거인 머클 증명을 요청할 수 있다
  • 이를 단순화된 결제 검증 (SPV, Simplified Payment Verification) 라고 한다

TXID가 ‘hD’인 트랜잭션이 이 블록 안에 포함되어 있는지를 머클트리를 사용해 검증하는 예시 👆

1. hD 와 같은 청크로 묶인 hC 를 가져오고
2. hABCD 를 계산하기 위해 hAB 도 가져온다
3. hAB 와 hCD 를 사용해 hABCD 를 구하고
4. 머클루트인 hABCDEFGH 를 계산하기 위해 hEFGH 를 가져온다
5. hABCD 와 hEFGH 를 사용해 hABCDEFGH 를 구한다

👉 ‘hABCDEFGH’ 의 값이 실제 블록헤더에 저장된 머클루트 값과 같다면,
👉 해당 트랜잭션이 블록에 포함되어 있다는 것을 의미한다

(머클 트리가 없었다면 ‘7번’을 진행해야 했을 것을 ‘3번’만에 검증했다)

👉 블록에는 수천 개의 트랜잭션이 포함되기 때문에,
👉 머클 증명을 사용하면 상당한 시간과 컴퓨터 자원이 절약된다

머클 패트리샤 트리(Merkle Patricia Tree)

‘이더리움’ 에서는 모든 트랜잭션의 완전한 모델을 만들기 위해
머클 패트리샤 트리 Merkle-Patricia-Tree (trie) 방법을 사용한다

  • 머클-패트리샤는 연관 배열을 저장하기 위해 ‘키’🔑 (일반적으로 문자열로 정의됨) 를 사용하여 이를 향상시킨다

  • 노드는 키🔑와 연결된다

  • 이것은 ‘디지털 트리’인 ‘트라이(trie)’로 정의된다

  • 이것은 각 노드의 실제 ‘키🔑’가 저장되지 않지만

  • 트리에서의 위치가 ‘키🔑’를 정의하는 데 사용된다는 점에서 머클 트리와 다르다

머클 패트리샤 트리 특징

  • 이더리움의 전역상태는 계정 주소와 계정 상태를 매핑한 것으로 구성되어 있다

  • 부모 노드는 ‘두 자식 노드를 모아’ 해싱한 값을 가진다

  • 자식 노드의 값이 ‘조금이라도 바뀌면’ 부모 노드의 값도 바뀐다

  • 이더리움 블록 헤더는 상태트리 / 트랜잭션 트리 / 영수증 트리 세 트리의 루트 노드 해시값이 저장되어 있다

  • 블록 헤더에 루트 노드들의 값을 가지고 있지만, 이더리움의 ‘상태 일부분을 검증’ 할 수 있다
  • 트리 ‘맨 아래’에 있는 노드들은 데이터를 가지고 있다