Topic: Pollard's kangaroo ECDLP solver - page 5. (Read 58537 times)

Dear @Baskentliia,

It may be because English is probably not your first language, but saying to Jean Luc "We expect from you" is pretty rude.
The "prize" for solving puzzle #130 is very high, so don't expect to be able to do it with someone else's tools/software.
If you want to solve one of the remaining puzzles, you have to team up with a lot of people (and share the prize money) or be smarter than everyone else, i.e. come up with a new method or code to do it much faster than is possible with the actual hardware and software.
In fact, showing how secure the bitcoin crypto is was the whole idea behind these puzzles.

And a 256 bit range is ridiculous at the moment, please do the maths and calculate how many resources you'll need to solve a 256 bit number! That's why the puzzles stop at 160 bit...

Sincerely and good luck puzzling!

Please update your program and upgrade to 256 bit range as soon as possible.
Others have updated your program but it wasn't successful enough. We expect from you

Here's my current work file for 130, i got here in about 3 days
i need 25.55 DP
is what i have wrong? since you said the program can't solve it?
Kangaroo v2.2
Loading: save.work
Version   : 0
DP bits   : 40
Start     : 200000000000000000000000000000000
Stop      : 3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Key       : 03633CBE3EC02B9401C5EFFA144C5B4D22F87940259634858FC7E59B1C09937852
Count     : 0 2^-inf
Time      : 00s
DP Size   : 2.1/4.7MB
DP Count  : 4480 2^12.129
HT Max    : 2 [@ 001ECF]
HT Min    : 0 [@ 000000]
HT Avg    : 0.02
HT SDev   : 0.13
Kangaroos : 0 2^-inf

I don't think so, unless someone proove me he has the needed power and is ready to beat the world record 

Are you going to modify the code to be able to search the 130 bit? There is a new NVIDIA GPU that was announced, the GB200 which is exponentially more powerful than the current gpus.

Yes but we don't have it, so brute force and 2^65 itérations for 50% of success, 2^64 for 25% etc...

If you have the public key of Puzzle 66, you can find the privat key in seconds. Why is that so ? What happens ? What does the program do ?

I checked on #125 with a RTX 4500 and a A100 (the H100 is not yet available).
The needed time evolve linearly with the number of board and you have to multiply by sqrt(32) for #130
So ~1 year to solve #130 with ~1000 RTX 4500 using this program with the required mods.

Kangaroo v2.2
Start:10000000000000000000000000000000
Stop :1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^124
Jump Avg distance: 2^62.04
Number of kangaroos: 2^20.81
Suggested DP: 38
Expected operations: 2^63.10
Expected RAM: 1387.8MB
DP size: 38 [0xfffffffffc000000]
GPU: GPU #0 NVIDIA RTX A4500 (56x0 cores) Grid(112x128) (147.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.81 kangaroos [9.9s]
[1514.20 MK/s][GPU 1514.20 MK/s][Count 2^34.77][Dead 0][22s (Avg 207.606y)][2.0/4.0MB]


Kangaroo v2.2
Start:10000000000000000000000000000000
Stop :1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^124
Jump Avg distance: 2^62.04
Number of kangaroos: 2^21.75
Suggested DP: 37
Expected operations: 2^63.10
Expected RAM: 2760.3MB
DP size: 37 [0xfffffffff8000000]
GPU: GPU #0 NVIDIA A100-PCIE-40GB (108x0 cores) Grid(216x128) (277.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^21.75 kangaroos [22.7s]
[3824.79 MK/s][GPU 3824.79 MK/s][Count 2^33.84][Dead 0][06s (Avg 82.0929y)][2.0/4.0MB]

---------

With a H100 (PCIe) (on #130)

Kangaroo v2.2
Start:200000000000000000000000000000000
Stop :3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^129
Jump Avg distance: 2^64.01
Number of kangaroos: 2^21.83
Suggested DP: 40
Expected operations: 2^65.62
Expected RAM: 1985.4MB
DP size: 40 [0xffffffffff000000]
GPU: GPU #0 NVIDIA H100 PCIe (114x0 cores) Grid(228x128) (292.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^21.83 kangaroos [23.3s]
[5113.99 MK/s][GPU 5113.99 MK/s][Count 2^34.26][Dead 0][06s (Avg 352.678y)][2.0/4.0MB]

You can find the cotation of the hypervisors we use for scientific calculation there (page 12 of my presentation):
https://indico.esrf.fr/event/93/contributions/559/

I had zero overflow during tests.

And for 130, I am using the average case scenario and numbers. No exabytes needed. And it’s obvious you don’t understand the difference between a kangaroo and a stored DP.

You do the math yourself, take a DP, we will say DP 32, and you tell me, in your expert opinion, how much storage space is needed, roughly, for solving 130. 

I would reference you to OPs GitHub to read on time/memory tradeoff but you’ve already stated you don’t agree with much of what he has said or programmed.

Anyway, let me know storage space required, avg run case, for 130, using DP32

What good does it do if you will most likely overflow the 128-bit after just a few jumps, no matter what start distance you begin with?

I never stated I'm solving 66 with pen and paper, only that 66 is a hashing rate contest that has nothing to do with ECDLP at all.
I believe you were the one thinking we only need something like 2* 2**33 kangaroos or whatever to solve #130 in something like 2**66 steps... when the reality is we need many exabytes of stored data to have a 50% chance for a collision, in that many steps you mentioned.

I tested a H100 SXM card and got 13,600 MKey/s, with a different Kangaroo program. I am curious what kind of speeds you will achieve.

I never mention those because they are extremely expensive to buy and expensive to rent on vast.

I'll try tomorow with a H100 (if free) just to see the performance.
At my job we have only gpu dedicated to scientific calculus which may be less adapted to integer calculus than a 4090.

In any case it will require a large number of boards and considerable amout of time to get the BTC 

I was able to solve a 128 bit key using an unmodded version, but I obviously knew where the key was and could place the kangaroos in optimal positions.

128-1 = 127, so really in a 127 bit range, because the program subs start range from key or start range is greater than 0.

As I stated, always do your own tests. Most don’t even know what the work files contain because they have never extracted them and looked under the hood.

However, JLP is basing time to solve off of older GPUs, more than likely the V100. Which when ran with this program, he’s probably right. A V100 only gets 1,600 MKey/s with this program. With 512 V100s, at that speed, it would take 2 years to solve. But fast forward from the last time he worked on this program and now you have 2 newer generation cards. The 4090 is a beast. With 512 of them and a modded/different version of Kangaroo, I calculate it would take right at 163 days to solve.

So I advise everyone to do their own DD and take what ktimes says, with a grain of salt. I believe he is the one who was going to solve #66 with pencil and paper. He’ll always spout this and that, and everyone but him is dumb, but hasn’t provided any insight into anything, other than his owned perceived genius.

You are the best person to mod it till 160 just in case.

Yes it seems Puzzle has gone beyond the continuous solvable limit. Perhaps some random jumper could catch the moving electron.

Hello OP,
I'm expressing my gratitude for stepping in to clear out this matter. Obviously, it should be a good lesson for absolutely anyone to always take with a big grain of salt what some users are trying to convince people of their "guaranteed" truth.

For everybody else - make your own judgments always in everything. Most of the claims done in these forums are complete bogus, with no actual underlying rationale to cover it up. Start by grabbing a statistics fast course, don't expect to miraculously reduce space-time algorithmic complexities, unless you change the fundamental hypothesis some way. Otherwise the Universe will just slap you in the face, since it's rules don't work according to our (very bad) intuition and perception.

After quick look at kangaroo code, looks like there is 3-bits of 128-bit value used for something. So, it actually really 125-bit max. I can be wrong and I think only JLP can answer 100%.
[/quote]

Hello,
Yes you are right. The GPU code should also be modified to return good distances.
Do not try to solve this puzzle, it will take years using a rendering farm !

lol…yall are killing me.

Stop asking for proof and/or videos.

Run some tests, extract the stored points and distances, and see for yourself.

If you do not want to do that, then use the version of Kangaroo that I have mentioned several times.

If you don’t want to do that; then mod the original or pay someone to mod the original.

After quick look at kangaroo code, looks like there is 3-bits of 128-bit value used for something. So, it actually really 125-bit max. I can be wrong and I think only JLP can answer 100%.

Can it work with 128 bit? Then can we divide the puzzle into 2 and run it?
Can we divide it into two parts as 20-2F and 30-3F and run it?
The owner of the program says that it can work with a range width of 125 bits.
You say that it will work at 128 bits and below. Do you have any proof of what?

It will work with 128 and below, 100%