Pollard's kangaroo ECDLP solver - page 71.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: mamuu on March 01, 2021, 10:47:37 AM

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

member

Activity: 73

Merit: 19

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

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: fxsniper on February 28, 2021, 02:45:30 AM

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.

bigvito19

full member

Activity: 706

Merit: 111

Quote from: fxsniper on February 28, 2021, 02:45:30 AM

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.

fxsniper

member

Activity: 406

Merit: 47

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?

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: NotATether on February 27, 2021, 03:33:27 AM

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)

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: WanderingPhilospher on February 26, 2021, 01:57:40 PM

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.

Quote from: WanderingPhilospher on February 26, 2021, 01:57:40 PM

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.

nioctib.co

jr. member

Activity: 64

Merit: 1

Quote from: nioctib.co on February 27, 2021, 01:44:21 AM

Hi,

Anyone here use -wsplit command?

If let's say I save a lot of work files. After merging all the files, I still unable to find the keys. So which save work file should I use to continue the work? Anyone have any idea about this because there is no output?

I think I got it already. Each time with 2 merge input and the last is output. If someone familiar with this, please correct me if I am wrong.

nioctib.co

jr. member

Activity: 64

Merit: 1

Hi,

Anyone here use -wsplit command?

If let's say I save a lot of work files. After merging all the files, I still unable to find the keys. So which save work file should I use to continue the work? Anyone have any idea about this because there is no output?

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: NotATether on February 26, 2021, 01:07:11 PM

Just another idea which came to my head. I was thinking what if we changed Kangaroo to dump the list of points that it has already jumped through for the same interval and pubkey into a file. That way it can be loaded into some other system that runs it later to avoid doing all that heavy math for that point since it knows that there cannot be a collision there.

1MB would fit 32000 points stored in binary or 4000 points stored in hex. The hex in particular can be heavily compressed with LZMA algorithm to save more space than if we just compressed them to byte form.

The points can all be sorted so that binary search becomes possible. How effective do you think this idea is?

What do you mean, run it in some other system that runs it later?
And you would never really know if a collision is there or not, unless you run the max group ops.
In a normal text document, I can store roughly 8 million points, 256 bits (64 chars) for the point and 256 bits (64 chars, padded with 0s) for the distance (all hex of course), and it takes up about 1 Gb.

What is the binary search you speak of?

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Just another idea which came to my head. I was thinking what if we changed Kangaroo to dump the list of points that it has already jumped through for the same interval and pubkey into a file. That way it can be loaded into some other system that runs it later to avoid doing all that heavy math for that point since it knows that there cannot be a collision there.

1MB would fit 32000 points stored in binary or 4000 points stored in hex. The hex in particular can be heavily compressed with LZMA algorithm to save more space than if we just compressed them to byte form.

The points can all be sorted so that binary search becomes possible. How effective do you think this idea is?

itod

legendary

Activity: 1974

Merit: 1077

^ Will code for Bitcoins

Quote from: fxsniper on February 26, 2021, 07:07:09 AM

I try to understand how to kangaroo.exe it work, how to Calculate?
I don't know c++
I try to read from python script kangaroo

Can anyone tell short, over view?

I think kangaroo get X and Y and generate pubkey and compare match with pubkey right?

Other idea Can possible find relationship from pubkey (or convert pubkey to decimal and use it)

Sorry I am not programmer, just power user. but I will try to learn.

You have all explanations in the opening post of this thread:
https://github.com/JeanLucPons/Kangaroo#how-it-works

fxsniper

member

Activity: 406

Merit: 47

I try to understand how to kangaroo.exe it work, how to Calculate?
I don't know c++
I try to read from python script kangaroo

Can anyone tell short, over view?

I think kangaroo get X and Y and generate pubkey and compare match with pubkey right?

Other idea Can possible find relationship from pubkey (or convert pubkey to decimal and use it)

Sorry I am not programmer, just power user. but I will try to learn.

_Counselor

member

Activity: 110

Merit: 61

Quote from: WanderingPhilospher on February 26, 2021, 01:17:05 AM

Sooooo what other files do you need merged? All files created from the program contain DPs. What is the final file?? If you mean you want to save the progress of the Kangaroos path, you would have to have prompted that before running the program.

I have several files contains kangaroos from multiple machines, that were running work on the CPU.
I want to continue work with that kangaroos on one single machine with GPU, which able to control all that kangaroos. With original solver I can load only one file, the missing kangaroos are created and starts a new paths.
So, I want to merge kangaroo's walks in one file, to continue their existing paths.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: _Counselor on February 26, 2021, 12:48:45 AM

Quote from: NotATether on February 26, 2021, 12:09:47 AM

There's merging functionally built in to Kangaroo, use -wm file1 file2 destfile for multiple files or -wmdir dir destfile to merge an entire directory full of work files (that it can recognize).

This option merges only DPs and final file gets cleaned from kangaroos.

Sooooo what other files do you need merged? All files created from the program contain DPs. What is the final file?? If you mean you want to save the progress of the Kangaroos path, you would have to have prompted that before running the program.

_Counselor

member

Activity: 110

Merit: 61

Quote from: NotATether on February 26, 2021, 12:09:47 AM

There's merging functionally built in to Kangaroo, use -wm file1 file2 destfile for multiple files or -wmdir dir destfile to merge an entire directory full of work files (that it can recognize).

This option merges only DPs and final file gets cleaned from kangaroos.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: NotATether on February 25, 2021, 11:33:33 PM

Hey guys, so apparently there's a discrepancy between the search length in the README and the actual search length.

The README says that there's a 125-but search limit, but this is apparently wrong and there's a 126-bit search limit according to the code for hashtable entries in Hashtable.h:

Quote from: https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/HashTable.h#L49-L56

Code:

// We store only 128 (+18) bit a the x value which give a probabilty a wrong collision after 2^73 entries

typedef struct {

  int128_t  x;    // Poisition of kangaroo (128bit LSB)
  int128_t  d;    // Travelled distance (b127=sign b126=kangaroo type, b125..b0 distance

} ENTRY;

While the class Int is 256 bits wide but the top half are going unused. Actually, the hash entry IF is shoved into the third int64 of kangaroo position (x)!

Anyhow, I'm working on extending the search interval to 256 bits (full disclosure: I'm being paid to do this) and I'll upload the code when it's done so you guys can check it out too. There's really no point in extending it longer than that because all other arithmetic is in 256 bits.

There is also apparently a constant in the code that changes the Int size from 256 to 512 bits (this does not change the interval size which is still locked to 126 bits), but who's going to use 512 bit public keys unless you're using some non bitcoin curve like secp512k1 [I forgot, is that really a curve? Tongue

]

Cheers all.

I think it was mentioned in passing in regards to the puzzle...i.e. can't go above #125.
It is one of the main reasons I decided not to use this version. Even though it is the fastest/best one to use. Jean Luc said it would be a slight overhaul to change it to 256 but no one seemed interested when I offered to work with him on it.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: _Counselor on February 26, 2021, 12:06:03 AM

Is there any tool to merge kangaroos from two files?

I have some files with a small number of kangaroos which has been ran long time on CPU, and want to continue working on them all together on another machine with GPU, is that possible?

There's merging functionally built in to Kangaroo, use -wm file1 file2 destfile for multiple files or -wmdir dir destfile to merge an entire directory full of work files (that it can recognize).

_Counselor

member

Activity: 110

Merit: 61

Is there any tool to merge kangaroos from two files?

I have some files with a small number of kangaroos which has been ran long time on CPU, and want to continue working on them all together on another machine with GPU, is that possible?

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Hey guys, so apparently there's a discrepancy between the search length in the README and the actual search length.

The README says that there's a 125-but search limit, but this is apparently wrong and there's a 126-bit search limit according to the code for hashtable entries in Hashtable.h:

Quote from: https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/HashTable.h#L49-L56

Code:

// We store only 128 (+18) bit a the x value which give a probabilty a wrong collision after 2^73 entries

typedef struct {

  int128_t  x;    // Poisition of kangaroo (128bit LSB)
  int128_t  d;    // Travelled distance (b127=sign b126=kangaroo type, b125..b0 distance

} ENTRY;

While the class Int is 256 bits wide but the top half are going unused. Actually, the hash entry IF is shoved into the third int64 of kangaroo position (x)!

Anyhow, I'm working on extending the search interval to 256 bits (full disclosure: I'm being paid to do this) and I'll upload the code when it's done so you guys can check it out too. There's really no point in extending it longer than that because all other arithmetic is in 256 bits.

There is also apparently a constant in the code that changes the Int size from 256 to 512 bits (this does not change the interval size which is still locked to 126 bits), but who's going to use 512 bit public keys unless you're using some non bitcoin curve like secp512k1 [I forgot, is that really a curve? Tongue

]

Cheers all.

Topic: Pollard's kangaroo ECDLP solver - page 71. (Read 58537 times)