Was sind Bloom-Filter und wofür sind sie gut?

Dieser Artikel ist der erste in einer Reihe, die die technischen Konzepte behandelt, welche im Kontext von On-Chain Skalierung, Blockpropagation und verwandten Themengebieten eine entscheidende Rolle spielen.

Eine Datenstruktur bezeichnet das Format, welches dazu verwendet wird, um Informationen zu speichern. Beim Bloom-Filter handelt es sich um eine probabilistische Datenstruktur, durch die eine Menge bestimmt werden kann. Wir werden nun zuerst darüber sprechen, was ein Bloom-Filter genauer ist, um dann dessen Nachteile bei der Erfüllung eines bestimmten Zwecks zu betrachten. Zum Schluß werden wir uns ansehen, welche konkrete Bedeutung der Bloom-Filter für Bitcoin Cash und Dash hat.

Wie funktioniert der Bloom-Filter?

Ein herkömmlicher Computer speichert alle Informationen als Nullen und Einsen ab. Diese kleinste Einheit, die dabei entsteht, wird von Informatikern Bit genannt. Um einen Bloom-Filter zu erstellen, müssen wir zunächst festlegen, wie viele Bits dieser Filter verwenden soll. Dabei ist es notwendig eine Reihe von Hash-Funktionen auszuwählen. Sehen wir uns z.B. einen Bloom-Filter mit 12-Bit an, der auf zwei Hash-Funktionen zurückgreift, um damit zwei Elemente zu bestimmen. Dies bedeutet, dass jede Hash-Funktion, die ein Element mit einbezieht, nur ein Bit bestimmt. Sie produziert dabei Zahlen zwischen 1 und 12.

Nehmen wir in diesem Beispiel nun an, dass das erste Element 4 und 9 bestimmt hat, während es beim zweiten Element 7 und 10 waren. Der Bloom-Filter stellt diese beiden Elemente mit 12 Bits dar, wobei 4, 7, 9 und 10 eingeschaltet sind. Nur wenn ein Bit einmal oder mehrmals bestimmt wird, wird es auch angeschaltet.

Wollen wir nun überprüfen, ob der Bloom-Filter diese Einträge wirklich erkennt, können wir schauen, ob das Element den Bloom-Filter passieren kann. Nur wenn die Bits 4 und 9 eingeschaltet sind, wird das Element den Bloom-Filter auch passieren.

Wenden wir nun die Hash-Funktion an, um 7 und 11 zu erhalten, so können wir sehen, dass das Element den Bloom-Filter nicht passiert, da das 11. Bit nicht eingeschaltet ist. Ein Bloom-Filter ist also ein tatsächlicher Filter, der dazu konstruiert ist, Elemente einer Reihe zu erkennen und jene, die nicht dazu gehören, auszuschließen.

Betrachten wir also nun ein viertes Element. Wie wahrscheinlich ist es, dass dieses Element den Filter passieren wird? Da der Filter 4 Bits aktiviert hat, ist die Chance 1:3, dass bei der ersten Hash-Funktion ein Wert vorkommt, der einem Bit entspricht, das bereits eingeschaltet ist. Auch bei der zweiten Hash-Funktion ist die Chance wieder 1:3, die Chance, dass das vierte Element den Filter also passieren kann, ist daher 1:9. Ist dies der Fall, wird das Element als falsches Positiv bezeichnet, da es den Filter passieren konnte, ohne selbst zur ursprünglichen Reihe zu gehören.

Dies ist das Problem. Bei einem Bloom-Filter handelt es sich in der Regel nur um eine kleine Datenstruktur, die eine bestimmte Reihe kommuniziert. Die Gefahr ist dabei, dass ein Element fälschlicherweise der Reihe zugeschrieben wird. Das Gute an dem Filter, ist allerdings, dass ein Element, das ihn nicht passieren kann, definitiv nicht zur Reihe gehört. Die Zahl der falschen Positive kann über die Anzahl der Bits und Hash-Funktionen gesteuert werden, wodurch eine beliebige Rate eingestellt werden kann.

Bedeutung des Bloom-Filters für Kryptowährungen

Bitcoin Unlimited verwendet Bloom-Filter, um Transaktionen zu bestimmen, die einer Node unbekannt sind. Bloom-Filter kommen zudem bei Simplified Payment Verification, also SPV, Wallets zum Einsatz. Die mobile Dash Wallet z.B., fragt nach Transaktionen mit Adressen, die einen Bloom-Filter passiert haben. Hierdurch wird die Privatsphäre zu einem gewissen Grad geschützt, da es sich bei manchen Ergebnissen auch lediglich um ein falsches Positiv handeln kann. Schließlich kommen Bloom-Filter auch beim Grapheneprotokoll für das Versenden von Blöcken zum Einsatz. Bei Graphene gibt es zudem eine invertierbare Bloom-Nachschlagetabelle zum Überprüfen von falschen Positiven.

https://dashnews.org/de/was-sind-bloom-filter-und-wofur-sind-sie-gut/