Geth - Merkle Patricia Tree

블록에는 블록 헤더와 트랜잭션들이 담긴다.
이더리움에서는 블록에 담기는 데이터를 효율적으로 관리하기 위해 머클 패트리샤 트리를 사용한다.
머클 패트리샤 트리는 머클 트리와 패트리샤 트라이를 합친것.

Merkle Tree

리프 노드부터 해시 > 형제 노드를 짝지어서 해시 > 반복 > 최상위는 머클루트.
머클루트는 블록헤더의 스테이트 루트 필드에 저장된다.

비트코인에서는 sha256, 이더리움에서는 keccak256 해시 함수를 사용

머클 트리는 모든 트랜잭션을 해시하여 최종적으로 단일한 해시 값인 머클 루트를 생성한다. 이 머클 루트를 통해 블록 내의 모든 트랜잭션의 무결성을 확인할 수 있으며, 블록에 포함된 어떤 트랜잭션에도 변경이 발생하면, 이는 머클 루트의 값이 변경되는 결과를 가져오게 되므로 위변조 여부를 확인할 수 있고 이로인해 데이터 무결성을 보장할 수 있다.

또한 블록 헤더에 포함된 주요한 필드로도 블록 해시를 만들어 체인을 연결하므로 블록의 무결성 또한 보장할 수 있다.

블록 해시를 만드는 필드들

• Parent Hash: 이전 블록의 헤더 해시, 블록체인의 연속성을 보장
• Merkle Tree Root: 블록에 포함된 모든 트랜잭션을 나타내는 머클 트리의 루트 해시
• State Root: 블록 생성 시점의 전체 네트워크 상태의 머클 패트리샤 트리 루트 해시
• Transaction Root: 블록에 포함된 모든 트랜잭션의 데이터를 담은 머클 패트리샤 트리의 루트 해시
• Receipts Root: 각 트랜잭션 실행 결과를 담은 리십트의 머클 패트리샤 트리 루트 해시
• Difficulty: 해당 블록을 생성하기 위해 요구되는 작업 증명(Proof of Work)의 난이도
• Timestamp: 블록이 생성된 시간의 타임스탬프
• Nonce: 작업 증명 알고리즘에서 사용되는, 블록의 유효성을 증명하는 데 필요한 값

Trie

패트리시아 트라이를 이해하기 위해서는 먼저 Trie를 알아야한다.
Trie는 문자열을 빠르게 검색하기 위한 트리 형태의 자료구조이다.

Trie는 retrieve라는 검색하다라는 뜻을 가진 단어에서 파생

효율적인 검색을 위해 위 이미지의 트리와 같이 공통인 접두사를 기반으로 트리에 문자열을 저장한다.

각 노드는 하나 이상의 자식 노드를 가지며, 각 자식 노드는 하나의 알파벳 문자를 갖는다.

고랭으로 구현한 Trie 자료구조

package main

import "fmt"

type Trie struct {
	/*
	   - rune은 int32 타입
	   - utf8 유니코드 값을 키로 넣으면 해당하는 문자열 Trie를 값으로 가짐
	*/
	children  map[rune]*Trie
	endOfWord bool // 문자열의 끝, 문자열 저장 및 검색 시 문자열의 끝을 알려주는 역할
}

// 문자열을 트라이에 저장
func (t *Trie) Insert(word string) {
	current := t
	for _, r := range word {
		if current.children[r] == nil {
			fmt.Println(r)
			current.children[r] = &Trie{children: make(map[rune]*Trie)}
		}
		current = current.children[r]
	}
	current.endOfWord = true
}

func (t *Trie) Search(word string) bool {
	current := t
	for _, r := range word {
		if current.children[r] == nil {
			return false
		}
		current = current.children[r]
	}
	return current.endOfWord
}

func main() {
	trie := &Trie{children: make(map[rune]*Trie)}
	trie.Insert("hello")
	fmt.Println(trie.Search("hello"))
}


> go run main.go
104
101
108
108
111
true

https://www.utf8-chartable.de/

자바스크립트 버젼

class TrieNode {
    constructor() {
        this.children = {};
        this.endOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // 문자열을 트라이에 저장
    insert(word) {
        let current = this.root;
        for (let i = 0; i < word.length; i++) {
            let ch = word[i];
            let node = current.children[ch];
            if (!node) {
                node = new TrieNode();
                current.children[ch] = node;
            }
            current = node;
        }
        current.endOfWord = true;
    }

    // 트라이에서 문자열 검색
    search(word) {
        let current = this.root;
        for (let i = 0; i < word.length; i++) {
            let ch = word[i];
            let node = current.children[ch];
            if (!node) {
                return false;
            }
            current = node;
        }
        return current.endOfWord;
    }
}

// 사용 예시
let trie = new Trie();
trie.insert("hello");
console.log(trie.search("hello"));  // true

Patricia Trie

패트리시아 트라이는 효율적인 정보 검색을 위해 개발된 트라이 기반 자료구조이다.
표준 트라이와는 다르게 공통된 접두사를 문자열로 묶어서 트라이를 구성한다.
공통 접두사를 찾는 속도가 빨라지고 메모리 사용량이 줄어든다.

메모리 사용량 감소:

일반 트라이에서는 각 문자에 대해 별도의 노드를 생성한다. 이는 특히 긴 문자열이나 공통 접두사를 많이 공유하는 문자열들에 대해 많은 메모리를 소모한다. 반면, 패트리샤 트라이에서는 공통 접두사를 하나의 노드에 저장함으로써 별도의 노드를 여러 개 생성할 필요가 없어진다. 이는 특히 접두사가 긴 경우에 더욱 메모리 효율적이다.

검색 속도 향상:

일반 트라이에서는 검색 시 각 문자마다 노드를 방문해야 하므로, 검색할 단어의 길이에 비례하여 검색 시간이 증가한다. 패트리샤 트라이에서는 공통 접두사가 하나의 노드에 저장되므로, 검색 시 불필요한 노드 방문을 줄일 수 있으며, 이는 특히 긴 공통 접두사를 가진 단어들을 검색할 때 시간 효율성을 크게 향상시킨다.

노드 탐색 최적화:

패트리샤 트라이는 공통 접두사를 기반으로 트리를 압축하여 저장하기 때문에, 한 번의 탐색으로 여러 문자를 한꺼번에 비교할 수 있다. 이는 특히 데이터베이스 조회, 라우팅 테이블 조회와 같은 응용에서 검색 시간을 크게 단축시킨다.

이와 같은 특징들 때문에 패트리샤 트라이는 대용량의 문자열 집합을 효율적으로 처리하고, 빠른 검색과 낮은 메모리 사용량을 제공하는 자료구조로 사용된다.

Merkel Patricia Tree

머클 패트리시아 트리는 머클 트리에 패트리샤 트라이를 적용한 것이다.

참고: https://devkly.com/blockchain/ethereum-state/

머클 트리 처럼 리프 노드에 해시값을 저장하고 루트 노드에는 각 해시값을 해싱한 값을 저장한다.
이때 프리픽스(접두사)를 사용하여 각 노드를 구분한다. 해당 트리는 레벨 디비에 저장된다.

Extension Node

목적:익스텐션 노드는 트라이의 길이를 압축하는 데 사용. 이 노드는 공통 접두사를 가지는 경로를 나타내고, 키의 일부를 나타내는 공통 접두사를 저장한다.

용도:키가 길고, 특정 경로를 따라가는 데 많은 중복이 있는 경우, 이 중복을 제거하여 효율적으로 트리를 표현. 트리의 특정 부분으로 빠르게 이동하기 위해 공통된 경로를 압축하여 저장. 메모리 사용을 최적화하고, 트리의 깊이를 줄여 검색 시간을 단축.

Branch Node)

목적: 브랜치 노드는 트리 내에서 분기점을 나타냄. 이 노드는 16진수 한 자리에 해당하는 16개의 포인터를 가질 수 있으며, 트리의 각 분기를 나타낸다.

용도: 각각의 포인터는 16진수 한 자리(0-9 및 a-f)에 해당하는 키 값을 가리킬 수 있다.
만약 노드가 키의 끝을 나타내면, 이 노드는 직접적으로 값을 가지고 있을 수 있으며, 이 값을 통해 실제 데이터에 접근할 수 있다. 트리에서 특정 키를 찾을 때, 각 분기점에서 어느 방향으로 탐색을 계속할지 결정하는 데 사용됨.

익스텐션 노드와 브랜치 노드의 조합을 통해 머클 패트리샤 트리는 경로를 따라가는 동안 필요한 정보만을 탐색하도록 하여 검색 효율성을 대폭 향상시킨다. 이런 방식으로 이더리움은 계정의 상태, 스마트 계약의 코드, 스토리지 등의 데이터를 효과적으로 저장하고 검색할 수 있다.

이더리움에서 머클 패트리시아 트리가 사용되는 부분

• 상태: 이더를 주고 받을때의 스테이트를 저장
• 스토리지: 컨트랙트 데이터
• 트랜잭션: 거래
• 리십트: 거래 결과