From: Rusty Russell <rusty@rustcorp•com.au>
To: bitcoin-dev@lists•linuxfoundation.org
Subject: [bitcoin-dev] [RFC] IBLT block testing implementation
Date: Tue, 23 Jun 2015 15:23:27 +0930 [thread overview]
Message-ID: <871th3t1go.fsf@rustcorp.com.au> (raw)
Hi all,
I've come up with a model for using IBLT to communicate blocks
between peers. The gory details can be found on github: it's a
standalone C++ app for testing not integrated with bitcoin.
https://github.com/rustyrussell/bitcoin-iblt
Assumptions and details:
1. The base idea comes from Gavin's Block Propagation gist:
https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2
2. It relies on similarity in mempools, with some selection hints. This
is designed to be as flexible as possible to make fewest assumptions
on tx selection policy.
3. The selection hints are: minimum fee-per-byte (fixed point) 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.
4. Cost to represent these exceptional added or excluded transactions is
(on average) log2(transactions in mempool) bits.
5. At Peiter Wuille's suggestion, it is designed to be reencoded between
nodes. It seems fast enough for that, and neighboring nodes should
have most similar mempools.
6. It performs reasonably well on my 100 block sample in bitcoin-corpus
(chosen to include a mempool spike):
Average block range (bytes): 7988-999829
Block size mean (bytes): 401926
Minimal decodable BLT size range (bytes): 314-386361
Minimal decodable BLT size mean (bytes): 13265
7. Actual results will have to be worse than these minima, as peers will
have to oversize the IBLT to have reasonable chance of success.
8. There is more work to do, and more investigation to be done, but I
don't expect more than a 25% reduction in this "ideal minimum"
result.
Special thanks to Kalle Rosenbaum for helping investigate IBLTs with me
last year.
Cheers,
Rusty.
PS. I work for Blockstream. And I'm supposed to be working on
Lightning, not this.
next reply other threads:[~2015-06-23 5:53 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-06-23 5:53 Rusty Russell [this message]
2015-06-25 21:02 ` Kalle Rosenbaum
2015-06-27 4:46 ` Rusty Russell
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=871th3t1go.fsf@rustcorp.com.au \
--to=rusty@rustcorp$(echo .)com.au \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox