Brannon King
e72f99ac3f
renamed package to lbcutil, updated refs to it
2021-09-10 16:37:45 -04:00
Conner Fromknecht
9e5f4b9a99
gcs/gcs: use sort.Slice instead of sort.Sort, remove uint64Slice
...
This commit removes the uint64Slice type and performs sorting during
filter construction and ZipMatchAny using sort.Slice. The benchmarks
indicated that this speeds up BuildGCSFilter and ZipMatchAny by 10-12%,
likely to the overhead of needing to resolve the sort.Interface methods.
The benchmarks indicate that this improvement is not present for the
smallest query size in our benchmarks, i.e. 100 elements, but the
reduction is only about 3%. This would indicate the at these small
values, the use of reflection is actually slightly slower than interface
method resolution in total.
2019-04-25 16:57:16 -07:00
Conner Fromknecht
8cea9a2e28
gcs/gcs: ensure match zero hash
2019-04-25 16:42:51 -07:00
Conner Fromknecht
6f51807c27
gcs/gcs_test: match zero element
2019-04-25 16:42:51 -07:00
Jim Posen
4c204d6978
gcs/builder: Omit all OP_RETURN scripts from basic filter.
2019-02-06 16:39:14 -08:00
Conner Fromknecht
bf1e1be935
gcs/gcs_test: adds generic tests for all matching strats
2019-01-11 20:11:46 -08:00
Conner Fromknecht
36301f211d
gcs/gcsbench_test: adds Zip/HashMatchAny comparsions
2019-01-11 20:11:46 -08:00
Conner Fromknecht
784cec0650
gcs/gcs: adds HashMatchAny for large filter queries
2019-01-11 20:11:46 -08:00
Olaoluwa Osuntokun
ab6388e0c6
gcs/builder: remove the AddScript method as it's no longer used ( #121 )
...
In this commit, we remoec the AddScript method as it's no longer used,
and AddEntry should be used in place for adding pkScripts to the
filters.
2018-07-06 18:06:48 -05:00
Olaoluwa Osuntokun
7eb98d5700
gcs/builder: skip zero nil outputs scripts
2018-07-06 17:32:55 -05:00
Olaoluwa Osuntokun
46d39f9c2c
gcs/builder: skip OP_RETURN outputs when for regular filter
2018-07-06 17:32:55 -05:00
Olaoluwa Osuntokun
98e65a007d
builder: remove outpoint methods
2018-07-06 17:32:55 -05:00
Olaoluwa Osuntokun
d3e82fcd5d
gcs: switch basic filter to index prev output scripts of all inputs
2018-07-06 17:32:55 -05:00
Olaoluwa Osuntokun
e993e6ce27
gcs/builder: remove extended filter
...
In this commit, we remove the extended filter as it doesn't have a clear
use atm.
2018-07-06 17:32:55 -05:00
Olaoluwa Osuntokun
0ecd90b8d6
gcs: update fp and modulus values based on recent optimality analysis
...
In this commit, we decrease the default fp rate to 19, or 1/2^19. We do
this as recent analysis by sipa on the bitcoin dev mailing list has
shown that optimally, we can use a value of 2^19 for the fp rate, while
use n=1.497137*2^P rather than n directly. As a result, we can shrink
the filter size by quite a bit, while still maintaining a sane false
positive value.
2018-07-06 17:32:55 -05:00
Olaoluwa Osuntokun
996307736e
gcs/builder: update builder tests to use addr script directly
2018-07-06 17:32:55 -05:00
Olaoluwa Osuntokun
3b3422dc54
gcs/builder: update regular filter to exclude txid
...
In this commit, we update the regular filter to exclude the txid, as in
most cases we can use the output script for the same purpose.
2018-07-06 17:32:55 -05:00
Olaoluwa Osuntokun
d4cc87b860
gcs: properly only use hash of pkscript to insert into filter
...
This commit fixes a mistake during the rebase process meant to include
this commit in its entire:
dfb640c571
2018-05-23 20:27:03 -07:00
Olaoluwa Osuntokun
45edb4b6e5
gcs: fix stray import
2018-05-22 17:48:27 -07:00
Olaoluwa Osuntokun
b9afb0b986
gcs/builder: fix linter errors
2018-05-15 19:14:18 -07:00
Jim Posen
ad0070fa44
gcs/builder: Deduplicate items before creating block filters.
2018-05-15 19:14:18 -07:00
Jim Posen
cbc2d0fee6
Allow construction of empty filters.
2018-05-15 19:14:18 -07:00
Jim Posen
884680ddbd
Serialize filter with N as a VarInt instead of fixed-size.
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
9da482119c
gcs/builder: revert recursion of push datas in p2sh/witness
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
54b6d534d2
gcs: extract fast reduce into distinct func, add comments
2018-05-15 19:14:18 -07:00
Alex
5151e0586d
gcs/builder: move tx hash from extended into basic filter
2018-05-15 19:14:18 -07:00
Alex
6cffb54a22
gcs/builder: recurse into P2SH/witness scripts
2018-05-15 19:14:18 -07:00
Alex
03a7f9b01f
gcs/builder: fix tests by rebuilding filter, making failure to match fatal
2018-05-15 19:14:18 -07:00
Alex
dabaf053db
gcs: update modulo algorithm to fast range per gmaxwell's suggestion
...
The BIP will now specify that the fast range described at the URL
below is used instead of modulo:
https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
2018-05-15 19:14:18 -07:00
Alex
0878c162dd
gcs: update benchmarks to use correct import
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
e14ee486e6
gcs: fix constant overflow for 32-bit systems
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
18097a52c4
gcs: explicitly optimize inner loop of gcs filter computation
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
c26776fe48
gcs: add an extra benchmark for a filter with 100k items
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
e87fef40f3
gcs: ensure benchmarks aren't optimized away by the compiler
...
This commit modifies the benchmarks a bit to ensure that the
computations themselves aren’t optimized away. We do this by binding
each variable to a local variable, and them ultimately a variable at
the package level scope.
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
5a770ec85e
gcs/builder: an empty filter has a zero-hash
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
65172ea539
gcs/builder: ignore scripts with no data pushes
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
b3d8578868
gcs: add witness stack items to filter, update tests
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
c01c00e8b4
gcs: check to see if sigScript exists before adding it
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
0830c7046f
gcs: fix slight typo in docs, 2^-n not 2^-1
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
c59d7e8fba
gcs: pre-allocate capacity of slice for uncompressed filter values
...
This change will reduce the total number of allocations required to
create/store the allocated filter as we’ll now perform a _single_
allocation, rather than one each time the the dynamically size slice
reaches capacity.
2018-05-15 19:14:18 -07:00
Olaoluwa Osuntokun
0f2eb80fdb
gcs: add some line spacing, wrap comments to 80 characters
2018-05-15 19:14:18 -07:00
Alex
e3c79234e6
gcs/builder: Add pre-BIP block filter and header calculations.
2018-05-15 19:14:18 -07:00
Alex
f74edf2c4d
gcs: allow optional de/serialization of N and P parameters
2018-05-15 19:14:18 -07:00
Alex
ca65f28ca1
Ignore error from txscript.PushedData
2018-05-15 19:14:18 -07:00
Alex
12e95e2790
gcs: improve test coverage for builder
2018-05-15 19:14:18 -07:00
Alex
197462ade8
README.md fixes
2018-05-15 19:14:18 -07:00
Alex
856e3a320d
Change OutPoint index encoding to little-endian to match Bitcoin
2018-05-15 19:14:18 -07:00
Alex
119a03a3ca
Add comment to DefaultP to fix lint issue with exported constant.
2018-05-15 19:14:18 -07:00
Alex
6654eb61e4
Add filter builder and some tests
2018-05-15 19:14:18 -07:00
Alex
53c8e22157
Change tests to use gcs.Filter instead of custom interface
2018-05-15 19:14:18 -07:00
