블룸 필터(Bloom Filters)

0xWonTiger·2022년 6월 28일

블룸필터

어떤 값을 여러 해시 함수에 넣어 결과값들을 임의의 테이블에 인덱싱하여 해당되는 모든 값이 1인지를 따지는 자료구조

확률적 검색 필터로 원하는 패턴이, 무엇인지 정확하게 규정할 필요없이 원하는 패턴을 설명하는 방식이라 할 수 있으며, 비트코인에서는 노드에 알려지지 않은 거래를 식별하는데 도움을 주고 있다.

단순히 설명하면 있는지 없는지만 체크하는 특성때문에 긍정 오류의 가능성이 있으며, 삽입은 가능하나 제거는 안된다. 왜냐면 여러 값이 똑같은 인덱스에 대응 될 수 있기 때문에 어떤 값을 제거하면서 해당 값의 인덱스를 0으로 바꿔버리면 기존에 저장되어 있는 다른 값들에게 영향을 미치기 때문이다

즉 요소 제거는 블룸 필터를 스크래핑하고 처음부터 다시 작성해야만 수행 할 수 있다.

*긍정 오류(false positive): 넣은 적 없는 값에 대해 있다고 하는 경우

블룸필터의 사용 방식

집합의 크기가 굉장히 크거나 집합의 속해있는 원소의 크기가 커서 원소가 집합에 속해있는지 정확히 판단하는데 시간이 오래걸리는 경우 이 과정의 전처리 과정으로 Bloom Filter를 이용해서 아예 집합에 속할 일이 없는 원소를 미리 걸러낼 수 있다.

Google Chrome은 위험한 사이트 검사에 Bloom Filter를 사용한다고 알려져 있는데, Bloom Filter를 사용해서 빠르게 대충 검사한 다음, 의심이 가는 사이트인 경우 데이터베이스에 다시 정확하게 검사하는 것이다. 아마 위험 사이트 데이터베이스의 크기가 크고, 검사 요청이 굉장히 빈번하게 일어나기 때문에 Bloom Filter를 전처리 과정으로 사용해서 데이터베이스 요청 부하를 줄이는 것으로 보인다. 비트코인도 내부적으로 Bloom Filter를 사용하는 것으로 알려져 있다. 보통은 Disk IO를 줄이기 위한 최적화 방법으로 많이 사용한다.

비트코인의 블룸필터

Bloom Filters는 SPV 노드들이 transactions의 집합을 받을 때 그들이 어느 주소에 관심이 있는지 노출되지 않게 하는 기법이다.

SPV 노드란?
Simple Payment Verification의 약자로 거래에 대한 모든 블록체인을 저장하지 않고도 트랜잭션을 검증하는 방법으로, 라이트 웨이트 노드, 혹은 경량노드라고도 불린다.

SPV는 비트코인을 받았다는 거래에 대해 모든 블록체인을 다운로드 하지 않고 검증하는 간이 결제 확인 방법이다. 즉 모든 정보를 가진 풀 노드를 사용하지 않고 풀노드에서 머클 증명과 일부 블록헤더만 받아와서 트랜잭션의 유효성을 검증하는 방법이다. 가볍고 신속하지만 트랜잭션 검증과정에 참여하지 않기 때문에 네트워크 보안에도 기여를 하지 않는 특징이 있다.