본 글은 온 체인 네트워크 확장, 블록 전파 및 기타 주제에 관련된 기술적 개념을 설명하는 시리즈의 첫 기사입니다.

 

데이터 구조는 컴퓨터에 정보를 저장하는 데 사용되는 형식을 일컫는다. 블룸 필터(Bloom Filter)는 집합을 식별하는 데 사용될 수 있는 확률적 데이터 구조이다. 우선 블룸 필터가 무엇인지부터 들여다보자. 그리고 나서, 특정한 목적에 따라 블룸 필터를 설계할 때의 트레이드 오프를 설명할 예정이다. 마지막으로, 비트코인 캐시와 대시에 있어서 발생하는 응용 프로그램을 살펴보겠다.

 

블룸 필터는 어떻게 작동하는가?

 

전통적인 컴퓨터에 저장된 모든 정보는 궁극적으로 0과 1의 형태를 가진다. 컴퓨터 과학자들은 이 적은 양의 정보를 비트(Bit)라고 부른다. 블룸 필터를 구성하기 위해서 우리는 블룸 필터에 필요한 비트의 숫자를 식별해야 한다. 또한 다수의 해시 함수 역시 선택해야 한다. 예를 들어 두 개의 항목을 식별하기 위한 두 개의 해시 함수를 사용하는 12비트 블룸 필터를 생각해보자. 이 경우에, 해시 함수는 어떤 아이템이든 오직 하나의 비트만을 식별하는 데 사용된다. 즉, 1과 12사이의 숫자를 생성하는 것이다.

이 예를 계속 사용하여, 두 해시 함수가 적용되었을 때 첫 번째 항목이 4와 9를 식별한다고 가정해보자. 두 번째 항목은 7과 10을 식별하였다. 이 경우 이 두 항목을 나타내는 블룸 필터는 4번째, 7번째, 9번째 및 10번째 비트만이 온(On)으로 설정된 12비트인 것이다. 만일 동일한 비트가 1회 이상 식별되면 블룸 필터는 해당 비트는 온이 되고, 그렇지 않으면 이는 오프(Off)가 된다.

 

이제 우리가 해당 블룸 필터가 목록의 첫 번째 항목을 식별하였으며 이 항목이 실제로 이 리스트에 있다는 점을 확인하기 위해서는 해시 함수를 적용하여 4와 9를 얻는다. 이 방식을 통해 우리는 이 두 비트가 블룸 필터에서 온(On) 상태 인지 확인할 수 있다. 이들이 켜져 있으면 해당 항목은 필터를 통과한다.

 

세 번째 항목을 가져와서 해시 함수를 적용한 결과 7과 11을 얻었다고 가정해보자. 그렇다면 이 세 번째 항목은 이 블룸 필터를 통과할 수 없는데, 이는 11번째 비트가 온으로 설정되어 있지 않기 때문이다. 블룸 필터는 실제로 필터처럼 작동한다. 블룸 필터는 아이템이 집합 내에 있는 지 식별하기 위해 만들어졌다. 누구나 블룸 필터를 활용하여 의도한 집합 내에 항목이 존재하는 지 확인하여 해당 항목을 배제할 수 있다.

 

이제, 네 번째 항목을 가져와보자. 이 항목이 필터를 통과할 확률은 얼마나 되는가? 우선, 이 필터는 12비트 중 4비트가 온으로 설정 되어 있으니 이 첫 번째 해시 함수가 비트를 온으로 설정할 확률은 1/3이다. 유사하게, 두 번째 해시 함수가 비트를 온으로 설정할 확률은 1/3이다. 결과적으로 이 네 번째 항목이 필터를 통과할 확률은 1/9가 되는 것이다. 이와 같은 일이 발생하는 경우 이를 잘못된 긍정(False Positive)이라고 부른다. 이 네 번째 항목은 집합에 존재하지 않더라도 필터를 통과할 수 있다.

 

여기에서 어려움이 발생한다. 블룸 필터는 일반적으로 집합과 교신하는 작은 데이터 구조이다. 그러나, 항목이 세트의 일부로 잘못 식별될 확률이 존재한다. 좋은 소식은, 만일 아이템이 블룸 필터를 통과하지 못한다면 이는 확실히 집합에 존재하지 않는다는 것이다. 또 하나의 좋은 소식은, 블룸 필터의 이 잘못된 긍정 확률은 조정될 수 있다는 것이다.  블룸 필터를 구성할 때, 우리는 비트의 숫자를 조정하거나 해시 함수의 숫자를 조정하여 잘못된 긍정의 확률을 조절할 수 있다. 일반적으로, 블룸 필터에 더 많은 비트를 허용함으로써 잘못된 긍정의 비율을 감소시킬 수 있다. 사실, 원하는 잘못된 긍정 비율과 목록에 있는 항목의 숫자를 고려하여, 가장 작은 블룸 필터에 원하는 잘못된 긍정 비율을 제공하기 위해서는 비트와 해시 함수의 숫자를 최적화할 수 있다.

 

암호화폐에 있어 블룸 필터

 

블룸 필터는 비트코인 언리미티드 팀(Bitcoin Unlimited Team)이 노드에 알려지지 않은 거래를 식별하는 데 도움을 주고 있다. 블룸 필터를 사용하는 또 다른 예는 Simplified Payment Verification, SPV 지갑들이다. 대시 지갑과 같은 일부 SPV 지갑은 거래에 대해 블룸 필터를 통과하는 주소를 포함하도록 요구한다. 이로써 요청된 주소가 지갑에 속하지 않을 수 있다는 질문을 제기함으로써 개인 정보 보호에 있어 일정 수준을 허용하게 되나, 이는 잘못된 긍정 반응보다는 낫다는 것이다.  또한 블룸 필터는 브로드 캐스팅 블록에 있어서 그래핀 프로토콜의 블록에 속한 거래 집합을 식별하는 데에도 사용된다. 그래핀은 또한 잘못된 긍정을 식별하기 위해 가역성 블룸 락업 테이블(invertible bloom lookup tables)을 사용한다.