최근에 Gleb Naumenko, 전 동료인 Greg Maxwell시와 함께 미니스케치(Minisketch)를 공개했습니다. 미니스케치란, 분산시스템을 구성하는 각 노드간 데이터를 동기할 때 필요한 대역폭을 감소시키는 소프트웨어 라이브러리입니다.

미니스케치는 본래 비트코인 네트워크를 구성하는 노드 간 트랜젝션 정보를 공유할 때 사용되는 세트조화 릴레이 방식(set reconciliation relay, SRR) 연구 프로젝트의 일부로 개발이 진행되어 왔습니다. SRR의 목적은 비트코인 풀노드를 운영할 때 필요한 대역폭을 크게 감소시키는 것입니다.

금일 미니스케치를 SSR 와는 독립적으로 먼저 공개하는 이유는, 본 라이브러리가 비트코인 이외의 분야에서도 폭넓게 어플리케이션 개발에 도움이 될 것이라고 판단하였기 때문입니다.

미니스케치를 왜 사용하는지

모든 분산시스템은 예전부터 시스템을 구성하는 노드 간 데이터를 동기화시키는 것이 쉽지 않았습니다. 반면, 중앙화된 시스템의 경우, 중앙시스템에서 각 노드가 가져야 할 데이터를 정하고 관리할 수 있기 때문에 데이터의 동기화는 쉽게 이뤄질 수 있었습니다.

하나의 예로, 분산시스템에서 노드의 동기화에 사용되는 기술로 Invertible Bloom Lookup Tables(IBLT)를 들 수 있습니다. CPU 사용률은 비교적 낮습니다만, 노드 간 데이터의 차이가 적으면 적을 수록 많은 대역폭이 필요하게 됩니다. 미니스케치는 대역폭을 더욱 효과적으로 사용하는 알고리즘인 PinSketch를 기반으로 사용합니다. 미니스케치는 대역폭을 효율적으로 사용하는 세트조화 알고리즘 중 CPISync 나 PinSketch에 비해 더욱 적은 계산능력을 요합니다. 미니스케치는 PinSketch 보다 20배에서 100배, CPISync 보다 때로는 천 배 이상의 속도로 동기화할 수 있습니다.

어떻게 개선되었는지

미니스케치에서 구현된 세트조화(set reconciliation)는 각 노드가 수학적 ‘스케치’를 생성 및 활용하여 노드가 보유한 모든 데이터를 송신할 필요 없이 타 노드와 비교할 수 있게 되어 더욱 효과적인 대역폭 사용이 가능해집니다. 스케치의 크기는 데이터 세트와 무관하며 타 노드와의 데이터 불일치의 기대치에 의해 정해집니다. 스케치를 비교하는 것 만으로도 타 노드와의 차이점을 확실하게 파악할 수 있게 됩니다.

아래에서 구체적으로 어떻게 차이점을 산출하는지 설명하도록 하겠습니다. 가령, A는 {3,5,7,11}, B는 {3,5,7,9,11}의 데이터 세트를 가지고 있다고 가정합니다. 각 데이터 세트의 요소의 합을 계산하면, A의 경우 3+5+7+11=26, B의 경우, 3+5+7+9+11=35가 됩니다. A의 합계인 26을 B에게 송신하고, B가 본인의 합계 수치에서 뺄셈을 하여 차이점인 9를 산출할 수 있습니다. 다만, 이 예시의 경우 하나의 차이점만 산출할 수 있는데, 미니스케치에서는 데이터 세트의 다양한 ‘합계들’을 계산하여 송신하게 됩니다. 결과적으로는 N개의 합계는 N개의 차이점을 산출할 수 있게 됩니다. 송신된 ‘합계들’의 총 수 보다, 두 개의 데이터 세트의 차이점이 적기만 하면 미니스케치를 통해 모든 차이점을 산출할 수 있습니다.

비트코인에서의 미니스케치

ビ비트코인 네트워크의 강건성은 Sybil 또는 partizionamento 공격으로부터 지킬 수 있도록 충분한 수의 풀 노드의 접속수준에 의해 좌우됩니다.

안타깝게도 현재 비트코인 노드가 사용하는 대부분의 데이터(평균적으로 약 40~70%)는 트랜잭션 데이터가 아니라 릴레이 해야하는 새로운 트랜잭션을 찾기 위해 노드간 확인하는 작업에 사용됩니다. 현 시점에서는, 각 노드의 노드접속수를 증가시킬 경우, 이와 정비례하여 대역폭 부담이 커지기 때문에 각 노드가 유지할 수 있는 노드접속수가 제한적이 될 수 밖에 없습니다.

이러한 상황에서 세트조화 기법을 활용할 경우, 모든 노드(피어)에게 트랜잭션 데이터를 공유하여 비교하지 않더라도 아직 릴레이 되지 않은 트랜잭션을 효율적으로 찾을 수 있습니다. 대역폭에 대한 부담은 접속노드수에 따르지 않게 되며 각 노드가 접속할 수 있는 노드 수가 비약적으로 증가하게 됩니다. 또, 이 솔루션의 가장 큰 매력은 비트코인 네트워크의 합의 룰(consensus rule)을 일체 건드리지 않아도 된다는 점이기도 합니다. SRR은 SRR 프로토콜을 지원하는 노드들 사이에서만 사용되며, 지원하지 않은 노드에는 아무런 악영향이 없습니다.

SRR 프로토콜 자체는 아직 연구 중이며, 비트코인 네트워크로 도입되기에는 다소 시간이 걸릴 수 있습니다만, 미니스케치와 같은 기술은 비트코인 풀 노드의 운영용이성과 접근성을 높이는 소중한 한 걸음이라고 할 수 있습니다. 본 프로젝트의 업데이트 정보는 여기서 지속적으로 공유드리도록 하겠습니다.

미니스케츠에 대해 더욱 구체적으로 알고 싶으신 분은 Minisketch GitHub repository를 참고하여 주세요.