Sparse Merkle Tree란 무엇일까? (번역)

January 19, 2019

Cover

역주: 이 글은 다음 Kelvin Fichter의 글을 번역했습니다. 만약 트리에 대한 지식 (e.g. Root Node, Leaf Node, Siblings)이 없으시다면 트리에 대해 따로 설명된 글을 읽고 오시는 것을 추천드립니다.

What’s a Sparse Merkle Tree? - Kelvin Fichter - Medium

만약 당신이 최근에 이더리움 리서치 커뮤니티를 지켜보고 있었다면, 아마도 사람들이 Sparse Merkle Tree (SMT) 란 것에 대해 이야기하는 걸 들어보셨을 겁니다. 이름만 들으면 무서워 보이는데요, 실제로는 간단한 개념입니다.

이 글에서는 SMT가 무엇이며 왜 좋고, 어디에 쓰이는지를 소개하려고 합니다.

머클 트리 (Merkle Trees)

먼저 간단히 머클 트리에 대해 복습해보겠습니다. 머클 트리는 어떤 데이터 셋에 대해서 암호학적인 Commitment를 할 수 있게 해주는 자료구조입니다. (역: 이 글에서 Commitment Scheme에 대해 한글로 자세히 설명이 되어 있습니다)

먼저 데이터 셋 안의 각각의 데이터들을 해싱하는 것부터 시작해서, 두개를 묶어서 해싱하고, 두개를 묶어서 해싱하는 방식으로 루트 노드만 남을 때까지 해싱해 봅시다. 그러면 다음과 같은 모양이 됩니다.

포함 증명 (Inclusion Proof)

트리의 루트 노드는 그냥 해시기 때문에, 트리 안의 내용에 대해선 아무 것도 담고 있지 않습니다. 그래서 우리는 “Merkle Proof”이라는 걸 사용해서 어떤 데이터가 실제로 트리의 일부분이라는 사실을 보일 수 있습니다.

예를 들어, A 가 위 그림의 트리 안에 포함된다는 것을 증명해봅시다. 우리가 해야 할 건 단지 A 위의 자매 노드들을 제공하고, 그걸로 머클 트리를 다시 계산해서, 원래 트리와 일치하는지 체크하면 됩니다.

A 노드와 그에 해당하는 자매 노드들이 표시된 그림. 이를 Merkle Path라고 한다.

위 그림처럼 파란색으로 강조된 자매 노드들을 보실 수 있습니다. 단지 A, H(B), H(H(C)+H(D)) 값만을 통해 우리는 원래 루트 해시를 계산할 수 있습니다. 전체 트리 내용을 드러내지 않아도, A가 트리에 속한다는 걸 증명할 수 있기 때문에 효율적입니다!

포함되지 않다는 걸 증명하기 (Proving Non-Inclusion)

그래서 우리는 뭔가가 머클 트리 안에 포함된다는 걸 쉽게 증명할 수 있는데요, 그런데 만약 뭔가가 머클 트리 안에 없다는 사실은 어떻게 증명할 수 있을까요? 슬프게도 일반적인 머클 트리로는 마땅히 좋은 방법이 없습니다. 만약 머클 트리의 모든 내용을 드러낸다면 가능할 지도 모르겠지만, 그렇게 한다면 애초에 머클 트리를 쓰는 의미가 없어지니까요.


Sparse Merkle Tree (SMT)

드디어 Sparse Merkle Tree가 등장할 시간입니다! Sparse Merkle Tree는 일반적인 머클 트리와 비슷하지만, 트리 안의 데이터가 키값으로 인덱싱되어 있으며, 해당 데이터가 위치한 Leaf 순서가 해당 데이터의 키값이 되게 됩니다.

예를 들어 Leaf가 4개인 머클 트리가 있다고 합시다. 이 트리 안에는 A, D라는 노드가 각각 첫번째, 세번째 Leaf에 위치해있다고 합시다.

잠깐, 그러면 나머지 Leaf들은요? 그냥 비어있게 내버려 둡시다. 정확하게는, 특별한 값 (e.g. null)을 넣어서 비어있다고 표시해둡시다. 그럼 트리가 이렇게 생겼을 겁니다.

포함 증명

일반적인 머클 트리와 똑같이 머클 증명을 통해 A가 트리의 일부분이란 걸 증명할 수 있습니다. 이 증명은 보시는 것처럼 일반적인 머클 증명과 완전히 똑같습니다.

아까 했던 것처럼, 그냥 Sibling 노드 (H(null), H(H(null)+H(D)))를 제공해서 루트 해시와 일치하는 지 확인합니다.

미포함 증명 (Proving Non-Inclusion)

여기서 마법이 일어나게 됩니다. 만약 C가 트리에 포함되지 않았다는 걸 증명하지 않으려면 어떻게 해야 할까요? 이번엔 쉽습니다! 우리는 만약 C가 트리의 일부분이라면, 세번째 자리에 올거란 걸 알고 있습니다. C가 트리의 일부분이 아니라면, 그 자리엔 null이 들어있을 겁니다.

즉, 우리에게 필요한 건 세번째 자리에 null이 들어있다는 걸 보이는 일반적인 머클 증명입니다!

C가 포함되지 않았다는 것을 증명하는 미포함 증명

일반적인 머클 증명이랑 똑같이 생겼습니다. 이제 해당 Leaf 자리에 C 대신 null이 들어있다는 사실만 다를 뿐입니다. Sparse Merkle Tree에서 가장 좋은 점은, 이렇게 SMT를 통해 Key-Value 스토어 구조를 머클 트리 안에서도 구현할 수 있다는 점입니다!

문제점

Sparse Merkle Tree는 효율적으로 미포함 증명 (Proofs of non inclusion)을 할 수 있게 해준다는 점에서 정말 멋집니다. 그런데 이건 반대로 SMT가 엄청나게, 정말 엄청나게 커질 수 있다는 이야기도 됩니다. 우리가 예시로 다룬 알파벳 인덱스는 26글자밖에 안되지만, 우리는 평소에도 2²⁵⁶ 길이만큼의 해시를 다루고 있잖아요! 그 경우엔 트리를 생성하기엔 인덱스 수가 너무 많습니다.

다행히 효율적으로 머클 트리를 생성하는 몇가지 테크닉이 나와 있습니다. 그 테크닉의 핵심은 바로 이 거대한 Sparse Merkle Tree 공간의 대부분이… 비어있단 점입니다. H(null) 은 일정한 상수 값이고, H(H(null)) 도 마찬가지고… 그래서 대부분의 트리 내용이 손쉽게 캐시될 수 있습니다!

이는 우리가 256비트 길이의 해시를 다루는 깊이 256짜리 Sparse Merkle Tree라고 해서 머클 증명의 길이가 해시 256개짜리일 필요는 없단 걸 의미합니다. 대부분이 비어있어 캐시될 수 있기 때문에, 머클 증명 또한 엄청나게 짧습니다.

사용 사례

Sparse Merkle Tree는 블록체인 위에서 멋진 일들을 하기 위해 많이 사용되고 있습니다.

플라즈마 캐시는 예치된 자산 정보를 저장하기 위해 SMT를 사용합니다. 모든 플라즈마 캐시 자산에는 고유 ID가 부여되는데, 어떤 자산이 다른 사용자에게 전송되었을 때 그 트랜잭션 정보는 Sparse Merkle Tree 안에 해당 자산의 인덱스에 저장되게 됩니다! 그래서 트랜잭션 히스토리를 검증하기 위해서 포함 증명 (Proof-of-inclusion) (아니면 미포함 증명)을 사용합니다.

심지어 이더리움 자체에도 Sparse Merkle Tree가 쓰일 지도 모릅니다! 이더리움 리서쳐들은 현재 이더리움의 상태를 저장하는 데 사용중인 Merkle Patricia Trie의 대안으로 Sparse Merkle Tree를 사용하는 방안에 대해서도 연구하고 있습니다.



Blockchain
Blockchain
Plasma