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
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
|
Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193]
helo=mx.sourceforge.net)
by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <tier.nolan@gmail.com>) id 1V1xfQ-0005Uo-I2
for bitcoin-development@lists.sourceforge.net;
Wed, 24 Jul 2013 11:55:40 +0000
Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.192.181 as permitted sender)
client-ip=209.85.192.181; envelope-from=tier.nolan@gmail.com;
helo=mail-pd0-f181.google.com;
Received: from mail-pd0-f181.google.com ([209.85.192.181])
by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1V1xfP-0001g3-Ap
for bitcoin-development@lists.sourceforge.net;
Wed, 24 Jul 2013 11:55:40 +0000
Received: by mail-pd0-f181.google.com with SMTP id 14so302348pdj.12
for <bitcoin-development@lists.sourceforge.net>;
Wed, 24 Jul 2013 04:55:33 -0700 (PDT)
MIME-Version: 1.0
X-Received: by 10.66.122.5 with SMTP id lo5mr42350808pab.175.1374666933456;
Wed, 24 Jul 2013 04:55:33 -0700 (PDT)
Received: by 10.70.78.232 with HTTP; Wed, 24 Jul 2013 04:55:33 -0700 (PDT)
In-Reply-To: <20130724094255.GB12568@savin>
References: <CAE-z3OX+Uzw_diW97yKWGzVMBFZHq2t+w15jNSdGMGqwyJ65yQ@mail.gmail.com>
<20130724094255.GB12568@savin>
Date: Wed, 24 Jul 2013 12:55:33 +0100
Message-ID: <CAE-z3OWBoMz6jC36Bp+dGqj6jHiWj1d1zGtH+iBbLcCt_6kNJw@mail.gmail.com>
From: Tier Nolan <tier.nolan@gmail.com>
Cc: bitcoin-development@lists.sourceforge.net
Content-Type: multipart/alternative; boundary=047d7b2e465440d2e304e24096ce
X-Spam-Score: 0.6 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/,
no trust [209.85.192.181 listed in list.dnswl.org]
-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.2 MISSING_HEADERS Missing To: header
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: 1V1xfP-0001g3-Ap
Subject: Re: [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: Wed, 24 Jul 2013 11:55:40 -0000
--047d7b2e465440d2e304e24096ce
Content-Type: text/plain; charset=ISO-8859-1
On Wed, Jul 24, 2013 at 10:42 AM, Peter Todd <pete@petertodd.org> wrote:
> Please provide equations and data justifying the 'magic constants' in
> this proposal.
>
The are a range of workable values. Ideally, there would first need to be
agreement on the general principle.
Distributing headers with 1/64 of the standard POW means that a header
would be broadcast approximately once every 9 seconds (assuming a 10 minute
block time). This was picked because sending 80 byte headers every 9
seconds shouldn't represent much load on the network.
The second magic number is how much credit to give for mini-headers.
Setting it at 1/16 means that the headers will be worth around 4 times as
much as a block (since there would be around 63 low POW headers for each
full POW one).
This creates an incentive for miners to take headers into account. If all
the headers were worth less than a full block, then a fork which was losing
would suddenly be winning if a block is found. A fork will only become the
main chain due to a new block, if it is within 16 mini-confirms.
Miners don't have to mine against the absolute best fork, but they do need
to make sure they stay within 16 of the best one (so if they find a block,
that block would be considered part of the main chain). Some hysteresis
might be helpful. The rule could be to only switch unless the current fork
is losing by at least 4 mini-confirms.
In most cases, this won't be a problem, since orphans don't happen that
often anyway.
Since it isn't a chain, this doesn't give the full benefits of a 9 second
block, but it should bring things to consensus faster. 6 full confirms
would be much more secure against random and hostile reversals.
It doesn't have the risks of 9 second blocks in causing network collapse,
since it isn't a chain, the headers are short, and there is no
confirmations of the required (other than checking the hash).
Each "mini" confirms adds to the strength of leaf blocks of the tree. If
there is a tie, and 20% of the network is mining one block and 80% is
mining the other, the mining power of the network will be split until the
next block arrives.
With mini confirms, the entire network is aware of the 2 blocks (since the
headers would be forwarded) and the mini-confirms would show which one has
majority hashing power.
The least risk option would be to make them purely advisory. The proposal
takes it further than that.
The proposal means that if the network is split 80/20, then miners should
stick with the 80% fork, even if the 20% fork wins the race for the next
block.
Winning a few rounds is easier than wining many rounds worth of
mini-confirms.
The key is that as long as the honest miners stay on the main chain, they
will eventually overwhelm any rewrite attack with less than 50% of the
mining power. This is a system to agree on what is the main chain in the
face of a re-write attack.
>
> Currently we do not relay blocks to peers if they conflict with blocks
> in the best known chain. What changes exactly are you proposing to that
> behavior?
>
The (sub) proposal is that headers would still be broadcast. The blocks
would not be forwarded.
If a header extends the header tree, meets full POW and is "near" the end
of the chain, then it is broadcast. This means that all nodes will have
the entire header tree, including orphans.
The full blocks would only be sent if they extend the main chain.
Second, if a header builds on a header that is in the header tree, then it
is broadcast, even if it doesn't meet full POW (only 1/64 required). This
gives information on which fork is getting the most power.
It gives information about potential "consensus loss" forks, where a
significant number of miners are following an alternative chain.
In fact, this is probably worth doing as an initial step.
A warning could be displayed on the client if a fork is getting more than
15% of the hashing power.
--047d7b2e465440d2e304e24096ce
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><br><div class=3D"gmail=
_quote">On Wed, Jul 24, 2013 at 10:42 AM, Peter Todd <span dir=3D"ltr"><=
<a href=3D"mailto:pete@petertodd.org" target=3D"_blank">pete@petertodd.org<=
/a>></span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div class=3D"im">
</div>Please provide equations and data justifying the 'magic constants=
' in<br>
this proposal.<br></blockquote><div><br></div><div>The are a range of worka=
ble values.=A0 Ideally, there would first need to be agreement on the gener=
al principle.<br><br></div><div>Distributing headers with 1/64 of the stand=
ard POW means that a header would be broadcast approximately once every 9 s=
econds (assuming a 10 minute block time).=A0 This was picked because sendin=
g 80 byte headers every 9 seconds shouldn't represent much load on the =
network.<br>
<br></div><div>The second magic number is how much credit to give for mini-=
headers.=A0 Setting it at 1/16 means that the headers will be worth around =
4 times as much as a block (since there would be around 63 low POW headers =
for each full POW one).=A0 <br>
<br>This creates an incentive for miners to take headers into account.=A0 I=
f all the headers were worth less than a full block, then a fork which was =
losing would suddenly be winning if a block is found.=A0 A fork will only b=
ecome the main chain due to a new block, if it is within 16 mini-confirms.<=
br>
<br></div><div>Miners don't have to mine against the absolute best fork=
, but they do need to make sure they stay within 16 of the best one (so if =
they find a block, that block would be considered part of the main chain).=
=A0 Some hysteresis might be helpful.=A0 The rule could be to only switch u=
nless the current fork is losing by at least 4 mini-confirms.<br>
<br></div><div>In most cases, this won't be a problem, since orphans do=
n't happen that often anyway.<br></div><div><br></div><div>Since it isn=
't a chain, this doesn't give the full benefits of a 9 second block=
, but it should bring things to consensus faster.=A0 6 full confirms would =
be much more secure against random and hostile reversals.<br>
<br>It doesn't have the risks of 9 second blocks in causing network col=
lapse, since it isn't a chain, the headers are short, and there is no c=
onfirmations of the required (other than checking the hash).<br><br>Each &q=
uot;mini" confirms adds to the strength of leaf blocks of the tree.=
=A0 If there is a tie, and 20% of the network is mining one block and 80% i=
s mining the other, the mining power of the network will be split until the=
next block arrives.<br>
<br>With mini confirms, the entire network is aware of the 2 blocks (since =
the headers would be forwarded) and the mini-confirms would show which one =
has majority hashing power.<br><br></div>The least risk option would be to =
make them purely advisory.=A0 The proposal takes it further than that.<br>
<br></div><div class=3D"gmail_quote">The proposal means that if the network=
is split 80/20, then miners should stick with the 80% fork, even if the 20=
% fork wins the race for the next block.<br><br></div><div class=3D"gmail_q=
uote">
Winning a few rounds is easier than wining many rounds worth of mini-confir=
ms.<br></div><div class=3D"gmail_quote"><br>The key is that as long as the =
honest miners stay on the main chain, they will eventually overwhelm any re=
write attack with less than 50% of the mining power.=A0 This is a system to=
agree on what is the main chain in the face of a re-write attack.<br>
</div><div class=3D"gmail_quote"><div>=A0</div><blockquote class=3D"gmail_q=
uote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1e=
x">
<br>
Currently we do not relay blocks to peers if they conflict with blocks<br>
in the best known chain. What changes exactly are you proposing to that<br>
behavior?<br></blockquote><div><br></div><div>The (sub) proposal is that he=
aders would still be broadcast.=A0 The blocks would not be forwarded.<br><b=
r></div><div>If a header extends the header tree, meets full POW and is &qu=
ot;near" the end of the chain, then it is broadcast.=A0 This means tha=
t all nodes will have the entire header tree, including orphans.<br>
<br></div><div>The full blocks would only be sent if they extend the main c=
hain.<br></div><div><br>Second, if a header builds on a header that is in t=
he header tree, then it is broadcast, even if it doesn't meet full POW =
(only 1/64 required).=A0 This gives information on which fork is getting th=
e most power.<br>
<br></div><div>It gives information about potential "consensus loss&qu=
ot; forks, where a significant number of miners are following an alternativ=
e chain.<br><br></div><div>In fact, this is probably worth doing as an init=
ial step.<br>
<br></div><div>A warning could be displayed on the client if a fork is gett=
ing more than 15% of the hashing power.<br></div></div></div></div>
--047d7b2e465440d2e304e24096ce--
|
