블룸 필터 (Bloom Filter)

블룸 필터(Bloom Filter)는 어떤 항목이 집합에 속하는지 여부를 확인하는 데 쓰는 확률적 데이터 구조입니다. 비트코인에서는 SPV 클라이언트가 전체 노드에 조건에 맞는 트랜잭션과 머클 블록만 요청할 때 주로 쓰였습니다.

장점:

• 공간 효율성: 블룸 필터는 집합 전체를 저장하는 것보다 훨씬 적은 공간을 차지하며, 집합이 클수록 차이가 커집니다.
• 빠른 조회: 원소가 집합에 있는지 확인하는 데 보통 해시 연산 몇 번이면 충분해 매우 빠릅니다.

단점:

• 확률적 특성: 블룸 필터는 거짓 양성(false positive)을 낼 수 있습니다. 즉, 집합에 없는 원소를 있다고 판단할 수 있습니다. 반면 거짓 음성은 절대 나오지 않습니다.
• 삭제 어려움: 블룸 필터에서 원소를 삭제하기는 어렵고, 큰 성능 저하 없이는 불가능한 경우가 많습니다.

암호화폐에서의 사용 사례:

블룸 필터는 암호화폐 분야에서 여러 방식으로 활용됩니다.

1. SPV 클라이언트: 단순 결제 검증(SPV) 클라이언트는 블록체인 전체를 내려받지 않고, 블룸 필터를 이용해 전체 노드에 필요한 트랜잭션과 블록만 요청합니다.
2. 비트코인 네트워크: 블룸 필터 덕분에 SPV 클라이언트는 전체 노드에서 관련 데이터만 효율적으로 받아 대역폭 사용량을 줄이고 개인 정보 보호를 개선할 수 있습니다.

블룸 필터란?

데이터 전체를 저장하지 않고도 트랜잭션 같은 특정 정보가 큰 데이터 집합 안에 있을 가능성이 있는지 알려 주는, 문지기 같은 데이터 구조입니다.

어떻게 쓰일까요?

SPV(단순 결제 검증) 클라이언트를 위한 지름길이라고 보면 됩니다. 용량이 매우 큰 블록체인 전체를 내려받는 대신, 블룸 필터를 쓰면 클라이언트는 다음과 같이 동작합니다.

• 찾는 데이터(예: 특정 주소와 관련된 트랜잭션)를 압축해 표현한 필터를 만듭니다.
• 이 “필터”를 전체 노드로 보냅니다.
• 전체 노드는 필터를 사용하여 일치하는 데이터가 있는지 빠르게 확인합니다.
• 전체 노드는 일치하는 항목이 있을 때만 관련 트랜잭션과 머클 블록을 보내므로 대역폭과 시간을 아낄 수 있습니다.

도서관 서가를 전부 훑는 대신 사서에게 특정 저자의 책이 있는지 묻는 것과 같습니다.

주의할 점

블룸 필터는 매우 유용하지만 완벽하지 않습니다. 작은 확률로 거짓 양성이 생길 수 있습니다. 즉, 실제로 없는 데이터를 있다고 알려 줄 수 있습니다. 다만 크게 높아지는 효율에 비하면 작은 대가입니다.

비유로 이해하기

증권 시장의 바쁜 트레이더를 떠올려 보세요. 수천 개 종목의 시세가 끊임없이 쏟아지지만 관심 종목은 몇 개뿐입니다. 지나가는 시세를 전부 읽는 대신, 관심 종목이 언급되었는지 알려 주는 특별한 필터를 쓴다고 생각해 보세요.

이 필터는 완벽하지 않아서 가끔 거짓 양성(관심 종목이 언급되지 않았는데 언급되었다고 알림)이 생깁니다. 그래도 관련 없는 정보를 빠르게 걸러 내고 중요할 수 있는 소식만 골라 주는 데는 매우 뛰어납니다. 블룸 필터가 하는 일이 바로 이것입니다.

암호화폐에서 작동하는 방식

블록체인 전체를 저장하지 않는 “라이트” 지갑을 생각해 보세요. 이런 지갑은 모든 트랜잭션을 확인하는 대신(시세를 전부 읽는 것처럼) 블룸 필터를 사용합니다.

• 지갑은 네트워크에 “이러한 주소와 관련된 트랜잭션에만 관심이 있습니다.”라고 알립니다.
• 노드는 블룸 필터로 새 트랜잭션이 해당 주소와 일치하는지 빠르게 확인합니다.
• 필터에 거짓 양성이 일부 섞일 수 있지만, 지갑이 처리할 데이터 양은 크게 줄어듭니다.

정리하면, 블룸 필터는 집합 전체를 저장하지 않고도 어떤 항목이 집합에 속할 수도 있는지 빠르게 확인하는 방법입니다. 완벽한 정확성 대신 속도와 효율을 택한 절충입니다.