Bloom Filter

[TOC]

개념

블룸필터(Bloom Filter)는 특정 원소가 집합에 속하는지 검사하는 데 사용할 수 있는 확률형 자료 구조이다. 확률적 검색 필터로 통계적 특성을 설명할 수 있으며, 또한 많은 양의 데이터를 줄여서 공간 효율적으로 빠르게 검색할 수 있다.

블룸필터에서는 있을 수도 있지만, 없는 경우 완전히 없다는 것이 표현된다.

블룸필터는 프라이버시를 보호하면서 검색 패턴을 구현하기 위한 효율적인 방법을 제공한다. 또한, Bitcoin Unlimited 팀이 노드에 알려지지 않은 거래를 식별하는 데 도움을 주고 있다.

SPV 노드가 블롬필터를 사용해 이웃 노드들에게 특정 거래를 제공해달라고 요청하는 경우, 검색중인 주소가 정확히 어떤 주소인지 밝힐 필요가 없게 된다.

SPV(Simple Payment Verification): 거래에 대한 모든 블록체인을 저장하지 않고도 트랜잭션을 검증하는 방법

여기서는 블랙리스트 기반의 IP 주소 검색 및 차단의 예를 가지고 동작 방식을 살펴본다. x, y, z라는 IP를 블랙리스트에 저장하고, 방화벽에서 이러한 블랙 리스트의 IP를 차단하려고 등록한다고 가정한다.

먼저 N 비트 크기의 bit array, 그리고 J개의 해싱 함수가 필요하다. 여기서는 N = 18, J = 3이다.

블랙리스트에 IP 주소 저장 순서

x IP 저장: x IP를 3개 해싱함수에 돌리고, 각 출력값에 해당하는 배열 인덱스 값을 1로 수정한다.

여기서는 각 해싱함수 결과값의 범위는 1 ~ 18(1 ~ N)까지이며, 결과값이 예를 들어 각각 1, 5, 13이 나온 경우, bit array에서 1, 5, 13만 1로 수정해준다. (나머지 배열 값은 0이다.)
y IP 저장: 1번과 같은 방식으로 진행한다. (결과값이 4, 11, 16으로 나왔다고 가정한다.)
z IP 저장: 1번과 같은 방식으로 진행한다. (결과값이 3, 5, 11로 나왔다고 가정한다.)

블랙리스트와 IP 주소 비교 순서

w라는 IP를 가진 패킷을 받는다.
w라는 IP에 대해 3개의 해싱 함수를 돌린다.
만약 결과값이 4, 13, 15이 나온 경우, 위의 예시에서 15의 인덱스 값은 0이므로 w라는 IP는 블랙리스트가 확실히 아니다.
- 만약 결과값이 4, 13, 16이라면, 위의 예시에서 적용해봤을 때 probably yes이다. (아마 블랙리스트 IP이다.)

Binary Array의 길이 N과 해시함수의 개수 j를 조절함으로써 정확도와 프라이버시 보호 수준을 조절할 수 있다.
False Negative(거짓-부정)는 존재하지 않는다고 보장할 수 있는 반면, False Positive(거짓-긍정)는 존재할 수 있다.
- 위 예시로 보면, 정상 IP를 블랙 리스트로 판단하여 차단할 확률이 존재한다.
넣어야 하는 자료 크기를 고려해서 테이블의 크기와 해시 함수 수를 정하는 편이다.
단순히 존재여부를 보는 특성 때문에 자료를 삽입만 할 수 있다. (제가는 안 된다.)

블룸필터는 처리능력 대비 적은 메모리 공간을 필요로 하는 장점 덕분에 DB 이외에도 많은 곳에서 사용되고 있다.