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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
|
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
helo=mx.sourceforge.net)
by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <tier.nolan@gmail.com>) id 1V1akM-0007S7-FJ
for bitcoin-development@lists.sourceforge.net;
Tue, 23 Jul 2013 11:27:14 +0000
Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.160.49 as permitted sender)
client-ip=209.85.160.49; envelope-from=tier.nolan@gmail.com;
helo=mail-pb0-f49.google.com;
Received: from mail-pb0-f49.google.com ([209.85.160.49])
by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1V1akH-0003UP-FR
for bitcoin-development@lists.sourceforge.net;
Tue, 23 Jul 2013 11:27:14 +0000
Received: by mail-pb0-f49.google.com with SMTP id jt11so8221477pbb.8
for <bitcoin-development@lists.sourceforge.net>;
Tue, 23 Jul 2013 04:27:03 -0700 (PDT)
MIME-Version: 1.0
X-Received: by 10.66.159.105 with SMTP id xb9mr36438315pab.146.1374578823510;
Tue, 23 Jul 2013 04:27:03 -0700 (PDT)
Received: by 10.70.78.232 with HTTP; Tue, 23 Jul 2013 04:27:03 -0700 (PDT)
Date: Tue, 23 Jul 2013 12:27:03 +0100
Message-ID: <CAE-z3OX+Uzw_diW97yKWGzVMBFZHq2t+w15jNSdGMGqwyJ65yQ@mail.gmail.com>
From: Tier Nolan <tier.nolan@gmail.com>
To: bitcoin-development@lists.sourceforge.net
Content-Type: multipart/alternative; boundary=047d7b6d80267dbeca04e22c127f
X-Spam-Score: -0.6 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(tier.nolan[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
1.0 HTML_MESSAGE BODY: HTML included in message
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
author's domain
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1V1akH-0003UP-FR
Subject: [Bitcoin-development] Distributing low POW headers
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Tue, 23 Jul 2013 11:27:14 -0000
--047d7b6d80267dbeca04e22c127f
Content-Type: text/plain; charset=ISO-8859-1
I was thinking about a change to the rules for distinguishing between forks
and maybe a BIP..
*Summary*
- Low POW headers should be broadcast by the network
If a header has more than 1/64 of the POW of a block, it should be
broadcast. This provides information on which fork is getting most of the
hashing power.
- Miners should use the header information to decide on longest chain
The fork selection rule for miners should be biased towards staying on the
fork that has the most hashing power.
This means that they might keep hashing on a fork that is 1-2 blocks
shorter.
If most miners follow the rule, then it is the best strategy for other
miners to also follow this rule.
- Advantages
This lowers the probability of natural and malicious reversals.
*Distributing low POW headers*
First block header messages that have more than 1/64 of the standard POW
requirements would be forwarded.
This means the client needs to maintain a short term view of the entire
header tree.
if (header extends header tree) {
if (header meets full POW) {
add to header tree;
forward to peers;
check if any blocks in storage now extend the header tree
} else {
if (header meets POW / 64) {
forward to peers;
}
} else {
if (header meets POW) {
add to orphan header storage
}
}
The storage could be limited and headers could be discarded after a while.
This has the extra advantage that it informs clients of forks that are
receiving hashing power.
This could be linked to a protocol version to prevent disconnects due to
invalid header messages.
*Determining the longest chain*
Each link would get extra credit for headers received.
Assume there are 2 forks starting at block A as the fork point.
A(63) <- B(72) <- C(37) <- D(58)
and
A(63) <- B'(6) <- C'(9) <- D'(4) <- E(7) <- F(6)
The numbers in brackets are the number of low POW headers received that
have those blocks as parent.
The new rule is that the POW for a block is equal to
POW * (1 + (headers / 16))
Only headers within <some threshold> of the end of the (shorter) chain
count. However, in most cases, that doesn't matter since the fork point
will act as the start point. As long as miners keep headers for 30-40
blocks, they will likely have all headers back to any reasonable fork point.
This means that the top fork is considered longer, since it has much more
headers, even though it has 2 less blocks.
If 75% of the miners follow this rule, then the top fork will eventually
catch up and win, so it is in the interests of the other 25% to follow the
rule too.
Even if there isn't complete agreement on headers received, the fork that
is getting the most hashing will naturally gain most of the headers, so
ties will be broken quickly.
--047d7b6d80267dbeca04e22c127f
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div><div><div><div><div>I was thinking about a change to =
the rules for distinguishing between forks and maybe a BIP..<br><br></div><=
div><b>Summary</b><br></div><br></div><div>- Low POW headers should be broa=
dcast by the network<br>
<br></div><div>If a header has more than 1/64 of the POW of a block, it sho=
uld be broadcast.=A0 This provides information on which fork is getting mos=
t of the hashing power.<br><br></div><div>- Miners should use the header in=
formation to decide on longest chain<br>
<br></div>The fork selection rule for miners should be biased towards stayi=
ng on the fork that has the most hashing power.<br><br></div><div>This mean=
s that they might keep hashing on a fork that is 1-2 blocks shorter.<br>
<br>If most miners follow the rule, then it is the best strategy for other =
miners to also follow this rule.<br><br></div><div>- Advantages<br><br>This=
lowers the probability of natural and malicious reversals.<br></div><div>
<br></div><div><b>Distributing low POW headers</b><br></div><div><br>First =
block header messages that have more than 1/64 of the standard POW requirem=
ents would be forwarded.<br>
<br></div><div>This means the client needs to maintain a short term view of=
the entire header tree.<br><br></div><div>if (header extends header tree) =
{<br></div><div>=A0 if (header meets full POW) {<br></div><div>=A0=A0=A0 ad=
d to header tree;<br>
</div><div>=A0=A0=A0 forward to peers;<br></div><div>=A0=A0=A0 check if any=
blocks in storage now extend the header tree<br></div><div>=A0 } else {<br=
></div><div>=A0=A0=A0 if (header meets POW / 64) {<br></div><div>=A0=A0=A0=
=A0=A0 forward to peers;<br>
</div><div>=A0=A0=A0 }<br></div><div>} else {<br></div><div>=A0 if (header =
meets POW) {<br></div><div>=A0=A0=A0 add to orphan header storage<br></div>=
<div>=A0 }<br>}<br><br></div><div>The storage could be limited and headers =
could be discarded after a while.<br>
<br></div><div>This has the extra advantage that it informs clients of fork=
s that are receiving hashing power.<br><br></div><div>This could be linked =
to a protocol version to prevent disconnects due to invalid header messages=
.<br>
</div><div><br></div><div><b>Determining the longest chain</b><br></div><di=
v><br></div><div>Each link would get extra credit for headers received.<br>=
<br></div>Assume there are 2 forks starting at block A as the fork point.<b=
r>
</div><br><div>A(63) <- B(72) <- C(37) <- D(58)<br><br>and <br><br=
>A(63) <- B'(6) <- C'(9) <- D'(4) <- E(7) <- F(6=
)<br><br></div><div>The numbers in brackets are the number of low POW heade=
rs received that have those blocks as parent.<br>
<br></div><div>The new rule is that the POW for a block is equal to<br><br>=
</div><div>POW * (1 + (headers / 16))<br><br></div><div>Only headers within=
<some threshold> of the end of the (shorter) chain count.=A0 However=
, in most cases, that doesn't matter since the fork point will act as t=
he start point.=A0 As long as miners keep headers for 30-40 blocks, they wi=
ll likely have all headers back to any reasonable fork point.<br>
</div><br><div>This means that the top fork is considered longer, since it =
has much more headers, even though it has 2 less blocks.<br><br></div><div>=
If
75% of the miners follow this rule, then the top fork will eventually=20
catch up and win, so it is in the interests of the other 25% to follow=20
the rule too.<br>
<br></div>Even if there isn't complete agreement on headers=20
received, the fork that is getting the most hashing will naturally gain=20
most of the headers, so ties will be broken quickly.<br></div></div>
--047d7b6d80267dbeca04e22c127f--
|
