- membership query시 사용
- 어떤 원소가 특정 집합에 포함되어있는지 확인할 때 사용
- 검색 시간과 메모리 절약.
- 길이가 x인 bit 배열과 k개의 hash함수를 이용, 검색할 원소에 대한 k개 hash의 결과를 배열의 인덱스로 함
- 배열의 원소 삭제 불가. insert만 가능
- false positive : 거짓 긍정 (false negative는 불가능)
→ 블룸 필터로 membership query한 결과에 실제로는 없는 원소가 포함될 가능성이 있음.
- FPR(False Positive Rate)는 배열의 크기(x)가 크고, 해시 함수의 수(k)가 많을수록, 검색할 원소의 수(n)가 작을수록 낮아짐.
- 해시함수를 늘리면 cpu 사용량이 증가
- 배열의 bit수를 늘리면 메모리 사용량이 증가
- 위의 식에따라 에러율(FPR)과 k, x, n 을 조절 가능하므로 적절한 값을 유지해야함
False Positive 확률(FPR)을 줄이기 위해서는 블룸필터의 크기를 키워야하지만
일반적으로 데이터량을 줄이기 위해 블룸필터를 사용한다는 점을 고려해야한다.
트랜잭션 insert 과정
다음은 블록에대한 트랜잭션(txn1,txn2)의 포함여부를 블룸필터로 확인하기위해 트랜잭션을 insert하는 과정이다.
배열을 생성하고 0으로 초기화
txn1, txn2에 대해 hash함수 H1, H2로 계산한 결과를 배열의 index와 비교 하여 해당되는곳에 1을 증가시킨다.
txn은 tx id의 전체나 일부를 활용.(salt를 사용하기도함)
H2(txn2) = 4 일때는, 이전에 이미 1이 되어 충돌.
txn4에 대해 H1(txn4)와 H2(txn4) 인덱스는 모두 1이므로 결과는 True이지만,
txn4를 추가한적이 없으므로 False Positive.
References
Scaling Bitcoin Stanfornd 2017 - Graphene: A New PRotocol for Block Propagation Using Set Reconciliation
