📅 Original date posted:2018-05-24
📝 Original message:Greg, I've attached a graph including the input scripts.
In the top graph, we can see how the input script filter compares to the
input outpoint filter. It is definitely smaller as a result of address
reuse. The bottom graph shows the ratio over time of combining the input
prev script and output script filters vs keeping them separate. In more
recent blocks, it appears that there are decreasing savings.
On Wed, May 23, 2018 at 6:04 PM Conner Fromknecht
<conner at lightning.engineering> wrote:
> Hi all,
>
> Jimpo, thanks for looking into those stats! I had always imagined that
> there
> would be a more significant savings in having all filters in one bundle, as
> opposed to separate. These results are interesting, to say the least, and
> definitely offer us some flexibility in options for filter sharding.
>
> So far, the bulk of this discussion has centered around bandwidth. I am
> concerned, however, that splitting up the filters is at odds with the
> other
> goal of the proposal in offering improved privacy.
>
> Allowing clients to choose individual filter sets trivially exposes the
> type of
> data that client is interested in. This alone might be enough to
> fingerprint the
> function of a peer and reduce anonymity set justifying their potential
> behavior.
>
> Furthermore, if a match is encountered, and block requested, full nodes
> have
> more targeted insight into what caused a particular match. They could
> infer that
> the client received funds in a particular block, e.g., if they are only
> requesting
> output scripts.
>
> This is above and beyond the additional complexity of now syncing,
> validating,
> and managing five or six distinct header/filter-header/filter/block chains.
>
> I agree that saving on bandwidth is an important goal, but bandwidth and
> privacy
> are always seemingly at odds. Strictly comparing the bandwidth
> requirements of
> a system that heavily weighs privacy to existing ones, e.g. BIP39, that
> don't is a
> losing battle IMO.
>
> I'm not fundamentally opposed to splitting the filters, I certainly see the
> arguments for flexibility. However, I also want to ensure we are
> considering the
> second order effects that fall out of optimizing for one metric when
> others exist.
>
> Cheers,
> Conner
> On Wed, May 23, 2018 at 10:29 Gregory Maxwell via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>> Any chance you could add a graph of input-scripts (instead of input
>> outpoints)?
>>
>> On Wed, May 23, 2018 at 7:38 AM, Jim Posen via bitcoin-dev
>> <bitcoin-dev at lists.linuxfoundation.org> 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.
>> >
>> >
>> >
>> > _______________________________________________
>> > bitcoin-dev mailing list
>> > bitcoin-dev at lists.linuxfoundation.org
>> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>> >
>> _______________________________________________
>> 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/20180523/fe5608eb/attachment-0001.html>;
-------------- next part --------------
A non-text attachment was scrubbed...
Name: filter_sizes.svg
Type: image/svg+xml
Size: 2833873 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/fe5608eb/attachment-0001.svg>;
Jim Posen [ARCHIVE] /
npub1nc…lqt2n
2023-06-07 18:12:16
in reply to nevent1q…v27g
Author Public Key
npub1ncnj8arudstdxzfhxk7k4nwgkrw3hyw8sgt0wqqmm5hh2c4knmgs2lqt2nPublished at
2023-06-07 18:12:16Event JSON
{
"id": "e9d0a0f2304c1445c0560a53effcd07de763f1bebc3e0a925efee39e0f7778a1",
"pubkey": "9e2723f47c6c16d3093735bd6acdc8b0dd1b91c78216f7001bdd2f7562b69ed1",
"created_at": 1686161536,
"kind": 1,
"tags": [
[
"e",
"aefee7e3913729b7ef736d47c6f2a24954de10011f27b89dcaeaac62c51b6a6f",
"",
"root"
],
[
"e",
"88eaf2fc5a1b7dba5071de08db88372f825ba83c82f2a6a96644c58ca01be565",
"",
"reply"
],
[
"p",
"175fd2f52497b9ba272cebdb436ee9876f111b6aa2af3ea9bc03e7cdf4b45246"
]
],
"content": "📅 Original date posted:2018-05-24\n📝 Original message:Greg, I've attached a graph including the input scripts.\n\nIn the top graph, we can see how the input script filter compares to the\ninput outpoint filter. It is definitely smaller as a result of address\nreuse. The bottom graph shows the ratio over time of combining the input\nprev script and output script filters vs keeping them separate. In more\nrecent blocks, it appears that there are decreasing savings.\n\nOn Wed, May 23, 2018 at 6:04 PM Conner Fromknecht\n\u003cconner at lightning.engineering\u003e wrote:\n\n\u003e Hi all,\n\u003e\n\u003e Jimpo, thanks for looking into those stats! I had always imagined that\n\u003e there\n\u003e would be a more significant savings in having all filters in one bundle, as\n\u003e opposed to separate. These results are interesting, to say the least, and\n\u003e definitely offer us some flexibility in options for filter sharding.\n\u003e\n\u003e So far, the bulk of this discussion has centered around bandwidth. I am\n\u003e concerned, however, that splitting up the filters is at odds with the\n\u003e other\n\u003e goal of the proposal in offering improved privacy.\n\u003e\n\u003e Allowing clients to choose individual filter sets trivially exposes the\n\u003e type of\n\u003e data that client is interested in. This alone might be enough to\n\u003e fingerprint the\n\u003e function of a peer and reduce anonymity set justifying their potential\n\u003e behavior.\n\u003e\n\u003e Furthermore, if a match is encountered, and block requested, full nodes\n\u003e have\n\u003e more targeted insight into what caused a particular match. They could\n\u003e infer that\n\u003e the client received funds in a particular block, e.g., if they are only\n\u003e requesting\n\u003e output scripts.\n\u003e\n\u003e This is above and beyond the additional complexity of now syncing,\n\u003e validating,\n\u003e and managing five or six distinct header/filter-header/filter/block chains.\n\u003e\n\u003e I agree that saving on bandwidth is an important goal, but bandwidth and\n\u003e privacy\n\u003e are always seemingly at odds. Strictly comparing the bandwidth\n\u003e requirements of\n\u003e a system that heavily weighs privacy to existing ones, e.g. BIP39, that\n\u003e don't is a\n\u003e losing battle IMO.\n\u003e\n\u003e I'm not fundamentally opposed to splitting the filters, I certainly see the\n\u003e arguments for flexibility. However, I also want to ensure we are\n\u003e considering the\n\u003e second order effects that fall out of optimizing for one metric when\n\u003e others exist.\n\u003e\n\u003e Cheers,\n\u003e Conner\n\u003e On Wed, May 23, 2018 at 10:29 Gregory Maxwell via bitcoin-dev \u003c\n\u003e bitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\n\u003e\u003e Any chance you could add a graph of input-scripts (instead of input\n\u003e\u003e outpoints)?\n\u003e\u003e\n\u003e\u003e On Wed, May 23, 2018 at 7:38 AM, Jim Posen via bitcoin-dev\n\u003e\u003e \u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\u003e \u003e So I checked filter sizes (as a proportion of block size) for each of\n\u003e\u003e the\n\u003e\u003e \u003e sub-filters. The graph is attached.\n\u003e\u003e \u003e\n\u003e\u003e \u003e As interpretation, the first ~120,000 blocks are so small that the\n\u003e\u003e \u003e Golomb-Rice coding can't compress the filters that well, which is why\n\u003e\u003e the\n\u003e\u003e \u003e filter sizes are so high proportional to the block size. Except for the\n\u003e\u003e \u003e input filter, because the coinbase input is skipped, so many of them\n\u003e\u003e have 0\n\u003e\u003e \u003e elements. But after block 120,000 or so, the filter compression\n\u003e\u003e converges\n\u003e\u003e \u003e pretty quickly to near the optimal value. The encouraging thing here is\n\u003e\u003e that\n\u003e\u003e \u003e if you look at the ratio of the combined size of the separated filters\n\u003e\u003e vs\n\u003e\u003e \u003e the size of a filter containing all of them (currently known as the\n\u003e\u003e basic\n\u003e\u003e \u003e filter), they are pretty much the same size. The mean of the ratio\n\u003e\u003e between\n\u003e\u003e \u003e them after block 150,000 is 99.4%. So basically, not much compression\n\u003e\u003e \u003e efficiently is lost by separating the basic filter into sub-filters.\n\u003e\u003e \u003e\n\u003e\u003e \u003e On Tue, May 22, 2018 at 5:42 PM, Jim Posen \u003cjim.posen at gmail.com\u003e wrote:\n\u003e\u003e \u003e\u003e\u003e\n\u003e\u003e \u003e\u003e\u003e My suggestion was to advertise a bitfield for each filter type the\n\u003e\u003e node\n\u003e\u003e \u003e\u003e\u003e serves,\n\u003e\u003e \u003e\u003e\u003e where the bitfield indicates what elements are part of the filters.\n\u003e\u003e This\n\u003e\u003e \u003e\u003e\u003e essentially\n\u003e\u003e \u003e\u003e\u003e removes the notion of decided filter types and instead leaves the\n\u003e\u003e \u003e\u003e\u003e decision to\n\u003e\u003e \u003e\u003e\u003e full-nodes.\n\u003e\u003e \u003e\u003e\n\u003e\u003e \u003e\u003e\n\u003e\u003e \u003e\u003e I think it makes more sense to construct entirely separate filters for\n\u003e\u003e the\n\u003e\u003e \u003e\u003e different types of elements and allow clients to download only the\n\u003e\u003e ones they\n\u003e\u003e \u003e\u003e care about. If there are enough elements per filter, the compression\n\u003e\u003e ratio\n\u003e\u003e \u003e\u003e shouldn't be much worse by splitting them up. This prevents the\n\u003e\u003e exponential\n\u003e\u003e \u003e\u003e blowup in the number of filters that you mention, Johan, and it works\n\u003e\u003e nicely\n\u003e\u003e \u003e\u003e with service bits for advertising different filter types independently.\n\u003e\u003e \u003e\u003e\n\u003e\u003e \u003e\u003e So if we created three separate filter types, one for output scripts,\n\u003e\u003e one\n\u003e\u003e \u003e\u003e for input outpoints, and one for TXIDs, each signaled with a separate\n\u003e\u003e \u003e\u003e service bit, are people good with that? Or do you think there\n\u003e\u003e shouldn't be a\n\u003e\u003e \u003e\u003e TXID filter at all, Matt? I didn't include the option of a prev output\n\u003e\u003e \u003e\u003e script filter or rolling that into the block output script filter\n\u003e\u003e because it\n\u003e\u003e \u003e\u003e changes the security model (cannot be proven to be correct/incorrect\n\u003e\u003e \u003e\u003e succinctly).\n\u003e\u003e \u003e\u003e\n\u003e\u003e \u003e\u003e Then there's the question of whether to separate or combine the\n\u003e\u003e headers.\n\u003e\u003e \u003e\u003e I'd lean towards keeping them separate because it's simpler that way.\n\u003e\u003e \u003e\n\u003e\u003e \u003e\n\u003e\u003e \u003e\n\u003e\u003e \u003e _______________________________________________\n\u003e\u003e \u003e bitcoin-dev mailing list\n\u003e\u003e \u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e\u003e \u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\u003e \u003e\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-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/fe5608eb/attachment-0001.html\u003e\n-------------- next part --------------\nA non-text attachment was scrubbed...\nName: filter_sizes.svg\nType: image/svg+xml\nSize: 2833873 bytes\nDesc: not available\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/fe5608eb/attachment-0001.svg\u003e",
"sig": "960ab59d1098e26a78bb71fd4f40e99914460dd37269ec597de16d31910c89aa6b055bbb8abf77987309d23c3912af0d744faba10602dbc7aa598fb4cc3a1499"
}