Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo

[jovica888]

I am not sure how Kangaroo algorithm is functioning but for example I run JeanLucPons/Kangaroo a few time...

I saw that it creates about 2^19 Kangaroos at the start (I have Nvidia 1070ti - it sucks) and then it finds solutions for small ranges really fast

So my question is, how are the starting points for those Kangaroos created or selected?

If it is not already working in this way, I thought maybe it would be good to make it like this

So from a lower position of range, you create 2^19 kangaroos and those Kangaroos are consecutive - one by one.... from 1G to 2^19G

Then you create a jumps and all jumps are random but those jumps must be "jump_value % 2^19 = 0" and the same jumps we use for the public_key we are searching. because jumps are "jump_value % 2^19 = 0" then all starting Kangaroos will not collide with themselves because it is not possible. Public key is jumping with those jumps and save points where X is starting with (I do not know) 0000 for example

Then we move each kangaroo with those jumps and we move public_key with those jumps UP so we are adding points basically

A collision will happen when 1 of the starting kangaroos hits the path of public_key...

The starting Kangaroo that is going to hit the path of public_key will basically follow this rule

starting_value_of_that_Kangaroo % 2^19 = private_key_of_public_key % 2^19

So if you can create more starting Kangaroos with more GPUs then you can jump larger jumps and collision will occur faster... right?

Thank you (sorry for such a bad English)

[RetiredCoder]

So my question is, how are the starting points for those Kangaroos created or selected?

Random, within some interval. For SOTA, these intervals are shown on the diagram on this page:
https://github.com/RetiredC/Kang-1

Therefore the rest of your assumptions is incorrect, learn sources to see how it works.
When huge number of kangaroos is used basically you can assume that you use birthday paradox to find a collision.

[kTimesG]

Congratulations on the 100 merits! What did you say you would do when you got here to celebrate? A mini puzzle or something else?

Judging by his new status, my guess is this happened after 3 consecutive ECDLP records:

1. Some mini-puzzles to grab some BCH change residuals.

2. Publish some breakthroughs directly via code - why write papers, it's boring.

3. Silence

4. A trip to Vegas.

5. Trying to cheat on the big casinos after a careful research on the roulette systems.

6. The mafia grabbed him, he went too greedy.

7. He lost all the puzzle winnings to the mob bosses, in exchange for his limbs to stay in their place.

8. The comeback: "no pain, no gain!".

[RetiredCoder]

Congratulations on the 100 merits! What did you say you would do when you got here to celebrate? A mini puzzle or something else?

Sure! 
https://bitcointalk.org/index.php?topic=5538285

[RetiredCoder]

@RetiredCoder, How true is this?

This fight with random values is tremendous, especially with the sources, so I support it as I can!
The answer is too boring as I said before, google gambler’s fallacy and Bayes' theorem if you are a nerd.
But instead of reading silly books, let's have some fun and write another 100 pages in "blah-blah" thread!

[jean1984]

Hello, my name is Jean from Venezuela, I live in Brazil and I speak Spanish, I'm new to this and I saw that you have discovered the key to puzzle 69, I'm trying to test this but everyone is talking and fighting and I really don't understand, I like to try with the keyhunt options and try with gpt chat to create a script by python, I'm not a computer scientist or mathematician, in fact I use a google translator, could you help me with an approach to test in any other puzzle? any clue, a code snippet and I would try to search something or create something with AI because I'm not a programmer, I would appreciate it, the last thing I tried is a script that apparently filters 75% of the keys and does a partial comparison between hashes and I think it's a good approach but without a little clue as to how the ranges could be reduced or a different approach it is really almost impossible for me because I don't know much but if you explain it to me I understand, if you could help me with something I would appreciate it, congratulations on your achievement

[RetiredCoder]

...I saw that you have discovered the key to puzzle 69...

Great.
I did not solve #69. Moreover, I never searched for low-level puzzles and I'm not going to do it in the future.

[mcdouglasx]

@RetiredCoder, How true is this?

This fight with random values is tremendous, especially with the sources, so I support it as I can!
The answer is too boring as I said before, google gambler’s fallacy and Bayes' theorem if you are a nerd.
But instead of reading silly books, let's have some fun and write another 100 pages in "blah-blah" thread!

The final definitive conclusion was the boring part.

[drpxxx]

...I saw that you have discovered the key to puzzle 69...

Great.
I did not solve #69. Moreover, I never searched for low-level puzzles and I'm not going to do it in the future.

Now crack #135 my only hope is your mini puzzles

[analyticnomad]

Dang. I'm over here writing dummy python scripts and splitting vast ranges with 8 measly cores and you're talking about cross-chain signature vulnerabilities.

I feel dumb lol

[kTimesG]

Dang. I'm over here writing dummy python scripts and splitting vast ranges with 8 measly cores and you're talking about cross-chain signature vulnerabilities.

I feel dumb lol

Don't feel, that post is full of truisms that don't really have anything to do with the puzzle, nor add any new information.

But you also shouldn't split ranges, you're increasing the difficulty of the problem. Looking for the solution using 8 subranges increases the solve time by 183% (2.83x). Not that it really matters when we're comparing an expected solve time of 1000 years with one of 2830 years though.

[analyticnomad]

Why does it increase time splitting subs? Is it the increased overhead? Easier to just iterate the entire range as quickly as possible rather than dilute ranges and iterate over those? I tried to DM you for help, but newbs get no love lol

[kTimesG]

Why does it increase time splitting subs? Is it the increased overhead? Easier to just iterate the entire range as quickly as possible rather than dilute ranges and iterate over those? I tried to DM you for help, but newbs get no love lol

I explained it like a dozen times.

When you split a sqrt(N) problem into two sqrt(N / 2) problems, it becomes a 2 * sqrt(N/2) problem, which by basic math simplification results in sqrt(2) * sqrt(N).

Last I checked, sqrt(2) is larger than the constant you started with (which was 1).

So dividing by 8 means 3 splits, hence sqrt(2) ** 3 = 2.828 = 183% increase.

Now I have to do 100 pushups. Thanks, it's been a while

[analyticnomad]

Gotcha. Yeah I had no idea. This is all new and I know its annoying to you guys to have to answer the same questions over and over.

I don't really speak the language yet but I'm learning every day. I just need help. Thank you.

[nevesromario234]

So my question is, how are the starting points for those Kangaroos created or selected?

Random, within some interval. For SOTA, these intervals are shown on the diagram on this page:
https://github.com/RetiredC/Kang-1

Therefore the rest of your assumptions is incorrect, learn sources to see how it works.
When huge number of kangaroos is used basically you can assume that you use birthday paradox to find a collision.

Thanks for the clarification! The way the starting points for the kangaroos are selected within specific intervals—especially in SOTA implementations—is really interesting. It makes sense that the birthday paradox comes into play when a large number of kangaroos are involved.

This actually reminds me of how details matter in every system, whether it’s cryptographic algorithms or personal moments like preparing the perfect пpивiтaння з днeм нapoджeння cинa (birthday wishes for a son). Just like precise intervals in cryptography, meaningful words—whether in English or Ukrainian—make all the difference in leaving a lasting impact.

Appreciate the pointer to the GitHub resource. Always good to go back to the source and learn how things really work.

[RetiredCoder]

...
you will never get 250 MK/s on any GPU, by computing H160 out of some list of private keys.
...

You just don't have enough experience in GPU coding or/and don't know about some efficient methods for EC scalar multiplication.
4090 can do >0.5GK/s at rndprivkey-to-h160, I can publish the code, just need to find some time to make my sources more readable to make them public.

[kTimesG]

...
you will never get 250 MK/s on any GPU, by computing H160 out of some list of private keys.
...

You just don't have enough experience in GPU coding or/and don't know about some efficient methods for EC scalar multiplication.
4090 can do >0.5GK/s at rndprivkey-to-h160, I can publish the code, just need to find some time to make my sources more readable to make them public.

That's great and all, but I'm not sure your estimations fit the context of what you've quoted.

I'm well aware that there are a lot of optimizations for scalar multiplication, and it's great you have really fast code to do it in CUDA as fast as you state (which sounds miraculous in itself to be honest), but there's one thing you maybe missed: the private keys are not random, they're fed as input. Yeah, maybe redo the math after crawling private keys from GPU memory

Not sure why you had to bring smth from page 520 of that topic here though. It'd be much more interesting if you instead update us on 135 progress

[RetiredCoder]

That's great and all, but I'm not sure your estimations fit the context of what you've quoted.

I'm well aware that there are a lot of optimizations for scalar multiplication, and it's great you have really fast code to do it in CUDA as fast as you state (which sounds miraculous in itself to be honest), but there's one thing you maybe missed: the private keys are not random, they're fed as input. Yeah, maybe redo the math after crawling private keys from GPU memory

Not sure why you had to bring smth from page 520 of that topic here though. It'd be much more interesting if you instead update us on 135 progress

Yeah may be I missed some context, I did not check carefully. But anyway, reading 0.5GK/s privkeys is only 16GB/s which is almost nothing for 4090 bandwidth.
I don't read "blah-blah" thread (it's disgusting), but sometimes when I'm bored I read your messages because you have some skills

[kTimesG]

That's great and all, but I'm not sure your estimations fit the context of what you've quoted.

I'm well aware that there are a lot of optimizations for scalar multiplication, and it's great you have really fast code to do it in CUDA as fast as you state (which sounds miraculous in itself to be honest), but there's one thing you maybe missed: the private keys are not random, they're fed as input. Yeah, maybe redo the math after crawling private keys from GPU memory

Not sure why you had to bring smth from page 520 of that topic here though. It'd be much more interesting if you instead update us on 135 progress

Yeah may be I missed some context, I did not check carefully. But anyway, reading 0.5GK/s privkeys is only 16GB/s which is almost nothing for 4090 bandwidth.
I don't read "blah-blah" thread (it's disgusting), but sometimes when I'm bored I read your messages because you have some skills

You also need to write 16 GB/s as well, since it's not a one-shot job. And there goes the 4090 max memory throughput.

So to compute even those minimum 250 MK/s, the first wall to pass is reading a file from disk at least at 8 GB/s, before even talking about GPUs and their memory bandwidth.

[RetiredCoder]

You also need to write 16 GB/s as well, since it's not a one-shot job. And there goes the 4090 max memory throughput.
So to compute even those minimum 250 MK/s, the first wall to pass is reading a file from disk at least at 8 GB/s, before even talking about GPUs and their memory bandwidth.

Following this logic, you forgot to mention time required to write the list to the disk before reading, also time to prepare that list before writing to the disk 
Well, ok, I just wanted to mention that there are some ways to calc random privkeys-to-pubkeys very quickly on GPU. Just a hint for those who are interested.