Pollard's kangaroo ECDLP solver

[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?

Well, finally, we got to the truth, and I expected this when the jump table changed, add NB_JUMP option and leveling the length of the jumps (It is clear that accessing a larger amount of constant GPU memory replaces the speed). Who had the results of 10% or 25% of operations? That should be! Small jumps should be present in the table.

I'm not saying this solver doesn't work...it does it's job and does it well! I am just trying to figure the "trade off" with time vs. storage. I just didn't see any; and I know that's based on "expected" results. The theory behind time and storage makes sense, in general. But if you go with -dp 31, your storage is 1.6 Gb, as opposed to say -dp 25 which is 60 Gb. 2^55 - 31 = 2^24; 2^55 - 25 = 2^30. How do I know which one will be faster? or are they really the same as far as solve time, one just takes less storage than the other...

[1715413736]

1715413736

[1715413736]

1715413736

[1715413736]

1715413736

[1715413736]

1715413736

[WhyMe]

In multi gpu system, is PCIE bandwith important ?
Will you support AMD opencl version ?

[WanderingPhilospher]

I'm not saying this solver doesn't work...it does it's job and does it well! I am just trying to figure the "trade off" with time vs. storage. I just didn't see any; and I know that's based on "expected" results. The theory behind time and storage makes sense, in general. But if you go with -dp 31, your storage is 1.6 Gb, as opposed to say -dp 25 which is 60 Gb. 2^55 - 31 = 2^24; 2^55 - 25 = 2^30. How do I know which one will be faster? or are they really the same as far as solve time, one just takes less storage than the other...

Faster comparison of less data. It is not speed that matters, but the probability of a collision. In this table, all jumps are approximately the same, perhaps for this reason the DP size does not have much effect. Tested with the same settings, but there have never been solutions with less than 50% ops. You can change the table and compare the results. https://bitcointalk.org/index.php?topic=5244940.msg54378164#msg54378164

I put in your code to compare; how do I know if it's using your small jumps or original jumps?

for (int i = 1; i < NB_JUMP; i++) {
      
      if (i < small_jump) {

What number has to be less than small_jump to let the code know to use the small jump code?

[WanderingPhilospher]

I'm not saying this solver doesn't work...it does it's job and does it well! I am just trying to figure the "trade off" with time vs. storage. I just didn't see any; and I know that's based on "expected" results. The theory behind time and storage makes sense, in general. But if you go with -dp 31, your storage is 1.6 Gb, as opposed to say -dp 25 which is 60 Gb. 2^55 - 31 = 2^24; 2^55 - 25 = 2^30. How do I know which one will be faster? or are they really the same as far as solve time, one just takes less storage than the other...

Faster comparison of less data. It is not speed that matters, but the probability of a collision. In this table, all jumps are approximately the same, perhaps for this reason the DP size does not have much effect. Tested with the same settings, but there have never been solutions with less than 50% ops. You can change the table and compare the results. https://bitcointalk.org/index.php?topic=5244940.msg54378164#msg54378164

This is what I get from yours:

Jump: 0 Distance: 1
Jump Avg distance: 2^24.77
Jump: 0 Distance: 1
Jump Avg distance: 2^25.13
Jump: 0 Distance: 1
Jump Avg distance: 2^25.13
Jump: 0 Distance: 1
Jump Avg distance: 2^25.13
Jump: 0 Distance: 1
Jump Avg distance: 2^25.13
Jump: 0 Distance: 1
Jump Avg distance: 2^25.13
Jump: 0 Distance: 1
Jump Avg distance: 2^25.13

which is about 2^1 lower than original code

[WanderingPhilospher]

I'm not saying this solver doesn't work...it does it's job and does it well! I am just trying to figure the "trade off" with time vs. storage. I just didn't see any; and I know that's based on "expected" results. The theory behind time and storage makes sense, in general. But if you go with -dp 31, your storage is 1.6 Gb, as opposed to say -dp 25 which is 60 Gb. 2^55 - 31 = 2^24; 2^55 - 25 = 2^30. How do I know which one will be faster? or are they really the same as far as solve time, one just takes less storage than the other...

Faster comparison of less data. It is not speed that matters, but the probability of a collision. In this table, all jumps are approximately the same, perhaps for this reason the DP size does not have much effect. Tested with the same settings, but there have never been solutions with less than 50% ops. You can change the table and compare the results. https://bitcointalk.org/index.php?topic=5244940.msg54378164#msg54378164

Ok, I figured out how to see the difference; my NB_JUMP has to be 32 or less and I can then see about a 2^7 difference in avg jumps at 40 bit range. Will test and compare later today.

[zielar]

Hello,
I am asking you kindly for help in writing .bat which will automatically start the server process after it turns off. The problem is so frequent that I would have to sit around the clock to watch it.
I offer a reward for help if I manage to solve # 110

Server executable name: server.exe
DP value: 28

Referring to earlier guesses: the reason for shutting down the server is not on the RAM side, because the machine has 256GB of RAM, so there is no question that it is the cause.

---
EDIT: Something is wrong! Look at this dump from few seconds ago:

Code:

Unexpected wrong collision, reset kangaroo !
Found: Td-73xxxxxxxxx57E8567EB949E04A8
Found: Wd-34xxxxxxxxxE8567EB949E04A8

What does it mean?

[Etar]

Hello,
I am asking you kindly for help in writing .bat which will automatically start the server process after it turns off. The problem is so frequent that I would have to sit around the clock to watch it.
I offer a reward for help if I manage to solve # 110

Server executable name: server.exe
DP value: 28

Referring to earlier guesses: the reason for shutting down the server is not on the RAM side, because the machine has 256GB of RAM, so there is no question that it is the cause.

You can use my launcher https://drive.google.com/open?id=1esYd5WFHnVjvSOj94rIzyFZZawj2QBRA
Do not forget test file in antivirus.
This launcher is very simple, he just lauch kangaroo.exe and wait while they quit after that he restart it again. You can see how many restart already done.
Drop this file to your server folder and replace kangaroo.exe with launcherkangaroo.exe in your bat file

[zielar]

Could you send me the source code for this? I have several changes in my version, such as the maximum number of clients connected to the server, etc.

P.S. I edited my previous post before you could reply.

[Etar]

Could you send me the source code for this? I have several changes in my version, such as the maximum number of clients connected to the server, etc.

P.S. I edited my previous post before you could reply.

Code:

Compiler.i
Filename$="Kangaroo.exe"
OpenConsole("launcher")
PrintN ("[START launcher]")
 parametrscount=CountProgramParameters()
  p$=""
  For i=0 To parametrscount-1    
      p$+ProgramParameter(i)+" "
    Next i 
    Debug p$
    PrintN ("START ["+Filename$+"]")
    restart=0
    *Buffer = AllocateMemory(1024)
  While 1    
    ConsoleTitle("launcher /restart " +Str(restart))
    Compiler = RunProgram("cmd.exe" ,"/c "+Filename$+" "+p$,"",#PB_Program_Open)  
    If Compiler
      While ProgramRunning(Compiler)
        
          Delay(10)
      Wend
      Delay(5000)
      PrintN("")
      PrintN ("RESTART ["+Filename$+"]")
      restart+1
    Else
      PrintN ("["+Filename$+"] not found")
      Break
    EndIf
  Wend
  
  PrintN("Press Enter to exit")
  Input()
  End

There not need made changes in source file. all parametrs from bat file kangaroolauncher send to kangaroo.exe(like -s, -nt and so on)
you have bat file like:

Code:

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

just replace Kangaroo.exe to launcherkangaroo.exe, like this:

Code:

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

laucher will find kangaroo.exe in folder and launch with your params from bat file.

[Etar]

How can i compile it? Can you send me an VS project ? Your release say "no input file specified"... Too many changes.

https://www.purebasic.com/download.php
it is a simple language basic + C to made simple project in few minutes. Paste source code to IDE and compile in 1 click.
I don`t have Visual C and never use it)

[zielar]

OK.It works :-) Many thanks.

What do you think about the error I received before? :

Code:

Unexpected wrong collision, reset kangaroo !
Found: Td-73xxxxxxxxx57E8567EB949E04A8
Found: Wd-34xxxxxxxxxE8567EB949E04A8

[Etar]

OK.It works :-) Many thanks.

What do you think about the error I received before? :

Code:

Unexpected wrong collision, reset kangaroo !
Found: Td-73xxxxxxxxx57E8567EB949E04A8
Found: Wd-34xxxxxxxxxE8567EB949E04A8

i don`t know) JeanLucPons say in Kangaroo.cpp

// Should not happen, reset the kangaroo

[zielar]

OK.It works :-) Many thanks.

What do you think about the error I received before? :

Code:

Unexpected wrong collision, reset kangaroo !
Found: Td-73xxxxxxxxx57E8567EB949E04A8
Found: Wd-34xxxxxxxxxE8567EB949E04A8

i don`t know) JeanLucPons say in Kangaroo.cpp

// Should not happen, reset the kangaroo

Shit... :/

JeanLucPons...
So I am waiting for you to take a position on this matter, because the question mark is the sense of engaging further power :-)

[Etar]

OK.It works :-) Many thanks.

What do you think about the error I received before? :

Code:

Unexpected wrong collision, reset kangaroo !
Found: Td-73xxxxxxxxx57E8567EB949E04A8
Found: Wd-34xxxxxxxxxE8567EB949E04A8

i don`t know) JeanLucPons say in Kangaroo.cpp

// Should not happen, reset the kangaroo

Shit... :/

JeanLucPons...
So I am waiting for you to take a position on this matter, because the question mark is the sense of engaging further power :-)

maybe i wrong but i think it is not a big problem. because hashtable do not store full x coordinat but only DP i think there can be false collision.
in that case when reconstuct pubkey from TD and WD can be different pubkey. it think with DP=10 can get a lot of this error (maybe)
This is just my thinking. what to do is up to you.

[WanderingPhilospher]

OK.It works :-) Many thanks.

What do you think about the error I received before? :

Code:

Unexpected wrong collision, reset kangaroo !
Found: Td-73xxxxxxxxx57E8567EB949E04A8
Found: Wd-34xxxxxxxxxE8567EB949E04A8

i don`t know) JeanLucPons say in Kangaroo.cpp

// Should not happen, reset the kangaroo

Shit... :/

JeanLucPons...
So I am waiting for you to take a position on this matter, because the question mark is the sense of engaging further power :-)

Did you change anything in source code? I will get the same error when I am tweaking the code with different settings. It happens. The good news is, the program automatically resets the kangaroos and it keeps on jumping to the key!

[zielar]

OK.It works :-) Many thanks.

What do you think about the error I received before? :

Code:

Unexpected wrong collision, reset kangaroo !
Found: Td-73xxxxxxxxx57E8567EB949E04A8
Found: Wd-34xxxxxxxxxE8567EB949E04A8

i don`t know) JeanLucPons say in Kangaroo.cpp

// Should not happen, reset the kangaroo

Shit... :/

JeanLucPons...
So I am waiting for you to take a position on this matter, because the question mark is the sense of engaging further power :-)

maybe i wrong but i think it is not a big problem. because hashtable do not store full x coordinat but only DP i think there can be false collision.
in that case when reconstuct pubkey from TD and WD can be different pubkey. it think with DP=10 can get a lot of this error (maybe)
This is just my thinking. what to do is up to you.

Maybe ... I am more concerned about the "restart kangaroo" part :-)

[zielar]

My changes:

In Constans.h:

Code:

#define CLIENT_TIMEOUT 36000.0

In Kangaroo.cpp:
...added

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;
  }
}

// ----------------------------------------------------------------------------

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;

}

afer

Code:

bool Kangaroo::ParseConfigFile(std::string &fileName) {

  // In client mode, config come from the server
  if(clientMode)
    return true;

  // Check file
  FILE *fp = fopen(fileName.c_str(),"rb");
  if(fp == NULL) {
    ::printf("Error: Cannot open %s %s\n",fileName.c_str(),strerror(errno));
    return false;
  }
  fclose(fp);

  // Get lines
  vector<string> lines;
  int nbLine = 0;
  string line;
  ifstream inFile(fileName);
  while(getline(inFile,line)) {

    // Remove ending \r\n
    int l = (int)line.length() - 1;
    while(l >= 0 && isspace(line.at(l))) {
      line.pop_back();
      l--;
    }

    if(line.length() > 0) {
      lines.push_back(line);
      nbLine++;
    }

  }

  if(lines.size()<3) {
    ::printf("Error: %s not enough arguments\n",fileName.c_str());
    return false;
  }

  rangeStart.SetBase16((char *)lines[0].c_str());
  rangeEnd.SetBase16((char *)lines[1].c_str());
  for(int i=2;i<(int)lines.size();i++) {
    
    Point p;
    bool isCompressed;
    if( !secp->ParsePublicKeyHex(lines[i],p,isCompressed) ) {
      ::printf("%s, error line %d: %s\n",fileName.c_str(),i,lines[i].c_str());
      return false;
    }
    keysToSearch.push_back(p);

  }

  ::printf("Start:%s\n",rangeStart.GetBase16().c_str());
  ::printf("Stop :%s\n",rangeEnd.GetBase16().c_str());
  ::printf("Keys :%d\n",(int)keysToSearch.size());

  return true;

}

// ----------------------------------------------------------------------------

and in Kangaroo.h

added

Code:

bool output(std::string msg);

after

Code:

 bool saveKangaroo;

and before

Code:

  int wtimeout;
  int ntimeout;

(section //Backup stuff)

[zielar]

Server autorestart now works fine. You calmed me down, gentlemen. I must admit that I hope to find # 110 in the next few days ... I will remember you if I do it, and of course about the author of this tool, to which I already owe a lot :-)

Greetings !

[WanderingPhilospher]

Server autorestart now works fine. You calmed me down, gentlemen. I must admit that I hope to find # 110 in the next few days ... I will remember you if I do it, and of course about the author of this tool, to which I already owe a lot :-)

Greetings !

Good luck! And I must admit, I hope I find it first 

[WhyMe]

Doing some tests with a 1070ti.
Why playing with OC does not affect hashrate ?