Pollard's kangaroo ECDLP solver

[3dmlib]

you need instead the DoubleDirect function:
https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L438  

Thanks.
DoubleDirect() works, but it only about 10% faster, than do entire private key to public key calculation with ComputePublicKey() function.
Is any faster way possible to do this 'increment private key by 1 and get public key' method?

UPD: 25.12.2023
Actually DoubleDirect() also not working. It starting to calculate wrong keys after some interval. Why this is can happen?
The only function work so far for sequential private keys to public keys is ComputePublicKey().

[arulbero]

UPD: 25.12.2023
Actually DoubleDirect() also not working. It starting to calculate wrong keys after some interval. Why this is can happen?
The only function work so far for sequential private keys to public keys is ComputePublicKey().

For sequential private keys there is the NextKey function.

DoubleDirect does, as the name indicates, only the double of P.

Then, if you start from G:

G
P = DoubleDirect(G)  :  G -> P = 2G
P = NextKey(P)         :  P -> P+1 = 3G
P = NextKey(P)         :  P -> P+1 = 4G
P = NextKey(P)         :  P -> P+1 = 5G

and so on

[3dmlib]

UPD: 25.12.2023
Actually DoubleDirect() also not working. It starting to calculate wrong keys after some interval. Why this is can happen?
The only function work so far for sequential private keys to public keys is ComputePublicKey().

For sequential private keys there is the NextKey function.

DoubleDirect does, as the name indicates, only the double of P.

Then, if you start from G:

G
P = DoubleDirect(G)  :  G -> P = 2G
P = NextKey(P)         :  P -> P+1 = 3G
P = NextKey(P)         :  P -> P+1 = 4G
P = NextKey(P)         :  P -> P+1 = 5G

and so on

But what if I need to start not from G point...

Int* privateKey = "some random private key";
Point* point;

This is working:
point = secp->ComputePublicKey(&privateKey);
while(1)
{
   privateKey.AddOne();
   point = secp->ComputePublicKey(&privateKey);
}


This is NOT working:
point = secp->ComputePublicKey(&privateKey);
while(1)
{   
   point = secp->NextKey(point);
}

[WanderingPhilospher]

UPD: 25.12.2023
Actually DoubleDirect() also not working. It starting to calculate wrong keys after some interval. Why this is can happen?
The only function work so far for sequential private keys to public keys is ComputePublicKey().

For sequential private keys there is the NextKey function.

DoubleDirect does, as the name indicates, only the double of P.

Then, if you start from G:

G
P = DoubleDirect(G)  :  G -> P = 2G
P = NextKey(P)         :  P -> P+1 = 3G
P = NextKey(P)         :  P -> P+1 = 4G
P = NextKey(P)         :  P -> P+1 = 5G

and so on

But what if I need to start not from G point...

Int* privateKey = "some random private key";
Point* point;

This is working:
point = secp->ComputePublicKey(&privateKey);
while(1)
{
   privateKey.AddOne();
   point = secp->ComputePublicKey(&privateKey);
}


This is NOT working:
point = secp->ComputePublicKey(&privateKey);
while(1)
{   
   point = secp->NextKey(point);
}

Hard to tell anything without the results of what your program is spitting out.

What happens when you use NextKey? Give exact examples.

[arulbero]

This is NOT working:
point = secp->ComputePublicKey(&privateKey);
while(1)
{   
   point = secp->NextKey(point);
}

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L59C7-L59C60

Secp256K1::ComputePublicKey(Int *privKey,bool reduce)

do you set bool reduce = True?

[3dmlib]

do you set bool reduce = True?

Yes.
I'm using ComputePublicKey() function from vanitysearch project, not from kangaroo project. It do reduction by default at the end of ComputePublicKey() function.
NextKey() function still not working as it should.

[arulbero]

do you set bool reduce = True?

Yes.
I'm using ComputePublicKey() function from vanitysearch project, not from kangaroo project. It do reduction by default at the end of ComputePublicKey() function.
NextKey() function still not working as it should.

Looking at this code:

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L42C1-L52C4

Code:

  // Compute Generator table
  Point N(G);
  for(int i = 0; i < 32; i++) {
    GTable[i * 256] = N;
    N = DoubleDirect(N);
    for (int j = 1; j < 255; j++) {
      GTable[i * 256 + j] = N;
      N = AddDirect(N, GTable[i * 256]);
    }
    GTable[i * 256 + 255] = N; // Dummy point for check function
  }

I would try this:

Code:

Int* privateKey = "some random private key";

Point P(secp->ComputePublicKey(&privateKey));


while(1) {

      P = NextKey(P)
}

[3dmlib]

Hard to tell anything without the results of what your program is spitting out.

What happens when you use NextKey? Give exact examples.

// test 1 (WORKING) returns correct public key and BTC address for 0x01 and 0x02 private keys
privateKey.SetBase16((char*)"0000000000000000000000000000000000000000000000000000000000000001");
point = secp->ComputePublicKey(&privateKey);
std::cout << " (" << secp->GetPublicKeyHex(true, point) << ") [" << secp->GetAddress(P2PKH, true, point) << "]" << std::endl;

privateKey.AddOne();

point = secp->ComputePublicKey(&privateKey);
std::cout << " (" << secp->GetPublicKeyHex(true, point) << ") [" << secp->GetAddress(P2PKH, true, point) << "]" << std::endl;


// test 2 (NOT WORKING) returns correct public key and BTC address for 0x01 private key only
privateKey.SetBase16((char*)"0000000000000000000000000000000000000000000000000000000000000001");
point = secp->ComputePublicKey(&privateKey);
std::cout << " (" << secp->GetPublicKeyHex(true, point) << ") [" << secp->GetAddress(P2PKH, true, point) << "]" << std::endl;

point = secp->NextKey(point);

std::cout << " (" << secp->GetPublicKeyHex(true, point) << ") [" << secp->GetAddress(P2PKH, true, point) << "]" << std::endl;


// test 3 as arulbero suggested (NOT WORKING) returns correct public key and BTC address for 0x01 private key only
privateKey.SetBase16((char*)"0000000000000000000000000000000000000000000000000000000000000001");
Point P(secp->ComputePublicKey(&privateKey));
std::cout << " (" << secp->GetPublicKeyHex(true, secp->ComputePublicKey(&privateKey)) << ") [" << secp->GetAddress(P2PKH, true, secp->ComputePublicKey(&privateKey)) << "]" << std::endl;

P = secp->NextKey(P);   

std::cout << " (" << secp->GetPublicKeyHex(true, P) << ") [" << secp->GetAddress(P2PKH, true, P) << "]" << std::endl;

[arulbero]

But why you use 01 as starting point?  

I already told you:

For sequential private keys there is the NextKey function.

DoubleDirect does, as the name indicates, only the double of P.

Then, if you start from G:

G
P = DoubleDirect(G) :  G -> P = 2G
P = NextKey(P)         :  P -> P+1 = 3G
P = NextKey(P)         :  P -> P+1 = 4G
P = NextKey(P)         :  P -> P+1 = 5G

and so on

If you use 0000000000000000000000000000000000000000000000000000000000000002

as starting point it should work.

You can't compute G+G = 2G with NextKey, what is not clear?

Point Secp256K1::NextKey(Point &key) {
  // Input key must be reduced and different from G
  // in order to use AddDirect
  return AddDirect(key,G);
 }

You are using the NextKey in the only case you can't (and it is clearly written)

[3dmlib]

But why you use 01 as starting point?  

I already told you:

For sequential private keys there is the NextKey function.

DoubleDirect does, as the name indicates, only the double of P.

Then, if you start from G:

G
P = DoubleDirect(G) :  G -> P = 2G
P = NextKey(P)         :  P -> P+1 = 3G
P = NextKey(P)         :  P -> P+1 = 4G
P = NextKey(P)         :  P -> P+1 = 5G

and so on

If you use 0000000000000000000000000000000000000000000000000000000000000002

as starting point it should work.

You can't compute G+G = 2G with NextKey, what is not clear?

Point Secp256K1::NextKey(Point &key) {
  // Input key must be reduced and different from G
  // in order to use AddDirect
  return AddDirect(key,G);
 }

You are using the NextKey in the only case you can't (and it is clearly written)

Thank you very much. Now I understand, finally It working on CPU fine. Moving on to GPU

4090 cards have a lot more cache than previous ones.
Looking for changes to fit to cache as much data as possible to speed up kangaroo and prevent memory bottleneck kangaroo have.

[WanderingPhilospher]

4090 cards have a lot more cache than previous ones.
Looking for changes to fit to cache as much data as possible to speed up kangaroo and prevent memory bottleneck kangaroo have.

Code def needs tweaked to see if there as any pickup in performance.

Code also needs tweaked in how it finds DPs.

The best speed I got out of Kangaroo with a 4090 was 7,750 MKey/s and an A100 got 7,350 MKey/s; but I had tweaked the way DPs were found.

I haven't messed with the code since #125 was found though.

Hope you have success!

Just found old exe file and ran a full 44 bit range to check avg speed; 3060Ti = 2,685 MKey/s Kangaroo.

[3dmlib]

but I had tweaked the way DPs were found.

Can we have your code?

[Baboshka]

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

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