블룸필터 (Bloom Filter)

 

어느 마을에 한 수상한 거지가 있었다.

그는 마을을 돌아다니며 각종 버려진 물건들을 주어서 자신의 비밀공터로 가지고 왔다.
공터 한구석에는 그 물건 폐품들이 산더미 처럼 쌓여 있었으며,
그 물건들은 날을 잡아서 공터 다른 구석에 있는 드럼통들에 무작정 눌러 담아 놓았다.

몇 일이 지나 거지는 어떤 마법사를 만나게 되는데 이 마법사는 폐품에서 몇가지 물건을 조합하여 
엄청난 보물을 만들 수 있는 방법을 알려 주었다. 

아무렇게나 담아져있는 드럼통에서 해당 물건을 찾기란 거의 불가능 했다. 
그래서 거지는 드럼통에 아무것이나 쑤셔 넣는게 아니라, 수 많은 폐품중에서 자신만 알고 있는 그 부품을 다른 것들과 함께 섞여져서 담을 (위장하기 위해)  드럼통을 만들어야 겠다고 생각했다.

즉 드럼통에 무엇이 들어 있는지는 다른 사람에게 들키고 싶지 않았기에 드럼통 위에 "룬조각", "성수" "에메랄드" 이런 식으로 표식 할 수는 없었다. 마법사가 또 다른 사람에게도 알려 줬을지도 모르니.. 

곰곰히 생각한 결과 만들어낸 방식은 다음과 같다. (천재 거지?) 

드럼통 뚜껑에 그 여러가지 물건을 대표하는 표식을 해 둔다. 
대표하는 방식은 아래와 같다.  

이름이 "선풍기" 라면 획수가 16개라,  16 * o의 갯수(1) * ㅅ 의 갯수(1) = 32 이라고 써 두었다. 
이름이 "자동차 사이드미러" 라면 39 * o의 갯수(1) * ㅅ 의 갯수(1) = x 이라고 써 두었다. 
동일한 숫자의 이름이 나왔을 때는 드럼통에 추가로 적지 않고 그냥 집어 넣었다. 
이렇게 되면 하나의 드럼통에 여러가지 물건이 담겨져 있겠지~

...

어느 날 거지는 수 백개의 드럼통에서 "밥솥뚜껑" 을 찾고 싶어서 모든 드럼통을 뒤지다가..
날이 샜다. 문득 거지는 자신이 드럼통 뚜껑에 표식을 남겼다는 것을 깨닿고 ;;; (갑자기 바보?)
드럼통 뚜껑에 "밥솥뚜껑"에 대한 획수번호가 있는 드럼통을 뒤졌다.  

쉽게 찾았다. ^^v

조금의 수고  [획수번호 = '추가 계산']  및 [드럼통 위에 표식 = '추가 저장공간'] 를 한 덕분에 내부를 확인하지 않고도 자신에 필요한 정보 위주로 모아두고 검색도 빨리 할 수 있는 드럼통을 확보 할 수 있었다.

그러던 어느날 

어느날 거지는 이번에는 "갤럭시10"을 찾아야 했다.
먼저 획수번호를 구한 후에 드럼통들의 표식을 확인하였다. 동일 한 숫자를 발견하였고 
드럼통을 확인하니 웬걸~  갤럭시 10이 없는 것이었다.?!?!

그렇다. 갤럭시10과 동일한 획수번호를 가진 놈들만 그 안에 있던 것이었다.
거지는 깨닫길

이 획수번호 체계는 드럼통안에 "갤럭시10"이 없다는 것은 100% 검증 가능하지만
"갤럭시10" 이 있다는 것은 100% 검증 할 수 없구나. 하고 탄식을 하였다..

거짓 양성(false positive) 은 실제로는 거짓인데 검사 결과는 참 이라고 나오는 것이며,
거짓 음성(false nagative) 실제로는 참인데 검사 결과는 거짓이라고 나오는 것이다. 
불룸필터는 거짓 양성기반의 확률적인 데이터 분류 체계이다. 효율적인 검색, 효율적인 분류에 사용된다.

예를 하나 더 들면 
거짓 양성(false positive) 은 부품검사장비에서 실제로는 망가진 부품인데 검사 결과는 참 이라고 나오는 것이며, 거짓 음성(false nagative) 은 부품검사장비에서 실제로는 정상인 부품인데 검사 결과는 고장이라고 나오는 것이다.
이 경우 100%정확한 장비를 만들지 못한다면 거짓음성쪽으로 발생할 확률이 높게 코딩하는게 맞다고 볼 수 있다.

P.S
비트코인의 SPV에서 볼룸필터는 왜 사용하는 걸 까요? 제 생각엔 (코드를 보고 명확히 확인하진 않았음) 

만약 내 지갑에서 네트워크상에서 발생되는 모든 트랜잭션을 전파한다고 칩시다. 그러면 일개 라이트노드인 지갑에서 너무 많은 부담을 가지게 되니깐 이건 싫습니다. 그렇다고 아무 트랜잭션도 받지 않고, 혹은 받아서 전파하지 않는 다고 합시다. 그러면 부담은 없어지지만 지갑의 존재는 무의미 하죠. 따라서 외부의 풀노드에게 나의 거래 요청(트랜잭션)만 보낸다면, 풀노드들은 내 지갑의 계정정보를 알게 됩니다. 이건 또 싫은거죠. 따라서 내 지갑에서 시작 되는 트랜잭션과 추가적으로 얼만큼의 외부에서 받아드리는 트랜잭션을 전파한다면 비교적 덜 노출 시키게 될 것입니다. 이때 외부에게 나는 이런 트랜잭션만 받겠다라고 하는데 사용되는게 블룸필터.