[Blockchain] 블룸 필터(Bloom Filter)란?

블룸필터(Bloom Filter)란 확률적 자료구조형으로써 특정 원소가 집합에 속했는지 여부를 확인하는데 사용됩니다. 1970년 Burton Howard Bloom에 의해 고안되었습니다. 확률적인 검색 필터를 사용해서 패턴을 정확하게 규정하지 않더라도 원하는 패턴을 설명하는 방식입니다. 많은 양의 데이터를 축소해서 공간 효율성을 개선할 수 있습니다. 

 

 

비트코인에 블룸필터가 적용되는 이유는 보안성을 강화하면서 검색 패턴을 효율적으로 처리하기 위해서입니다. 비트코인 언리미티드(Bitcoin Unlimited)팀이 노드에 알려지지 않은 거래를 식별할 때 사용되고 있습니다. SPV 노드는 블룸필터를 사용해서 이웃 노드들에게 특정 거래 정보를 요청해야 하는데 이 때 주소를 노출하지 않은 상태에서 요청이 가능하게 됩니다. 

 

 

블룸 필터의 특징

 

블룸 필터는 N 길이의 이진 배열과 J개의 해시 함수를 가지고 작동합니다. N과 J를 조절해 정확도와 프라이버시를 개선할 수 있습니다. 원소가 집합에 속하지 않았다고 판단되었지만 실제로 원소가 집합에 속하는 부정적인 오류는 절대로 발생하지 않는 특징(Flase Negative)을 가지고 있기 때문에 블랙 리스트 검별시 주로 사용됩니다. 또한 문자열 맞춤법 교정이라던지 가상화폐, 라우터, 크롬 브라우저, 빅데이터 환경에서 사용됩니다. 

 

 

반대로 특정 원소가 있다고 판단되었지만 실제 집합에 원소가 존재하지 않을 경우(False Positive) 문제는 발생할 수 있습니다. 블룸필터의 오류확률은 임의의 테이블 크기 + 추가해야할 자료의 크기 + 해시 함수의 갯수에 따라 조절됩니다. 따라서 긍정 오류율이 존재하는 경우 자료의 크기를 감안해 테이블 크기 + 해시 함수 갯수를 조절해 오류율을 조절할 수 있습니다.

블룸 필터에서는 원소가 집합에 속했는지만 판단하므로 원소의 삽입은 가능하지만 삭제는 불가능합니다. 블랙 리스트 IP를 검열할 때 IP가 추가될 때 비트 배열을 덮어쓰기만 할 뿐 배열을 초기화 하지는 않습니다. 

 

블룸 필터 작동방식

 

블랙 리스트 IP를 차단해야 하는 경우를 가정합니다. x, y, z라는 IP를 블랙리스트로 지정하고 방화벽에서 이를 차단하고자 합니다. 먼저 N 길이의 비트 배열과 J개의 해시 함수를 준비합니다. 예제 에서는 N=18, J=3 입니다.

① x IP에 대해 3개의 해시 함수를 작동시키고 출력값에 해당하는 배열 인덱스를 1로 변경합니다.

 

② y IP에 대해 3개의 해시 함수를 작동시키고, 출력값에 해당하는 배열 인덱스를 1로 수정합니다.

 

 

 

③ z IP에 대해 3개의 해시 함수를 작동시키고, 출력값에 해당하는 배열 인덱스를 1로 수정합니다.

 

④ w IP를 담은 패킷을 전달받은 후 w IP에 대해 3개의 해시함수를 작동시키고, 기존 값과 비교를 진행합니다. 3, 4, 13 인덱스는 1이지만 15 인덱스는 0이므로, w IP가 블랙리스트가 아님을 확인할 수 있습니다. 만약 4, 13, 15 모두 1인 경우 블랙리스트라고 판단할 수 있습니다.

 

 

 

[Blockchain] 탭 루트(Tap Root)란? 슈노르 서명?

 

[Blockchain] PBFT(Practical Byzantine Fault Tolerance) 합의 알고리즘이란?

 

[Blockchain] 루나 테라 사태 총정리