Bitcoin block propagation with IBLT, Part I (opens in new tab)

(popeller.io)

49 pointsmartinkallstrom10y ago5 comments

5 comments

kang10y ago

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...

kallerosenbaum10y ago

[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.

CyberDildonics10y ago

When you say blocksize do you mean block size limit or are you talking about miners not including low fee transactions so they have a smaller block and thus lower latency?

placeybordeaux10y ago

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.

kanzure10y ago

Here is where IBLT was specified:

https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2

http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-...

j / k navigate · click thread line to collapse