Date: Thu, 20 Apr 2017 20:32:12 +0000
From: Andrew Poelstra <apoelstra@wpsoftware.net>
To: Tom Zander <tomz@freedommail.ch>
Message-ID: <20170420203211.GR10783@boulet.lan>
References: <CAFVRnypbQQ-vsSLqv48cYaqTCty4R1DmFRqfAvxe4mAqyQNXxQ@mail.gmail.com>
	<19dbfef2-3791-8fe7-1c00-c4052c3d6c45@gmail.com>
	<CAFVRnyrQ3CMPW0=dtR-xnW1bF8cD9o5yvD67w25=w9wxVyJT9w@mail.gmail.com>
	<2652067.QRUcnb74ny@strawberry>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="0bZv59N4cPmzrjnk"
Content-Disposition: inline
In-Reply-To: <2652067.QRUcnb74ny@strawberry>
User-Agent: Mutt/1.7.1 (2016-10-04)
Cc: bitcoin-dev@lists.linuxfoundation.org
Subject: Re: [bitcoin-dev] Small Nodes: A Better Alternative to Pruned Nodes
Precedence: list


--0bZv59N4cPmzrjnk
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

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=20
> wrote:
> > > I suggested something similar which is a much simpler version;
> > > https://zander.github.io/scaling/Pruning/
>=20
> > 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.
>=20
> I don=E2=80=99t really see the problem here, even if your math is a off. =
(Statistics=20
> is difficult, I know). Connecting to many nodes to download faster is rea=
lly=20
> 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
=66rom 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.=20
>=20
> You make the assumption that this new mode of pruning will be used by 100=
%=20
> 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.
=20

--=20
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


--0bZv59N4cPmzrjnk
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQEcBAEBCAAGBQJY+RrJAAoJEMWI1jzkG5fBSZ4H/i2JkaWw0qKr0yFqNHlwcuMs
AUpW+EmQZLPmzyFkbCVZe/xzxfqeoCXoAqk7g5q/1stPGmI5n+wkzuvEsz+QiyQm
Ktqj8g4WFr48RzIHEupxh+bxrSTFa4pfCka2KG9LYk8u1thdytRdXXdiEC1317O6
OgKFX01KxYeGWK02BSWnjKQ5tvWK/kfbKuFGTy/aINxbv1n4Rz26bl8OU5Cj1n+u
cIypcMu+l5hh0ykdDIEMlqhWUK6m4PivR2KJF6Lkmgnh//XvcFWp9M3HRy9uPjiw
i5SSJ2mgkatXQ2ENSpJX+3KpBvcOUCyGG44zbZ5PWTkKIzD8Pvfn3VTZglE4vIk=
=lBWF
-----END PGP SIGNATURE-----

--0bZv59N4cPmzrjnk--