1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
helo=mx.sourceforge.net)
by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <pieter.wuille@gmail.com>) id 1VAhI2-00044F-7p
for bitcoin-development@lists.sourceforge.net;
Sat, 17 Aug 2013 14:15:38 +0000
Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.128.48 as permitted sender)
client-ip=209.85.128.48; envelope-from=pieter.wuille@gmail.com;
helo=mail-qe0-f48.google.com;
Received: from mail-qe0-f48.google.com ([209.85.128.48])
by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1VAhI1-0000Z6-AI
for bitcoin-development@lists.sourceforge.net;
Sat, 17 Aug 2013 14:15:38 +0000
Received: by mail-qe0-f48.google.com with SMTP id 3so87763qea.21
for <bitcoin-development@lists.sourceforge.net>;
Sat, 17 Aug 2013 07:15:31 -0700 (PDT)
MIME-Version: 1.0
X-Received: by 10.224.54.210 with SMTP id r18mr3483836qag.62.1376748931797;
Sat, 17 Aug 2013 07:15:31 -0700 (PDT)
Received: by 10.49.96.165 with HTTP; Sat, 17 Aug 2013 07:15:31 -0700 (PDT)
Received: by 10.49.96.165 with HTTP; Sat, 17 Aug 2013 07:15:31 -0700 (PDT)
In-Reply-To: <CAJHLa0PfHa9Xinv0rdGUK8PRxR5NMC6h2an2ZGgCaTi_DpFrfQ@mail.gmail.com>
References: <CAJHLa0PfHa9Xinv0rdGUK8PRxR5NMC6h2an2ZGgCaTi_DpFrfQ@mail.gmail.com>
Date: Sat, 17 Aug 2013 16:15:31 +0200
Message-ID: <CAPg+sBhHmXx_qV7i-9rSBHsV7U7AET7b+FXecRuROMF=R2UJhA@mail.gmail.com>
From: Pieter Wuille <pieter.wuille@gmail.com>
To: Jeff Garzik <jgarzik@bitpay.com>
Content-Type: multipart/alternative; boundary=089e01537274065b7b04e425579c
X-Spam-Score: -0.6 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(pieter.wuille[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
1.0 HTML_MESSAGE BODY: HTML included in message
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
author's domain
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1VAhI1-0000Z6-AI
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Combining bloom filters?
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Sat, 17 Aug 2013 14:15:38 -0000
--089e01537274065b7b04e425579c
Content-Type: text/plain; charset=ISO-8859-1
If both constructed bloom filters use the same seed and the same number of
hash functions, yes. Assuming the input filters were optimal for a given FP
rate, the resulting filter will be worse.
--
Pieter
On 17 Aug 2013 16:01, "Jeff Garzik" <jgarzik@bitpay.com> wrote:
> Consider wallet A builds bloom filter A' and wallet B builds bloom
> filter B'. Can A' and B' be or'd together to form a single bloom
> filter C' ?
>
> --
> Jeff Garzik
> Senior Software Engineer and open source evangelist
> BitPay, Inc. https://bitpay.com/
>
>
> ------------------------------------------------------------------------------
> Get 100% visibility into Java/.NET code with AppDynamics Lite!
> It's a free troubleshooting tool designed for production.
> Get down to code-level detail for bottlenecks, with <2% overhead.
> Download for free and get started troubleshooting in minutes.
> http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
--089e01537274065b7b04e425579c
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<p dir=3D"ltr">If both constructed bloom filters use the same seed and the =
same number of hash functions, yes. Assuming the input filters were optimal=
for a given FP rate, the resulting filter will be worse.</p>
<p dir=3D"ltr">-- <br>
Pieter<br>
</p>
<div class=3D"gmail_quote">On 17 Aug 2013 16:01, "Jeff Garzik" &l=
t;<a href=3D"mailto:jgarzik@bitpay.com">jgarzik@bitpay.com</a>> wrote:<b=
r type=3D"attribution"><blockquote class=3D"gmail_quote" style=3D"margin:0 =
0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Consider wallet A builds bloom filter A' and wallet B builds bloom<br>
filter B'. =A0Can A' and B' be or'd together to form a sing=
le bloom<br>
filter C' ?<br>
<br>
--<br>
Jeff Garzik<br>
Senior Software Engineer and open source evangelist<br>
BitPay, Inc. =A0 =A0 =A0<a href=3D"https://bitpay.com/" target=3D"_blank">h=
ttps://bitpay.com/</a><br>
<br>
---------------------------------------------------------------------------=
---<br>
Get 100% visibility into Java/.NET code with AppDynamics Lite!<br>
It's a free troubleshooting tool designed for production.<br>
Get down to code-level detail for bottlenecks, with <2% overhead.<br>
Download for free and get started troubleshooting in minutes.<br>
<a href=3D"http://pubads.g.doubleclick.net/gampad/clk?id=3D48897031&iu=
=3D/4140/ostg.clktrk" target=3D"_blank">http://pubads.g.doubleclick.net/gam=
pad/clk?id=3D48897031&iu=3D/4140/ostg.clktrk</a><br>
_______________________________________________<br>
Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-develo=
pment@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
</blockquote></div>
--089e01537274065b7b04e425579c--
|