Author

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

full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 22, 2020, 09:33:30 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).
full member
Activity: 282
Merit: 114
May 22, 2020, 09:09:23 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 :-)
sr. member
Activity: 642
Merit: 316
May 22, 2020, 08:36:34 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
full member
Activity: 282
Merit: 114
May 22, 2020, 06:39:21 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
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 20, 2020, 11:59:18 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?
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 20, 2020, 08:07:20 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 Smiley

Alek, do you mean your version? 
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 20, 2020, 04:46:59 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.
newbie
Activity: 17
Merit: 0
May 20, 2020, 03:34:47 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.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 20, 2020, 03:24:48 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.
newbie
Activity: 17
Merit: 0
May 20, 2020, 03:18:09 PM
Hi, i'm having some issues saving the private key once found, it does not get saved?
sr. member
Activity: 642
Merit: 316
May 20, 2020, 03:15:12 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
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 20, 2020, 02:49:07 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.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 20, 2020, 02:35:17 PM
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?
sr. member
Activity: 642
Merit: 316
May 20, 2020, 02:33:32 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.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 20, 2020, 02:28:50 PM
Sr. Member or higher? Interesting... DP 31, seems too high.
Suggested DP for RTX 2080ti is 32, i used 31 because have  some rigs rtx2070 where DP=32 is bit high.
Less DP need much more memory.

It just seems with a DP of 31, it'll take a lot longer.  What is the expected RAM usage at DP 31, 1 Gb?
1.6Gb , you know that usage more memory can  affect performance

Yes, I experimented with the different DP settings. From suggested to raising and lowering.

For your 2070 at DP 31, what is your Mkey/s rate? At DP 25, mine get between 700 and 800 Mkey/s.
6x2070 hashrate 4.6Gkeys, so around 766Mkeys per GPU
if you have only 2070 it is not a problem setup DP=25, but with DP=25 and rtx2080ti you get around 950Mkeys it is to small hashrate for 2080ti
and there difference betwenn when you launch 1 GPU or rig with 6-10GPU, the speed is not the same.

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?
sr. member
Activity: 642
Merit: 316
May 20, 2020, 02:22:05 PM
Sr. Member or higher? Interesting... DP 31, seems too high.
Suggested DP for RTX 2080ti is 32, i used 31 because have  some rigs rtx2070 where DP=32 is bit high.
Less DP need much more memory.

It just seems with a DP of 31, it'll take a lot longer.  What is the expected RAM usage at DP 31, 1 Gb?
1.6Gb , you know that usage more memory can  affect performance

Yes, I experimented with the different DP settings. From suggested to raising and lowering.

For your 2070 at DP 31, what is your Mkey/s rate? At DP 25, mine get between 700 and 800 Mkey/s.
6x2070 hashrate 4.6Gkeys, so around 766Mkeys per GPU
if you have only 2070 it is not a problem setup DP=25, but with DP=25 and rtx2080ti you get around 950Mkeys it is to small hashrate for 2080ti
and there difference between when you launch 1 GPU or rig with 6-10GPU, the speed is not the same.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 20, 2020, 02:17:08 PM
Sr. Member or higher? Interesting... DP 31, seems too high.
Suggested DP for RTX 2080ti is 32, i used 31 because have  some rigs rtx2070 where DP=32 is bit high.
Less DP need much more memory.

It just seems with a DP of 31, it'll take a lot longer.  What is the expected RAM usage at DP 31, 1 Gb?
1.6Gb , you know that usage more memory can  affect performance

Yes, I experimented with the different DP settings. From suggested to raising and lowering.

For your 2070 at DP 31, what is your Mkey/s rate? At DP 25, mine get between 700 and 800 Mkey/s.
sr. member
Activity: 642
Merit: 316
May 20, 2020, 02:10:38 PM
Sr. Member or higher? Interesting... DP 31, seems too high.
Suggested DP for RTX 2080ti is 32, i used 31 because have  some rigs rtx2070 where DP=32 is bit high.
Less DP need much more memory.

It just seems with a DP of 31, it'll take a lot longer.  What is the expected RAM usage at DP 31, 1 Gb?
1.6Gb , you know that usage more memory can  affect performance
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 20, 2020, 02:05:38 PM
Sr. Member or higher? Interesting... DP 31, seems too high.
Suggested DP for RTX 2080ti is 32, i used 31 because have  some rigs rtx2070 where DP=32 is bit high.
Less DP need much more memory.

It just seems with a DP of 31, it'll take a lot longer.  What is the expected RAM usage at DP 31, 1 Gb?
sr. member
Activity: 642
Merit: 316
May 20, 2020, 01:30:52 PM
Sr. Member or higher? Interesting... DP 31, seems too high.
Suggested DP for RTX 2080ti is 32, i used 31 because have  some rigs rtx2070 where DP=32 is bit high.
Less DP need much more memory.
Jump to: