📅 Original date posted:2018-05-31
📝 Original message:I processed the historic blockchain to create a single filter populated with spent input scripts and output scripts. The Golomb parameter was P=2^20
The resulting chart shows a volatile history of same-block address re-use with a notable drops in relative filter size during the early history and in the time window where SatoshiDICE was popular, since then trending higher.
The history of only the last half year suggests a current filter size of between 2.0% - 2.5% of block sizes.
Since most outputs are spent within a short time period, but apparently not that often in same blocks, I think it was worth considering filter series that match over a windows of 2^n blocks (n=(0…10)). Applications could then bracket the
range of interest and then narrow down requesting finer filters or blocks.
Then I created 1600 random (P2SH) scripts and totaled the false positive block download data size if observing 100, 200, 400, 800, 1600 of them.
The result suggests that even for 1600 the false positive overhead is less than 0.1% of blockchain data size.
I agree with Greg that we should optimize the parameters for a small observed set as those will be running on mobile devices.
As of Pieter’s findings the simulation parameters were optimal for ca. 1000 observed scripts which is maybe to many for a “small” application.
On the other hand we do not know the needs of future popular mobile applications.
With parameters of the simulation the current minimal data burden on a mobile wallet would be ca. 0.1 GB / Month.
Simulations with other parameters could be executed using this patch branch: https://github.com/tamasblummer/rust-bitcoin-spv/tree/blockfilterstats A run takes a few hours on a fast machine with release build and local bitcoind.
The calculation can not be reduced to the recent history as the process builds in-memory utxo from genesis.
The result of executing the binary is a CSV file containing:
blocknumber, blocksize, utxo size, filter size, false positive data size for 100, false positive data size for 100, … false positive data size for 100
e.g:
524994,1112181,57166825,21556,0,0,0,0,1112181
Tamas Blummer
> On May 29, 2018, at 06:01, Olaoluwa Osuntokun via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> > The additional benefit of the input script/outpoint filter is to watch for
> > unexpected spends (coins getting stolen or spent from another wallet) or
> > transactions without a unique change or output address. I think this is a
> > reasonable implementation, and it would be nice to be able to download that
> > filter without any input elements.
>
> As someone who's implemented a complete integration of the filtering
> technique into an existing wallet, and a higher application I disagree.
> There's not much gain to be had in splitting up the filters: it'll result in
> additional round trips (to fetch these distinct filter) during normal
> operation, complicate routine seed rescanning logic, and also is detrimental
> to privacy if one is fetching blocks from the same peer as they've
> downloaded the filters from.
>
> However, I'm now convinced that the savings had by including the prev output
> script (addr re-use and outputs spent in the same block as they're created)
> outweigh the additional booking keeping required in an implementation (when
> extracting the precise tx that matched) compared to using regular outpoint
> as we do currently. Combined with the recently proposed re-parametrization
> of the gcs parameters[1], the filter size should shrink by quite a bit!
>
> I'm very happy with the review the BIPs has been receiving as of late. It
> would've been nice to have this 1+ year ago when the draft was initially
> proposed, but better late that never!
>
> Based on this thread, [1], and discussions on various IRC channels, I plan
> to make the following modifications to the BIP:
>
> 1. use P=2^19 and M=784931 as gcs parameters, and also bind these to the
> filter instance, so future filter types may use distinct parameters
> 2. use the prev output script rather than the prev input script in the
> regular filter
> 3. remove the txid from the regular filter(as with some extra book-keeping
> the output script is enough)
> 4. do away with the extended filter all together, as our original use case
> for it has been nerfed as the filter size grew too large when doing
> recursive parsing. instead we watch for the outpoint being spent and
> extract the pre-image from it if it matches now
>
> The resulting changes should slash the size of the filters, yet still ensure
> that they're useful enough for our target use case.
>
> [1]: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/016029.html
>
> -- Laolu
> _______________________________________________
> 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/20180531/34f94f8e/attachment-0001.html>;
-------------- next part --------------
A non-text attachment was scrubbed...
Name: filtersize.png
Type: image/png
Size: 58848 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180531/34f94f8e/attachment-0003.png>;
-------------- next part --------------
A non-text attachment was scrubbed...
Name: lasthalfyear.png
Type: image/png
Size: 50431 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180531/34f94f8e/attachment-0004.png>;
-------------- next part --------------
A non-text attachment was scrubbed...
Name: falsepositive.png
Type: image/png
Size: 82663 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180531/34f94f8e/attachment-0005.png>;
Tamas Blummer [ARCHIVE] /
npub1cc…ex8m8
2023-06-07 18:12:18
in reply to nevent1q…j96a
Author Public Key
npub1ccegg9n9lnx6huppxg43m95488yur7pfemkn3pz0agjws5ffvtts0ex8m8Published at
2023-06-07 18:12:18Event JSON
{
"id": "e74e1b99c5cf5c7584db498103dc65f316cf5e973c4fcc3dc16ccefc450c4e9f",
"pubkey": "c632841665fccdabf021322b1d969539c9c1f829ceed38844fea24e8512962d7",
"created_at": 1686161538,
"kind": 1,
"tags": [
[
"e",
"aefee7e3913729b7ef736d47c6f2a24954de10011f27b89dcaeaac62c51b6a6f",
"",
"root"
],
[
"e",
"7fbf914925378ccfe3399369a144ab4826cd22d1405d9f7550533dff20bd9cdf",
"",
"reply"
],
[
"p",
"2df3fc2660459521b852c995d4fc1a93938389a5e085677d0ebb33ef92cc5476"
]
],
"content": "📅 Original date posted:2018-05-31\n📝 Original message:I processed the historic blockchain to create a single filter populated with spent input scripts and output scripts. The Golomb parameter was P=2^20\n\nThe resulting chart shows a volatile history of same-block address re-use with a notable drops in relative filter size during the early history and in the time window where SatoshiDICE was popular, since then trending higher.\nThe history of only the last half year suggests a current filter size of between 2.0% - 2.5% of block sizes.\n\nSince most outputs are spent within a short time period, but apparently not that often in same blocks, I think it was worth considering filter series that match over a windows of 2^n blocks (n=(0…10)). Applications could then bracket the \nrange of interest and then narrow down requesting finer filters or blocks.\n\nThen I created 1600 random (P2SH) scripts and totaled the false positive block download data size if observing 100, 200, 400, 800, 1600 of them. \nThe result suggests that even for 1600 the false positive overhead is less than 0.1% of blockchain data size. \n\nI agree with Greg that we should optimize the parameters for a small observed set as those will be running on mobile devices.\nAs of Pieter’s findings the simulation parameters were optimal for ca. 1000 observed scripts which is maybe to many for a “small” application.\nOn the other hand we do not know the needs of future popular mobile applications. \n \nWith parameters of the simulation the current minimal data burden on a mobile wallet would be ca. 0.1 GB / Month.\n\nSimulations with other parameters could be executed using this patch branch: https://github.com/tamasblummer/rust-bitcoin-spv/tree/blockfilterstats A run takes a few hours on a fast machine with release build and local bitcoind.\nThe calculation can not be reduced to the recent history as the process builds in-memory utxo from genesis.\n\nThe result of executing the binary is a CSV file containing:\nblocknumber, blocksize, utxo size, filter size, false positive data size for 100, false positive data size for 100, … false positive data size for 100\ne.g:\n524994,1112181,57166825,21556,0,0,0,0,1112181\n\nTamas Blummer\n\n\n\u003e On May 29, 2018, at 06:01, Olaoluwa Osuntokun via bitcoin-dev \u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e \n\u003e \u003e The additional benefit of the input script/outpoint filter is to watch for\n\u003e \u003e unexpected spends (coins getting stolen or spent from another wallet) or\n\u003e \u003e transactions without a unique change or output address. I think this is a\n\u003e \u003e reasonable implementation, and it would be nice to be able to download that\n\u003e \u003e filter without any input elements. \n\u003e \n\u003e As someone who's implemented a complete integration of the filtering\n\u003e technique into an existing wallet, and a higher application I disagree.\n\u003e There's not much gain to be had in splitting up the filters: it'll result in\n\u003e additional round trips (to fetch these distinct filter) during normal\n\u003e operation, complicate routine seed rescanning logic, and also is detrimental\n\u003e to privacy if one is fetching blocks from the same peer as they've\n\u003e downloaded the filters from.\n\u003e \n\u003e However, I'm now convinced that the savings had by including the prev output\n\u003e script (addr re-use and outputs spent in the same block as they're created)\n\u003e outweigh the additional booking keeping required in an implementation (when\n\u003e extracting the precise tx that matched) compared to using regular outpoint\n\u003e as we do currently. Combined with the recently proposed re-parametrization\n\u003e of the gcs parameters[1], the filter size should shrink by quite a bit!\n\u003e \n\u003e I'm very happy with the review the BIPs has been receiving as of late. It\n\u003e would've been nice to have this 1+ year ago when the draft was initially\n\u003e proposed, but better late that never!\n\u003e \n\u003e Based on this thread, [1], and discussions on various IRC channels, I plan\n\u003e to make the following modifications to the BIP:\n\u003e \n\u003e 1. use P=2^19 and M=784931 as gcs parameters, and also bind these to the\n\u003e filter instance, so future filter types may use distinct parameters\n\u003e 2. use the prev output script rather than the prev input script in the\n\u003e regular filter\n\u003e 3. remove the txid from the regular filter(as with some extra book-keeping\n\u003e the output script is enough) \n\u003e 4. do away with the extended filter all together, as our original use case\n\u003e for it has been nerfed as the filter size grew too large when doing\n\u003e recursive parsing. instead we watch for the outpoint being spent and\n\u003e extract the pre-image from it if it matches now\n\u003e \n\u003e The resulting changes should slash the size of the filters, yet still ensure\n\u003e that they're useful enough for our target use case.\n\u003e \n\u003e [1]: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/016029.html\n\u003e \n\u003e -- Laolu\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/20180531/34f94f8e/attachment-0001.html\u003e\n-------------- next part --------------\nA non-text attachment was scrubbed...\nName: filtersize.png\nType: image/png\nSize: 58848 bytes\nDesc: not available\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180531/34f94f8e/attachment-0003.png\u003e\n-------------- next part --------------\nA non-text attachment was scrubbed...\nName: lasthalfyear.png\nType: image/png\nSize: 50431 bytes\nDesc: not available\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180531/34f94f8e/attachment-0004.png\u003e\n-------------- next part --------------\nA non-text attachment was scrubbed...\nName: falsepositive.png\nType: image/png\nSize: 82663 bytes\nDesc: not available\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180531/34f94f8e/attachment-0005.png\u003e",
"sig": "a78b7e9b4a1725e218fedd45158337756a0b45fc4d8623bc17b753f08c3b1c38456d7027fc5217f1db5a7aed98a18b29d52b1e0fc77e7fcb16aac6cb4577236e"
}