Bitcoin block propagation with IBLT, Part I

The problem statement is not so simple; one one hand there is incentive for the miner to keep the block small so that it propagates the network faster but that is looking at immediate profit, however, on the other hand, Peter Todd has shown[1] in the bitcoin-dev mailinglist that actually "increasing" the blocksize and even withholding it for some time significantly increases profit in the near long term.

Now, even ignoring this, if we assume the problem statement just as what the author describes, there are problems with his approach. Firstly, big pools have said that they operate at a loss and their aim is not to earn profit from mining but by providing value-added services like 'guaranteed tx confirmation', which big pools can. Secondly, and technically, this only works if data set is low so as to keep collision low [2]. Beyond a certain point there are many false positives and worst case all transactions might be needed to sent anyways.

So although this is not worse than the current status, but certainly could end up not even being useful.

[1] http://www.mail-archive.com/bitcoin-development@lists.source... [2] https://en.wikipedia.org/wiki/Bloom_filter#Interesting_prope...

[1]: Selfish mining may be a problem, and only big miners can profit from it. This has nothing to do with IBLTs though, other than that big miners may withhold them just as they would withhold a full block. The rest of us (small miners) can still use IBLTs to decrease our orphan rate.

"providing value-added services": Yes, it's up to each and every miner to decide how and when blocks are transmitted. If they want fast propagation, use IBLT. If not, use full block. Any relay node may as well chose to relay it as an IBLT or as a full block.

"Beyond a certain point there are many false positives and worst case all transactions might be needed to sent anyways": Definately yes! I will present some stats on that in future blog posts. Meanwhile you can look at https://github.com/kallerosenbaum/bitcoin-iblt/wiki for some data on this.

The abstract problem is there is a set of objects and all peers have access to some subset of them. You want to communicated an ordered list of them plus some arbitrary data (your winning hash) to as many peers in as little data as possible.

It seems to me that the best solution is to have a well agreed upon function that keeps them in an ordered state and simply keep track of what transactions your neighbors know about, the information should largely already be there due to the fact that the transactions are dissiminated by a gossip protocol in the first place.