IAVL트리는 Cosmos SDK에서 사용 되는 상태를 저장하기 위한 자료구조로 이더리움의 머클 패트리샤 트라이(MPT)와 같은 역할을 합니다.
AVL 트리
AVL트리는 균형잡힌 이진 탐색 트리(Balanced BST) 이며 기본 이진 탐색 트리에서 데이터가 불균형(노드의 높이의 불균형)하게 쌓여 최악의 경우 삽입, 탐색, 삭제 연산이 O(n)이 되는 것을 해결하기 위해 고안되었습니다.
AVL트리는 내부 노드의 높이차가 최대 1만큼 나는것을 보장하여 노드의 높이를 균형있게 만들며, 따라서 삽입, 탐색, 삭제 연산이 최악의 경우에도 O(log(n))이 보장 됩니다.
AVL트리는 삽입이나 삭제 연산을 한 후 노드의 높이차가 2이상 나게 되면, 리밸런싱을 통하여 높이 차를 최대 1만큼 나도록 형태를 바꾸는 원리입니다.
원리가 궁금하신 분은 논문 이나 AVL 트리 시뮬레이터를 보시면 좋을것 같습니다.
AVL+ 트리
AVL+ 트리는 AVL트리와 다르게 모든 값들을 리프 노드에 저장한 트리입니다. 코스모스 IAVL github페이지에는 알고리즘을 단순화 하기 위해서 사용했다고 적혀있습니다.
AVL+의 모든 값은 리프 노드에 저장 되고 리프 노드를 제외한 나머지 노드는 이너 노드(inner node)로 이루어져있습니다. 이너 노드에는 값이 없고 키만 가지고 있습니다.
다음의 두 트리는 같은 정보를 저장하는데, 일반 AVL 트리는 모든 노드가 키와 값을 가지고 있고 키를 기준으로 노드의 위치가 정렬되어있습니다.
AVL+ 트리에서 값은 모두 리프 노드에 저장이 되고, 이너 노드들은 값은 가지지 않고 키만 가지며, 키는 오른쪽 자식 서브트리에서 가장 왼쪽에 있는 노드의 키를 가지며 오른쪽 자식이 없다면 부모의 키를 키로 갖습니다. 이렇게 이너 노드의 키를 지정하면, 탐색시 일반 BST 처럼 탐색을 할 수 있습니다.
IAVL 트리
IAVL 트리는 AVL+ 트리를 기반으로한 자료구조이며, 데이터베이스 저장, 머클 루트 해쉬를 계산할 수 있는 트리입니다.
Node
먼저 트리의 각 노드는 다음의 구조체로 되어있습니다.
키와 값을 가지고 있으며, 스냅샷을 관리하는 version을 가지고 있고, 머클 루트 해쉬를 계산할 때 사용하는 hash를 가지고 있습니다.
노드 중에서 orphan 노드가 있는데, orphan 노드는 최신 IAVL 트리에 포함되지 않는 노드 입니다. (IAVL 트리는 절대 노드를 지우지 않고 orphan에 저장하는데, 이렇게 하는 이유는 MPT와 마찬가지로 현재 상태 뿐만 아니라 과거 상태들도 트랙킹 하기 위해서 입니다.)
예를들어 키는 2이고 값이 4인 노드를 IAVL 트리에 삽입하려고 합니다.
삽입하면 노드는 주황색 위치에 들어가게 됩니다.
그 이후, 중간에 있는 이너 노드의 키가 달라지고 그림에는 설명되어 있지 않지만, 노드의 해쉬를 계산할때, 자식의 해쉬를 포함하여 계산하기 때문에, 자식이 바뀐다면 해쉬값이 달라지게 됩니다. 즉, 자식 노드가 업데이트 된다면, 부모 노드도 반드시 업데이트 되어야 합니다. 이렇게 달라지는 값을 노드에 업데이트하는 것이 아니라, 새로운 노드를 생성한 후, 그 전 노드는 orphans에 저장합니다.
이렇게 되면 트리의 루트 또한 해쉬값이 달라지기 때문에, 현재 루트를 orphans에 저장하고 루트를 새로 만듭니다.
이렇게 값을 다 바꾼후, 균형이 잘 맞는지 확인합니다. 예시에는 균형이 잘 맞지만, 균형이 잘 맞지 않는다면 리밸런싱을 하며, 균형 잡힌 트리 형태로 바꿉니다.
현재까지는 메모리에서 작동하는 IAVL트리고 이 트리를 데이터베이스에 저장할 수 있어야 합니다. IAVL에는 SaveVersion, GetVersioned, deleteVersion 데이터베이스에 IAVL 트리를 저장하고 불러오고 할 수 있는 함수가 있습니다.
IAVL은 goLevelDB를 사용하는데 goLevelDB는 키밸류 데이터베이스 입니다. Node와 Orphan, Root는 다양한 데이터저장 방식으로 저장되어 있는데, 값으로 바꾸기 위해서 직렬화를 한 후, 각각의 키 포맷에 맞추어 키를 만든 후 저장합니다.
머클 증명
d
/ \
c e
/ \ / \
b c=3 d=4 e=5
/ \
a=1 b=2다음과 같은 IAVL 트리가 있고 a가 1이라고 증명하고 싶다면,
d
/ \
c hash=d6f56d
/ \
b hash=ec6088
/ \
a,hash(1) hash=92fd030다음과 같은 패스를 보내주면 a가 1임을 증명할 수 있습니다.
또한 IAVL은 range proof를 생성 할 수 있는데, range proof를 통해서, 여러 값을 동시에 증명할 수 있습니다.
a=1, b=2, c=3임을 증명하기 위해서는,
d
/ \
c hash=d6f56d
/ \
b c,hash(3)
/ \
a,hash(1) b,hash(2)패스 하나만 보내주면 a=1, b=2, c=3임을 증명 할 수 있으며, range proof를 통해서 키에 해당하는 노드가 없다는것 또한 증명할 수 있습니다.
k라는 키가 없는 것을 증명하고 싶다면, k 보다 큰 노드 b와 k보다 작은 노드 a를 가지고 k가 없음을 증명할 수 있습니다. 위의 range proof 패스로 a와 b사이에 어떠한 노드도 없음을 증명할 수 있기 때문에 k가 없음을 증명 할 수 있습니다.
또한 IAVL 트리는 MPT에 비해서 머클 증명의 크기가 작아서 효율적으로 머클 증명을 할 수 있습니다.
결론
IAVL 트리는 균형 잡힌 이진 탐색 트리(Balanced BST)이기 때문에 삽입, 삭제, 탐색 연산에 대해서 최악의 경우에도 O(log(n))을 보장합니다.
IAVL트리는 스냅샷 기능이 있어서, MPT와 마찬가지로 과거 블록에서의 상태를 볼 수 있습니다. MPT에는 데이터 저장 뿐만 아니라 머클 루트 해쉬를 구할 수 있는데, IAVL트리도 마찬가지로 머클 루트 해쉬를 구할 수 있습니다.
또한 IAVL트리는 MPT보다 머클 증명의 크기가 작기 때문에, 효율적으로 머클 증명을 할 수 있습니다.
참고문헌
[1] Leonid Reyzin, Dmitry Meshkov, Alexander Chepurnoy and Sasha Ivanov, “Improving Authenticated Dynamic Dictionaries, with Applications to Cryptocurrencies”, International Conference on Financial Cryptography and Data Security. [Online]. Available: https://eprint.iacr.org/2016/994.pdf
