Subject: Re: [bitcoin-dev] Small Nodes: A Better Alternative to Pruned Nodes

From: Andrew Poelstra <[email-masked]>
Date: Thu, 20 Apr 2017 20:32:12 +0000

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