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 825BB955 for ; Fri, 6 Jan 2017 22:07:39 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wj0-f170.google.com (mail-wj0-f170.google.com [209.85.210.170]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5698F141 for ; Fri, 6 Jan 2017 22:07:38 +0000 (UTC) Received: by mail-wj0-f170.google.com with SMTP id i20so42871898wjn.2 for ; Fri, 06 Jan 2017 14:07:38 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to; bh=YetsFST9KXKjC7lu+T/da/8iy2qm2yeVeLWaPaWOvi8=; b=CuUQOhmJjZx3tnkjHUrODpthxMJCmJtE2iGyW0WMtpVsQAy4RFTVbx7DXTtccmNVGu 7WKe2npfAEnR6yBYI27xT5d4UCet7MQKTG95JSeDTN/SEWx/QVDA8mQJAnxF8M7x8Iwx HuCsRPL3r6ps1U544FWTTmGGCVVRcsCFYxHv/Axy1bOXLapOVKlbpqn5+kAm1pNhdhld Xbwf5B1WLJNw+iZS4CZ+SkM2RMWS0XNtVbUOIuq9GrdZQSFs3mWLehQ1+RZGwh0qDNuh Tj68bw/zMc8AsqG4lc1Ft2fNYYh289Suf8+9wNuiXKkbDBYPlcxsM7DpqS3Z3Od0/7Ch Xt7A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to; bh=YetsFST9KXKjC7lu+T/da/8iy2qm2yeVeLWaPaWOvi8=; b=lyx09MjWkaXYqTuq1O3x4s1GRivyERxWExDaPMm2+BrIMaReyqYec5YFKzH5NKUMX4 LB9CHtOsdDkuH+yIzvGu0Yn6skKN8hRxH1KbOPbPutcOvMbjkRj27gLbiTE5VK3nLhHu rtdhvf7jmQCupxzr2q3wW/2gorrNQ9yeScNQqN2V7mixo8tZESL0ITx3vRY13J2OYwFv vrIQQ5ITwcYECjDLUcA7+5uA1SlaHCFXslgf6tZvsgZzQvtM+yyuhkqUaUUjnhdry0P8 dR2qqEdc+ZBMy0WmY/yTLvjTXvTsMOByFB0Bge/9wrU11hWW9OL8189lSUVnjn/XwgVt H2sw== X-Gm-Message-State: AIkVDXIZMl6ntRyY8sVr6bKkysWx+SUhsTOJxwk1gcX5l1uU/zJo8FvGDKvN/UXB/Yd4agGO2sFBBcm7RGUSQQ== X-Received: by 10.195.11.41 with SMTP id ef9mr60370187wjd.89.1483740456912; Fri, 06 Jan 2017 14:07:36 -0800 (PST) MIME-Version: 1.0 Sender: earonesty@gmail.com Received: by 10.194.169.104 with HTTP; Fri, 6 Jan 2017 14:07:36 -0800 (PST) In-Reply-To: <307a1ca0-5554-a14e-fd3b-aace7d7c2233@LeoWandersleb.de> References: <71d822e413ac457a530e1c367811cc24@cock.lu> <20160511200648.GQ20063@mcelrath.org> <20160511202933.GR20063@mcelrath.org> <307a1ca0-5554-a14e-fd3b-aace7d7c2233@LeoWandersleb.de> From: Erik Aronesty Date: Fri, 6 Jan 2017 17:07:36 -0500 X-Google-Sender-Auth: GBfN0zAunxreQHFYRwHjOU8KGUU Message-ID: To: Leo Wandersleb , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary=047d7b874de8df8e8e0545743ea1 X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org 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: Fri, 06 Jan 2017 22:07:39 -0000 --047d7b874de8df8e8e0545743ea1 Content-Type: text/plain; charset=UTF-8 - N \log_2 \epsilon * 1.44 N = 41000 blocks epsilon = 1/41000 (fp rate) = 904689.8bits ~ 1 MB On Thu, Jul 28, 2016 at 5:07 PM, Leo Wandersleb via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > 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 > makes > the difference of being able to store it on a phone, vs. not being able > to. 80GB > "compressed" to 3GB is not that bad at all. Unfortunately, with segWit > this will > be worse, with the higher transaction count per MB. > > Regards, > > Leo > > [0] > https://www.reddit.com/r/Bitcoin/comments/4v28jl/how_ > have_fungiblity_problems_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 > block > > headers only which are about 33 MB today. So this proposal is not really > > compatible with such a wallet being "light"... > > > > Damn units... > > > > Bob McElrath via bitcoin-dev [bitcoin-dev@lists.linuxfoundation.org] > wrote: > >> 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 of > elements > >> it contains for fixed false-positive rate, and logarithmic in the > false-positive > >> rate. (This comment applies to a RLL encoded Bloom filter Greg > mentioned, but > >> that's not the only way) That is for N elements and false positive rate > >> \epsilon: > >> > >> filter size = - 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, > choosing a > >> fixed false-positive rate, given expected wallet sizes. For Bloom > filters, > >> 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 > filter, for a > >> 3% increase in block size, if blocks commit to the filter. Thus the > required > >> size of the filter commitment is roughly: > >> > >> filter size = N \log_2 H > >> > >> where H is the block height. If bitcoin had these filters from the > beginning, a > >> light client today would have to download about 12MB of data in > filters. 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 > >> > >> > >> > >> !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, > and wrong." > > -- H. L. Mencken > > > > > > > > _______________________________________________ > > bitcoin-dev mailing list > > bitcoin-dev@lists.linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > --047d7b874de8df8e8e0545743ea1 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
- N \log_2 \epsilon * 1.44

N =3D 4= 1000 blocks
epsilon =3D 1/41000 (fp rate)

=3D=20 904689.8bits

~ 1 MB

=
On Thu, Jul 28, 2016 at 5:07 PM, Leo Wanders= leb via bitcoin-dev <bitcoin-dev@lists.linuxfoundation= .org> wrote:
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 pret= ty sure
that 12GB is overkill. My code is currently broken and I have no time to wo= rk 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 mak= es
the difference of being able to store it on a phone, vs. not being able to.= 80GB
"compressed" to 3GB is not that bad at all. Unfortunately, with s= egWit this will
be worse, with the higher transaction count per MB.

Regards,

Leo

[0]
https://www.reddit.com/r/Bitcoin/comments/4v28jl/how_have_fungib= lity_problems_affected_you_in/d5ux6aq
[1] https://github.com/Giszmo/TransactionFinder<= br>
On 05/11/2016 10:29 PM, Bob McElrath via bitcoin-dev wrote:
> Eerrrr....let me revise that last paragraph.=C2=A0 That's 12 *GB* = of filters at
> today's block height (at fixed false-positive rate 1e-6.=C2=A0 Com= pared to block
> headers only which are about 33 MB today.=C2=A0 So this proposal is no= t really
> compatible with such a wallet being "light"...
>
> Damn units...
>
> Bob McElrath via bitcoin-dev [bitcoin-dev@lists.linuxfoundation.org] wrote:
>> 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 bl= ock
>> Bloom filters completely obfuscate the required size of the filter= for a desired
>> false-positive rate.=C2=A0 But, an optimal filter is linear in the= number of elements
>> it contains for fixed false-positive rate, and logarithmic in the = false-positive
>> rate.=C2=A0 (This comment applies to a RLL encoded Bloom filter Gr= eg mentioned, but
>> that's not the only way)=C2=A0 That is for N elements and fals= e positive rate
>> \epsilon:
>>
>>=C2=A0 =C2=A0 =C2=A0filter 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] filte= r, choosing a
>> fixed false-positive rate, given expected wallet sizes.=C2=A0 For = Bloom filters,
>> multiply the above formula by 1.44.
>>
>> To prevent light clients from downloading more blocks than necessa= ry, the
>> false-positive rate should be roughly less than 1/(block height).= =C2=A0 If we take
>> the false positive rate to be 1e-6 for today's block height ~ = 410000, this is
>> about 20 bits per element.=C2=A0 So for todays block's, this i= s a 30kb filter, for a
>> 3% increase in block size, if blocks commit to the filter.=C2=A0 T= hus the required
>> size of the filter commitment is roughly:
>>
>>=C2=A0 =C2=A0 =C2=A0filter size =3D N \log_2 H
>>
>> where H is the block height.=C2=A0 If bitcoin had these filters fr= om the beginning, a
>> light client today would have to download about 12MB of data in fi= lters.=C2=A0 My
>> personal SPV wallet is using 31MB currently.=C2=A0 It's not cl= ear this is a bandwidth
>> win, though it's definitely a win for computing load on full n= odes.
>>
>>
>> [1] https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
>>
>> --
>> Cheers, Bob McElrath
>>
>> "For every complex problem, there is a solution that is simpl= e, neat, and wrong."
>>=C2=A0 =C2=A0 =C2=A0-- H. L. Mencken
>>
>>
>>
>> !DSPAM:5733934b206851108912031!
>
>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-d= ev@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, n= eat, and wrong."
>=C2=A0 =C2=A0 =C2=A0-- H. L. Mencken
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@l= ists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev



_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev


--047d7b874de8df8e8e0545743ea1--