Topic: Pollard's kangaroo ECDLP solver - page 9. (Read 60582 times)

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

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

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

Can we have your code?

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.

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.

But why you use 01 as starting point?  

I already told you:


If you use 0000000000000000000000000000000000000000000000000000000000000002

as starting point it should work.

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



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

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

Looking at this code:

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


I would try this:

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.

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

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

do you set bool reduce = True?

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

What happens when you use NextKey? Give exact examples.

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

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

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().

A public key is a point of the elliptic curve. A point can be represented by 3 coordinates (X,Y,Z) (projective coordinates) or by 2 coordinates (x,y) (affine coordinates).

The passage from projective to affine coordinates is the "reduction"

x = X/Z
y = Y/Z

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/Point.cpp#L64



The addition between 2 points in projective coordinates is performed by the function Add:

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L369

and it is faster, because it avoids the inverse of x;


the addition between the same 2 points in affine coordinates is performed instead by the function AddDirect:

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L238.

To compute NextKey function (that calls the AddDirect function), you have:

a) to use a point in affine coordinates (because the AddDirect function needs affine coordinates)
b) to avoid the case P = G, because to perform G+G (in the general P + P ) the AddDirect function doesn't work

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

Hello.

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

Is anybody can explain me why this function in secp256k1.cpp file not work correctly?
As I understand it should return next public key like as increment private key by 1 and compute public key from it.
What is reduced public key?

Thanks.

After some tests I found that memory speed is an issue. It GPU memory bound, not GPU chip. This is why it can't scale well for more GPU cores.

I see. While i have no idea which optimization can be done, you might want to try fork of this software or implementation written by different people. Here are few example,
https://github.com/ZenulAbidin/Kangaroo-256
https://github.com/PawelGorny/Kangaroo
https://github.com/secoc/Pollard-Rho-kangaroo

P.S. i haven't tried any of those.

Yes. I tried all possible grid size combinations. Also, I tried to compile on latest cuda version using more recent compute_89 shader model. Same result. The maximum I have on 4090 is about 2500 MK/s. On 3090 is 2200 MK/s. 4090 should be faster. Looks like Kangaroo need some optimization for large number of cores 4090 have. Any ideas where this optimization can be made? Thanks.