[Blockchain] 이더리움 머클 패트리시아 트리(MPT)란?

블록체인이 기존 서비스들을 대체하기에 가장 큰 힘은 탈중앙성에서 나옵니다. 즉 네트워크에 참여한 모든 노드들이 동일한 데이터를 공유하고 관리하는 시스템은 투명한 거래와 보안성을 보장합니다. 하지만 네트워크가 성장하면서 자연스럽게 노드들간에 동기화되는 데이터의 양이 많아지게 되고, 이는 네트워크 성능 저하로 이어지게 됩니다. 예를 들어 스마트폰에서 풀 블록체인을 다운로드 할 수 없습니다. 용량의 크기가 300GB가 넘어가기 때문입니다.

 

 

이러한 문제를 해결하기 위해 블록체인 네트워크들은 제각각 해결책을 내놓기 시작합니다. 비트코인에서는 머클 트리(Merkle Tree)를 사용하고, 이더리움에서는 머클 패트리시아 트리(MPT, Merkle Patricia Tree) 기반의 트리 자료구조를 사용합니다. 트리 내의 모든 정보들은 레벨DB에 저장됩니다.

 

[Blockchain] 블록체인 머클트리(Merkle Tree)란?

 

 

이더리움 경량화 하위 프로토콜(LES)란?

 

이더리움은 머클 트리를 사용해 전체 Account 정보를 담고 있는 상태(Root)와 트랜잭션(TxHash), 트랜잭션의 처리 결과를 알 수 있는 리시트(ReceiptHash)의 값을 저장한 후 각 머클 루트들을 Keccak256 알고리즘으로 해싱한 후 블록헤더에 포함합니다.

 

 

블록헤더에 담은 상태정보, 트랜잭션, 리시트의 머클 루트를 가지고 전체 블록체인 데이터를 다운로드 하지 않아도 다양한 블록체인 상태를 조회할 수 있게 됩니다. 이 경우 경량화 하위 프로토콜(LES, Light Ethereum Subprotocol)을 사용하고 이더리움 클라이언트 싱크 모드로는 경량 동기화(light sync)를 사용합니다. 

경량화 하위 프로토콜(LES)를 사용하면 임의의 트랜잭션이 어떤 블록에 포함되어 있는지, 특정 Account의 이더 잔액이 얼마인지, 특정 Account가 존재하는지 등의 정보를 조회할 수 있게 됩니다. 이더리움에서의 머클 트리는 대량의 블록체인 전체 데이러를 동기화하지 않으면서 데이터 조회 및 데이터 무결성을 보장합니다.

 

이더리움 머클 패트리시아 트리(MPT)

 

머클 패트리시아 트리가 사용되는 이유?

이더리움 블록 헤더에 포함되는 상태(Root), 트랜잭션(TxHash), 리시트(ReceiptHash) 중에서 트랜잭션과 리시트는 일단 블록에 저장되면 변하지 않는 값입니다. 하지만 Account 정보를 포함하는 상태(Root)는 키~값 쌍으로 구성된 맵(Map) 구조로 자주 변경됩니다. Account는 새로 생성되거나, 잔액이 수시로 변경되기 때문입니다. 이더리움에서는 자주 변하는 값을 조회하기에 최적화된 방법으로 머클 패트리시아 트리(MPT)를 사용합니다.

 

 

기존 머클 트리에서 값이 변경되면 변경이 시작된 지점 부터 머클 루트 까지 모든 값이 다시 해시값을 연산하게 됩니다. 즉, 변경이 자주 일어날 수록 네트워크의 오버헤드는 증가하게 됩니다. 재계산을 줄이기 위해서 이더리움 코어 개발팀에서는 2가지 해법을 제안합니다.

1. 트리의 깊이를 한정 짓는다 : 깊이가 한정되어 있지 않으면 DDoS 공격에 노출되고 트리가 무한정 깊어지면서 성능 저하로 이어집니다.
2. 머클 루트값을 고정시킨다 : 업데이트가 되더라도 머클 루트를 고정함으로써 전체 트리를 재계산 하더라도 머클 루트는 변경되지 않습니다. 머클 루트에 숫자 값을 할당하고 이 값에 한정되도록 합니다.

 

기존 머클 트리를 개선하는 2가지 아이디어로 머클 패트리시아 트리가 다음과 같이 구현되었습니다.

• 이더리움 코어 개발팀은 트리의 각 노드에 숫자값을 할당하고 경로를 표시하게 됩니다.
• 머클 패트리시아 트리 내의 모든 항목들은 RLP(Recursive Length Prefix) 인코딩 됩니다.
• 머클 패트리시아 트리 내의 모든 노드에 대한 경로는 RLP 인코딩 후 Keccak256 암호 해시해 레벨 DB에 저장됩니다. 이로 인해 머클 패트리시아 루트 노드는 전체 트리에 대해 해시 암호가 된 상태가 됩니다. 레벨 DB에 저장되는 키(Key) 값은 실제 다음 노드에 대한 경로(Path)가 됩니다. 즉, 트리 내에 다음 노드의 경로를 확인할 수 있는 키(Key)로 조회하게 되면 해당 키에 대한 값을 이용해 다음 노드에 대한 접근 경로를 확인할 수 있게 됩니다. 이 과정을 반복하면서 마지막 노드에 저장된 경로 값을 찾을 수 있습니다.
• 트리(Trie)는 성능 개선을 위해 4가지 노드로 구성됩니다.
  - 공백 노드(Blank Node) : 비어 있는 노드(NULL)
  - 리프 노드(Leaf Node) : RLP 인코딩 된 경로 값은 이더 등의 실제 값을 의미합니다.
  - 확장 노드(Extension Node) : RLP 인코딩 된 경로인 키의 목록입니다. 키는 연결된 노드의 해시값이자 레벨DB 호출시 키 값으로 사용됩니다.
  - 브랜치 노드(Branch Node) : 16진수 0~f 값으로 17개 항목으로 구성된 리스트 구조입니다. 리스트 중 처음 16자리는 16진수 문자값으로 다음 노드를 가리키는 키 역할을 하므로 16개의 자식 노드를 가질 수 있습니다. 브랜치 노드의 마지막 항목이 존재하는 경우 해당 키, 값 중 값만 저장되어 있습니다. 
• 리프 노드(Leaf Node)와 확장 노드(Extension)를 구분하기 위해 선행구분자(Prefix)를 사용합니다. 선행 구분자는 헥사 선행구분자 방식으로 인코딩 되어 있습니다. 선행 구분자가 0이면 확장 노드, 경로값의 길이가 짝수를 의미합니다. 선행 구분자가 2인 경우 리프 노드, 경로 값의 길이가 짝수임을 의미합니다. 

이더리움의 상태정보는 이더리움 블록체인 내에서 단일한 공통의 스테이트 트리를 구성하고 있습니다. 따라서 월드 상태 트리(World State Trie) 혹은 글로벌 상태 트리(Global State Trie)라고 합니다. 월드 상태 트리 경로를 나타내는 키 값을 따라가다 보면 머클 패트리시아 트리의 경로를 따라 리프 노드에 저장된 이더 값을 확인할 수 있게 됩니다. 

이더리움 월드 스테이트 트리

 

머클 패트리시아 트리를 고려한 블록의 연결을 보면 시간순으로 연결된 블록들은 내부에 담고 있는 머클 패트리시아 트리 형태의 상태 정보(Root), 트랜잭션(TxHash), 리시트 정보(ReceiptHash)들은 단일한 트리를 구성하게 됩니다. 

 

 

 

 

머클 상태 전이 증명

 

이더리움 블록 헤더에는 상태 정보 트리(Root), 트랜잭션 트리(TxHash), 리시트 트리(ReceiptHash)의 암호화된 해시 루트가 담겨 있어 다양한 정보를 조회할 수 있습니다. 초기 블록체인의 블록 헤더만을 Sync하고 필요한 정보를 별도로 다운로드하는 라이트 클라이언트에서 해시 루트를 통해 해당 트랜잭션이 어떤 블록에 담겼는지, 특정 Account의 잔액은 얼마인지 등의 다양한 정보를 조회할 수 있게 됩니다. 

가상으로 특정 컨트랙트의 트랜잭션을 실행한 후 해당 결과를 확인할 수 있습니다. 이를 이더리움에서는 머클 상태 전이 증명(MSTP, Merkle Status Transition Proof)라고 합니다. MSTP는 만약 상태 루트 S상에서 트랜잭션 T를 실행하는 경우 결과는 로그 L과 아웃풋 O를 가지는 상태루트 S'가 된다고 정의할 수 있습니다. 

 

 

즉 상태 트리 루트, 트랜잭션, 리시트 트리에서 관련 정보를 조회한 후, 결과 O를 가상으로 재현합니다. 이로써 상태 S'가 올바른 전이가 맞는지 확인할 수 있습니다. 머클 상태 전이 증명은 다음 과정을 거쳐 진행됩니다.

① 임의 상태 S 선택

상태 전이 증명을 위해 이더리움 노드는 로컬 컴퓨터 상에서 임의의 가짜 블록을 생성한 후 임의의 상태 S를 설정합니다. 라이트 클라이언트 모드로 특정 트랜잭션을 실행한 후 필요한 정보를 상태 트리 루트, 트랜잭션, 리시트 루트를 통해 찾게 됩니다. 만약 잔액을 찾는 경우 잔액에 대한 조회 질의를 생성합니다.

② 트리 정보 탐색

이더리움 노드는 라이트 클라이언트로 부터 요청받은 모든 질의를 트리 정보를 탐색해 처리한 다음, 결과를 라이트 클라이언트에게 반환합니다. 모든 관련 기록들이 저장됩니다.

③ 결과 검증

라이트 클라이언트는 전달 받은 모든 데이터를 사용해 똑같은 트랜잭션 실행 과정을 재현해 상태 S'를 생성합니다. 만일 결과 상태 S'가 이더리움 노드가 알려준 결과와 같은 경우 라이트 클라이언트는 해당 증명을 수용하게 됩니다. 

 

 

 

[Blockchain] 프루닝(Pruning)이란?

 

[Blockchain] PBFT(Practical Byzantine Fault Tolerance) 합의 알고리즘이란?

 

[Security] 해시 함수 알고리즘 특징