Pollard's kangaroo ECDLP solver

[qq569160818]

I probably miss something here, but please explain why do you guys use Kangaroo while there is another tool Keyhunt, which BSGS option is very very fast. With above average hardware, you can get around 10 exa keys per second. That is 10,000,000,000,000,000,000 keys per second.  I have never seen such numbers with Kangaroo.

I have been testing keyhunt and the conclusion is that its speed is very fast within a small range. For example, with a 45 bit interval, 8GB of memory is much faster than 1060 speed. However, once it reaches a high level, the efficiency of keyhunt is relatively low. Currently, I am testing with 128GB of memory, and the speed has reached 2Ekey/s. However, it is obvious that these speeds are negligible in such a huge space, so I prefer kangaroo high search. I am still testing more kangaroo conclusions. Thank you and greetings

[Baskentliia]

I probably miss something here, but please explain why do you guys use Kangaroo while there is another tool Keyhunt, which BSGS option is very very fast. With above average hardware, you can get around 10 exa keys per second. That is 10,000,000,000,000,000,000 keys per second.  I have never seen such numbers with Kangaroo.

I have been testing keyhunt and the conclusion is that its speed is very fast within a small range. For example, with a 45 bit interval, 8GB of memory is much faster than 1060 speed. However, once it reaches a high level, the efficiency of keyhunt is relatively low. Currently, I am testing with 128GB of memory, and the speed has reached 2Ekey/s. However, it is obvious that these speeds are negligible in such a huge space, so I prefer kangaroo high search. I am still testing more kangaroo conclusions. Thank you and greetings

Well, sir, if our luck is high, is there a possibility that we can find it with a bad graphics card by using the Kangaroo program?


Is JLP's Kangaroo program used for puzzle 130, which is original and published on github? Yes or no ?

Some said you can use it because the range width is 125 bits. Some have said that the original version of JLP has 130 puzzles and you cannot use it for more comprehensive puzzles.

Which one is right ?


What I'm talking about is the 130 bit range width, that is, if there is more than a 125 bit gap between the start and end, does the program work?

Mod note: consecutive posts merged

[3dmlib]

It will be nice to know from this program developer if kangaroo can work with 128-bit range?
Or it absolute maximum 125-bit as stated in the readme?
So, splitting in half #130 puzzle will help? It will be exactly two 128-bit ranges then.
Thanks.

[Baskentliia]

It will be nice to know from this program developer if kangaroo can work with 128-bit range?
Or it absolute maximum 125-bit as stated in the readme?
So, splitting in half #130 puzzle will help? It will be exactly two 128-bit ranges then.
Thanks.

I'm waiting for the answer to this question, but no one can say anything definitive. It is necessary to find the person who made this program.
Does this program work with more than 125 BIT RANGE?

[WanderingPhilospher]

It will be nice to know from this program developer if kangaroo can work with 128-bit range?
Or it absolute maximum 125-bit as stated in the readme?
So, splitting in half #130 puzzle will help? It will be exactly two 128-bit ranges then.
Thanks.

I'm waiting for the answer to this question, but no one can say anything definitive. It is necessary to find the person who made this program.
Does this program work with more than 125 BIT RANGE?

It has been answered multiple times, please read.

Again, on JLPs github (the person who built this program)

#130
Expected time: several years on 256 Tesla V100 (Not possible with this program without modification)

[qq569160818]

I probably miss something here, but please explain why do you guys use Kangaroo while there is another tool Keyhunt, which BSGS option is very very fast. With above average hardware, you can get around 10 exa keys per second. That is 10,000,000,000,000,000,000 keys per second.  I have never seen such numbers with Kangaroo.

I have been testing keyhunt and the conclusion is that its speed is very fast within a small range. For example, with a 45 bit interval, 8GB of memory is much faster than 1060 speed. However, once it reaches a high level, the efficiency of keyhunt is relatively low. Currently, I am testing with 128GB of memory, and the speed has reached 2Ekey/s. However, it is obvious that these speeds are negligible in such a huge space, so I prefer kangaroo high search. I am still testing more kangaroo conclusions. Thank you and greetings

Well, sir, if our luck is high, is there a possibility that we can find it with a bad graphics card by using the Kangaroo program?

It is obvious that Kangaroo and Keyhunt each have their own strengths. As far as I know, the Kangaroo program GPU cannot be used for multiple public keys and has a limit of 125 bit intervals. Therefore, Kangaroo is currently only used as a puzzle solver. Keyhunt does not use GPU, but it can be tested in the full range space and under multiple public keys simultaneously, although its efficiency is not high when running at high bits. If kangaroos can support full range and multiple public keys, then undoubtedly it will be the most suitable. Also, I come from China and the translator may not be accurate. I apologize!

[3dmlib]

It will be nice to know from this program developer if kangaroo can work with 128-bit range?
Or it absolute maximum 125-bit as stated in the readme?
So, splitting in half #130 puzzle will help? It will be exactly two 128-bit ranges then.
Thanks.

I'm waiting for the answer to this question, but no one can say anything definitive. It is necessary to find the person who made this program.
Does this program work with more than 125 BIT RANGE?

It has been answered multiple times, please read.

Again, on JLPs github (the person who built this program)

#130
Expected time: several years on 256 Tesla V100 (Not possible with this program without modification)

Sorry, but I can't find 100% official answer that it will work on 128-bit range.
125-bit will work, 129-bit (#130 puzzle) no, as stated in readme.
Some speculation that it can work with 126, 127 and 128-bit ranges.
But I need 100% to know so. I think developer of this program should know this 100%.
Thanks.

[WanderingPhilospher]

It will be nice to know from this program developer if kangaroo can work with 128-bit range?
Or it absolute maximum 125-bit as stated in the readme?
So, splitting in half #130 puzzle will help? It will be exactly two 128-bit ranges then.
Thanks.

I'm waiting for the answer to this question, but no one can say anything definitive. It is necessary to find the person who made this program.
Does this program work with more than 125 BIT RANGE?

It has been answered multiple times, please read.

Again, on JLPs github (the person who built this program)

#130
Expected time: several years on 256 Tesla V100 (Not possible with this program without modification)

Sorry, but I can't find 100% official answer that it will work on 128-bit range.
125-bit will work, 129-bit (#130 puzzle) no, as stated in readme.
Some speculation that it can work with 126, 127 and 128-bit ranges.
But I need 100% to know so. I think developer of this program should know this 100%.
Thanks.

It will work with 128 and below, 100%

[Baskentliia]

It will be nice to know from this program developer if kangaroo can work with 128-bit range?
Or it absolute maximum 125-bit as stated in the readme?
So, splitting in half #130 puzzle will help? It will be exactly two 128-bit ranges then.
Thanks.

I'm waiting for the answer to this question, but no one can say anything definitive. It is necessary to find the person who made this program.
Does this program work with more than 125 BIT RANGE?

It has been answered multiple times, please read.

Again, on JLPs github (the person who built this program)

#130
Expected time: several years on 256 Tesla V100 (Not possible with this program without modification)

Sorry, but I can't find 100% official answer that it will work on 128-bit range.
125-bit will work, 129-bit (#130 puzzle) no, as stated in readme.
Some speculation that it can work with 126, 127 and 128-bit ranges.
But I need 100% to know so. I think developer of this program should know this 100%.
Thanks.

It will work with 128 and below, 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?

[3dmlib]

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?

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

[WanderingPhilospher]

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.

[Jean_Luc]

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 !

[kTimesG]

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 !

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.

[iceland2k14]

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 !

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.

[WanderingPhilospher]

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 !

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.

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.

[Jean_Luc]

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 

[WanderingPhilospher]

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

[kTimesG]

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.

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?

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.

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.

[WanderingPhilospher]

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.

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?

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.

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

[Jean_Luc]

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/