Pollard's kangaroo ECDLP solver

[fxsniper]

Google cloud gave me €200 free credit and 1 GPU to try, I'm only in 1st year of computer science though so not a researcher or anything

Thank you very much for great information

https://cloud.google.com/compute/gpus-pricing

How much you google cloud show cost, expensive?

[NotATether]

Google cloud gave me €200 free credit and 1 GPU to try, I'm only in 1st year of computer science though so not a researcher or anything

Thank you very much for great information

https://cloud.google.com/compute/gpus-pricing

How much you google cloud show cost, expensive?

I'm an AWS groupie but you can get your bills from your billing statement in GCP's console, no?

The table linked on this page shows costs per hour and month, but you can get away with ridiculously low  costs if you only run the GPUs for a few hours. For instance I am trying to get an NVIDIA T4 running Linux at $0.75 an hour.

[fxsniper]

I'm an AWS groupie but you can get your bills from your billing statement in GCP's console, no?

The table linked on this page shows costs per hour and month, but you can get away with ridiculously low  costs if you only run the GPUs for a few hours. For instance I am trying to get an NVIDIA T4 running Linux at $0.75 an hour.

Thanks,

AWS have v100 same GCP
https://docs.aws.amazon.com/dlami/latest/devguide/gpu.html
https://aws.amazon.com/blogs/aws/new-amazon-ec2-instances-with-up-to-8-nvidia-tesla-v100-gpus-p3/

Can free trial credit cover to using testing?

[NotATether]

AWS have v100 same GCP
https://docs.aws.amazon.com/dlami/latest/devguide/gpu.html
https://aws.amazon.com/blogs/aws/new-amazon-ec2-instances-with-up-to-8-nvidia-tesla-v100-gpus-p3/

Can free trial credit cover to using testing?

Unlike Google Cloud, AWS doesn't give you free credit - their trial makes some products free and others not free. The GPUs fall into the not-free category unfortunately.

[fxsniper]

reference script python
both
http://bitchain.pl/100btc/pollard_kangaroo.txt
and
https://github.com/Telariust/pollard-kangaroo
pollard-kangaroo-multi.py

they are work same kangaroo 2.2 right?
https[Suspicious link removed] on windows easy setup with file in.txt
(Kangaroo.exe work very well and better with GPU option)

my question for setup python script pollard-kangaroo-multi.py
Done pubkey list on python they are useful or use on calculate or not?
Can I setup  pubkey list on python script just one pubkey?

if pubkey list effect with calculate I will try to put all pubkey found already.


I try to use pollard-kangaroo-multi.py
if use python script work well, I would like to modify to sent email to me and message to know when found privatekey.

I try to use Kangaroo.exe -gpu (use GPU) and pollard-kangaroo-multi.py (use CPU) on  pc same time.

[NotATether]

reference script python
both
http://bitchain.pl/100btc/pollard_kangaroo.txt
and
https://github.com/Telariust/pollard-kangaroo
pollard-kangaroo-multi.py

I have to admit, that was a good attempt of them to port Kangaroo to Python. Though it uses xrange so it will not work on newer Python 3.

my question for setup python script pollard-kangaroo-multi.py
Done pubkey list on python they are useful or use on calculate or not?
Can I setup  pubkey list on python script just one pubkey?

if pubkey list effect with calculate I will try to put all pubkey found already.


I try to use pollard-kangaroo-multi.py
if use python script work well, I would like to modify to sent email to me and message to know when found privatekey.

It looks like it can only handle one public key at a time: [usage] %s [bits] [pubkey].

For email sending you can use the built-in smtplib module.

I try to use Kangaroo.exe -gpu (use GPU) and pollard-kangaroo-multi.py (use CPU) on  pc same time.

It has a GPU switch? I checked it and all the kangaroos were spawned as different CPU processes using message queues to communicate with each other. Not as fast as a native implementation that uses threads and shared memory though.

[fxsniper]

It looks like it can only handle one public key at a time: [usage] %s [bits] [pubkey].

For email sending you can use the built-in smtplib module.
 

Thanks NotATether

I try already, it can use only one public key
and other public key may be not help to any calculate.

[NotATether]

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:

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

Cheers all.

[_Counselor]

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]

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

[WanderingPhilospher]

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:

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

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.

[_Counselor]

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]

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]

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.

[fxsniper]

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.

[itod]

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

[NotATether]

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?

[WanderingPhilospher]

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?

[nioctib.co]

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? 

[nioctib.co]

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.