Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1YsEqQ-0006ZQ-Hl for bitcoin-development@lists.sourceforge.net; Tue, 12 May 2015 18:23:54 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.220.170 as permitted sender) client-ip=209.85.220.170; envelope-from=tier.nolan@gmail.com; helo=mail-qk0-f170.google.com; Received: from mail-qk0-f170.google.com ([209.85.220.170]) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1YsEqP-0006hL-IA for bitcoin-development@lists.sourceforge.net; Tue, 12 May 2015 18:23:54 +0000 Received: by qkgy4 with SMTP id y4so11829430qkg.2 for ; Tue, 12 May 2015 11:23:48 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.55.15.15 with SMTP id z15mr3586886qkg.21.1431455028145; Tue, 12 May 2015 11:23:48 -0700 (PDT) Received: by 10.140.85.241 with HTTP; Tue, 12 May 2015 11:23:48 -0700 (PDT) In-Reply-To: <20150512171640.GA32606@savin.petertodd.org> References: <20150512171640.GA32606@savin.petertodd.org> Date: Tue, 12 May 2015 19:23:48 +0100 Message-ID: From: Tier Nolan Cc: Bitcoin Dev Content-Type: multipart/alternative; boundary=001a11475dda772c460515e6980e 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 X-Headers-End: 1YsEqP-0006hL-IA 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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 12 May 2015 18:23:54 -0000 --001a11475dda772c460515e6980e Content-Type: text/plain; charset=UTF-8 On Tue, May 12, 2015 at 6:16 PM, Peter Todd wrote: > > Lots of people are tossing around ideas for partial archival nodes that > would store a subset of blocks, such that collectively the whole > blockchain would be available even if no one node had the entire chain. > A compact way to describe which blocks are stored helps to mitigate against fingerprint attacks. It also means that a node could compactly indicate which blocks it stores with service bits. The node could pick two numbers W = window = a power of 2 P = position = random value less than W The node would store all blocks with a height of P mod W. The block hash could be used too. This has the nice feature that the node can throw away half of its data and still represent what is stored. W_new = W * 2 P_new = (random_bool()) ? P + W/2 : P; Half of the stored blocks would match P_new mod W_new and the other half could be deleted. This means that the store would use up between 50% and 100% of the allocated size. Another benefit is that it increases the probability that at least someone has every block. If N nodes each store 1% of the blocks, then the odds of a block being stored is pow(0.99, N). For 1000 nodes, that gives odds of 1 in 23,164 that a block will be missing. That means that around 13 out of 300,000 blocks would be missing. There would likely be more nodes than that, and also storage nodes, so it is not a major risk. If everyone is storing 1% of blocks, then they would set W to 128. As long as all of the 128 buckets is covered by some nodes, then all blocks are stored. With 1000 nodes, that gives odds of 0.6% that at least one bucket will be missed. That is better than around 13 blocks being missing. Nodes could inform peers of their W and P parameters on connection. The version message could be amended or a "getparams" message of some kind could be added. W could be encoded with 4 bits and P could be encoded with 16 bits, for 20 in total. W = 1 << bits[19:16] and P = bits[14:0]. That gives a maximum W of 32768, which is likely to many bits for P. Initial download would be harder, since new nodes would have to connect to at least 100 different nodes. They could download from random nodes, and just download the ones they are missing from storage nodes. Even storage nodes could have a range of W values. --001a11475dda772c460515e6980e Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On T= ue, May 12, 2015 at 6:16 PM, Peter Todd <pete@petertodd.org> wrote:

Lots of people are tossing around ideas for partial archival nodes t= hat
would store a subset of blocks, such that collectively the whole
blockchain would be available even if no one node had the entire chain.
=

A compact way to describe which blocks are= stored helps to mitigate against fingerprint attacks.

I= t also means that a node could compactly indicate which blocks it stores wi= th service bits.

The node could pic= k two numbers

W =3D window =3D a po= wer of 2
P =3D position =3D random valu= e less than W

The node would store = all blocks with a height of P mod W.=C2=A0 The block hash could be used too= .

This has the nice feature that th= e node can throw away half of its data and still represent what is stored.<= br>
W_new =3D W * 2
P_new =3D (random_bool()) ? P + W/2 : P;

Half of the stored blocks would match P_new mod W_ne= w and the other half could be deleted.=C2=A0 This means that the store woul= d use up between 50% and 100% of the allocated size.

Another benefit is that it increases the probability that= at least someone has every block.

= If N nodes each store 1% of the blocks, then the odds of a block being stor= ed is pow(0.99, N).=C2=A0 For 1000 nodes, that gives odds of 1 in 23,164 th= at a block will be missing.=C2=A0 That means that around 13 out of 300,000 = blocks would be missing.=C2=A0 There would likely be more nodes than that, = and also storage nodes, so it is not a major risk.

If everyone is storing 1% of blocks, then they would set W= to 128.=C2=A0 As long as all of the 128 buckets is covered by some nodes, = then all blocks are stored.=C2=A0 With 1000 nodes, that gives odds of 0.6% = that at least one bucket will be missed.=C2=A0 That is better than around 1= 3 blocks being missing.

Nodes could= inform peers of their W and P parameters on connection.=C2=A0 The version = message could be amended or a "getparams" message of some kind co= uld be added.

W could be encoded wi= th 4 bits and P could be encoded with 16 bits, for 20 in total.=C2=A0 W =3D= 1 << bits[19:16] and P =3D bits[14:0].=C2=A0 That gives a maximum W = of 32768, which is likely to many bits for P.

Initial download would be harder, since new nodes would have to = connect to at least 100 different nodes.=C2=A0 They could download from ran= dom nodes, and just download the ones they are missing from storage nodes.= =C2=A0 Even storage nodes could have a range of W values.
--001a11475dda772c460515e6980e--