BigStepGiantStep algorithm for Nvidia GPUs

I created my version of the BigStepGiantStep algorithm specifically for Nvidia graphics cards, working with Cuda and Windows x64 only. Check it out on GitHub. Would love to hear about your performance results.

It seems that you know a bit bsgs algo and x86 assembler.... So I would like to ask you one question. I already modified Jean's bsgs for curve "r1" (btc uses k1) What is the meaning of start value? Jean even need start and stop values for k1 and k2. Does the searched k must lie in this interval?

awesome. will let you know speed on various GPUs once I run it

Great. I thin your project will be more usable then JLP cangaro. Tuning JLP kangaroo is a real big shit !!!!

I tested your BSGS on GTX 1660s, the speed was significantly slower than JeanLucPons Kangaroo: BSGS-cuda => 330 Mkey/s Kangaroo 2.2 => 450 Mkey/s

Need real tests on how many time need for find exaple pprivkey, what code find faste.

COBRAS, then how about you start testing and benchmarking? Or should others do that for you too?

with v1.2 and single 2080ti i solve example pubkeys in range: start: 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000 end: 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff in 28minutes with params -w 26: Here is pubkeys for searching: it is 6 times faster then original bsgs from JLP based on CPU.

Ok, and how fast it would be with interval 000000000....00000000 Ffffffffffff......fffffffffffff ?

How many bytes of memory do you need to store one babystep? Hashtable uses GPU memory or global ram?

Yeah something like sarcasm. COBRAS is a lazy lurker. And you can see, that his last post does not make any sense.

RTX 3070 = 1,000 MKey/s Default settings. Have not tinkered with settings to see if GPUs can gain any speed.

I ran the same test as Etar and JLP, with 16 pubkeys: Total time: For comparison, JLP with CPU only took 3 hours and 35 minutes.

each baby step used 8 bytes memory. HT stored in GPU memory. with -w 26 and -htsz 25(default), app generate 2^26 babysteps that stored in HT with size (2^25 + 2^26 )*8 bytes

Thank Etar I think BSGS-cuda is work better than JLP BSGS JLP BSGS is good but using very long time (for my GPU) I test first sample command from github page speed result (GPU GTX 1050 on laptop) Result

Mantadory update v.1.2.1 *bug fixed with multy GPU searching.

JLP's BSGS does not support GPU; his is CPU only. Side by side tests of BSGS Cuda and JLP's Kangaroo... 4 pubkeys all in 65 bit range: Kangaroo total time = 2 mins 34 seconds: BSGS Cuda total time = 1 min 29 seconds: For at least this range (and probably more up to a certain size) the BSGS Cuda program will be faster, for checking multiple pubkeys, as the spin up time between pub keys (finding a pub key and moving to the next pub key) is a lot faster than kangaroo program.

Correct, Sorry I forget it, I mean it use very slow for my laptop work , sometime I give up to end task for waiting longtime overnight

work fast on 65 bit range still limited for power can fine on 120 bit right and still limited to fine range that on 65 bit nearly point to hit key

searching these 2 pubkeys in 100 bit range 034786ac12686480348261b5dce84efcffc27b56b512ca793a09229ed06d63058d 027ede4f01c7dd2690603cd0449fc4e4ac9ca2d11de2404ef2285ab897d2645391 some one can help me to understand what hardware gpu's models you are using for above result data ? is there any ubuntu compilation/sourcecode program available, for cuda 8.0 and ccap 20, g++ 4.8 love to see your updates