What Are Invertible Bloom Lookup Tables?

[ZionRTZ]

How do IBLTs work?

An IBLT has a number of cells. Objects in a set can be packed into each cell. Someone with the IBLT and an item in the set can unpack the item from a cell. Each cell also keeps track of the count of the number of items in the cell. IBLTs are most useful when communicating a set to another computer where you expect that the receiver will know many of the items in the set but not all the items. An IBLT can be used to identify missing items.

As an example, lets consider a IBLT with eight cells, and the 10 items a,b,c,t,u,v,w,x,y,z. Similar to how bits are chosen for a bloom filter cells are chosen to pack each item in to our IBLT. Let’s say a is packed into cell 1 and 3, b is packed into 3 and 6, and c is packed into 6 and 8. After packing these three items into the IBLT it will look something like this:

After packing all the items into this IBLT we would get something like:

Now, this IBLT can be sent to the receiver. If the receiver already knows that t,u,v,w,x,y and z are in the list. The receiver can then unpack these items from the IBLT to restore it to the form below:

Now, after unpacking, the receiver can attempt to decode this IBLT. The decode operation will yield a and c from the first and and eighth cells respectively. However, the over-packed cells 3 and 6 will not return anything. After the receiver recovers these two items, the receiver can then unpack them. After this unpacking a and c the IBLT will look like:

Now the receiver can decode this IBLT to recover b. After unpacking b, the IBLT is empty and the receiver knows they are done. The set has items, a,b,c,t,u,v,w,x,y,z.


What are IBLTs useful for?
IBLTs are very useful when a set needs to be communicated to someone who knows some of the items in the set. One major advantage of an IBLT is that there is no limit as to what can be packed into the IBLT. The receiver can unpack items and the decode operation may still work. A disadvantage of IBLTs is that the receiver will may need to unpack some items to get any information. In the example above, if the receiver did not know any items in the set, the IBLT would not help them.

In some applications the number of missing items can be estimated. In this case, the probability of decoding the IBLT can be calculated. In practice, aspects of the IBLT such as the number of cells can be adjusted to maximize the probability of decoding. There is a trade off as larger IBLTs generally have a better chance of decoding. That is, IBLTs could be made more compact and have a lower probability of decoding or they could require more bandwidth and be more likely to decode.

This article has some simplifications. An IBLT adds extra data that provides for an integrity check. Also, the items in an IBLT must not uses too much space. In practice, identifiers are used instead of the items themselves. The receiver can also unpack items that are not in the IBLT and the receiver can still recover the set. The count could be negative in this case.


IBLTs and bloom filters for improving block propagation
Bloom filters and IBLTs are the two main tools that are used by Gavin Andresen in an article that was a predecessor of the graphene block propagation protocol. If you really want to do a deep dive into IBLTs this paper is a good place to start.


SOURCE: https://dashnews.org/what-are-invertible-bloom-lookup-tables/