Double speed for BSGS

[albertobsd]

Hi every one, hi JLP i hope you read this.

Current approach for BSGS is more o less the, example:

Target Key 99
known range 75-100 (Like puzzles etc...)
Baby step 5  = { 0,1,2,3,4}
Giant step 5 = {0,5,10,15,20}

First subtraction to move key to the BSGS range
99(key) - 75(Base range) = 24

New Target Key 24

Giant step 0
24 - 0 = 24 is on Baby Table? NO

Giant step 1
24 - 5 = 19 is on Baby Table? NO

Giant step 2
24 - 10 = 14 is on Baby Table? NO

Giant step 3
24 - 15 = 9 is on Baby Table? NO

Giant step 4
24 - 20 = 4 is on Baby Table? YES (HIT)

Calcualted KEY is Giant Step 4 plus Baby step 4 PLUS [b]Base range[/b], this is 20 + 4 + 75 = 99

Here we covered from 0 to 25

But since negative Numbers have the same X value of positive numbers that mean that our current baby table is also valid for:
Baby step 5 = {-4,-3,-2,-1,0,1,2,3,4}

We can move exclude the 0 for this example and keep some table like:
Baby step 5 = {-5,-4,-3,-2,-1,1,2,3,4,5}

We can handle the Zero element in some especial case, or include it and use an odd baby table,

So to work with this new Baby table we need to rearange the Giant steps just a litle.

Giant step 5 = {5,15,25,35,45}

| GS | RANGE BS |
|  5 | 0  - 10  |
| 15 | 10 - 20  |
| 25 | 20 - 30  |
| 35 | 30 - 40  |
| 45 | 40 - 50  |

So we covered a Double Range from 0 to 50 with the same number of Operations, this is double speed.

I already implement this on my tool keyhunt.

[hskun]

that is good point.
I tested the speed of keyhunt and my modified BSGS based JLP.

time ./keyhunt -m bsgs -t 8 -f tests/63.pub -k 512 -s 0 -S -b 63
[+] Version 0.2.230519 Satoshi Quest, developed by AlbertoBSD
[+] Threads : 8
[+] K factor 512
[+] Turn off stats output
[+] Mode BSGS sequential
[+] Opening file tests/63.pub
[+] Added 1 points from file
[+] Bit Range 63
[+] -- from : 0x4000000000000000
[+] -- to : 0x8000000000000000
[+] N = 0x100000000000
[+] Bloom filter for 2147483648 elements : 7361.33 MB
[+] Bloom filter for 67108864 elements : 230.04 MB
[+] Bloom filter for 2097152 elements : 7.19 MB
[+] Allocating 32.00 MB for 2097152 bP Points
[+] processing 2147483648/2147483648 bP points : 100%
[+] Making checkums .. ... done
[+] Sorting 2097152 elements... Done!
[+] Writing bloom filter to file keyhunt_bsgs_4_2147483648.blm .... Done!
[+] Writing bloom filter to file keyhunt_bsgs_6_67108864.blm .... Done!
[+] Writing bP Table to file keyhunt_bsgs_2_2097152.tbl .. Done!
[+] Writing bloom filter to file keyhunt_bsgs_7_2097152.blm .... Done!
[+] Thread Key found privkey 7cce5efdaccf6808
[+] Publickey 0365ec2994b8cc0a20d40dd69edfe55ca32a54bcbbaa6b0ddcff36049301a54579
All points were found00000000
[+] Thread 0x7cd0a00000000000
real 10m32.613s
user 83m49.550s
sys 2m58.607s

./bsgs -t 8 63.txt
BSGS v1.3 Block Bloom Filter
BabyStep:0x80000000 (2^31.00)
Start:4000000000000000
Stop :8000000000000000
Keys :1
Number of CPU thread: 8
FPP(false positive probability): 0.000100
Bloom filter size:6743.5 MB
Fill baby step for 65EC2994B8CC0A20D40DD69EDFE55CA32A54BCBBAA6B0DDCFF36049301A54579
BabyStep Thread 1: 0x10000001 -> 0x20000000
BabyStep Thread 2: 0x20000001 -> 0x30000000
BabyStep Thread 6: 0x60000001 -> 0x70000000
BabyStep Thread 3: 0x30000001 -> 0x40000000
BabyStep Thread 5: 0x50000001 -> 0x60000000
BabyStep Thread 7: 0x70000001 -> 0x80000000
BabyStep Thread 0: 0x1 -> 0x10000000
BabyStep Thread 4: 0x40000001 -> 0x50000000
[23.05 MKey/s][Count 2^31.00][01:30]
GiantStep Thread 3: 5800000000000000
GiantStep Thread 0: 4000000000000000
GiantStep Thread 4: 6000000000000000
GiantStep Thread 1: 4800000000000000
GiantStep Thread 2: 5000000000000000
GiantStep Thread 5: 6800000000000000
GiantStep Thread 6: 7000000000000000
GiantStep Thread 7: 7800000000000000
[25.66 MKey/s][Count 2^30.46][58s]
Key Pub: 0x0365EC2994B8CC0A20D40DD69EDFE55CA32A54BCBBAA6B0DDCFF36049301A54579
Priv: 0x7CCE5EFDACCF6808

Done: Total time 02:31

I will try to add your point to my version.
Thanks for sharing.

[albertobsd]

If you run my program with the data already processed from file it will take less time, the program waste a litte more time writing the files and making checksums.

Also it may sound a little cheat but BSGS from JLP divide the whole range in Ranges of the same size. if you notice

GiantStep Thread 7: 7800000000000000

That thread goes from 7800000000000000 to 8000000000000000 so the time of 2:31 time is really the time from 7800000000000000 to 7CCE5EFDACCF6808 (other threads also have finished the half of their respectives sub-ranges)

I did ad test with the same key data already preloaded check:

time ./keyhunt -m bsgs -t 8 -f tests/63.pub -k 512 -s 0 -S -b 63 -6
[+] Version 0.2.230519 Satoshi Quest, developed by AlbertoBSD
[+] Threads : 8
[+] K factor 512
[+] Turn off stats output
[W] Skipping checksums on files
[+] Mode BSGS sequential
[+] Opening file tests/63.pub
[+] Added 1 points from file
[+] Bit Range 63
[+] -- from : 0x4000000000000000
[+] -- to   : 0x8000000000000000
[+] N = 0x100000000000
[+] Bloom filter for 2147483648 elements : 7361.33 MB
[+] Bloom filter for 67108864 elements : 230.04 MB
[+] Bloom filter for 2097152 elements : 7.19 MB
[+] Allocating 32.00 MB for 2097152 bP Points
[+] Reading bloom filter from file keyhunt_bsgs_4_2147483648.blm .... Done!
[+] Reading bloom filter from file keyhunt_bsgs_6_67108864.blm .... Done!
[+] Reading bP Table from file keyhunt_bsgs_2_2097152.tbl .... Done!
[+] Reading bloom filter from file keyhunt_bsgs_7_2097152.blm .... Done!
[+] Thread Key found privkey 7cce5efdaccf6808
[+] Publickey 0365ec2994b8cc0a20d40dd69edfe55ca32a54bcbbaa6b0ddcff36049301a54579
All points were found
[+] Thread 0x7ccf400000000000
real    0m52.851s
user    6m42.925s
sys     0m3.184s

I my case that time was efectively from 4000000000000000 to 7cce5efdaccf6808

Now i suggest this publickey, same range

02217daf90deb73bdf8b6709bb42093fdfaff6573fd47b630e2d3fdd4a8193a74d

Result:

time ./keyhunt -m bsgs -t 8 -f other63.txt -k 512 -s 0 -S -b 63 -6
[+] Version 0.2.230519 Satoshi Quest, developed by AlbertoBSD
[+] Threads : 8
[+] K factor 512
[+] Turn off stats output
[W] Skipping checksums on files
[+] Mode BSGS sequential
[+] Opening file other63.txt
[+] Added 1 points from file
[+] Bit Range 63
[+] -- from : 0x4000000000000000
[+] -- to   : 0x8000000000000000
[+] N = 0x100000000000
[+] Bloom filter for 2147483648 elements : 7361.33 MB
[+] Bloom filter for 67108864 elements : 230.04 MB
[+] Bloom filter for 2097152 elements : 7.19 MB
[+] Allocating 32.00 MB for 2097152 bP Points
[+] Reading bloom filter from file keyhunt_bsgs_4_2147483648.blm .... Done!
[+] Reading bloom filter from file keyhunt_bsgs_6_67108864.blm .... Done!
[+] Reading bP Table from file keyhunt_bsgs_2_2097152.tbl .... Done!
[+] Reading bloom filter from file keyhunt_bsgs_7_2097152.blm .... Done!
[+] Thread Key found privkey 7fffffffffffffff
[+] Publickey 02217daf90deb73bdf8b6709bb42093fdfaff6573fd47b630e2d3fdd4a8193a74d
All points were found

real    0m55.747s
user    7m4.271s
sys     0m3.497s

In my test the key 7fffffffffffffff only take 3 seconds more than the key 7CCE5EFDACCF6808

[hskun]

You are right.

In fact, I have been studying a binary search (judging by subtracting the key to be found from the start key and end key) to quickly find the key to be found. Do you have any good insights？

[winnery2022]

You are right.

In fact, I have been studying a binary search (judging by subtracting the key to be found from the start key and end key) to quickly find the key to be found. Do you have any good insights？

Hi) will be version for windows? Tnx.)!