Pollard's kangaroo ECDLP solver

[WanderingPhilospher]

Hi, i'm having some issues saving the private key once found, it does not get saved?

It does not save. Are you compiling your own version? If so, I can give you a code snippet to add to source file that will generate a saved file with pub and priv key.

No i'm just using the release version, ah that's a little concerning, would be nice to save in case of a power outage, crash or accidental cmd close.

I downloaded a fresh copy from JeanLucPons' 1.5 release, only added the save keys to file feature, and recompiled. I've uploaded a copy here:

https://github.com/WanderingPhilosopher/GPUKangaroo

It will automatically save a file called "Keys" to the folder where you run the program from. Try and on a low bit (for quickness) and let me know if it worked for you. I ran one test with it, and it works as my other compiled versions.

[WanderingPhilospher]

Hi, i'm having some issues saving the private key once found, it does not get saved?

It does not save. Are you compiling your own version? If so, I can give you a code snippet to add to source file that will generate a saved file with pub and priv key.

No i'm just using the release version, ah that's a little concerning, would be nice to save in case of a power outage, crash or accidental cmd close.

It looks something like this:
in Kangaroo.cpp

Code:

bool Kangaroo::output(string msg) {
  
  FILE *f = stdout;
  f = fopen("Result.txt", "a");
    
  if (f == NULL) {
	  printf("[error] Cannot open file Result.txt\n");
	  f = stdout;
	  return false;
  } 
  else {
	  fprintf(f, "%s\n", msg.c_str());
	  fclose(f);
	  printf("[i] Success saved to file Result.txt\n");
	  return true;
  }
}

and

Code:

bool  Kangaroo::CheckKey(Int d1,Int d2,uint8_t type) {

  // Resolve equivalence collision

  if(type & 0x1)
    d1.ModNegK1order();
  if(type & 0x2)
    d2.ModNegK1order();

  Int pk(&d1);
  pk.ModAddK1order(&d2);

  Point P = secp->ComputePublicKey(&pk);

  if(P.equals(keyToSearch)) {
    // Key solved    
#ifdef USE_SYMMETRY
    pk.ModAddK1order(&rangeWidthDiv2);
#endif
    pk.ModAddK1order(&rangeStart);    
    Point PR = secp->ComputePublicKey(&pk);
    ::printf("\nKey#%2d [%dN]Pub:  0x%s \n",keyIdx,type,secp->GetPublicKeyHex(true,keysToSearch[keyIdx]).c_str());
    // Save Priv
    std::string prvkey = pk.GetBase16().c_str();
    bool save_pk = output(prvkey + string(":") + string("04") + PR.x.GetBase16().c_str() + PR.y.GetBase16().c_str() ); 
    if( PR.equals(keysToSearch[keyIdx]) ) {
      ::printf("       Priv: 0x%s \n",pk.GetBase16().c_str());
    } else {
      ::printf("       Failed !\n");
      ::printf("       Priv: 0x%s \n",pk.GetBase16().c_str());
      return false;
    }
    return true;
  }

  if(P.equals(keyToSearchNeg)) {
    // Key solved
    pk.ModNegK1order();
#ifdef USE_SYMMETRY
    pk.ModAddK1order(&rangeWidthDiv2);
#endif
    pk.ModAddK1order(&rangeStart);
    Point PR = secp->ComputePublicKey(&pk);
    ::printf("\nKey#%2d [%dS]Pub:  0x%s \n",keyIdx,type,secp->GetPublicKeyHex(true,keysToSearch[keyIdx]).c_str());
    // Save Priv
    std::string prvkeyNeg = pk.GetBase16().c_str();
    bool save_pk = output(prvkeyNeg + string(":") + string("04") + PR.x.GetBase16().c_str() + PR.y.GetBase16().c_str() ); 
    if(PR.equals(keysToSearch[keyIdx]) ) {
      ::printf("       Priv: 0x%s \n",pk.GetBase16().c_str());
    } else {
      ::printf("       Failed !\n");
      ::printf("       Priv: 0x%s \n",pk.GetBase16().c_str());
      return false;
    }
    return true;
  }

  return false;

}

Add in Kangaroo.h

Code:

bool output(std::string msg);

But I do not need this, I use other version. Where the problem with RAM is solved, can change the number of files to save DP=16. But the problems with disk space have begun

Alek, do you mean your version? 

[WanderingPhilospher]

Alek, do you mean your version?  

Yes, I changed the code again, splitting the DP type by kIdx (as in the original code). Thank you very much Jean Luc for your work! But the table did the original - G, 2G, 4G, 8G, ..., (2 ^ NB_JUMP) G.
#define NB_JUMP 64. For bit 110, it’s enough.
Saving to multiple files, rewritten comparator. Added by #define NB_WORK 8
Now it uses 8 wild.txt and 8 tame.txt files - the number of comparisons is 64. The comparison of small files does not take up much RAM.
In the original version, a collision check occurs when files are combined (adding a DP point to the hash table), therefore it is impossible to combine all working files at the same time, this will require hundreds of gigabytes of RAM to solve bit 110. The DP points must be written to the server side several files and comparison in turn.

I used yours, with tweaks to the code. It used 2 wild and 2 tame files. Have you updated the new source code on github?

[zielar]

Hello,

I would like to present an interval ECDLP solver based on the Pollard's kangaroo method.
This program is fully open source and available on GitHub: https://github.com/JeanLucPons/Kangaroo
It has GPU support (CUDA Only) and works on both Linux and Windows.
This program is currently under development.

Thanks to test it and to share ideas of improvements here

NICE WORK!!!

As the complexity of the design itself is already surprisingly large - please indicate the best code configuration to achieve results in terms of # 110 puzzle address. The start-up mode will take place inside the network using a dozen or so Tesla V100 machines, but with the use of a built-in server function. I made changes to the code in this form:

Constans.h file:

Code:

- Change NB_JUMP to value 64
- Change CLIENT_TIMEOUT to value 36000.0

My questions:
1. Are these values be appropriate for this mode of operation, given that there will be ten of the same clients connected to one server?

2. What is the optimal "-d" value in my situation for #110?

3. Are configuration files below correct for server and client?

server.bat

Code:

kangaro.exe -w save.work -wi 300 -d 28 -s input.txt

client.bat

Code:

kangaro.exe -nt 36000 -t 0 -gpu -gpuId 0,1,2,3 -g 880,256,880,256,880,256,880,256 -c {MYserverIP} input.txt 

Many thanks

[Etar]

-snip-

server.bat

Code:

kangaro.exe -w save.work -wi 300 -d 28 -s input.txt

client.bat

Code:

kangaro.exe -nt 36000 -t 0 -gpu -gpuId 0,1,2,3 -g 880,256,880,256,880,256,880,256 -c {MYserverIP} input.txt 

Many thanks

I did`t change constant, so can`t say nothing about this.
server.bat is correct
client.bat is not correct because v100 have 80 SM, so you need set grid like 160,256 or 160,128
DP bit size you should set as you wish, somebody set it to 25, somebody to 31. It is only your choice.
Less DP  = more memory usage, affect gpu perfomance
More DP = more time to find DP

[zielar]

-snip-

server.bat

Code:

kangaro.exe -w save.work -wi 300 -d 28 -s input.txt

client.bat

Code:

kangaro.exe -nt 36000 -t 0 -gpu -gpuId 0,1,2,3 -g 880,256,880,256,880,256,880,256 -c {MYserverIP} input.txt 

Many thanks

I did`t change constant, so can`t say nothing about this.
server.bat is correct
client.bat is not correct because v100 have 80 SM, so you need set grid like 160,256 or 160,128
DP bit size you should set as you wish, somebody set it to 25, somebody to 31. It is only your choice.
Less DP  = more memory usage, affect gpu perfomance
More DP = more time to find DP

Many thanks for the reply and explanation "-d"
Unfortunately, I have to watch the server, because it just ends every hour for no reason. What could be the reason?
Can I resume working clients (who are still waiting for the server to reappear) with the -i save.work option? Because the resumption of the server theoretically looks like it continued where it ended and the clients act as if nothing happened :-)

[WanderingPhilospher]

-snip-

server.bat

Code:

kangaro.exe -w save.work -wi 300 -d 28 -s input.txt

client.bat

Code:

kangaro.exe -nt 36000 -t 0 -gpu -gpuId 0,1,2,3 -g 880,256,880,256,880,256,880,256 -c {MYserverIP} input.txt 

Many thanks

I did`t change constant, so can`t say nothing about this.
server.bat is correct
client.bat is not correct because v100 have 80 SM, so you need set grid like 160,256 or 160,128
DP bit size you should set as you wish, somebody set it to 25, somebody to 31. It is only your choice.
Less DP  = more memory usage, affect gpu perfomance
More DP = more time to find DP

Many thanks for the reply and explanation "-d"
Unfortunately, I have to watch the server, because it just ends every hour for no reason. What could be the reason?
Can I resume working clients (who are still waiting for the server to reappear) with the -i save.work option? Because the resumption of the server theoretically looks like it continued where it ended and the clients act as if nothing happened :-)

Not sure why your server ends every hour. Mine stops occasionally but maybe twice a day, not every hour.
As far as resuming, yes. If your server stops, your clients will be sitting and waiting for the server to come back up on line.
But after you run the server batch file for the first time, you need to modify it if you want it to read/append the same working file. Do this with the -i save.work option.
For grid size and -d option, there is no one size fits all. Tweak them until you are happy/content with performance (grid size) and time/memory trade off (-dp).

[zielar]

Thanks for the information. One more thing does not give me peace ... After changing the code value NB_JUMP 64 the total hashrate drops from ~ 7000 to ~ 5700. Well, I understand that option 32 was better?
and what does it look like with NB_RUN?

[Etar]

Many thanks for the reply and explanation "-d"
Unfortunately, I have to watch the server, because it just ends every hour for no reason. What could be the reason?
Can I resume working clients (who are still waiting for the server to reappear) with the -i save.work option? Because the resumption of the server theoretically looks like it continued where it ended and the clients act as if nothing happened :-)

i have the same problem with server on WIndows. It is just shutdown without any error or some reasons.

[WanderingPhilospher]

Thanks for the information. One more thing does not give me peace ... After changing the code value NB_JUMP 64 the total hashrate drops from ~ 7000 to ~ 5700. Well, I understand that option 32 was better?
and what does it look like with NB_RUN?

I had that problem as well but only when I bumped up the NBJUMP past 128...But I'm not using Tesla's so I imagine the more powerful the card, the more that number affects performance even as small as moving it to 64.

[zielar]

Okay ... Thanks again for the information.
The server actually turns off randomly (and not like I wrote every hour), and eventually I managed to achieve the highest hashrate (7200MK / s) by changing NB_JUMP to 16 and setting -g 400,512
It is true that it shows me that it consumes memory -1687.00MB, but it does not affect the effects, where with the setting -g 320,512 it shows without "-" 1983.00MB) and hashrate is ~ 7000
greetings

[Etar]

Okay ... Thanks again for the information.
The server actually turns off randomly (and not like I wrote every hour), and eventually I managed to achieve the highest hashrate (7200MK / s) by changing NB_JUMP to 16 and setting -g 400,512
It is true that it shows me that it consumes memory -1687.00MB, but it does not affect the effects, where with the setting -g 320,512 it shows without "-" 1983.00MB) and hashrate is ~ 7000
greetings

it is from 3 GPU v100 7200MK / s ?

[zielar]

it is from 3 GPU v100 7200MK / s ?

From 4 v100

[zielar]

I am thinking about the sense of the current version over # 110. Well:
1. Absolutely: in the time interval of 60-120 minutes - the application started in server mode goes offline, causing the task to be suspended, causing an obstacle in the form of restarting, and as you know - any break or obstacle - it is not known what it brings.
2. In my case, the reduction of NB_JUMP to 16 raised the hashrate to 7200MK / s. I am beginning to consider whether this change in code has actually benefited or will have a negative impact.
3. After manually restarting the server with the command

Code:

Kangaroo.exe -nt 36000000 -w saved.work -i saved.work -wi 300 -d 28 -s input.txt

...the number that was in DEAD is counted again from zero. Is it alright?
4. How will the result be dump if it is found? I implemented a code add-on from a friend's post a few posts before me.
5. Does the indicator next to hashrate 2 ^ XX.XX / 2 ^ YY.YY mean that reaching X to level Y is the maximum time needed for the solution?

[WanderingPhilospher]

I am thinking about the sense of the current version over # 110. Well:
1. Absolutely: in the time interval of 60-120 minutes - the application started in server mode goes offline, causing the task to be suspended, causing an obstacle in the form of restarting, and as you know - any break or obstacle - it is not known what it brings.
2. In my case, the reduction of NB_JUMP to 16 raised the hashrate to 7200MK / s. I am beginning to consider whether this change in code has actually benefited or will have a negative impact.
3. After manually restarting the server with the command

Code:

Kangaroo.exe -nt 36000000 -w saved.work -i saved.work -wi 300 -d 28 -s input.txt

...the number that was in DEAD is counted again from zero. Is it alright?
4. How will the result be dump if it is found? I implemented a code add-on from a friend's post a few posts before me.
5. Does the indicator next to hashrate 2 ^ XX.XX / 2 ^ YY.YY mean that reaching X to level Y is the maximum time needed for the solution?

#5 (if you are talking server) first 2^ is your current DP# the second 2^ is what is expected, DP wise, to find solution.
#4 yeah, I added my own print to text code for when key is found
#3 I had same thing happen once, it as well showed zero when restarted because I don't think the table/file keeps the dead kangaroos
#2 go back through the posts, Jean Luc did a test on number of jumps, from 32 - 512; 16 seems low, but who knows
#1 hopefully breaks/restarts have no impact or everybody will be in same boat as I am sure everyone has had to stop and restart, intentionally or not, at some point or another

Did you mess around with DP number? What DP did you go with? The lower it is, it will also affect the MKey/s rate.

[WanderingPhilospher]

I am thinking about the sense of the current version over # 110. Well:
1. Absolutely: in the time interval of 60-120 minutes - the application started in server mode goes offline, causing the task to be suspended, causing an obstacle in the form of restarting, and as you know - any break or obstacle - it is not known what it brings.
2. In my case, the reduction of NB_JUMP to 16 raised the hashrate to 7200MK / s. I am beginning to consider whether this change in code has actually benefited or will have a negative impact.
3. After manually restarting the server with the command

Code:

Kangaroo.exe -nt 36000000 -w saved.work -i saved.work -wi 300 -d 28 -s input.txt

...the number that was in DEAD is counted again from zero. Is it alright?
4. How will the result be dump if it is found? I implemented a code add-on from a friend's post a few posts before me.
5. Does the indicator next to hashrate 2 ^ XX.XX / 2 ^ YY.YY mean that reaching X to level Y is the maximum time needed for the solution?

Also, I haven't ever used the -nt option, try and remove it and up your -wi from 300 to 600; unless RAM on your server is an issue/bottleneck.

As a workaround until the actual server problem is figured out, maybe create a batch file to start and then taskkill the server application every 30 minutes; so if you still use -wi 300 (every 5 minutes) you will get 6 saves in and then the batch script will restart for another 30 minutes. At least this way you don't have to constantly monitor if it's online or not. Set the batch file up with a :loop and taskkill after 30 minutes...the server app will rinse and repeat.

[Etar]

I am thinking about the sense of the current version over # 110. Well:
1. Absolutely: in the time interval of 60-120 minutes - the application started in server mode goes offline, causing the task to be suspended, causing an obstacle in the form of restarting, and as you know - any break or obstacle - it is not known what it brings.
2. In my case, the reduction of NB_JUMP to 16 raised the hashrate to 7200MK / s. I am beginning to consider whether this change in code has actually benefited or will have a negative impact.
3. After manually restarting the server with the command

Code:

Kangaroo.exe -nt 36000000 -w saved.work -i saved.work -wi 300 -d 28 -s input.txt

...the number that was in DEAD is counted again from zero. Is it alright?
4. How will the result be dump if it is found? I implemented a code add-on from a friend's post a few posts before me.
5. Does the indicator next to hashrate 2 ^ XX.XX / 2 ^ YY.YY mean that reaching X to level Y is the maximum time needed for the solution?

1) you can make easy app that will restart server if it crashed.
But I refused the server which is built into the program, because it constantly shuts down.
I wrote my simple server that merge the work files of clients
2) i don`t touch any constants in file and use default NB_JUMP=32
3)yes, server kangaroo restart, because server don`t save kangaroo in work file.
4) you already do that
5) there no maximum time needed, there only expected time. For your choice DP=28 you should find around 2^55.5-28=2^27.5 DP

[WanderingPhilospher]

I am thinking about the sense of the current version over # 110. Well:
1. Absolutely: in the time interval of 60-120 minutes - the application started in server mode goes offline, causing the task to be suspended, causing an obstacle in the form of restarting, and as you know - any break or obstacle - it is not known what it brings.
2. In my case, the reduction of NB_JUMP to 16 raised the hashrate to 7200MK / s. I am beginning to consider whether this change in code has actually benefited or will have a negative impact.
3. After manually restarting the server with the command

Code:

Kangaroo.exe -nt 36000000 -w saved.work -i saved.work -wi 300 -d 28 -s input.txt

...the number that was in DEAD is counted again from zero. Is it alright?
4. How will the result be dump if it is found? I implemented a code add-on from a friend's post a few posts before me.
5. Does the indicator next to hashrate 2 ^ XX.XX / 2 ^ YY.YY mean that reaching X to level Y is the maximum time needed for the solution?

1) you can make easy app that will restart server if it crashed.
But I refused the server which is built into the program, because it constantly shuts down.
I wrote my simple server that merge the work files of clients
2) i don`t touch any constants in file and use default NB_JUMP=32
3)yes, server kangaroo restart, because server don`t save kangaroo in work file.
4) you already do that
5) there no maximum time needed, there only expected time. For your choice DP=28 you should find around 2^55.5-28=2^27.5 DP

I am interested in your merge process...what type of program/script/code are you using to auto merge files of clients?

[Etar]

-snip-

I am interested in your merge process...what type of program/script/code are you using to auto merge files of clients?

look there https://bitcointalk.org/index.php?topic=5244940.msg54425721#msg54425721
it is simple server app and client app.
Client app got job from server like range,key,saving interval,dp size.
Do this job and save job (with kangaroos)  in saving interval time, than app check this file and send to server.
server app check file and with kangaroo exe merge to workfile.
The server does not support constant communication with clients. Moreover, the initiators of session are always the client.
So i don`t have any error in socket.
And ther 2 ways to find key:
- on client side, and client app will send key to server
- or during merge files.
The only thing that may not be very convenient is that the client files are quite weighty from 600-1700mb (if client have good enternet it is not a problem send 1.7Gb in 200s)
But this is not such a big problem such as they are sent every 2 hours.
Once key solve server app do log file and send notify to telegramm.

[WanderingPhilospher]

Okay, I'm not understanding this DP time/memory trade off.

Maybe I have over thought it.  Running several tests with same configurations and only changing the -dp, whether I was at DP 14 - 31, the expected time and 2^ops stayed the same, the only thing that changed was the amount of expected RAM.

Anyone explain it better?