블룸 필터

블룸 필터는 특정 항목이 집합의 일부인지 여부를 사용자에게 알리는 데 사용할 수 있는 데이터 구조입니다. 요소가 집합에 있는지 여부를 확실하게 말할 수는 없지만 요소가 없는 경우에는 확실하게 말할 수 있습니다.

1970년 Burton Howard Bloom이 만든 Bloom 필터는 공간 사용의 효율성으로 인해 다양한 응용 분야에 매력적인 제품입니다. 일부 암호화폐(특히 비트코인)에서는 단순화된 지불 확인(SPV)에서 중요한 역할을 합니다.

SPV 클라이언트를 사용하면 사용자는 전체 노드를 실행하지 않고도 비트코인 네트워크와 상호 작용할 수 있습니다. 전체 노드에는 스마트폰과 같은 저전력 장치에서 실행하기 어렵게 만드는 특정 스토리지 및 계산 요구 사항이 있습니다. 반면에 SPV 클라이언트는 사용자의 지갑과 관련된 정보에 대해 전체 노드에 간단히 쿼리합니다.

이 데이터를 사용자에게 전달하는 가장 간단한 솔루션은 전체 노드가 클라이언트의 키를 인식하도록 하여 적절한 트랜잭션만 전송되도록 하는 것입니다. 분명히 이것은 클라이언트의 개인 정보가 희생될 것이기 때문에 수준 이하의 솔루션입니다. 반면에 모든 트랜잭션을 다운로드하여 대부분을 버리는 것은 대역폭 낭비입니다. 블룸 필터를 입력합니다.

예를 들어 보겠습니다. 클라이언트 Alice가 전체 노드를 실행하는 Bob이 인식하지 않기를 바라는 고가치 트랜잭션을 가지고 있다고 가정합니다. 그녀는 10x1 그리드로 설명할 Bloom 필터를 구성합니다.

그녀는 관심 있는 트랜잭션 데이터를 0과 9 사이의 두 숫자를 출력하는 두 개의 다른 해시 함수를 통해 전달합니다. 이를 4와 7이라고 부르겠습니다. 그녀는 필터를 Bob에게 보냅니다.

이 그리드를 보면 Alice가 필터에 어떤 데이터를 전달했는지 알 수 없습니다. 데이터가 포함된 집합이 있는 경우 이를 해시하고 필터와 비교할 수 있습니다. 일치하는 경우 Alice가 요청한 정보일 가능성이 있습니다.

동시에 4와 7에 매핑되는 많은 입력이 있을 수 있으므로 Bob은 Alice가 관심을 갖고 있는 데이터 부분을 결정할 수 없습니다. 그는 단순히 모든 일치 항목을 반환하고 Alice는 해당 항목을 필터링합니다.

물론 이것은 지나치게 단순화한 것이지만 개념을 보여줍니다. 블룸 필터는 클라이언트의 진정한 이익을 난독화합니다. 완벽한 방법은 아니지만(여전히 개인 정보 보호에 대한 우려가 있음) 노드에 대한 비차폐 요청에 비해 개선된 것입니다.