HMDB: How to Manage the Data in the Blockchain

Published in

Decipher Media ｜디사이퍼 미디어

26 min readAug 31, 2024

Disclaimer : 서울대학교 블록체인 학회 디사이퍼(Decipher)에서 블록체인의 상태(State)를 저장하는 방법을 주제로 Weekly Session에서 발표한 내용을 바탕으로 합니다. 본 아티클은 상태 저장에 사용되는 다양한 데이터 구조에 대한 배경 지식, Merkle Patricia Trie와 Sparse Merkle Tree의 개요 및 심층 분석을 제공하며, 다른 데이터 구조들도 함께 소개합니다. 이 보고서에 포함된 어떠한 내용도 투자 조언이 아니며, 투자 조언으로 해석되어서도 안 됩니다.

Author

허정, 송만섭 of Decipher

Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)

Reviewed By 이현우, 최재우, 신성헌

Introduction
Background
Merkle Patricia Trie (MPT)
Sparse Merkle Tree
4.1. Sparse Merkle Tree 소개
4.2. Sparse Merkle Tree 특징
4.3. Sparse Merkle Tree 동작 과정
4.4. Sparse Merkle Tree 기반 블록체인 프로젝트 소개
Introducing other data structures
5.1. Verkle Tree
5.2. Namespaced Merkle Tree
5.3. Jellyfish Merkle Tree
Summary

1. Introduction

최근에는 블록을 전파하고 검증하는 과정이나 트랜드에 대한 리서치가 많은 반면에, 블록체인이 데이터를 어떻게 다루는지에 대한 논의는 적었습니다. 이번 아티클에서는 블록체인 데이터가 어떤 구조에 담기는지에 대해 얘기해보려고 합니다. 큰 맥락에서 Merkle Patricia Trie(MPT)와 Sparse Merkle Tree(SMT)에 대해 공유합니다.

블록체인은 시간 순서대로 연결된 블록에 데이터를 저장합니다. Blockchain Data를 볼 수 있는 예시는 우리 주변에서 쉽게 찾아볼 수 있습니다. 대표적으로 Etherscan에서 블록과 트랜잭션 데이터를 볼 수 있습니다. 그리고 노드를 운영하는 사람들은 직접 블록체인 데이터를 저장하고 있습니다. 이런 데이터들이 어떻게 다뤄지는지 알아보겠습니다.

2. Background

위에서 말한 블록체인 데이터는 네트워크 내에서 투명하게 공개되어 있습니다. 이더리움에서는 이런 데이터들을 일시적인 데이터와 영구적인 데이터, 이렇게 2가지 유형으로 볼 수 있습니다. Account의 Balance 잔액은 변경될 수 있는 데이터, 즉 일시적인 데이터입니다. Transaction은 영구적인 데이터로 볼 수 있습니다. 이런 데이터 유형에 따라 데이터는 따로 저장되고 있습니다.

우선 일시적인 데이터부터 보겠습니다. 앞에서 일시적인 데이터의 예시로 Account의 Balance를 말했습니다. Account는 계정 주소를 Nonce, Balance, StorageRoot, CodeHash로 구성된 상태에 맵핑합니다. 이런 상태는 key-value 쌍으로 되어있습니다. key-value 쌍을 그대로 저장하는 것은 효율적이지만, 데이터 전체가 정확하다는 것을 검증하기 위해서는 전체 데이터 세트를 다시 스캔해야한다는 단점이 있습니다.

그림1 예시에는 데이터 세트 a,b,c,d가 있습니다. 각 데이터 집합은 key-value로 되어있고, 이 데이터 집합들을 flat data로 저장한 상황입니다. 데이터 무결성 검증을 위해서 b가 b’로 변경되었을때, 전체 데이터 세트를 다시 해시화하고 있습니다. 그럼 무결성 검증을 위해서는 모든 데이터 세트를 스캔해야하는데, 대규모 데이터 세트인 경우에는 비효율적입니다. 그래서 이더리움에서는 모든 데이터 세트의 단일 루트 값을 생성해서, 이것을 데이터 무결성 검증에 사용하는 Merkle Tree 데이터 구조를 사용합니다.

그림2 예시를 보면 Hash(b’)은 연산되었으므로, 데이터 무결성 검증을 위해서는 파란색 노드들의 해시값만 필요한 것을 알 수 있습니다. 앞의 예시에서 데이터 세트 a,b,c,d가 모두 필요했던 것보다 효율적인 것을 알 수 있습니다.

3. Merkle Patricia Trie (MPT)

실제 이더리움에서는 Merkle Tree와 Patricia Trie를 결합한 MPT 데이터 구조를 사용합니다. Merkle Patricia Trie는 이더리움 상태를 구성하는 데이터들을 검색하는 것과 트리를 업데이트 하는 것을 효율적으로 하기 위해 사용합니다. 위에서는 Merkle tree를 알아봤고, 이제 MPT에 대해 알아보겠습니다. Merkle tree 내용을 다시 짚어보면, 모든 데이터로부터 하나의 Root Hash 값을 구할 수 있고, 데이터 무결성을 검증하기에 적합했습니다.

Merkle Tree에서 모든 데이터는 가장 하위 Leaf Node에 저장됩니다. 이 Leaf Node의 데이터가 변경되면 상위 노드의 Hash들이 변경되고, 결과적으로 Root Hash가 변경됩니다. 이렇게 데이터가 변경되었을때, Root Hash도 변경되기 때문에 머클 증명으로 데이터 무결성 검증이 가능한 것입니다. 이렇게 기존 데이터에 대한 수정사항을 통해 Root Hash를 변경하는 것은 효율적이지만, Leaf 노드가 가지고 있는 데이터를 찾아가는 과정이 비효율적입니다. 그 해결책으로 Patricia Trie와 Merkle Tree를 결합시킨 데이터 구조를 사용합니다. Patricia Trie를 사용하면, 키를 path로 사용하게 됩니다. 이는, 공통의 키들을 그룹화하여 트라이의 깊이를 현저하게 줄입니다.

Patricia Trie가 경로를 줄이고, 공간낭비를 줄이는 방법을 보려고 합니다. 우선 기본이 되는 Radix Trie를 보겠습니다. Radix trie는 키-값 쌍을 저장하는데 사용됩니다. Radix 트라이에서 키는 값을 찾아가기 위한 경로입니다. 키를 구성하는 문자열의 각 문자 또는 문자 그룹에 따라 노드를 생성하고, 각 노드는 그 다음 문자 또는 문자 그룹으로의 포인터를 가집니다. 각 키의 끝에는 해당 키와 관련된 값을 저장할 수 있는 노드가 존재합니다. 긴 키를 공통 접두어(prefix) 기반으로 압축해서, 저장 공간을 효과적으로 절약할 수 있습니다. 우선 Radix 트라이 예시를 보겠습니다.

그림3과 같이 CAT, CATS, DOG, DODO, DOGS를 키로 하고, 1,2,3,4,5를 값으로 갖는 데이터 세트가 있습니다. 트라이의 각 경로는 ASCII 문자이고, 값을 찾기 위해 사용됩니다. Basic Radix Trie는 그림4의 이미지와 같이 나타낼 수 있습니다. 키 DOGS는 값 5를 갖고 있습니다. Basic Radix Trie에서 이 값을 찾아가는 과정을 보겠습니다. 맨위의 루트에서 시작해서, 경로이면서 키인 D — O — G — S를 따라내려갑니다.

Path인 D,O,G,S를 따라내려가면서, 유효하지 않은 값을 뜻하는 NULL인 노드들을 자세히 살펴보겠습니다.

왼쪽의 CAT 키 (C — A — T) 를 통해, 값 1을 표현하기 위해서 2개의 NULL 노드가 존재하여 저장 공간을 낭비하고 있습니다. 이런 공간낭비를 줄이기 위해, 중간에 분기가 없는 키를 하나의 키로 합치겠습니다.

값이 NULL 인 경로 (C — A — T) 를 합치니 그림7의 Trie가 됐습니다.

마지막으로 다른 NULL들도 처리해보겠습니다. 경로를 모두 합친 결과는 그림8의 트라이와 같습니다. 문자였던 경로들이 하나의 문자열로 표현됐습니다. 이와 같이, 중간에 분기가 없는 경로를 하나의 키로 합쳐 사용하는것이 Patricia Trie 사용 목적이라고 할 수 있습니다. 이번에는 각 노드에 대해 살펴보겠습니다. 그림9에서 노드의 구조를 확인할 수 있습니다.

기본 Radix 트라이에서 각 노드는 슬롯 0부터 슬롯 n, 그리고 value로 되어있습니다. 각 슬롯의 값은 NULL 또는 다른 노드로의 포인터입니다. 이더리움의 경우, 다른 노드의 해시를 말합니다.

노드가 어떻게 생겼는지 확인했으니, 이제 Patricia Trie를 보겠습니다. 실제 이더리움에서는 그림9와 같이, 노드당 16개의 슬롯과 1개의 value를 위한 공간을 사용합니다. 아래 예시에서는 편의를 위해 10개의 슬롯과 1개의 value로 설명하겠습니다.

키가 “3,5,1,2”인 경우, 값을 찾아가봅니다. 맨위의 Root Hash에서 시작하면, 경로 3에 해당하는 값은 hashA 입니다. hashA를 찾아갈건데, 이렇게 key에 해당하는 해시 값을 찾아가는 것은 레벨DB에 저장되어 있는 특정 노드를 검색하는 것입니다. 계속해서 트라이의 경로를 따라가보면, hashA에서 경로 5에 해당하는 값은 hashC 입니다. hashC에서 경로 1에 해당하는 값은 hashB, hashB에서 경로 2에 해당하는 값은 hashD 입니다. hashD에서는 최종값에 도달하여, CAT 이라는 값을 찾게 됩니다. 위 예제에서 Data가 비어있으면 해당 노드는 NULL 값을 갖습니다.

위의 트라이는 각 노드가 많은 NULL 값을 가지고 있어, 많은 저장 공간 낭비를 일으키고 있습니다. 저장 공간 낭비를 개선하기 위해서 확장 노드와 리프 노드를 도입합니다. 이 노드들은 2개의 요소가 있는 배열 형태입니다. 노드의 첫번째 요소는 Null 노드를 줄이는데 도움이 되는 부분 경로입니다. 노드의 두번째 요소는 확장 노드인 경우 merkle Hash이고, Leaf node인 경우 최종값에 해당하는 data입니다.

이번 예시에서는 확장노드를 적용시켜봅니다. 위 이미지에서 첫번째 경로 “3”에서 hashA를 찾게 되는데, hashA에 해당하는 노드에 확장노드를 적용시켜봅니다. 아래 이미지는 확장 노드가 적용된 그림입니다.

해당 노드는 첫번째 요소로 “51”을 갖고, 두번째 요소로 Merkle Hash인 hashB 를 갖게 됩니다. 경로 “3,5,1,2”를 다시 따라가보겠습니다. Root Hash의 경로 3은 hashA를 가리키고 있습니다. hashA에서 첫번째 요소인 “51”이 부분 경로이고, 두번째 요소인 hashB가 merkle hash 입니다. 바로 hashB에 해당하는 노드로 가면, 남은 경로인 경로 2에서 hashD를 얻게 됩니다. hashD에 해당하는 노드에서 최종값인 “CAT”을 찾게 됩니다. 이렇게 최적화된 패트리샤 트라이는 Null 노드를 줄여서 저장 공간을 효율적으로 사용합니다.

이번에는 리프노드를 적용시켜봅니다. hashB에서는 경로 2와 경로 7에서 각각 hashD, hashE에 해당하는 노드를 찾게 됩니다. 각 노드들은 CAT, DOG를 최종값으로 하는 데이터로 갖습니다. 따라서 hashD와 hashE에 해당하는 노드는 리프노드를 적용시킬 수 있습니다. 확장노드에서는 첫번째 요소가 부분경로를 나타냈지만, 리프노드에서는 부분경로가 남아있지 않으므로 비어있습니다. 아래 이미지는 리프노드까지 적용된 그림입니다.

앞에서 Merkle Tree와 Patricia Trie를 결합한 데이터 구조를 알아봤습니다. 실제로 이더리움의 Execution Layer에 있는 모든 Merkle Tree는 Merkle Patricia Trie를 사용합니다. 이더리움의 대표적인 MPT 예시로 State Trie가 있습니다. 그리고 이더리움 블록 헤더에서 root hash들을 찾아볼 수 있습니다.

State Trie를 구성할때, 경로에 해당하는 key는, 주소를 해싱한 결과를 사용하고, value로는 이더리움 Account 상태를 rlp 인코딩한 값을 사용합니다. 또 다른 MPT 예시로는 ReceiptsRoot, TransactionsRoot 등이있습니다. 이런 특징을 가진 MPT에도 한계점은 있습니다.

MPT의 한계점은 대표적으로 proof의 크기에 있습니다. 이더리움은 상태를 트리에 저장합니다. 최적화를 위해 16개의 자식노드를 두고 있습니다. merkle proof를 생성할때, 모든 형제 노드를 포함해야하는데, hexary 트리에서는 형제 노드가 15개이기 때문에 proof 의 크기가 커집니다. 블록 제안자만 상태 트라이를 저장하는 개념인 Weak statelessness와 이더리움 풀노드가 상태 트라이를 주기적으로 초기화하는 개념인 State expiry를 적용한 Stateless를 도입하면, proof가 자주 사용되기 때문에 문제가 될 수 있는것입니다. 그래서 MPT 대신에 proof의 크기를 상수 크기로 줄인, Verkle Tree를 사용하는 것에 대한 논의가 되고 있습니다. Verkle Tree는 MPT와 유사한 트리 구조를 사용합니다. 주요 차이점은 각 노드가 벡터 커밋이라는 특수한 해시를 사용한다는 것입니다. Proof를 위해, 각 레벨에서 형제 노드의 해시를 제공하지 않고, 각 리프 노드에서 Root 까지의 경로를 따라 모든 부모 노드만 제공하면 됩니다. 이를 통해 Proof의 크기는 줄고, 이더리움의 stateless 상태를 달성하는데 도움이 됩니다. 자세한 설명은 이전 Verkle Trie 리서치 글에서 찾아볼 수 있습니다.

4. Sparse Merkle Tree

4.1. Sparse Merkle Tree 소개

Sparse Merkle Tree(SMT)는 앞서 소개한 MPT와 마찬가지로 효율적인 데이터 인증 및 검증을 위해 사용되는 데이터 구조 중 하나입니다. 이름에서 알 수 있듯이, SMT는 Merkle Tree를 기반으로 하고 있으며 자식 노드가 두 개씩 생기는 Binary Merkle Tree의 구조를 따릅니다. SMT는 2014년에 구글 리서치의 Ben Laurie가 처음 제안한 데이터 구조로 알려져 있습니다. 구글에서 웹 브라우징을 할 때, 구글 서버와 인터넷 통신을 시작하기 전에 서버는 인증서를 제시합니다. 클라이언트는 제시된 인증서를 검증하여 서버와의 통신이 안전한지 판단합니다. 이 때, SMT는 인증서 투명성(Certificate Transparency)을 보장하기 위해 보다 효율적인 검증 방식을 제공하도록 제안되었습니다.

이처럼 SMT는 2015년에 탄생한 이더리움보다 이전에 나온 개념입니다. 블록체인 분야에서 처음 SMT라는 키워드가 언급된 것은 2018년에 이더리움 리서치에서 이더리움의 확장성을 높이기 위한 솔루션 중 하나인 Plasma Cash에서 트랜잭션 인덱스 순서로 Merkle tree에 트랜잭션을 저장하는 대신, SMT에 트랜잭션을 저장하자는 제안이 있었습니다. 이 후에는 zkEVM, zkSync, aptos 등 여러 프로젝트에서 SMT를 활발히 활용하고 있습니다.

4.2. Sparse Merkle Tree 특징

SMT의 가장 큰 특징중 하나는 트리의 깊이가 고정되어 있다는 점입니다.

트리의 깊이는 키의 비트수에 의해 결정됩니다. 즉, SMT에서는 모든 경우의 키의 값을 표현할 수 있고 하나의 키 당 하나의 리프 노드로 구성됩니다. 그림 13에서 보듯이, 키의 크기가 5bits라면 SMT의 깊이는 5가 되고 최종적으로 리프 노드는 2⁵인 32개가 생성됩니다. 만약 이더리움 주소를 키로 사용한다면, 주소의 크기는 160bits (20bytes)이기 때문에 SMT의 리프 노드의 수는 2¹⁶⁰가 생성됩니다.

예를 들어, 전 세계 인구 80억명이 모두 이더리움 주소를 하나씩 가지고 있더라도 이더리움 주소는 약 2³³(약 80억)개면 충분하다는 점을 생각해본다면, 2¹⁶⁰라는 수는 매우 큽니다. 따라서 SMT의 특징 중 하나는 실제 사용되는 노드는 많지 않고 비어 있는 노드가 많다는 것입니다.

그렇다면 어떤 경우에 SMT가 효과적일까요?

SMT에서는 특정 데이터가 트리에 포함되어 있음을 증명하는 membership proof와 트리에 포함되어 있지 않음을 증명하는 non-membership proof를 효율적으로 수행할 수 있습니다.

그림 14는 키의 크기가 2bits인 경우의 SMT 구조입니다. 파란색 박스는 리프 노드를 의미하고 각각의 위치는 키의 값에 따라 정해져 있습니다. 즉, 제일 왼쪽부터 리프 노드들의 <key, value>는 <00, data0>, <01, null>, <10, null>, <11, data3>으로 구성되어 있습니다. 이 때, 만약 <10, data2>가 포함되어 있는지 검증하는 요청이 왔다면 SMT에서는 해당 키값의 리프 노드(왼쪽에서 세번째)를 확인하고 null임을 증명하면 포함 여부를 알 수 있습니다. 비트맵(Bitmap)을 활용한다면 리프 노드가 null인지 아닌지 바로 알 수 있습니다. 비트맵은 각 비트(Bit)로 하나의 요소(Element)의 존재 여부를 나타내는 자료구조입니다. 비트맵은 비트의 배열로 구성되며, 각각의 비트는 0 또는 1의 값을 가질 수 있습니다. 예를 들어, 비트맵이 {1001}로 표현될 때, 이는 키 값이 10에 해당하는 리프 노드가 null임을 즉시 알 수 있게 해줍니다.

SMT는 고정된 깊이를 통해 membership 및 non-membership proof를 효율적으로 할 수 있지만, 반대로 고정된 깊이가 단점으로 작용하기도 합니다. 아까 들었던 예시 중, 이더리움 주소의 크기인 20 bytes가 키가 된다면 ²¹⁶⁰개의 리프 노드가 생성되는데 이는 매우 많은 메모리 및 스토리지 공간을 요구합니다. 또한, 특정 리프 노드의 값을 업데이트하고 싶으면 (예를 들어, 해당 주소의 잔액(Balance)가 변경될 때) 리프 노드부터 루트 노드까지 값이 다 바뀌어야 하기 때문에 최악의 경우 160개의 노드의 값을 업데이트해야 할 수도 있습니다.

이를 해결하기 위해, 두 가지 룰을 통해 SMT를 최적화기도 합니다. 첫 번째는, “하나만 비어 있지 않은 리프 노드를 가진 각 서브 트리(메인 트리 안에 또 다른 형태의 트리)는 해당 리프 노드 자체로 대체한다”이고, 두 번째는 “모두 비어 있는 노드들로 구성된 각 서브 트리는 고정된 해시 값으로 대체한다” 입니다.

그림 15은 최적화 되기 전의 SMT 구조와 최적화 된 이후의 SMT 구조를 비교한 그림입니다. 빨간색 점선 네모 박스는 규칙 1번에 의해 변경된 지점이고, 파란색 점선 네모 박스는 규칙 2번에 의해 변경된 지점입니다. 두 가지 룰을 통해 최적화를 진행한 결과, 적은 노드로 SMT 구성을 할 수 있게 됩니다.

4.3. Sparse Merkle Tree 동작 과정

SMT를 구성할 때 네 가지 오퍼레이션을 통해 구성할 수 있습니다.

Create: 특정 key-value pair를 생성
Update: 특정 key에 대한 기존 value를 새로운 value로 수정
Read: 특정 key에 대한 value를 반환
Delete: 특정 key-value pair를 삭제

그림 16와 그림 17는 Create 오퍼레이션을 통해 SMT를 구성할 때의 예시를 단계별로 보여줍니다. 이 때, 그림 15의 오른쪽 그림이 초기 SMT 구성도라고 가정하고 그림 15는 비어 있는 리프 노드 (Empty leaf node)에 데이터를 넣는 단계를 나타낸 그림입니다. 그림 15와 같이, 키의 값이 5(이진수로 101)인 리프 노드에 데이터(Value)를 추가하고 싶은 경우, 점선 네모 박스 위치에 노드가 만들어지고 앞서 설명한 첫 번째 룰에 의해 오른쪽 그림처럼 구성됩니다.

그림 17는 키의 값이 3(이진수로 011)인 리프 노드에 데이터를 추가 과정을 보여줍니다. 파란색 점선 네모 박스 위치에 노드가 만들어지고 앞서 설명한 두 번째 룰에 의해 오른쪽 그림처럼 구성됩니다. 본 아티클에선 Create 오퍼레이션을 통해 SMT 구성도의 생성과정을 상세히 알아봤고 Update, Read, Delete도 마찬가지로 동작하게 됩니다.

4.4. Sparse Merkle Tree 기반 블록체인 프로젝트 소개

롤업 및 레이어 1 블록체인과 같은 여러 블록체인 프로젝트들이 SMT를 기반으로 상태를 저장하고 있습니다. 이더리서치(Ethresearch)의 아티클에 의하면, 롤업 프로젝트 중에서 Polygon의 zkEVM, zkSync Era, Consensys의 zkEVM에서 SMT를 기반으로 상태를 저장하고 있습니다. 롤업에서 SMT를 사용하는 이유는 non-membership proof를 효율적으로 할 수 있기 때문입니다. 예를 들어, 클라이언트 A의 Layer 1 계정에서 클라이언트 B의 Layer 2 계정으로 자산을 이동할 때, 보내기 전에 수신 계정이 Layer 2에 존재하는지 여부를 쉽게 검증할 수 있습니다.

롤업뿐만 아니라 레이어 1 블록체인에서도 상태 저장을 위해 SMT 개념을 활용합니다. 첫 번째로 앱토스(Aptos)에서는 Jellyfish Merkle Tree라는 SMT를 기반의 데이터 구조로 앱토스의 상태를 저장하고 있습니다. 앱토스는 많은 트랜잭션을 빠르게 처리하기 위해 고성능(High performance) 블록체인에 요구되는 아키텍처에 맞춘 lock-free Sparse Merkle Tree라는 데이터 구조를 사용하며, 이는 여러 프로세스가 동일한 공유 변수에 동시에 접근할 때 공유 변수의 일관성을 유지하기 위한 락킹(Locking) 메커니즘을 사용하지 않습니다. 또한, 이더리움 2.0의 Deposit 컨트랙트에서도 SMT를 활용합니다. 이 컨트랙트에서는 트리 구조와 동일한 크기의 단일 배열을 활용하여 메모리 사용량을 줄이고, 그 결과로 가스비를 절감할 수 있습니다.

5. Introducing other data structures

Merkle Patricia Trie(MPT)와 Sparse Merkle Tree(SMT) 외에도 제안된 다양한 데이터 구조를 소개하고자 합니다.

5.1. Verkle Tree

Verkle Tree는 Ethereum의 확장성과 효율성을 개선하기 위해 제안된 새로운 데이터 구조입니다. Verkle Tree는 Merkle Tree의 기본 구조에 암호학적 증명을 제공하는 Vector Commitment를 결합하여, 상태의 무결성을 보장하고 전체 상태를 빠르게 검증할 수 있도록 지원합니다. 기존의 Merkle Patricia Tree(MPT) 대비하여 membership proof를 하기 위한 데이터의 양을 크게 줄일 수 있었고, 특히 대규모 데이터 저장과 검증 과정에서 더 나은 성능을 제공합니다. Verkle tree는 특히 Ethereum 2.0의 데이터 구조 업그레이드로 관심을 받고 있습니다. Verkle Tree에 대한 심층 분석은 디사이퍼 미디어의 “버클 트리는 머클 트리를 완벽히 대체할 수 있을까?” 아티클을 참고하면 많은 도움이 될 것입니다.

5.2. Namespaced Merkle Tree

DA(Data Availability) 레이어 중 하나인 Celestia는 요청된 애플리케이션의 모든 데이터를 포함하고 있음을 증명해야 합니다. Namespaced Merkle Tree(NMT)는 Celestia DA의 핵심 기능 중 하나입니다. NMT는 SMT와 마찬가지로 Binary Merkle Tree의 일종으로, 트리의 각 노드가 자식들의 최소 및 최대 네임스페이스로 태그됩니다. 트리의 리프 노드들은 메시지의 네임스페이스 식별자에 따라 정렬됩니다. 이를 통해 특정 네임스페이스의 모든 요소가 포함되었음을 검증자에게 증명할 수 있는 Merkle 증명을 생성할 수 있습니다. Celestia는 롤업 데이터의 포함 여부를 쉽게 증명하기 위해 NMT를 사용합니다. 더 자세한 내용은 디사이퍼 미디어의 “Data Availability” 아티클을 참고하면 많은 도움이 될 것입니다.

5.3. Jellyfish Merkle Tree

Jellyfish Merkle Tree (JMT)는 메타(구 페이스북)에서 주도한 블록체인 프로젝트인 Diem(구 Libra) 블록체인에서 사용하기 위해 설계된 효율적이고 확장 가능한 데이터 구조입니다. JMT는 Diem 블록체인을 위해 특별히 설계된 LSM-트리(Log-Structured Merge-tree) 기반 키-값 저장소에 최적화된 공간 및 계산 효율적인 Sparse Merkle Tree 구조를 기반으로 설계되었습니다. JMT는 노드 키, 노드 유형 및 증명 형식을 상당히 최적화하여 데이터 구조의 복잡성, 저장, I/O 오버헤드 및 계산 효율성 사이의 이상적인 균형을 찾아 Diem 블록체인의 요구 사항을 충족합니다. 또한 제시된 JMT 구조는 상태 업데이트와 검증이 빠르고 효율적이고 대규모 데이터베이스에서도 효율적으로 작동할 수 있도록 설계되어 블록체인의 확장성을 높이는데 기여합니다. 더 자세한 내용은 다음 논문을 참고하시기 바랍니다.

6. Summary

블록체인에서 데이터 저장 구조는 데이터의 무결성 유지, 검색 및 검증 효율성, 시스템 성능, 보안, 합의 알고리즘의 구현, 그리고 스마트 계약의 실행에 핵심적인 역할을 합니다. 따라서 효과적인 데이터 저장 구조를 설계하고 구현하는 것은 블록체인 네트워크의 안정성, 신뢰성, 그리고 효율성을 높이는 데 매우 중요합니다. 많은 블록체인 네트워크에서는 각각의 특성에 맞춰 최적화된 데이터 저장 구조를 제시하고 자신의 블록체인에 적합한 형태로 데이터를 관리하고 있습니다.

본 아티클에서는 많은 블록체인에서 사용되는 저장 구조 기술의 핵심 개념인 Merkle Patricia Trie와 Sparse Merkle Tree의 개요와 심층 분석을 다루었으며, Merkle Patricia Trie 외에도 Verkle Tree, Namespaced Merkle Tree, Jellyfish Merkle Tree와 같은 다양한 상태 저장 데이터 구조를 간략히 소개했습니다. 블록체인에서 데이터 저장 구조는 데이터의 무결성, 검색 및 검증의 효율성, 성능, 보안, 합의 알고리즘, 그리고 스마트 계약의 실행에 핵심적인 역할을 합니다. 따라서, 효과적인 데이터 저장 구조를 설계하고 구현하는 것은 블록체인 네트워크의 안정성, 신뢰성, 그리고 효율성을 높이는 데 필수적입니다. 많은 사람들이 블록체인이 데이터를 어떻게 유지하고 관리하는지 이해하는 데 도움이 되었기를 바라고, 블록체인 산업이나 학계에서 최근에 제안되는 데이터 구조 사례를 조사하고 소개할 기회가 있기를 기대합니다.