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

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


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.

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

so everybody seraching higher known addresses ?

[EDITED]

I must rethink it ;-)

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

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

Hi all,

So no one knows a pubkey to 64?

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

Hello,

Regarding https://bitcointalksearch.org/topic/solving-wif-in-a-hybrid-mode-5265788, 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,

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.

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

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 ?

Hi all





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

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

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?

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.

Looks like you are only running a server mode.  Show me your current config/batch file. Run the example I showed you and don't run as a server. Basically, when you are running server mode, it's just that, a server. It is waiting for a client to connect to it. With one gpu, you do not need to run as server.

 
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?

Also, I did get the prog to run but this is what I get:

This output makes no sense to me as its unclear as to how well my GPU is performing. What is "dead" and why am I only using 12MB of expected RAM when I have 11GB?

no, I run on Windows as well. Just run the default settings. The program will auto detect your GPUs grid size and will multiply it by 2. So if your grid size is 20x100 the program will auto set it at 40x200.

As far as what's happening
Using the distinguished point method...if a wild kangaroo lands on a dp that a tame has already landed on, from that point, the wild will follow same path as tame and yes, the private key will be solved.

All of the setting options are described here:

https://github.com/JeanLucPons/Kangaroo (there are many) but the basic settings could/would be something like:

Kangaroo.exe -t 0 -gpu -gpuId 0 -i inputfile.txt -o outputfile.txt

that's basically saying -t 0 = no cpu threads, -gpu = use gpu, -gpuId 0 = use GPU as 0 index (if you have more you can use -gpuId 0,1,2,3,etc), -i = input file that contains the range you want to search and the pubkey you are searching for, -o = output file that pubkey and private key will be written to.