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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
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 C709E256
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 11 May 2016 00:54:26 +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 9506713D
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 11 May 2016 00:54:22 +0000 (UTC)
Received: by ozlabs.org (Postfix, from userid 1011)
id 3r4Hgw2WB3z9t3m; Wed, 11 May 2016 10:54:20 +1000 (AEST)
From: Rusty Russell <rusty@rustcorp.com.au>
To: Gregory Maxwell <greg@xiph.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
In-Reply-To: <CAAS2fgRePSQ=-3MTR3p3U1zbd1ucfNg0_ocAegJCi4qR=XpypA@mail.gmail.com>
References: <5727D102.1020807@mattcorallo.com> <5730C37E.2000004@gmail.com>
<87twi6zdl8.fsf@rustcorp.com.au>
<CAAS2fgRePSQ=-3MTR3p3U1zbd1ucfNg0_ocAegJCi4qR=XpypA@mail.gmail.com>
User-Agent: Notmuch/0.21 (http://notmuchmail.org) Emacs/24.5.1
(x86_64-pc-linux-gnu)
Date: Wed, 11 May 2016 06:53:55 +0930
Message-ID: <87k2j1zjx0.fsf@rustcorp.com.au>
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Status: No, score=-4.7 required=5.0 tests=BAYES_00, DATE_IN_PAST_03_06,
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: Re: [bitcoin-dev] Compact Block Relay BIP
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol 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: Wed, 11 May 2016 00:54:26 -0000
Gregory Maxwell <greg@xiph.org> writes:
> On Tue, May 10, 2016 at 5:28 AM, Rusty Russell via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
>> I used variable-length bit encodings, and used the shortest encoding
>> which is unique to you (including mempool). It's a little more work,
>> but for an average node transmitting a block with 1300 txs and another
>> ~3000 in the mempool, you expect about 12 bits per transaction. IOW,
>> about 1/5 of your current size. Critically, we might be able to fit in
>> two or three TCP packets.
>
> Hm. 12 bits sounds very small even giving those figures. Why failure
> rate were you targeting?
That's a good question; I was assuming a best-case in which we have
mempool set reconciliation (handwave) thus know they are close. But
there's also an alterior motive: any later more sophisticated approach
will want variable-length IDs, and I'd like Matt to do the work :)
In particular, you can significantly narrow the possibilities for a
block by sending the min-fee-per-kb and a list of "txs in my mempool
which didn't get in" and "txs which did despite not making the
fee-per-kb". Those turn out to be tiny, and often make set
reconciliation trivial. That's best done with variable-length IDs.
> (*Not interesting because it mostly reduces exposure to loss and the
> gods of TCP, but since those are the long poles in the latency tent,
> it's best to escape them entirely, see Matt's udp_wip branch.)
I'm not convinced on UDP; it always looks impressive, but then ends up
reimplementing TCP in practice. We should be well within a TCP window
for these, so it's hard to see where we'd win.
>> I would also avoid the nonce to save recalculating for each node, and
>> instead define an id as:
>
> Doing this would greatly increase the cost of a collision though, as
> it would happen in many places in the network at once over the on the
> network at once, rather than just happening on a single link, thus
> hardly impacting overall propagation.
"Greatly increase"? I don't see that.
Let's assume an attacker grinds out 10,000 txs with 128 bits of the same
TXID, and gets them all in a block. They then win the lottery and get a
collision. Now we have to transmit ~48 bytes more than expected.
> Using the same nonce means you also would not get a recovery gain from
> jointly decoding using compact blocks sent from multiple peers (which
> you'll have anyways in high bandwidth mode).
Not quite true, since if their mempools differ they'll use different
encoding lengths, but yes, you'll get less of this.
> With a nonce a sender does have the option of reusing what they got--
> but the actual encoding cost is negligible, for a 2500 transaction
> block its 27 microseconds (once per block, shared across all peers)
> using Pieter's suggestion of siphash 1-3 instead of the cheaper
> construct in the current draft.
>
> Of course, if you're going to check your whole mempool to reroll the
> nonce, thats another matter-- but that seems wasteful compared to just
> using a table driven size with a known negligible failure rate.
I'm not worried about the sender: The recipient needs to encode all the
mempool.
>> As Peter R points out, we could later enhance receiver to brute force
>> collisions (you could speed that by sending a XOR of all the txids, but
>> really if there are more than a few collisions, give up).
>
> The band between "no collisions" and "infeasible many" is fairly
> narrow. You can add a small amount more space to the ids and
> immediately be in the no collision zone.
Indeed, I would be adding extra bits in the sender and not implementing
brute force in the receiver. But I welcome someone else to do so.
Cheers,
Rusty.
|
