Pollard's kangaroo ECDLP solver - page 72.

mamuu

member

Activity: 73

Merit: 19

Quote from: WanderingPhilospher on March 01, 2021, 03:58:19 PM

Quote from: mamuu on March 01, 2021, 02:37:24 PM

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

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: mamuu on March 01, 2021, 02:37:24 PM

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

member

Activity: 73

Merit: 19

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

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: mamuu on March 01, 2021, 01:55:12 PM

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

member

Activity: 73

Merit: 19

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://bitcointalksearch.org/topic/m.56416339

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.

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

Merit: 242

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

Merit: 242

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

Merit: 242

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

Merit: 1077

Honey badger just does not care

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

Merit: 242

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.

Topic: Pollard's kangaroo ECDLP solver - page 72. (Read 60189 times)