Bitcoin Forum

Hi all,

Here is my research about using kangaroo methods to solve ECDLP, Part 1.
Open source:  https://github.com/RetiredC/Kang-1 (https://github.com/RetiredC/Kang-1)

This software demonstrates various ways to solve the ECDLP using Kangaroos.
The required number of operations is approximately K * sqrt(range), where K is a coefficient that depends on the method used.
This software demonstrates five methods:

1 - Classic. The simplest method. There are two groups of kangaroos: tame and wild.
As soon as a collision between any tame and wild kangaroos happens, the ECDLP is solved.
In practice, K is approximately 2.10 for this method.

2 - 3-way. A more advanced method. There are three groups of kangaroos: tame, wild1, and wild2.
As soon as a collision happens between any two types of kangaroos, the ECDLP is solved.
In practice, K is approximately 1.60 for this method.

3 - Mirror. This method uses two groups of kangaroos and the symmetry of the elliptic curve to improve K.
Another trick is to reduce the range for wild kangaroos.
In practice, K is approximately 1.30 for this method.
The main issue with this method is that the kangaroos loop continuously.

4 - SOTA. This method uses three groups of kangaroos and the symmetry of the elliptic curve.
In practice, K is approximately 1.15 for this method. The main issue is the same as in the Mirror method.
I couldn’t find any papers about this method, so let's assume that I invented it :)
See "diagram.jpg" for details. Also there are several other good option sets, one of them is used in the application by default, check the sources.

5 - SOTA+. This method is the same as SOTA, but also uses cheap second point.
When we calculate "NextPoint = PreviousPoint + JumpPoint" we can also quickly calculate "PreviousPoint - JumpPoint" because inversion is the same.
If inversion calculation takes a lot of time, this second point is cheap for us and we can use it to improve K.
Using cheap point costs only (1MUL+1SQR)/2. K is approximately 1.02 for this method (assuming cheap point is free and not counted as 1op).
Or you can pay 1MUL+1SQR and get K about 0.99 (preferable for GPU implementation).
Or you can pay only (1MUL+1SQR)/4 and get K about 1.05.
Again, I couldn’t find any papers about this method applied to Kangaroo, so let's assume that I invented it.

Important note: this software handles kangaroo looping in a very simple way, this method is bad for high ranges.
Next part will demonstrate a good way to handle loops.

PS. Please don't post any stupid messages here, I will remove them; also don't post AI-generated messages and other spam.

Here is my research about using kangaroo methods to solve ECDLP, Part 2.
Open source:  https://github.com/RetiredC/Kang-2 (https://github.com/RetiredC/Kang-2)

In this part I propose a new method to handle kangaroo looping, it works for all ranges and DP values and does not increase the number of required operations, the only requirement is keeping a short list of visited points which can be coded efficiently on GPU as well, and I will demonstrate it in Part 3.

Here is my research about using kangaroo methods to solve ECDLP, Part 3.

RCKangaroo software, Windows/Linux:
Open source:  https://github.com/RetiredC/RCKangaroo (https://github.com/RetiredC/RCKangaroo)

This software demonstrates fast implementation of SOTA method and advanced loop handling on Nvidia cards.

When gpu test version?

It's part #3, the last one, so not very soon.

Hello.
I find it difficult to understand C or C++ language in math operations.

Instead, I develop algorithms with the Fastecdsa Library in Python. I then switch to C or C++ for performance and then use it with GPU performance.

When I tried to read your article, I tried to understand what the value of K is based on. If I see this rule of 4 algorithm you mentioned (such as Fastecdsa or Sagemath in Python), I can join your conversation more.

Just wanted to point out. I am following your topic.

Thank you very much.

I use C++ because it's faster so I can test thousands of points to measure K carefully. CUDA is even faster of course, but it's difficult to use it for research, so I use it only at the last stage.
Yes, it's not an easy topic, so today I added "diagram.jpg" to show how it works.

Hello.
I analysed the diagram.
if we call pubkey the big X
according to the diagram
Tame , Wild and K, what kind of an elliptic curve process is applied to X when K = 1.15
Thank you

Check "Ec.cpp", this one:
https://en.bitcoin.it/wiki/Secp256k1 (https://en.bitcoin.it/wiki/Secp256k1)

Hi!
can it tested on MacOS ?

Windows only and You need Visual Studio with MFC

Correct.
Windows, VS MFC C++.
Oldschool hardcore  :)

Hello.
I think I misunderstood.
I know Elliptic Curve operations and the Signature algorithm, I know the applicable attack methods.
I'm trying to find out what you're trying to explain.
I think you have a prejudice. Nevertheless, thank you for your work.

I propose a new method to solve ECDLP with 1.15*sqrt(N) operations (real, not theoretical).
You can read this paper to see methods with 2*sqrt(N) and 1.714*sqrt(N) required ops:
https://arxiv.org/pdf/1501.07019 (https://arxiv.org/pdf/1501.07019)
Or this paper with 1.36*sqrt(N) required ops:
https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf (https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf)
The best K that I can find in papers is 1.275 (theoretical, in practice it's always a bit worse).
If you know papers describing kangaroo methods with K=1.15 or lower - let me know.

And what is the meaning of calculating K? As soon as you increase the number of kangaroos, your K will fly into space.
With 65536 kangaroos  in the classic version K will be 3.07
And when using the GPU, K increases even more due to dp overhead, in this case you will easily reach k=10
Your experiment is purely laboratory conditions, in real life on the GPU, the number of kangaroos is huge.

Correct, if you set a large number of kangaroos, DP overhead will be high and K will be high.
The number of kangaroos must be small related to sqrt(range), for example, it's a bad idea to use 64K kangaroos to solve 32bit range because total number of jumps of all kangs to solve 32bit is about 64K so it's just one jump for every kang, and DP>0 will cause a big overhead.
On GPU you have a lot of kangs but you will solve high ranges so K will be good.
There are many ways to get high K, you can play with parameters and find out how to keep it small.
The reason to calculate K is to see what parameters are the best.

First of all, thank you guys for all your support!  ;D
Slowly, but I keep working on making my ideas public, here is Part 2 of 3:

Open source:  https://github.com/RetiredC/Kang-2 (https://github.com/RetiredC/Kang-2)

In this part I propose a new method to handle kangaroo looping, it works for all ranges and DP values and does not increase the number of required operations, the only requirement is keeping a short list of visited points which can be coded efficiently on GPU as well, and I will demonstrate it in Part 3.
Take care!

Thank you RetiredCoder for part 1,2.

Of course you can use CPU instead of GPU if you don't care about speed.
You can do many things if you don't care about speed, for example, you can use Python instead of C++ to make life easier.

Please don't spam my github repos, you waste your time.

Update: final part #3 (RCKangaroo) is ready and will be released shortly.

Thank you,

As promised, here is the third and final part: RCKangaroo, Windows/Linux, open source:
https://github.com/RetiredC/RCKangaroo (https://github.com/RetiredC/RCKangaroo)
This software demonstrates fast implementation of SOTA method and advanced loop handling on RTX40xx cards.
Note that I have not included all possible optimizations because it's public code and I want to keep it as simple/readable as possible. Anyway, it's fast enough to demonstrate the advantage and you can improve it further if you have enough skills.

wow,  congratulations to you for finding #120, 125 and 130 (probably a world record for 130). Your skills have been rewarded with over 37 BTC recovered. How many GPUs did you have to use to find the 130? Have you used an optimized version of your RCKangaroo or another tool?

Less than 37BTC, check you calculations.
Most of GPU code from RCKangaroo was used for #130.
I spent two months, about 400 RTX4090, I was lucky and solved it twice faster than expected.

As much for me 26 bTC I had not noticed that for #120 the price had not yet been *10! the reward remains correct. Thank you for your response and the details but 400 RTX 4090 for 2 months is colossal and impossible for 99.9% of people!! Well done anyway

Thanks for sharing your repositories and source code.

Great job!

Some explanations about other GPUs support:
1. I have zero interest in old cards (same for AMD cards) so I don't have them for development/tests and don't support them.
2. You can easily enable support for older nvidia cards, it will work, but my code is designed for the latest generation, for previous generations it's not optimal and the speed is not the best, that's why I disabled them.

Executing the puzzle #85 on RTX 4060


I compare the number of operations with JLP:


Quick comparison, its using the half of the RAM used with the same DP and less operations

Thank you so much, any advice for Linux users?

Ok, it's better to support 30xx cards even if RCKangaroo is not optimized for them, so I released v1.1.
3090 shows about 3GKeys/sec only, it can be really faster.


Linux exe is included as well, or you can compile it by yourself.

Really? "3090 shows about 3GKeys/sec only" this is a record man, I can believe! I just can say Thanks!

have a Makefile compatible with linux ?

Sure

this is my version of make file

PROJECT = RCKangaroo
CC = g++
NVCC = nvcc
CFLAGS = -Wall -O2
INCLUDES = -I/usr/local/cuda/include 
LIBDIRS = -L/usr/local/cuda/lib64   
LIBS_CUDA = -lcudart               

# File sorgente
CPP_FILES = $(wildcard *.cpp)
CU_FILES = $(wildcard *.cu)
OBJECTS = $(CPP_FILES:.cpp=.o) $(CU_FILES:.cu=.o)

all: $(PROJECT)

$(PROJECT): $(OBJECTS)
   $(NVCC) $(OBJECTS) -o $(PROJECT) $(LIBDIRS) $(LIBS_CUDA)

%.o: %.cpp
   $(CC) $(CFLAGS) $(INCLUDES) -c $< -o $@

%.o: %.cu
   $(NVCC) -O2 $(INCLUDES) -c $< -o $@

clean:
   rm -f $(PROJECT) $(OBJECTS)

how to use it with RTX2070super, please, because I only have 2070, I am very interested in testing your work. I tried modifying the parameter settings but it failed.

As far as I remember these cards have only 64KB of shared memory.
Set JMP_CNT to 512 and change 17 to 16 in this line in KernelB:
u64* table = LDS + 8 * JMP_CNT + 17 * THREAD_X;
and recalculate LDS_SIZE_ constants.
I think it's enough, though may be I forgot something...
The main issue is not in compiling, but in optimizations, my code is not for 20xx and 30xx cards, so it won't work with good speed there.
That's why I don't want to support old cards: if I support them officially but not optimize you will blame me that they have bad speed.
But feel free to modify/optimize sources for your hardware :)

I'll be honest, your kangaroo finds the key faster than mine or jlp. Yes, the speed shows less, but in the end it finds it much faster.
Works even on 1660 super (~600Mkeys/s).
Thanks for sharing.

@Etar how did you do everything to make your GTX 1660 work? Can you tell me all the changes and show me them? Many thanks

file: RCGpuCore.cu
line 285: u64* table = LDS + 8 * JMP_CNT + 16 * THREAD_X;
file: RCKangaroo.cpp
Line 99: if (deviceProp.major < 6)
file: defs.h
#define LDS_SIZE_A         (64 * 1024)
#define LDS_SIZE_B         (64 * 1024)
#define LDS_SIZE_C         (64 * 1024)
#define JMP_CNT            512
file: RCKangaroo.vcxproj
line 118: <CodeGeneration>compute_75,sm_75;compute_75,sm_75</CodeGeneration>
line 141: <CodeGeneration>compute_75,sm_75;compute_75,sm_75</CodeGeneration>

May I ask why, my 4060ti graphics card has a speed of just over 2000



CUDA devices: 1, CUDA driver/runtime: 12.6/12.5
GPU 0: NVIDIA GeForce RTX 4060 Ti, 16.00 GB, 34 CUs, cap 8.9, PCI 1, L2 size: 32768 KB
Total GPUs for work: 1
Solving point: Range 76 bits, DP 16, start...
SOTA method, estimated ops: 2^38.202, RAM for DPs: 0.367 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 23.090.
GPU 0: allocated 1187 MB, 208896 kangaroos.
GPUs started...
MAIN: Speed: 2332 MKeys/s, Err: 0, DPs: 345K/4823K, Time: 0d:00h:00m, Est: 0d:00h:02m
MAIN: Speed: 2320 MKeys/s, Err: 0, DPs: 704K/4823K, Time: 0d:00h:00m, Est: 0d:00h:02m

Thank you very much. Following your suggestion, I modified LDS_SIZE_ constants and successfully ran it perfectly on my 2070. Thanks again for your artistic work. By comparing the test, it is faster to find the private key than JLP's code. Next, I will try to understand your code and optimize it with the help of Claude 3.5 to increase the speed. Maybe you have more good suggestions.

file: RCGpuCore.cu
Line 99 looks like this
SubModP(tmp, x, jmp_x);

If you replace it with
if (deviceProp.major < 6)

This error occurs when creating:
RCGpuCore.cu(99): error: identifier "deviceProp" is undefined
     if (deviceProp.major < 6)
         ^

1 error detected in the compilation of "RCGpuCore.cu".
make: *** [Makefile:26: RCGpuCore.o] Error 2

Did you make a mistake?

Thank you for your effort

I use visual studio. Oh, sorry it is in file RCKangaroo.cpp line 99 (changed previous post)
I also made other changes, which is probably why the line numbers don't match. But you can easily find the lines you need, because I didn't add anything new, I just changed it.

You can improve it in many ways.
For example, since L2 is useless for old cards, disable setting persistent part of L2 and set
#define PNT_GROUP_CNT      32
and change these lines in KernelB:



Do you expect better speed? Why? 4090 has 128 CUs, 4060ti only 34.

Hello, can you tell me in which file you can find L2 and what you have to deactivate?
Thank you

I found it GpuKang.cpp that
Is that right there?

No, it's "cudaStreamSetAttribute".
Be careful with modifications if you don't know what you are doing exactly. The algorithm is not so straight as the classic one, for example, if you damage loop handling it will work for small ranges but fail for high ranges.

Discovered a problem
I didn't modify your source code, I ran it directly using the program you compiled
However, after running for a period of time, a large number of errors occurred.

DPs buffer overflow，some points lost, increase DP value!
DPs buffer overflow，some points lost, increase DP value!
DPs buffer overflow，some points lost, increase DP value!

At the beginning, it was normal, but the error message above kept appearing. May I ask why?

Yes, if parameters are not optimal, in some cases it will show you a warning.
In this case you should increase "-dp" option value, DB is growing and CPU cannot add so many DPs every second.

Hello would anyone be able to adapt it to RTX 20xx series and compile it for windows?

Yes, some people already took my code optimized for 40xx, compiled it on 1xxx/20xx/30xx and said that it's slow, completely unexpected behavior :D
However, you can find instructions how to compile in this thread.

I really appreciate it. I prioritize faster results over raw speed, as they are not the same thing.
Thks ::)

I am trying to get the code to run on my humble GEFORCE 1060
I have made etar's modifications and get this.
CUDA devices: 1, CUDA driver/runtime: 12.2/12.0
GPU 0: NVIDIA GeForce GTX 1060 6GB, 5.93 GB, 10 CUs, cap 6.1, PCI 83, L2 size: 1536 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: 157.013.
GPU 0, cuSetGpuParams failed: invalid argument!
GPU 0 Prepare failed
GPUs started...
BENCH: Speed: 125829 MKeys/s, Err: 0, DPs: 0K/9646K, Time: 0d:00h:00m, Est: 0d:00h:00m

How can I fix the GPU 0, cuSetGpuParams failed: invalid argument! error?

Thank you.

I appreciate it for your great work!
It work fine for my A3000 and it more faster than JPL about 30%!
Will you work for the client/server version the next step?
Thanks.

A3000 slow then 4090

Hi all,

first of all thanks for RetiredCoder for his research and work and providing it to the community!

I am new here but followed all the posts already for a while and trying to get my head around it :D

I got a dumb question, its mentioned the theres no workload tooling, but lets say i have 2 machines I can run, can I split the worklod e.g. as sample take puzzle #85.
Do I just split the range parameter as well as the start point?

Your question isn’t dumb at all! Yes, if you're running a workload like solving puzzle #85 and have multiple machines to use, splitting the range and start point is a common approach to divide the workload.

How it works:
Range Parameter:
If the puzzle involves iterating over a range of numbers or states, you can split that range across the machines. For instance, if the range is [0, 100], you could let:

Machine 1 handle [0, 49]
Machine 2 handle [50, 100]
Start Point:
If there's a start parameter involved, ensure each machine knows where to begin for its portion of the range.

Independent Processing:
Make sure that each machine can independently process its assigned range without depending on results from the other. This ensures no overlap or missed parts.

Steps to Implement:
Divide the workload logically based on the problem's parameters (e.g., ranges or chunks of input data).
Ensure the start and end points for each machine are mutually exclusive.
If the workload has side effects or shared state, manage synchronization carefully (e.g., use locks or shared memory if needed, or avoid shared state altogether).
Example:
Assuming puzzle #85 involves calculating something over a range [0, 1000]:

On Machine 1, run the code with start=0 and end=499.
On Machine 2, run the code with start=500 and end=1000.
This approach scales well as long as:

The problem is divisible.
The results from one range don’t depend on another range.
Let me know if you'd like more detailed help with setting up the splitting logic!

Thanks for the fast response, and yes maybe I need more clarity on the splitting. I started to get my head around the details just 2 weeks ago and sometimes there comes a lot of questionmarks.

Lets assume with puzzle #81, I got the private key range in 100000000000000000000:1ffffffffffffffffffff

So if I have one machine only I would do:

And for 2 machines, would I split the range in half, which would be: 17fffffffffffffffffff

Machine 1:

Machine 2:


With the range I am not sure about.
I did not find the "END" parameter you mentioned in the RCKangaroo, and im sure it works with the range parameter to determine "the end"

RCKangaroo supports only the start of the range, but this is not an issue. You can simply split the range into multiple pieces depending on how many machines you have. For example, if the key range is from 100000000000000000000 to 1ffffffffffffffffffff, and you split the range into two parts, it would look like:

Machine 1:

Machine 2:

"Don't worry about the end of the range, as some machines will find the key before reaching the end."

PD: You can use AI to create a Python tool that splits the hex range. ;)

Whenever I see a post going like "splitting the range is a good idea and not an issue at all" after all the uncountable and obvious proofs to the contrary, I do 50 pushups, to compensate for the 41% extra steps required to solve the same problem in 2 ranges.

To solve the # 135 puzzle with RCKangaroo, it would take tens of thousands of years to use an RTX4090 for computation.

Mathematicians need to continue working hard to create algorithms that are better than the kangaroo algorithm in order to complete this task.

+/- 249934d

CUDA devices: 1, CUDA driver/runtime: 12.7/12.6
GPU 0: NVIDIA GeForce RTX 4090, 23.99 GB, 128 CUs, cap 8.9, PCI 1, L2 size: 73728 KB
Total GPUs for work: 1

MAIN MODE

Solving public key
X: 145D2611C823A396EF6712CE0F712F09B9B4F3135E3E0AA3230FB9B6D08D1E16
Y: 667A05E9A1BDD6F70142B66558BD12CE2C0F9CBC7001B20C8A6A109C80DC5330
Offset: 0000000000000000000000000000004000000000000000000000000000000000

Solving point: Range 134 bits, DP 16, start...
SOTA method, estimated ops: 2^67.202, RAM for DPs: 96468992.188 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 3292808260.267.
GPU 0: allocated 4437 MB, 786432 kangaroos.
GPUs started...
MAIN: Speed: 7859 MKeys/s, Err: 0, DPs: 1154K/2589569785738K, Time: 0d:00h:00m, Est: 249934d:16h:16m
MAIN: Speed: 7822 MKeys/s, Err: 0, DPs: 2359K/2589569785738K, Time: 0d:00h:00m, Est: 251116d:22h:21m
MAIN: Speed: 7822 MKeys/s, Err: 0, DPs: 3563K/2589569785738K, Time: 0d:00h:00m, Est: 251116d:22h:21m

If one RTX4090 card can do it in +/- 249934 days (68 years). Then eighty RTX4090 cards can do it i in less than a year.

if will be not one 130, but 2^45 in 2^90 how long it take ?

Who taught you mathematics?
249934 days=684 years

The 135 remains technically feasible with very large resources like that used by retiredcoder (400 GPU 4090 if he is telling the truth) and with a very well optimized RCKangaroo, depending on the position of the privateKey it would take between 0 and 1.2 years to resolve it. Depending on the price of bitcoin, the operation can be profitable but it must be possible to do so with such a resource. for 99% of people who try to solve it it is useless to do so unless they believe in phenomenal luck like the lottery it will be a waste of money and time

with this math, we need +400 4090 GPU to solve the 135 in 1.7 years or something like this, and in half a year but we need to use +1000 GPU :o  ;D
if I'm not wrong this is a hallucination  :D


in this situation, as the Retired Coder tells us one GPU costs between 0.20 to 0.30 per hour, this may cost 180$ month > 2160$ year

so 400 card cost (864000$)
1000 cost (2160000$)

if I'm not wrong

I think I will still laugh for the next year  ;D :D

Stop posting AI BS here, I will remove it every time.

@RetiredCoder Maybe you can share networking and dp load/save options. Do you have any plan on it? 

I'm not going to create serious ready-to-use open-source solution for cracking really high ranges. You should do it by yourself if you want to crack #135 and get a lot of money :)
But I'm going to update RCKangaroo to support old cards better (+higher speed) when I have time.

It would actually be great if 20xx GPUs could be supported!  And if in addition a speed optimization for these 20xx and 30xx series is made great . Thank you  :)

Yes, new version will support these cards and will be faster by at least 20-30% for these cards.

Hi! pretty cool tool :-)
Do you plan to implement if possible to have
 - a "continue" option in case the gpu stop and you want to continue from where is stopped ?
 - a "multiple pubkey" option like an input file with a list of pubkey ?

thanks and have a good one

I must admit you used some really clever tricks to make maximum usage of shared memory (L1) and L2 caches. I'm still trying to figure out the way you keep track of the jump distances using the shared memory instead of updating them using L2.

After adapting my own kernel to load/store stuff using L2 (instead of only once, before and after all the jumps) I reached 9.7 GK/s on RTX 4090 (64 jump points, DP 32), which was an increase of 75% in speed, and I haven't even tried to do micro-optimizations on it, like before. So I guess this was the missing lack of knowledge to be able go beyond the advertised 8+ GK/s stated by others around here, after trying every possible advanced optimizations I could think of to speed things up.

So did you start work on solving 135?

1. Maybe.
2. No, it's bad idea.


Yes, 10G for 4090 is ok.
And then one day you will understand that the only way to improve it further - use symmetry and get sqrt(2) boost. Yes you will lose some speed but total improvement worth it.
From RCKangaroo readme:

Fastest ECDLP solvers will always use SOTA method, as it's 1.39 times faster and requires less memory for DPs compared to the best 3-way kangaroos with K=1.6. Even if you already have a faster implementation of kangaroo jumps, incorporating SOTA method will improve it further. While adding the necessary loop-handling code will cause you to lose about 5–15% of your current speed, the SOTA method itself will provide a 39% performance increase. Overall, this translates to roughly a 25% net improvement, which should not be ignored if your goal is to build a truly fast solver.

The comparison between SOTA and 3-kangaroo you made is only relevant if the jumping device (RTX 4090 in your case) allows the tradeoffs you mention, in order for the tradeoffs to end up with a more efficient solver.

Let me give you an example.

RTX 3050 or other cards that have a low amount of L2 memory.

Your RCKangaroo is much slower than a non-cycling jumper, like 50% slower, because the overhead of handling the cycles is clearly visible (no L2 memory to hide computing bounds). It is even worse when the kangaroos are stored in global memory (since L2 is too small to cache them).

So the winner in these cases is a normal (optimized) 3-kangaroo algorithm.

But because RTX 4090 has around 75 MB of L2 cache, the lower speed is hidden because it is offset by the fast L2 cache. In other words, the raw speed becomes irrelevant, because now the speed bound is limited by the memory latency of L2, not by the raw computing cores.

In this case you can do pretty much whatever you want in the kernel and go crazy with whatever algorithm you want to use, like your SOTA method. Because it won't affect the speed too much.

What I want to say is: in the future you can't really know if new GPUs will have the same tradeoff benefit, so there is no guarantee that the computing size of a CUDA device won't have a greater influence on speed when compared to the cache latency and size of L2 memory.

You are wrong, it's not related to L2, loop handling slowdown for new and old cards is similar. But I won't argue.
I will release new version with 20-35% speedup for old cards soon. Not much optimized, but anyway faster than now.

If X1, Y1, X2, Y2, Z, and the jump distance are all in registers, you get maximum speed. You can never get faster than that. But you can only do it with a very small number of kangaroos, like up to 6 or 7 kangaroos, depending on how well you use the registers.

Next wall is when L1 + shared memory gets used. This is the next maximum possible speed, but lower speed per kangaroo then above. You can add maybe 1 kangaroo more this way, because this cache is really small (128 KB per SM).

Third wall is using L2 cache. So, much lower speed / kangaroo, even though the overall throughput is greater. This scales up better only if L2 is really big.

This is why: when L2 cache is small, then loading and storing X1 Y1 in/out of L2 before and after each jump is much too slow, because they will actually pass into deice global memory. So, if L2 is small, the only logical (and faster) option is to only load and store X1 Y1 before all the jumps, and store them back after all the jumps.

Adding cycle handling in this case reduces the number of allowed X1 Y1 = less kangaroos = lower speed.

I have like seven different kernel versions that test these different strategies for when and how data is being loaded into/to different memory levels, so I'm pretty sure about the differences in each strategy.

v2.0 (Windows/Linux):
https://github.com/RetiredC/RCKangaroo

- added support for 30xx, 20xx and 1xxx cards.
- some minor changes.

Speed:
4090 - 7.9GKeys/s.
3090 - 4.1GKeys/s.
2080Ti - 2.9GKeys/s.

Please report speed for other cards, for old cards speedup is up to 40%.

Thanks!
1660Super 930-948Mkey/s

NVIDIA GeForce GTX 1660 Ti "Laptop" 975 MKeys/s

Thank you so much for your incredible contribution to this tool!

I believe it’s already fantastic, but there’s just one feature that could make it truly perfect: the addition of an --end parameter.

Here’s an example to illustrate what I mean:

Puzzle 135: 40000000000000000000000000000000000000:7fffffffffffffffffffffffffffffff

I’d like to try my luck and search within a specific range, such as:
--start 52000000000000000000000000000000000000
--end 5affffffffffffffffffffffffffffff

The inclusion of an --end parameter would be a game-changer for scenarios like this.

Thanks in advance for your consideration

I request that CPU support be added. We are doing some studies and research, using only GPU is not enough. Sometimes we need to use only CPU. Please add CPU support.

NVIDIA GeForce RTX 3060, 11.76 GB, 28 CUs, cap 8.6, PCI 40, L2 size: 2304 KB
Speed: 1.5 GKeys/s

NVIDIA GeForce GTX 1660 SUPER, 5.80 GB, 22 CUs, cap 7.5, PCI 39, L2 size: 1536 KB
Speed: 1.1 GKeys/s

2x GTX 1660 SUPER + 1x RTX 3060 (-gpu "012")
Speed: 3.7 GKeys/s

22m to solve key 85bit  ::)

Thanks man!  ;D

  Speed: 2310 MKeys/s - 3070
Well done! Can I ask you a question about kangaroos? in private messages.

so that the program ends after a complete search.

If by pure chance Puzzle 135 is in the range I chose, it will end with the foundkey, otherwise it will end with nothing found :D

I wish you good luck! in general, yes, it is convenient that after passing a certain period of values, the program completes its work.

In this case, the program stores dp in RAM and you don't have enough for your entire range. if you add the completion of the process by iterating over a certain area (which RAM allows), you can exclude it in further searches.

@RetiredCoder
Thank you for making the 'old card' version.
Compiled first go, no errors, works on my old GTX1060 @ 188MKeys/sec

Managed to crack a 74-bit private key in less than a minute using one 3060 Ti!

Now, the real question: Is it worth running this occasionally to attempt a 135-bit private key?
Would it still work purely on sequence, or is there a way to incorporate randomness to test our luck with this blazing performance?

Looking forward to hearing your reply!

There seems to be a bug for 20xx cards, nothing is found
For small beaches as well as larger ones it turns without finding anything.
I take as examples the beach mentioned by Zahid888



Identical problem searching for #76 including varying the DP to 14 ca finds nothing. Au bout de 5 min cela fini par mentionner "Collision Error"



Avec DP 14 same problem and same message


Would it be possible to fix the  bug?
For the moment this version does not work for 20xx series cards

Yes, it's a bug, but not in the software.
You should check parameters, -start 40000000000000000000 is incorrect for puzzle #75, must be -start 4000000000000000000

you were right the bug was me in the command line  ;D
It works very well. Thanks for the clarification



For this same pubkey 03FAC615733B5B83682DBBCD4539A8DA3E90085D43FAC8B3B54E43B92DDAAB14B8 75 bit space, I compared with the latest version of JLP kangaroo2.2



kangaroo 10m19s  
RCKangaroo 2m40s
On my RTX 2070 RCKangaroo is X4 faster than Kangaroo from JLP


RCKangaroo speed for other GPUs
4090 - 7.9GKeys/s.
4080Super - 5.2GKeys/s.
3090 - 4.1GKeys/s.
2080Ti - 2.9GKeys/s.
3070Ti - 2.6GKeys/s.
4060Ti - 2.3GKeys/s.
3070 - 2.3GKeys/s.
4070 - 1.6Gkeys/s.
3060 - 1.5GKeys/s.
2070 - 1.5GKeys/s.
4060 - 1.1Gkeys/s.
1660 Ti - 1.15GKeys/s.
1660Super - 930-948Mkey/s
A3000 - 954 MKeys/s

Ok, in next version I will add support for precomputed DB to solve ranges like 80bit within seconds.

Hello, RetiredCoder,
First off, thanks for creating RCKangaroo. The performance works now quite impressively with K=1.15.
I wanted to ask if you could consider implementing the WorkSave feature present in Kangaroo 2.2.
Use Case:

- Long-running searches (>24 hours) - While running, saving progress in case of sudden shutdowns of the power/system
- Important for less stable systems when running on them Current Workaround:
- Tracking progress manually by oneself - Performing different searches in smaller pieces manner
- Higher risk of failure of the process and losing results, due to manual checks and working in broken shots. Although I realize this would complicate your code, I think being able to save and restore work is going to make RCKangaroo program so much more useful for running searches that last quite a long time.

Thank you!

Hi
I don't know how to start but all thanks to you RetiredCoder,


So i started to install the tool in my WSL using windows 11

Any way i thank i missed up badly will you please help me out
this is what i see

''
This software is free and open-source: https://github.com/RetiredC
It demonstrates fast GPU implementation of SOTA Kangaroo method for solving ECDLP
Linux version
CUDA devices: 1, CUDA driver/runtime: 12.6/12.0
GPU 0: NVIDIA GeForce RTX 4070 Laptop GPU, 8.00 GB, 36 CUs, cap 8.9, PCI 1, L2 size: 32768 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: 43.615.
GPU 0, cuSetGpuParams failed: no kernel image is available for execution on the device!
GPU 0 Prepare failed
GPUs started...
BENCH: Speed: 0 MKeys/s, Err: 1, DPs: 0K/9646K, Time: 0d:00h:00m, Est: 213503982334601d:07h:00m
BENCH: Speed: 0 MKeys/s, Err: 1, DPs: 0K/9646K, Time: 0d:00h:00m, Est: 213503982334601d:07h:00m
''

You can run it directly on Windows. Within this post, you will find all the relevant information about compiling on Windows.

i mange to fix it its running smooth now

MAIN: Speed: 1668 MKeys/s, Err: 0, DPs: 28768K/77175K, Time: 0d:00h:25m, Est: 0d:00h:50m

Can you make multypubkeys search  in parallel?

Thank you

could someone please explain to me what is the relationship between the jumps the kangaroos make or what is the nature of the jump exactly , how does the jumps are made and what makes us soo shore that when they collide on the same point that exact point have something to do with the scalar we are looking for , and from where does start the jumps is it from the interval of the known range of the scalar ?

First I would like to thank the RetiredCoder or (RC). Great work!!!

I'm trying to understand and analyze your code.

I carried out some tests with my 4090 and noticed that e.g. Bit 70 everything works perfectly!

Unfortunately, when I go to bit 130 it looks different, but I'm trying to figure out why there are problems here. Currently I have no idea what the reason(s) are. I'll take a look at the code in a few days. Maybe someone here has the same experiences.

Thanks again :-)

Hi,

Can you add end range to the code? I want to search for narrower ranges.

RCKangaroo v3.0:

- added "-tames" and "-max" options.
- fixed some bugs.

Hello, thank you very much for your work! Sir, could you also add the -end function to indicate the end of a range? I think many people here would like to break a large range into small ones and go through it)

Why don't you want to use "-range" for that?

Because I am searching by dividing the whole range into smaller ranges. Even though I used -range option, it does not terminate and continues searching. However, the -max option in V3 can solve this problem. I haven't tried it yet, but I will try, thanks.

Amazing thanks a lot for investing so much of your time in this project so that we can enjoy it!!

Very interesting this update, for fun I did the test with a precalculation of the points on #75 bit with -max 3 this already requires 350 Mo of free space.
how many Go available requires for example the precalculation of a 100bit space with -max 10 ?

I did a 85bit -max10 the Generation took 4 hours and 35GB of space

ok thank you for your answer I'm going to test a 90 in -max 5 to see but I'm not sure I'll have enough space we'll see

When app starts it displays estimated RAM for DPs based on -range and -dp options, multiply it by -max option to get required RAM (roughly).
Or download latest sources and compile them, I added max RAM size calculation.

I must not have understood correctly but in this case the ram displayed is indeed 0.315GB and -max 3 it should take 900 MB or even 1 GB but it took 352 MB exactly 352055KB, why?  ???

Because there is some fixed RAM size required to store table itself (about 200MB):

yes it is perfectly clear now ok thank you and congratulations again for your work and sharing it is impressive ! I hope you find #135, you deserve it sincerely ;)

I had time again and was able to continue taking tests.
I think there is a bug in the tool when solving large bit areas.

I was able to solve bits 70, 75, and 80 without any problems, but from 85 onwards none of the puzzles that had already been solved. For example, I changed values ​​at Bit 85 start, etc. but it was never found. An example, after that i stop -> Err: 0, DPs: 98481K/77175K, Time: 0d:00h:13m/0d:00h:10m

Don't think I'm making a mistake because it solved bit 70, 75, 80. If I had time again I would look at it more intensively, I'm not sure but maybe there is an overflow, .....
Can someone else please test this too??

Please, it is better to send the command line you are / were using. That way someone can take a better look at everything. Maybe you forgot to use the correct subtract amount, wrong key, etc. Could be anything, could be nothing, but it's the first thing to look at.

It takes a lot of time to confirm K at higher ranges.
For v3.0 I did tests for "-range 89 -dp 22": I started 12 instances of RCKangaroo on 12 4090 (one GPU per one instance to get larger path for kangaroos), solved 133 points in total with average K=1.21.
For range 100 I did the same and just waited for two points solved so at least it can solve it, though I cannot confirm exact K because it would take a couple of weeks.

---

One more piece of science!  :D
Everybody knows that when we calculate "NextPoint = PreviousPoint + JumpPoint", we can also quickly calculate "PreviousPoint - JumpPoint" because the inversion is the same.
Therefore, if the inversion calculation takes a lot of time, this second point is cheap for us, and we can use it to improve K.
I updated Part #1: Added "SOTA+" method with K = 1.02.

[moderator's note: consecutive posts merged]

The actual DPs (1176754K) far exceed the expected DPs (109142K), meaning the solver is generating significantly more DPs than anticipated.
The more i lower the DP bits from 16 the worse it gets, it does not generate a single Solved Point.

Anyone ?

For solving points with saved tames you must use same "-range" and "-dp" values that you used for tames generation.

Thanks, i must had it messed up!

This was something already known and smart guys here already used this knowledge for example in faster vanity searches and even for BSGS. arulbero posted this trick many years ago and it is also in the literature. I used the P + Q and P - Q same inverse speedup even for Python scripts, however there is one big problem here: if P - Q is a DP then this only marginally improves the collision probability lower and lower as DP value grows, because the walk does not continue from P - Q, it continues from P + Q. It is what I call a "weak DP". For low DPs it indeed brings what you call "K" down a lot, or more precisely, you get an increase in DP throughput with the same "K" if not a larger "K".

Do you remember a few months ago when you said you don't believe I reached a K of ~1.0 and it was most likely a bug in my code? Well, do you still believe this today? :)

I'm not talking about the trick with cheap second point, I mentioned that everybody knows about it. But noone could use this trick to improve K at DP>0 and you explained why. But I can and I demonstrated it. If you have any links to sources or papers that do it (improve K at any DP>0) - let me know!


Yes I'm still sure that your non-looping method with K=1.0 (at DP>0) does not exist  ;D

Can you explain how that is, without having to be a C++ expert? Once you have P - Q you are at a point that is basically the end of a line, how does that help you further (unless maybe you save it and walk further, but this grows your herd size by 2x of course at each step). The cheap point is still one extra semi-addition (sort of), are you sure you're counting it correctly? :) In my tests, as DP grows, K grows as well, but less than double, so overall it's an improvement. But then again, it depends what you are counting.


Remains to be seen :) It's debatable what K means anymore once the inner guts of adding points start to become intertwined and you only need parts of the final result. We'd need the hyperelliptic equations style of notation to get the complexity (how many field ops we need grouped by op type).

I don't check cheap points for DP, it's senseless. Instead, I choose cheap point as next point if it has even X. So I use it for kang walking and prefer even X when possible, it helps kangs to collide faster.
Here is the related code, since it's open-source you can easily compile and check everything by yourself:


You can use this trick only for methods that use symmetry.
It works, I know why it works, and I never saw this trick before.

Here is for Bit 85, i can´t find the key:

./rckangaroo -dp 16 -range 84 -start 1000000000000000000000  -pubkey 0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a
./rckangaroo -dp 16 -range 84 -start 11720c4f018d51b8000000  -pubkey 0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a


For Bit 70 i always find the key, doesn´t matter which -start i use (only two see below):

./rckangaroo -dp 16 -range 69 -start 200000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 100000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 300000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 340000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 349000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 349B84B6431A6C4EF0 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483

with this -start offset can´t find the key:
./rckangaroo -dp 16 -range 69 -start 0 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 349B84B6431A6C4EF1 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483

I have solved #85, using -range 85. Try it and see if you find the key.

./rckangaroo -dp 16 -range 85 -start 1000000000000000000000 -pubkey 0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a

I am running it with -range 84 to see if it solves. Will update.

Edit:

Spoke to soon lol. Here is my result using your command line:


So since I solved at both 85 and 84 range, I am not sure what the problem is/was on your end. Your command line args are fine.

Can you explain what you are referring to as "K"? Because any algorithmician can tell you that once you do 1.5 times more operations / loop (such as your "cheap point" even X preference with a 50% increase in ops count) and you ignore the extra .5 steps, then this "K" of yours is not really useful for anything, no one should care about how many iterations your algorithm does, but the number of group (or field) operations.

Cheap point does not cost 0.5 op, practically it costs max 15-20% of op (it's just additional 1 MUL + 1 SQR and these additional calculations happen only in 50% of jumps), but if you don't use groups in inversions (or group size is small), it costs much less, so it's not a good idea to count cheap point as 1 op. That's why in some cases using cheap point makes the whole algorithm faster. For example, you can compile my "Kang1" project and press "SOTA" button and then "SOTA+" button to see about 8% speedup.

I still study your code, especially the gpu part, which gives me a lot to learn.
I think JLP applied this trick in his BSGS/kangaroo.
https://github.com/JeanLucPons/BSGS/blob/master/BSGS.cpp#L347

Yes, he did it for BSGS, and now I’ve figured out how to apply it to Kangaroo.

I can't follow up on your logic. A key is still a key, no matter what optimizations are used to compute it or whether it was 90% easier to compute it or not. By your logic, in order to compare efficiency, we should also reduce (divide by 1.5 2.0) the reported complexity of any other implementations that use this "trick", but count the number of computed keys (not the number of iterations). For example BSGS where this trick does wonders. Or maybe a kangaroo with weak DPs. Is it fair?

But it's your software so do as you wish, but please try to not be misleading at the abstract level. The number of iterations where you do whatever you want is not at all the same thing as the number of computed X & Y.

If I were you I would:
- count the number of ops (so complexity increases correctly, yes I know you would hate this)
- use the cheap point to increase throughput (keys/s)

which would result in a worse complexity (more keys), but a faster speed (more keys / s) due to implementation-specific optimizations.

But again, do as you wish.

If after a jump I get second (cheap) point for almost free, I can calc K without this point.
Yes it's not 100% correct, but it's definitely better than counting it as 1op, showing almost twice speed at almost twice worse K.
But of course this assumption must be mentioned in the method description and I do it.
Also, it depends on a point of view: for example, if cheap point is used for vanity addresses generation, this point should be counted because it's used as a normal point. But for kangaroo jumps - this point should not be counted because only one point is used for next jump and only one point is calculated completely (both X and Y).

I took a closer look at JLP's code, and kangaroo's code does not have this.
This PreviousPoint - JumpPoint jump is equivalent to PreviousPoint jumping JumpPoint backwards. ;D

about bots, yes bots  can f y.... and blockchain.com wallet too

https://github.com/phrutis/Bitcoin_Hack

Public keys were already known.
Also, best of luck to bots cracking >100-bit ranges before the block is confirmed  ;D

Okay you think they can´t cracking over 100 bit ranges? I read that someone stole bit 66 from the finder, thats only possible because is < 100 bit?

Hey atom13,

You need to learn a bit of how a Bitcoin Address is generated and in which ranges are we talking.

Generate private key:
1. Private key is 256 random bits.
2. Prepend version number.
3. Append compression flag.
4. Append checksum. Checksum is the first 4 bytes of double sha256 hash of whatever is being checkedsum'ed.
5. Base58 encoded data is easier to read and manage.

Generate public key:
6. Multiply the private key by the elliptic curve generator point to get the public key. The public key is a point on the elliptic curve and has x and y coordinates.
7. Use parity of y coordinate and full x coordinate to represent the public key.
8. Hash public key twice. This obfuscates the public key and shortens it.
9. Prepend version (version number is different than in step 2)
10. Append checksum (same method as step 4)
11. After another base58 encoding, we have our public address

This page will help you a bit to understand the process behind it: https://royalforkblog.github.io/2014/08/11/graphical-address-generator/

The problem with bots is in the ranges where it is fast to calculate the private key given a public key (not the same as a public address).

Moreover, puzzles 135, 140, 145, 150, 155 and 160 have the public key known, but nobody has taken the private key. That is due to the range they are in (and the high cost to extract it).

The problem is in puzzles 67, 68, ... where the public key is not yet available (but the public address is). The moment you send the transaction to send Bitcoin from that puzzle to a wallet of yours is when you can get the public key (it is in Mempool).

Public keys can be found inside the ScriptPubKey or ScriptSig of raw transactions.

I hope this helps you a bit to understand the process behind it. If you have any questions, feel free to ask. I will be glad to help you.

Been interested about this puzzle for more than a week now; unfortunately I don't have the gear required (I do own two desktops, one i9 14900k with an RTX 2060 and an RTX 2080 and another with i9 10900k with an RTX 3050) and the speeds I got are very good, but won't do much.

Thank you a lot for the work you are doing, I do wonder if you had implemented or found a way to implement this new method? https://arxiv.org/html/2409.08784v1

Why would anyone get past the title of that paper? Its title is "How to cook potatoes better", while what we are interested in here is "how to make the perfect cheesecake". Elliptic curves DLP is not a DLP over a finite prime field, it's over curve points defined over a finite prime field. Notice the difference.

Updated Part #1, v1.4:

- added option to make K better at the range edges (for SOTA and SOTA+) - define BETTER_EDGE_K.
- added option to see interval stats - define INTERVAL_STATS.
- fixed some bugs.

First, Happy New Year to everybody!

RetiredCoder thank you for sharing your work!
I had commented on your repo with a pdf that may be useful to speedup the code. Also, I asked you kindly to contact me to my email but you didn't, which is a bit sad, but it's up to you.

Regarding the RCKangaroo version I have three questions:

1) does it use any CPU for DPs?
I ask because I use a rented GPU and I am not sure if I can get a powerful CPU from this provider

2) can you explain a bit the ideal -dp value for small and high puzzles and the impact on each case?

3) i rent an RTX 4090 but no matter the options I use, it doesn't utilize the full RAM of the GPU...why is that? is it from my side or a bug in your updated version?

Thanks

Hi tmar777,

You should learn a bit about how programming works with CUDA (Compute Unified Device Architecture) and how RetiredCoder has implemented it in his code.

In CUDA, you work with the following:
* Kernel: name of a function run by CUDA on the GPU.
* Thread: CUDA will run many threads in parallel on the GPU. Each thread executes the kernel.
* Blocks: Threads are grouped into blocks, a programming abstraction. Currently a thread block can contain up to 1024 threads.
* Grid: contains thread blocks.

If we focus on the software that RetiredCoder has shared on GitHub (https://github.com/RetiredC/RCKangaroo):

There are currently 4 Kernels:
* KernelGen: Runs once at the beginning this kernel calculates start points of kangs
* KernelA: this kernel performs main jumps
* KernelB: this kernel counts distances and detects loops Size>2
* KernelC: this kernel performs single jump3 for looped kangs

Then KernelA, KernelB and KernelC are run in a loop where if we ignore KernelGen (since it is only run once at the start) in percentages of time it would be something like this:
* KernelA: 90%
* KernelB: 4%
* KernelC: 1%

So, you have to understand that the executable that is run will run on the CPU and then in CUDA the Kernels will run on the GPU.

Answering your questions:
1) This problem does NOT require much CPU. This problem is computationally intensive on the GPU. Imagine that it needed 400x RTX 4090 to be able to complete the 129-bit puzzle.
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.

3) When running any software, these are the metrics (there are more, but these could be the main ones) that one should look at:
* CPU usage
* Disk usage (disk I/O: input/output operations).
* RAM usage

With this you have a view of what is happening with the application you are running. In this case, and as I already told you, it is an application that uses CUDA, that is, it makes use of the GPU, therefore, you should analyze:
* GPU index (starts from 0)
* GPU name
* GPU temperature
* GPU memory usage (Used / Total). Here you can see how different memories are used
* Using CUDA Cores and SMs

You can use `nvidia-smi` or other tools like:
* https://github.com/XuehaiPan/nvitop
* https://github.com/Syllo/nvtop
* NVIDIA Nsight Compute (https://developer.nvidia.com/nsight-compute)

To sum up: the important thing is not the RAM or memory usage that the GPU uses, but the amount of work that it is processing in the kernels.

I hope it has helped you and if you have any questions, I am here to help you.

As the above post explained it in too many words, using the GPU memory is not beneficial at all. The highest performance occurs when 0 (zero) bytes of memory are being used. The highest throughput is a fine balance between the GPU clock (cycles/s), the kernel implementation, the launched grid size, and the size of the on-chip registers, L1 cache, and L2 cache. This balance greatly differs from one GPU to another, but in all cases, filling up the GPU memory with a gazillion kangaroos is a very bad idea, as it slows down the computations and also greatly increases the DP overhead, for no good reason.

In essence, the less kangaroos, the better.

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

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

Updated Part #1, v1.6:

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

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

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


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


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  :D
Some people don´t understand how hard is this to crack

This thread is a great opportunity to learn how Bitcoin works and use Kangaroos to solve ECDLP but in the end people are only interested in asking for money.

I am doing a project based on yours, RetiredCoder, where I have created the following:
- Lib: Where all the logic is and it is a library available to different executables.
- Worker: Connect to a Dpserver, receives a job and is responsible for sending points to the dpserver
- Dpserver: Receives the points and processes them.

Additionally I have created the following:
- GitHub Actions to validate that it can be compiled on Windows/Ubuntu
- Added CMake to generate the solution on Windows/Ubuntu
- Unit and performance tests to validate different solutions.

Maybe in a few months I will share it with the community, in the meantime I will continue learning since it seems like a great opportunity.

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>

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

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

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.

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

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.


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.

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.

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

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

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

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.

You say that is puzzle 22 but you are using a range size of 74. Try this:

RCKangaroo.exe -dp 16 -range 21 -start 100000 -pubkey 023ed96b524db5ff4fe007ce730366052b7c511dc566227d929070b9ce917abb43

See if that speeds it up for you.

This do not work.
I get an error: error: invalid value for -range option

With puzzle 22 I mean the 22. from this side: https://privatekeys.pw/puzzles/bitcoin-puzzle-tx

I thoght that everyone is talking about it, because RetiredCoder solves some for the puzzles from there, 120 for exsample.

And the other point is still, where to get the public key. Because for 67 we only have the Bitcoin adress: 1BY8GQbnueYofwSuFAT3USAhGjPrkxDdW9 and the public hash 160: 739437bb3dd6d1983e66629c5f08c70e52769371
see also: https://privatekeys.pw/address/bitcoin/1BY8GQbnueYofwSuFAT3USAhGjPrkxDdW9

Per the source:


So it has to be at least 32.

As far as wanting to know the public key for 67...don't we all, don't we all.

@RetiredCoder

Maybe you can fix these warnings in the next update

Could you please explain why the code doesn't work when the generator point changes? I'm very interested in experimenting with different generators. Can you assist me with this?

Are you saying that you are changing the value of Generator (G) and it is not working?

https://github.com/RetiredC/RCKangaroo/blob/main/Ec.cpp#L113-L114

Bitcoin uses secp256k1, so the G should be what is defined to be: https://en.bitcoin.it/wiki/Secp256k1

G point is the following:
(compressed form): 0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
(uncompressed form): 0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C 4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

Not work for pubkey what not divides to G, for exp pubkey 5 and basepoint 2

For example, I would like to use N/2x as the Generator base. so, Gx=(N/2)x ,2P= Gx,  3P=.....,and so on.

I created a Discord Server just in case someone needs more in depth help.

There is a channel to share files and scripts!

https://discord.gg/eEQbQnnRaY (https://discord.gg/eEQbQnnRaY)

Good afternoon! when the program starts, the number of kangaroos is displayed, 1548806? does each scan its segment sequentially at a rate of 2.3 million per second? Did you get it right, or was there a mistake somewhere?

What about little bit of clues 😬@RetiredCoder

I wasn't sure if you reran this or not or figured out what the issue was.
I ran a 100 bit test (99 bits) and it did find the key:


So we know it works. But why didn't it work for you? DP size?

Hai Wander, did you modify or change the code in your test?

I changed how the program receives its info, and some cosmetic stuff.

Basically, you enter a start and end range, start:end, the program calculates the difference and from that, the bit size of the range. Since we entered the start range, this is passed as the old offset flag.
So all of that is automatic now.

./rckangaroo -dp 24 -range 8000000000000000000000000:fffffffffffffFFFFFFFFFFFF -pubkey 024ECC524F1F53F525A7224364A4290BA97D72298D885FCF93B6E139E802B421B9

is all you have to enter now.

And I got rid of the repeating lines and just kept them on a single line. And I added a start/finish timer.

So while I did tweak a few things, I did not touch the actual Kangaroo parts of the program; no math or jumps or any of that. This way I could test if the program had issues or was user error, maybe the cause.

Ok thank for the explaining, so far what maximum bits did you test and success?

Hypotetical scenario: a RTX 5090 can do at least 13.0 G jumps/s at DP 32. Are there plans to improve RCKangaroo or is 9.3 Gk/s still a "very good" speed, compared to an optimized version?

I am disappointed in the 5090 so far, I only got at most a 20% speed up compared to 4090.

In general, I'm not interested in further support/improvements of RCKangaroo, but since it's open-source, someone else can do it.
My original goal was to share my method of solving ECDLP with best K.
I did it, but people (and you too btw) said that K is calculated incorrectly, also my method will not work in practice because loops cannot be handled properly and my method worked for puzzles only because I burned tons of money and any method is good in this case. So I also created RCKangaroo for 4090 to demonstrate that loops can be handled efficiently and K=1.15 is real.
Then people tried to run it on old cards so I had to support old cards too (and also to prove that loops can be handled efficiently on any GPU).
Right now RCKangaroo uses the fastest method for solving ECDLP ever, and also it's the fastest open-source GPU solver, so I think it's still good enough for open-source.
Yes sometimes you say that you have magic non-looping method with K=1 (DP>0) or that you have faster jumps like 13Gkeys/s, but it's just words, nobody can test or use it. Sometimes here I see funny messages like "I have broken EC" or "I solved all puzzles"  ;D
At this moment, I have demonstrated and proved everything I want and now I'm busy with another interesting project.

Thank you for taking time to respond!

While I do admire that you had the skills and resources to break three ECDLP problems in a row, judging by your expertise you know very well that everything is a tradeoff when it comes to programming. I still stand by all my previous comments regarding this: cycle handling slows down the jumps. Another way to view this is: even with a very fast optimized cycle-handling kernel such as yours (much faster than some whatever JLP reference fork), it can be made to run faster if we trade the resources for cycle handling to enabling more jumps. The question at the end of the day is: from what point on is it worth it to either have low "K" with slow jumps, or a higher "K" with faster jumps. And yes, I did manage to reach 13.4 G/s on a RTX 5090 without even compiling natively to ccap 12.0, so the question is even more interesting now.

I was more interested about one of your older replies, regarding the fact that an optimized version is not even twice as fast as RCKang, which hinted that maybe somehow you managed to reach 14 Go/s on a RTX 4090, which would have been fascinating, considering that the public version can't reach 8 G/s.

Currently I have about 12.8GKeys/s on 4090. 5090 is a shame, I skip it and wait for next generation.
Perhaps I will make all my sources public when #135 is solved, though I'm not sure, people are not interested in what I do, also I see zero good discussions on this forum about EC, so better I will spend my time for more interesting things  :D

Yes, there are surely many people intrigued by your code; it's just that not all of us have thousands of dollars to explore or buy a high-end PC. What's more unfortunate is that those who do have the means don't offer anything just theories backed by zero code, which is a vague and empty argument. I admit that I plan to include in your final version of Rckangaroo the different kangaroo methods to verify if SOTA is the main factor or if it is the optimization of CUDA code.

Are you blind? ???
All my ideas I published here are proved by sources so everyone can check and confirm them on CPU:
https://github.com/RetiredC/Kang-1 (https://github.com/RetiredC/Kang-1)
https://github.com/RetiredC/Kang-2 (https://github.com/RetiredC/Kang-2)

RCKangaroo is just a proof that these ideas can be implemented efficiently on GPUs as well.

Yes, I saw them but they are partially implemented. Your approach was always the SOTA (state-of-the-art) method, so it's not an impartial environment, which is what I'm referring to. The final Rckangaroo should be able to compare all methods equitably with all its advantages; that would be a fair and rigorous test.

Part #1 demonstrates full implementation of FIVE methods. So you can compare SOTA with classic methods. Easily.
I have no idea what else you need, if you want to implement all these methods in RCKangaroo for some reason - no problem, it's up to you how to spend your time  ;D
But your statement that I have only theories with zero code... awesome  :-\

I wasn't referring to you when I mentioned 'theories with zero code'; I'm talking about those who give opinions without having contributed any code, commit, or fork, saying 'this would be more efficient.' And yes, I just want to test your final version with all the methods and see it for myself. Rest assured, if the SOTA (state-of-the-art) method is better, I will say it. The truth cannot be hidden.

Geez... so you have a software that is marked all over the place as "Proof of Concept".

Then the author admits himself that the speed of his private optimized version is at least 50% faster than the public PoC.

And somehow the people that have "theories with zero code" who state that the speed can be much faster and the program can be more efficient, are called bullshitters.

OK. So this would mean that the author himself is a bullshitter, or not? Because he doesn't give out his optimized version? If he himself does not do that, who on their right mind would do that instead? It's like giving out a better Tesla for free to everyone, just because. Geez...

I want to clarify again: it's not my goal to publish the fastest version of ECDLP solver I have, it's not RCKangaroo.
My goal is to share the best kangaroo method for solving ECDLP with proofs on CPU so you can learn/use it. And I have done it.
RCKangaroo is a "Proof of Concept" of SOTA method for GPU (however, it's fastest in public) and I give it for free with sources so you can use and improve it.
If someone thinks that I must do even more and publish some ultimate software for cracking #135 - it's funny :D

---

#135 takes about 5.6 more calculations than #130, so I think #135 is the last high puzzle that will be solved in this decade.


About zero code, may be people mean this your post where you promise to show something? It's ok that you changed your mind :)

---

Ok, let's keep all our achievements secret, it will be a great progress for science ;D
Take care, I will come back when something interesting happens, for example, if someone publishes a method with K lower than mine.

[moderator's note: consecutive posts merged]

Deadline missed, health is more important. Also, I'll never actually share the code that allows for the speed I mentioned (it is the real speed). It is a CUDA binary file (precompiled in advance) loaded dynamically, optimized for the specific GPU it runs on. This is a safe way to share a CUDA kernel without compromising personal IP, and it has zero security issues (a CUDA binary can't do shit except run assembler instructions on the GPU). But since the kangaroos are computed correctly and verified at the end of the jump loop, and there is a steady rate of DPs, it proves 100% that the speed is correct, because the kangaroos landed where they were supposed to, which can't be computed in advance, there is no magic shortcut to compute the final landing spot, unless they each do the entire number of jumps.

But I feel you when people are asking for full solutions, they would then want the software that manages hundreds / thousands of cloud GPU instances, and so on. Lazy people will never be happy.

Thanks for this quick and optimized Kangaroo program, it is the fastest.

Is it possible to have the "save work" option and "load work" from file like in JLP's Kangaroo?

Thanks

A friend left me his PC to reinstall Windows and other programs, and I took the opportunity to run some tests. My impression was that RcKangaroo, in terms of SOTA, is the best version of the various Kangaroo methods published to date.

I recommend RetiredCoder to write a formal paper on this method if he hasn't done so yet.

Hey RetiredCoder,

I'm the guy who broke 67. Trying to DM you but I can't as a newbie.
Can you please DM me ?

Thanks :)

Signature from bc1qfk357t8n045f8mwx672rx2re4pftm5gmjzdwq7 :
ICT+NVyqwPrXEel/+jHHAMttjPlU8a/P89SCu50oH1sHERdl6L3qtHK5A1RxMUwBvUCQx/xZChNH8xzeH/QkrUc=

I have reviewed your code, and I must say I am truly impressed. Your approach is fundamentally different from anything I have seen before. I am a developer myself, but your code seems more like the work of a mathematician, a physicist – or simply an extraordinary talent, a genius, or a scientist.

What impresses me the most is its efficiency: Despite my own optimization attempts, I have never been able to achieve 12.8 GKeys/s on an RTX 4090. And what astonishes me even more – I could not find any references to your method in existing literature or research.

May I ask how you came up with this remarkable approach?

Good Morning RetiredCoder:

I have been studying the puzzles for a year now.  I was able to comunicate with professor Teske and professor Galbraith, they both worked with professor Pollard, and pointed me in the right direction. I have some questions and some original ideas about the pollard methods. I would like to ask if you can give me some advice.

I believe the Pollard methods can be improved using this observations I have made:

The key to accelerate the Pollard method computations is to improve the efficiency of the inversion part.

Teske in her paper says it is ok to use 32 types of jumps to give enough randomness. What about using more jump types, let´s say 2**32 types of jumps? Then you select every jump by the first 32 bits of the X coordinate. You store the X and Y in a database, which index is the first 32 bits of X. Now the jump formula considers the 32 most significant bits of the actual point, and adds the corresponding point in the database, with the same 32 bits .

This has the advantage that X2-X1 for the inversion, can be selected to give a number of only 224 Bits instead of 256. When you calculate the batch inversion, let's say you make 400 inversions, you can multiply a 256 bit number times a 224 bit number for the partial product part.

I also have made an algorithm for batch inversion using instead a pairwise multiplication, where I think you could improve the efficiency a little bit more, because you will begin making 224 bit*224 bit multiplications. 

Does this make any sense? Will the big database search at every jump make the program slower vs the speedup of the multiplication of smaller numbers?

Thanks for your time.

Thanks. It was an interesting task  :)
SOTA method itself is based on classic 3-way and mirror methods with some adjustments about ranges for wilds and tames.
For loops I had to examine them carefully to find a good and fast way to handle them.


From my experience, 64 jumps are better than 32 by about 2%, so better use 64 when possible. For symmetry methods you need at least 256 jumps.
Your idea is to have 2^32 jumps, right? It will take 240GB of RAM, so not suitable for GPUs. The end, sorry.


Thanks. Last time I wrote such papers for my PhD degree many years ago and I definitely don't want to start it again, too boring and useless :D
I gave up science then, chose money  ;D
Now I do it only for fun.


Congrats. I don't use PM at all, write you ideas here if you want.

 :) Thank's for your answer.

I have other question:
I have studied bitcrack and kangaroo (From Jean-Luc Pons) in detail. In the Pollard method with only 2 heards, Pollard recommends using a jump formula of powers of 2. When I tried to understand the Van-Oorschot method of parallelization, I realized that if you double the amount of Kangaroos, you must double the jump size mean. This results in huge jumps for a big range and a big number of kangaroos if you use powers of 2. Do you recommend better selecting the jump size using random K's in a given interval?

Thanks

There are several ways to choose good jump sizes, I just use random sizes in some interval, check my sources for details. Also in my approach the average size of jumps does not depend on the number of kangs are used and it still works fine. There are not any known ways to improve K somehow by choosing jumps in some special way, all known good ways get same result, so it's not important what way you use.

I understand that you use a base magnitude for the jumps and add a random portion to make the jumps, in a different way for each of the 3 heards, I will study this in detail. I'm not able to find an implementation for batch inversion on your code, do you use batch inversion to speed up the computation of the inverses? I understand that in the Classic Pollard method, you can use this approach, computing the next point for a group kangaroo paths. This will make the cost for one inversion only 3 - 4 multiplications? Is that correct?

It seems you don't know how it works even after a year. The jump table is the same for all herds, otherwise it won't work.


For CPU code I don't use batch inversion because I tried to make the code as simple as possible. That code demonstrates various methods for ECDLP and loop handling, not optimizations.
For RCKangaroo I use batch inversion, check its CUDA sources.

Hello everyone, can you tell me how to run 135 puzzle on several machines? Something like a pool or hashtopolis server

The only place I've been able to find anyone publicly using Inverse Wild Herd is in this Python script here:

https://github.com/mikorist/Kangaroo-256-bit-python/blob/main/kangaroo.py

 Everyone else seems to be hiding how it works.  :)

Another conspiracy theory in the series?  ;D

I'm not sure. I know that Google search often brings me back to this forum. I also know that you have code you don't want to release publicly, or you release code as bait. Nothing specific which is the fastest.  :P

Maybe you are not watching carefully, I posted a Kangaroo python script that used the inverse herd since last July or August, and explained all the equations of why it's working, and why it brings down Kangaroo to 1.0 * sqrt(N) when DP = 0 :)

But TBH this is already known for many years, just maybe not many people bothered to apply it, since it's at most something like a 20% speed-up over the usual 2 kang method.

What would you do with the fastest Kangaroo program I have? To be fair, you still need 1,200 GPUs, even if kTimesG or RetiredCoder publicly release the fastest version.


Exactly.  ;D

To experiment and learn. I mean, it's impossible that you don't have a faster solution at least for the CPU.  ::)

And what is to be learned? Definitely nothing about the 3-kang algorithm itself, all of that is public already. Like nomachine said, one would still need many, many GPUs to find high-bit solutions, no matter how well an implementation is optimized.

The only curiosity one might have would be "why is it faster" or "how did RetiredCoder manage to pull off 12.8 Gk/s on a RTX 4090", which might end up just as a terrible headache reading low-level code, or an "oh", not a revolutionary breakthrough.

It's not about that. If you think that research without a 'real' (for you) use is impractical, you're wrong. Many of the technological advances we consider fundamental today started as theoretical ideas without an apparent practical application. We never know when something might be useful or if it will pave the way for something bigger. Perhaps in the context of current puzzles, it might not be enough without thousands of GPUs, but that doesn't detract from its merit, like the study of radio waves, someone studying rainbows and light, and another person who wanted to organize the elements in a table to make it more practical. If we all thought that way, we would still be sending carrier pigeons instead of using mobile phones.

Yes you are absolutely right, after one year of dreaming with babies, gigants and kangaroos, I understand that the jump table has to be the same for all herds  ;D.

For me is very interesting the way you see the kangaroo methods conceptually. There is one part that is the method itself were we try to make as little as possible point additions, the other part is "optimizations" were we try to make those point additions as fast as possible, and use parallel computing to increase the point output.

I understand why is so important the concept of "K", I have an intuition about this that i would like to ask if it is correct. The kangaroo method by itself as in only 2 kangaroos (Tame and Wild) would solve the discrete logarithm in only sqrt(range) steps (k = 1) if both kangaroos started at the same point. This is sqrt(range)/2 for each kangaroo. This is related with the birthday paradox. Wen you use the first method in your program, and the kangaroos are separated, there is an overhead, because the path before both kangaroos meet is wasted. This accounts for an additional K points, so this method will solve in 2K jumps on average. What I have not been able to understand is how the 3 kangaroo method works. You start with one tamed an 2 wilds, and place them in a different position. This makes the kangaroos meet faster on average.

There is also the concept that if you start the path in the origin, and jump to the right, is the same as jumping to the left, so you are actually making, 2 paths at once.
 
For the 3 kangaroo methods this are my questions:

1) Where the 3 kangaroos should be placed at the beginning?
2) The wild kangaroos travel 1/4 of the jumps each and the tamed 1/2 of the jumps?

Thanks

You know, this thread is a POC about something called SOTA+ method, not 3-kang. Usually in literature this is actually a Gaudry-Schost variant, because there cannot be a Kangaroo algorithm that actually goes side-ways, since cycles cannot be part of a Kangaroo algorithm, by definition.

You can read up on the actual 3 and 4 kangaroo algorithm in the original paper from 2012 by Pollard et. co, it's called "Computing discrete logarithms in an interval", maybe you will then notice some of your statements or questions don't make much sense. Also don't forget that 3-kang works on any generic group, and has a lower complexity for groups with fast inversion, like secp256k1. I'm not aware of any papers that take this into account. The rabbit hole is deep.

Thanks for your answer. Yes, I am trying to understand SOTA+, but I believe I have to learn all the methods in order to understand SOTA+.  This means in order to understand SOTA+, I should understand 2 kangaroos, then 3-4 kangaroos, then Mirror, and then SOTA, and SOTA+. Is this correct?


This means the 2-3-4 kangaroo algorithm makes 2-3-4 long paths, while Gaudry-Schost variant makes many smaller paths until a distinguished point is found. I see your point, a normal kangaroo method can't go sideways, as the "maximum excursion" would not allow for the kangaroo to travel very far before going in to a loop?

But in general terms:

Mirror is faster than 3 kangaroos because it calculates 2 "cheap" points in every jump instead of 1, and SOTA is faster than mirror because it computes 4 "cheap" points instead of 1?

The trick in SOTA+ is how to detect and then get out of the cycles in a way that the overhead is not to big?

Thanks

Mirror = takes advantage of group symmetry - you have both P and -P with the same X. If DP is on X and a DP is found, then you basically have two DPs found instead of one. Also this helps with more collisions.

What I'm trying to say, this is just something that's part of the group, it has nothing to do with any 2-kang or 3-kang algorithm itself, it works the same even for a brute-force algorithm (to halve the key space).

The cheap points have nothing to do with mirroring, or with 2-kang, 3-kang. It's simply reusing the (x1 - x2) field inverse to compute both P + Q and P - Q, where P can be anywhere on the curve.

RetiredCoder uses cheap points to selectively pick the next landing point, since somehow this helps - probably because it increases collision chances if visited points have a heavy bias on the lowest bit.

This doesn't make sense to me. Why would you need the same point in the database. I don't see how this is useful.

In general terms, first you bring the wild kangaroo to the (-N/2, N/2) range, and you are not sure if it landed on the positive side or the negative side of the range, so you need a way to calculate the next jump, taking in to consideration both possibilities but having the same resulting landing point. This means you begin in one point, calculate the negative (-Y) at no cost and then you choose the one with smaller Y to calculate the jump.

In practice if the tamed kangaroo lands on the positive or negative point, it will be a collision, and you will catch it at the next distinguished point.

Also you have the same range N and you double the amount of calculated points but with only 1 point computation per 2 points result cost.

About the database now 1 distinguished point will "Include" twice as much points in the trailing paths. Remember the X coordinate is the same for both points so the probability of finding one distinguished point stays the same. Also as KtimesG says you will have 2 distinguished points instead of 1, the same X with n trailing zeroes and different Y, one with +Y and -Y.

This is the paper:
Steven D. Galbraith and Raminder S. Ruprai "Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval"

Yeah but if I am storing X points, I don't really care about having 2 in the database "will have 2 distinguished points instead of 1, the same X with n trailing zeroes and different Y, one with +Y and -Y"; I only need one of them stored to solve.

Well a DP entry has a key (hash or whatever) and a value (distance from base point).

If the DP hash matches, you can compute for two possible values for each distance, because the collision may have happened on either the odd or even Y coord.

So, a 4-way match instead of just one. For tames, you know the distance, so you can compute both key values. For wilds, you can similarly consider the distance as being on the left or right side of the interval, so they can both be used as a potential match. It all checks out.

Yes I believe, you only need to store the X coordinate (or its hash) and the corresponding Kangaroo ID

I still do not get why you have to store both, tame or wild, or both, all 4 DPs, a 4-way match as you said. Or just going back to the original statement, why it makes sense to store both, "...then you basically have two DPs found instead of one".

The kicker is, if you found one, you know that you have found both. They are the same value +/-. So I do not know why one would save both in a table.

Let us say we are searching for private key 0x15, public key 02352bbf4a4cdd12564f93fa332ce333301d9ad40271f8107181340aef25be59d5 at DP 0.

I have a tame that landed on private key (point) 0x16, point and distance stored:
421F5FC9A21065445C96FDB91C0C1E2F2431741C72713B4B99DDCB316F31E9FC :  16

Let's say we had a tame land on the + and the -; right or left side, etc. of private key (point) 0x1, or fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140; the point and distance stored would be:
421F5FC9A21065445C96FDB91C0C1E2F2431741C72713B4B99DDCB316F31E9FC :  1

or if you program in some wacky kind of way, it would be stored as:
421F5FC9A21065445C96FDB91C0C1E2F2431741C72713B4B99DDCB316F31E9FC :  fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140

Now you can jumble up the table and add some kind of switch that lets you know if it is right/left +/-, or have your solver code check both +/-, but I would never store the same exact points, for tames nor wilds. Just one for me :)

I think it was misunderstood. Where did I mention that both DPs need to be stored?

I said that when a DP is found, then you basically have two DPs. In a single database entry, since they both have the same X, hence the same hash (if Y is not used to affect the hash of the DP entry).

It shouldn't even be possible to store both - DP database keys must be unique for fast search. So an insertion will fail when a collision is detected, or when the DP hash collides, or when some kangaroo type collides with itself (and dies if the landed point is the stored DP point, not its opposite).

How many rtx 4090 gpu needed to solve puzzle 135 using your software?

Do you understand that the way you asked your question is plain stupid? And because you didn't put much effort into your question, I will answer deliberately on the same level: you need just one RTX 4090 to solve puzzle 135 eventually, in few hundreds of years. You could also use just zero RTX 4090 and go cpu-only, we're then in a time frame of many thousands of years.

I'm sure it's not precisely the answer you were looking for. Ask your questions with a bit more brain involved.

Around 2,500 RTX 4090 GPUs would take approximately two months to solve the puzzle. For Puzzle 140, you would need to be Elon Musk and have over 10,000 GPUs.

Hello sir , Could you please allow me to contact you? I am a first-year Computer Science student at IIT (India). I recently heard about the BTC puzzle and would love to solve these puzzles, but I am a complete beginner.

I genuinely want to learn and understand the concepts rather than simply copying others' scripts and running them on my PC. I would be truly grateful if you could guide me in solving these puzzles. Would you be willing to take me under your guidance? I promise to put in my best effort to learn and understand.

As a student, I am not in a good financial condition, but I am eager to learn. Kindly consider my request and reply at your convenience.

Thank you 🙏

how much time does it take to break 107 bit key using rckangaroo ?

It is well known that bit keys are a bit tough. Usually a single bit takes some effort, depending on how much of a hammer you use to crack it open. It also depends on your body constitution and any known medical conditions. Some people take them slow, others jump right on it with full force.

So 107 bits might take somewhere between one Planck time unit and some infinite amount of time well beyond after the last proton in the Universe decays.

so my question is , let say we have 2^27 points stored in a file and we guarantee that one of theme's scalar is between 1 and 2^107 , what is the fastest approach we can take to solve it?

Easy-peasy. You need one tame kangaroo and 2^27 types of wild kangaroos. They all walk one step at a time until you have a tame-wildX collision or a wildX/wildX collision (same type of wild). Basically that's running 2^27 Kangaroo instances at once.

If some point indeed has a scalar less than 2^107 then the shenanigan stops after around 2^54 steps or so. But it may not, because we only used one wild kangaroo for every problem. What to do? Create a new wild kangaroo for each type and start over. This will, again take more or less than 2^54 steps.

By that time you'll have jumped some good 2^(27 + 54) * numberOfRestarts steps, that's 2^80 jumps at least. Equivalent of Puzzle 160. Multiply that by the number of restarts.

Or simply start off 2^27 Kangaroo instances. Set and forget, until one yields something. It may not. Who's to know.  ??? ;D

hi RetiredCoder, thank you for sharing your hard work with us, I am new to this, so I do not really understand much of what is mentioned here.

Have you posted any pictures of your hardware setup anywhere ?


Anyway I tested puzzle 85, I have two of the 3060M Frankenstein Cards in my desktop

Are you too lazy to look for yourself in RetiredCoder's post history? Just invest a little bit of time yourself, instead of asking to be spoon-fed, how tiresome!

Quick overview: https://ninjastic.space/search?author=RetiredCoder (https://ninjastic.space/search?author=RetiredCoder)  ---  Look, Ma, I can read!

why are you cluttering this thread with your useless pompous comments, stop hijacking peoples threads

OP asked to post speed results of different cards, so I did, it was my first post ever on this forum, and I purposely
 joined so that I can post my results and try to contribute some data to this thread, and then you reply to it with your snotty comment, what is wrong with you, get over yourself, you are not that important


Just because I showed interest in his hardware setup of 400 gpus, does not mean I want to be spoon fed, I was just wanting to see what a 400 gpu setup looks like.

I did look threw his post history and did not see pictures, maybe he posted them some where else, did you happen do consider that?

I just wonder RC when he said use more than 400 gpus for solving P130, what kind of single motherboard can accept that all gpus for running RCkang?? I never see that even for mining rig when ETH in POW. so I just make conclusion (disclaimer maybe its wrong) he split the range of P130 and his 400 gpus in several rig. make illustration for explaining  the range is 200 and number gpus is 80 then split to 4 range (1 - 50, 50 - 100, 100 -150, 150 - 200) and each range use 20 gpus for running RCkang.

So I did another puzzle 84 test with 5 RTX 3060m Frankenstein cards, and 1 RTX 2070 card

It solved it in 10 minutes

It seem the MKeys/s goes down over time for some reason.

Any suggestions on what command parameters I should use for puzzle 135 with this current Gpu setup, I am not sure what the dp and tames parameters do exactly.

Would it be better to split up the 135 range ?

I hopes it is OK that I am asking questions, like I said before I am new to this.

Yeah, I really wonder why as well. I think it has to do with some basic laws of physics, like... things heat up, and heat = energy, so you're losing more energy on disipating heat rather than on jumping RC kangaroos.


I suggest you don't, since this a demo program. You will waste your time, you need a fully distributed software system, not an .exe Frankly, all of your questions are kinda stupid. Computing power is a commodity that can be bought, and you are asking people to show pictures of their oil drilling setup just because they drove a car. Or setup of their solar power grid just because they can light up their TV.

import threading
from hashlib import sha256
from ecdsa import SECP256k1, ellipticcurve
from binascii import unhexlify
import random

# Elliptic Curve Parameters
curve = SECP256k1.curve
G = SECP256k1.generator
order = SECP256k1.order

# Puzzle 135 Compressed Public Key
pubkey_hex = '02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16'
pubkey_bytes = unhexlify(pubkey_hex)

def decompress_pubkey(pubkey_bytes):
    prefix = pubkey_bytes[0]
    x = int.from_bytes(pubkey_bytes[1:], 'big')
    alpha = (x ** 3 + 7) % curve.p()
    beta = pow(alpha, (curve.p() + 1) // 4, curve.p())
    y = beta if (beta % 2 == 0 and prefix == 2) or (beta % 2 == 1 and prefix == 3) else curve.p() - beta
    return ellipticcurve.Point(curve, x, y)

P_target = decompress_pubkey(pubkey_bytes)

# Puzzle 135 Range
lower_bound = int("4000000000000000000000000000000000", 16)
upper_bound = int("7fffffffffffffffffffffffffffffffff", 16)

# Generate fixed step table
def generate_step_table(n=64):
    random.seed(42)
    return [random.randint(1 << 16, 1 << 20) for _ in range(n)]

# Step function using point hash
def step_function(P, table):
    h = int(sha256(P.x().to_bytes(32, 'big') + P.y().to_bytes(32, 'big')).hexdigest(), 16)
    idx = h % len(table)
    s = table[idx]
    return s, s * G

# Walk logic
def kangaroo_walk(start_scalar, start_point, table, max_iters=500000):
    X = start_point
    a = start_scalar
    visited = {}

    for _ in range(max_iters):
        s, sG = step_function(X, table)
        X = X + sG
        a = (a + s) % order

        if (X.x() & ((1 << 20) - 1)) == 0:
            key = (X.x(), X.y())
            if key in visited:
                return visited[key], a, key
            visited[key] = a

    return None, a, None

# Threaded worker
def kangaroo_thread(thread_id, table):
    secret_scalar = random.randint(lower_bound, upper_bound)
    wild_point = secret_scalar * G
    _, wild_a, wild_key = kangaroo_walk(0, wild_point, table)

    tame_point = upper_bound * G
    _, tame_a, tame_key = kangaroo_walk(upper_bound, tame_point, table)

    if tame_key and wild_key and tame_key == wild_key:
        recovered = (tame_a - wild_a) % order
        if recovered == secret_scalar:
            print(f"[Thread {thread_id}] SUCCESS: Recovered key {hex(recovered)} matches {hex(secret_scalar)}")
        else:
            print(f"[Thread {thread_id}] Collision found but recovery failed.")
    else:
        print(f"[Thread {thread_id}] No collision found in this walk.")

# Main launcher
def run_kangaroo_threads(num_threads=10):
    step_table = generate_step_table()
    threads = []

    for i in range(num_threads):
        t = threading.Thread(target=kangaroo_thread, args=(i, step_table))
        t.start()
        threads.append(t)

    for t in threads:
        t.join()

# Run all
if __name__ == "__main__":
    run_kangaroo_threads(10)
This was closest I came with python hope it helps still raw.

---

sorry posted wrong script previously this is raw script with the new methods:
import threading
import multiprocessing
import hashlib
import cupy as cp
from ecdsa import SECP256k1, ellipticcurve
from binascii import unhexlify
import os

# === CONFIGURATION ===
NUM_THREADS = 10
BATCH_SIZE = 1_000_000
LOG_DIR = "./logs"
MATCH_LOG = os.path.join(LOG_DIR, "135match.txt")
PROGRESS_LOG = os.path.join(LOG_DIR, "kangaroo_progress.log")

# === ECDSA SETUP ===
curve = SECP256k1.curve
G = SECP256k1.generator
order = SECP256k1.order

# Puzzle 135 compressed public key
pubkey_hex = '02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16'
pubkey_bytes = unhexlify(pubkey_hex)

def decompress_pubkey(pubkey_bytes):
    prefix = pubkey_bytes[0]
    x = int.from_bytes(pubkey_bytes[1:], 'big')
    alpha = (x ** 3 + 7) % curve.p()
    beta = pow(alpha, (curve.p() + 1) // 4, curve.p())
    y = beta if (beta % 2 == 0 and prefix == 2) or (beta % 2 == 1 and prefix == 3) else curve.p() - beta
    return ellipticcurve.Point(curve, x, y)

P_target = decompress_pubkey(pubkey_bytes)

# Puzzle 135 keyspace
lower_bound = int("4000000000000000000000000000000000", 16)
upper_bound = int("7fffffffffffffffffffffffffffffffff", 16)
keyspace = upper_bound - lower_bound

# === LOGGING SETUP ===
os.makedirs(LOG_DIR, exist_ok=True)
log_lock = threading.Lock()

def log_progress(message):
    with log_lock:
        with open(PROGRESS_LOG, "a") as f:
            f.write(message + "\n")
        print(message)

def log_match(scalar_hex):
    with log_lock:
        with open(MATCH_LOG, "a") as f:
            f.write(scalar_hex + "\n")
        print(f"[MATCH FOUND] {scalar_hex}")

# === STEP TABLE ===
def generate_step_table(n=256):
    cp.random.seed(42)
    return cp.array(cp.random.randint(1 << 12, 1 << 20, size=(n, 3), dtype=cp.uint64))

def step_function_3jump(P, table):
    h = int(hashlib.sha256(P.x().to_bytes(32, 'big') + P.y().to_bytes(32, 'big')).hexdigest(), 16)
    idx = h % table.shape[0]
    steps = table[idx]
    s1, s2, s3 = int(steps[0]), int(steps[1]), int(steps[2])
    total = s1 + s2 + s3
    return total, s1 * G + s2 * G + s3 * G

# === KANGAROO WALK ===
def kangaroo_walk(start_scalar, start_point, table, max_iters=500000):
    X = start_point
    a = start_scalar
    visited = {}

    for _ in range(max_iters):
        s, sG = step_function_3jump(X, table)
        X = X + sG
        a = (a + s) % order
        if (X.x() & ((1 << 20) - 1)) == 0:
            key = (X.x(), X.y())
            if key in visited:
                return visited[key], a, key
            visited[key] = a
    return None, a, None

# === WORKER FUNCTION ===
def kangaroo_worker(proc_id, start_base, step_table):
    threads = []

    def thread_func(thread_id, thread_offset):
        batch_start = start_base + thread_offset * BATCH_SIZE
        batch_end = min(batch_start + BATCH_SIZE, upper_bound)
        secret_scalar = batch_start
        wild_point = secret_scalar * G
        _, wild_a, wild_key = kangaroo_walk(0, wild_point, step_table)

        tame_point = upper_bound * G
        _, tame_a, tame_key = kangaroo_walk(upper_bound, tame_point, step_table)

        if tame_key and wild_key and tame_key == wild_key:
            recovered = (tame_a - wild_a) % order
            if recovered == secret_scalar:
                log_match(hex(recovered))
            else:
                log_progress(f"[Proc {proc_id}][Thread {thread_id}] Collision mismatch.")
        else:
            log_progress(f"[Proc {proc_id}][Thread {thread_id}] Range {hex(batch_start)} - {hex(batch_end)} completed with no match.")

    for i in range(NUM_THREADS):
        t = threading.Thread(target=thread_func, args=(i, i))
        t.start()
        threads.append(t)
    for t in threads:
        t.join()

# === MULTIPROCESS CONTROL ===
def launch_processes(total_batches=5):
    step_table = generate_step_table()
    processes = []

    for i in range(total_batches):
        start = lower_bound + i * NUM_THREADS * BATCH_SIZE
        if start >= upper_bound:
            break
        p = multiprocessing.Process(target=kangaroo_worker, args=(i, start, step_table))
        p.start()
        processes.append(p)

    for p in processes:
        p.join()

# === START ===
if __name__ == "__main__":
    launch_processes(total_batches=5)

---

Here is my best shot at nailing Sota+ It is still raw but if it helps:
import threading
import multiprocessing
import hashlib
import cupy as cp
from ecdsa import SECP256k1, ellipticcurve
from binascii import unhexlify
import os

# === CONFIGURATION ===
NUM_THREADS = 10
BATCH_SIZE = 1_000_000
LOG_DIR = "./logs"
MATCH_LOG = os.path.join(LOG_DIR, "135match.txt")
PROGRESS_LOG = os.path.join(LOG_DIR, "kangaroo_progress.log")
USE_SOTA_PLUS = True  # Toggle SOTA+ mode

# === ECDSA SETUP ===
curve = SECP256k1.curve
G = SECP256k1.generator
order = SECP256k1.order
p = curve.p()

pubkey_hex = '02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16'
pubkey_bytes = unhexlify(pubkey_hex)

def decompress_pubkey(pubkey_bytes):
    prefix = pubkey_bytes[0]
    x = int.from_bytes(pubkey_bytes[1:], 'big')
    alpha = (x ** 3 + 7) % p
    beta = pow(alpha, (p + 1) // 4, p)
    y = beta if (beta % 2 == 0 and prefix == 2) or (beta % 2 == 1 and prefix == 3) else p - beta
    return ellipticcurve.Point(curve, x, y)

P_target = decompress_pubkey(pubkey_bytes)

lower_bound = int("4000000000000000000000000000000000", 16)
upper_bound = int("7fffffffffffffffffffffffffffffffff", 16)
keyspace = upper_bound - lower_bound

# === LOGGING ===
os.makedirs(LOG_DIR, exist_ok=True)
log_lock = threading.Lock()

def log_progress(message):
    with log_lock:
        with open(PROGRESS_LOG, "a") as f:
            f.write(message + "\n")
        print(message)

def log_match(scalar_hex):
    with log_lock:
        with open(MATCH_LOG, "a") as f:
            f.write(scalar_hex + "\n")
        print(f"[MATCH FOUND] {scalar_hex}")

# === STEP TABLE ===
def generate_step_table(n=256):
    cp.random.seed(42)
    return cp.array(cp.random.randint(1 << 12, 1 << 20, size=(n, 3), dtype=cp.uint64))

def step_function_sota(P, table):
    h = int(hashlib.sha256(P.x().to_bytes(32, 'big') + P.y().to_bytes(32, 'big')).hexdigest(), 16)
    idx = h % table.shape[0]
    steps = table[idx]
    s1, s2, s3 = int(steps[0]), int(steps[1]), int(steps[2])
    total = s1 + s2 + s3
    direction = h & 1  # 50/50 split for forward/inverse

    jump = s1 * G + s2 * G + s3 * G
    if USE_SOTA_PLUS and direction == 1:
        jump = ellipticcurve.Point(curve, jump.x(), (-jump.y()) % p)
        total = -total % order
    return total, jump

# === WALK ===
def kangaroo_walk(start_scalar, start_point, table, max_iters=500000):
    X = start_point
    a = start_scalar
    visited = {}

    for _ in range(max_iters):
        s, sG = step_function_sota(X, table)
        X = X + sG
        a = (a + s) % order
        if (X.x() & ((1 << 20) - 1)) == 0:
            key = (X.x(), X.y())
            if key in visited:
                return visited[key], a, key
            visited[key] = a
    return None, a, None

# === THREAD WORKER ===
def kangaroo_worker(proc_id, start_base, step_table):
    threads = []

    def thread_func(thread_id, thread_offset):
        batch_start = start_base + thread_offset * BATCH_SIZE
        batch_end = min(batch_start + BATCH_SIZE, upper_bound)
        secret_scalar = batch_start
        wild_point = secret_scalar * G
        _, wild_a, wild_key = kangaroo_walk(0, wild_point, step_table)

        tame_point = upper_bound * G
        _, tame_a, tame_key = kangaroo_walk(upper_bound, tame_point, step_table)

        if tame_key and wild_key and tame_key == wild_key:
            recovered = (tame_a - wild_a) % order
            if recovered == secret_scalar:
                log_match(hex(recovered))
            else:
                log_progress(f"[Proc {proc_id}][Thread {thread_id}] Collision mismatch.")
        else:
            log_progress(f"[Proc {proc_id}][Thread {thread_id}] Range {hex(batch_start)} - {hex(batch_end)} complete.")

    for i in range(NUM_THREADS):
        t = threading.Thread(target=thread_func, args=(i, i))
        t.start()
        threads.append(t)
    for t in threads:
        t.join()

# === MULTIPROCESS CONTROL ===
def launch_processes(total_batches=5):
    step_table = generate_step_table()
    processes = []

    for i in range(total_batches):
        start = lower_bound + i * NUM_THREADS * BATCH_SIZE
        if start >= upper_bound:
            break
        p = multiprocessing.Process(target=kangaroo_worker, args=(i, start, step_table))
        p.start()
        processes.append(p)

    for p in processes:
        p.join()

# === START ===
if __name__ == "__main__":
    launch_processes(total_batches=5)

Frankly, all of your assumptions are kinda stupid

The 3060m uses lower wattage and runs pretty cool, plus i got a good cooling system, the rtx 2070 runs pretty hot though

Using other programs like bitcrack, keyhuntcuda, vanitygen, etc, etc I did not see mkey rate drop after hours and hours of runtime

I think it has more to do with memory being used up, so I think you are wrong about the heating issue.

Yes I understand that gpus can be rented by minute, hour, day, week, month, I have already did that and tested rckangaroo with 8 4090 gpus, but I saw a post from OP which made me think he was using his own gpus


He could certainly afford to use his own gpus with his winnings, so it is not a far stretch to think he has some type of hardware setup. For me building the rig and seeing how fast you can get it running is part of the fun.

So you are saying he has no hardware rigs setup at all, you seem to know everything, but I have seen OP saying you were wrong about a lot of things in this thread alone, almost every one of your posts.

I do not see myself wasting time, I am doing this for a hobby, for fun and most importantly to learn. How many puzzles did you solve with your super secret software that no one has seen? If you have not solved any then maybe you have wasted a lot more time then me.

I think some of the people on this forum just like to be rude to new comers to discourage people from trying to solve puzzles, the less people that are doing them, the better their chances are to solving it, maybe you are one of those people, not sure.

My assumptions are based on what I'm seeing you put out :)

If you want to use an unoptimized PROOF OF CONCEPT software that has no networking built in, and that requires 1000 top-end GPUs to solve Puzzle 135 in ~1 year, and better yet, by splitting it into ranges (probably because you found out there is no networking built in), that's your problem, not mine.

I only gave you a suggestion: don't do it. Every time you split, you increase your running time by 41%. Two splits? Double your time.

So maybe first learn, and then throw yourself into a witch hunt.

no, you were rude and said that my questions are stupid, and made some other snarky comments about solar panels, and oil drilling

you could not just answer a question without trying to belittle me, the question was not even directed to you

I am trying to learn, that is why I ask questions, is that OK with you ? Do I have your permission to ask questions on this forum ?

You want to be rude to me I will give it right back, you may know a lot more about this stuff then I do, but the fact is you have not solved a puzzle yet, and you probably never will.

Maybe you need to LEARN how to be a little bit more humble, get over you technical arrogance, and work on your decorum.

@Dontbeatool2
If you post the wrong script then why don't you edit your post with the wrong script and replace it with the correct one?

And please, post code in [code]...[/code] tags, not only for better readability but mainly for the reason that the forum code may gobble up certain character sequences in your code because they may be interpreted as bbcode or sometimes smileys (you know that e.g. [i] isn't that uncommon in code, guess what happens if that were in your code snippets posted like you did).

Additionally you violate forum rule #32 (see here for rules (https://bitcointalk.org/index.php?topic=703657.0) to avoid possible trouble).


I'm not soo deep in the technicalities of the method using Kangaroos. Do you (or anybody else) mind explaining in more or less short words why there's such a significant penalty by splitting the range? I struggle a bit at the moment to wrap my head around for an explanation.

If that's is so, than splitting the range to distribute work to multiple GPUs seems not the time and energy efficient way. What's the more efficient work load distribution method? Distributing the number of Kangaroos over multiple GPUs all working on the same range? How to sync efficiently?

My apologies, I'm probably too much of only an interested bystander whose brain has been (partially?) fried by too much of let's say sub-par thought-out ideas and brain-dead chit-chat in the mega threads
Bitcoin puzzle transaction ~32 BTC prize to who solves it (https://bitcointalk.org/index.php?topic=1306983.0)
== Bitcoin challenge transaction: ~1000 BTC total bounty to solvers! ==UPDATED== (https://bitcointalk.org/index.php?topic=5218972.0)


You may have a point. Questions should always be possible. It's sometimes easier to bark than to wiggle the tail or be constructive, call it whatever you want. Questions are sometimes or more often misinterpreted as stupid or lazyness or whatever, highly depends on the question and its perception by others which is also highly subjective. It happens that others react harsh, me included, when newbies step in and "do their thing" (no pun intended, everybody here once was a newbie).

It's good to point that out, helps to reflect if ones own response is actually appropriate.

Because if you need c*sqrt(n) steps to solve for an n-interval, you need sqrt(2)*c*sqrt(n) to solve for two n/2-intervals. That's an 41% increase in the time to solve, for every halving. It's actually the most efficient way to intentionally increase the necessary number of steps - splitting a problem in two halves until there's nothing more to split :)

It's basically moving an sqrt(n) complexity problem towards an (n) complexity problem (brute-force).

I actually am/been working on something likes this that uses c# and utilizes cpu to run on my computers that do not have a good Nvidia gpu, it is more a brute force method.

I also want to make something that will utilize Nvida cuda to use with a mining rig that I have been putting together. I know mining is not lucrative, I am only building it for puzzles and maybe some AI stuff in the future

The c++ code is a bit harder for me to understand, so I have been testing and looking at other cuda applications that do this, like rckangaroo, vanitygen bitcrack and stuff like that, trying to learn the best methods of going about it.

I do not think I will be renting gpus from Simplepod anymore, I just don't have the money for it at this point, I want to utilize the hardware I already have and try not to spend too much on this.


Anyway this will be my last post here on the forum, I feel kind of bad that my questions have caused RetiredCoder's thread to go off topic, I did not intend to derail this thread, so I will find some where else to go if I need to ask questions.

Take into account that remaining puzzles still need massive numbers of GPUs to find a solution in a competitive time. I don't think there's a shortcut to this. Your own GPUs aren't for free: you either had or have to buy them and they need energy while they "crunch numbers".

This isn't meant as discouragemant.


That's your decision. You need a thicker skin here.


Oops, well, that's almost embarrassing.  :o  Apparently I didn't see the forest with all the trees around me... thanks!

How to install/compile on windows?

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)

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.

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

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

Oh damn! I arrived too late to the party.

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! :D

World is getting crazier.

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

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.

The final definitive conclusion was the boring part. ;D

Now crack #135 my only hope is your mini puzzles :D

Hi RetiredCoder,

I've been researching the Bitcoin puzzle challenges and was especially intrigued by your successful solution to Puzzle #130. I'm reaching out as part of a small group analyzing these puzzles in-depth, trying to understand the methods that could realistically lead to a solve beyond brute force or Pollard's Kangaroo — both of which we've tested extensively without success.

Here’s what we’ve uncovered so far:

The puzzles all use shared private keys across chains (BTC, BCH, DOGE, ETH, DASH, etc.).

We've confirmed there's no r reuse in BTC or BCH signatures for puzzle #130.

Pollard's Kangaroo returns impractical solve times.

Your side-puzzle for BCH related to #130 shows transactions with shared TXIDs and structure, suggesting that BCH (or another altchain) played a role.

We're considering the possibility of a cross-chain signature comparison or vulnerability — possibly a reused r or signature weakness on a chain like DOGE, DASH, or CLAMS.

If you're willing to share any insights — even general direction or confirmation of our reasoning — it would be greatly appreciated. We’re not seeking the key itself, just a better understanding of how the solve was approached, and what kind of cross-chain data analysis might be most productive.

Thanks for your time and for pushing the boundaries of what’s possible in crypto research.

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.

I see how my post might’ve come across as redundant or not directly helpful to the discussion for that i apologize. I’m still learning a lot as I go, and just trying to better understand the mechanics behind narrowing the keyspace and how people like RetiredCoder were able to approach these high-bit puzzles. I’ll aim to keep future posts more focused and relevant. i do have a something about puzzle 135 on my rtx 3050 ti (i know its not great and part 3 of the research was intended with a 4090 im going to rent out a 4090 when the research is concluded) i get 7,000 days do i narrow down the keyspace width to like 35bits instead of the full 135 to search smaller areas first is that incorrect? at times i do get a collision error but one of my colleagues said that even with 35 bits there's a possibility it wont be there and im just wasting my time. 

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

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.