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 3407D959 for ; Tue, 3 Jan 2017 20:24:39 +0000 (UTC) X-Greylist: delayed 00:05:35 by SQLgrey-1.7.6 Received: from cock.li (cock.li [185.100.85.212]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5BBC3209 for ; Tue, 3 Jan 2017 20:24:38 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Spam-Level: X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU autolearn=ham version=3.3.1 MIME-Version: 1.0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cock.lu; s=mail; t=1483475075; bh=hG4jym2u7IDlqqcTUxDGQUyobe8afcg6YpXPUhCL8OU=; h=Date:From:To:Cc:Subject:In-Reply-To:References:From; b=lekT5vTM2TGqgkCQgrEiutqh3jPcTqo4fZevZiisqVJN4NhBPI7C5rgJqlcZ/9ODY RnnhTFbLTFr7BRDFexcvBa/A5LM4TPRlcGcvq/2vpNk7qorBRiLKvETAs53+jhYI09 B/N/R3TbBGlSWQVgJMXAEfCWEe99M3rJ9icItfdDqwhk2VneMiuoWU6W9jSI5AoqA5 mkj7ZN0jQWix+a6cDXsME7spl6dfO+Br9vmFgr5gmyRWjCZgDzvjZgZ5gHGWgWnTUb 3a4Sl1gu1Y2ItfPv9L0WNKLHH2YgCWHRaB3nek4eaFGNHP5qiJd5unBq0LBqJtXJRN DwwOUkeRaeSGA== Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit Date: Tue, 03 Jan 2017 12:24:35 -0800 From: bfd@cock.lu To: Bob McElrath In-Reply-To: <20160511202933.GR20063@mcelrath.org> References: <71d822e413ac457a530e1c367811cc24@cock.lu> <20160511200648.GQ20063@mcelrath.org> <20160511202933.GR20063@mcelrath.org> Message-ID: <019588aaf210830f55742bbc5db43ea3@cock.lu> X-Sender: bfd@cock.lu User-Agent: Roundcube Webmail/1.2.3 X-Mailman-Approved-At: Tue, 03 Jan 2017 20:40:07 +0000 Cc: Bitcoin Protocol Discussion 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: Tue, 03 Jan 2017 20:24:39 -0000 I believe the filter can be more compact than this, but even if not an order of magnitude saving of disk space is still significant. On 2016-05-11 13:29, Bob McElrath 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