Was sind Invertible Bloom Lookup Tables?

Dieser Artikel ist der zweite in einer Reihe, die sich mit den technischen Konzepten befasst, die mit OnChain-Skalierung, Blockpropagation und verwandten Themen zusammenhängen.

In der letzten Woche sprachen wir davon, wie Bloom-Filter uns dabei helfen können, Elemente einer Reihe zu identifizieren. Eine Datenstruktur, die hiermit zusammenhängt, nennt sich Invertible Bloom Lookup Table oder auch IBLT. Der Vorteil hierbei ist, dass fehlende Reihenmitglieder identifiziert werden können. Ansonsten ähneln sich die beiden Konzepte. In diesem Text möchte ich nun vereinfacht erklären, was IBLT ist und wofür es verwendet wird.

Wie funktionieren IBLTs?

Ein IBLT verfügt über mehrere Zellen. Elemente einer Reihe können dabei jeder Zelle zugewiesen werden. Jemand, der über den IBLT verfügt, kann ein Element aus einer Zelle extrahieren. IBLTs sind dann am nützlichsten, wenn eine Reihe an ein anderes Gerät gesandt wird, das bereits einige Elemente kennt, aber eben noch nicht alle. Über ein IBLT können die fehlenden Elemente identifiziert werden.

Betrachten wir nun ein IBLT mit acht Zellen und zehn Elementen (a,b,c,t,u,v,w,x,y,y,z). Ähnlich wie bei den Bits, die für den Bloom-Filter verwendet wurden, werden nun Zellen ausgewählt. Nehmen wir an, dass a in Zelle 1 und 3 gepackt wurde, b in 3 und 6 und c in 6 und 8. Nachdem dies geschehen ist, sollte das IBLT etwa so aussehen:

Nachdem alle zehn Elemente gepackt wurden, sieht es dann so aus:

Diese IBLT kann nun an den Empfänger gesandt werden, der bereits weiß, dass t,u,v,w,x,y und z enthalten sind. Daher kann der Empfänger diese Elemente bereits aus dem IBLT entpacken:

Nach dem Entpacken kann er a und c aus Zelle 1 und 8 dekodieren. Die Zellen 3 und 6 sind allerdings noch überladen. Daher muss er zunächst a und c entpacken, woraufhin nur noch dies stehen bleibt:

Der Empfänger kann dies nun ebenfalls dekodieren und dadurch b wiederherstellen. Nachdem b entpackt wurde, ist das IBLT leer und der Empfänger weiß nun, dass er alles entpackt hat und die Reihe die Elemente a,b,c,t,u,v,w,x,y,y,z enthielt.

Wofür können IBLTs verwendet werden?

IBLTs sind besonders dann von Wert, wenn eine Reihe an jemanden übermittelt werden muss, der bereits die Mehrheit der Elemente dieser Reihe kennt. Von ganz besonderem Interesse ist dabei, dass sehr viele verschiedene Informationen in ein IBLT verpackt werden können. Der Nachteil ist, dass der Empfänger Elemente, die er noch nicht kennt, entpacken muss. Daher bieten IBLTs keine Vorteile, wenn der Empfänger noch keine der Elemente kennt.

Da die Anzahl der fehlenden Elemente geschätzt werden kann, ist es möglich die Wahrscheinlichkeit der Notwendigkeit einer Dekodierung zu berechnen. Hierdurch kann eine gewisse Priorisierung geschaffen werden, bei der das IBLT entweder kompakter gehalten wird, wodurch die Wahrscheinlichkeit geringer ist, oder eine höhere Bandbreite zum früheren Dekodieren notwendig ist.

Dieser Artikel stellt IBLTs sehr vereinfacht dar, da IBLTs auf weitere Daten zugreifen, um eine Integritätsprüfung durchzuführen. Da die Elemente selbst nicht zu viel Platz beanspruchen dürfen, werden in der Praxis Identifikatoren statt der Elemente selbst verwendet. Zudem kann der Empfänger auch Elemente entpacken, die nicht zu der Reihe gehören, damit er diese noch retten kann. Dadurch kann die angegebene Zahl sogar negativ sein.

IBLTs und Bloom-Filter in Bezug auf Blockpropagation

Bloom-Filter und IBLTs sind zwei Werkzeuge, die von Gavin Andresen in einem Artikel besprochen wurden, der als Vorläufer des Graphene-Propokolls gesehen werden kann. Dieses Paper ist ein guter Einstieg für jene, die sich tiefer mit der Materie beschäftigen wollen.