Pollard's kangaroo ECDLP solver

[NotATether]

What do you mean, run it in some other system that runs it later?

Yeah, just like you can save and merge the DPs into a file and run them again, you'll be able to save all of the points that have been crossed in a file and load and merge them again.

The idea is to reduce the running time by skipping all the math calculations for these points, but it becomes largely useless for large interval sizes since it's impractical to store more than 100 million points (compressed with no padding) on disk, and that'll already make several hundred gigabytes.

What is the binary search you speak of?

We could sort the points on file by their numerical value and then use binary search to see if a given point is in the file, without checking thousands of points, rather only a few dozen points in O(log n) time.

[WanderingPhilospher]

We could sort the points on file by their numerical value and then use binary search to see if a given point is in the file, without checking thousands of points, rather only a few dozen points in O(log n) time.

So start a collection of sorts? Everyone would have to search for same DP size and same ranges, and pubkeys...if you are talking of using it to solve one of the puzzle keys. If just in general, how could this help?

I have probably close to 60 million DPs of various sizes, but they are mostly trailing.

I still wonder which one is faster/more effective in searching for, leading, trailing, or in the middle.

Edit: Also, I guess you could just store the point, but seems like storing the distance, at least for the tames, would be better because you can recreate the point from the distance. Wilds would only be good if looking for same pubkey, with same range (For Jean Luc's, because you add/subtract difference of wild and tame and add back start range)

[fxsniper]

for using Kangaroo.exe example puzzle 64 bits still very large
if using 8000000000000000 to fffffffffffffff may be too much large

but if use split rank to very small  size example 8000000000000000  to 800000004190AB00  (and next each 10000000000000)

I test some address by using rank not so far from private key, Kangaroo work very fast.

What recommend for Kangaroo.exe search by fast?

[bigvito19]

for using Kangaroo.exe example puzzle 64 bits still very large
if using 8000000000000000 to fffffffffffffff may be too much large

but if use split rank to very small  size example 8000000000000000  to 800000004190AB00  (and next each 10000000000000)

I test some address by using rank not so far from private key, Kangaroo work very fast.

What recommend for Kangaroo.exe search by fast?

No it wouldn't with kangaroo if the public key for #64 was exposed it would be 2^32 or 2^33 search range, can be solved in an hour or less.

[WanderingPhilospher]

for using Kangaroo.exe example puzzle 64 bits still very large
if using 8000000000000000 to fffffffffffffff may be too much large

but if use split rank to very small  size example 8000000000000000  to 800000004190AB00  (and next each 10000000000000)

I test some address by using rank not so far from private key, Kangaroo work very fast.

What recommend for Kangaroo.exe search by fast?

As big said, you can't use Kangaroo for #64; also, it's hard to break up a range when using Kangaroo, because you never know if a key was truly in a subrange unless you run the full group ops through the range. But any 64 bit key can be found within minutes with a CPU, seconds with a GPU.

If you want to break up ranges, I would use BSGS as it checks entire range and you know 100% if key is in that range or not.

[mamuu]

Hello there
Generally, I use sagemath, but in this project I am trying to do what I do there in C.

Point * ScalarNumber
I could not see a method for processing

I added it here. I'm not a complete programmer so I'm writing it here.

It works for CPU but I want to run this method with GPU.
Can you help me ?

File Name Secp256K1.cpp

Code:

Point Secp256K1::ECMultiply(Point& p, Int* scalar)
{
    if(scalar->IsZero() || scalar->IsEqual(&order))
        exit(NULL);

    string scalarBin = scalar->GetBaseN(2, "01");
    const char* sclarBinChar = scalarBin.c_str();
    Point tempP = p;

    //tempP = DoubleDirect(tempP);
    //cout << "tempP: " << tempP.x.GetBase10() << "\n";

    for (int i = 1; i < strlen(sclarBinChar); i++)
    {
        tempP = DoubleDirect(tempP);

        if (sclarBinChar[i] == sclarBinChar[0])
        {
            //cout << "Add" << "\n";
            tempP = AddDirect(tempP, p);
        }
    }
    return tempP;
}

[NotATether]

Hello there
Generally, I use sagemath, but in this project I am trying to do what I do there in C.

Point * ScalarNumber
I could not see a method for processing

I added it here. I'm not a complete programmer so I'm writing it here.

It works for CPU but I want to run this method with GPU.
Can you help me ?

~snip

When you say running on GPU, do you mean only on NVIDIA GPUs, so CUDA, or on all GPUs, meaning OpenCL?

I can give you some advice to help you CUDA'ify your function, but first you have to install the CUDA Toolkit.

You should modify your function to pass the return value as a pointer argument, so that the function itself returns void. Also change all references to pointers, I have no idea how CUDA will handle references.

Move the exit() function outside of the function so that it runs on the CPU. You can do that by setting the return value to some null value on failure and then copying it to the CPU, then on the CPU make a condition that exits the program if it's NULL.

Once you do that, put __global__ in front of the function signature like this: __global__ void ECMultiply(Point* p, Int* scalar, Point* ret) (external function, do not make it a method). Change the file extension to .cu and then you're all set!
 

[mamuu]

I am not familiar with the C programming language. Trying to understand just by reading the code I do,
I installed CudaToolkit 10.2 and opened the project in Visual Studio. I have left some parameters from main.ccp.
i don't know how and what to change

I wrote my running main.ccp file here.
https://bitcointalk.org/index.php?topic=5244940.msg56416339#msg56416339

I added the ECmultipy method to the secp256K1.ccp file. He works on the project. With CPU only

OpenCL or Cuda? I am currently using Nvidia Card. As far as I understand, OpenCL looks more advantageous. My goal is to reach the EllipticCurve Point Arithmetic library that works with more than one graphics card. Running Graphics Cards Rig line or Graphics card sharing system such as https://vast.ai
For now, I want to try it on my own computer.

About 2 weeks ago I didn't know anything about C. I learn by researching and experimenting.

Here's a simple control draft code for GPU .

Code:

PrMod = 3618502788666131106986593281521497120414687020801267626233049500247285301313
ScalarNumber=0
while True :
    ScalarNumbe = ScalarNumber +1 
    
    NewPoint = Point * i #for C -> Point NewPoint= secp256k1.ECMultiply(G, &ScalarNumber );
    
    if NewPoint.x % PrMod == 85070591730234615865843651857942052871 :
        SaveScalarFile(ScalarNumber)

I would really apreciate if you help. thank you for your interest.

[WanderingPhilospher]

Code:

PrMod = 3618502788666131106986593281521497120414687020801267626233049500247285301313
ScalarNumber=0
while True :
    ScalarNumbe = ScalarNumber +1 
    
    NewPoint = Point * i #for C -> Point NewPoint= secp256k1.ECMultiply(G, &ScalarNumber );
    
    if NewPoint.x % PrMod == 85070591730234615865843651857942052871 :
        SaveScalarFile(ScalarNumber)

I would really apreciate if you help. thank you for your interest.

What are you trying to do, exactly? Create a version where multiple GPUs/CPUs can contribute to what/on what?

[mamuu]

Actually my question is about doing operation on the GPU, not about what I am trying to do.

I just wrote an example that I want to experiment with.

I generally experiment, read articles, but processing speed takes a lot of time.

For example, I wanted to experiment by reading the last discussion here.

https://math.stackexchange.com/questions/873843/cyclic-group-presentation

[WanderingPhilospher]

Actually my question is about doing operation on the GPU, not about what I am trying to do.

I just wrote an example that I want to experiment with.

I generally experiment, read articles, but processing speed takes a lot of time.

For example, I wanted to experiment by reading the last discussion here.

https://math.stackexchange.com/questions/873843/cyclic-group-presentation

Ok. Well the code you are looking at/tweaking is full of GPU code, and the program works with multiple GPUs.  That's why I asked. Are you trying to tweak and make your own Kangaroo program or something else??

[mamuu]

Actually my question is about doing operation on the GPU, not about what I am trying to do.

I just wrote an example that I want to experiment with.

I generally experiment, read articles, but processing speed takes a lot of time.

For example, I wanted to experiment by reading the last discussion here.

https://math.stackexchange.com/questions/873843/cyclic-group-presentation

Ok. Well the code you are looking at/tweaking is full of GPU code, and the program works with multiple GPUs.  That's why I asked. Are you trying to tweak and make your own Kangaroo program or something else??

sorry, I didn't understand what is not understood,

just

I want to make an Elliptic Curve Arithmetic GPU Based Library. I'm working on developing new algorithms like kangaroo

thank you

[NotATether]

OpenCL or Cuda? I am currently using Nvidia Card. As far as I understand, OpenCL looks more advantageous. My goal is to reach the EllipticCurve Point Arithmetic library that works with more than one graphics card. Running Graphics Cards Rig line or Graphics card sharing system such as https://vast.ai
For now, I want to try it on my own computer.

Sounds like you should go with OpenCL then. I think there's an SDK bundled with CUDA toolkit IIRC, but you definitely already have OpenCL drivers provided by NVIDIA installed.

You are better off skimming an OpenCL tutorial first such as https://www.codeproject.com/Articles/92788/Introductory-Tutorial-to-OpenCL without actually writing the example code in there since you don't need them.

I'd probably move out the file saving code from the GPU, you'll only be able to save files from C language on CPU.

[NotATether]

Note: This was posted in the VanitySearch thread by mistake and I later moved it here.

Does anyone here know if the GPU engine makes use of the flags at the end of "distance"? In the ITEM struct there is px,py for X and Y coordinate of a kangaroo and then there's a "d" member 128-bits long that's for the distance.

In the CPU engine the 126'th bit is used as the kangaroo type and the 127'th bit is used as a sign bit.

 It in GPU/GPUEngine.cu it doesn't look like the type bit is used at all:

Code:

void GPUEngine::SetKangaroo(uint64_t kIdx,Int *px,Int *py,Int *d) {

  int gSize = KSIZE * GPU_GRP_SIZE;
  int strideSize = nbThreadPerGroup * KSIZE;
  int blockSize = nbThreadPerGroup * gSize;

  uint64_t t = kIdx % nbThreadPerGroup;
  uint64_t g = (kIdx / nbThreadPerGroup) % GPU_GRP_SIZE;
  uint64_t b = kIdx / (nbThreadPerGroup*GPU_GRP_SIZE);
...

In my (experimental in-development) build of Kangaroo I moved the flags out to an extra parameter so I would like to know if I can safely remove that from here.

[WanderingPhilospher]

Note: This was posted in the VanitySearch thread by mistake and I later moved it here.

Does anyone here know if the GPU engine makes use of the flags at the end of "distance"? In the ITEM struct there is px,py for X and Y coordinate of a kangaroo and then there's a "d" member 128-bits long that's for the distance.

In the CPU engine the 126'th bit is used as the kangaroo type and the 127'th bit is used as a sign bit.

 It in GPU/GPUEngine.cu it doesn't look like the type bit is used at all:

In my (experimental in-development) build of Kangaroo I moved the flags out to an extra parameter so I would like to know if I can safely remove that from here.

Here are what they look like:

Code:

63a169e28af90b75159c93ac88638314 -0000006f7d4a376f241adf3febd1ce73
779155e640a6f97c0d87b47ee5eec0f6 00000bc152a6b02a0bc5730dd5be8ae0

[NotATether]

Here are what they look like:

Code:

63a169e28af90b75159c93ac88638314 -0000006f7d4a376f241adf3febd1ce73
779155e640a6f97c0d87b47ee5eec0f6 00000bc152a6b02a0bc5730dd5be8ae0

Since these are all 128-bit numbers I'm guessing the left numbers are tame kangaroo positions and the right numbers are distances (with their bit 126 set to 0=TAME constant) right?

This might sound like a dumb question but I also assume the px and py pointers above are the public keys right? No way those can be private keys or kangaroo positions because there are two of these.

[WanderingPhilospher]

Here are what they look like:

Code:

63a169e28af90b75159c93ac88638314 -0000006f7d4a376f241adf3febd1ce73
779155e640a6f97c0d87b47ee5eec0f6 00000bc152a6b02a0bc5730dd5be8ae0

Since these are all 128-bit numbers I'm guessing the left numbers are tame kangaroo positions and the right numbers are distances (with their bit 126 set to 0=TAME constant) right?

This might sound like a dumb question but I also assume the px and py pointers above are the public keys right? No way those can be private keys or kangaroo positions because there are two of these.

These are wild DPs, tames do not use the '-' signs as they are all positive?

Yes, if you looked at a tame file, the left is pubkey x coord and that pubkey's priv key is on the right side. For the wild, the distance is based off of Y coord position, not distance traveled...I do believe that's how it works. Basically, if you took a wild dp and ran the priv key, it wouldn't correlate to the pubkey but the tames do.

Here are examples of mine:
Tames

Code:

3AA3BB15292F3A2688A85F1DC635E159BF18120631AE07AA4844EF9D00000000 000000000000000000000000000000000000000000136B4461F2984CBB55F8CA
1B91BF8C8C3993578623E10E9D979FE8C3FAE2C390A48997930416A700000000 0000000000000000000000000000000000000000001E70CC8AAB08D481DD25AD

Wilds

Code:

087A24CA49535730AAEFBAB161100740BECF3187F27E9F94FA34709B00000000 0000000000000000000000000000000000000000000A021D0CD9D38B5BA7639D
79E73EC2D79A6E794B692B03910D31137936859E9505B92316AA807000000000 00000000000000000000000000000000000000000001D3C65E1F9264DECB72ED

[fxsniper]

I would like to learn more about kangaroo code for modify.
may be start from kangaroo python script one file easy to modify than C++ code
(sorry I am not coding I am not programmer, just power user know more about computer more end user)

may be my mistake modify code will make kangaroo  jump to hit target LOL.

I know kangaroo is code best already. may be change it make it not kangaroo.

just want try to so some possible.

What is kangaroo variable to can modify it like add more value to high?

What is kangaroo power variable on code?

What is tame and wild on kangaroo ?
look like two array and program do compare two value inside right?

[WanderingPhilospher]

I would like to learn more about kangaroo code for modify.
may be start from kangaroo python script one file easy to modify than C++ code
(sorry I am not coding I am not programmer, just power user know more about computer more end user)

may be my mistake modify code will make kangaroo  jump to hit target LOL.

I know kangaroo is code best already. may be change it make it not kangaroo.

just want try to so some possible.

What is kangaroo variable to can modify it like add more value to high?

What is kangaroo power variable on code?

What is tame and wild on kangaroo ?
look like two array and program do compare two value inside right?

@fx; the quick version. The kangaroo program basically creates wild and tame kangaroos. Both are set out to look for the distinguish point size you designate. So let's say you set dp to 20 (that will be a pubkey that has 5 leading zeros 0x00000; 5x4 = 20). Each time a dp is found, it is recorded in a hash table (the location and the distance traveled), if a tame visits a dp and a wild visits the same dp, then the key is solved. The kangaroos keep hopping around until a "collision" occurs when a tame and wild visit same dp (location).
Now, you talk about modifying it to not make it a kangaroo program, what would you want or change? Might be a better program to tweak to suit what you are looking for.

[fxsniper]

@fx; the quick version. The kangaroo program basically creates wild and tame kangaroos. Both are set out to look for the distinguish point size you designate. So let's say you set dp to 20 (that will be a pubkey that has 5 leading zeros 0x00000; 5x4 = 20). Each time a dp is found, it is recorded in a hash table (the location and the distance traveled), if a tame visits a dp and a wild visits the same dp, then the key is solved. The kangaroos keep hopping around until a "collision" occurs when a tame and wild visit same dp (location).
Now, you talk about modifying it to not make it a kangaroo program, what would you want or change? Might be a better program to tweak to suit what you are looking for.

Thank you very very much WanderingPhilospher

you explain quick version and with image illustration  on JeanLucPons Kangaroo github page now I understand better
https://raw.githubusercontent.com/JeanLucPons/Kangaroo/master/DOC/paths.jpg
first time I just read code and try understand

good to know how tools it works (better than use tools only)

How can we know what happen with higher bits or large range ?
may be start point long too much difference
I try to find what problem and fix that point

I think may be try to write code to save data to can read like  image illustration plot graph

How 2 public point X, Y (from public key) use to calculate on Kangaroo?

I think I need to more learn fundamental basic and help can figure out