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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
Return-Path: <gmaxwell@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 86EFF26C
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 May 2016 10:43:05 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lf0-f46.google.com (mail-lf0-f46.google.com
[209.85.215.46])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A04621A3
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 May 2016 10:43:04 +0000 (UTC)
Received: by mail-lf0-f46.google.com with SMTP id u64so195666285lff.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 09 May 2016 03:43:04 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:sender:in-reply-to:references:date:message-id:subject
:from:to:cc; bh=jbUlKwK1qClJXF975ry5Rp5py+Yhsh1+C5hK+ND9Xe0=;
b=W8DDHYtg1d8mKt1uL+TE3NezfHC/2NHGwq6m6JWEyhVi4CqF0jd3ja+9PYX3ZwcEPs
8D6lAKjSmiIQKKegVZy/4N/l5m4zNpeNWl0LZTCq6PuicnvlyUJ0bqnYoBKXS657szuI
4vgbyBGjHgjROnSsKa5P2Gp/IsrRPJ1o+AwOzp0BAkwzWCDcbZ8mCVZSHO1Rn5qjfqx3
UR0ocUQg4pw31zPT52rpAB6fshXzFOrVg2FKPLgkiSnovzqUISfmT2tCkAFq5sRzy4Ca
+5cN0glVKqxMkCFsZASHaP9lWKIlNwIFeLB73bBctiB/kA0mefOeYObrCnZ+vGXEFf1c
pQrw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:sender:in-reply-to:references:date
:message-id:subject:from:to:cc;
bh=jbUlKwK1qClJXF975ry5Rp5py+Yhsh1+C5hK+ND9Xe0=;
b=EnUlDBzdoZ3RxQiUSMaMFrqeS2TDteyx3lfX20X/XVSlcMdYmYROL56uT2V0ZvmzbG
1W0ck8XBvQxW6qMZJIkzBmG351SBLjuVA/iMTs+sqD0tjLAOsxoH8bpHq6qU7auluZSb
A4sVdG1ighkpG1BbpUmbOpT4STgowcxtVcBIKx/Wx3rQW6EDTWY1RfE7AO8Hd2+KabJm
PDaVS0L1Epxrp78CLSSVT8gzuUlUaGLmsg91ryKYj5zH9RqoVN8k4qycquUr8lfwnpxD
O+A3MWMe81M6qJzLk0saM+jB8S66W2+WgCTEBD9snC5CBsBysRpS3FN6mVUE+JKuMCyb
OjeQ==
X-Gm-Message-State: AOPr4FXgcOTtYrWmI4m43AqwJ+Dd+YtQX9GvcQ0KCiuJGivqxOTDkCcf0cEyMB5xpvqSYGTrzFH5NYAPBZQ8ww==
MIME-Version: 1.0
X-Received: by 10.112.171.98 with SMTP id at2mr7458330lbc.124.1462790582727;
Mon, 09 May 2016 03:43:02 -0700 (PDT)
Sender: gmaxwell@gmail.com
Received: by 10.112.65.108 with HTTP; Mon, 9 May 2016 03:43:02 -0700 (PDT)
In-Reply-To: <86058327.pdmfHP132A@kiwi>
References: <5727D102.1020807@mattcorallo.com>
<CALOxbZv5GL5br=Z5idR-ACVzkBxS6JP_KgSr3JBuYVLgsej3eA@mail.gmail.com>
<572EB166.5070305@mattcorallo.com> <86058327.pdmfHP132A@kiwi>
Date: Mon, 9 May 2016 10:43:02 +0000
X-Google-Sender-Auth: r_ukf3rzMNmTCJMY5wlNUGe77bQ
Message-ID: <CAAS2fgRiSNNHA5psaUYOM6rHfjJ1aOgWhnsT8Z-pU4FBcR_65w@mail.gmail.com>
From: Gregory Maxwell <greg@xiph.org>
To: Tom Zander <tomz@freedommail.ch>
Content-Type: text/plain; charset=UTF-8
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Mon, 09 May 2016 10:49:33 +0000
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.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 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: Mon, 09 May 2016 10:43:05 -0000
On Mon, May 9, 2016 at 9:35 AM, Tom Zander via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> You misunderstand the networking effects.
> The fact that your node is required to choose which one to set the announce
> bit on implies that it needs to predict which node will have the best data in
> the future.
Not required. It may. If it chooses fortunately, latency is reduced--
to 0.5 RTT in many cases. If not-- nothing harmful happens.
Testing on actual nodes in the actual network (not a "lab") shows that
blocks are normally requested from one of the last three peers they
were requested from 70% of the time, with no special affordances or
skipping samples when peers disconnected.
(77% for last 4, 88% for last 8)
This also _increases_ robustness. Right now a single peer failing at
the wrong time will delay blocks with a long time out. In high
bandwidth mode the redundancy means that node will be much more likely
to make progress without timeout delays-- so long at least one of the
the selected opportunistic mode peers was successful.
Because the decision is non-normative to the protocol, nodes can
decide based on better criteria if better criteria is discovered in
the future.
> Another problem with your solution is that nodes send a much larger amount of
> unsolicited data to peers in the form of the thin-block compared to the normal
> inv or header-first data.
"High bandwidth" mode uses somewhat more bandwidth than low
bandwidth... but still >>10 times less than an ordinary getdata relay
which is used ubiquitously today.
If a node is trying to minimize bandwidth usage, it can choose to not
request the "high bandwidth" mode.
The latency bound cannot be achieved without unsolicited data. The
best we can while achieving 0.5 RTT is try to arrange things so that
the information received is maximally useful and as small as
reasonably possible.
If receivers implemented joint decoding (combining multiple
comprblocks in the event of faild decoding) 4 byte IDs would be
completely reasonable, and were what I originally suggested (along
with forward error correction data, in that case).
> Am I to understand that you choose the solution based on the fact that service
> bits are too expensive to extend? (if not, please respond to my previous
> question actually answering the suggestion)
>
> That sounds like a rather bad way of doing design. Maybe you can add a second
> service bits field of message instead and then do the compact blocks correctly.
Service bits are not generally a good mechanism for negating optional
peer-local parameters.
The settings for compactblocks can change at runtime, having to
reconnect to change them would be obnoxious.
> Wait, you didn't steal the variable length encoding from an existing standard
> and you programmed a new one?
This is one of the two variable length encodings used for years in
Bitcoin Core. This is just the first time it's shown up in a BIP.
[It's a little disconcerting that you appear to be maintaining a fork
and are unaware of this.]
> Look at UTF-8 on wikipedia, you may have "invented" the same encoding that IBM
> published in 1992.
The similarity with UTF-8 is that both are variable length and some
control information is in the high bits. The similarity ends there.
UTF-8 is more complex and less efficient for this application (coding
small numbers), as it has to handle things like resynchronization
which are critical in text but irrelevant in our framed, checksummed,
reliably transported binary protocol.
> Just the first (highest) 8 bytes of a sha256 hash.
>
> The amount of collisions will not be less if you start xoring the rest.
> The whole reason for doing this extra work is also irrelevant as a spam
> protection.
Then you expose it to a trivial collision attack: To find two 64 bit
hashes that collide I need perform only roughly 2^32 computation. Then
I can send them to the network. You cannot reason about these systems
just by assuming that bad things happen only according to pure chance.
This issue is eliminated by salting the hash. Moreover, with
per-source randomization of the hash, when a rare chance collision
happens it only impacts a single node at a time, so the propagation
doesn't stall network wide on an unlucky block; it just goes slower on
a tiny number of links a tiny percent of the time (instead of breaking
everywhere an even tinyer amount of the time)-- in the non-attacker,
chance event case.
|
