Bloom-Filter
Ein Bloom-Filter ist eine Datenstruktur, die verwendet werden kann, um dem Benutzer mitzuteilen, ob ein bestimmtes Element Teil einer Menge ist.
Obwohl ein Bloom-Filter nicht mit Sicherheit sagen kann, ob ein Element in der Menge enthalten ist, kann er mit Sicherheit sagen, ob das Element nicht enthalten ist.
Bloom-Filter wurden 1970 von Burton Howard Bloom entwickelt und sind aufgrund ihrer effizienten Raumnutzung ein vielseitiges Werkzeug für eine Reihe von Anwendungen.
Bei einigen Kryptowährungen (vor allem Bitcoin) spielen sie eine wesentliche Rolle bei der vereinfachten Zahlungsverifizierung (Simplified Payment Verification, oder kurz SPV).
Durch die Verwendung eines SPV-Clients können Benutzer mit dem Bitcoin-Netzwerk interagieren, ohne einen vollständigen Node zu betreiben.
Full Nodes sind mit bestimmten Speicher- und Rechenanforderungen verbunden, die sie für den Betrieb auf Geräten mit geringer Leistung wie Smartphones unhandlich machen.
SPV-Clients hingegen fragen einfach Full Nodes nach Informationen ab, die für die Wallet(s) des Nutzers relevant sind.
Die einfachste Lösung, um diese Daten an den Nutzer weiterzugeben, besteht darin, den Full Nodes die Schlüssel des Kunden mitzuteilen, sodass nur relevante Transaktionen an sie gesendet werden.
Dies ist natürlich eine unzureichende Lösung, da die Privatsphäre des Kunden geopfert werden würde. Andererseits wäre es eine Verschwendung von Bandbreite, alle Transaktionen herunterzuladen, nur um die meisten von ihnen zu verwerfen. Hier kommen Bloom-Filter ins Spiel.
Zur Veranschaulichung. Nehmen wir an, dass eine Kundin, namens Alice, eine Transaktion von hohem Wert hat, von der sie nicht möchte, dass Bob, der einen vollständigen Node betreibt, davon erfährt. Sie konstruiert einen Bloom-Filter, den wir als 10 × 1-Gitter darstellen werden:
Sie lässt die Transaktionsdaten, an denen sie interessiert ist, durch zwei verschiedene Hash-Funktionen laufen, die zwei Zahlen zwischen 0 und 9 ausgeben. Benennen wir sie in diesem Beispiel als 4 und 7. Sie sendet den Filter an Bob.
Wenn man sich dieses Raster ansieht, weiß man nicht, welche Daten Alice an den Filter weitergegeben hat. Hätte man einen Datensatz, in dem die Daten enthalten sind, könnte man ihn hacken und mit dem Filter vergleichen – wenn es eine Übereinstimmung gibt, besteht die Möglichkeit, dass es sich um die von Alice angeforderten Informationen handelt.
Gleichzeitig gibt es wahrscheinlich viele Eingaben, die mit 4 und 7 übereinstimmen, sodass Bob nicht feststellen kann, an welchem Teil der Daten Alice interessiert ist. Er gibt einfach alle Übereinstimmungen zurück, und Alice filtert sie auf ihrer Seite.
Das ist natürlich eine grobe Vereinfachung, aber es veranschaulicht das Konzept: Bloom-Filter verschleiern die wahren Interessen des Kunden.
Es ist keine perfekte Methode (es gibt immer noch Bedenken hinsichtlich des Datenschutzes), aber es ist eine Verbesserung gegenüber einer ungeschützten Anfrage an einen Node.
« Zurück zum Glossar Index