📅 Original date posted:2018-05-25
📝 Original message:On Fri, May 25, 2018 at 5:54 PM, Pieter Wuille via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
> Hi all,
>
> I spent some time working out the optimal parameter selection for the
> Golomb Coded Sets that are proposed in BIP158:
> https://gist.github.com/sipa/576d5f09c3b86c3b1b75598d799fc845
>
> TL;DR: if we really want an FP rate of exactly 1 in 2^20, the Rice
> parameter should be 19, not 20. If we don't, we should pick an FP rate
> of 1 in a 1.4971*2^B. So for example M=784931 B=19 or M=1569861 B=20.
I did a rough analysis using Pieter's approximations on what
parameters minimizes the total communications for a lite wallet
scanning the chain and fetching a witnessless block whenever they get
a filter hit. For a wallet with 1000 keys and blocks of 1MB if the
number of entries in the is at least 5096 then M=784931 results in a
lower total data rate rate (FP blocks + filters) than M=1569861.
M=392465 (the optimal value for the rice parameter 18) is
communications is better if at least 10192 entries are set, and
M=196233 (optimal FP for rice 17) is better if at least 20384 entries
are set.
The prior filter set proposal is setting roughly 13300 entries per
full block, and I guestimate that the in+out scripts only ones are
setting about 7500 entries (if that actual number was in any of the
recent posts I missed it, I'm guessing based on jimpo's sizes graph).
The breakpoints are obviously different if the client is monitoring
for, say, 10,000 keys instead of 1000 but I think it generally makes
more sense to optimize for lower key counts since bigger users are
more likely to tolerate the additional bandwidth usage.
So I think that assuming that all-scripts inputs and outputs (but no
txids) are used and that my guess of 7500 bits set for that
configuration is roughly right, then M=1569861 and rice parameter 19
should be used.
The actual optimal FP rate for total data transferred won't be one
that gets the optimal rice coding efficiency, but since different
clients will be monitoring for different numbers of keys, it probably
makes sense to pick a parameter with optimal compression rather than
optimal-data-transfer-for-a-specific-key-count-- at least then we're
spending the least amount of filter bits per false positive rate,
whatever that rate is... if we can't be optimal at least we can be
efficient. :)
Gregory Maxwell [ARCHIVE] /
npub1f2…crwet
2023-06-07 18:12:29
in reply to nevent1q…tm68
Author Public Key
npub1f2nvlx49er5c7sqa43src6ssyp6snd4qwvtkwm5avc2l84cs84esecrwetPublished at
2023-06-07 18:12:29Event JSON
{
"id": "5b3a340d64201ca3925f364eae4bda259f369bf04f31cf3076f47b45bd6e6ed9",
"pubkey": "4aa6cf9aa5c8e98f401dac603c6a10207509b6a07317676e9d6615f3d7103d73",
"created_at": 1686161549,
"kind": 1,
"tags": [
[
"e",
"1fb299cd51cda0be4ef64f1bb0e47ab3eddd2a29a6e21aa9760ff086cb48ddfb",
"",
"root"
],
[
"e",
"01309902400955c52b38344fe1f9ee1f317d4fa6de19eee892c95e75e77d959d",
"",
"reply"
],
[
"p",
"5cb21bf5d7f25a9d46879713cbd32433bbc10e40ef813a3c28fe7355f49854d6"
]
],
"content": "📅 Original date posted:2018-05-25\n📝 Original message:On Fri, May 25, 2018 at 5:54 PM, Pieter Wuille via bitcoin-dev\n\u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e Hi all,\n\u003e\n\u003e I spent some time working out the optimal parameter selection for the\n\u003e Golomb Coded Sets that are proposed in BIP158:\n\u003e https://gist.github.com/sipa/576d5f09c3b86c3b1b75598d799fc845\n\u003e\n\u003e TL;DR: if we really want an FP rate of exactly 1 in 2^20, the Rice\n\u003e parameter should be 19, not 20. If we don't, we should pick an FP rate\n\u003e of 1 in a 1.4971*2^B. So for example M=784931 B=19 or M=1569861 B=20.\n\n\nI did a rough analysis using Pieter's approximations on what\nparameters minimizes the total communications for a lite wallet\nscanning the chain and fetching a witnessless block whenever they get\na filter hit. For a wallet with 1000 keys and blocks of 1MB if the\nnumber of entries in the is at least 5096 then M=784931 results in a\nlower total data rate rate (FP blocks + filters) than M=1569861.\nM=392465 (the optimal value for the rice parameter 18) is\ncommunications is better if at least 10192 entries are set, and\nM=196233 (optimal FP for rice 17) is better if at least 20384 entries\nare set.\n\nThe prior filter set proposal is setting roughly 13300 entries per\nfull block, and I guestimate that the in+out scripts only ones are\nsetting about 7500 entries (if that actual number was in any of the\nrecent posts I missed it, I'm guessing based on jimpo's sizes graph).\n\nThe breakpoints are obviously different if the client is monitoring\nfor, say, 10,000 keys instead of 1000 but I think it generally makes\nmore sense to optimize for lower key counts since bigger users are\nmore likely to tolerate the additional bandwidth usage.\n\nSo I think that assuming that all-scripts inputs and outputs (but no\ntxids) are used and that my guess of 7500 bits set for that\nconfiguration is roughly right, then M=1569861 and rice parameter 19\nshould be used.\n\nThe actual optimal FP rate for total data transferred won't be one\nthat gets the optimal rice coding efficiency, but since different\nclients will be monitoring for different numbers of keys, it probably\nmakes sense to pick a parameter with optimal compression rather than\noptimal-data-transfer-for-a-specific-key-count-- at least then we're\nspending the least amount of filter bits per false positive rate,\nwhatever that rate is... if we can't be optimal at least we can be\nefficient. :)",
"sig": "e5afe757aca939331b0066aa966c25eb642c00ff5ba9c6315b889f89281f6543314506a4bafb5e6ee38173a1f42f8ce6e3e16aa6219714060302e532b6234321"
}