TIL) 블룸필터(Bloom filter)와 SPV

#블룸필터(Bloom filter)

- probabilistic search filter
- BitArray로 구성되고 비암호화 해시함수인 crc, murmur, md5를 사용함
- 확률적으로 찾기 때문에, 속도가 빠르면서 메모리 사용량도 적은 장점이 있지만 false positive 오류 발생하기도 함

 

https://www.waitingforcode.com/big-data-algorithms/bloom-filter/read

 

#false positive 오류

https://freecontent.manning.com/all-about-bloom-filters/

- K: 해시함수 갯수
- M: BitArray 크기
- N: elements 총 갯수 
- false positive는 M과 N이 작을수록, K가 클수록 발생할 확률이 높아짐.  

 

#Usecase of 블룸필터

- SPV node 운영
- 컨텐츠 추천: 유튜브, 구글

#SPV(Simplified Payment Verification) node with 블룸필터

- SPV는 헤더만 갖고있는 light한 노드임.

- full node는 트랜잭션 중 블룸 필터와 연관된 트랜잭션을 SPV node에 아웃소싱함.

- SPV 노드는 Bloom filter를 활용하여 아래와 같이 동작하여 검증활동에 참여함.

1. SPV 노드에서 A,B,C 지갑 검증하려고 함
2. SPV노드는 A,B,C 지갑 Address 블룸필터로 저장
3. 풀노드에게 블룸필터 전달
4. 풀노드는 블룸필터와 매치되는 트랜잭션(a,b,c,d) 전달
5. SPV 노드는 트랜잭션 a,b,c,d 중 지갑 A,B,C와 관련된 a,b,c만 남기고 d는 버림
6. a,b,c 가지고 UTXO 업데이트

- SPV node(clinet)로는 스마트폰이 사용되는데, 이는 스마트폰이 full node를 운영하기에는 하드와 전력이 뒷받침되지 않기 때문임.

 

#블룸필터외에 membership test에 사용될 수 있는 filter

- Linear
- Hash Set
- Bit Set