HEX-BLOOM: An Alternative to the Merkle Tree[1]를 참고해 작성함.
머클 트리(Merkle Tree)가 블록체인을 비롯한 여러 영역에서 활용되고 있다. 실제로 데이터의 무결성 검증이나 신뢰성을 보이기에 유용한 자료구조이지만, 여러 한계점도 있다. 머클 트리는:
- 암호학적 해시 함수를 많이 활용하고 있고
- 특정 데이터에 대한 검증을 위해 부분적인 해시값들의 전송을 많이 요구하므로
연산과 네트워크 측면에서 비용이 많이 드는 자료구조이다. 일반적으로 로컬 연산보다 네트워크 통신 비용이 더 비싸므로, 머클 트리의 성능은 네트워크 지연(latency)에 달려있다고 볼 수 있다. 이러한 문제들은 머클 트리가 유용함에도 불구하고 널리 활용되기 어렵게 만든다.
이에 저자들은 머클 트리를 대체할 수 있는 모델인 HEX-BLOOM이라는 모델을 제안한다. 이 모델은 네트워크 지연과 관계없이 매우 높은 확률로 데이터의 무결성과 신뢰성을 검증할 수 있다. 확률이 관계된다는 점이 중요한데, 이는 HEX-BLOOM이 블룸 필터(Bloom Filter)에 기반하기 때문이다. 무슨 말인지 알아보도록 하자.
머클 트리
머클 트리는 리프(leaf) 노드가 데이터이며 비-리프(non-leaf) 노드가 자식 노드들의 해시값으로 구성된 포화 이진 트리이다. 이진 트리가 아닌 일반화된 머클 트리 구조도 생각할 수 있지만, 일반적으로 위와 같은 포화 이진 트리로 많이 표현한다.
머클 트리의 루트(root) 노드를 머클 루트라 칭하며, 머클 루트는 데이터들의 요약으로 간주할 수 있다. 임의의 데이터(그림에서 data 6)가 위/변조됐을 경우 머클 루트에 도달하기까지의 비-리프 노드 값이 달라지고, 결과적으로 머클 루트까지 달라지기 때문이다.
머클 트리의 특징적인 요소 중 하나는 머클증명(Merkle Proof)인데, 이를 통해 전체 데이터 없이도 특정 데이터의 무결성 및 신뢰성을 검증할 수가 있다. 위 그림에서 data 6(그림에서 붉은색 블록)과 그 머클경로(Merkle Path, 그림에서 파란색으로 표시한 블록들)만으로 머클 루트를 만들어낼 수 있음을 잘 생각해보자.
이 과정에서는 여러 해시값과 네트워크 트래픽이 요구되기 때문에 머클 트리의 전체적인 성능이 저하된다. 반대로 1. 전체 검증을 하거나 2. 네트워크 트래픽을 줄이기 위해 전체 머클 트리 데이터를 저장하려면 많은 양의 메모리가 요구된다.
앞서 언급했듯이 머클 트리는 (생성, 삭제, 업데이트 등에) 많은 시간과 연산을 소모하는 자료구조이다. 그 역사가 깊기 때문에 시간과 공간 복잡도 문제를 해결하기 위한 여러 변형[2–7]이 존재하지만, 여전히 현저히 많은 자원을 요구한다. 물론 무의미하게 소모하는 것은 아니고 덕분에 데이터의 무결성 및 신뢰성을 검증할 수 있으니, 트레이드-오프라 할 수 있겠다.
예를 들어 새 노드(데이터)를 추가하는 상황을 생각해보자. 단순히 하나의 데이터 노드를 추가하는 것으로 끝나지 않는다. 트리 크기의 큰 확장이 요구될 수 있고, 연관된 (아마 거의 대부분의) 비-리프 노드가 달라진다는 문제가 발생한다. 머클 트리에서는 암호학적 해시 함수를 사용하기 때문에 그 연산 비용이 상당하다.
글의 첫 부분에서 언급했지만, 일반적으로 로컬 연산 비용보다 네트워크 통신 비용이 더 비싸다. 머클 트리에서도 통신 횟수를 줄이는 것이 중요하지만 쉽지 않다. 자명하게도, 머클 트리의 모든 노드를 검증하기 위해서는 적어도 그 리프 노드 개수만큼의 통신이 요구된다. 전체 사용자 수를 η명, 리프 노드의 개수를 L, 그리고 전체 노드의 개수를 n이라 하면 전체 검증을 위한 비용은 무려 O(η*L*log_n)나 된다.
블룸 필터
블룸 필터는 µ-bit 배열을 가지는 멤버십 필터이다. 배열은 0으로 초기화되어 있다. 새로운 항목이 추가될 때 이 배열의 k개 원소가 영향을 받게 되는데,
- 항목에 대해 k개의 서로 다른 해시 함수를 이용해 k개의 결과값을 구하고
- 해시값 각각을 인덱스로 삼아 배열에 접근해
- 만일 그 원소가 0이면 1로 변경, 1이면 그대로 둔다.
이때 해시 함수의 결과값은 배열의 인덱스 범위인 0과 µ 사이의 값으로 도출된다.
블룸 필터를 이용하면 ‘어떤 항목이 집합에 속해 있는지’에 대한 질문에 답할 수 있다.
- 항목에 대해 k개의 서로 다른 해시 함수를 이용해 k개의 결과값을 구하고
- 해시값 각각을 인덱스로 삼아 배열에 접근해
- 만일 모든 원소가 1이면 확률적으로 ‘속한다(속할 수도 있다)’로 판단하고
- 하나라도 0이 있으면 ‘속하지 않는다’로 판단한다.
서로 다른 항목에 대해 해시값이 겹칠 수도 있으니, ‘속한다’라는 판단은 확률적으로 이루어짐에 주의하자. 블룸 필터는 긍정 오류(false positive)가 발생할 수 있는 자료구조이다. 적절한 µ과 k에 대해서 블룸 필터는 낮은 긍정 오류 확률을 보인다.
블룸 필터에 항목을 추가하는 데 드는 비용은 해시 연산에 요구되는 만큼인 O(k)이다. 상수로 취급할 수 있으니 O(1)으로 봐도 좋다.
블룸 필터의 추가 공간 복잡도는 얼마일까? 몇 번의 계산을 통해 긍정 오류 확률을 최소로 줄이는 최적의 k 값을 도출할 수 있다:
여기서 n은 추가하는 항목의 개수이다.
모든 배열의 원소가 1이 될 확률(ε)을 계산해보면 다음과 같고:
최적의 k값을 대입해 정리하면 공간 µ는 다음과 같이 정리된다(자세한 내용은 논문[1]을 참고):
위 식을 통해 추가되는 항목 개수(n)와 목표하는 긍정 오류의 확률(ε)에 따른 요구되는 메모리 사이즈(bit)를 계산할 수 있다.
두 자료구조를 비교해보자. 블룸 필터는 전반적으로 머클 트리보다 빠른 속도를 보인다. 머클 트리는 암호학적 해시 함수를 사용하는 반면 블룸 필터는 비-암호학적 해시 함수를 사용한다. 구축 및 검증에 드는 비용도 적다. 그러나 블룸 필터는 확률적으로 긍정 오류의 가능성을 내포하므로 어떤 측면에서든 머클 트리를 완전히 대체할 수 없다.
HEX-BLOOM
저자들이 제안하는 HEX-BLOOM은 시간 및 공간 복잡도가 높은 고비용의 머클 트리를 대체하고자 하는 모델이다. 이 시스템은 LinkedHashX와 블룸 필터로 구성된다. 블룸 필터는 이제 알고 있으니, LinkedHashX가 무엇인지 살펴보자.
LinkedHashX
LinkedHashX는 해시와 XOR 연산(⊕)을 이용해 머클 트리를 대체하려 한다. 가령 데이터가 1에서 8까지 존재한다고 하자. 여기서 데이터의 개수 L=8이다. LinkedHashX의 루트는 다음과 같이 계산된다:
- h_{1} ⊕ h_{2} = h_{12}
- h_{12} ⊕ h_{3} = h_{123}
- …
- h_{12…67} ⊕ h_{8} = h_{12…78}
- LinkedHashX의 루트 h_{root} = h(h_12…78)
데이터 각각에 대해 한 번씩 해시(h)가 취해지므로, 해시 연산은 총 L번 이루어진다. 마지막 루트를 구하기 위한 해시 연산까지 포함하면 (L+1)번이다. XOR 연산은 (L-1)번 이루어진다. 이는 같은 크기의 머클 트리에서 해시 연산이 (2L-1)번 계산되는 것과는 대조적으로, 암호학적 해시 함수의 연산보다 XOR 연산이 훨씬 빠르다는 점을 고려하면 큰 차이이다.
더욱이, 새 노드의 추가와 제거가 LinkedHashX에서는 O(1)에 가능한데, 추가적인 한 번의 해시 연산과 한 번의 XOR 연산만 있으면 되기 때문이다. 업데이트는 삭제와 추가를 연달아서 하는 것으로 볼 수 있으니 마찬가지로 O(1)이다. 머클 트리보다 훨씬 빠름이 자명하다. 공간 복잡도는 어떨까? LinkedHashX는 추가적인 공간을 사용하지 않으니 O(1)이다.
그러나 LinkedHashX는 데이터의 부분만을 검증할 수가 없다는 단점이 있다. 머클 트리는 머클 증명을 통해 일부 데이터의 무결성 및 신뢰성의 검증이 가능하다. 반면 LinkedHashX는 무조건 모든 데이터를 다운로드해서 검증해야한다. 따라서 LinkedHashX만으로는 머클 트리의 모든 기능을 대체할 수 없다.
다시 HEX-BLOOM
그래서 저자들이 제안하는 HEX-BLOOM은 LinkedHashX와 더불어 블룸 필터까지 사용한다. 모든 해시값은 블룸 필터에 추가된다. 블룸 필터에 항목 L개를 추가하기 위해 추가 연산은 kL 만큼 요구되고, 이들 해시 연산은 비-암호적 해시 연산임을 감안하면 그렇게 큰 오버헤드가 아니다.
이제 LinkedHashX와 블룸 필터를 이용해 검증하게 되는데, 빠른 연산인 XOR과 비-암호적 해시 함수들을 사용한 덕분에 전반적으로 매우 적은 비용만을 지불하면 된다. 연산 비용만이 아니라 공간 비용도 절감할 수 있다.
전체 데이터 검증을 다루기 위해 머클 트리가 O(L)번 통신해야 했음을 생각해보자. 반면 HEX-BLOOM은 LinkedHashX 루트와 블룸 필터만 가지고 있으면 추가적인 네트워크 통신을 필요로 하지 않는다. 통신 비용이 연산 비용보다 훨씬 비싸다는 점을 상기해보자. 이는 매우 큰 절감이다.
단점/약점
다만, 잘 생각해보면 블룸 필터는 긍정 오류가 발생할 수 있어 머클 트리를 완전히 대체할 수 없다고 했었다. HEX-BLOOM 역시 여전히 같은 문제를 겪는다. 블룸 필터로 검증한 데이터들로부터 LinkedHashX 루트를 구축했더니 기록된 값과 다를 수 있다. 이 경우 어느 데이터가 문제를 야기한 것인지 검출할 수도 없다는 한계를 가진다. 그러나 이러한 긍정 오류는 (적절한 하이퍼파라미터들로부터) 발생할 가능성이 거의 없을 것이기 때문에 괜찮다고 한다. 흠. 🤔
꼭 블룸 필터를 고집할 필요는 없는데, 비슷한 역할을 수행할 수 있는 Cuckoo 필터[8], Morton 필터[9], 혹은 XOR 필터[10]를 이용해도 된다. 이들 필터 모두 확률적인 요소를 가진 필터이므로 여전히 문제는 해결되지 않지만.
결론
머클 트리가 팔방미인 자료구조는 아니기 때문에, 단점을 보완하거나 대체하기 위한 모델은 꾸준히 연구되어 왔다. 저자들의 HEX-BLOOM 역시 그러한 모델 중 하나이다. HEX-BLOOM은 시간 및 공간 복잡도에서 머클 트리 대비 훨씬 우수한 성능을 가진다. 빠르고 메모리도 덜 차지하면서 네트워크 통신도 추가로 요구되지 않는데 머클 트리가 하는 역할을 대신할 수 있으니, 말 그대로 좋은 자료구조이다.
그러나 (비록 저자들은 그 가능성이 작다고 주장하지만) 긍정 오류를 이용한 데이터의 위변조가 가능하기 때문에, 블록체인에 적용되기에는 한계가 있을성싶다. 블록체인 외에도 스마트그리드(smart grid)나 사물인터넷, 생물 의학, 금융 거래 등에 머클 트리가 널리 적용되고 있다고 하니, 해당 영역들에서 용처를 찾아보면 좋을 듯하다.
참고문헌
[1] Ripon Patgiri and Malaya Dutta Borah, “HEX-BLOOM: An Alternative to the Merkle Tree”, Cryptology ePrint Archive: Report 2021/773, 2021. [Online]. Available: https://ia.cr/2021/773
[2] M. Jakobsson, T. Leighton, S. Micali, and M. Szydlo, “Fractal Merkle Tree Representation and Traversal,” in Topics in Cryptology — CT-RSA 2003. Berlin, Germany: Springer, Feb 2003, pp. 314– 326.
[3] M. Yu, S. Sahraei, S. Li, S. Avestimehr, S. Kannan, and P. Viswanath, “Coded merkle tree: Solving data availability at- tacks in blockchains,” in Financial Cryptography and Data Security, J. Bonneau and N. Heninger, Eds. Cham: Springer International Publishing, 2020, pp. 114–134.
[4] J. Mao, Y. Zhang, P. Li, T. Li, Q. Wu, and J. Liu, “A position-aware Merkle tree for dynamic cloud data integrity verification,” Soft Comput., vol. 21, no. 8, pp. 2151–2164, Apr 2017.
[5] Z. Sun, Y. Liu, J. Wang, F. Mei, W. Deng, and Y. Ge, “Non- cooperative game of throughput and hash length for adaptive merkle tree in mobile wireless networks,” IEEE Transactions on Vehicular Technology, vol. 68, no. 5, pp. 4625–4650, 2019.
[6] U. Chelladurai and S. Pandian, “HARE: A new Hash-based Authenticated Reliable and Efficient Modified Merkle Tree Data Structure to Ensure Integrity of Data in the Healthcare Systems,” J. Ambient Intell. Hum. Comput., pp. 1–15, Apr 2021.
[7] Y. Zou and M. Lin, “Fast: A frequency-aware skewed merkle tree for fpga-secured embedded systems,” in 2019 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), 2019, pp. 326–331.
[8] B. Fan, D. G. Andersen, M. Kaminsky, and M. D. Mitzenmacher, “Cuckoo filter: Practically better than bloom,” in Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, ser. CoNEXT ’14. New York, NY, USA: Association for Computing Machinery, 2014, p. 75–88. [Online]. Available: https://doi.org/10.1145/2674005.2674994
[9] A. D. Breslow and N. S. Jayasena, “Morton filters: Faster, space-efficient cuckoo filters via biasing, compression, and decoupled logical sparsity,” Proc. VLDB Endow., vol. 11, no. 9, p. 1041–1055, May 2018. [Online]. Available: https: //doi.org/10.14778/3213880.3213884
[10] T. M. Graf and D. Lemire, “Xor filters: Faster and smaller than bloom and cuckoo filters,” ACM J. Exp. Algorithmics, vol. 25, Mar. 2020. [Online]. Available: https://doi.org/10.1145/3376122
