Keyhunt - development requests - bug reports

[SlaitX]

@SlaitX

I wrote the binary bloom filter update for Keyhunt. Hit me up if you have any issues or questions.

Great job. But I tested your version.
I have also already solved the problem with the fuse filter and added an XOR filter as well. The most memory-efficient is undoubtedly the fuse filter. It saves more memory.
For large filters of 256 GB, I implemented a file-based version of writing all the points, which is why the formation of this filter takes a long time. I need to study your code to understand whether you have solved the problem of forming three filters or not. Because the FUSE filter requires all the points in memory or splitting them into packets.

Regarding the differences between the versions.

Alberto's version
./keyhunt -m bsgs -f test.txt -r 8aa15e21125e3806:9fa15e21125e3806 -k 64 -S -s 1 -t 16
Thread 0x8e0ede21125e3806 s in 14 seconds: ~17 Pkeys/s (17494172436454253 keys/s)


Punk_design version
./keyhunt -m bsgs -f test.txt -r 8aa15e21125e3806:9fa15e21125e3806 -k 64 -S -s 1 -t 16
Thread Key found privkey 90e15e21125e3806 ~20 Pkeys/s (20406935811522560 keys/s)

My version
keyhunt -m bsgs -f test.txt -r 8aa15e21125e3806:9fa15e21125e3806 -k 64 -S -s 1 -t 16 -x fuse
Thread 0x90d6be21125e3806 | [446841525528166400 keys][14 sec][~31 Pkeys/s (31917251823440457 keys/s)]

Even the Bloom filter version has a faster speed.
keyhunt -m bsgs -f test.txt -r 8aa15e21125e3806:9fa15e21125e3806 -k 64 -S -s 1 -t 16 -x bloom
Thread 0x8e9f5e21125e3806 | [287139660616957952 keys][11 sec][~26 Pkeys/s (26103605510632541 keys/s)]

This speed depends not only on the filter but also on monthly code optimization. I updated file in github.

And size filters.
your version (fuse filter -k 64) 751 mb
my version (fuse filter -k 64) 598 mb

https://github.com/Slait/Keyhuntbsgs

[punk_design]

SlaitX

Thanks for the update.

I see you implemented a 16 bit binary fuse filter - false alarm rate = 0.00001

I opted for a 20 bit binary fuse filter - false alarm rate = 0.00000095, (kept it true to the original version).

However, after seeing you speed and performance improvement with a 16 bit binary fuse filter. I modified mine and tested it.
I did get similar performance improvement and memory savings as you did.

With a 16-bit binary fuse filter with false alarm (0.00001)
My file size is ~600 Mb now (20% reduced) and my performance is another 20% improved as well. Now it only needs 2.25 bits per element in the 16 bit table, instead of 2.81 bits per elements in the 20 bit table.

The original false alarm rate might have been too conservative with respect to performance. The risk of performing the binary search is more costly than the filter search, hence the very low false alarm rate.

Next, I'll try a 14 bit table - false alarm rate of 0.00006103. This should make it faster and get another 12% reduction in memory and performance increase. Eventually, the false alarms will negate any performance improvement. Just trying to find the point in which further reductions no longer bring better performance.

[punk_design]

https://github.com/punk-design/keyhunt_binary_fuse_filter/blob/main/BSGS_Binary_Fuse_Analysis.png

Looks like 12 bit might be the best bang for the buck. If I make some further memory optimizations to pack 12 bits into 16 bit or reorder to store into memory more efficient, then it'll perform like 16 bit variant. However, there is an additional 25% memory savings over 16 bit approach. So increasing the search space by 25% with a 6% reduction in processing, puts the processing ahead in terms of performance.

This is 40% memory savings over my original approach of 20 bit. Turns out the defined false alarms can be significantly relaxed, this might be because the hash is uniform and not prone to false alarms.