머클트리

비트코인에서의 머클트리와 이더리움에서의 머클트리의 구조는 다소 차이가 있다.

 

우선 머클 트리(Merkle Tree)는 블록체인 기술에서 데이터의 무결성을 검증하는 데 사용되는 데이터 구조이다. 이 구조는 특히 거래 데이터의 무결성을 효율적으로 검증하기 위해 설계되었다. 여기서 "무결성"이란 데이터가 변경되지 않았음을 의미한다.

 

비트코인 머클트리

• 머클 트리의 기본 원리
  • 머클 트리는 기본적으로 이진 트리 구조를 가지며, 각 노드는 자식 노드의 해시값을 합친 후, 그 결과를 다시 해시한 값으로 구성된다. 이 과정은 트리의 최상단에 도달할 때까지 반복되며, 최상단에 위치한 노드를 "머클 루트"라고 한다.
• 거래 해시와 머클 트리
  • 1. 거래 해시화: 블록 내의 각 거래는 해시 함수를 통해 고유한 해시값으로 변환된다. 이 해시값은 거래의 디지털 지문과 같은 역할을 한다.
  • 2. 트리 구성: 이 해시값들은 이진 트리 형태로 정렬된다. 가장 가까운 두 거래의 해시값을 합쳐(이를 '부모 노드'라고 함) 새로운 해시값을 생성하고, 이 과정을 트리의 모든 레벨에 대해 반복한다.
    • 이진트리 : 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조
  • 3. 머클 루트 생성: 최종적으로, 트리의 최상단에 도달하여 단 하나의 해시값, 즉 머클 루트가 생성된다. 이 머클 루트는 블록 내 모든 거래의 요약 정보를 담고 있다.
• 머클 트리의 장점
  • 데이터 무결성 검증: 머클 루트를 통해 블록 내의 모든 거래 데이터가 변경되지 않았음을 효율적으로 검증할 수 있다. 블록 내의 어떤 데이터라도 변경되면, 그 변경은 머클 루트에 반영되어 머클 루트의 값이 달라진다.
  • 효율성: 전체 거래 데이터를 다운로드하지 않고도 특정 거래가 블록 내에 포함되었는지를 검증할 수 있다. 이는 "경량 노드"나 "SPV(Simplified Payment Verification) 클라이언트"가 전체 블록체인을 다운로드하지 않고도 거래를 검증할 수 있게 한다.
• 예시
  • 블록 내에 4개의 거래(A, B, C, D)가 있다고 가정해보자. 각 거래의 해시값을 HA, HB, HC, HD라 한다. 이 해시값들을 이용해 머클 트리를 구성하면 다음과 같은 과정을 거친다:
    • 1. HA와 HB의 해시값을 합쳐 HAB를 생성, HC와 HD의 해시값을 합쳐 HCD를 생성
    • 2. HAB와 HCD를 합쳐 최종 머클 루트를 생성
  • 이 과정을 통해, 블록 내의 모든 거래 정보를 단 하나의 해시값(머클 루트)내의 모든 거래 정보를 단 하나의 해시값(머클 루트)으로 요약할 수 있다. 이 머클 루트는 블록 헤더에 포함되어 블록체인 네트워크 전체와 공유한다. 머클 트리의 구조 덕분에, 블록 내의 어떤 거래 데이터가 변경되면, 그 변경은 머클 루트의 값에도 반영되어, 머클 루트의 값이 달라지게 된다. 이는 블록 내의 데이터 무결성이 보장됨을 의미한다.
• 머클 트리를 통한 검증 과정
  • 머클 트리를 사용하면, 전체 거래 목록을 다운로드하지 않고도 특정 거래가 블록에 포함되었는지를 검증할 수 있다. 예를 들어, 거래 A가 블록에 포함되었는지 확인하려면, 거래 A의 해시값(HA)과 거래 A를 검증하기 위해 필요한 "머클 경로"만 있으면 된다.
  • 머클 경로는 특정 거래를 머클 루트까지 연결하는 데 필요한 모든 해시값의 집합. 이 경로와 거래 A의 해시값을 사용하여, 머클 루트를 독립적으로 계산하고, 이 계산된 머클 루트가 블록 헤더에 저장된 머클 루트와 일치하는지 확인함으로써 거래 A의 포함 여부를 검증할 수 있다.
• 머클 트리의 파급 효과
  • 블록 내의 하나의 데이터가 변경되면, 해당 데이터의 해시값이 변경되고, 이는 부모 노드의 해시값 변경으로 이어진다. 이 변경은 머클 트리를 따라 최상위 노드인 머클 루트까지 전파된다. 따라서, 머클 루트의 값이 달라지게 되며, 이는 블록 내의 데이터가 변경되었음을 즉각적으로 알 수 있는 강력한 지표가 된다.
• 결론
  • 머클 트리는 블록체인 기술에서 데이터 무결성을 효율적으로 검증할 수 있는 중요한 메커니즘이다. 이를 통해 블록체인 네트워크는 높은 수준의 보안과 투명성을 유지할 수 있으며, 사용자는 블록 내의 거래가 변경되지 않았음을 신뢰할 수 있다.

 

 

이더리움의 머클 트리 구조

 

이더리움은 비트코인과는 다르게, 머클 패트리샤 트리(Merkle Patricia Tree, MPT)라는 특별한 형태의 머클 트리를 사용한다. 이 구조는 데이터의 저장, 검색, 수정이 빈번하게 발생하는 이더리움의 특성을 고려하여 설계되었다. 머클 패트리샤 트리는 효율성, 보안성, 그리고 유연성을 제공한다.

머클 패트리샤 트리의 특징

 

1. 트라이(Trie) 구조: MPT는 트라이의 한 형태로, 키-값 쌍을 저장하는 검색 트리이다. 이더리움에서는 이 구조를 사용하여 상태(state), 트랜잭션, 영수증의 데이터를 저장한다.

2. 경로 압축: MPT는 경로 압축을 사용하여 노드 간의 경로를 최적화하고, 저장 공간을 절약한다.

3. 세 가지 유형의 노드: MPT는 리프 노드(leaf node), 확장 노드(extension node), 분기 노드(branch node)의 세 가지 유형의 노드를 가진다. 이를 통해 효율적인 데이터 저장 및 검색이 가능하다.

 

이더리움에서의 사용

이더리움은 세 가지 주요 유형의 머클 패트리샤 트리를 사용한다:

 

1. 상태 트리(State Trie): 모든 계정의 상태(잔액, 스토리지, 코드, nonce)를 저장한다. 각 블록 후의 최종 상태가 이 트리에 저장된다.

2. 트랜잭션 트리(Transaction Trie): 블록 내의 모든 트랜잭션을 저장한다. 이를 통해 특정 트랜잭션이 블록 내에 포함되었는지 검증할 수 있다.

3. 영수증 트리(Receipts Trie): 각 트랜잭션의 실행 결과를 저장하는 영수증을 포함한다. 이는 트랜잭션이 성공적으로 실행되었는지, 어떤 로그 이벤트가 발생했는지 등의 정보를 제공한다.

4. 스토리지 트리(storage Trie): 컨트렉트 계정의 storage 정보가 담겨 있다. ethereumAccount 배열 안에 storageRoot에 root 값이 들어간다. key 값(path)은 약간의 계산 과정을 거친다.

 

머클 패트리샤 트리의 주요 용어

 

- Node: 트리를 구성하는 기본 단위로, 여러 형태가 있다.

- Blank Node: 비어 있는 노드.

- Leaf Node: [key, value] 구조로, 거래 정보 등을 저장한다.

- Branch Node: 17개의 요소를 가진 배열로, 앞의 16개는 자식 노드를 가리키고, 마지막 요소는 노드 자체의 값이다.

- Extension Node: [key, value] 구조로, 공통 경로를 가진 노드들을 연결한다.

- Hex-Prefix Encoding: 키 값을 인코딩하는 방식으로, 노드의 타입과 경로의 길이 정보를 포함한다.

 

머클 패트리샤 트리의 동작 원리

머클 패트리샤 트리는 키-값 쌍을 저장하며, 키 값의 공통 부분을 따라 데이터를 조직화한다. 데이터가 추가되거나 변경될 때, 해당 경로에 있는 노드들의 해시값이 업데이트되어, 최종적으로 루트 노드의 해시값이 변경된다. 이 구조는 데이터의 무결성을 보장하며, 특정 데이터가 트리에 포함되어 있는지를 효율적으로 검증할 수 있게 한다.

 

머클 패트리샤 트리의 장점

- 데이터 무결성: 상태 트리의 루트 해시는 블록 헤더에 저장되어, 블록체인의 모든 상태 변경이 무결성을 유지하도록 한다.

- 경량 노드 지원: 경량 노드는 전체 블록체인 데이터를 다운로드하지 않고도, 특정 데이터가 블록체인에 포함되었는지 검증할 수 있다.

- 데이터 복구: 상태 트리의 구조 덕분에, 노드는 네트워크의 다른 노드로부터 필요한 부분만을 요청하고 다운로드하여 자신의 로컬 데이터베이스를 복구하거나 업데이트할 수 있다. 이는 특히 네트워크에 새로 참여한 노드가 전체 블록체인의 상태를 동기화할 때 유용하다.

 

이더리움 머클 패트리샤 트리의 도전 과제

 

- 복잡성: 머클 패트리샤 트리는 구현과 유지 관리 측면에서 상당한 복잡성을 가진다. 이는 특히 새로운 개발자가 이더리움 플랫폼에 참여하거나 기존 시스템을 수정할 때 장벽이 될 수 있다.

- 성능 문제: 머클 패트리샤 트리의 복잡한 구조는 때때로 데이터 검색과 업데이트에 있어 성능 저하를 초래할 수 있다. 이더리움은 이러한 문제를 해결하기 위해 지속적으로 최적화 작업을 수행하고 있다.