Pollard's kangaroo ECDLP solver

[NotATether]

that means that about 1/3 of the all possible values of Y are valid Y coordinates (are coordinates of a point/pub key) and about 1/2 of all the possible values of X are valid X coordinates.

Maybe we can use that as an optimization and go through all the X values, and check that (X² + 7) mod p gives a cubed number which would imply a valid Y. This would eliminate half of the search space. Similarly we can go through all the Y values and calculate Y³ mod p is a square number which implies a valid X and eliminate 2/3s of the search space.

Since the invalid points derived for each X and Y don't overlap, we have already removed 1/2 * 2/3 = 1/3 of the total possible search space like that.

[arulbero]

Since the invalid points derived for each X and Y don't overlap, we have already removed 1/2 * 2/3 = 1/3 of the total possible search space like that.

No, because all the tame and the wild move directly (jump) between the points (with valid coordinates); the points are about 2^256:

(1/2 * 2^256 X coordinates) * (2 valid Y coordinates) = 2^256 points.

[bigvito19]

that means that about 1/3 of the all possible values of Y are valid Y coordinates (are coordinates of a point/pub key) and about 1/2 of all the possible values of X are valid X coordinates.

Maybe we can use that as an optimization and go through all the X values, and check that (X² + 7) mod p gives a cubed number which would imply a valid Y. This would eliminate half of the search space. Similarly we can go through all the Y values and calculate Y³ mod p is a square number which implies a valid X and eliminate 2/3s of the search space.

Since the invalid points derived for each X and Y don't overlap, we have already removed 1/2 * 2/3 = 1/3 of the total possible search space like that.

256/3  128/3  64/3  does sound better than  256/2  128/2  64/2

[WanderingPhilospher]

For the really smart people out there...I had read somewhere that a pubkey may have 2 X coordinates, maybe 3 X coordinates, can't really remember.

Each pubkey has only 1 X coordinate and 1 Y coordinate. And only 1 private key.

There are 2 pubkeys that share the same X coordinate (for each valid X coordinate) but they have different Y coordinates:

if A = (X,Y) then  B = -A = (X, p-Y)

(p =  2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1)


There are 3 pubkeys that share the same Y coordinate (for each valid Y coordinate) but they have different X coordinates:

if A = (X,Y) then B = k*A = (beta*X, Y) and C = k*k*A = (beta*beta*X, Y)

(k = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72  
and  beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee)

There are about 2^256 points on secp256k1, (to be precise n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141) and Fp (the field of the coordinates X e Y) has about the same size;

that means that about 1/3 of the all possible values of Y are valid Y coordinates (are coordinates of a point/pub key) and about 1/2 of all the possible values of X are valid X coordinates.

That's all.

So within the Kangaroo program, with a Tame file:

Code:

4308F55406236F06FBBB5A328499E9F2787C64AC7779FD387BFBD803C0000000 00000000000000000000000000000000004448E8FD4C2B40AAF6E5C2D6A8A1E5

Are neither one of those the X coord? I read somewhere in this thread, that the above 4308F55406236F06FBBB5A328499E9F2787C64AC7779FD387BFBD803C0000000 was an X coord (034308f55406236f06fbbb5a328499e9f2787c64ac7779fd387bfbd803c0000000). Is that not true?

Because what I was saying, is that I have found the same exact private key, with different tame and wild coords/distances.

Meaning, if I was searching for private key 0x17A57BE2, using the Kangaroo program, I solved with different tame and wild files, example:

first solve tame:

Code:

4308F55406236F06FBBB5A328499E9F2787C64AC7779FD387BFBD803C0000000 00000000000000000000000000000000004448E8FD4C2B40AAF6E5C2D6A8A1E5[

first solve wild:

Code:

4308F55406236F06FBBB5A328499E9F2787C64AC7779FD387BFBD803C0000000 00000000000000000000000000000000000008E8FD4C2B40AAF6E5C2D6A8A1E5[

second solve tame:

Code:

DDD6055558606CB730B603F4ECF20B497A709FECF23671612A742FFBC0000000 000000000000000000000000000000000058D5A2BF77F6FA6D631B606B604BCE

second solve wild:

Code:

DDD6055558606CB730B603F4ECF20B497A709FECF23671612A742FFBC0000000 0000000000000000000000000000000000000002BF77F6FA6D631B606B604BCE

those are examples, not the actual wild and tame files I solved the one private key with.

[WanderingPhilospher]

Here was the post I was talking about:

https://bitcointalk.org/index.php?topic=5244940.msg54564299#msg54564299

Anywho, like I said, I did not know that you could search for the same private key, in the same range, using the same distinguished point ( example = -d 29) and solve the exact same private key with two entirely different tame and wild points/coords and distances.

I also did not know that you could solve a 3 digit private key, example 0x1A2. in a keyspace search range such as 1A012BE379AC91023ADF:1A012BFFFFFFFFFFFFFF

And before anyone says that the program shifts down to zero, I wasn't using JLPs kangaroo program which shifts down, and the actual tame wild points/coords were obviously the same and the distances were like tame 1A012BE379AC91023ADF and wild 1A012BE3789A91023ADF

[bigvito19]

Can someone explain the ht max, ht min, ht avg, ht sdev means. Is that like how many times a DP has occurred in the table?

[NotATether]

Can someone explain the ht max, ht min, ht avg, ht sdev means. Is that like how many times a DP has occurred in the table?

HT stands for Hash Table, it is used to store the kangaroo positions and distances. The statistics HT max, min, avg, sdev are just maximum, minimum, average and standard deviations of the number of kangaroos in each DP. The DP (1st argument pos) is slightly transformed (1st argument x passed to Convert() to get h) into keys (h in HashTable::Add(h,e)) in the hash table.

[dextronomous]

DP: 626,941,151 TP: 14,389,459,189,655,514

how much percentage of 120th puzzle should these dp and tp have reached, anyone?
thanks

[$upermoney]

Anyone have luck installing Kangaroo on vast.ai platform? The Linux CUDA installation seems somewhat complex is there a streamlined process of exactly what to install?

[MisterCooper]

Today I tested Kangaroo 2.2 on the Ubuntu. Everything works great! Thanks a lot Jean_Luc!
Most of the participants in this discussion are programmers, and I have a question for you. How do you loop the MultiPubKey?
I would really like to search the list using different public keys in one specific range.

[bigvito19]

Today I tested Kangaroo 2.2 on the Ubuntu. Everything works great! Thanks a lot Jean_Luc!
Most of the participants in this discussion are programmers, and I have a question for you. How do you loop the MultiPubKey?
I would really like to search the list using different public keys in one specific range.

For now it only search for 1 key at a time. When the first key is found then it goes to the next one.

[WanderingPhilospher]

Today I tested Kangaroo 2.2 on the Ubuntu. Everything works great! Thanks a lot Jean_Luc!
Most of the participants in this discussion are programmers, and I have a question for you. How do you loop the MultiPubKey?
I would really like to search the list using different public keys in one specific range.

you can use the:

-m maxStep: number of operations before give up the search (maxStep*expected operation)

and the program will move to next pubkey if not found within -m operations

[MisterCooper]

Today I tested Kangaroo 2.2 on the Ubuntu. Everything works great! Thanks a lot Jean_Luc!
Most of the participants in this discussion are programmers, and I have a question for you. How do you loop the MultiPubKey?
I would really like to search the list using different public keys in one specific range.

you can use the:

-m maxStep: number of operations before give up the search (maxStep*expected operation)

and the program will move to next pubkey if not found within -m operations

@WanderingPhilospher thanks for the advice. I am using the command:

Code:

./kangaroo -ws -w save.work -wi 30 -o result.txt in.txt

How to correctly write in (-m maxStep) so that every 15 minutes there is a transition to the next new public key?

[WanderingPhilospher]

Today I tested Kangaroo 2.2 on the Ubuntu. Everything works great! Thanks a lot Jean_Luc!
Most of the participants in this discussion are programmers, and I have a question for you. How do you loop the MultiPubKey?
I would really like to search the list using different public keys in one specific range.

you can use the:

-m maxStep: number of operations before give up the search (maxStep*expected operation)

and the program will move to next pubkey if not found within -m operations

@WanderingPhilospher thanks for the advice. I am using the command:

Code:

./kangaroo -ws -w save.work -wi 30 -o result.txt in.txt

How to correctly write in (-m maxStep) so that every 15 minutes there is a transition to the next new public key?

the max step is based off of group operations so you'd have to watch when your program normally gets to where you want to end (watching the time) and then enter it, if you want it to end after a length of time. But let's say the estimated operations is 2^30, you would use the max step to end the program's search after 2^30.5, or 2^31, or 2^100, or whatever you want.

[MisterCooper]

Today I tested Kangaroo 2.2 on the Ubuntu. Everything works great! Thanks a lot Jean_Luc!
Most of the participants in this discussion are programmers, and I have a question for you. How do you loop the MultiPubKey?
I would really like to search the list using different public keys in one specific range.

you can use the:

-m maxStep: number of operations before give up the search (maxStep*expected operation)

and the program will move to next pubkey if not found within -m operations

@WanderingPhilospher thanks for the advice. I am using the command:

Code:

./kangaroo -ws -w save.work -wi 30 -o result.txt in.txt

How to correctly write in (-m maxStep) so that every 15 minutes there is a transition to the next new public key?

the max step is based off of group operations so you'd have to watch when your program normally gets to where you want to end (watching the time) and then enter it, if you want it to end after a length of time. But let's say the estimated operations is 2^30, you would use the max step to end the program's search after 2^30.5, or 2^31, or 2^100, or whatever you want.

Is it possible to automate this in UBUNTU so as not to manually enter the add-on in the terminal? 15 minutes is enough for me to search in each public key in the list.

[WanderingPhilospher]

Today I tested Kangaroo 2.2 on the Ubuntu. Everything works great! Thanks a lot Jean_Luc!
Most of the participants in this discussion are programmers, and I have a question for you. How do you loop the MultiPubKey?
I would really like to search the list using different public keys in one specific range.

you can use the:

-m maxStep: number of operations before give up the search (maxStep*expected operation)

and the program will move to next pubkey if not found within -m operations

@WanderingPhilospher thanks for the advice. I am using the command:

Code:

./kangaroo -ws -w save.work -wi 30 -o result.txt in.txt

How to correctly write in (-m maxStep) so that every 15 minutes there is a transition to the next new public key?

the max step is based off of group operations so you'd have to watch when your program normally gets to where you want to end (watching the time) and then enter it, if you want it to end after a length of time. But let's say the estimated operations is 2^30, you would use the max step to end the program's search after 2^30.5, or 2^31, or 2^100, or whatever you want.

Is it possible to automate this in UBUNTU so as not to manually enter the add-on in the terminal? 15 minutes is enough for me to search in each public key in the list.

If you use the save feature, I'm not sure you can run another pubkey; I think it will throw an erro "Multiple pubkeys not supported..."
I am not an UBUNTU expert, I mainly use Windows. For what you are wanting to do, in Windows, I would create a batch file that would timeout after 15 minutes for each pubkey and set the save file to a different name for each pubkey, then no issues with multiple pubkey error.

[MisterCooper]

Today I tested Kangaroo 2.2 on the Ubuntu. Everything works great! Thanks a lot Jean_Luc!
Most of the participants in this discussion are programmers, and I have a question for you. How do you loop the MultiPubKey?
I would really like to search the list using different public keys in one specific range.

you can use the:

-m maxStep: number of operations before give up the search (maxStep*expected operation)

and the program will move to next pubkey if not found within -m operations

@WanderingPhilospher thanks for the advice. I am using the command:

Code:

./kangaroo -ws -w save.work -wi 30 -o result.txt in.txt

How to correctly write in (-m maxStep) so that every 15 minutes there is a transition to the next new public key?

the max step is based off of group operations so you'd have to watch when your program normally gets to where you want to end (watching the time) and then enter it, if you want it to end after a length of time. But let's say the estimated operations is 2^30, you would use the max step to end the program's search after 2^30.5, or 2^31, or 2^100, or whatever you want.

Is it possible to automate this in UBUNTU so as not to manually enter the add-on in the terminal? 15 minutes is enough for me to search in each public key in the list.

If you use the save feature, I'm not sure you can run another pubkey; I think it will throw an erro "Multiple pubkeys not supported..."
I am not an UBUNTU expert, I mainly use Windows. For what you are wanting to do, in Windows, I would create a batch file that would timeout after 15 minutes for each pubkey and set the save file to a different name for each pubkey, then no issues with multiple pubkey error.

@WanderingPhilospher I am using one file: "save.work" to search for privkeys for different public keys in one specific range.
Does this decrease the speed with one file: "save.work"? Or do me need to change the file: "save.work" that is, register a separate file for each public key?

[NotATether]

Anyone have luck installing Kangaroo on vast.ai platform? The Linux CUDA installation seems somewhat complex is there a streamlined process of exactly what to install?

I have installed Bitcrack for someone on Vast.ai so that's close enough.

Use the default image that Vast gives you for CUDA. They bundle CUDA Toolkit 10.0 but without nvcc. You need to install cuda-nvcc-10-0 and cuda-cudart-dev-10-0 and build-essential. Don't try to install another toolkit version because the installer doesn't play well with Vast servers and you'll have to destroy and create another server again.

Don't lease any RTX 30 series cards because those need CUDA toolkit 11.0 and as I already mentioned it's a PITA to install. RTX 20 series is OK.

@WanderingPhilospher I am using one file: "save.work" to search for privkeys for different public keys in one specific range.
Does this decrease the speed with one file: "save.work"? Or do me need to change the file: "save.work" that is, register a separate file for each public key?

My gut feeling says that with the amount of disk I/O involved in writing files, it's faster to use one work file for saving. This only makes a difference if Kangaroo happens to write so many work files at once though, I believe it only writes one so it doesn't make a difference whether you use the same name or a different name.

[WanderingPhilospher]

Today I tested Kangaroo 2.2 on the Ubuntu. Everything works great! Thanks a lot Jean_Luc!
Most of the participants in this discussion are programmers, and I have a question for you. How do you loop the MultiPubKey?
I would really like to search the list using different public keys in one specific range.

you can use the:

-m maxStep: number of operations before give up the search (maxStep*expected operation)

and the program will move to next pubkey if not found within -m operations

@WanderingPhilospher thanks for the advice. I am using the command:

Code:

./kangaroo -ws -w save.work -wi 30 -o result.txt in.txt

How to correctly write in (-m maxStep) so that every 15 minutes there is a transition to the next new public key?

the max step is based off of group operations so you'd have to watch when your program normally gets to where you want to end (watching the time) and then enter it, if you want it to end after a length of time. But let's say the estimated operations is 2^30, you would use the max step to end the program's search after 2^30.5, or 2^31, or 2^100, or whatever you want.

Is it possible to automate this in UBUNTU so as not to manually enter the add-on in the terminal? 15 minutes is enough for me to search in each public key in the list.

If you use the save feature, I'm not sure you can run another pubkey; I think it will throw an erro "Multiple pubkeys not supported..."
I am not an UBUNTU expert, I mainly use Windows. For what you are wanting to do, in Windows, I would create a batch file that would timeout after 15 minutes for each pubkey and set the save file to a different name for each pubkey, then no issues with multiple pubkey error.

@WanderingPhilospher I am using one file: "save.work" to search for privkeys for different public keys in one specific range.
Does this decrease the speed with one file: "save.work"? Or do me need to change the file: "save.work" that is, register a separate file for each public key?

Ok, I ran a quick test to make sure. If you search for multiple pubkeys listed in a input file, once the kangaroo finds or starts searching for the next pubkey, it overwrites the save.work file.

The speed is not effected, it will just overwrite previous data each time it searches for new/next pubkey. Search for pubkeys in a small range and you can see what I mean.

[$upermoney]

Anyone have luck installing Kangaroo on vast.ai platform? The Linux CUDA installation seems somewhat complex is there a streamlined process of exactly what to install?

I have installed Bitcrack for someone on Vast.ai so that's close enough.

Use the default image that Vast gives you for CUDA. They bundle CUDA Toolkit 10.0 but without nvcc. You need to install cuda-nvcc-10-0 and cuda-cudart-dev-10-0 and build-essential. Don't try to install another toolkit version because the installer doesn't play well with Vast servers and you'll have to destroy and create another server again.

Don't lease any RTX 30 series cards because those need CUDA toolkit 11.0 and as I already mentioned it's a PITA to install. RTX 20 series is OK.

Thanks a ton!! Working great now.