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
|
Return-Path: <tier.nolan@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 00908DEB
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 11 Dec 2017 22:42:33 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-oi0-f53.google.com (mail-oi0-f53.google.com
[209.85.218.53])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 38884E7
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 11 Dec 2017 22:42:32 +0000 (UTC)
Received: by mail-oi0-f53.google.com with SMTP id l6so12736106oih.11
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 11 Dec 2017 14:42:32 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to;
bh=tQg/nJokEm9Jq7ZJTlon82+1i+xjfniy/n6DupnCYfE=;
b=aC2jfyVkq596on6cRV/Y66XRNyBSUjEqC0J6is1upXV6HDV9TpxOYCukEYkYKI7GT7
Lv4isFP928PK/cSlWyf/ERazUEH5VIPgnA9cKMyzPKi5b/9+F0x1DvpFy58ZfH7iUS3I
hKbqXFroFjV+V5Opgq+sVH0Uaw5IfY1yAOza+COlV67T8GuwCaE0vxt7DiTn17KBLvga
XHB7m7votID4kqIYZjG3dUjQpPcuedG6s1hkr3jzXNE8yTrbXmxdsemNzkoYZyB1HbY+
614xoXa9lX9uWzLazFsNya1A5jyXdeHiHyiP1zCM7UQ2/AzyZZbKqxiw6QR0Y3YCbAwy
vcXw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to;
bh=tQg/nJokEm9Jq7ZJTlon82+1i+xjfniy/n6DupnCYfE=;
b=cfJniy15L5nhlSd6ON3BF3yUFrFP4IVpQs8ccNvD1irK6kEEwqaAgOGPdD8lThRoUW
+8wKGqv1WmfYhZxYX4fPrxJOpgJtrhPAO5eNneh/XGyuVCb2weRDGIRtRavgwzVKsCIF
JiURfQwCY4OOPOSZVMCyPeD2EoUCcMqENSrmdtfDdYnnCWwEFY2k6l3iyAZMPibpGpx4
15lUdI5CqOC4+xpylebYzespjCo9BMt9at5yN9xO8scTfRNhOQvuv54Re+yeiSW709Pz
aqmTqNn++u7CF75fYBEeAcfQACo32yjQ61lFUIGzkkZ92HJAG5jLekbYv4+OvHwApj5z
zJAw==
X-Gm-Message-State: AKGB3mJgvVn9kjCJvRKvbj23z1atMU8+Z6yY2lEKtbG3+3rnXp4WhwWb
ckfQHgaoWEb0bXNySyCxCpaQLtoa2GxlVmdC/Y6wSacM
X-Google-Smtp-Source: ACJfBotkFvEQblFV/FJVW0AAj2G04XTegA/qKvOXFdKA0IpsIVQ0Fi1J+GJOxFojC2pehuTBbuM8Nd2euAQPHAvusAo=
X-Received: by 10.202.53.197 with SMTP id c188mr1516994oia.205.1513032151307;
Mon, 11 Dec 2017 14:42:31 -0800 (PST)
MIME-Version: 1.0
Received: by 10.74.38.72 with HTTP; Mon, 11 Dec 2017 14:41:50 -0800 (PST)
In-Reply-To: <CADZtCSi1vimZ88kqG=HQHa3sHeLtvMjdJrZuqS2=iYr-=EHaLw@mail.gmail.com>
References: <CADZtCShywq_s9ZK3oBBTUdCgjrTxbyeb-p7QrhJJ3mwRAECCMA@mail.gmail.com>
<CAAS2fgROykenGH43_FXun+q4u+=94tKqnRW=kQQ2AQFeXKdW=Q@mail.gmail.com>
<CADZtCSi1vimZ88kqG=HQHa3sHeLtvMjdJrZuqS2=iYr-=EHaLw@mail.gmail.com>
From: Tier Nolan <tier.nolan@gmail.com>
Date: Mon, 11 Dec 2017 22:41:50 +0000
Message-ID: <CAE-z3OUetqa16Ub792dCXodpzafsgMyvO9QaVNWJ3bKZ59HWVQ@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="001a113cfb3ce99e710560183f58"
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
Subject: Re: [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 22:42:33 -0000
--001a113cfb3ce99e710560183f58
Content-Type: text/plain; charset="UTF-8"
On Mon, Dec 11, 2017 at 9:56 PM, Jim Posen via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> Omitting nBits entirely seems reasonable, I wrote up a possible
> implementation here
> <https://github.com/bitcoin/bitcoin/compare/master...jimpo:compact-headers-difficulty>.
> The downside is that it is more complex because it leaks into the
> validation code. The extra 4 byte savings is certainly nice though.
>
A compromise would be to have 1 byte indicating the difference since the
last header.
Since the exponent doesn't use the full range you could steal bits from
there to indicate mode.
- no change
- mantissa offset (for small changes)
- full difficulty
This would support any nBits rule and you say 3 of the 4 bytes.
> Can you elaborate on how parallel header fetching might work? getheaders
> requests could probably already be pipelined, where the node requests the
> next 2,000 headers before processing the current batch (though would make
> sense to check that they are all above min difficulty first).
>
I suggest adding a message where you can ask for the lowest N hashes
between 2 heights on the main chain.
The reply is an array of {height, header} pairs for the N headers with the
lowest hash in the specified range.
All peers should agree on which headers are in the array. If there is
disagreement, then you can at least narrow down on which segment there is
disagreement.
It works kind of like a cut and choose. You pick one segment of the ones
he gave you recursively.
You can ask a peer for proof for a segment between 2 headers of the form.
- first header + coinbase with merkle branch
- all headers in the segment
This proves the segment has the correct height and that all the headers
link up.
There is a method called "high hash highway" that allows compact proofs of
total POW.
--001a113cfb3ce99e710560183f58
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Mon, Dec 11, 2017 at 9:56 PM, Jim Posen via bitcoin-dev <span dir=3D=
"ltr"><<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=
=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>></span> wrote:<br>=
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div cla=
ss=3D"gmail_extra"><div class=3D"gmail_quote"><span class=3D"gmail-"></span=
><div>Omitting nBits entirely seems reasonable, I wrote up a possible imple=
mentation <a href=3D"https://github.com/bitcoin/bitcoin/compare/master...ji=
mpo:compact-headers-difficulty" target=3D"_blank">here</a>. The downside is=
that it is more complex because it leaks into the validation code. The ext=
ra 4 byte savings is certainly nice though.</div></div></div></div></blockq=
uote><div><br></div><div>A compromise would be to have 1 byte indicating th=
e difference since the last header.</div><div><br></div><div>Since the expo=
nent doesn't use the full range you could steal bits from there to indi=
cate mode.</div><div><br></div><div>- no change</div><div>- mantissa offset=
(for small changes)</div><div>- full difficulty</div><div><br></div><div>T=
his would support any nBits rule and you say 3 of the 4 bytes.<br></div><di=
v></div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:=
0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">=
<div dir=3D"ltr"><div class=3D"gmail_extra">Can you elaborate on how parall=
el header fetching might work? getheaders requests could probably already b=
e pipelined, where the node requests the next 2,000 headers before processi=
ng the current batch (though would make sense to check that they are all ab=
ove min difficulty first).</div></div></blockquote><div><br></div><div>I su=
ggest adding a message where you can ask for the lowest N hashes between 2 =
heights on the main chain.<br></div><div><br></div><div>The reply is an arr=
ay of {height, header} pairs for the N headers with the lowest hash in the =
specified range.<br></div><div><br></div><div>All peers should agree on whi=
ch headers are in the array.=C2=A0 If there is disagreement, then you can a=
t least narrow down on which segment there is disagreement.</div><div><br><=
/div><div>It works kind of like a cut and choose.=C2=A0 You pick one segmen=
t of the ones he gave you recursively.<br></div><div><br></div><div>You can=
ask a peer for proof for a segment between 2 headers of the form.<br></div=
><div><br></div><div>- first header + coinbase with merkle branch</div><div=
>- all headers in the segment<br></div><div><br></div><div>This proves the =
segment has the correct height and that all the headers link up.</div><div>=
<br></div><div>There is a method called "high hash highway" that =
allows compact proofs of total POW.<br></div></div></div></div>
--001a113cfb3ce99e710560183f58--
|
