📅 Original date posted:2019-09-21
📝 Original message:Hi Aleksey,
Yes, BIP158 uses the block hash to seed the hash function, which makes distinct block filters non-aggregatable
for common values. Aggregate fiters on ranges of blocks would have to use some other seed and then
achive significant savings using the same design.
I think that the most likely use of filters is to decide if a newly announced block should be downloaded and
not scanning over the entire chain, where aggregate filters would help. I also suspect that whole chain
scans would be better served with plain sequential reads in map-reduce style.
Typical clients do not care of filters for blocks before the birth date of their wallet’s keys, so they skip over the
majority of history which is a bigger saving than any aggregate filter.
I wish we get a filter committed as commitment would unlock more utility than any marginal savings through
more elaborate design.
Tamas Blummer
> On Sep 19, 2019, at 19:20, admin--- via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Hello list,
>
> Here is a link for a draft of a BIP for compact probabilistic block filters alternative of BIP 158
>
> https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSxv80ik/edit?usp=sharing <https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSxv80ik/edit?usp=sharing>;
>
> Summary:
>
> - BIP 158 false positive rate is low, we can achieve lower bandwidth with higher false positive rate filter while sync blockchain
>
> - BIP 158 not do not support filter batching by design of used parameters for siphash and Golomb coding optimal parameters
>
> - Alternative compression with delta coding and splitting data to 2 bit string sequences. First for data without prefixes, second one for information about bit length written to first sequence.
> Second sequence have a lot of duplicates, compressed with 2 round of Huffman algorithm. (Effectivity about 98% vs Golomb with optimal parameters)
>
> - Block filters batching reduce filter size significantly
>
> - Separation of filters by address type allows lite client not to download redundant information without compromising privacy.
>
> - Lite client filters download strategy: get biggest filter (smallest blocks/size rate) for blocks range, in case positive test -> get medium filters to reduce blocks range -> get block filters for affected range -> download affected blocks over TOR
>
> Implementation (python): https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.py#L172 <https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.py#L172>;
>
> Exactly information from mainnet about size for separated filters by address types and batch size will be added within few days.
>
> Thanks for any feedback.
> Aleksey Karpov
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20190921/ecea43cc/attachment.html>;
Tamas Blummer [ARCHIVE] /
npub1cc…ex8m8
2023-06-07 18:20:41
in reply to nevent1q…xz7r
Author Public Key
npub1ccegg9n9lnx6huppxg43m95488yur7pfemkn3pz0agjws5ffvtts0ex8m8Published at
2023-06-07 18:20:41Event JSON
{
"id": "dc882b5e422efb463307309eaec0ff46fca39145cb38a7e33fa3d0e6f061a4a9",
"pubkey": "c632841665fccdabf021322b1d969539c9c1f829ceed38844fea24e8512962d7",
"created_at": 1686162041,
"kind": 1,
"tags": [
[
"e",
"adc7deac287f85c5a689bc3f11dfaf4f1072526bb31216e9967281d380cbb379",
"",
"root"
],
[
"e",
"b92d8ff498ed3e2068525a8c5c3acd3e4a87e1423ffa71ebe0c4c09c47882c55",
"",
"reply"
],
[
"p",
"02356003e4b2742aa27d4e06103f6ed596a7dcd0b024321a6c15d2c57c8bfc0c"
]
],
"content": "📅 Original date posted:2019-09-21\n📝 Original message:Hi Aleksey,\n\nYes, BIP158 uses the block hash to seed the hash function, which makes distinct block filters non-aggregatable \nfor common values. Aggregate fiters on ranges of blocks would have to use some other seed and then \nachive significant savings using the same design.\n\nI think that the most likely use of filters is to decide if a newly announced block should be downloaded and \nnot scanning over the entire chain, where aggregate filters would help. I also suspect that whole chain \nscans would be better served with plain sequential reads in map-reduce style.\n\nTypical clients do not care of filters for blocks before the birth date of their wallet’s keys, so they skip over the \nmajority of history which is a bigger saving than any aggregate filter.\n\nI wish we get a filter committed as commitment would unlock more utility than any marginal savings through\nmore elaborate design.\n\nTamas Blummer\n\n\u003e On Sep 19, 2019, at 19:20, admin--- via bitcoin-dev \u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e \n\u003e Hello list, \n\u003e \n\u003e Here is a link for a draft of a BIP for compact probabilistic block filters alternative of BIP 158\n\u003e \n\u003e https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSxv80ik/edit?usp=sharing \u003chttps://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSxv80ik/edit?usp=sharing\u003e\n\u003e \n\u003e Summary:\n\u003e \n\u003e - BIP 158 false positive rate is low, we can achieve lower bandwidth with higher false positive rate filter while sync blockchain\n\u003e \n\u003e - BIP 158 not do not support filter batching by design of used parameters for siphash and Golomb coding optimal parameters\n\u003e \n\u003e - Alternative compression with delta coding and splitting data to 2 bit string sequences. First for data without prefixes, second one for information about bit length written to first sequence.\n\u003e Second sequence have a lot of duplicates, compressed with 2 round of Huffman algorithm. (Effectivity about 98% vs Golomb with optimal parameters)\n\u003e \n\u003e - Block filters batching reduce filter size significantly\n\u003e \n\u003e - Separation of filters by address type allows lite client not to download redundant information without compromising privacy.\n\u003e \n\u003e - Lite client filters download strategy: get biggest filter (smallest blocks/size rate) for blocks range, in case positive test -\u003e get medium filters to reduce blocks range -\u003e get block filters for affected range -\u003e download affected blocks over TOR \n\u003e \n\u003e Implementation (python): https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.py#L172 \u003chttps://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.py#L172\u003e\n\u003e \n\u003e Exactly information from mainnet about size for separated filters by address types and batch size will be added within few days.\n\u003e \n\u003e Thanks for any feedback.\n\u003e Aleksey Karpov\n\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\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20190921/ecea43cc/attachment.html\u003e",
"sig": "5b947143c27a4809c3e75de2c0dd79d6b10640da0efc0067aea2a5f0a09239db4fced1caad17e9df7ad939a9a050ee5f916ea63341bd6c965669e4da825ac735"
}