Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo

[tmar777]

Hi albertajuelo and kTimesG

thank you both for your replies, especially albertajuelo's detailed explanation was very helpful!
While being here to solve the puzzle, the process itself has become more interesting than the price itself. The parallel computing power of GPUs it will become my next learning endeavour.
albertajuelo and kTimesG if not bothering you, please DM me as I cannot send you as a newbie (bitcointalk by default has deactivated the option to receive from newbies DMs)
Thanks

[zloy_ya]

Hello, I previously asked you a question about adding the -end search range function, you answered me why you are not satisfied with -range .. I will answer why if I am looking for a 130 puzzle, then -range 84 will search where the zeros are in this example -dp 16 -range 84 -start 33e7665705350000000000000000000000 but nothing more right?) and what I mean is that with the -end function I can break the same 135 puzzle into a dozen or a hundred pieces and search throughout -range 134 but with short distances as an example -range 134 -start 6d9999999999999999999999999999996 -end 7ffffffffffffffffffffffffffff I can calculate the work here, let’s say that I would go through one path in one day and the next day start another path, but only with the start I can’t do this because I don’t know where this path ended if I turn off the program in other words, -end is needed so that you can start with it later) but with -range this is not possible

[RetiredCoder]

Updated Part #1, v1.6:

- Best K = 0.99.
- optimized SOTA/SOTA+ parameters for smooth K for all intervals.

[pfr advance]

Hi RetiredCoder,

Can you confirm that you are using the code from Jean Luc here: https://github.com/JeanLucPons/Kangaroo ? I'm really interested, and for us beginners, it would be super helpful to have a detailed tutorial explaining how you set it up from start to finish, including allocating resources on https://cloud.vast.ai.

If you could create a tutorial detailing the whole process, including how to configure and run the Kangaroo, it would be amazing! Thanks in advance for your help and the time you could dedicate to it!

Best regards,

P.S. A big thank you to Satoshi, even though I lost all my 10 BTC back in 2017 . That’s why I want to try my luck with Jean Luc’s code.
PFR ==> bc1qltyqxw94nynyj9nq8kqfvzuxjrwejd6vrdvhlm

[RetiredCoder]

Hello, I previously asked you a question about adding the -end search range function, you answered me why you are not satisfied with -range .. I will answer why if I am looking for a 130 puzzle, then -range 84 will search where the zeros are in this example -dp 16 -range 84 -start 33e7665705350000000000000000000000 but nothing more right?) and what I mean is that with the -end function I can break the same 135 puzzle into a dozen or a hundred pieces and search throughout -range 134 but with short distances as an example -range 134 -start 6d9999999999999999999999999999996 -end 7ffffffffffffffffffffffffffff I can calculate the work here, let’s say that I would go through one path in one day and the next day start another path, but only with the start I can’t do this because I don’t know where this path ended if I turn off the program in other words, -end is needed so that you can start with it later) but with -range this is not possible

Your idea sounds senseless for me, but anyway it's open-source so you can modify sources and implement all ideas you have.

Can you confirm that you are using the code from Jean Luc here: https://github.com/JeanLucPons/Kangaroo ?

You can download both sources and compare, my code is not related to JLP's code.

I'm really interested, and for us beginners, it would be super helpful to have a detailed tutorial explaining how you set it up from start to finish

I won't write articles like "step-by-step guide how to crack #135", sorry  

[atom13]

Hello, I previously asked you a question about adding the -end search range function, you answered me why you are not satisfied with -range .. I will answer why if I am looking for a 130 puzzle, then -range 84 will search where the zeros are in this example -dp 16 -range 84 -start 33e7665705350000000000000000000000 but nothing more right?) and what I mean is that with the -end function I can break the same 135 puzzle into a dozen or a hundred pieces and search throughout -range 134 but with short distances as an example -range 134 -start 6d9999999999999999999999999999996 -end 7ffffffffffffffffffffffffffff I can calculate the work here, let’s say that I would go through one path in one day and the next day start another path, but only with the start I can’t do this because I don’t know where this path ended if I turn off the program in other words, -end is needed so that you can start with it later) but with -range this is not possible

Your idea sounds senseless for me, but anyway it's open-source so you can modify sources and implement all ideas you have.

Can you confirm that you are using the code from Jean Luc here: https://github.com/JeanLucPons/Kangaroo ?

You can download both sources and compare, my code is not related to JLP's code.

I'm really interested, and for us beginners, it would be super helpful to have a detailed tutorial explaining how you set it up from start to finish

I won't write articles like "step-by-step guide how to crack #135", sorry  

And by the way can you send me your BTC 
Some people don´t understand how hard is this to crack

[pfr advance]

Hello, I previously asked you a question about adding the -end search range function, you answered me why you are not satisfied with -range .. I will answer why if I am looking for a 130 puzzle, then -range 84 will search where the zeros are in this example -dp 16 -range 84 -start 33e7665705350000000000000000000000 but nothing more right?) and what I mean is that with the -end function I can break the same 135 puzzle into a dozen or a hundred pieces and search throughout -range 134 but with short distances as an example -range 134 -start 6d9999999999999999999999999999996 -end 7ffffffffffffffffffffffffffff I can calculate the work here, let’s say that I would go through one path in one day and the next day start another path, but only with the start I can’t do this because I don’t know where this path ended if I turn off the program in other words, -end is needed so that you can start with it later) but with -range this is not possible

Your idea sounds senseless for me, but anyway it's open-source so you can modify sources and implement all ideas you have.

Can you confirm that you are using the code from Jean Luc here: https://github.com/JeanLucPons/Kangaroo ?

You can download both sources and compare, my code is not related to JLP's code.

I'm really interested, and for us beginners, it would be super helpful to have a detailed tutorial explaining how you set it up from start to finish

I won't write articles like "step-by-step guide how to crack #135", sorry  

And by the way can you send me your BTC 
Some people don´t understand how hard is this to crack

Hi,

Thanks for your response. Could you please share the GitHub repository for your solution? I’d like to explore different approaches, but I want to start by testing Jean Luc’s solution first. I’m not asking for a step-by-step guide to crack #135—I’m still figuring out how to compile Jean Luc’s program with the latest versions. For example, to compile VanitySearch, you had to update Visual Studio Code in 2017 instead of using the 2022 version. Unfortunately, there haven't been any updates from him for a while, and I hope he’s doing well.

As for the other person, it seems you’re taking the easy way out. I never asked for BTC; I prefer to solve the puzzles that the most kind and fair Satoshi made available to us. At least he let us try freely. He would probably be sad to see shortcuts like the ones you’ve suggested. Anyway, I forgive you.

Best regards,
P.S. A big thank you to Satoshi, even though I lost all my 10 BTC back in 2017 Cry. That’s why I want to try my luck with Jean Luc’s code.
PFR ==> bc1qltyqxw94nynyj9nq8kqfvzuxjrwejd6vrdvhlm

[karrask]

Hello, I previously asked you a question about adding the -end search range function, you answered me why you are not satisfied with -range .. I will answer why if I am looking for a 130 puzzle, then -range 84 will search where the zeros are in this example -dp 16 -range 84 -start 33e7665705350000000000000000000000 but nothing more right?) and what I mean is that with the -end function I can break the same 135 puzzle into a dozen or a hundred pieces and search throughout -range 134 but with short distances as an example -range 134 -start 6d9999999999999999999999999999996 -end 7ffffffffffffffffffffffffffff I can calculate the work here, let’s say that I would go through one path in one day and the next day start another path, but only with the start I can’t do this because I don’t know where this path ended if I turn off the program in other words, -end is needed so that you can start with it later) but with -range this is not possible

Your idea sounds senseless for me, but anyway it's open-source so you can modify sources and implement all ideas you have.

Can you confirm that you are using the code from Jean Luc here: https://github.com/JeanLucPons/Kangaroo ?

You can download both sources and compare, my code is not related to JLP's code.

I'm really interested, and for us beginners, it would be super helpful to have a detailed tutorial explaining how you set it up from start to finish

I won't write articles like "step-by-step guide how to crack #135", sorry  

And by the way can you send me your BTC 
Some people don´t understand how hard is this to crack

Hi,

Thanks for your response. Could you please share the GitHub repository for your solution? I’d like to explore different approaches, but I want to start by testing Jean Luc’s solution first. I’m not asking for a step-by-step guide to crack #135—I’m still figuring out how to compile Jean Luc’s program with the latest versions. For example, to compile VanitySearch, you had to update Visual Studio Code in 2017 instead of using the 2022 version. Unfortunately, there haven't been any updates from him for a while, and I hope he’s doing well.

As for the other person, it seems you’re taking the easy way out. I never asked for BTC; I prefer to solve the puzzles that the most kind and fair Satoshi made available to us. At least he let us try freely. He would probably be sad to see shortcuts like the ones you’ve suggested. Anyway, I forgive you.

Best regards,
P.S. A big thank you to Satoshi, even though I lost all my 10 BTC back in 2017 Cry. That’s why I want to try my luck with Jean Luc’s code.
PFR ==> bc1qltyqxw94nynyj9nq8kqfvzuxjrwejd6vrdvhlm

in the 2022 version

<Import Project="$(VCTargetsPath)\BuildCustomizations\CUDA 12.6.props" />
<Import Project="$(VCTargetsPath)\BuildCustomizations\CUDA 12.6.targets" />

<CodeGeneration Condition="'$(Configuration)|$(Platform)'=='Release|x64'">compute_86,sm_86;compute_90,sm_90</CodeGeneration>

[damiankopacz87]

Hi,

Did You guys check newest release od RCKangaroo? Does it work on eg. 100bit space?

@RetiredCoder, do You plan any other minipuzzles (or maxi) in the future? Let us know "when", if You plan something, please

BR
Damian

[pfr advance]

not at all. did you manage to assemble the code?

I finally managed to compile the VanitySearch and Kangaroo projects by Jean-Luc with the version he uploaded on GitHub. It's much easier now! I hope he'll update his projects to allow us to randomly define a search interval. If you're here, Jean-Luc, we need you! (As for Satoshi, we'll save you for last, haha!)

Best regards,
P.S. A big thank you to Satoshi, even though I lost all my 10 BTC back in 2017 Cry. That’s why I want to try my luck with Jean Luc’s code.
PFR ==> bc1qltyqxw94nynyj9nq8kqfvzuxjrwejd6vrdvhlm

[tmar777]

not at all. did you manage to assemble the code?

I finally managed to compile the VanitySearch and Kangaroo projects by Jean-Luc with the version he uploaded on GitHub. It's much easier now! I hope he'll update his projects to allow us to randomly define a search interval. If you're here, Jean-Luc, we need you! (As for Satoshi, we'll save you for last, haha!)

Best regards,
P.S. A big thank you to Satoshi, even though I lost all my 10 BTC back in 2017 Cry. That’s why I want to try my luck with Jean Luc’s code.
PFR ==> bc1qltyqxw94nynyj9nq8kqfvzuxjrwejd6vrdvhlm

Hi,
this is what i was looking for and just came across!
can you please share your code?
Thanks

[mjojo]

Hi @albertajuelo,

Would you elaborate again for your explanation below about DP.

2) To understand DPs and how they affect. First you need to know what a DP is: Distinguished points: a point is a distinguished point if its representation exhibits a certain bit pattern, e.g., has the top 20 bits equal to zero.

You have to know that you have a number of X kangaroos that make Y jumps every second.

Now if we use a DP of Z bits, that means that depending on the Z, that will be the average chance that a kangaroo will find a point that has that DP.

The higher the Z, the harder it will be to find that DP.

Now I recommend that for you to learn better in a practical way, you play with if I use a very low DP, what happens to the memory? How many points do I store?
Same if I use a very high DP.

Thank you.

[Denevron]

Hello, won't there be a version for red cards (amd)?

[Khaak Ru]

Hi everyone. Thank to RC for this software.

I just run the exe and get very low speeds for my 3080. Where can be the problem? You can also see that speed is increasing gradually.

Code:

********************************************************************************
*                    RCKangaroo v3.0  (c) 2024 RetiredCoder                    *
********************************************************************************

This software is free and open-source: https://github.com/RetiredC
It demonstrates fast GPU implementation of SOTA Kangaroo method for solving ECDLP
Windows version
CUDA devices: 1, CUDA driver/runtime: 12.7/12.6
GPU 0: NVIDIA GeForce RTX 3080, 10.00 GB, 68 CUs, cap 8.6, PCI 65, L2 size: 5120 KB
Total GPUs for work: 1

BENCHMARK MODE

Solving point: Range 78 bits, DP 16, start...
SOTA method, estimated ops: 2^39.202, RAM for DPs: 0.547 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 4.329. DP overhead is big, use less DP value if possible!
GPU 0: allocated 6557 MB, 2228224 kangaroos. OldGpuMode: Yes
GPUs started...
BENCH: Speed: 19 MKeys/s, Err: 0, DPs: 33K/9646K, Time: 0d:00h:00m/0d:09h:14m
BENCH: Speed: 64 MKeys/s, Err: 0, DPs: 101K/9646K, Time: 0d:00h:00m/0d:02h:44m
BENCH: Speed: 86 MKeys/s, Err: 0, DPs: 134K/9646K, Time: 0d:00h:00m/0d:02h:02m
BENCH: Speed: 131 MKeys/s, Err: 0, DPs: 202K/9646K, Time: 0d:00h:00m/0d:01h:20m
BENCH: Speed: 154 MKeys/s, Err: 0, DPs: 236K/9646K, Time: 0d:00h:00m/0d:01h:08m
BENCH: Speed: 197 MKeys/s, Err: 0, DPs: 305K/9646K, Time: 0d:00h:01m/0d:00h:53m
BENCH: Speed: 242 MKeys/s, Err: 0, DPs: 372K/9646K, Time: 0d:00h:01m/0d:00h:43m
BENCH: Speed: 265 MKeys/s, Err: 0, DPs: 406K/9646K, Time: 0d:00h:01m/0d:00h:39m
BENCH: Speed: 309 MKeys/s, Err: 0, DPs: 475K/9646K, Time: 0d:00h:01m/0d:00h:34m
BENCH: Speed: 331 MKeys/s, Err: 0, DPs: 508K/9646K, Time: 0d:00h:01m/0d:00h:31m
BENCH: Speed: 357 MKeys/s, Err: 0, DPs: 576K/9646K, Time: 0d:00h:01m/0d:00h:29m
BENCH: Speed: 357 MKeys/s, Err: 0, DPs: 644K/9646K, Time: 0d:00h:02m/0d:00h:29m
BENCH: Speed: 357 MKeys/s, Err: 0, DPs: 678K/9646K, Time: 0d:00h:02m/0d:00h:29m
BENCH: Speed: 356 MKeys/s, Err: 0, DPs: 746K/9646K, Time: 0d:00h:02m/0d:00h:29m
BENCH: Speed: 355 MKeys/s, Err: 0, DPs: 779K/9646K, Time: 0d:00h:02m/0d:00h:29m
BENCH: Speed: 356 MKeys/s, Err: 0, DPs: 848K/9646K, Time: 0d:00h:02m/0d:00h:29m
BENCH: Speed: 356 MKeys/s, Err: 0, DPs: 915K/9646K, Time: 0d:00h:02m/0d:00h:29m
BENCH: Speed: 356 MKeys/s, Err: 0, DPs: 949K/9646K, Time: 0d:00h:03m/0d:00h:29m

After keeping benchmark mode running for a day I saw results like this, but they were not consistent. Some of the test were done with good speeds but some were very slow. I am not sure what it depends on. I use Windows 11.

Code:

Solving point: Range 78 bits, DP 16, start...
SOTA method, estimated ops: 2^39.202, RAM for DPs: 0.547 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 4.329. DP overhead is big, use less DP value if possible!
GPU 0: allocated 6557 MB, 2228224 kangaroos. OldGpuMode: Yes
GPUs started...
BENCH: Speed: 1224 MKeys/s, Err: 0, DPs: 305K/9646K, Time: 0d:00h:00m/0d:00h:08m
BENCH: Speed: 2261 MKeys/s, Err: 0, DPs: 645K/9646K, Time: 0d:00h:00m/0d:00h:04m
BENCH: Speed: 2261 MKeys/s, Err: 0, DPs: 985K/9646K, Time: 0d:00h:00m/0d:00h:04m
BENCH: Speed: 2258 MKeys/s, Err: 0, DPs: 1358K/9646K, Time: 0d:00h:00m/0d:00h:04m
BENCH: Speed: 2261 MKeys/s, Err: 0, DPs: 1699K/9646K, Time: 0d:00h:00m/0d:00h:04m
BENCH: Speed: 2261 MKeys/s, Err: 0, DPs: 2038K/9646K, Time: 0d:00h:01m/0d:00h:04m
BENCH: Speed: 2258 MKeys/s, Err: 0, DPs: 2378K/9646K, Time: 0d:00h:01m/0d:00h:04m
BENCH: Speed: 2261 MKeys/s, Err: 0, DPs: 2718K/9646K, Time: 0d:00h:01m/0d:00h:04m
BENCH: Speed: 2256 MKeys/s, Err: 0, DPs: 3056K/9646K, Time: 0d:00h:01m/0d:00h:04m
BENCH: Speed: 2258 MKeys/s, Err: 0, DPs: 3430K/9646K, Time: 0d:00h:01m/0d:00h:04m
BENCH: Speed: 2259 MKeys/s, Err: 0, DPs: 3770K/9646K, Time: 0d:00h:01m/0d:00h:04m
BENCH: Speed: 2256 MKeys/s, Err: 0, DPs: 4110K/9646K, Time: 0d:00h:02m/0d:00h:04m
BENCH: Speed: 2256 MKeys/s, Err: 0, DPs: 4450K/9646K, Time: 0d:00h:02m/0d:00h:04m
BENCH: Speed: 2258 MKeys/s, Err: 0, DPs: 4791K/9646K, Time: 0d:00h:02m/0d:00h:04m
BENCH: Speed: 2261 MKeys/s, Err: 0, DPs: 5131K/9646K, Time: 0d:00h:02m/0d:00h:04m
BENCH: Speed: 2261 MKeys/s, Err: 0, DPs: 5471K/9646K, Time: 0d:00h:02m/0d:00h:04m
BENCH: Speed: 2258 MKeys/s, Err: 0, DPs: 5846K/9646K, Time: 0d:00h:02m/0d:00h:04m
BENCH: Speed: 2250 MKeys/s, Err: 0, DPs: 6186K/9646K, Time: 0d:00h:03m/0d:00h:04m
BENCH: Speed: 2193 MKeys/s, Err: 0, DPs: 6492K/9646K, Time: 0d:00h:03m/0d:00h:04m
BENCH: Speed: 2185 MKeys/s, Err: 0, DPs: 6831K/9646K, Time: 0d:00h:03m/0d:00h:04m
Stopping work ...
Point solved, K: 0.823 (with DP and GPU overheads)

Points solved: 124, average K: 1.354 (with DP and GPU overheads)

[mjojo]

Hi @albertajuelo,

Would you elaborate again for your explanation below about DP.

2) To understand DPs and how they affect. First you need to know what a DP is: Distinguished points: a point is a distinguished point if its representation exhibits a certain bit pattern, e.g., has the top 20 bits equal to zero.

You have to know that you have a number of X kangaroos that make Y jumps every second.

Now if we use a DP of Z bits, that means that depending on the Z, that will be the average chance that a kangaroo will find a point that has that DP.

The higher the Z, the harder it will be to find that DP.

Now I recommend that for you to learn better in a practical way, you play with if I use a very low DP, what happens to the memory? How many points do I store?
Same if I use a very high DP.

Thank you.

Hey mjojo,

I created a table using what I recommended to do, to play around with DP values.

https://i.ibb.co/MV9M9yk/DP-values.png

You can see the values of using different DPs.

@albertajuelo thank you, may I talking with you in private, still confuse about DP.

[kTimesG]

Hey mjojo,

I created a table using what I recommended to do, to play around with DP values.



You can see the values of using different DPs.

DP ovh also depends on the total # of kangaroos. And the total # of kangaroos depends on how many GPUs you use and how many kangs / GPU (you may have different GPU specs, some more powerful, some with less or more kangaroos to increase throughput to maximum).

Why? Simple, let's say you have 1000 GPUs all running at once, each jumping 1 million kangs.

So even if one lucky GPU jumps one lucky kangaroo to a DP that is later found to be a collision, there were still 999.999.999 kangaroos that were also each jumped the same amount of times as the lucky kangaroo, on the lucky GPU and on the other 999 GPUs.

If one really plans to break 135 there are much more factors in play in order to determine the optimal parameters to minimize the total runtime, and I'm not only talking about the command line parameters, but the kernel code itself. RC's software is just a proof of concept about his strategy, it doesn't take a genius to figure out his actual code is totally different and most likely heavily more optimized so that it fits well with his algorithm.

[mjojo]

Hey mjojo,

I created a table using what I recommended to do, to play around with DP values.

https://i.ibb.co/MV9M9yk/DP-values.png

You can see the values of using different DPs.

DP ovh also depends on the total # of kangaroos. And the total # of kangaroos depends on how many GPUs you use and how many kangs / GPU (you may have different GPU specs, some more powerful, some with less or more kangaroos to increase throughput to maximum).

Why? Simple, let's say you have 1000 GPUs all running at once, each jumping 1 million kangs.

So even if one lucky GPU jumps one lucky kangaroo to a DP that is later found to be a collision, there were still 999.999.999 kangaroos that were also each jumped the same amount of times as the lucky kangaroo, on the lucky GPU and on the other 999 GPUs.

If one really plans to break 135 there are much more factors in play in order to determine the optimal parameters to minimize the total runtime, and I'm not only talking about the command line parameters, but the kernel code itself. RC's software is just a proof of concept about his strategy, it doesn't take a genius to figure out his actual code is totally different and most likely heavily more optimized so that it fits well with his algorithm.

@kTimesG thank you for the explanation

[RetiredCoder]

If one really plans to break 135 there are much more factors in play in order to determine the optimal parameters to minimize the total runtime, and I'm not only talking about the command line parameters, but the kernel code itself. RC's software is just a proof of concept about his strategy, it doesn't take a genius to figure out his actual code is totally different and most likely heavily more optimized so that it fits well with his algorithm.

Yes RCKangaroo is not heavily optimized and it's actually just a proof of concept to demonstrate that K=1.15(0.99) is possible in practice, but even well-optimized version is not even twice more faster, so it's not so bad.
As for DP overhead, from the table above it may look like DP=45 is a good idea   but of course it's not, as you have to use at least hundreds of GPUs for #135 and this table must be recalculated for the number of GPUs you use.

[RetiredCoder]

@RetiredCoder, do You plan any other minipuzzles (or maxi) in the future? Let us know "when", if You plan something, please

I don't plan them in advance, but anyway here is another one:
https://bitcointalk.org/index.php?topic=5526453.0

[HansiPeter]

Hello, I'm a little bit stupid. Maybe someone is able to help me.

I want to try the RCKangaroo.exe first with a know puzzle.
I tried
# Puzzle 22
# Adresse: 1CfZWK1QTQE3eS9qn61dQjV89KDjZzfNcv
# puplic key: 023ed96b524db5ff4fe007ce730366052b7c511dc566227d929070b9ce917abb43
# Start: 200000 Ende: 3fffff

First, which range should I use? This is not clear for me. So to what does it depend?

With the following it works, but needs a long time on my RTX 3060 Ti
RCKangaroo.exe -dp 16 -range 74 -start 200000 -pubkey 023ed96b524db5ff4fe007ce730366052b7c511dc566227d929070b9ce917abb43

And that secound, where to get the puplic key?
I mean for example for puzzle 67 it is not known.
Or how must the commandline must look for puzzle 67? Or is not possible to solve it with this programm?

Thanks a lot.