Pollard's kangaroo ECDLP solver

[WanderingPhilospher]

I pushed an update to Kangaroo-256 a couple of days ago that fixes the botched GPU implementation. https://gitea.datahoarding.agency/ZenulAbidin/Kangaroo-256

Next I want to add the ability to create your own dpmask - whether you want certain bits to always be set and others always be cleared. I think I will need two different masks for this, one for the bits that should be set and another for the ones that should be cleared.

Currently all of the dpmask bits are at the left of every kangaroo but I think the ability to define it at random positions could influence the speed it takes to find a collision. I could even make the dpmask to change at random it I want to.

Hi NotATether, can you please explain what this version with 256 can do that the original version from JeanLucPons can not do ?

- Is it just faster ?
- can solve ranges that the JeanLucPons version can not solve (like puzzle 160 for example because the key space is wider)?

I know that i am a bit later as that was posted 3 years ago, but i find the subject very interesting.

Regards

Yes, you are correct, it was meant to expand the search range, like you said, be able to solve 160.

However, I am pretty sure it had bugs or speed was lost. I'm not sure it he has tinkered with it any more since his original post.

Check out Etar's kangaroo version; it is same as JLPs (but trailing DPs; zeros at the end) but can solve up to 192 bit range.

[Baboshka]

Yes, you are correct, it was meant to expand the search range, like you said, be able to solve 160.

However, I am pretty sure it had bugs or speed was lost. I'm not sure it he has tinkered with it any more since his original post.

Check out Etar's kangaroo version; it is same as JLPs (but trailing DPs; zeros at the end) but can solve up to 192 bit range.

Hi WanderingPhilospher, thanks for the quick answer

Actually the 256 version is not working, i cloned the code from the Repo and build it with CUDA 12.3 & sm_86 and tested it with the same example from JeanLucPons
This one

Code:

49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
0335BB25364370D4DD14A9FC2B406D398C4B53C85BE58FCC7297BD34004602EBEC

The original JeanLucPons Kangaroo took 1:30 to find both minute while this 256 version didn't find anything even after 20 min ... therefore i think its not helpful.

Regarding the Etar's kangaroo .. you mean this one https://github.com/Etayson/Etarkangaroo ?
I wonder why there is no source code

what do you mean with this "trailing DPs; zeros at the end" can you explain more please

Regards

[WanderingPhilospher]

Yes, you are correct, it was meant to expand the search range, like you said, be able to solve 160.

However, I am pretty sure it had bugs or speed was lost. I'm not sure it he has tinkered with it any more since his original post.

Check out Etar's kangaroo version; it is same as JLPs (but trailing DPs; zeros at the end) but can solve up to 192 bit range.

Hi WanderingPhilospher, thanks for the quick answer

Actually the 256 version is not working, i cloned the code from the Ripo and build it with CUDA 12.3 & sm_86 and tested it with the same example from JeanLucPons
This one

Code:

49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
0335BB25364370D4DD14A9FC2B406D398C4B53C85BE58FCC7297BD34004602EBEC

The original JeanLucPons Kangaroo took 1:30 to find both minute while this 256 version didn't find anything even after 20 min ... therefore i think its not helpful.

Regarding the Etar's kangaroo .. you mean this one https://github.com/Etayson/Etarkangaroo ?
I wonder why there is no source code

what do you mean with this "trailing DPs; zeros at the end" can you explain more please

Regards

The source code is there. It's built with PureBasic. Nice, simple, clean code.

DPs can be at the beginning, middle, end.

JLPs DPs (Zeros) are leading, meaning they are at the beginning. I believe Etar's are trailing, at the end.

So JLP DP 20 = 00000xxxxxxx
Etar's DP 20  = xxxxxxx00000

It doesn't matter if they are trailing or leading. Both are good and work.

Test Etar's version out.

[Baboshka]

The source code is there. It's built with PureBasic. Nice, simple, clean code.

DPs can be at the beginning, middle, end.

JLPs DPs (Zeros) are leading, meaning they are at the beginning. I believe Etar's are trailing, at the end.

So JLP DP 20 = 00000xxxxxxx
Etar's DP 20  = xxxxxxx00000

It doesn't matter if they are trailing or leading. Both are good and work.

Test Etar's version out.

Thanks @WanderingPhilospher, I really didn't notice the PureBasic code.
I have been developing software since 30 years and have experience with many programming languages but first time to see the PureBasic but is also seems not difficult.

I really wish to do something in this Vanity search subject, not because of the puzzle only but its very interesting and challenging.

My problem is that I am not that deep in this Bitcoin Private/Public keys, also not having any idea how CUDA really works, also need to read about the Pollard's kangaroo algorithm.

What I also noticed, and also from my experience that many developers never test their own software well (I am not complaining, actually I am thankful for everyone sharing the code) therefore most of the time those tools never work correctly.

As I told before, after testing the Kangaroo-256 with the examples of JeanLucPons and got no result, I started doubting the other tools therefore I created a simple test tile the same as the one from JeanLucPons but in the range of puzzle 130 but with a very small range as following

Code:

2F633CBE3EC02B9401000000007000000
2F633CBE3EC02B9401000000009000000
021c20007f8c8984d403a695494d6afbff37f55a01c8bd1aafb9b958fa9485bb02

which is small range of about 33M and the PKey is 2F633CBE3EC02B9401000000008000000 and run the following

• Kangaroo 2.2 (JeanLucPons) : found the key in 15secs
• Kangaroo 2.3 (NotATether) : no result
• Etar-Kangaroo : no result
• Rotor-Cuda: found key in few seconds - like Kangaroo 2.2

I am not sure if I am starting those tools with the correct options but i think there is no much to give.

That was my observation ..

I will be very happy if can get a change to talk to JeanLucPons, as hi code is not that easy

[WanderingPhilospher]

The source code is there. It's built with PureBasic. Nice, simple, clean code.

DPs can be at the beginning, middle, end.

JLPs DPs (Zeros) are leading, meaning they are at the beginning. I believe Etar's are trailing, at the end.

So JLP DP 20 = 00000xxxxxxx
Etar's DP 20  = xxxxxxx00000

It doesn't matter if they are trailing or leading. Both are good and work.

Test Etar's version out.

Thanks @WanderingPhilospher, I really didn't notice the PureBasic code.
I have been developing software since 30 years and have experience with many programming languages but first time to see the PureBasic but is also seems not difficult.

I really wish to do something in this Vanity search subject, not because of the puzzle only but its very interesting and challenging.

My problem is that I am not that deep in this Bitcoin Private/Public keys, also not having any idea how CUDA really works, also need to read about the Pollard's kangaroo algorithm.

What I also noticed, and also from my experience that many developers never test their own software well (I am not complaining, actually I am thankful for everyone sharing the code) therefore most of the time those tools never work correctly.

As I told before, after testing the Kangaroo-256 with the examples of JeanLucPons and got no result, I started doubting the other tools therefore I created a simple test tile the same as the one from JeanLucPons but in the range of puzzle 130 but with a very small range as following

Code:

2F633CBE3EC02B9401000000007000000
2F633CBE3EC02B9401000000009000000
021c20007f8c8984d403a695494d6afbff37f55a01c8bd1aafb9b958fa9485bb02

which is small range of about 33M and the PKey is 2F633CBE3EC02B9401000000008000000 and run the following

• Kangaroo 2.2 (JeanLucPons) : found the key in 15secs
• Kangaroo 2.3 (NotATether) : no result
• Etar-Kangaroo : no result
• Rotor-Cuda: found key in few seconds - like Kangaroo 2.2

I am not sure if I am starting those tools with the correct options but i think there is no much to give.

That was my observation ..

I will be very happy if can get a change to talk to JeanLucPons, as hi code is not that easy

JLP doesn't respond much these days. I know his code works (but is limited to x bits) because his code was used to solve #110 and #115. Not sure about #120 or #125 because no one has claimed they solved them and what was used.

did you run the normal etar kangaroo or the fractional one?

UPDATE:
Try etar's again. Here's the thing, your initial range size is 2^26; his says the range has to be higher than 2^32 (or else it's just a waste of time since even a brute force program can find that within seconds)

Try this config:
-rb 2F633CBE3EC02B9401000000000000000 -re 2F633CBE3EC02B94010000000ffffffff -pub 021c20007f8c8984d403a695494d6afbff37f55a01c8bd1aafb9b958fa9485bb02

I ran it and it found the key.

[citb0in]

... therefore most of the time those tools never work correctly.

As I told before, after testing the Kangaroo-256 with the examples of JeanLucPons and got no result, I started doubting the other tools therefore I created a simple test tile the same as the one from JeanLucPons but in the range of puzzle 130 but with a very small range as following

Code:

2F633CBE3EC02B9401000000007000000
2F633CBE3EC02B9401000000009000000
021c20007f8c8984d403a695494d6afbff37f55a01c8bd1aafb9b958fa9485bb02

which is small range of about 33M and the PKey is 2F633CBE3EC02B9401000000008000000 and run the following

• Kangaroo 2.2 (JeanLucPons) : found the key in 15secs
• Kangaroo 2.3 (NotATether) : no result
• Etar-Kangaroo : no result
• Rotor-Cuda: found key in few seconds - like Kangaroo 2.2

What exactly is your question? JLP Kangaroo works without any problems and as far as I have understood your statement correctly, you confirm this yourself. You found the key with JLP software, or have I misunderstood something?

[WanderingPhilospher]

... therefore most of the time those tools never work correctly.

As I told before, after testing the Kangaroo-256 with the examples of JeanLucPons and got no result, I started doubting the other tools therefore I created a simple test tile the same as the one from JeanLucPons but in the range of puzzle 130 but with a very small range as following

Code:

2F633CBE3EC02B9401000000007000000
2F633CBE3EC02B9401000000009000000
021c20007f8c8984d403a695494d6afbff37f55a01c8bd1aafb9b958fa9485bb02

which is small range of about 33M and the PKey is 2F633CBE3EC02B9401000000008000000 and run the following

• Kangaroo 2.2 (JeanLucPons) : found the key in 15secs
• Kangaroo 2.3 (NotATether) : no result
• Etar-Kangaroo : no result
• Rotor-Cuda: found key in few seconds - like Kangaroo 2.2

What exactly is your question? JLP Kangaroo works without any problems and as far as I have understood your statement correctly, you confirm this yourself. You found the key with JLP software, or have I misunderstood something?

He was talking about the Kanga-256 version. He used it with the examples (configuration of cmd line/input text) and it did not find the key. I believe NotATether can confirm it has bugs/slow speed. I know he worked on that years ago and I'm not sure he has messed with it since.

[citb0in]

I see.

well, although I have not tested the Kanga-256 myself, I can add the following: the version of VanitySearch modified by NotATether not only had drastic performance losses compared to the original VanitySearch but also had several bugs and did not work properly. I tested it several times and came to the conclusion that the program is useless because it does not work reliably. I would therefore not trust this modified Kanga-256 (which is also in line with the results you already experiences by yourself) and would rather stick with the original program from JLP. This is just my personal opinion.

[Baboshka]

JLP doesn't respond much these days. I know his code works (but is limited to x bits) because his code was used to solve #110 and #115. Not sure about #120 or #125 because no one has claimed they solved them and what was used.

did you run the normal etar kangaroo or the fractional one?

UPDATE:
Try etar's again. Here's the thing, your initial range size is 2^26; his says the range has to be higher than 2^32 (or else it's just a waste of time since even a brute force program can find that within seconds)

Try this config:
-rb 2F633CBE3EC02B9401000000000000000 -re 2F633CBE3EC02B94010000000ffffffff -pub 021c20007f8c8984d403a695494d6afbff37f55a01c8bd1aafb9b958fa9485bb02

I ran it and it found the key.

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

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.

[3dmlib]

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.

[CryptoMaster84]

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.

[WanderingPhilospher]

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.

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.

[CryptoMaster84]

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.

but I had tweaked the way DPs were found.

Can we have your code?

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

Code:

// Number of random jumps
// Max 512 for the GPU
#define NB_JUMP 32

// GPU group size
#define GPU_GRP_SIZE 128

// GPU number of run per kernel call
#define NB_RUN 64

[3dmlib]

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

What's the relation between this constants?

Code:

// Number of random jumps
// Max 512 for the GPU
#define NB_JUMP 32

// GPU group size
#define GPU_GRP_SIZE 128

// GPU number of run per kernel call
#define NB_RUN 64

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.

[De_Freedom]

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.

[whataburger9]

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

you can search for privatekeys up to 256 bit, but program is limited to a 125bit interval search


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

[WanderingPhilospher]

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

you can search for privatekeys up to 256 bit, but program is limited to a 125bit interval search


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

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.

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.

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.

[De_Freedom]

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. 

[whataburger9]

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

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

you can search for privatekeys up to 256 bit, but program is limited to a 125bit interval search


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

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.

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.

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.

[_Counselor]

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.

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.