summaryrefslogtreecommitdiff
path: root/7c/eb0eb3a878291393ba755434d5736f49740b45
blob: 995e75b9515b27dfa12f335d2fbc3fdc48fde4f6 (plain)
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
Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193]
	helo=mx.sourceforge.net)
	by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <tier.nolan@gmail.com>) id 1YsT3J-0007zx-Rt
	for bitcoin-development@lists.sourceforge.net;
	Wed, 13 May 2015 09:34:09 +0000
Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.216.182 as permitted sender)
	client-ip=209.85.216.182; envelope-from=tier.nolan@gmail.com;
	helo=mail-qc0-f182.google.com; 
Received: from mail-qc0-f182.google.com ([209.85.216.182])
	by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
	(Exim 4.76) id 1YsT3I-0004cv-SD
	for bitcoin-development@lists.sourceforge.net;
	Wed, 13 May 2015 09:34:09 +0000
Received: by qcvo8 with SMTP id o8so19199254qcv.0
	for <bitcoin-development@lists.sourceforge.net>;
	Wed, 13 May 2015 02:34:03 -0700 (PDT)
MIME-Version: 1.0
X-Received: by 10.140.217.17 with SMTP id n17mr26626047qhb.69.1431509643480;
	Wed, 13 May 2015 02:34:03 -0700 (PDT)
Received: by 10.140.85.241 with HTTP; Wed, 13 May 2015 02:34:03 -0700 (PDT)
In-Reply-To: <5552DEFA.4080508@domob.eu>
References: <CANJO25J1WRHtfQLVXUB2s_sjj39pTPWmixAcXNJ3t-5os8RPmQ@mail.gmail.com>
	<CANJO25JTtfmfsOQYOzJeksJn3CoKE3W8iLGsRko-_xd4XhB3ZA@mail.gmail.com>
	<CAJHLa0O5OxaX5g3u=dnCY6Lz_gK3QZgQEPNcWNVRD4JziwAmvg@mail.gmail.com>
	<20150512171640.GA32606@savin.petertodd.org>
	<CAE-z3OV3VdSoiTSfASwYHr1CjZSqio303sqGq_1Y9yaYgov2sw@mail.gmail.com>
	<CAAS2fgRzGkcJbWbJmFN2-NSJGUcLdPKp0q7FjM0x7WDvHoRq=g@mail.gmail.com>
	<5552DEFA.4080508@domob.eu>
Date: Wed, 13 May 2015 10:34:03 +0100
Message-ID: <CAE-z3OWiurTt=QqjeL+KN-7AdKKgW2tJc_Yu-eMzoM-GUZ=fAg@mail.gmail.com>
From: Tier Nolan <tier.nolan@gmail.com>
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Content-Type: multipart/alternative; boundary=001a1139b816caea950515f34f6e
X-Spam-Score: 2.5 (++)
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.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
	1.9 MALFORMED_FREEMAIL Bad headers on message from free email service
	0.0 AWL AWL: Adjusted score from AWL reputation of From: address
X-Headers-End: 1YsT3I-0004cv-SD
Subject: Re: [Bitcoin-development] Proposed additional options for pruned
	nodes
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, 13 May 2015 09:34:09 -0000

--001a1139b816caea950515f34f6e
Content-Type: text/plain; charset=UTF-8

On Wed, May 13, 2015 at 6:19 AM, Daniel Kraft <d@domob.eu> wrote:

> 2) Divide the range of all blocks into intervals with exponentially
> growing size.  I. e., something like this:
>
> 1, 1, 2, 2, 4, 4, 8, 8, 16, 16, ...
>

Interesting.  This can be combined with the system I suggested.

A node broadcasts 3 pieces of information

Seed (16 bits): This is the seed
M_bits_lsb (1 bit):  Used to indicate M during a transition
N (7 bits):  This is the count of the last range held (or partially held)

M = 1 << M_bits

M should be set to the lowest power of 2 greater than double the block
chain height

That gives M = 1 million at the moment.  During changing M, some nodes will
be using the higher M and others will use the lower M.

The M_bits_lsb field allows those to be distinguished.

As the block height approaches 512k, nodes can begin to upgrade.  For a
period around block 512k, some nodes could use M = 1 million and others
could use M = 2 million.

Assuming M is around 3 times higher than the block height, then the odds of
a start being less than the block height is around 35%.  If they runs by
25% each step, then that is approx a double for each hit.

Size(n) = ((4 + (n & 0x3)) << (n >> 2)) * 2.5MB

This gives an exponential increase, but groups of 4 are linearly
interpolated.


*Size(0) = 10 MB*
Size(1) = 12.5MB
Size(2) = 15 MB
Size(3) = 17.5MB
Size(4) = 20MB

*Size(5) = 25MB*
Size(6) = 30MB
Size(7) = 35MB

*Size(8) = 40MB*

Start(n) = Hash(seed + n) mod M

A node should store as much of its last start as possible.  Assuming start
0, 5, and 8 were "hits" but the node had a max size of 60MB.  It can store
0 and 5 and have 25MB left.  That isn't enough to store all of run 8, but
it should store 25MB of the blocks in run 8 anyway.

Size(255) = pow(2, 31) * 17.5MB = 35,840 TB

Decreasing N only causes previously accepted runs to be invalidated.

When a node approaches a transition point for N, it would select a block
height within 25,000 of the transition point.  Once it reaches that block,
it will begin downloading the new runs that it needs.  When updating, it
can set N to zero.  This spreads out the upgrade (over around a year), with
only a small number of nodes upgrading at any time.

New nodes should use the higher M, if near a transition point (say within
100,000).

--001a1139b816caea950515f34f6e
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On W=
ed, May 13, 2015 at 6:19 AM, Daniel Kraft <span dir=3D"ltr">&lt;<a href=3D"=
mailto:d@domob.eu" target=3D"_blank">d@domob.eu</a>&gt;</span> wrote:<br><b=
lockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-le=
ft:1px solid rgb(204,204,204);padding-left:1ex">
2) Divide the range of all blocks into intervals with exponentially<br>
growing size.=C2=A0 I. e., something like this:<br>
<br>
1, 1, 2, 2, 4, 4, 8, 8, 16, 16, ...<br></blockquote><div><br></div><div>Int=
eresting.=C2=A0 This can be combined with the system I suggested.<br><br></=
div><div>A node broadcasts 3 pieces of information<br><br></div>Seed (16 bi=
ts): This is the seed<br><div>M_bits_lsb (1 bit):=C2=A0 Used to indicate M =
during a transition<br>N (7 bits):=C2=A0 This is the count of the last rang=
e held (or partially held)<br></div><div><br></div><div></div><div></div><d=
iv>M =3D 1 &lt;&lt; M_bits<br></div><div><br>M should be set to the lowest =
power of 2 greater than double the block chain height<br><br></div><div>Tha=
t gives M =3D 1 million at the moment.=C2=A0 During changing M, some nodes =
will be using the higher M and others will use the lower M.<br><br></div><d=
iv>The M_bits_lsb field allows those to be distinguished.<br><br></div><div=
>As the block height approaches 512k, nodes can begin to upgrade.=C2=A0 For=
 a period around block 512k, some nodes could use M =3D 1 million and other=
s could use M =3D 2 million.<br></div><div><br></div><div>Assuming M is aro=
und 3 times higher than the block height, then the odds of a start being le=
ss than the block height is around 35%.=C2=A0 If they runs by 25% each step=
, then that is approx a double for each hit.<br><br></div><div></div><div>S=
ize(n) =3D ((4 + (n &amp; 0x3)) &lt;&lt; (n &gt;&gt; 2)) * 2.5MB<br><br></d=
iv><div>This gives an exponential increase, but groups of 4 are linearly in=
terpolated.<br></div><div><br><b>Size(0) =3D 10 MB<br></b></div><div>Size(1=
) =3D 12.5MB<br></div><div>Size(2) =3D 15 MB<br></div><div>Size(3) =3D 17.5=
MB<br></div><div>Size(4) =3D 20MB<br></div><div><b>Size(5) =3D 25MB<br></b>=
</div><div>Size(6) =3D 30MB<br></div><div>Size(7) =3D 35MB<br></div><div><b=
>Size(8) =3D 40MB<br></b></div><div><br></div><div>Start(n) =3D Hash(seed +=
 n) mod M <br><br></div><div>A node should store as much of its last start =
as possible.=C2=A0 Assuming start 0, 5, and 8 were &quot;hits&quot; but the=
 node had a max size of 60MB.=C2=A0 It can store 0 and 5 and have 25MB left=
.=C2=A0 That isn&#39;t enough to store all of run 8, but it should store 25=
MB of the blocks in run 8 anyway.<br><br></div><div>Size(255) =3D pow(2, 31=
) * 17.5MB =3D 35,840 TB<br><br></div><div>Decreasing N only causes previou=
sly accepted runs to be invalidated.=C2=A0 <br><br></div><div>When a node a=
pproaches a transition point for N, it would select a block height within 2=
5,000 of the transition point.=C2=A0 Once it reaches that block, it will be=
gin downloading the new runs that it needs.=C2=A0 When updating, it can set=
 N to zero.=C2=A0 This spreads out the upgrade (over around a year), with o=
nly a small number of nodes upgrading at any time.=C2=A0 <br><br></div><div=
>New nodes should use the higher M, if near a transition point (say within =
100,000).<br></div></div></div></div>

--001a1139b816caea950515f34f6e--