public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Olaoluwa Osuntokun <laolu32@gmail.com>
To: Riccardo Casatta <riccardo.casatta@gmail.com>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size
Date: Fri, 18 May 2018 20:08:29 -0700	[thread overview]
Message-ID: <CAO3Pvs_Ca6FKWw32hDSnuOGWLHAikNrdeopgS6L-FdXT6jn-AA@mail.gmail.com> (raw)
In-Reply-To: <CADabwBCKe6DaiBf_sjz9zyirkw8BdsDZnWSLEiAABEZvVDwj-Q@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 3509 bytes --]

Riccardo wrote:
> The BIP recall some go code for how the parameter has been selected which
> I can hardly understand and run

The code you're linking to is for generating test vectors (to allow
implementations to check the correctness of their gcs filters. The name of
the file is 'gentestvectors.go'. It produces CSV files which contain test
vectors of various testnet blocks and at various false positive rates.

> it's totally my fault but if possible I would really like more details on
> the process, like charts and explanations

When we published the BIP draft last year (wow, time flies!), we put up code
(as well as an interactive website) showing the process we used to arrive at
the current false positive rate. The aim was to minimize the bandwidth
required to download each filter plus the expected bandwidth from
downloading "large-ish" full segwit blocks. The code simulated a few wallet
types (in terms of number of addrs, etc) focusing on a "mid-sized" wallet.
One could also model the selection as a Bernoulli process where we attempt
to compute the probability that after k queries (let's say you have k
addresses) we have k "successes". A success would mean the queries item
wasn't found in the filter, while a failure is a filter match (false
positive or not). A failure in the process requires fetching the entire
block.

-- Laolu

On Fri, May 18, 2018 at 5:35 AM Riccardo Casatta via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Another parameter which heavily affects filter size is the false positive
> rate which is empirically set
> <https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki#construction>
> to 2^-20
> The BIP recall some go code
> <https://github.com/Roasbeef/bips/blob/83b83c78e189be898573e0bfe936dd0c9b99ecb9/gcs_light_client/gentestvectors.go>
> for how the parameter has been selected which I can hardly understand and
> run, it's totally my fault but if possible I would really like more details
> on the process, like charts and explanations (for example, which is the
> number of elements to search for which the filter has been optimized for?)
>
> Instinctively I feel 2^-20 is super low and choosing a lot higher alpha
> will shrink the total filter size by gigabytes at the cost of having to
> wastefully download just some megabytes of blocks.
>
>
> 2018-05-17 18:36 GMT+02:00 Gregory Maxwell via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org>:
>
>> On Thu, May 17, 2018 at 3:25 PM, Matt Corallo via bitcoin-dev
>> <bitcoin-dev@lists.linuxfoundation.org> wrote:
>> > I believe (1) could be skipped entirely - there is almost no reason why
>> > you'd not be able to filter for, eg, the set of output scripts in a
>> > transaction you know about
>>
>> I think this is convincing for the txids themselves.
>>
>> What about also making input prevouts filter based on the scriptpubkey
>> being _spent_?  Layering wise in the processing it's a bit ugly, but
>> if you validated the block you have the data needed.
>>
>> This would eliminate the multiple data type mixing entirely.
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>
>
>
> --
> Riccardo Casatta - @RCasatta <https://twitter.com/RCasatta>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 5342 bytes --]

  reply	other threads:[~2018-05-19  3:08 UTC|newest]

Thread overview: 60+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-05-17 15:25 [bitcoin-dev] BIP 158 Flexibility and Filter Size Matt Corallo
2018-05-17 15:43 ` Peter Todd
2018-05-17 15:46   ` Matt Corallo
2018-05-17 16:36 ` Gregory Maxwell
2018-05-17 16:59   ` Matt Corallo
2018-05-17 18:34     ` Gregory Maxwell
2018-05-17 18:34     ` Gregory Maxwell
2018-05-17 20:19       ` Jim Posen
2018-05-17 20:45         ` Gregory Maxwell
2018-05-17 21:27           ` Jim Posen
2018-05-19  3:12             ` Olaoluwa Osuntokun
2018-05-21  8:35               ` Johan Torås Halseth
2018-05-22  1:16                 ` Olaoluwa Osuntokun
2018-05-22  9:23                   ` Johan Torås Halseth
2018-05-23  0:42                     ` Jim Posen
2018-05-23  7:38                       ` Jim Posen
2018-05-23  8:16                         ` Johan Torås Halseth
2018-05-23 17:28                         ` Gregory Maxwell
2018-05-24  1:04                           ` Conner Fromknecht
2018-05-24  3:48                             ` Jim Posen
2018-05-28 18:18                               ` Tamas Blummer
2018-05-28 18:28                                 ` Tamas Blummer
2018-05-28 19:24                                   ` Gregory Maxwell
2018-05-29  2:42                                     ` Jim Posen
2018-05-29  3:24                                       ` Gregory Maxwell
2018-05-29  4:01                                       ` Olaoluwa Osuntokun
2018-05-31 14:27                                         ` Tamas Blummer
2018-06-01  2:52                                         ` Olaoluwa Osuntokun
2018-06-01  4:15                                           ` Gregory Maxwell
     [not found]                                           ` <CAAS2fgSyVi0d_ixp-auRPPzPfFeffN=hsWhWT5=EzDO3O+Ue1g@mail.gmail.com>
2018-06-02  0:01                                             ` Olaoluwa Osuntokun
2018-06-02  0:22                                               ` Gregory Maxwell
2018-06-02  2:02                                                 ` Jim Posen
2018-06-02 12:41                                                   ` David A. Harding
2018-06-02 22:02                                                     ` Tamas Blummer
2018-06-03  0:28                                                       ` Gregory Maxwell
2018-06-03  5:14                                                         ` Tamas Blummer
2018-06-03  6:11                                                           ` Pieter Wuille
2018-06-03 16:44                                                             ` Tamas Blummer
2018-06-03 16:50                                                               ` Tamas Blummer
2018-06-08  5:03                                                             ` Olaoluwa Osuntokun
2018-06-08 16:14                                                               ` Gregory Maxwell
2018-06-08 23:35                                                                 ` Olaoluwa Osuntokun
2018-06-09 10:34                                                                   ` David A. Harding
2018-06-12 23:51                                                                     ` Olaoluwa Osuntokun
2018-06-09 15:45                                                                   ` Gregory Maxwell
2018-06-12 23:58                                                                     ` Olaoluwa Osuntokun
2018-05-18  8:46   ` Riccardo Casatta
2018-05-19  3:08     ` Olaoluwa Osuntokun [this message]
2018-05-19  2:57   ` Olaoluwa Osuntokun
2018-05-19  3:06     ` Pieter Wuille
2018-05-22  1:15       ` Olaoluwa Osuntokun
2018-05-18  6:28 ` Karl-Johan Alm
2018-06-04  8:42   ` Riccardo Casatta
2018-06-05  1:08     ` Jim Posen
2018-06-05  4:33       ` Karl-Johan Alm
2018-06-05 17:22         ` Jim Posen
2018-06-05 17:52       ` Gregory Maxwell
2018-06-06  1:12     ` Olaoluwa Osuntokun
2018-06-06 15:14       ` Riccardo Casatta
2018-05-19  2:51 ` Olaoluwa Osuntokun

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CAO3Pvs_Ca6FKWw32hDSnuOGWLHAikNrdeopgS6L-FdXT6jn-AA@mail.gmail.com \
    --to=laolu32@gmail.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=riccardo.casatta@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox