1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
Return-Path: <rusty@ozlabs.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id DD58983D
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 Jun 2015 05:53:37 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from ozlabs.org (ozlabs.org [103.22.144.67])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 32BB0136
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 Jun 2015 05:53:37 +0000 (UTC)
Received: by ozlabs.org (Postfix, from userid 1011)
id 7D5901401AF; Tue, 23 Jun 2015 15:53:34 +1000 (AEST)
From: Rusty Russell <rusty@rustcorp.com.au>
To: bitcoin-dev@lists.linuxfoundation.org
User-Agent: Notmuch/0.17 (http://notmuchmail.org) Emacs/24.4.1
(x86_64-pc-linux-gnu)
Date: Tue, 23 Jun 2015 15:23:27 +0930
Message-ID: <871th3t1go.fsf@rustcorp.com.au>
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Status: No, score=-5.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_MED,
RP_MATCHES_RCVD autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: [bitcoin-dev] [RFC] IBLT block testing implementation
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 23 Jun 2015 05:53:38 -0000
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.
|
