{"type":"rich","version":"1.0","author_name":"npub19helcfnqgk2jrwzjex2aflq6jwfc8zd9uzzkwlgwhve7lykv23mq5zkvn4","author_url":"https://nostr.ae/npub19helcfnqgk2jrwzjex2aflq6jwfc8zd9uzzkwlgwhve7lykv23mq5zkvn4","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2018-05-19\n📝 Original message:Riccardo wrote:\n\u003e The BIP recall some go code for how the parameter has been selected which\n\u003e I can hardly understand and run\n\nThe code you're linking to is for generating test vectors (to allow\nimplementations to check the correctness of their gcs filters. The name of\nthe file is 'gentestvectors.go'. It produces CSV files which contain test\nvectors of various testnet blocks and at various false positive rates.\n\n\u003e it's totally my fault but if possible I would really like more details on\n\u003e the process, like charts and explanations\n\nWhen we published the BIP draft last year (wow, time flies!), we put up code\n(as well as an interactive website) showing the process we used to arrive at\nthe current false positive rate. The aim was to minimize the bandwidth\nrequired to download each filter plus the expected bandwidth from\ndownloading \"large-ish\" full segwit blocks. The code simulated a few wallet\ntypes (in terms of number of addrs, etc) focusing on a \"mid-sized\" wallet.\nOne could also model the selection as a Bernoulli process where we attempt\nto compute the probability that after k queries (let's say you have k\naddresses) we have k \"successes\". A success would mean the queries item\nwasn't found in the filter, while a failure is a filter match (false\npositive or not). A failure in the process requires fetching the entire\nblock.\n\n-- Laolu\n\nOn Fri, May 18, 2018 at 5:35 AM Riccardo Casatta via bitcoin-dev \u003c\nbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\n\u003e Another parameter which heavily affects filter size is the false positive\n\u003e rate which is empirically set\n\u003e \u003chttps://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki#construction\u003e\n\u003e to 2^-20\n\u003e The BIP recall some go code\n\u003e \u003chttps://github.com/Roasbeef/bips/blob/83b83c78e189be898573e0bfe936dd0c9b99ecb9/gcs_light_client/gentestvectors.go\u003e\n\u003e for how the parameter has been selected which I can hardly understand and\n\u003e run, it's totally my fault but if possible I would really like more details\n\u003e on the process, like charts and explanations (for example, which is the\n\u003e number of elements to search for which the filter has been optimized for?)\n\u003e\n\u003e Instinctively I feel 2^-20 is super low and choosing a lot higher alpha\n\u003e will shrink the total filter size by gigabytes at the cost of having to\n\u003e wastefully download just some megabytes of blocks.\n\u003e\n\u003e\n\u003e 2018-05-17 18:36 GMT+02:00 Gregory Maxwell via bitcoin-dev \u003c\n\u003e bitcoin-dev at lists.linuxfoundation.org\u003e:\n\u003e\n\u003e\u003e On Thu, May 17, 2018 at 3:25 PM, Matt Corallo via bitcoin-dev\n\u003e\u003e \u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\u003e \u003e I believe (1) could be skipped entirely - there is almost no reason why\n\u003e\u003e \u003e you'd not be able to filter for, eg, the set of output scripts in a\n\u003e\u003e \u003e transaction you know about\n\u003e\u003e\n\u003e\u003e I think this is convincing for the txids themselves.\n\u003e\u003e\n\u003e\u003e What about also making input prevouts filter based on the scriptpubkey\n\u003e\u003e being _spent_?  Layering wise in the processing it's a bit ugly, but\n\u003e\u003e if you validated the block you have the data needed.\n\u003e\u003e\n\u003e\u003e This would eliminate the multiple data type mixing entirely.\n\u003e\u003e _______________________________________________\n\u003e\u003e bitcoin-dev mailing list\n\u003e\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\u003e\n\u003e\n\u003e\n\u003e\n\u003e --\n\u003e Riccardo Casatta - @RCasatta \u003chttps://twitter.com/RCasatta\u003e\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180518/b40519c4/attachment.html\u003e"}