Filtr Blooma to struktura danych, za pomocą której można informować użytkownika, czy dany element jest częścią zestawu. Chociaż nie może z całą pewnością stwierdzić, czy element jest w zestawie, może z całą pewnością stwierdzić, czy elementu nie ma.
Przykład filtru Blooma
- Parametry: k=3, m=18.
- Kolorowe strzałki wskazują wartości funkcji haszujących dla dodanych elementów x, y, z; szare – dla szukanego elementu w.
- Dla szukanego elementu w jedna z funkcji haszujących wskazuje w tablicy na wartość 0, co oznacza że tego elementu nie ma w zbiorze.
Filtry Blooma, stworzone przez Burtona Howarda Bloom’a w 1970 roku, są atrakcyjną ofertą do wielu zastosowań ze względu na ich efektywność wykorzystania przestrzeni. W niektórych kryptowalutach (w szczególności Bitcoin) odgrywają one integralną rolę w uproszczonej weryfikacji płatności lub SPV.
Korzystając z klienta SPV, użytkownicy mogą wchodzić w interakcje z siecią Bitcoin bez uruchamiania pełnego węzła. Pełne węzły mają pewne wymagania dotyczące pamięci i obliczeń, które sprawiają, że są niewygodne do działania na urządzeniach o niskiej mocy, takich jak smartfony. Z drugiej strony klienci SPV po prostu sprawdzają pełne węzły w celu uzyskania informacji dotyczących portfela użytkownika.
Najprostszym rozwiązaniem do przekazania tych danych użytkownikowi byłoby uświadomienie pełnych węzłów o kluczach klienta, aby wysyłane były do nich tylko odpowiednie transakcje. Jest to oczywiste rozwiązanie, ponieważ prywatność klienta zostałaby poświęcona. Z drugiej strony pobieranie wszystkich transakcji tylko w celu odrzucenia większości z nich byłoby marnotrawstwem przepustowości. Wprowadź filtry Bloom’a.
Zilustrujmy to. Załóżmy, że klient, Alice, ma transakcję o wysokiej wartości, której nie chce, aby Bob, który prowadzi pełny węzeł, był tego świadomy. Tworzy filtr Blooma, który zilustrujemy jako siatkę 10 x 1:
Przekazuje dane transakcji, którymi jest zainteresowana, za pośrednictwem dwóch różnych funkcji skrótu, które generują dwie liczby od 0 do 9. Nazwijmy je 4 i 7. Wysyła filtr do Boba.
Patrząc na tę siatkę, nie masz pojęcia, jakie dane Alice przekazała do filtra. Jeśli masz zestaw, w którym dane są zawarte, możesz go zaszyfrować i porównać z filtrem – jeśli istnieje dopasowanie, istnieje możliwość, że to była informacja, o którą poprosiła Alice.
Jednocześnie prawdopodobnie będzie wiele danych wejściowych, które zostaną odwzorowane na 4 i 7, więc Bob nie może określić, którą częścią danych Alice jest zainteresowana. Po prostu zwraca wszystkie dopasowania, a Alice filtruje je na swoim końcu.
Jest to oczywiście rażące uproszczenie, ale pokazuje koncepcję: filtry Bloom’a zaciemniają prawdziwe interesy klienta. Nie jest to idealna metoda (nadal istnieją obawy o jej prywatność), ale stanowi ulepszenie w stosunku do nieekranowanego żądania do węzła.
