From: Tier Nolan <tier.nolan@gmail•com>
Cc: Bitcoin Dev <bitcoin-development@lists•sourceforge.net>
Subject: Re: [Bitcoin-development] Proposed additional options for pruned nodes
Date: Tue, 12 May 2015 19:23:48 +0100 [thread overview]
Message-ID: <CAE-z3OV3VdSoiTSfASwYHr1CjZSqio303sqGq_1Y9yaYgov2sw@mail.gmail.com> (raw)
In-Reply-To: <20150512171640.GA32606@savin.petertodd.org>
[-- Attachment #1: Type: text/plain, Size: 2361 bytes --]
On Tue, May 12, 2015 at 6:16 PM, Peter Todd <pete@petertodd•org> 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.
[-- Attachment #2: Type: text/html, Size: 3273 bytes --]
next prev parent reply other threads:[~2015-05-12 18:23 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <CANJO25J1WRHtfQLVXUB2s_sjj39pTPWmixAcXNJ3t-5os8RPmQ@mail.gmail.com>
2015-05-12 15:26 ` gabe appleton
2015-05-12 16:05 ` Jeff Garzik
2015-05-12 16:56 ` gabe appleton
2015-05-12 17:16 ` Peter Todd
2015-05-12 18:23 ` Tier Nolan [this message]
2015-05-12 19:03 ` Gregory Maxwell
2015-05-12 19:24 ` gabe appleton
2015-05-12 19:38 ` Jeff Garzik
2015-05-12 19:43 ` gabe appleton
2015-05-12 21:30 ` [Bitcoin-development] [Bulk] " gb
2015-05-12 20:02 ` [Bitcoin-development] " Gregory Maxwell
2015-05-12 20:10 ` Jeff Garzik
2015-05-12 20:41 ` gabe appleton
2015-05-12 20:47 ` Gregory Maxwell
[not found] ` <CAFVoEQTdmCSRAy3u26q5oHdfvFEytZDBfQb_fs_qttK15fiRmg@mail.gmail.com>
[not found] ` <CAJHLa0OxxxiVd3JOp8SDvbF8dHj6KHdUNGb9L_GvTe93z3Z8mg@mail.gmail.com>
[not found] ` <CAJHLa0MYSpVBD4VE65LVbADb2daOvE=N83G8F_zDSHy3AQ5DAQ@mail.gmail.com>
2015-05-12 21:17 ` [Bitcoin-development] Fwd: " Adam Weiss
2015-05-12 22:00 ` [Bitcoin-development] " Tier Nolan
2015-05-12 22:09 ` gabe appleton
2015-05-13 5:19 ` Daniel Kraft
2015-05-13 9:34 ` Tier Nolan
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAE-z3OV3VdSoiTSfASwYHr1CjZSqio303sqGq_1Y9yaYgov2sw@mail.gmail.com \
--to=tier.nolan@gmail$(echo .)com \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox