📅 Original date posted:2018-05-23
📝 Original message:Thanks, Jimpo!
This is very encouraging, I think. I sorta assumed that separating the
elements into their own sub-filters would hurt the compression a lot more.
Can the compression ratio/false positive rate be tweaked with the
sub-filters in mind?
With the total size of the separated filters being no larger than the
combined filters, I see no benefit of combined filters? Committing to them
all in the headers would also save space, and we could ensure nodes are
serving all sub-filters.
- Johan
On Wed, May 23, 2018 at 9:38 AM, Jim Posen <jim.posen at gmail.com> wrote:
> So I checked filter sizes (as a proportion of block size) for each of the
> sub-filters. The graph is attached.
>
> As interpretation, the first ~120,000 blocks are so small that the
> Golomb-Rice coding can't compress the filters that well, which is why the
> filter sizes are so high proportional to the block size. Except for the
> input filter, because the coinbase input is skipped, so many of them have 0
> elements. But after block 120,000 or so, the filter compression converges
> pretty quickly to near the optimal value. The encouraging thing here is
> that if you look at the ratio of the combined size of the separated filters
> vs the size of a filter containing all of them (currently known as the
> basic filter), they are pretty much the same size. The mean of the ratio
> between them after block 150,000 is 99.4%. So basically, not much
> compression efficiently is lost by separating the basic filter into
> sub-filters.
>
> On Tue, May 22, 2018 at 5:42 PM, Jim Posen <jim.posen at gmail.com> wrote:
>
>> My suggestion was to advertise a bitfield for each filter type the node
>>> serves,
>>> where the bitfield indicates what elements are part of the filters. This
>>> essentially
>>> removes the notion of decided filter types and instead leaves the
>>> decision to
>>> full-nodes.
>>>
>>
>> I think it makes more sense to construct entirely separate filters for
>> the different types of elements and allow clients to download only the ones
>> they care about. If there are enough elements per filter, the compression
>> ratio shouldn't be much worse by splitting them up. This prevents the
>> exponential blowup in the number of filters that you mention, Johan, and it
>> works nicely with service bits for advertising different filter types
>> independently.
>>
>> So if we created three separate filter types, one for output scripts, one
>> for input outpoints, and one for TXIDs, each signaled with a separate
>> service bit, are people good with that? Or do you think there shouldn't be
>> a TXID filter at all, Matt? I didn't include the option of a prev output
>> script filter or rolling that into the block output script filter because
>> it changes the security model (cannot be proven to be correct/incorrect
>> succinctly).
>>
>> Then there's the question of whether to separate or combine the headers.
>> I'd lean towards keeping them separate because it's simpler that way.
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/7df6715a/attachment.html>;
Johan Torås Halseth [ARCHIVE] /
npub1pp…hs2fw
2023-06-07 18:12:15
in reply to nevent1q…etpk
Author Public Key
npub1ppn2nhlfdzkw9gw0ytljpef5dpyzsxzw8ffcyykamt32hw6pge0smhs2fwPublished at
2023-06-07 18:12:15Event JSON
{
"id": "321408720d53341496e96963cd300f806c71dbcd1fc7ae37285733368d6f2d6f",
"pubkey": "0866a9dfe968ace2a1cf22ff20e534684828184e3a538212dddae2abbb41465f",
"created_at": 1686161535,
"kind": 1,
"tags": [
[
"e",
"aefee7e3913729b7ef736d47c6f2a24954de10011f27b89dcaeaac62c51b6a6f",
"",
"root"
],
[
"e",
"37ac1a6e3e4a2a40336d352b94d53ba7ff71bec293f8df2073708f8b229142a9",
"",
"reply"
],
[
"p",
"9e2723f47c6c16d3093735bd6acdc8b0dd1b91c78216f7001bdd2f7562b69ed1"
]
],
"content": "📅 Original date posted:2018-05-23\n📝 Original message:Thanks, Jimpo!\n\nThis is very encouraging, I think. I sorta assumed that separating the\nelements into their own sub-filters would hurt the compression a lot more.\nCan the compression ratio/false positive rate be tweaked with the\nsub-filters in mind?\n\nWith the total size of the separated filters being no larger than the\ncombined filters, I see no benefit of combined filters? Committing to them\nall in the headers would also save space, and we could ensure nodes are\nserving all sub-filters.\n\n- Johan\n\nOn Wed, May 23, 2018 at 9:38 AM, Jim Posen \u003cjim.posen at gmail.com\u003e wrote:\n\n\u003e So I checked filter sizes (as a proportion of block size) for each of the\n\u003e sub-filters. The graph is attached.\n\u003e\n\u003e As interpretation, the first ~120,000 blocks are so small that the\n\u003e Golomb-Rice coding can't compress the filters that well, which is why the\n\u003e filter sizes are so high proportional to the block size. Except for the\n\u003e input filter, because the coinbase input is skipped, so many of them have 0\n\u003e elements. But after block 120,000 or so, the filter compression converges\n\u003e pretty quickly to near the optimal value. The encouraging thing here is\n\u003e that if you look at the ratio of the combined size of the separated filters\n\u003e vs the size of a filter containing all of them (currently known as the\n\u003e basic filter), they are pretty much the same size. The mean of the ratio\n\u003e between them after block 150,000 is 99.4%. So basically, not much\n\u003e compression efficiently is lost by separating the basic filter into\n\u003e sub-filters.\n\u003e\n\u003e On Tue, May 22, 2018 at 5:42 PM, Jim Posen \u003cjim.posen at gmail.com\u003e wrote:\n\u003e\n\u003e\u003e My suggestion was to advertise a bitfield for each filter type the node\n\u003e\u003e\u003e serves,\n\u003e\u003e\u003e where the bitfield indicates what elements are part of the filters. This\n\u003e\u003e\u003e essentially\n\u003e\u003e\u003e removes the notion of decided filter types and instead leaves the\n\u003e\u003e\u003e decision to\n\u003e\u003e\u003e full-nodes.\n\u003e\u003e\u003e\n\u003e\u003e\n\u003e\u003e I think it makes more sense to construct entirely separate filters for\n\u003e\u003e the different types of elements and allow clients to download only the ones\n\u003e\u003e they care about. If there are enough elements per filter, the compression\n\u003e\u003e ratio shouldn't be much worse by splitting them up. This prevents the\n\u003e\u003e exponential blowup in the number of filters that you mention, Johan, and it\n\u003e\u003e works nicely with service bits for advertising different filter types\n\u003e\u003e independently.\n\u003e\u003e\n\u003e\u003e So if we created three separate filter types, one for output scripts, one\n\u003e\u003e for input outpoints, and one for TXIDs, each signaled with a separate\n\u003e\u003e service bit, are people good with that? Or do you think there shouldn't be\n\u003e\u003e a TXID filter at all, Matt? I didn't include the option of a prev output\n\u003e\u003e script filter or rolling that into the block output script filter because\n\u003e\u003e it changes the security model (cannot be proven to be correct/incorrect\n\u003e\u003e succinctly).\n\u003e\u003e\n\u003e\u003e Then there's the question of whether to separate or combine the headers.\n\u003e\u003e I'd lean towards keeping them separate because it's simpler that way.\n\u003e\u003e\n\u003e\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/7df6715a/attachment.html\u003e",
"sig": "ab7972d946125c70854e2602344a101219149bc89dcaef827c60022c8d42a4fd02b3bed8d1840ffca4258bfcb210c01bc0e4f7677ffce58df6c8633cb84762f4"
}