버클 트리는 머클 트리를 완벽히 대체할 수 있을까?
- 참고 논문: Kuszmaul, John. “Verkle trees.” Verkle Trees (2019): 1–12.
지난 8월, ‘HEX-BLOOM은 머클 트리를 대체할 수 있을까?’라는 게시글을 통해 HEX-BLOOM이라는 자료구조를 소개한 바 있다:
이 HEX-BLOOM은 LinkedHashX와 블룸 필터를 사용해 머클 트리를 대체하는, 시간 및 공간 복잡도 문제를 경감한 모델이다. 머클 트리와 대비해 빠르고, 특히 데이터 검증을 위한 네트워크 통신 비용도 줄일 수 있어 강점이라고 소개했었다.
그러나 HEX-BLOOM의 블룸 필터에서는 긍정 오류가 발생할 수 있어 머클 트리를 완벽히 대체할 수 없다. 때문에 무결성을 주된 덕목으로 생각하는 블록체인에 사용하기는 부적절하다.
HEX-BLOOM은 머클 트리를 완벽히 대체할 수 없다. 적어도 블록체인에서는.
이번에 소개할 버클 트리(Verkle Trees) 역시 머클 트리를 대체하기 위해 고안된 자료구조이다.
- 버클 트리에서는 머클 트리에서의 암호학적 해시 함수를 대신에 벡터 커미트먼트를 사용한 덕분에,
- 브랜칭 팩터(branching factor)를 조정하는 것으로 연산력과 대역폭 간의 트레이드-오프를 직접 조절할 수 있다.
이게 무슨 말인지 차근차근 살펴보도록 하자. 머클 트리에 대한 기본적인 내용은 HEX-BLOOM 게시글에서 다룬 바 있으니, 해당 내용을 우선 참고하고 본 게시글을 읽기를 추천한다.
머클 트리
머클 트리에서 머클 증명(Merkle Proof)을 이용해 효율적인 멤버십 증명을 할 수 있다는 사실은 잘 알려져 있다. 위 그림에서 data6이 (머클 트리를 형성하는) 멤버인지 아닌지를 판단해보자.
- 가장 쉬운 방법은 data1부터 data8까지 모든 데이터를 통해 머클 트리를 재구축해보는 것이다.
- 더 효율적인 방법을 생각해보자. 붉은색으로 표시된 data6, 그리고 파란색으로 표시된 머클 증명만 있으면 머클 루트를 복구해낼 수가 있다.
후자를 통해 멤버십 증명을 하기 위한 데이터의 양을 크게 줄일 수 있다. 전체 데이터의 개수를 N이라 하면, 전자는 O(N)을 요구하지만 후자는 O(log_2(N))만을 요구한다.
요구되는 데이터 양을 선형에서 로그스케일로 줄였다는 점은 매우 괄목할만하나, 안타깝게도 고작(?) 로그스케일이기 때문에, 머클 트리의 크기가 커짐에 따라 점차 비효율적이게 된다. 어떻게 더 줄일 방법이 없을까?
k-ary 머클 트리
쉽게 생각해 볼 수 있는 방법은 두 개씩 있는 자식 노드의 개수를 세 개 이상으로 확장하는 것이다. 이를 브랜칭 팩터(branching factor)라 하며, 앞으로 k로 지칭할 것이다. 또한, k-ary 머클 트리는 부모 노드 당 자식 노드의 개수가 k 개인 머클 트리를 지칭한다.
간단히 보자면 머클 트리의 일반화라고 볼 수 있겠다.
위 그림은 3-ary 머클 트리의 예시이다. 우선 눈에 띄는 사실은 트리의 높이가 줄어들었다는 것이다. 정확하게는 O(log_2(N))에서 이제 O(log_k(N))으로 줄어들게 된다.
그러면 머클 증명의 크기도 줄어들었을까? 안타깝게도 높이는 줄어들었지만 한 레벨(층)에서 요구되는 데이터의 양은 (k-1)으로 늘었다. 종합하자면 O(k*log_k(N))의 데이터가 요구된다. k>2의 상황에서 k-ary 머클 트리는 그냥 머클 트리(k=2)보다 오히려 더 비효율적이다.
위 그림에서 붉은색이 머클 트리의 log_2(N), 초록색이 k-ary 머클 트리의 k*log_k(N) 그래프에 해당한다. N≥1 영역에서 항상 초록색 그래프가 붉은색 그래프 위에 존재함을 알 수 있다.
벡터 커미트먼트
버클 트리를 얘기하기에 앞서, 먼저 커미트먼트와 벡터 커미트먼트에 대해 알아보자.
커미트먼트
(암호학적) 커미트먼트는 나중에 참이었음을 밝히기 전에, 무엇인가를 지금은 숨긴 상태에서 참인 것으로 확약 하고 싶을 때 사용된다. 커미트먼트를 구현하는 가장 단순한 방법은 단반향 함수를 사용하는 것이다. 대표적으로 해시 함수가 있다.
- 값 2를 커밋하고 싶다.
- 2에 대한 해시 53c234e5e8472b6ac51c1ae1cab3fe06fad053beb8ebfd8977b010655bfdd3c3를 우선 전송 혹은 등록한다.
- 은닉성을 더하기 위해 무작위 값을 함께(2 + 무작위 값의 조합을) 커밋할 수 있다. 이 경우 값 2를 무작위 값 327과 함께(2, 327) 계산한 해시 99f21892d9d8590152d2e9299722c9ed9c6b242681b793562eae5c1ffefff8b8를 등록한다.
- 나중 단계에서 값(그리고 무작위 값)을 요청해 커미트먼트가 올바르게 만들어졌음을 증명할 수 있다.
커밋할 값을 v, 무작위 값을 r, 그리고 이들로부터 형성한 커미트먼트를 C(v, r)라고 하자. C는 은닉과 구속이라는 커미트먼트 스킴의 주요한 두 속성을 모두 충족한다.
- 은닉(Hiding): 커미트먼트 C는 커밋한 값을 드러내지 않는다. 무작위 값 r이 추가되며 의미상(semantic) 보안도 확보된다.
- 구속(Binding): 커미트먼트 C(v)를 v으로부터 만든 이상, 다른 값 v’으로 만들었다고 주장할 수 없다.
커미트먼트를 형성하는 방법은 해시 외에도 다양하게 존재한다. 가령 단반향 함수 중 하나인 타원곡선 스칼라배 연산을 이용하면 동형(homomorphic)의 특징을 가지는 커미트먼트 스킴을 만들 수 있다. 타원곡선에 대한 자세한 내용은 이전에 포스팅한 게시글을 참고하길 바란다:
다시 벡터 커미트먼트
벡터는 값들의 나열이고, 그렇다면 벡터 커미트먼트는 순서가 있는 값의 나열을 커밋(commit)할 수 있는 기법을 의미할 것이다. 간단히 말하자면 그렇다.
벡터 커미트먼트는 연산 과정에서 각 원소에 대응하는 증거(π)들을 형성하고, 이를 이용해 멤버십 증명을 할 수 있다. 증거들이 각자 만들어지기 때문에 멤버십 증명의 크기는 O(1)에 해당한다. O(1)이라는 말은 가장 최적화된 수준임을 의미한다.
그러나 벡터 커미트먼트를 형성하는 것에는 O(N²)의 비용이 요구되므로 연산 성능의 한계가 존재한다. 멤버십 증명의 크기가 적당히 작으면서, 로컬 연산도 적당하게 수행하는 그런 자료구조가 필요한 시점이다. 더 좋은 것은 연산과 크기의 트레이드-오프를 경우에 따라 조절할 수 있는 기능성이 있는 자료구조이다. 그게 바로 버클 트리이다.
버클 트리
버클 트리(Verkle Tree)의 핵심 인사이트는 다음과 같다:
- 단순히 벡터 커미트먼트만을 이용하는 것이 아니라 머클 트리에 기반하면서도,
- 머클 트리를 형성할 때 암호학적 해시 함수가 아닌 벡터 커미트먼트를 사용
버클 트리를 형성하는 절차는 다음과 같다. 위 그림은 k=3에서 절차에 따라 버클 트리를 형성한 것이다.
- 브랜칭 팩터 k를 결정한다.
- 데이터 k 개를 모아 커미트먼트를 형성한다. 이 커미트먼트가 k 개의 데이터들에 대한 부모 노드가 된다.
- 위 단계를 같은 층의 모든 데이터에 대해, 그리고 각 층에 대해 재귀적으로 반복해 트리를 형성한다.
벡터 커미트먼트는 해당하는 멤버십 증거와 함께 계산된다. 따라서 데이터에 대한 증거(π)가 각 노드에 함께 포함되어 있다. 가령, π_1은 커미트먼트 C_1에 대해 data1에 상응하는 멤버십 증거이다.
그러다 보니 멤버십 증명을 만들 때 상응하는 증거를 각 층에 하나씩, 그것도 자기 노드에 들어 있는 데이터를 가지고 수행할 수 있다. 따라서 버클 트리의 멤버십 증명은 O(log_k(N))으로 가능하다. 이는 머클 트리와 비교하면 log_2(k) 배의 차이이고, k-ary 머클 트리와 비교하면 k 배의 차이이다. 만일 k를 1024로 설정하면 머클 증명의 크기를 log_2(1024)=10배나 줄일 수 있다.
물론 이를 위해 로컬 연산을 더 많이 요구하지만, 일반적으로 네트워크 통신의 비용이 로컬 연산보다 훨씬 비싸므로 괜찮은 거래라 할 수 있다.
대신 각 노드에 대해 증거들을 추가 계산해야 하니 버클 트리를 형성하는 것에는 O(kN)의 노고가 들어간다. 머클 트리와 k-ary 머클 트리의 O(N)과 비교하면 상수배만큼 더 크지만, 벡터 커미트먼트의 O(N²)과 비교하면 훨씬 작다.
결론
본 게시글에 등장한 자료구조들의 성능을 한 표로 정리하면 다음과 같다:
해당 열에서 가장 최적화된 수치는 푸른색으로, 가장 비효율적인 수치는 붉은색으로 표시하였다. 이를 살펴보면 버클 트리는 무난한 수준의 성능을 보이는 자료구조임을 알 수 있다.
또한, 브랜칭 팩터 k를 조정하는 것으로 형성에 요구되는 비용과 네트워크에 요구되는 비용(멤버십 증명 크기)의 트레이드-오프를 조절할 수가 있다. 용처에 따라 가장 적합한 수준을 결정하면 될 것이다.
자, 그렇다면 글 초반에 던진 질문에 답해보자. 버클 트리는 머클 트리를 완벽히 대체할 수 있을까? 물론 완벽하다는 키워드가 자극적이기는 하지만, 적어도 이 게시글에서 언급된 범위에 한해서는, “그렇다”.
- CURG(Crypto United Research Group)는 2018년 5월 대학(원), 기업, 스타트업 등 다양한 분야의 열정적인 블록체인-er들이 모인 연합 연구 그룹입니다. CURG는 2018년 5월 출범된 이후, ‘Trendy, Thoughtful, and Transdisciplinary’ 한 자세로 한 주도 빠짐없이 블록체인 연구를 지속해오고 있습니다.
- 디사이퍼(DECIPHER)는 “건강한 블록체인 생태계 조성에 기여한다” 라는 미션 아래 블록체인에 대해 연구하고 이를 실용적으로 응용하는 서울대 블록체인 연구 학회입니다. 2018년 3월에 처음 조직 되어 현재까지 블록체인 기술을 다방면에서 연구하고 산업계에 응용하고 있는 100명 이상의 회원들을 배출해왔습니다. 다양한 팀별 연구활동과 프로젝트, 컨퍼런스 개최, 서울대학교 블록체인 강의 개설, 유수 기업들과의 산학협력과 파트너십 체결을 해오며 국내 최고의 블록체인 학회로 자리 잡았습니다.
커그와 디사이퍼는 향후 적극적인 협력을 통해 블록체인 필드에서의 강력한 시너지를 구축하고자 합니다.
