Pollard's kangaroo ECDLP solver

[WanderingPhilospher]

Thanks. So the idea is that the tame herd is a series of numbers that are  increasing in a constant way and the wild herd is variables that are "randomly" moving forward...when a collision occurs, how does that determine the public key?

This is not exact, but will give you an example. The tame herd starts at random points, let's say at the middle of the range, then they make jumps. When they land on a dp, it's recorded. The wild herd starts at random points and they make jumps, but they normally start in a range behind the tame herd. If they land on a dp, it's recorded.

We have to solve P = k.G, P is the public key, we know that k lies in the range [k1,k2], G is the SecpK1 generator point.
(Tame,Wild) = Collision
k = k1 + Tame.dist - Wild.dist

[1715587092]

1715587092

[1715587092]

1715587092

[1715587092]

1715587092

[1715587092]

1715587092

[iamfreshfish]

Ok, still trying to wrap my head around the concept But getting there. Hats to those of you here who understand all this

So I got it to run.
1080ti on Windows
Bat file >> Kangaroo.exe -t 0 -gpu -gpuId 0 -ws -w save.work -wi 30 input.txt

Starts off at 200Mkeys/s and then continuously drops

Also why does this algo seem to only work for bit ranges that are multiples of 5?

[WanderingPhilospher]

Ok, still trying to wrap my head around the concept But getting there. Hats to those of you here who understand all this

So I got it to run.
1080ti on Windows
Bat file >> Kangaroo.exe -t 0 -gpu -gpuId 0 -ws -w save.work -wi 30 input.txt

Starts off at 200Mkeys/s and then continuously drops

Also why does this algo seem to only work for bit ranges that are multiples of 5?

Glad you finally got it to work.

Now that you finally got rid of the server command, you can play around with the grid size numbers for your gpu, up to you.

The MKey/s drop but shouldn't be that much. I have had 1070s that maintain above 200 MKey/s.

I do not know what you mean by multiples of 5...if you are referring to the puzzle, that's because every 5th address in the puzzle has the pubkeys exposed. This program works by only knowing the pubkey. But the program will work for any range, any "multiple".

[Marynarz]

Hi all

Yes From time to time it fails and go out the range. The number of dead kangaroo (collision in same herd) increase.
The idea of replaying walk is good, I do like this in my BTCCollider.

Here is an output on 30 trials.
The final private key is not reconstructed here, you need to add (mod n) start range + N/2

Code:

Kangaroo v1.3
Start:62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004A0000000000
Stop :62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004AFFFFFFFFFF
Keys :1000
Number of CPU thread: 2
Range width: 2^40
Jump Avg distance: 2^20.00
Number of kangaroos: 2^11.00
Suggested DP: 8
Expected operations: 2^21.15
Expected RAM: 6.5MB
DP size: 5 [0xF800000000000000]
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos

Key# 0 S3Pub:  0x03C88A1817454E1B49AEEF4D22DB60CD1FFF0513DECC2AFC52219C28C99CFE36A1
       Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3E9F06D632
[  0] 2^21.709 Dead:4 Avg:2^21.709 (2^21.148)

Code:

Kangaroo.exe -t 0 -d 11 -m 3.0 -gpu -g 80,256,80,256 -gpuId 0,1 -o found.txt in.txt
Kangaroo v2.1
Start:62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004A0000000000
Stop :62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004AFFFFFFFFFF
Keys :293566
Number of CPU thread: 0
Range width: 2^40
Jump Avg distance: 2^19.97
Number of kangaroos: 2^22.32
Suggested DP: 0
Expected operations: 2^25.49
Expected RAM: 12.9MB
DP size: 11 [0xFFE0000000000000]
GPU: GPU #0 GeForce GTX 1060 6GB (10x128 cores) Grid(80x256) (207.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #1 GeForce GTX 1060 6GB (10x128 cores) Grid(80x256) (207.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
SolveKeyGPU Thread GPU#1: 2^21.32 kangaroos [12.9s]
SolveKeyGPU Thread GPU#0: 2^21.32 kangaroos [12.9s]
[185.39 MK/s][GPU 185.39 MK/s][Count 2^28.49][Dead 204][02s (Avg 00s)][6.4/21.9M
B]
Key# 0 [XX]Pub:  0x03C88A1817454E1B49AEEF4D22DB60CD1FFF0513DECC2AFC52219C28C99CF
E36A1
       Aborted !

Jean_Luc, would you please explain to me why Kangaroo v2.1 has a problem finding this key?

[Wouimbly]

Hi! Just wonder what is the impact of searching multiple pubkey at once ?
Does the key are search one by one or all at once ?

[iamfreshfish]

Ok, still trying to wrap my head around the concept But getting there. Hats to those of you here who understand all this

So I got it to run.
1080ti on Windows
Bat file >> Kangaroo.exe -t 0 -gpu -gpuId 0 -ws -w save.work -wi 30 input.txt

Starts off at 200Mkeys/s and then continuously drops

Also why does this algo seem to only work for bit ranges that are multiples of 5?

Glad you finally got it to work.

Now that you finally got rid of the server command, you can play around with the grid size numbers for your gpu, up to you.

The MKey/s drop but shouldn't be that much. I have had 1070s that maintain above 200 MKey/s.

I do not know what you mean by multiples of 5...if you are referring to the puzzle, that's because every 5th address in the puzzle has the pubkeys exposed. This program works by only knowing the pubkey. But the program will work for any range, any "multiple".

Yeah it was weird but I was running out of space...was gobbling up RAM and I'm assuming pagefile as well but when I moved the app to a separate drive it is now running at 500Mkeys/s

As for the "every 5th" I now understand that this algo requires the public key and the other BTC puzzle programs just brute force all the private key options in a range

[WanderingPhilospher]

Hi! Just wonder what is the impact of searching multiple pubkey at once ?
Does the key are search one by one or all at once ?

If you have more than one pubkey in your input file, the program searches one by one. If you don't use the -m option, the program could search for the first pubkey forever.

[PawGo]

Hello,

Regarding https://bitcointalk.org/index.php?topic=5265788.0, would it be possible to modify kangaroos to work on sparse range?
I would like to launch search on range [a0, ..., ai, ..., aN], where ai = a0+(i*s), with stride 's'.
As I understand now program 'scales down' range to 0->aN', with a corresponding changes on pubkey, right?

Regards,

[j2002ba2]

Hello,

Regarding https://bitcointalk.org/index.php?topic=5265788.0, would it be possible to modify kangaroos to work on sparse range?
I would like to launch search on range [a0, ..., ai, ..., aN], where ai = a0+(i*s), with stride 's'.
As I understand now program 'scales down' range to 0->aN', with a corresponding changes on pubkey, right?

Regards,

For continuous range you could divide a_i by 's': a_i/s = a₀/s + i.

[paniker]

Hi all,

So no one knows a pubkey to 64?

[bigvito19]

Hi all,

So no one knows a pubkey to 64?

If pubkey to 64 was exposed it would have been solved already.

[vimp666]

Hi all,

So no one knows a pubkey to 64?

Address 64 has no outgoing transactions.Therefore, the public key is unknown.

[PawGo]

[EDITED]

I must rethink it ;-)

[paniker]

Hi all,

So no one knows a pubkey to 64?

Address 64 has no outgoing transactions.Therefore, the public key is unknown.

so everybody seraching higher known addresses ?

[COBRAS]

@Jean_Luc, implement please Pollard's RHO code to bitcoin

Maybe you can make a Pollard RHO like Pollard Kangaro without memory cost



This is a link to sources:



Code Sources ready to go - CUDA demonstration using Pollard's Rho  - https://github.com/dghost/factor-cuda

https://github.com/dghost

BSGS and Pollard's rho both cost O(n−−√) operations where n is the order of the group, typically a >250-bit integer as in edwards25519, secp256k1, nistp256, etc. However, BSGS also has O(n−−√) memory cost, so the area*time cost—which is a proxy for euro or joule cost—is O(n) even if we unrealistically assume O(1) random access to memory. In contrast, Pollard's rho costs O(n−−√) time on a machine of constant space and thus O(n−−√) area*time. Pollard's rho can also be naturally parallelized to trade space for time without increasing the overall cost. There are also some small optimizations that apply to Pollard's rho for elliptic curves, but they only change the constant factors a little; it remains O(n−−√)
.
If you knew the secret scalar were in a restricted range [a,b]
, you could use Pollard's kangaroo, which costs O(b−a−−−−√) time on a machine of constant size. The kangaroo method too can be parallelized without increasing overall cost. If, say, b−a≈2100 for your secp256k1 target, then this would be within reach for you while none of the above methods would be feasible. But it would be surprising for anyone to choose a scalar restricted enough that Pollard's kangaroo finds it substantially faster than rho.

[gmaxwell]

I haven't seen this paper discussed here: https://cr.yp.to/dlog/cuberoot-20120919.pdf

There are a number of good points in it but particularly the point of generating *better* distinguished points by preferentially keeping ones that have longer walk lengths is interesting.

[Jean_Luc]

I won't implement a rho method for secp256k1. It is not feasible to reach a solution using this method.

I haven't seen this paper discussed here: https://cr.yp.to/dlog/cuberoot-20120919.pdf

There are a number of good points in it but particularly the point of generating *better* distinguished points by preferentially keeping ones that have longer walk lengths is interesting.

Thanks for the reading. I didn't read it yet.
I suppose that when you speak of walk length, you mean the total number of jumps of the walk, not the total traveled distance.
The problem of storing length of walk is that on GPU access to global memory is very slow. I will see if I manage to improve things.

[gmaxwell]

Thanks for the reading. I didn't read it yet.
I suppose that when you speak of walk length, you mean the total number of jumps of the walk, not the total traveled distance.
The problem of storing length of walk is that on GPU access to global memory is very slow. I will see if I manage to improve things.

Right.

This is specific to disk stored distinguished points stored for tame entries used to generically accelerate many different executions.

The idea is that sometimes distinguished points are closely spaced on a walk, and sometimes far apart. Given a constant amount of storage you would prefer to store widely spaced distinguished points over closely spaced ones.  You can't know the actual spacing, since you don't know what the walk looked like before your start-- but you could track how far you walked and store that.

[vimp666]

Hi all,

So no one knows a pubkey to 64?

Address 64 has no outgoing transactions.Therefore, the public key is unknown.

so everybody seraching higher known addresses ?

Pollard's method can only search for those addresses where the public key is known. So the answer to your question is Yes.

[bigvito19]

So this is what you all really wanted to use Kangaroo vs RHO