블록체인의 가장 큰 장점은 블록체인의 모든 데이터를 참여자들이 모두 공유한다는 것이다. 그러나 블록체인의 크기가 계속해서 증가한다면 공유를 위해 많은 데이터를 동기화해야하기 땜누에 큰 문제가 아닐 수 없다. 따라서 비트코인의 경우 이 문제를 해결하기 위해 머클 트리를 사용했고, 이더리움에서는 이를 개선하여 머클 페트리시아 트리(Merkle Patricia Tree)라는 암호 해시 기반의 트리 자료구조를 사용한다. 그리고 트리 내의 모든 정보는 레벨DB에 저장한다.

이더리움은 Keccak256 암호 해시를 사용한다.

1. 머클 패트리시아 트리

이더리움 블록 헤어데 포함되어 있는 상태(root), 트랜잭션(TxHash), 리시트(ReceiptHash) 중 트랜잭션과 리시트는 일단 블록 내에 저장되면 변하지 않는다. 그러나 어카운트 정보를 포함하고 있는 상태(Root)는 키(key)와 값(value)의 맵(map) 구조이기 때문에 자주 변경된다. 왜냐하면 어카운트는 생성되거나 삭제될 수 있고 잔액 또한 수시로 변할 수 있기 때문이다. 이러한 특징때문에 상태 트리의 경우 머클 트리에 패트리시아 트리의 특징을 결합한 머클 패트리시아 트리를 사용한다.

상태 머클 패트리시아 트리는 새로운 어카운트가 추가되거나 삭제되는 등 변경이 자주 발생한다. 이렇게 변경이 자주 발생하면 머클 트리는 변경된 부분과 관련된 트리의 해시값을 매번 재계산해야 한다. 따라서 머클 트리에서 재계산을 줄이기 위한 개선이 필요하게 되었다. 이더리움 개발팀은 기존 머클 트리에 두 가지 추가적인 개선사항을 도출하였다.

1-1. 재계산 개선 방법

1-1-1. 트리의 깊이를 한정

트리 깊이를 한정 짓지 않으면 자칫 디도스 공격 등으로 트리를 무한정 깊게 만들어 급격한 성능 저하를 가져올 수 있다.

1-1-2. 머클 루트에 숫자 값

업데이트가 되더라도 머클 루트가 변경되지 않도록 머클 루트에 숫자 값을 주고 이 값에 한정되도록 하는 것이다. 이렇게 하면 전체 트리를 재계산하더라도 트리 루트는 변경되지 않는다.

패트리시아 트리는 트리의 각 노드에 숫자 값을 지정하여 경로를 표시한다. 이더리움은 기존 머클 트리에 패트리시아 트리의 장점을 추가하여 머클 패트리시아 트리를 구현하였다.

2. 머클 패트리시아 트리의 주요 특징

• 머클 패트리시아 트리 내의 모든 항목은 RLP(Recursive Length Prefix) 인코딩 된다.
• 머클 패트리시아 트리 내의 모든 노드에 대한 경로는 RLP 인코딩 후 Keccak256 암호 해시하여 레벨DB에 저장된다. 따라서 머클 패트리시아 루트 노드는 전체 트리에 대해 해시 암호된 상태가 되며 레벨DB에 저장이 되는 키는 실제 다음 노드의 경로를 알 수 있는 키로 조회하면, 해당 키에 대한 값을 이용하여 다음 노드에 대한 접근 경로를 알 수 있다. 이 과정을 반복하면 마지막 노드에 저장된 경로 값을 찾을 수 있다.
• 트리(trie)는 성능 향상을 위해 공백노드(Blank Node), 리프 노드(Leaf Node), 확장 노드(Extension Node), 브랜치 노드(Branch Node)라는 네 가지 노드 타입을 갖는다.

2-1. 노드 타입

• 공백 노드 비어있는 노드
• 리프 노드 일렬의 [RLP 인코딩된 경로, 값]. 값은 이더 같은 실제 값을 의미
• 확장 노드 일렬의 [RLP 인코딩된 경로, 값]의 목록. 키는 연결된 노드의 해시값이고 레벨DB 호출시 키값으로 사용한다.
• 브랜치 노드 [0, ..., f값]으로, 17개 항목으로 구성된 리스트 구조. 리스트 중 처음 16 항목은 16진수 문자값(0~f)으로 다음의 노드를 가리키는 키 역할을 하기 때문에 총 16개의 자식 노드를 가질 수 있다. 브랜치 노드의 마지막 항목이 [키, 값]을 갖는다면 17번째 값 항목에는 해당 [키, 값] 중 [값]만을 저장한다.