블룸필터는 특정 원소가 집합에 속하는지 검사하는데 사용할 수 있는 확률형 자료 구조이다.
확률적 검색 필터로 원하는 패턴이 무엇인지 정확하게 규정할 필요 없이 원하는 패턴을 설명하는 방식이다. 많은 양의 데이터를 줄여 공간 효율적으로 빠르게 검색할 수 있다.
SPV(Simple payment Verification)노드는 블록체인의 모든 정보를 저장하는 대신, 블록헤더만을 저장하여 거래의 유효성을 검사하는 노드를 의미하는데,
SPV노드는 블룸필터를 사용해 이웃 노드들에게 특정 거래를 제공해 달라고 요청하는데 이때 노드는 검색중인 주소가 정확히 어떤 주소인지 밝힐 필요는 없다.
[블룸 필터 동작 방식]
블랙리스트에 IP 주소 저장 순서
[블랙 리스트와 IP 주소 비교 순서]
[블룸필터의 특징]
거짓-긍정 확률이 존재한다.
블룸필터는 길이 N의 이진 배열과 1부터 N까지의 출력값을 갖는 J개의 해시함수를 가지고 있다고 했는데 이 N과 J를 조절함으로써 정확도와 프라이버시 보호 수준을 조절할 수 있다.
⇒ 특정 원소가 존재하지 않는다는 부정적인 답변을 받는다면, 이 원소는 확실하게 없다고 할 수 있다.
요구하는 긍정 오류율이 있다면 넣어야 하는 자료의 크기를 고려해서 테이블의 크기와 해시 함수의 수를 정하는 것이 일반적이다.