path: root/8e/8393c98886b8e5146824285e859b41c895cf96

Return-Path: <earonesty@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 825BB955
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  6 Jan 2017 22:07:38 +0000 (UTC)
Received: by mail-wj0-f170.google.com with SMTP id i20so42871898wjn.2
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <erik@q32.com>
Date: Fri, 6 Jan 2017 17:07:36 -0500
X-Google-Sender-Auth: GBfN0zAunxreQHFYRwHjOU8KGUU
Message-ID: <CAJowKgLvZQxGqB6U5RiEizjkNXd1OYuTaRqXONTWTQ0VvX7FGA@mail.gmail.com>
To: Leo Wandersleb <leo@leowandersleb.de>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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

<div dir=3D"ltr"><div><div><div> - N \log_2 \epsilon * 1.44 <br><br>N =3D 4=
1000 blocks<br></div>epsilon =3D 1/41000 (fp rate)<br><br></div>=3D=20
  904689.8bits<br><br></div>~ 1 MB<br><br></div><div class=3D"gmail_extra">=
<br><div class=3D"gmail_quote">On Thu, Jul 28, 2016 at 5:07 PM, Leo Wanders=
leb via bitcoin-dev <span dir=3D"ltr">&lt;<a href=3D"mailto:bitcoin-dev@lis=
ts.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation=
.org</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">gmaxwell just =
made me aware of this mail thread [0]. Some days ago I had<br>
independently and naively started implementing &quot;something similar&quot=
; [1].<br>
<br>
My version totally ignored the commitment and signing part but I&#39;m pret=
ty sure<br>
that 12GB is overkill. My code is currently broken and I have no time to wo=
rk on<br>
it much but I thought it might be helpful to chime in.<br>
<br>
At this point in time the difference between 80GB and 3GB (as my current 1.=
5GB<br>
of only outputs would suggest if I had covered the inputs) or even 12GB mak=
es<br>
the difference of being able to store it on a phone, vs. not being able to.=
 80GB<br>
&quot;compressed&quot; to 3GB is not that bad at all. Unfortunately, with s=
egWit this will<br>
be worse, with the higher transaction count per MB.<br>
<br>
Regards,<br>
<br>
Leo<br>
<br>
[0]<br>
<a href=3D"https://www.reddit.com/r/Bitcoin/comments/4v28jl/how_have_fungib=
lity_problems_affected_you_in/d5ux6aq" rel=3D"noreferrer" target=3D"_blank"=
>https://www.reddit.com/r/<wbr>Bitcoin/comments/4v28jl/how_<wbr>have_fungib=
lity_problems_<wbr>affected_you_in/d5ux6aq</a><br>
[1] <a href=3D"https://github.com/Giszmo/TransactionFinder" rel=3D"noreferr=
er" target=3D"_blank">https://github.com/Giszmo/<wbr>TransactionFinder</a><=
br>
<br>
On 05/11/2016 10:29 PM, Bob McElrath via bitcoin-dev wrote:<br>
&gt; Eerrrr....let me revise that last paragraph.=C2=A0 That&#39;s 12 *GB* =
of filters at<br>
&gt; today&#39;s block height (at fixed false-positive rate 1e-6.=C2=A0 Com=
pared to block<br>
&gt; headers only which are about 33 MB today.=C2=A0 So this proposal is no=
t really<br>
&gt; compatible with such a wallet being &quot;light&quot;...<br>
&gt;<br>
&gt; Damn units...<br>
&gt;<br>
&gt; Bob McElrath via bitcoin-dev [<a href=3D"mailto:bitcoin-dev@lists.linu=
xfoundation.org">bitcoin-dev@lists.<wbr>linuxfoundation.org</a>] wrote:<br>
&gt;&gt; I like this idea, but let&#39;s run some numbers...<br>
&gt;&gt;<br>
&gt;&gt; bfd--- via bitcoin-dev [<a href=3D"mailto:bitcoin-dev@lists.linuxf=
oundation.org">bitcoin-dev@lists.<wbr>linuxfoundation.org</a>] wrote:<br>
&gt;&gt;&gt; A Bloom Filter Digest is deterministically created of every bl=
ock<br>
&gt;&gt; Bloom filters completely obfuscate the required size of the filter=
 for a desired<br>
&gt;&gt; false-positive rate.=C2=A0 But, an optimal filter is linear in the=
 number of elements<br>
&gt;&gt; it contains for fixed false-positive rate, and logarithmic in the =
false-positive<br>
&gt;&gt; rate.=C2=A0 (This comment applies to a RLL encoded Bloom filter Gr=
eg mentioned, but<br>
&gt;&gt; that&#39;s not the only way)=C2=A0 That is for N elements and fals=
e positive rate<br>
&gt;&gt; \epsilon:<br>
&gt;&gt;<br>
&gt;&gt;=C2=A0 =C2=A0 =C2=A0filter size =3D - N \log_2 \epsilon<br>
&gt;&gt;<br>
&gt;&gt; Given that the data that would be put into this particular filter =
is *already*<br>
&gt;&gt; hashed, it makes more sense and is faster to use a Cuckoo[1] filte=
r, choosing a<br>
&gt;&gt; fixed false-positive rate, given expected wallet sizes.=C2=A0 For =
Bloom filters,<br>
&gt;&gt; multiply the above formula by 1.44.<br>
&gt;&gt;<br>
&gt;&gt; To prevent light clients from downloading more blocks than necessa=
ry, the<br>
&gt;&gt; false-positive rate should be roughly less than 1/(block height).=
=C2=A0 If we take<br>
&gt;&gt; the false positive rate to be 1e-6 for today&#39;s block height ~ =
410000, this is<br>
&gt;&gt; about 20 bits per element.=C2=A0 So for todays block&#39;s, this i=
s a 30kb filter, for a<br>
&gt;&gt; 3% increase in block size, if blocks commit to the filter.=C2=A0 T=
hus the required<br>
&gt;&gt; size of the filter commitment is roughly:<br>
&gt;&gt;<br>
&gt;&gt;=C2=A0 =C2=A0 =C2=A0filter size =3D N \log_2 H<br>
&gt;&gt;<br>
&gt;&gt; where H is the block height.=C2=A0 If bitcoin had these filters fr=
om the beginning, a<br>
&gt;&gt; light client today would have to download about 12MB of data in fi=
lters.=C2=A0 My<br>
&gt;&gt; personal SPV wallet is using 31MB currently.=C2=A0 It&#39;s not cl=
ear this is a bandwidth<br>
&gt;&gt; win, though it&#39;s definitely a win for computing load on full n=
odes.<br>
&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt; [1] <a href=3D"https://www.cs.cmu.edu/~dga/papers/cuckoo-conext201=
4.pdf" rel=3D"noreferrer" target=3D"_blank">https://www.cs.cmu.edu/~dga/<wb=
r>papers/cuckoo-conext2014.pdf</a><br>
&gt;&gt;<br>
&gt;&gt; --<br>
&gt;&gt; Cheers, Bob McElrath<br>
&gt;&gt;<br>
&gt;&gt; &quot;For every complex problem, there is a solution that is simpl=
e, neat, and wrong.&quot;<br>
&gt;&gt;=C2=A0 =C2=A0 =C2=A0-- H. L. Mencken<br>
&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt; !DSPAM:<wbr>5733934b206851108912031!<br>
&gt;<br>
&gt;<br>
&gt;&gt; ______________________________<wbr>_________________<br>
&gt;&gt; bitcoin-dev mailing list<br>
&gt;&gt; <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-d=
ev@lists.<wbr>linuxfoundation.org</a><br>
&gt;&gt; <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitc=
oin-dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation=
.<wbr>org/mailman/listinfo/bitcoin-<wbr>dev</a><br>
&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt; !DSPAM:<wbr>5733934b206851108912031!<br>
<span class=3D"HOEnZb"><font color=3D"#888888">&gt; --<br>
&gt; Cheers, Bob McElrath<br>
&gt;<br>
&gt; &quot;For every complex problem, there is a solution that is simple, n=
eat, and wrong.&quot;<br>
&gt;=C2=A0 =C2=A0 =C2=A0-- H. L. Mencken<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt; ______________________________<wbr>_________________<br>
&gt; bitcoin-dev mailing list<br>
&gt; <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@l=
ists.<wbr>linuxfoundation.org</a><br>
&gt; <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-=
dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wb=
r>org/mailman/listinfo/bitcoin-<wbr>dev</a><br>
<br>
<br>
</font></span><br>______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
<br></blockquote></div><br></div>

--047d7b874de8df8e8e0545743ea1--