Pollard's kangaroo ECDLP solver - page 72.

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: NotATether on March 05, 2021, 10:55:52 AM

Quote from: WanderingPhilospher on March 05, 2021, 08:52:50 AM

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

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: WanderingPhilospher on March 05, 2021, 08:52:50 AM

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

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: NotATether on March 05, 2021, 04:21:01 AM

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

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

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.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

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

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.

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?

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