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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
Return-Path: <jim.posen@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 0A05ED32
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 11 Dec 2017 20:40:03 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f65.google.com (mail-it0-f65.google.com
[209.85.214.65])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 334F8463
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 11 Dec 2017 20:40:02 +0000 (UTC)
Received: by mail-it0-f65.google.com with SMTP id r6so18953230itr.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 11 Dec 2017 12:40:02 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:from:date:message-id:subject:to;
bh=7cRhwl0rqgzXhoC5A7BQo0qeV40twdMllTjPRoV+S+8=;
b=MZzFAOBmRmpjaRkuDA9PlfTMsZZIZA+UjYyeSj3PzOUTuf9UvDraOaf2NVrFDjcpwq
5Al5f0v8xEGMuA8cRwZNdluDuPZvIoUferfKb7r1P2SEbfsFgT79CbgfbmZX5m8Y6+8L
Wpoww0BLoXojPcJcjhU6sO3nh/gtsw1VfXE3M3KpAqbr8Bang5bHI8us6P9E26XSkg/B
AOu9z9puxo/wBjL7zVxieQrmRnDND/BVuEN6mMM3lpDbURkliK292h9G9gZNfszxChws
ajQFxCCVQjbX9tRskjMC46WMDE0KU5Td3StBem7B7ZWcMz6JHB8it7CpFm5sHxS9SNUi
vKMQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
bh=7cRhwl0rqgzXhoC5A7BQo0qeV40twdMllTjPRoV+S+8=;
b=YswntPNgelGENbUT68zkNVXm4qu/EijHXldd01V3OaddO7zQGUd5/SuAuYHAOTZsRd
cMJzNrSSos9ZZtQBmsxBgNj+9k/GKLz+F5XQugxPBrkKrQIkaNlhRXokyjD1cIytOiPr
26WtTF6zdUzbMn/vILDFoyknxIaxa+GFSw14MR918DH1Rl0yU7AxVQgr0MBiHiaPxKdv
aOr+COQTt5xti2hEHgxPkTrzoUysb4RyglzgfV/1mg3G1c5aiyw37B8hOYo8+iiTEPyT
RNVS3g42qqDxom0VLTon1rI64LXlox4xcRvZ4+SkA//FwT88igO77XqUbiJVhEq+clSc
FlJQ==
X-Gm-Message-State: AKGB3mIBSgaTNhQ4LLRWUqF/NXetLwhurF0QGHfZ4sKsinkk5t3lYKRC
vHqHhmRP++MAPu873B7BAWf0GF8WFClqTgU6RZzogZfH
X-Google-Smtp-Source: ACJfBouQnH0U4dQyWmJh50b3NbgfZPh3UdxPOTTQXNz2+mqzKsAU2d91SJkA0g23ikA8RqFgqfssTDf2HMdVc62ekHY=
X-Received: by 10.107.201.134 with SMTP id z128mr2160887iof.177.1513024801159;
Mon, 11 Dec 2017 12:40:01 -0800 (PST)
MIME-Version: 1.0
Received: by 10.107.13.9 with HTTP; Mon, 11 Dec 2017 12:40:00 -0800 (PST)
From: Jim Posen <jim.posen@gmail.com>
Date: Mon, 11 Dec 2017 12:40:00 -0800
Message-ID: <CADZtCShywq_s9ZK3oBBTUdCgjrTxbyeb-p7QrhJJ3mwRAECCMA@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary="94eb2c0b84f0cf3f4b05601689ed"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE 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, 11 Dec 2017 20:43:53 +0000
Subject: [bitcoin-dev] "Compressed" headers stream
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: Mon, 11 Dec 2017 20:40:03 -0000
--94eb2c0b84f0cf3f4b05601689ed
Content-Type: text/plain; charset="UTF-8"
I want to resurrect this thread from August/September because it seems like
a significant improvement for light clients at very little cost. From the
mailing list, it seems like this got stalled in determining how many more
bytes could be save in addition to the prev_block.
The ideas I've gathered from Greg Maxwell's forwarded email are:
1. Omit nBits altogether and have the receiving node determine it from
chain context.
2. Include nBits only on headers with a height that is a multiple of 2016
since it does not change in between.
3. Compress nTime to two bytes by using the bounds on allowed values from
the consensus rules.
I propose just moving ahead with only the exclusion of the prev_block, as
IMO the other savings are not worth the added complexity.
Firstly, I don't like the idea of making the net header encoding dependent
on the specific header validation rules that Bitcoin uses (eg. the fact
that difficulty is only recalculated every 2016 blocks). This would be
coupling together the two layers, breaking net compatibility for some alts,
and possibly making consensus rule changes even more difficult for a
savings with insufficient benefit. So if you buy that argument, I'm not in
favor of #2 or #3.
Option 1 is still viable, though it has some downsides. The implementation
leaks into the validation code, whereas calculating prev_block can occur
just at the net layer (see implementation below). Also, nodes would now be
*required* to sync the header chain from the genesis block, whereas they
had the option of starting from some checkpoint before.
So switching gears, I'd like to ask what the best way to actually implement
this change is. Solutions I can think of are:
1. New headers command name like "cmpctheaders" or "headersv2".
2. Change serialization of existing headers message in a new protocol
version.
3. Change serialization of existing headers message with new service bit.
I wrote up some proof-of-concept implementations in Core a) just omitting
prev_block
<https://github.com/bitcoin/bitcoin/compare/master...jimpo:compact-headers>
and b) omitting nBits as well
<https://github.com/bitcoin/bitcoin/compare/master...jimpo:compact-headers-difficulty>.
If people think a) is reasonable, I'll write up a BIP.
> Hi everyone, the Bitcoin headers are probably the most condensed and
> important piece of data in the world, their demand is expected to grow.
> When sending a stream of continuous block headers, a common case in IBD and
> in disconnected clients, I think there is a possible optimization of the
> transmitted data: The headers after the first could avoid transmitting the
> previous hash cause the receiver could compute it by double hashing the
> previous header (an operation he needs to do anyway to verify PoW). In a
> long stream, for example 2016 headers, the savings in bandwidth are about
> 32/80 ~= 40% without compressed headers 2016*80=161280 bytes with
> compressed headers 80+2015*48=96800 bytes What do you think? In
> OpenTimestamps calendars we are going to use this compression to give
> lite-client a reasonable secure proofs (a full node give higher security
> but isn't feasible in all situations, for example for in-browser
> verification) To speed up sync of a new client Electrum starts with the
> download of a file <https://headers.electrum.org/blockchain_headers>
> ~36MB containing the first 477637 headers. For this kind of clients could
> be useful a common http API with fixed position chunks to leverage http
> caching. For example /headers/2016/0 returns the headers from the genesis
> to the 2015 header included while /headers/2016/1 gives the headers from
> the 2016th to the 4031. Other endpoints could have chunks of 20160 blocks
> or 201600 such that with about 10 http requests a client could fast sync
> the headers
--94eb2c0b84f0cf3f4b05601689ed
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>I want to resurrect this thread from August/September=
because it seems like a significant improvement for light clients at very =
little cost. From the mailing list, it seems like this got stalled in deter=
mining how many more bytes could be save in addition to the prev_block.</di=
v><div><br></div><div>The ideas I've gathered from Greg Maxwell's f=
orwarded email are:</div><div><br></div><div>1. Omit nBits altogether and h=
ave the receiving node determine it from chain context.</div><div>2. Includ=
e nBits only on headers with a height that is a multiple of 2016 since it d=
oes not change in between.</div><div>3. Compress nTime to two bytes by usin=
g the bounds on allowed values from the consensus rules.</div><div><br></di=
v><div>I propose just moving ahead with only the exclusion of the prev_bloc=
k, as IMO the other savings are not worth the added complexity.</div><div><=
br></div><div>Firstly, I don't like the idea of making the net header e=
ncoding dependent on the specific header validation rules that Bitcoin uses=
(eg. the fact that difficulty is only recalculated every 2016 blocks). Thi=
s would be coupling together the two layers, breaking net compatibility for=
some alts, and possibly making consensus rule changes even more difficult =
for a savings with insufficient benefit. So if you buy that argument, I'=
;m not in favor of #2 or #3.</div><div><br></div><div>Option 1 is still via=
ble, though it has some downsides. The implementation leaks into the valida=
tion code, whereas calculating prev_block can occur just at the net layer (=
see implementation below). Also, nodes would now be <i>required</i> to sync=
the header chain from the genesis block, whereas they had the option of st=
arting from some checkpoint before.</div><div><br></div><div>So switching g=
ears, I'd like to ask what the best way to actually implement this chan=
ge is. Solutions I can think of are:</div><div><br></div><div>1. New header=
s command name like "cmpctheaders" or "headersv2".</div=
><div>2. Change serialization of existing headers message in a new protocol=
version.</div><div>3. Change serialization of existing headers message wit=
h new service bit.</div><div><br></div><div>I wrote up some proof-of-concep=
t implementations in Core a) <a href=3D"https://github.com/bitcoin/bitcoin/=
compare/master...jimpo:compact-headers">just omitting prev_block</a> and b)=
<a href=3D"https://github.com/bitcoin/bitcoin/compare/master...jimpo:compa=
ct-headers-difficulty">omitting nBits as well</a>. If people think a) is re=
asonable, I'll write up a BIP.</div><div>=C2=A0</div><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex">Hi everyone, the Bitcoin headers are proba=
bly the most condensed and important piece of data in the world, their dema=
nd is expected to grow. When sending a stream of continuous block headers, =
a common case in IBD and in disconnected clients, I think there is a possib=
le optimization of the transmitted data: The headers after the first could =
avoid transmitting the previous hash cause the receiver could compute it by=
double hashing the previous header (an operation he needs to do anyway to =
verify PoW). In a long stream, for example 2016 headers, the savings in ban=
dwidth are about 32/80 ~=3D 40% without compressed headers 2016*80=3D161280=
bytes with compressed headers 80+2015*48=3D96800 bytes What do you think? =
In OpenTimestamps calendars we are going to use this compression to give li=
te-client a reasonable secure proofs (a full node give higher security but =
isn't feasible in all situations, for example for in-browser verificati=
on) To speed up sync of a new client Electrum starts with the download of a=
file <<a href=3D"https://headers.electrum.org/blockchain_headers">https=
://headers.electrum.org/blockchain_headers</a>> ~36MB containing the fir=
st 477637 headers. For this kind of clients could be useful a common http A=
PI with fixed position chunks to leverage http caching. For example /header=
s/2016/0 returns the headers from the genesis to the 2015 header included w=
hile /headers/2016/1 gives the headers from the 2016th to the 4031. Other e=
ndpoints could have chunks of 20160 blocks or 201600 such that with about 1=
0 http requests a client could fast sync the headers</blockquote></div>
--94eb2c0b84f0cf3f4b05601689ed--
|
