public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Andrew Poelstra <apoelstra@wpsoftware.net>
To: Tom Zander <tomz@freedommail.ch>
Cc: bitcoin-dev@lists.linuxfoundation.org
Subject: Re: [bitcoin-dev] Small Nodes: A Better Alternative to Pruned Nodes
Date: Thu, 20 Apr 2017 20:32:12 +0000	[thread overview]
Message-ID: <20170420203211.GR10783@boulet.lan> (raw)
In-Reply-To: <2652067.QRUcnb74ny@strawberry>

[-- Attachment #1: Type: text/plain, Size: 2433 bytes --]

On Thu, Apr 20, 2017 at 11:46:33AM +0200, Tom Zander via bitcoin-dev wrote:
> On Wednesday, 19 April 2017 19:30:30 CEST David Vorick via bitcoin-dev 
> wrote:
> > > I suggested something similar which is a much simpler version;
> > > https://zander.github.io/scaling/Pruning/
> 
> > Your proposal has a significant disadvantage: If every peer is dropping
> > 75% of all blocks randomly, then you need to connect to a large number of
> > peers to download the whole blockchain.
> ...
> > If you are downloading 450,000 blocks, you will need to
> > connect to an expected 46 peers to download the whole blockchain.
> 
> I don’t really see the problem here, even if your math is a off. (Statistics 
> is difficult, I know). Connecting to many nodes to download faster is really 
> not an issue and already happens.
>

I think the expected number of peers is actually ~47.75, which is pretty
close to David's estimate, which was wrong in a way that was actually
more favorable to the "everyone stores random blocks" scheme than the
truth.

Even assuming no archival nodes, and all nodes storing only one random
index between 5 and 255 inclusive, the chance of five arbitrary nodes
giving unique indices by chance is about 98.4%. To get the same probability
from a scheme where each peer has only 25% of the blocks, you need to
connect to 59.59 nodes.

This is over a ten-times increase in the number of nodes required to
download the entire chain, and requires participating nodes to use 25%
more space than David's proposal.

> > Your proposal is also a lot less able to handle active adversaries: if
> > nodes are randomly dropping blocks, the probability that one block in
> > particular is dropped by everyone goes up significantly. 
> 
> You make the assumption that this new mode of pruning will be used by 100% 
> of the network, this is not how distributed systems work.
>

Storing random but complete blocks requires the assumption this is _not_ the
case; David's does not make any assumptions. So on top of the performance
considerations there is this potential DoS vector.
 

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
       --Joanna Newsom


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

  reply	other threads:[~2017-04-20 20:38 UTC|newest]

Thread overview: 24+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-04-17  6:54 [bitcoin-dev] Small Nodes: A Better Alternative to Pruned Nodes David Vorick
2017-04-17  7:11 ` Danny Thorpe
2017-04-17  7:27   ` David Vorick
2017-04-20 15:50   ` Erik Aronesty
2017-04-20 23:42     ` Aymeric Vitte
2017-04-21 13:35   ` David Kaufman
2017-04-21 15:58     ` Leandro Coutinho
2017-04-17 10:14 ` Aymeric Vitte
2017-04-19 17:30   ` David Vorick
2017-04-20  9:46     ` Tom Zander
2017-04-20 20:32       ` Andrew Poelstra [this message]
2017-04-21  8:27         ` Tom Zander
2017-04-20 11:27     ` Aymeric Vitte
2017-04-18  7:43 ` Jonas Schnelli
2017-04-18 10:50 ` Tom Zander
2017-04-18 13:07   ` Tier Nolan
2017-04-18 23:19     ` Aymeric Vitte
2017-04-19  4:28       ` udevNull
2017-04-19 13:47         ` Angel Leon
2017-04-21 20:38 ` Gregory Maxwell
2017-04-23 16:27   ` Aymeric Vitte
2017-05-03 14:03   ` Erik Aronesty
2017-05-03 19:10     ` Natanael
2017-05-03 22:45       ` Aymeric Vitte

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=20170420203211.GR10783@boulet.lan \
    --to=apoelstra@wpsoftware.net \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=tomz@freedommail.ch \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
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