Pollard's kangaroo ECDLP solver - page 134.

zielar

full member

Activity: 282

Merit: 114

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?

zielar

full member

Activity: 282

Merit: 114

Quote

it is from 3 GPU v100 7200MK / s ?

From 4 v100

Etar

sr. member

Activity: 654

Merit: 316

Quote from: zielar on May 22, 2020, 10:35:40 AM

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

full member

Activity: 282

Merit: 114

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

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: zielar on May 22, 2020, 09:40:22 AM

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.

Etar

sr. member

Activity: 654

Merit: 316

Quote from: zielar on May 22, 2020, 09:09:23 AM

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.

zielar

full member

Activity: 282

Merit: 114

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?

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: zielar on May 22, 2020, 09:09:23 AM

Quote from: Etar on May 22, 2020, 08:36:34 AM

Quote from: zielar on May 22, 2020, 06:39:21 AM

-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

full member

Activity: 282

Merit: 114

Quote from: Etar on May 22, 2020, 08:36:34 AM

Quote from: zielar on May 22, 2020, 06:39:21 AM

-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 :-)

Etar

sr. member

Activity: 654

Merit: 316

Quote from: zielar on May 22, 2020, 06:39:21 AM

-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

full member

Activity: 282

Merit: 114

Quote from: Jean_Luc on May 01, 2020, 12:22:44 AM

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 Wink

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

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: ?? on ??

Quote from: WanderingPhilospher on May 20, 2020, 08:07:20 PM

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?

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: ?? on ??

Quote from: fluffyCRUNK on May 20, 2020, 03:34:47 PM

Quote from: WanderingPhilospher on May 20, 2020, 03:24:48 PM

Quote from: fluffyCRUNK on May 20, 2020, 03:18:09 PM

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

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: fluffyCRUNK on May 20, 2020, 03:34:47 PM

Quote from: WanderingPhilospher on May 20, 2020, 03:24:48 PM

Quote from: fluffyCRUNK on May 20, 2020, 03:18:09 PM

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.

fluffyCRUNK

newbie

Activity: 17

Merit: 0

Quote from: WanderingPhilospher on May 20, 2020, 03:24:48 PM

Quote from: fluffyCRUNK on May 20, 2020, 03:18:09 PM

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.

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: fluffyCRUNK on May 20, 2020, 03:18:09 PM

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.

fluffyCRUNK

newbie

Activity: 17

Merit: 0

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

Etar

sr. member

Activity: 654

Merit: 316

Quote from: WanderingPhilospher on May 20, 2020, 02:49:07 PM

Quote from: Etar on May 20, 2020, 02:33:32 PM

Quote from: WanderingPhilospher on May 20, 2020, 02:28:50 PM

True, I guess that is the choice everyone has to make...more DP for longer runtime vs "performance". I saw MrFreeDragon running 2080Tis at DP 17 for I believe 80 bit range and still getting over 1200 Mkey/s. What does your 2080Ti's rate drop down to if you go down to DP 25?

I can answer you this question when the competition is done, all my 2080ti are in work.
Any way there DP size is not so important thing.
I think luck is more important here and total of GPU rigs.

I agree that luck is a big part of the equation, however, the DP has to/does play a big factor IMO. I tried to find a balance with DP/performance. I may not have go it right on this go around but I had over 2^30 DPs (1,000,000,000+) at DP 25 after a lot of testing so I just stuck with DP 25.

If you have DP size 25 and already found 2^30+ DP than you should find key in few days, maybe today, maybe tomorrow. 2^55.5-25=2^30.5

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: Etar on May 20, 2020, 02:33:32 PM

Quote from: WanderingPhilospher on May 20, 2020, 02:28:50 PM

True, I guess that is the choice everyone has to make...more DP for longer runtime vs "performance". I saw MrFreeDragon running 2080Tis at DP 17 for I believe 80 bit range and still getting over 1200 Mkey/s. What does your 2080Ti's rate drop down to if you go down to DP 25?

I can answer you this question when the competition is done, all my 2080ti are in work.
Any way there DP size is not so important thing.
I think luck is more important here and total of GPU rigs.

I agree that luck is a big part of the equation, however, the DP has to/does play a big factor IMO. I tried to find a balance with DP/performance. I may not have go it right on this go around but I had over 2^30 DPs (1,000,000,000+) at DP 25 after a lot of testing so I just stuck with DP 25.

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

I ran a 100 key test at the 56 Bit level, CPU only (2 cores, 2048 kangaroos), with some mods I have made to original code. I ran it in with STATS mode to see how it compares...can anyone explain these results?

Quote

[ 99] 2^29.138 Dead:2 Avg:2^28.739 DeadAvg:2.2 (1.669 2.084 sqrt(N))

Is it, the 1.669 sqrt is what my test ran versus what is expected the 2.084 sqrt?

Topic: Pollard's kangaroo ECDLP solver - page 134. (Read 60582 times)