BIP-0158: remove extended filter, remove txid from regular filter, reparameterize gcs params

Roasbeef commented at 2:34 am on June 1, 2018: contributor

In this PR, we propose a set of changes to BIP 158 (block filter digests) to reduce the size of the filters, while maintaining the same level of utility for wallets and applications that seek to utilize this new(ish) BIP. A rundown of the new changes follows:

The txid has been removed from the regular filter, as in many cases just matching on the pkScript, then checking the block locally after it matches for the precise txid match is enough. I’ve implemented this new logic in lnd (as we’re the primary user of this new functionality), and the changes were rather contained, so it shouldn’t be a big change application logic wise.
The extended filter has been removed as there isn’t really a clear use case for them atm, and they increase the index size for a full node.
The gcs parameters have been re-parameterized, to set the fp rate independently from the modulus used when hashing the set of N items down to a single range. As a result, the filter sizes have shrunk a bit as we can save a bit or two for each element.

BIP-0158: remove txid from extended filter 285606ef7a

in bip-0158/testnet-19.json:3 in bc10f2c9ef outdated

 6-[3,"000000008b896e272758da5297bcd98fdc6d97c9b765ecec401e286dc1fdbe10","0100000020782a005255b657696ea057d5b98f34defcf75196f64f6eeac8026c0000000041ba5afc532aae03151b8aa87b65e1594f97504a768e010c98c0add79216247186e7494dffff001d058dc2b60101000000010000000000000000000000000000000000000000000000000000000000000000ffffffff0e0486e7494d0151062f503253482fffffffff0100f2052a01000000232103f6d9ff4c12959445ca5549c811683bf9c88e637b222dd2e0311154c4c85cf423ac00000000","ec48f9f8a625bd8adb2d2684867a05baafebf935553e0b78b386da98179dcf49","0dd53b407c3f242f1838e39e2fc0cfb89cdca27de07ec230568a08d1872f9e01","022ce4b3256540","00","060b7e1be150cc3cabd9e96b00af217132b387f31fd2bd9adfb0c7f5a09a3356","5b2a59bc476d52b45de1398ee34ed10d0cccd2a4b19ba502a456c7356b35be0d",""],
 7-[926485,"000000000000015d6077a411a8f5cc95caf775ccf11c54e27df75ce58d187313","0000002060bbab0edbf3ef8a49608ee326f8fd75c473b7e3982095e2d100000000000000c30134f8c9b6d2470488d7a67a888f6fa12f8692e0c3411fbfb92f0f68f67eedae03ca57ef13021acc22dc4105010000000001010000000000000000000000000000000000000000000000000000000000000000ffffffff2f0315230e0004ae03ca57043e3d1e1d0c8796bf579aef0c0000000000122f4e696e6a61506f6f6c2f5345475749542fffffffff038427a112000000001976a914876fbb82ec05caa6af7a3b5e5a983aae6c6cc6d688ac0000000000000000266a24aa21a9ed5c748e121c0fe146d973a4ac26fa4a68b0549d46ee22d25f50a5e46fe1b377ee00000000000000002952534b424c4f434b3acd16772ad61a3c5f00287480b720f6035d5e54c9efc71be94bb5e3727f10909001200000000000000000000000000000000000000000000000000000000000000000000000000100000000010145310e878941a1b2bc2d33797ee4d89d95eaaf2e13488063a2aa9a74490f510a0100000023220020b6744de4f6ec63cc92f7c220cdefeeb1b1bed2b66c8e5706d80ec247d37e65a1ffffffff01002d3101000000001976a9143ebc40e411ed3c76f86711507ab952300890397288ac0400473044022001dd489a5d4e2fbd8a3ade27177f6b49296ba7695c40dbbe650ea83f106415fd02200b23a0602d8ff1bdf79dee118205fc7e9b40672bf31563e5741feb53fb86388501483045022100f88f040e90cc5dc6c6189d04718376ac19ed996bf9e4a3c29c3718d90ffd27180220761711f16c9e3a44f71aab55cbc0634907a1fa8bb635d971a9a01d368727bea10169522103b3623117e988b76aaabe3d63f56a4fc88b228a71e64c4cc551d1204822fe85cb2103dd823066e096f72ed617a41d3ca56717db335b1ea47a1b4c5c9dbdd0963acba621033d7c89bd9da29fa8d44db7906a9778b53121f72191184a9fee785c39180e4be153ae00000000010000000120925534261de4dcebb1ed5ab1b62bfe7a3ef968fb111dc2c910adfebc6e3bdf010000006b483045022100f50198f5ae66211a4f485190abe4dc7accdabe3bc214ebc9ea7069b97097d46e0220316a70a03014887086e335fc1b48358d46cd6bdc9af3b57c109c94af76fc915101210316cff587a01a2736d5e12e53551b18d73780b83c3bfb4fcf209c869b11b6415effffffff0220a10700000000001976a91450333046115eaa0ac9e0216565f945070e44573988ac2e7cd01a000000001976a914c01a7ca16b47be50cbdbc60724f701d52d75156688ac00000000010000000203a25f58630d7a1ea52550365fd2156683f56daf6ca73a4b4bbd097e66516322010000006a47304402204efc3d70e4ca3049c2a425025edf22d5ca355f9ec899dbfbbeeb2268533a0f2b02204780d3739653035af4814ea52e1396d021953f948c29754edd0ee537364603dc012103f7a897e4dbecab2264b21917f90664ea8256189ea725d28740cf7ba5d85b5763ffffffff03a25f58630d7a1ea52550365fd2156683f56daf6ca73a4b4bbd097e66516322000000006a47304402202d96defdc5b4af71d6ba28c9a6042c2d5ee7bc6de565d4db84ef517445626e03022022da80320e9e489c8f41b74833dfb6a54a4eb5087cdb46eb663eef0b25caa526012103f7a897e4dbecab2264b21917f90664ea8256189ea725d28740cf7ba5d85b5763ffffffff0200e1f5050000000017a914b7e6f7ff8658b2d1fb107e3d7be7af4742e6b1b3876f88fc00000000001976a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac0000000001000000043ffd60d3818431c495b89be84afac205d5d1ed663009291c560758bbd0a66df5010000006b483045022100f344607de9df42049688dcae8ff1db34c0c7cd25ec05516e30d2bc8f12ac9b2f022060b648f6a21745ea6d9782e17bcc4277b5808326488a1f40d41e125879723d3a012103f7a897e4dbecab2264b21917f90664ea8256189ea725d28740cf7ba5d85b5763ffffffffa5379401cce30f84731ef1ba65ce27edf2cc7ce57704507ebe8714aa16a96b92010000006a473044022020c37a63bf4d7f564c2192528709b6a38ab8271bd96898c6c2e335e5208661580220435c6f1ad4d9305d2c0a818b2feb5e45d443f2f162c0f61953a14d097fd07064012103f7a897e4dbecab2264b21917f90664ea8256189ea725d28740cf7ba5d85b5763ffffffff70e731e193235ff12c3184510895731a099112ffca4b00246c60003c40f843ce000000006a473044022053760f74c29a879e30a17b5f03a5bb057a5751a39f86fa6ecdedc36a1b7db04c022041d41c9b95f00d2d10a0373322a9025dba66c942196bc9d8adeb0e12d3024728012103f7a897e4dbecab2264b21917f90664ea8256189ea725d28740cf7ba5d85b5763ffffffff66b7a71b3e50379c8e85fc18fe3f1a408fc985f257036c34702ba205cef09f6f000000006a4730440220499bf9e2db3db6e930228d0661395f65431acae466634d098612fd80b08459ee022040e069fc9e3c60009f521cef54c38aadbd1251aee37940e6018aadb10f194d6a012103f7a897e4dbecab2264b21917f90664ea8256189ea725d28740cf7ba5d85b5763ffffffff0200e1f5050000000017a9148fc37ad460fdfbd2b44fe446f6e3071a4f64faa6878f447f0b000000001976a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac00000000","5c169b91332e661a4ebf684d6dffcf64aa139e1e736096ce462609b2e0783c55","5f3cd111e10ed28b7c2bc138fe4bc62e5df1cdc292c010b78c84e5111a5daaa6","16040c63f7ddea293f2d9c13690c0ba7b2910228c38b0fe542ce525021e49b598ada05f83bb9c37c711a02b1850265991c34c4fea6261d22a4b84596c0","0e6651beff00ee7a3be424a90e98450727b304558434c8d53781d469131ad21d399376c151ca28","c8f83ffbc9781c2bd4b7e3c055e888b00d3e2fea14e93b3c4f3adee86b063374","61f8ee615258981089be9f98337f53f44b14cc1532aa469a348fdee547117b80","Duplicate pushdata 913bcc2be49cb534c20474c4dee1e9c4c317e7eb"],
 8-[987876,"0000000000000c00901f2049055e2a437c819d79a3d54fd63e6af796cd7b8a79","000000202694f74969fdb542090e95a56bc8aa2d646e27033850e32f1c5f000000000000f7e53676b3f12d5beb524ed617f2d25f5a93b5f4f52c1ba2678260d72712f8dd0a6dfe5740257e1a4b1768960101000000010000000000000000000000000000000000000000000000000000000000000000ffffffff1603e4120ff9c30a1c216900002f424d4920546573742fffffff0001205fa012000000001e76a914c486de584a735ec2f22da7cd9681614681f92173d83d0aa68688ac00000000","37bf9e681888b3cd204ca4e0c995aad68cd0ecb86bdf19dd0fa2e72dbabcda28","c4c5051dd741c11840ef3f11fb4f372a16bb5aac1dc66576e89e8e6835d667e0","021016dc7a6a20","00","156e9bf3ec5be367f0a829858e9ee182cc3a6531bedced491a52fcfed841c6cb","cab50aab93410cb150fd761f2067a909d35c8a9c0114578efd9590e2d381ee02","Coinbase tx has unparseable output script"],
 9-[1263442,"000000006f27ddfe1dd680044a34548f41bed47eba9e6f0b310da21423bc5f33","000000201c8d1a529c39a396db2db234d5ec152fa651a2872966daccbde028b400000000083f14492679151dbfaa1a825ef4c18518e780c1f91044180280a7d33f4a98ff5f45765aaddc001d38333b9a02010000000001010000000000000000000000000000000000000000000000000000000000000000ffffffff230352471300fe5f45765afe94690a000963676d696e6572343208000000000000000000ffffffff024423a804000000001976a914f2c25ac3d59f3d674b1d1d0a25c27339aaac0ba688ac0000000000000000266a24aa21a9edcb26cb3052426b9ebb4d19c819ef87c19677bbf3a7c46ef0855bd1b2abe83491012000000000000000000000000000000000000000000000000000000000000000000000000002000000000101d20978463906ba4ff5e7192494b88dd5eb0de85d900ab253af909106faa22cc5010000000004000000014777ff000000000016001446c29eabe8208a33aa1023c741fa79aa92e881ff0347304402207d7ca96134f2bcfdd6b536536fdd39ad17793632016936f777ebb32c22943fda02206014d2fb8a6aa58279797f861042ba604ebd2f8f61e5bddbd9d3be5a245047b201004b632103eeaeba7ce5dc2470221e9517fb498e8d6bd4e73b85b8be655196972eb9ccd5566754b2752103a40b74d43df244799d041f32ce1ad515a6cd99501701540e38750d883ae21d3a68ac00000000","da6984906c48525f1d800b0e9b480b5fde1a3a32ad7e4cac6a0566d86b9b01a5","7820f3d2397d77068f0f0c824c4f403db89682e5ab6e82d027cb84d7beb8a08c","06970f05e70c2ec63508cdf07609cb8434","03049063c6b4e9a028","5a369775edcb1dcde9bbc88f0897bd3fd9ab0317d2906e8c10b62641c2104c54","73cee3d4b37b689f5da7251f175ff4630f2c142d7399b407d5cac65bc593b68d","Includes witness data"]
10+["Block Height,Block Hash,Block,Previous Basic Header,Basic Filter,Basic Header,Notes"],
11+[0,"000000000933ea01ad0ee984209779baaec3ced90fa3f408719526f8d77f4943","0100000000000000000000000000000000000000000000000000000000000000000000003ba3edfd7a7b12b27ac72c3e67768f617fc81bc3888a51323a9fb8aa4b1e5e4adae5494dffff001d1aa4ae180101000000010000000000000000000000000000000000000000000000000000000000000000ffffffff4d04ffff001d0104455468652054696d65732030332f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f722062616e6b73ffffffff0100f2052a01000000434104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac00000000","0000000000000000000000000000000000000000000000000000000000000000","019dfca8","21584579b7eb08997773e5aeff3a7f932700042d0ed2a6129012b7d7ae81b750","Genesis block"],

lontivero commented at 7:11 am on June 1, 2018:

Q: Given the filter for the genesis block has to contain two elements (the txid and the coinbase scriptPubKey) and that 019dfca8 is the basic filter serialized as [varint(N) | filterbytes], shouldn’t N be 02 instead of 01?

sipa commented at 7:21 am on June 1, 2018:

Read the PR title: “remove txid”.

in bip-0158/gentestvectors.go:25 in 20b692af5a outdated

25-	"github.com/roasbeef/btcutil/gcs/builder"
26+	"github.com/btcsuite/btcd/chaincfg/chainhash"
27+	"github.com/btcsuite/btcd/rpcclient"
28+	"github.com/btcsuite/btcd/wire"
29+	"github.com/btcsuite/btcutil"
30+	"github.com/btcsuite/btcutil/gcs/builder"

lontivero commented at 7:45 am on June 1, 2018:

Currently the referenced gcs builder github.com/btcsuite/btcutil/gcs/builder add the txid. Is this the new version https://github.com/Roasbeef/btcutil/blob/gcs-modifications/gcs/builder/builder.go?

Roasbeef commented at 11:49 pm on June 1, 2018:

The code used to generate these test vectors can be found here: https://github.com/Roasbeef/btcutil/commits/gcs-modifications. It’ll be merged back into btcsuite proper once this PR lands.

tamasblummer commented at 8:04 am on June 1, 2018: none

@Roasbeef I do not see any reference of the M value in https://github.com/Roasbeef/btcutil The test vectors also do not match my independent calculation with P=19 M=784931

in bip-0158.mediawiki:92 in bc10f2c9ef outdated

90+one is able to select both Parameters independently, then more optimal values
91+can be
92+selected<ref>https://gist.github.com/sipa/576d5f09c3b86c3b1b75598d799fc845</ref>.
93+Set membership queries against the hash outputs will have a false positive rate
94+of <code>2^(-P)</code>. To avoid integer overflow, the
95+number of items <code>N</code> MUST be <2^32 and <code>P</code> MUST be <=32.

jimpo commented at 11:31 pm on June 1, 2018:

Hmm, we’ll actually need to tighten the restriction on N to ensure F doesn’t overflow 64 bits. Might be enough to say that N MUST be < 2^64 / M.

Roasbeef commented at 0:00 am on June 2, 2018:

Isn’t it enough to just state that both N and M are < 2^32? As the product of those two values (with this constraint) will be < 2^64.

in bip-0158.mediawiki:86 in bc10f2c9ef outdated

82@@ -80,9 +83,13 @@ The following sections describe each step in greater detail.
83 
84 The first step in the filter construction is hashing the variable-sized raw
85 items in the set to the range <code>[0, F)</code>, where <code>F = N *
86-2^P</code>. Set membership queries against the hash outputs will have a false
87-positive rate of <code>2^(-P)</code>. To avoid integer overflow, the number of
88-items <code>N</code> MUST be <2^32 and <code>P</code> MUST be <=32.
89+M</code>. Customarily, <code>M</code> is set to <code>2^P</code>. However, if

jimpo commented at 11:33 pm on June 1, 2018:

Drop the sentence Customarily, M is set to 2^P. It’s not adding anything and just raises questions. You can simply say that parameters are selected to maximize compression efficiency and link to the analysis.

Roasbeef commented at 0:00 am on June 2, 2018:

IMO it does add something as if one if familiar with the regular selection of parameters, why might wonder why we didn’t just set M to 2^P.

jimpo commented at 3:57 am on June 2, 2018:

If someone is really curious, that’s what the link is for. But I guess leave it if you feel strongly.

in bip-0158.mediawiki:289 in bc10f2c9ef outdated

297+parameters.
298+
299+The parameter <code>P</code> MUST be set to <code>19</code>, and the parameter
300+<code>M</code> MUST be set to <code>784931</code>. Analysis has shown that if
301+one is able to select <code>P</code> and <code>M</code> independently, then
302+setting <code>M=1.497137 * 2^Q</code> is close to optimal

jimpo commented at 11:35 pm on June 1, 2018:

s/Q/P/

Roasbeef commented at 0:00 am on June 2, 2018:

Fixed!

in bip-0158.mediawiki:327 in bc10f2c9ef outdated

322@@ -323,7 +323,8 @@ though it requires implementation of the new filters.
323 
324 We would like to thank bfd (from the bitcoin-dev mailing list) for bringing the
325 basis of this BIP to our attention, Greg Maxwell for pointing us in the
326-direction of Golomb-Rice coding and fast range optimization, and Pedro
327+direction of Golomb-Rice coding and fast range optimization, Pieter Wullie for
328+his analysis of optimal gcs parameters, and Pedro

jimpo commented at 11:36 pm on June 1, 2018:

nit: s/gcs/GCS/ for consistency with the rest of the document.

Roasbeef commented at 0:00 am on June 2, 2018:

Fixed in all areas other than the pseudocode.

jimpo changes_requested

jimpo commented at 11:41 pm on June 1, 2018: contributor

The pseudo-code needs to be updated. It still calculates F = N << P instead of F = N * M.

Roasbeef commented at 0:00 am on June 2, 2018: contributor

@tamasblummer the code to generate those test vectors (the gcs stuff) is found at: https://github.com/Roasbeef/btcutil/commits/gcs-modifications

How do your generated test vectors differ? Are you excluding the txid in them now?

tamasblummer commented at 3:36 am on June 2, 2018: none

@Roasbeef fixed my range mapping. Now we are aligned.

lontivero referenced this in commit 4b6717db7a on Jun 2, 2018

lontivero cross-referenced this on Jun 2, 2018 from issue Update GSC filters to match bitcoin/bip158 PR by lontivero

NicolasDorier referenced this in commit 58828f4261 on Jun 3, 2018

jimpo commented at 5:18 pm on June 7, 2018: contributor

There are still N << P instead of N * M in hashed_set_construct and gcs_match pseudocode.

Roasbeef force-pushed on Jun 8, 2018

Roasbeef commented at 4:03 am on June 8, 2018: contributor

@jimpo fixed in latest version, squashed the fix up commits.

Roasbeef force-pushed on Jun 8, 2018

jimpo commented at 4:10 pm on June 8, 2018: contributor

Need to call hashed_set_construct with M in the construct_gcs pseudocode.

Sjors commented at 7:20 pm on June 15, 2018: member

Maybe add a Discussion section like here with links to the main dev list threads? I recall having difficulty finding the first one after seeing your presentation (because I searched for “neutrino”).

BIP-0158: remove the extended filter type 4a85759f02

BIP-0158: allow filters to define values for P and M, reparameterize default filter 1c2ed6dce3

Roasbeef force-pushed on Jul 4, 2018

BIP-0158: switch to prev output scripts, skip all OP_RETURN 6a4e819829

BIP-0158: regenerate test vectors for fp=19, new reg filter, no ext filter

In this commit, we simplify the code that generates the test vectors to
only generate filters for a target fp of 19, and also only for the
regular filter, as it's the only filter type currently defined.

The test vectors have also been updated to include the previous output
scripts for all input within a block as these are now required to
construct the regular filter.

Finally, the generation code has been updated to properly fetch the
previous input scripts to the generation code can verify the filter it
generates manually against the end server.

ac76644533

Roasbeef force-pushed on Jul 5, 2018

luke-jr merged this on Jul 5, 2018

luke-jr closed this on Jul 5, 2018

stevenroose cross-referenced this on Jul 4, 2019 from issue BIP-158: Remove some remaining "extended" mentions by stevenroose

BIP-0158: remove extended filter, remove txid from regular filter, reparameterize gcs params #687