텐더민트 IAVL 트리에 대해서 알아보자(2)
이전 글에서 IAVL 트리의 기본적인 정렬 알고리즘에 대해서 알아보았습니다. 이번에는 IAVL 트리를 특별하게 하는 여러 특징들에 대해서 알아보겠습니다.
머클 증명
IAVL 트리는 코스모스 네트워크의 IBC(Inter blockchain communication) 프로토콜에서 중요한 역할을 차지합니다. (물론 IBC 프로토콜이 IAVL 트리만으로 제약되는 것은 아닙니다.) IAVL 트리는 유명한 머클 트리인 이더리움의 머클 패트리샤 트리보다 머클 증명이 더 효율적이고 간단합니다.
위의 사진은 가장 간단한 이진 머클 트리의 예시입니다. 머클 트리를 사용해서 블록체인의 모든 상태를 알고있지 않아도 머클 루트와 증거들을 통해서 상태의 존재를 기술적으로 검증할 수 있습니다.
위의 사진은 블록체인 분야에서 아마도 가장 유명한 머클 패트리샤 트리입니다. 하지만 머클 패트리샤 트리는 16진 트리이기 때문에 이진 트리보다 복잡하고 위의 Branch node를 검증하기 위해서는 기본적으로 Branch node의 정보를 모두 알아야하기 때문에 머클 증명이 효율적이라고 볼 수 없습니다.
반면에 IAVL 트리는 가장 간결한 이진 머클 트리 형태이기 때문에 증명을 구현하기 간단하고 언제나 증거의 갯수는 O(logN)이기 때문에 더 효율적입니다.
스냅샷
IAVL 트리는 Immutable 하기 때문에 같은 키의 값이 바뀔 때 그 노드 자체를 바꾸는 것이 아니라 새로운 노드를 만들어서 그 노드를 대체하게 됩니다. 그리고 IAVL 트리는 블록이 커밋되는 시점에 리프 노드부터 해쉬 값이 계산되고 각 노드가 자신의 왼쪽, 오른쪽 노드의 해쉬 값을 기록합니다. 노드는 자신의 해쉬를 키로 해서 데이터베이스에 저장됩니다. 값이 바뀌거나 삭제된 노드도 여전히 데이터베이스에 기록되어 있기 때문에 각 높이의 루트 노드의 해쉬 값만 알고 있으면 그 루트 노드를 통해서 이전의 트리로 쉽게 돌아갈 수 있습니다.
프루닝
하지만 모든 데이터를 계속 해서 가지고 있는 것은 비효율적이기 때문에 노드의 설정에 따라 필요없어진 높이의 데이터를 삭제할 수 있습니다.
위에서 설명한대로 같은 노드를 수정하게 되면 노드를 삭제하는 것이 아니라 새로운 노드로 대체하고 되고 이전의 노드는 고아가 됩니다. 그 고아 노드가 생긴 높이의 스냅샷을 삭제하면 그 고아 노드의 생명 기간을 이전의 스냅샷이 존재하는 높이로 옮기고 만약 생명 기간의 처음과 끝이 같다면 그때는 완전히 삭제하면 됩니다. 위의 경우 저기서 첫번째 스냅샷을 삭제하게 된다면 A노드는 완전히 삭제될 것입니다.
비존재 증명
IAVL 트리는 상태의 존재뿐만 아니라 비존재도 증명할 수 있습니다.
IAVL 트리는 정렬되어 있기 때문에 비존재 증명을 하려는 값의 키보다 작은 노드와 큰 노드의 존재를 증명하고 그 두 노드가 인접해있다는 것을 증명하면 그 사이의 값은 존재하지 않는다는 것을 증명할 수 있습니다.
만약 비존재 증명을 하려는 값의 키가 가장 키가 작은 노드보다 더 작다면 그 노드의 존재를 증명하고 그 노드가 가장 작은 키 값을 가지고 있다는 것을 증명하면 증명하려는 키의 값은 존재하지 않는다는 것이 증명됩니다.
비존재 증명을 하려는 값의 키가 가장 키가 큰 노드보다 더 크다면 위의 경우와 반대로 증명하면 됩니다.
IAVL 트리의 의의
IAVL 트리는 DOS 공격에서 안전하기 때문에 개발자가 자유롭게 이터레이터를 사용할 수 있다는 점에서 이더리움의 패트리샤 트리에 비해 경쟁력이 있습니다.
특히 IAVL 트리는 머클 증명을 더 간단하고 효율적으로 할 수 있다는 점에서 체인 간의 통신에서 큰 강점을 가집니다. 블록체인의 인터넷을 만들겠다는 코스모스 개발팀의 노력을 알 수 있습니다.
