블룸 필터(Bloom Filter)

블록체인 기술 블룸 필터에 대해 알아봅시다 

 

블룸 필터란 특정 원소가 집합에 속하는지 검사하는데 사용할 수 있는 확률형 자료 구조 입니다

 

확률적 검색 필터로 원하는 패턴이 무엇인지 정확하게 규정할 필요 없이 원하는 패턴을 설명하는 방식이라, 통계적 특성을 보였다고 할수 있습니다 

 

또한 많은 양의 데이터를 줄여서 공간 효율적으로 빠르게 검색이 가능합니다 

 

블룸필터는 프라이버시를 보호하면서 검색 패턴을 구현하기 위한 효율적인방법을 제공합니다 

또한 블룸필터는 비트코인 언리미티드팀이 노드에 알려지지 않은 거래를 식별하는데 도움을 주고 있습니다 

 

예로 SPV노드가 블룸필터를 사용해 이웃 노드들에게 특정 거래를 제공해 달라고 요청하는데 이때 노드는 검색중인 주소가 정확히 어떤 주소인지 밝힐 필요는 없습니다 

 

자세히 알아봅시다

먼저 블룸 필터가 어떻게 동작 하는지 알아봅시다 

 

블랙 리스트 기반 IP주소 검색및 차단의 예를 들어 설명하겠습니다 

 

1. x,y,z 라고 하는 IP를 블랙리스트에 저장

2. 방화벽에 이러한 블랙리스트의 IP를 차단하려고 등록한다고 가정 

 

블룸 필터는 N비트 크기의 비트 배열구조와, 서로 다른 J가지의 Hash함수를 사용하여 구현 합니다

해시함수는 N가지의 값을 균일하게 출력해야합니다!

 

블랙 리스트에 어떻게 IP주소가 저장되고 패킷이 들어올떄 어떻게 블랙 리스트와 IP주소를 비교를 하는지 살펴봅시다 

 

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

1. 블랙리스트로 로그에 X의 IP를 저장

2. IP x를 가져와 3개의 해싱 함수(f1,f2,f3)로 해싱

3. 각 해싱값에 해당되는 해당 배열 인덱스 값을 1로 수정

18(N)개의 비트 배열, 그리고 3(J)개의 해싱 함수 사용

4. IP y로 1~3번 과정을 반복

5. IP z로 1~3번 과정을 반복 (이전 인덱스 값이 0이 아닌 1인경우 수정없이 1로 유지)

 

 

여기 까지가 블랙리스트로 저장하는 방법입니다 

이후 IP주소가 들어왔을때 필터링 하는 과정을 살펴 봅시다

 

1. w 라는 IP를 가진 패킷을 받음 

2. IP w를 위의 방식과 같이 3개의 해싱 함수(f1,f2,f3)로 해싱

3. 4,13 인덱스 값은 1이지만 15의 인덱스 값은 0 이므로 w라는 IP는 블랙 리스트 IP가 아님

 

마지막 3번을 보면 3가지의 인덱스중 2개만 1이기 떄문에 블랙리스트로 등록된 IP로 판별하지않습니다

반대로 3가지 인덱스가 모두 1이라면 블랙리스트로 등록된 IP로 판별합니다

 

블룸 필터의 특징

1. N의 이진 배열 1부터 ~ N까지 출력값을 갖는 J개의 해시함수를 가지는데 N,J를 조절함으로 정확도와 프라이버시 보호수준을 조절 가능

2. 오탐지율 존재, 결정적 결과 대신 부정확한 결과를 얻을 수 있음

3. False Negative(존재하는데 부정하는것)는 존재하지 않는다고 보장할 수 있다 

4. False Positive(거짓-긍정, 존재 하지않는데 있다고 하는것) 존재함 

 

위 예에 따라 정상IP를 블랙리스트로 판단할 가능성이있다

 

블룸 필터 사용예 

1. IP주소 검색및 차단 필터링

2. 문자열 맞춤법 교정

3. 가상화폐

4. 라우터

5. 크롬 브라우저

6. 빅데이터 환경