BSGS solver for cuda

[sky59sky59]

Not sure which author you are referring to, but if this is NotATether's version

yes it is, he informed me already about some problems and I should wait until he corrects them

but as I have written already, I could not resist and I migrated it to R1 curve just to try what it does...

yes, you are right, as it is now it behaves a bit non repetitive way, for me it found the keys but solving the same problem more time the time to resolve was from zero (!) seconds to minutes, but I tried only fewer bits search as it was considerably slower than JLP 125b version searching more bits range

I also noticed he changed DP mask meaning (not from left to rigth as original but from right to left) and he "regrets" this as it made me confused

also I noticed there is a problem when having public key in configuration file to solve in 03 mode (only x coordinate)  something is wrong as it falsely reports "point not lie on curve", when in 04 mode it seems to be ok

but let us see and wait if NotATether manages to bring it to life

I was already thinking if there is any way as to test the program before starting it for months..., would it be a change to provide instead of random numbers where algo starts some precalculated values so program would find a test private key in hours? or is there already a way to test the code?

Sorry, I do not understand abbreviation "IMO"  what does it mean?

[davidjjones]

New release v1.4.0
supported compressed/uncompressed format public keys
removed binsort program (don`t need sorted array any more)
baby array need only first time to create HT (or rebuild HT when -htsz changed)
After HT created and saved, next time you will need less ram and only HT, giant array to launch.
...

Thanks for your great code.
Is there a limit to the number of pubkeys in the input txt file?

Here is the list of 2800 top richest pubkeys:
https://pastebin.com/YMr3BaiU

[a.a]

Interesting List you have. I would have given merits If I had some.

I don't think that they can be effectively searched in parallel. You have to divide each pubkey and check it with the babysteps. So not only do you need to make very expensive global memory lookup (GPU has slow global and super fast local memory) and load each key.

So if you would search multiple keys you would effectively reduce the performance by them. Like 10 keys in parallel means 10 times slower. 2800 keys means 2800 times slower.

[WanderingPhilospher]

Is there a limit to the number of pubkeys in the input txt file?

I am sure there will be a limit, but it is probably in the millions. For similar programs, it usually caps out at around 30 million addresses, pubkeys, xpoints...

a.a.
Have you ran this program yet? It's just that some of your answers make it seem like you have not ran it at all.

The program does not check keys in parallel, it runs range with one pubkey, once finished, it moves to the next, until the last pubkey has been checked for that specific range.

[a.a]

I think I made myself not clear. My native language is German. I apologize. I Looked at it with my programmers eyes.

As you already explained few days ago, cuda BSGS is searching the keys one after another, not in parallel. I know that, I read carefully . With my previous post I meant that even if it would run in parallel it would slow down as described. So read my post in conjunctive and if someone would modify it to process in parallel I expect that behaviours.

[WanderingPhilospher]

I think I made myself not clear. My native language is German. I apologize. I Looked at it with my programmers eyes.

As you already explained few days ago, cuda BSGS is searching the keys one after another, not in parallel. I know that, I read carefully . With my previous post I meant that even if it would run in parallel it would slow down as described. So read my post in conjunctive and if someone would modify it to process in parallel I expect that behaviours.

Gotcha...no worries, I just did not want to mislead anyone or anyone mislead anyone lol.

But you are right, if it did search in parallel, performance would drop, but I believe it would be due to the giant steps (CPU performs the baby steps). If one had higher end card and wanted to search 2 pubkeys, then I think it would be worth it, to search 2 at same time. I have been running the program on slower card, my test card, for a few days now. The purpose is to see if there is a benefit or angle to attack the 120, 125, 130, etc keys where public key is exposed. More to come with this...

[davidjjones]

Interesting List you have. I would have given merits If I had some.

I don't think that they can be effectively searched in parallel. You have to divide each pubkey and check it with the babysteps. So not only do you need to make very expensive global memory lookup (GPU has slow global and super fast local memory) and load each key.

So if you would search multiple keys you would effectively reduce the performance by them. Like 10 keys in parallel means 10 times slower. 2800 keys means 2800 times slower.

Is there a limit to the number of pubkeys in the input txt file?

I am sure there will be a limit, but it is probably in the millions. For similar programs, it usually caps out at around 30 million addresses, pubkeys, xpoints...

a.a.
Have you ran this program yet? It's just that some of your answers make it seem like you have not ran it at all.

The program does not check keys in parallel, it runs range with one pubkey, once finished, it moves to the next, until the last pubkey has been checked for that specific range.

Thanks for your good explanation, I got how it works.
So multiple xpoints checking (in parallel) is only possible with KeyHunt-CUDA.

[NotATether]

I continue to work to migrate also  Kangaroo256 to r1 curve but I was told by the author to wait a bit until he updates hastables (?)

Not sure which author you are referring to, but if this is NotATether's version, I would not use it. Very buggy and last known speed is compromised and the program does not find keys.
The only thing needed, IMO, to upgrade JLPs original Kangaroo to be able to search a 256 bit range, was to update the limited 128 bit store function to a 256 bit store function (plus the + - and type bits) so the program could solve key. I have not looked at the code of the new 256bit version, but it seems it does not find keys.

Original JLP Kangaroo, you can search a 256 bit range for a key but since it only stores 128 bits for the distances, you will not solve key properly because it is missing 128 bits of the distance (private key), which is needed to reconstruct the private key of the pub key you are searching for.

Yep he was referring to mine.

You should not try to update it to 256-bit store - it's too complicated since you'll have to find a new home for the two flag bits at the end of each store (the ones which limit to the actual search range to 126 bits). This is how the hashtable got screwed.

It is more logical to update it to a 254-bit store instead so you don't have to move the flag bits anywhere.

[WanderingPhilospher]

I continue to work to migrate also  Kangaroo256 to r1 curve but I was told by the author to wait a bit until he updates hastables (?)

Not sure which author you are referring to, but if this is NotATether's version, I would not use it. Very buggy and last known speed is compromised and the program does not find keys.
The only thing needed, IMO, to upgrade JLPs original Kangaroo to be able to search a 256 bit range, was to update the limited 128 bit store function to a 256 bit store function (plus the + - and type bits) so the program could solve key. I have not looked at the code of the new 256bit version, but it seems it does not find keys.

Original JLP Kangaroo, you can search a 256 bit range for a key but since it only stores 128 bits for the distances, you will not solve key properly because it is missing 128 bits of the distance (private key), which is needed to reconstruct the private key of the pub key you are searching for.

Yep he was referring to mine.

You should not try to update it to 256-bit store - it's too complicated since you'll have to find a new home for the two flag bits at the end of each store (the ones which limit to the actual search range to 126 bits). This is how the hashtable got screwed.

It is more logical to update it to a 254-bit store instead so you don't have to move the flag bits anywhere.

Agreed...really, can it be bumped up to a 160-bit store plus the 2 flag bits, easier than the 254-bit store? Then the program could at least cover up to the last 160 bit key for the puzzle/challenge transaction.

[sky59sky59]

Yep he was referring to mine.

You should not try to update it to 256-bit store - it's too complicated since you'll have to find a new home for the two flag bits at the end of each store (the ones which limit to the actual search range to 126 bits). This is how the hashtable got screwed.

It is more logical to update it to a 254-bit store instead so you don't have to move the flag bits anywhere.

In a meantime I found that your updated Div() is faulty, why not to keep original functions? And it seems more functions are faulty that are tested in Check()

you can try this:  (gives wrong results)

I would be probably the happiest man in universe if with all your knowledge and experience just updated 125bit version to 254bit version, just absolutely unnecessary staff without any improvements   then I see your great success!!


 // Div -------------------------------------------------------------------------------------------
  tTotal = 0.0;
  ok = true;
  for (int i = 0; i < 2 && ok; i++) {


    a.SetBase16("D51263D15FC81DE32C5CB69070ABDF3D58A2028184E15F3A6C56EB8A787C81DB");
    b.SetBase16("2AED15B34BE1B98EE4246FB3F447059A");
    // a.Rand(BISIZE);
    //b.Rand(BISIZE/2);
    d.Set(&a);
    e.Set(&b);

 printf("a= %s\n", a.GetBase16().c_str());
 printf("b= %s\n", b.GetBase16().c_str());
 printf("d= %s\n", d.GetBase16().c_str());
 printf("e= %s\n", e.GetBase16().c_str());

    t0 = Timer::get_tick();
    a.Div(&b, &c);
 printf("a/b= %s\n", a.GetBase16().c_str());   
 printf("rem= %s\n", c.GetBase16().c_str());
   
    t1 = Timer::get_tick();
    tTotal += (t1 - t0);

    a.Mult(&e);
    a.Add(&c);
    if (!a.IsEqual(&d)) {
     ok = false;
      printf("Div() Results Wrong \nN: %s\nD: %s\nQ: %s\nR: %s\n",
        d.GetBase16().c_str(),
        b.GetBase16().c_str(),
        a.GetBase16().c_str(),
        c.GetBase16().c_str()
        
      );
      return;
    }

[NotATether]

Agreed...really, can it be bumped up to a 160-bit store plus the 2 flag bits, easier than the 254-bit store? Then the program could at least cover up to the last 160 bit key for the puzzle/challenge transaction.

254 bits is easier to make than 160 bits because I can just update the structures from

int128_t

to int256_t

in all occurrences without having to make any other changes.

[Etar]

This is the maximum that I can squeeze out of my 2080ti card:
16 pubkeys from JLP example solved in 1m 23s

Code:

NewFINDpubkey= (2375c86aa2a807fd50e4b1a2a65820244e704b8eabc8eb4dc0517393aff0c647, fad56264ae29d620205a68792091b64ae262bba359f8d013ce904d595e790ccf)
***************************
GPU#0 Cnt:0000000000000000000000000000000000000000000000000000000000000001
GPU#0 Cnt:0000000000000000000000000000000000000000000000003388000000000001 823MKey/s x1073741824 2^29.69 x2^31=2^60.69
GPU#0 Cnt:0000000000000000000000000000000000000000000000006754000000000001 826MKey/s x1073741824 2^29.69 x2^31=2^60.69
***********GPU#0************
KEY!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e7ad38337c7f173c7
Pub: 55b95bef84a6045a505d015ef15e136e0a31cc2aa00fa4bca62e5df215ee981b3b4d6bce33718dc6cf59f28b550648d7e8b2796ac36f25ff0c01f8bc42a16fd9
****************************
Found in 5 seconds
GPU#0 job finished
Working time 00:01:23s
Total time 00:06:00s

Used two hashtables:
first  for GPU without xpoint position, only xpoint 32bit + size htsz, totaly 32+29 = 61bit per xpoint
Second for host usage with xpoint position
Utilized 9008Mb of GPU memory.

[ssxb]

This is the maximum that I can squeeze out of my 2080ti card:
16 pubkeys from JLP example solved in 1m 23s

Code:

NewFINDpubkey= (2375c86aa2a807fd50e4b1a2a65820244e704b8eabc8eb4dc0517393aff0c647, fad56264ae29d620205a68792091b64ae262bba359f8d013ce904d595e790ccf)
***************************
GPU#0 Cnt:0000000000000000000000000000000000000000000000000000000000000001
GPU#0 Cnt:0000000000000000000000000000000000000000000000003388000000000001 823MKey/s x1073741824 2^29.69 x2^31=2^60.69
GPU#0 Cnt:0000000000000000000000000000000000000000000000006754000000000001 826MKey/s x1073741824 2^29.69 x2^31=2^60.69
***********GPU#0************
KEY!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e7ad38337c7f173c7
Pub: 55b95bef84a6045a505d015ef15e136e0a31cc2aa00fa4bca62e5df215ee981b3b4d6bce33718dc6cf59f28b550648d7e8b2796ac36f25ff0c01f8bc42a16fd9
****************************
Found in 5 seconds
GPU#0 job finished
Working time 00:01:23s
Total time 00:06:00s

Used two hashtables:
first  for GPU without xpoint position, only xpoint 32bit + size htsz, totaly 32+29 = 61bit per xpoint
Second for host usage with xpoint position
Utilized 9008Mb of GPU memory.

i optimized parameters and the key

"59A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887 AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8"

i solved in 17 seconds

well can you please tune it for parallel search for pubs , i undertand speed will drop but its still worth to try .. can you?

[Etar]

well can you please tune it for parallel search for pubs , i undertand speed will drop but its still worth to try .. can you?

BSGS algorithm  is not intended to search for public keys in parallel.
Possible to make pseudo-parallelism (this means finding the keys sequentially at each giant step). But the speed will drop in multiples of the number of search keys.
For ex. with search 1 public key your speed is 1000mkeys/s. if you setup 10 keys the speed will drop to 100mkey/s, with 1000keys speed drop to 1mkeys/s
By the way the search time for 16 keys will be exactly the same, either in a sequential search or in a pseudo-parallel.

[lostrelic]

This is the maximum that I can squeeze out of my 2080ti card:
16 pubkeys from JLP example solved in 1m 23s

Code:

NewFINDpubkey= (2375c86aa2a807fd50e4b1a2a65820244e704b8eabc8eb4dc0517393aff0c647, fad56264ae29d620205a68792091b64ae262bba359f8d013ce904d595e790ccf)
***************************
GPU#0 Cnt:0000000000000000000000000000000000000000000000000000000000000001
GPU#0 Cnt:0000000000000000000000000000000000000000000000003388000000000001 823MKey/s x1073741824 2^29.69 x2^31=2^60.69
GPU#0 Cnt:0000000000000000000000000000000000000000000000006754000000000001 826MKey/s x1073741824 2^29.69 x2^31=2^60.69
***********GPU#0************
KEY!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e7ad38337c7f173c7
Pub: 55b95bef84a6045a505d015ef15e136e0a31cc2aa00fa4bca62e5df215ee981b3b4d6bce33718dc6cf59f28b550648d7e8b2796ac36f25ff0c01f8bc42a16fd9
****************************
Found in 5 seconds
GPU#0 job finished
Working time 00:01:23s
Total time 00:06:00s

Used two hashtables:
first  for GPU without xpoint position, only xpoint 32bit + size htsz, totaly 32+29 = 61bit per xpoint
Second for host usage with xpoint position
Utilized 9008Mb of GPU memory.

Hi Etar what settings have you used to get that, and could you recommend what to use for a 3080?
Thanks Relic

[ssxb]

well can you please tune it for parallel search for pubs , i undertand speed will drop but its still worth to try .. can you?

BSGS algorithm  is not intended to search for public keys in parallel.
Possible to make pseudo-parallelism (this means finding the keys sequentially at each giant step). But the speed will drop in multiples of the number of search keys.
For ex. with search 1 public key your speed is 1000mkeys/s. if you setup 10 keys the speed will drop to 100mkey/s, with 1000keys speed drop to 1mkeys/s
By the way the search time for 16 keys will be exactly the same, either in a sequential search or in a pseudo-parallel.

Got it but just as example if you do 32 divisor and load 32 keys , assume if key is on position 1~ lucky you. but if the key is on position 30 program will hang with full range scan for key 1 and than will be back to second (my guess ~ didn't test your program) one perhaps after this century

but one thing that i noticed Alberto keyhunt [updated recently] is way too faster than BSGScuda [although both have different way]. i solved 80 key with blink of eye but that one need serious K and N optimization ~ do the wrong K and N you will never reach the goal. i am not sure if you guys have a chance to test that one Alberto KEYHUNT you will find it interesting.

but dark fact is keyhunt is ram eating bug  so if have less ram (minimum 128gb) no point to compare it with BSGScuda perhaps in that case BSGScuda will do way better than Keyhunt.

[WanderingPhilospher]

well can you please tune it for parallel search for pubs , i undertand speed will drop but its still worth to try .. can you?

BSGS algorithm  is not intended to search for public keys in parallel.
Possible to make pseudo-parallelism (this means finding the keys sequentially at each giant step). But the speed will drop in multiples of the number of search keys.
For ex. with search 1 public key your speed is 1000mkeys/s. if you setup 10 keys the speed will drop to 100mkey/s, with 1000keys speed drop to 1mkeys/s
By the way the search time for 16 keys will be exactly the same, either in a sequential search or in a pseudo-parallel.

Got it but just as example if you do 32 divisor and load 32 keys , assume if key is on position 1~ lucky you. but if the key is on position 30 program will hang with full range scan for key 1 and than will be back to second (my guess ~ didn't test your program) one perhaps after this century

but one thing that i noticed Alberto keyhunt [updated recently] is way too faster than BSGScuda [although both have different way]. i solved 80 key with blink of eye but that one need serious K and N optimization ~ do the wrong K and N you will never reach the goal. i am not sure if you guys have a chance to test that one Alberto KEYHUNT you will find it interesting.

but dark fact is keyhunt is ram eating bug  so if have less ram (minimum 128gb) no point to compare it with BSGScuda perhaps in that case BSGScuda will do way better than Keyhunt.

If you feel keyhunt is faster via your own tests, then divide that 120 pubkey up into 2^40 pubkeys and run keyhunt; maybe you find the key in 2 blinks of an eye...
and if you are going for this:

Got it but just as example if you do 32 divisor and load 32 keys , assume if key is on position 1~ lucky you

then just do your 32 divisor and let it search each pubkey for 1 minute; maybe lucky you.

[Etar]

Hi Etar what settings have you used to get that, and could you recommend what to use for a 3080?
Thanks Relic

It is unpublished version yet(i will publish it today)
it is my settings for 2080ti
-t 512 -b 136 -p 480 -w 30 -htsz 28
Utilized around 9200mb of GPU memory(totaly 2080ti in windows10 have only 9240 free memory)

P.s.Already released v1.6.0

[ssxb]

well can you please tune it for parallel search for pubs , i undertand speed will drop but its still worth to try .. can you?

BSGS algorithm  is not intended to search for public keys in parallel.
Possible to make pseudo-parallelism (this means finding the keys sequentially at each giant step). But the speed will drop in multiples of the number of search keys.
For ex. with search 1 public key your speed is 1000mkeys/s. if you setup 10 keys the speed will drop to 100mkey/s, with 1000keys speed drop to 1mkeys/s
By the way the search time for 16 keys will be exactly the same, either in a sequential search or in a pseudo-parallel.

Got it but just as example if you do 32 divisor and load 32 keys , assume if key is on position 1~ lucky you. but if the key is on position 30 program will hang with full range scan for key 1 and than will be back to second (my guess ~ didn't test your program) one perhaps after this century

but one thing that i noticed Alberto keyhunt [updated recently] is way too faster than BSGScuda [although both have different way]. i solved 80 key with blink of eye but that one need serious K and N optimization ~ do the wrong K and N you will never reach the goal. i am not sure if you guys have a chance to test that one Alberto KEYHUNT you will find it interesting.

but dark fact is keyhunt is ram eating bug  so if have less ram (minimum 128gb) no point to compare it with BSGScuda perhaps in that case BSGScuda will do way better than Keyhunt.

If you feel keyhunt is faster via your own tests, then divide that 120 pubkey up into 2^40 pubkeys and run keyhunt; maybe you find the key in 2 blinks of an eye...
and if you are going for this:

Got it but just as example if you do 32 divisor and load 32 keys , assume if key is on position 1~ lucky you

then just do your 32 divisor and let it search each pubkey for 1 minute; maybe lucky you.

you got big mouth but less sense and knowledge  

i hate to tell you that grow up your knowledge & perhaps things will get more clear.

1 > 80 key not 80 keys [single key] [random mode with 4.7 Ekeys/sec] [4300000000000000000 keys/sec] [3BACAB37B62E0000 keys/sec][ whole 65 range in 1 sec]. now compare with bsgscuda  
        with reference key in range 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff.  let me guess 3080 took with full
        optimization around 17 second but keyhunt took just 1 second. even i have to reduce k and n value to reduce speed for this  .
2 > do your research and than find how many keys you will get while doing 120 to 2^40 divisor [lol]. if you will load 2 keys, you will make keyhunt speed half and what about billion keys . speed will be just like your mind
       processing to understand my answer.
 

[WanderingPhilospher]

you got big mouth but less sense and knowledge  Grin

i hate to tell you that grow up your knowledge & perhaps things will get more clear.

1 > 80 key not 80 keys [single key] [random mode with 4.7 Ekeys/sec] [4300000000000000000 keys/sec] [3BACAB37B62E0000 keys/sec][ whole 65 range in 1 sec]. now compare with bsgscuda 
        with reference key in range 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff.  let me guess 3080 took with full
        optimization around 17 second but keyhunt took just 1 second. even i have to reduce k and n value to reduce speed for this  Grin.
2 > do your research and than find how many keys you will get while doing 120 to 2^40 divisor [lol]. if you will load 2 keys, you will make keyhunt speed half and what about billion keys . speed will be just like your mind
       processing to understand my answer.

Your English reading or comprehension is less sense and knowledge.

I never said anything about 80 keys...you are saying you found 80 key, I took that as a single key in an 80 bit range, not 80 keys because you did not pluralize the word key. So with that, I merely said instead of trying to get someone to reprogram BSGS Cuda for multi key, run keyhunt, since it already supports multi key and if you think it is faster, then break up 120 key into however many keys you want to, 2^5, 2^20, 2^40, or however many you want to and let that program eat.  I said 2^40 specifically because you said an 80 key in a blink of an eye; so 2^120/2^40 = 2^80; if you found one 80 key in a blink of an eye, maybe you find the 120 key in 80 bit range in 2 blinks of an eye.

BSGS Cuda, can find 65 bit key in less than a second, it all depends on your hardware.

you say

if you will load 2 keys, you will make keyhunt speed half

the same will happen to BSGS Cuda; so I am not sure what your point is really.