how does the IBLT scale with the size of the block UTXO set? linearly or by some other ratio?
edit: actually iirc, it scales with the size of the difference btwn UTXO set estimates across the network. iow, a UTXO set estimated to be 99% similar across the network will allow a miner to send a smaller IBLT when solving a block than a UTXO set estimated to be only 89% similar across the network. is that right?
Yes. The size of an IBLT does depend upon the average expected number of differences between the unconfirmed tx mempools of the majority of the nodes. Because each node has independent choice on which tx to accept or reject then it is impossible to be precise, in advance, about how efficient IBLT will be. Miners will always want to propagate small blocks, so there will be an incentive for mining nodes to find consensus on their tx mempools. Gavin describes it:
RE: O(1) versus O(some-function-of-total-number-of-transactions):
Yes, it will depend on whether or not the number of differences goes up as the number of transactions goes up.
The incentives align so it is in everybody's best interest to make the differences as small as possible. I wouldn't be surprised if that causes innovations to drive the actual size to O(1) minus an increasing constant, as code gets better at predicting which transactions our peers do or don't have.
It is also worth noting that IBLT can be implemented on top of other block propagation models, such as Matt Corallo's block relay system, which already saves on bandwidth.
with anything new like this, i'm interested in knowing the upper and lower bounds of the IBLT data size.
lower bound: theoretically, as the UTXO set difference shrinks to zero with 0 network latency, the IBLT will shrink similarly but can never reach zero since it has to at minimum relay enough data to convey the exact subset of tx's included in the miner's block. how small can this data get esp in relation to the avg block size now?
upper bound: if the UTXO set difference is 100%, how big does the IBLT data size get? or does the entire IBLT concept fall apart at some intermediate set difference?