From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 67C6E95D for ; Thu, 20 Apr 2017 20:38:18 +0000 (UTC) X-Greylist: delayed 00:06:04 by SQLgrey-1.7.6 Received: from mail.wpsoftware.net (wpsoftware.net [96.53.77.134]) by smtp1.linuxfoundation.org (Postfix) with ESMTP id D64411BF for ; Thu, 20 Apr 2017 20:38:17 +0000 (UTC) Received: from boulet.lan (boulot.lan [192.168.0.193]) by mail.wpsoftware.net (Postfix) with ESMTPSA id 6849D40162; Thu, 20 Apr 2017 20:32:11 +0000 (UTC) Date: Thu, 20 Apr 2017 20:32:12 +0000 From: Andrew Poelstra To: Tom Zander Message-ID: <20170420203211.GR10783@boulet.lan> References: <19dbfef2-3791-8fe7-1c00-c4052c3d6c45@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) X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: bitcoin-dev@lists.linuxfoundation.org Subject: Re: [bitcoin-dev] Small Nodes: A Better Alternative to Pruned Nodes X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 20 Apr 2017 20:38:18 -0000 --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--