Published on: 2015-06-27T04:46:35+00:00
Rusty Russell has developed a model for using Invertible Bloom Lookup Tables (IBLT) to communicate blocks between peers. The model is designed to be as flexible as possible, making few assumptions on transaction selection policy and relying on similarity in mempools, with some selection hints. The selection hints are minimum fee-per-byte and bitmaps of included-despite-that and rejected-despite-that. The former covers things like child-pays-for-parent and the priority area. The latter covers other cases like Eligius censoring "spam", bitcoin version differences, etc.The model performs reasonably well on a 100 block sample in bitcoin-corpus. There is more work to do, and more investigation to be done, but Rusty doesn't expect more than a 25% reduction in this "ideal minimum" result. Kalle Rosenbaum previously investigated IBLTs with Rusty last year.Rusty Russell's implementation of IBLTs does not use a keyHashSum, but instead concatenates (txid48, fragid, tx-chunk) as the value. The txid48+fragid functions as a kind of keyHashSum. Kalle Rosenbaum thinks this idea is very good.Rosenbaum asked if Rusty implemented his idea to remove all the count==1 fragments in ascending order of (fragid-base_fragid). Rusty replied that he keeps records of all the 1 and -1 buckets; separate lists depending on how far they are off the base. Lists for 0, 1, 2, ... 7, then powers of 2. They also discussed making more comparable tests as proposed last year by Rosenbaum.Rusty's design relies on similarity in mempools, with some selection hints. It is designed to be re-encoded between nodes as nodes will have similar mempools. Actual results will have to be worse than these minima, as peers will have to oversize the IBLT to have a reasonable chance of success.Rosenbaum suggested that exceptional tx *could* instead be encoded in the IBLT, just as if they were unknown differences. Rusty said that it's pretty easy to cut the bitmaps to zero and test this, whereas the overhead of IBLT is some factor greater than txsize. The purpose of reencoding when relaying is to improve the failure probability as new tx may have arrived in the mempool of the intermediary node.Rusty Russell thanks Kalle Rosenbaum for helping investigate IBLTs last year and adds that he works for Blockstream, while supposed to be working on Lightning.
Updated on: 2023-08-01T13:49:42.988801+00:00