Topic: Pollard's kangaroo ECDLP solver - page 4. (Read 55445 times)

I have been testing keyhunt and the conclusion is that its speed is very fast within a small range. For example, with a 45 bit interval, 8GB of memory is much faster than 1060 speed. However, once it reaches a high level, the efficiency of keyhunt is relatively low. Currently, I am testing with 128GB of memory, and the speed has reached 2Ekey/s. However, it is obvious that these speeds are negligible in such a huge space, so I prefer kangaroo high search. I am still testing more kangaroo conclusions. Thank you and greetings

Ahhhh, now go and look at how the hash table is built/what goes into it. I’ll give you a hint, as I’ve said all along, 128 bits max, for points and distances.

So no people, don’t use it unless you want headaches and possible heartbreaks 😁


Now on JLPs Kangaroo GitHub repository:

you have max setup : 128 bit as jumpBit if more  if(jumpBit > 128) jumpBit = 128;

As JLP says:

interval search not means the range of privatekey but diff beetween start and end of privatekey.


Start range
End range
Key #1
Key #2

max different end_range-start_range < 2**128

have fun!

What say you now?

The JLP, unmodded, kangaroo program, will not work for all the remaining ranges.

Now you’ll have everyone using it and wind up disappointed 😔

This is a false statement which is not true. Kangaroo is not limited to 125bit ranges. It works fine with all ranges intended for this little game-

I do not have a modded version of JLPs.

Peeps, listen up lol, use Etayson EtarKangaroo on github. Then you don't have to worry about all the tomfoolery.

Can you make public your modded version of JLP's kangaroo?



i don't know how to mod so this is not option for me

i can break into 2 parts and run on different rigs - thats what i thought at beginning, but how do i control the wrong DPs?



yes please make open source, just like original was open source to benefit you, please help us

Are you sure? When I tested many moons ago, if I ran a higher range than 128 (b/c hash table only stores 32 hex characters for point and distance (32x4 = 128)), the distances and points were correct, but obviously the leading characters were left out/off because of the 128 bit max storage.

I may have to run again and retest, and extract the hash table....I will check it now.

Update:

It is as how I remembered it. I just ran a super quick test for the 130 bit range. As you know, the program subtracts starting range so we are working with 0 thru 1ffffff.....(129 bit range)
Here is extracted DP, DP of 20:

178559a1004e94449e90d76ca10b3600 26311140a6e43a1530526461aed458e4

On the surface, if you just plugged in 26311140a6e43a1530526461aed458e4, it seems false, but we know that the only other possible number that could be added in front is a 1, so add a 1 to 26311140a6e43a1530526461aed458e4 and you get 126311140a6e43a1530526461aed458e4, now cross reference that distance and you get this point:
0300000B71D19F5FCD4AC6184EDE7C000C178559A1004E94449E90D76CA10B3600
which matches up to:
178559a1004e94449e90d76ca10b3600
178559A1004E94449E90D76CA10B3600

So that is what I mean by doing some manual work if you use JLPs unmodded version and find a collision in the 130 bit range. But if you go up to 135, it gets a little more tricky/complicated.

But you could be correct! Maybe I didn't let the program run long enough to see how any subsequent keys would be handled.

Honestly, I wouldn't use the unmodded version, nor the 256 bit one on github (doesn't work).

To be safe, use Etayson's Kangaroo on github or mod your own version. That's the safer bet.

You can't because GPU uses only 128 bit variable to store distance on each kernel call, it means that when kangaroo jumps out of 128 bit space, all subsequent jumps are calculated incorrectly.

130 puzzle still can be solved with unmodified JLP's kangaroo if you divide 129 bit space into two 128 bits parts, but kangaroos still can jumps out, so you have to control the wrong DPs.

thank you, can you tell me please the math that has to do if address is 3?
i am not good with it and want to make sure i can do it, otherwise waste my time haha

WanderingPhilospher thanks for your answer.

To succeed with further puzzles we definitely need an upgrade in tools, something combining different algorithms in one search also a pooling idea to eliminate already scanned ranges. 

No, no, no. DO not break the space/range into two parts.

First off, I believe it can solve up to 128 to 129 bits (on its own), I think JLP put 125 because of the puzzle, meaning 125 would possibly be the last one his program, unmodded, would solve.

If you extract a workfile, you will see that it holds 128 bits of info for the point and distance, which equates to 32 characters. As you know, 130 contains 33 characters. So I still believe it could solve 130 and then you would have to do some manual math (nothing hard) to get the actual private key. If the key starts with a 2, I think it would not require the manual math, but if it starts with a 3, then it will.

If you are worried about messing something up, and you use windows, I would suggest using Etayson's EtarKangaroo on github. It is good up to 192 bits.


Different programs; the best way I can explain it, to keep it simple, one is deterministic and one is probabilistic. IMO, BSGS is fast and better for smaller ranges, but Kangaroo is better in larger ranges. I also think it comes down to, do you have a modern PC with lots of RAM, maybe you go with BSGS; if you have GPUs, maybe you go with Kangaroo or BSGS Cuda. Maybe some mods could be made to build a BSGS server/client that would rival Kangaroo in larger ranges.

i've been reading this thread since last week till now and I don't find the answer

so if the program is limited to 125bit interval, if i want to search for puzzle 130bit key, do i break the address space to 2 parts and run twice or on 2 computers and then merge?

how is the result, is it the private key in the result.txt file or do I need to do some scalar math to get the key

please help explain, thanks

I probably miss something here, but please explain why do you guys use Kangaroo while there is another tool Keyhunt, which BSGS option is very very fast. With above average hardware, you can get around 10 exa keys per second. That is 10,000,000,000,000,000,000 keys per second.  I have never seen such numbers with Kangaroo.

I think GPU_GRP_SIZE should be small as possible to fit SM L1 cache, because it used most frequently.
2048 in KeyHuntCuda (rotorcuda) is too big and huge global memory pressure because of this.
As I understand more NB_RUN = less kernel calls from CPU code. It doing NB_RUNs of GPU_GRP_SIZE.

I'm using Nsight Compute and GPU-Z sensors data to experiment with different values.

Yes, I described the brute force approach on the entire range like I mentioned from the start just to give an idea of the magnitude of the scanning process.

I didn't know how Kangaroo works. (I admit, I didn't used it, just compiled once last year to see how it works, but quit using it, as I was involved only in puzzle 66).

Now after I read something on JLP Kangaroo's readme on github and how it works , you are right, but still requires enough power to do 2^66.05 operations per second, that's ~ 750 GK/s, so you still need 100 x RTX 4090 to maximize your chances to find it faster than anyone else, but that's a serious env which costs goes over the benefits if you do not find it in 2 Months or less.

---

+1 on this, can we see at least the logic you used, if you do not want to share your work you used to change that, perhaps a code snippet?

And did you reached that speed without anyother change? Going from 2500Mk/s to almost 7750Mk/s is something.

Also I do not see in any class from the JLP Kangarroo the use of GPUGroup.h, is that generated separately or it was migrated from VanitySearch and keept in the project?

Why the use of only 128 in GPU_GRP_SIZE as in KeyHuntCuda was 2048?

What's the relation between this constants?

Yeah...that's not how it works. What you are describing/showing the math for is a brute force approach.

With Kangaroo, and #130, you need to do 130/2 + 1.05 = 2^66.05 ops.

Now, recalculate.

I do not want to be offtopic, but guys did you calculated what computing speed is required to scan the entire range of 130 puzzle?

For the range: 200000000000000000000000000000000:3ffffffffffffffffffffffffffffffff, which have: 680564733841876926926749214863536422912 total keys to scan, on a speed of 100 YottaK/s it would take almost 215657 years to finish 

Not to mention that the highest reported speed on a single 4090 was only 7-8Gk/s .

So is there something that I miss, why you still bother to scan beyond 125?

I mean even if you change the bit range to scan to 160 bit range, is still impossible with the current gpu's, maybe with photonic gpu's we might have a chance.

What do you think about this mod:

If add this:

  err = cudaSetDeviceFlags(cudaDeviceScheduleBlockingSync);
  if (err != cudaSuccess) {
      printf("GPUEngine: %s\n", cudaGetErrorString(err));
      return;
  }

after this:

  err = cudaSetDevice(gpuId);
  if(err != cudaSuccess) {
    printf("GPUEngine: %s\n",cudaGetErrorString(err));
    return;
  }

in GPUEngine constructor

then you don't need this (this is bad by design just do nothing for 1ms and GPU just idling):

 // Use cudaMemcpyAsync to avoid default spin wait of cudaMemcpy wich takes 100% CPU
 cudaEvent_t evt;
 cudaEventCreate(&evt);
 cudaMemcpyAsync(outputItemPinned,outputItem,4,cudaMemcpyDeviceToHost,0);
 cudaEventRecord(evt,0);
 while(cudaEventQuery(evt) == cudaErrorNotReady) {
   // Sleep 1 ms to free the CPU
   Timer::SleepMillis(1);
 }
 cudaEventDestroy(evt);

and you can use:

gpu->Launch(gpuFound, true);

and it will be no spinwait cpu usage because of cudaSetDeviceFlags(cudaDeviceScheduleBlockingSync) set

Thanks.

Thanks WanderingPhilospher for the quick answer, i am sorry as i was away for few days.

Also many thanks for the explanation, you are very right  Etar Kangaroo didn't even start and i was wondering why but as you explained the range was very small.
After using a bigger range (as you did) and i even used bigger range and found the key - perfect.

Then i started it with the #130 and the full range .. and after 24h there was 100GB of work file but nothing was found - as expected  

Now i started it with the fractional but as you know it uses the JeanLucPons Kangaroo (which loses performance) but lets see how it goes.

Another issue with the tools is the good explanation of the parameters and the configuration also some more detailed information behind those to understand how and why to use them.

by the way, are you the developer of this https://github.com/WanderingPhilosopher/VanBitCrackenRandom2 ... seems you are also very expert in that subject  


Thanks citb0in for your response and the info about the Kanga-256.

I wish to spend more time on this subject, but not easy.

I will update you about any progress

Regards

---

So an update, ... after running the fractional for 24h the speed of Kangaroo went from 1300 MK/s to 27 MK/s without a result.

Today i started your VBCr v2.00 on #66 which is running with the constant speed around 1300 MK/s since few hours.