Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 9E57171 for ; Thu, 28 Jul 2016 21:16:34 +0000 (UTC) X-Greylist: delayed 00:09:01 by SQLgrey-1.7.6 Received: from geekbox.info (geekbox.info [5.9.151.241]) by smtp1.linuxfoundation.org (Postfix) with ESMTP id 8561D193 for ; Thu, 28 Jul 2016 21:16:33 +0000 (UTC) Received: from [192.168.178.57] (ppp-83-171-168-238.dynamic.mnet-online.de [83.171.168.238]) (Authenticated sender: leo) by geekbox.info (Postfix) with ESMTPSA id C4BC8DE03C9 for ; Thu, 28 Jul 2016 23:07:30 +0200 (CEST) To: bitcoin-dev@lists.linuxfoundation.org References: <71d822e413ac457a530e1c367811cc24@cock.lu> <20160511200648.GQ20063@mcelrath.org> <20160511202933.GR20063@mcelrath.org> From: Leo Wandersleb Openpgp: id=FAE4D5168E9EF9F104AA1B2D6B9A1F0CB7C20812 X-Enigmail-Draft-Status: N1110 Message-ID: <307a1ca0-5554-a14e-fd3b-aace7d7c2233@LeoWandersleb.de> Date: Thu, 28 Jul 2016 23:07:29 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Icedove/45.1.0 MIME-Version: 1.0 In-Reply-To: <20160511202933.GR20063@mcelrath.org> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="rG9Xq5TKBKPiPVai09PRBRfpIl6eWTV11" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Sat, 30 Jul 2016 14:20:44 +0000 Subject: Re: [bitcoin-dev] Committed bloom filters for improved wallet performance and SPV security 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, 28 Jul 2016 21:16:34 -0000 This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --rG9Xq5TKBKPiPVai09PRBRfpIl6eWTV11 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable gmaxwell just made me aware of this mail thread [0]. Some days ago I had independently and naively started implementing "something similar" [1]. My version totally ignored the commitment and signing part but I'm pretty= sure that 12GB is overkill. My code is currently broken and I have no time to = work on it much but I thought it might be helpful to chime in. At this point in time the difference between 80GB and 3GB (as my current = 1.5GB of only outputs would suggest if I had covered the inputs) or even 12GB m= akes the difference of being able to store it on a phone, vs. not being able t= o. 80GB "compressed" to 3GB is not that bad at all. Unfortunately, with segWit th= is will be worse, with the higher transaction count per MB. Regards, Leo [0] https://www.reddit.com/r/Bitcoin/comments/4v28jl/how_have_fungiblity_prob= lems_affected_you_in/d5ux6aq [1] https://github.com/Giszmo/TransactionFinder On 05/11/2016 10:29 PM, Bob McElrath via bitcoin-dev wrote: > Eerrrr....let me revise that last paragraph. That's 12 *GB* of filters= at > today's block height (at fixed false-positive rate 1e-6. Compared to b= lock > headers only which are about 33 MB today. So this proposal is not real= ly > compatible with such a wallet being "light"... > > Damn units... > > Bob McElrath via bitcoin-dev [bitcoin-dev@lists.linuxfoundation.org] wr= ote: >> I like this idea, but let's run some numbers... >> >> bfd--- via bitcoin-dev [bitcoin-dev@lists.linuxfoundation.org] wrote: >>> A Bloom Filter Digest is deterministically created of every block >> Bloom filters completely obfuscate the required size of the filter for= a desired >> false-positive rate. But, an optimal filter is linear in the number o= f elements >> it contains for fixed false-positive rate, and logarithmic in the fals= e-positive >> rate. (This comment applies to a RLL encoded Bloom filter Greg mentio= ned, but >> that's not the only way) That is for N elements and false positive ra= te >> \epsilon: >> >> filter size =3D - N \log_2 \epsilon >> >> Given that the data that would be put into this particular filter is *= already* >> hashed, it makes more sense and is faster to use a Cuckoo[1] filter, c= hoosing a >> fixed false-positive rate, given expected wallet sizes. For Bloom fil= ters, >> multiply the above formula by 1.44. >> >> To prevent light clients from downloading more blocks than necessary, = the >> false-positive rate should be roughly less than 1/(block height). If = we take >> the false positive rate to be 1e-6 for today's block height ~ 410000, = this is >> about 20 bits per element. So for todays block's, this is a 30kb filt= er, for a >> 3% increase in block size, if blocks commit to the filter. Thus the r= equired >> size of the filter commitment is roughly: >> >> filter size =3D N \log_2 H >> >> where H is the block height. If bitcoin had these filters from the be= ginning, a >> light client today would have to download about 12MB of data in filter= s. My >> personal SPV wallet is using 31MB currently. It's not clear this is a= bandwidth >> win, though it's definitely a win for computing load on full nodes. >> >> >> [1] https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf >> >> -- >> Cheers, Bob McElrath >> >> "For every complex problem, there is a solution that is simple, neat, = and wrong." >> -- H. L. Mencken=20 >> >> >> >> !DSPAM:5733934b206851108912031! > > >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> >> >> !DSPAM:5733934b206851108912031! > -- > Cheers, Bob McElrath > > "For every complex problem, there is a solution that is simple, neat, a= nd wrong." > -- H. L. Mencken=20 > > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev --rG9Xq5TKBKPiPVai09PRBRfpIl6eWTV11 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQEcBAEBCAAGBQJXmnQRAAoJEGuaHwy3wggS/JkH+QH6dL+fy4iPVpc51vXI9DDO 1jwZXw5wYC8I5Vrkz/CRFdVtej0mod9mh6iDrvGGpvEhEK4wkJ2b+9H21l0d221P xKYNNu6gXH8hwCDzi+ybHLcJQEYX5LqsJOZQswSP41Ylhg3oThkhr8y13Hngyppf do5gJCdr7aoORXcSwoMdUUrFSh/wN2bED+8jEaKg/AkwFB2W6/EjS1FZCwtyqOOn /cmaBs3WzWqkGgua7nZta943Mrwn4jsN119GV7VuK5cGVAJVy4kB5FXDddeALZMV 5XQhdzDQYVak51YmwaQEOIt/7lV+fBy623oQ/6zKTo0OK/q7hU7aqDNUaRI7/Fk= =MNzI -----END PGP SIGNATURE----- --rG9Xq5TKBKPiPVai09PRBRfpIl6eWTV11--