Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo

[Cricktor]

...

You can wait if citramonb answers you.

I was in contact with him when we discussed his case starting at this post in forum section Bitcoin Technical Support. I would suggest, you open an own topic there to discuss feasibility of your case later, once some details have been resolved here (see below).

An attempt to attack your recovery problem with any Kangaroo method tool will need a known public key for your Bitcoin address. If you don't have that (no spent coins from your address) then I'd say you're mostly out of luck.

If you definitely know the public key, chances aren't too bad, but it depends. If I interpret your WIF template correctly, you have a large known chunk at the start, then 3 unknown, another known chunk of 5, then 10 unknown and finally a known ending part. So at worst you have 18 unknowns somewhere in the middle or more to the end of the WIF.

Is that correct?

I'm not entirely sure how to handle unknown fragments of WIFs that are somewhere in the middle compared to having simply an unknown fragment at the end, specifically how to translate that into search regions for RCKangaroo or similar tools.

[ostap1706]

...

You can wait if citramonb answers you.

I was in contact with him when we discussed his case starting at this post in forum section Bitcoin Technical Support. I would suggest, you open an own topic there to discuss feasibility of your case later, once some details have been resolved here (see below).

An attempt to attack your recovery problem with any Kangaroo method tool will need a known public key for your Bitcoin address. If you don't have that (no spent coins from your address) then I'd say you're mostly out of luck.

If you definitely know the public key, chances aren't too bad, but it depends. If I interpret your WIF template correctly, you have a large known chunk at the start, then 3 unknown, another known chunk of 5, then 10 unknown and finally a known ending part. So at worst you have 18 unknowns somewhere in the middle or more to the end of the WIF.

Is that correct?

I'm not entirely sure how to handle unknown fragments of WIFs that are somewhere in the middle compared to having simply an unknown fragment at the end, specifically how to translate that into search regions for RCKangaroo or similar tools.

Yes, you're right. I wrote a very detailed explanation, but unfortunately my reply didn't pass moderation.

In short, that WIF is bait for beginners. 😄 It's not real. I looked at the photo and realized that we had found the same video online showing the WIF key. Even with a powerful tool like RCKangaroo, there is no chance of recovering it.

You can take a look if you're interested.
https://ibb.co/Ngx2dfDX

[SecretAdmirere]

I analyzed this SASS assembly code and it seems it lacks the final conditional subtraction after doing pseudo Mersenne folding twice. I know that probability of hitting non canonical form after two foldings is like ~2^(-192) so it's insignificant/negligible but still. Is it concious design choice (because of astronomically low probability) or was it overlooked?

Oh, hello, thanks for the reply. I'm sorry it took this long to reply myself. Short story is: It's a concious design choice (because of astronomically low probability) - saving a handfull of instructions that will execute every time the function is called, and on billion of those instructions executing per second, every one that isn't needed is a speed up waiting to happened. And FE mul and FE sqr are called frequently, and have the biggest impact on the speed of the code. On my program, difference of +7 (from 168 FE mul sass instructions, to 175 FE mul sass instructions) is difference between 2.25b/s and 2.22b/s (computed hash160 checks, 3070 Ti gpu), i roughly rounded up those numbers, but it's a quite the difference non the less.

And, here is the thing, anyone feel free to correct me if i'm wrong, but that non-canonical and canonical, only matter at the end when either feeding the coordinate into Sha256/Ripemd160 pipeline, or when comparing (x, y) = (x, y). And, and, if that astronomically low chance does occur at any step during the computation before the final FE function, and a non-canonical value (>= p) appears as input to FE mul, FE sql, or FE sub, the output of that function is not guaranteed to be non-canonical. It might be canonical (< p), or it might be non-canonical (>= p), which one depends entirely on the specific bit values involved, not on any property of "non-canonical inputs propagate non-canonical outputs". So in a sence, that astronomically low probability has to occur, at the very specific moment, right before hashing stage or coordinate comparison, for that one public key and it's private key that coresponds to the targeted "challenge address", and for challenge address 135, that would be that 1 in 2^135 private key, during it's calculation, happened to have FE mul or FE sqr reduction produce that 1 in 2^192 non-canonical value, at very specific moment, right before it's comparison and // missed private key, missed target address.

And for a brute force, check billions of if "this = target", the more you check in a interval of time, outweights the probability that "1 in 2^135 this, and happened to be at very specific moment 1 in 2^192 non-canonical form = target // missed private key, missed target address", beacuse only that one computation has to be correct canonical representation and the job is done, we don't care about the rest.

[lleoha]

that non-canonical and canonical, only matter at the end when either feeding the coordinate into Sha256/Ripemd160 pipeline

You are right, partially .
If you represent your field as 4x u64 (which is the usual case in RCKangaroo and whatnot) you might drop non-zero 256th bit of non canonical representation. Not to mention that other operations like field addition expect inputs to be canonical (because of the way they reduce).
Anyway, probability of getting non-canonical form from this multiplication routine is negligible, not worth exploring IMO, I was just curious.

[kTimesG]

Anyway, probability of getting non-canonical form from this multiplication routine is negligible, not worth exploring IMO, I was just curious.

For H160 vanity checks, this would be a disaster.

For Kangaroo, the full reduction is optional, because the final results (x, y) can be verified and dismissed in case of a check error (and with this occasion the astronomical chance input can be documented).

[satashi_nokamato]

Is there any possible way to look for odd or even keys in kangaroo's algo?

[mumsidea]

The issue is not DP tuning or range size.

The real problem is a DP pipeline bottleneck in RCKangaroo when running on 4×4090.

GPU generates distinguished points faster than the host-side collector / hash table can process them, which leads to continuous DP buffer overflow and dropped points.

So even if DP is set to 16–18, it does not fix the issue, because DP only changes selection density, not the ingestion rate.

This is not a mathematical failure and not a “range too small” issue.

It is purely an architectural throughput imbalance between DP generation and DP processing.

Result: effective collision rate is reduced because valid points are being dropped before being stored.

Code:

main) root@C.43053876:/workspace/RCKangaroo$ ./rckangaroo -dp 14 -range 83 -start AEDD4D7B7A5C4A00000000000 -pubkey 03d2063d40402f030d4cc71331468827aa41a8a09bd6fd801ba77fb64f8e67e617
********************************************************************************
*                    RCKangaroo v3.1  (c) 2024 RetiredCoder                    *
********************************************************************************

This software is free and open-source: https://github.com/RetiredC
It demonstrates fast GPU implementation of SOTA Kangaroo method for solving ECDLP
Linux version
CUDA devices: 4, CUDA driver/runtime: 12.8/12.1
GPU 0: NVIDIA GeForce RTX 4090, 23.53 GB, 128 CUs, cap 8.9, PCI 101, L2 size: 73728 KB
GPU 1: NVIDIA GeForce RTX 4090, 23.53 GB, 128 CUs, cap 8.9, PCI 102, L2 size: 73728 KB
GPU 2: NVIDIA GeForce RTX 4090, 23.53 GB, 128 CUs, cap 8.9, PCI 152, L2 size: 73728 KB
GPU 3: NVIDIA GeForce RTX 4090, 23.53 GB, 128 CUs, cap 8.9, PCI 153, L2 size: 73728 KB
Total GPUs for work: 4

MAIN MODE

Solving public key
X: D2063D40402F030D4CC71331468827AA41A8A09BD6FD801BA77FB64F8E67E617
Y: 875561C0BD6298FBF187053D33FFDE9672EDF2830E2CB961582431369FD53765
Offset: 000000000000000000000000000000000000000AEDD4D7B7A5C4A00000000000

Solving point: Range 83 bits, DP 14, start...
SOTA method, estimated ops: 2^41.702, RAM for DPs: 8.319 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 69.391.
GPU 0: allocated 2394 MB, 786432 kangaroos. OldGpuMode: No
GPU 1: allocated 2394 MB, 786432 kangaroos. OldGpuMode: No
GPU 2: allocated 2394 MB, 786432 kangaroos. OldGpuMode: No
GPU 3: allocated 2394 MB, 786432 kangaroos. OldGpuMode: No
GPUs started...
MAIN: Speed: 29694 MKeys/s, Err: 0, DPs: 16936K/218284K, Time: 0d:00h:00m/0d:00h:02m
MAIN: Speed: 29783 MKeys/s, Err: 0, DPs: 35363K/218284K, Time: 0d:00h:00m/0d:00h:02m
MAIN: Speed: 29787 MKeys/s, Err: 0, DPs: 53646K/218284K, Time: 0d:00h:00m/0d:00h:02m
MAIN: Speed: 29638 MKeys/s, Err: 0, DPs: 71831K/218284K, Time: 0d:00h:00m/0d:00h:02m
MAIN: Speed: 29803 MKeys/s, Err: 0, DPs: 90062K/218284K, Time: 0d:00h:00m/0d:00h:02m
MAIN: Speed: 29845 MKeys/s, Err: 0, DPs: 108198K/218284K, Time: 0d:00h:01m/0d:00h:01m
MAIN: Speed: 29777 MKeys/s, Err: 0, DPs: 126424K/218284K, Time: 0d:00h:01m/0d:00h:02m
DPs buffer overflow, some points lost, increase DP value!

My strategy is based on my own model and is focused on small-range search spaces. I am currently testing it on Puzzle 100.

However, I keep running into the same issue: no matter what DP value I set, the system eventually runs into performance problems.

This is not about tuning a single parameter. The behavior suggests a deeper limitation in the DP handling pipeline when running multi-GPU (4×4090) workloads in small-range regimes.

As a result, DP adjustment alone does not stabilize the system, and the same bottleneck appears across different configurations.

[Torin Keepler]

For anyone who wants to puzzle over it, I am publishing the challenge.

Important: these addresses belong to me, and I own the private keys. To confirm ownership, I can sign a message.
This task is published exclusively for theoretical analysis.

Task:

Given two Bitcoin addresses:
AddressX: 1MHCuKfWju9rv3apLB1As34RRSdAb2rxih
AddressY: 1GcpdwsCyBhHfSbmTr8oePYM6R6Km2CfEY

It is known that each address has at least one outgoing transaction.
It is additionally known that both private keys belong to the 0-134 bit range.

Let
kX and kY be the nonces used when creating the corresponding signatures.

The following relation has been discovered:
kX - kY = xY

where xY is the x-coordinate of the elliptic curve point
corresponding to the public key of AddressY.

Required:
Analyze this relation and determine a method for recovering the private keys of AddressX and AddressY.

Note:
Please consider this task exclusively in a theoretical context.
Do not perform any actions involving real addresses or funds that do not belong to you.

[lleoha]

For anyone who wants to puzzle over it, I am publishing the challenge.

Since you know both public keys and somewhat the relationship between them you can actually brute force it. You would have to check only 2^12 pairs. ((2^134)^2/2^256)
I dont have access to my PC right now and its too inconvenient to do this on my phone to provide all details.

[Torin Keepler]

Since you know both public keys and somewhat the relationship between them you can actually brute force it. You would have to check only 2^12 pairs. ((2^134)^2/2^256)
I dont have access to my PC right now and its too inconvenient to do this on my phone to provide all details.

Interesting approach, but it seems a bit too naive. Still, it would be interesting to see at least part of the recovered private keys or some partial proof of the solution.

If you solve the challenge, please do not publish the full private keys. Maybe someone else will also want to try solving it.

P.S. On average, solving this challenge should take no more than five minutes.

The issue is not DP tuning or range size.
The real problem is a DP pipeline bottleneck in RCKangaroo when running on 4×4090.

This is not a fundamental GPU to host pipeline problem, but simply a DP value that is too low for that speed.

According to your log, 4×4090 are running at about 29.8 GKeys/s. At DP14, that is roughly 1.8 million DPs per second. That amount of traffic can indeed overflow the buffer.

But DP is exactly what controls this flow. Every +1 to the DP value reduces the number of DPs by 2 times.
DP18 reduces the load by about 16 times, down to around 113k DPs/s.
DP20, down to around 28k DPs/s.

Increasing DP does not reduce the GPU trajectory walking speed and does not reduce the probability of a real collision. It only reduces how often DPs are stored and increases the detection delay after a collision has already happened.

Therefore, losing DPs due to buffer overflow is harmful, while increasing DP in a controlled way to a value that the host can handle reliably is the correct solution.

[BigEvilSoloMiner]

For anyone who wants to puzzle over it, I am publishing the challenge.

Since you know both public keys and somewhat the relationship between them you can actually brute force it. You would have to check only 2^12 pairs. ((2^134)^2/2^256)
I dont have access to my PC right now and its too inconvenient to do this on my phone to provide all details.

You are absolutely correct. The answer is either 2^(2×135 - 256) or 2^(2×134 - 256) possible solutions, depending on whether you read it literally or in the context of the current 135-bit challenge.

If we take it literally, then there are only 2^12 possible valid solutions to brute-force and verify. That should take only a fraction of a second on an AMD Ryzen 9 7950X or a similar CPU.

However, I find the challenge pretty suspicious. It probably deserves its own thread, and it is not much of a challenge at all if the creator’s information is actually correct. Of course, that information could be false from the start, and they may just be fishing for information.

Anyway, we should keep this thread focused on the OP’s RCKangaroo discussion. I have been thinking about applying similar ideas to something like dual mining. I may use my AI/ML hardware to help collect relations for solving the 135-bit challenge, as long as it does not interfere too much with actual tensor-performance workloads.

[lleoha]

Hello,
In the recent topic here: https://bitcointalk.org/index.php?topic=5587766 I shared my CUDA solver that is very inspired by the work of OP (if anyone is interested in).

But the real reason I am cross posting here is that in the README.md I tried to calculate what is the theoretical (i.e. without overhead) "k" for SOTAv2 and according to my calculations it is k ~= 1.128.
This computation was verified empirically in the other project of mine: https://github.com/lleoha/kangaroo-lab where I compare (by experiments) "k" values for different methods of solving DLP in interval, nonetheless I was hoping there are some smart people here who know their sh*t and would be able to verify my math .

Just to make it interesting the best methods so far (purely by number of group operations) for solving DLP in intervals are:

• Baby Step Giant Step: k ~= 0.943 (interleaved + mirror method) - impractical for large-ish intervals due to storage requirements
• Gaudry-Schost: k ~= 1.128 (SOTAv2 method)
• Pollard kangaroo (aka Lambda): k ~= 1.715 (four kangaroos method)

[Anas35]

Hello RC,

How are you, hope you are doing great.  I have had some previous keys in mind which i created with my own might and they were verified using the crypto key ru website and perfectly matched but i have forgotten those keys and lost them.  However, i remember they were only 32 or 33 chars off the total 64hex where i put something like this xxxxxxxxxxxxxxxx000000000000000000000000000000000xxxxxxxxxxxxxxx and they contain 50 btc each and litterally about 50 wallets.  I tried to make a program using cuda but it failed can you give it a try.

[kTimesG]

Hello,
Just to make it interesting the best methods so far (purely by number of group operations) for solving DLP in intervals are:

• Baby Step Giant Step: k ~= 0.943 (interleaved + mirror method) - impractical for large-ish intervals due to storage requirements
• Gaudry-Schost: k ~= 1.128 (SOTAv2 method)
• Pollard kangaroo (aka Lambda): k ~= 1.715 (four kangaroos method)

Those figures are incorrect for two reasons:

1. secp256k1 is not a generic group, while the PK constant applies to a generic group, not to secp256k1.
2. "group operation" cost greatly differs (cheapest for BSGS, cheapy for SOTA+, expensive for SOTA/GS/PK)

If you want to get tripped off, check this out: for secp256k1, with GS (SOTA+) and DP=0, you get k=0.55 which pretty much leaves any BSGS far away with dust in its eyes, uses sub-sqrt memory (.55 sqrt), finishes faster, but nevertheless, it's still as unfeasible for large bits, since it's still sqrt-bounded and a lower "k" constant doesn't do magic even if you get it close to 0.

[lleoha]

Those figures are incorrect for two reasons:

1. secp256k1 is not a generic group, while the PK constant applies to a generic group, not to secp256k1.

To compare apples to apples let me give what I mean by "k" for these methods (not sure if you've seen my kangaroo-lab where I explain it).

• Pollard Kangaroo: k is number of jumps
• Gaudry-Schost: k is number of samples
• Baby Step Giant Step: k is the number of steps

All are scaled by sqrt(N) of course. That way I can compare these numbers to the respective papers (which btw matches almost exactly, see: https://github.com/lleoha/kangaroo-lab#experimental-results)
Like I mentioned there, I am not trying to measure real world real cost or "wall clock" of these operations.

2. "group operation" cost greatly differs (cheapest for BSGS, cheapy for SOTA+, expensive for SOTA/GS/PK)

A group operation is a group operation and its cost depends solely on what that group is, but it is not what I measure, what I do measure is how many group operations (in algebraic sense) are required in idealized case.
BSGS step and PK jump is one group op, not sure why you would say otherwise (i.e. BSGS step being cheaper that PK jump), but I am interested in your rationale behind this. Pure GS I agree, restarting the GS walk takes more than one group op because it is scalar multiplication (which gets amortized if DP bits grows, or as in SOTA restarts by doing "long jump"), but again it is not what I try to measure.

If you want to get tripped off, check this out: for secp256k1, with GS (SOTA+) and DP=0, you get k=0.55 which pretty much leaves any BSGS far away with dust in its eyes, uses sub-sqrt memory (.55 sqrt), finishes faster, but nevertheless, it's still as unfeasible for large bits, since it's still sqrt-bounded and a lower "k" constant doesn't do magic even if you get it close to 0.

Not sure what SOTA+ you're referring to, because RC's SOTA with "cheap point" (if this is what you're referring to) doesn't get you near this. Since you're one of the very few people on this forum who know what they are talking about I would be happy to learn what method gets you to k=0.55 (any paper, blog post, whatever) so I can measure it in my kangaroo-lab project.
RC estimated SOTA+ to be k=0.99 which checks out, because this method essentially makes the range 25% smaller, RC estimates SOTA to have k=1.15, so naturally SOTA+ would have 1.15 * sqrt(0.75), which is ~0.99, which is also what RC reported. Thanks.

[kTimesG]

BSGS step and PK jump is one group op, not sure why you would say otherwise (i.e. BSGS step being cheaper that PK jump), but I am interested in your rationale behind this.

Dig into the actual arithmetic operations required. BSGS doesn't need any Y except for the last point addition in the batch. So there you have one less field multiplication per group addition.

Same goes with SOTA needing more ops, SOTA+ more ops, etc. Not the same group op. So you cannot compare k's these way.

And SOTA+ does yield 0.55 k when DP=0. If you get other k for this case, smth is wrong with your implementation. As DP goes up, then k goes up as well (up to the 1.1 or whatever).

Just like PK starts off from k around 1.1 when DP = 0 and goes up to the 1.71 as DP increases.

secp256k1 is not a generic group. The symmetry breaks k when DP is small.

[lleoha]

Just like PK starts off from k around 1.1 when DP = 0 and goes up to the 1.71 as DP increases.

I am assuming you didn't take a look at my kangaroo-lab project.
This is where I disagree, the Pollard kangaroo method (4 kangaroos method to be exact) starts off with k=1.71 and gets worse by some constant o(1) when DP bits increases (or number of kangaroos ran in parallel). The papers don't even consider DP>0, all math is done basically for keeping every point kangaroos visit (i.e. DP=0) which is also consistent with my experiments which do DP=0 and match the paper by +/- 0.1%.
Also the theoretical limit for SOTAv2+ from my computation is 0.95372 (DP=0, no cycles, tame ranges close to zero, etc.). 0.55 is wishful thinking. Again I would be happy to stand corrected If you prove me otherwise.

[RetiredCoder]

SOTA has K=1.15. For DP=0 with cheap point kangaroo can make two points for every jump that you add to DB, so you will get K=1.15/2

[kTimesG]

This is where I disagree, the Pollard kangaroo method (4 kangaroos method to be exact) starts off with k=1.71 and gets worse by some constant o(1) when DP bits increases

It starts off with k=1.71 only if you are working on a generic group (where an element and its inverse do not need to be easily derivable one from the other). For secp256k1, you're walking in an interval in which the first half mirrors the second half on the X property, so any detected DP collisions apply to two different points with the same X, but different distances, for each kangaroo, so there are around 7 different cases of computing the potential private key. So the base case with DP=0 for the 3-kang PK starts off much lower, at around 1.1.

See RC's post above, he's correct. Computing in batches both P±J + shared inverse + storing all unique X's + 7-way matching on collision + proper cycle exiting = k 0.55 (and no, this doesn't mean that the additions are 2x slower, since you get 2 points per addition almost for free instead of doing 2 additions).

k goes to 0.98 as DP goes up (without including the DP overhead). So if the computing device can optimize better the speed of eiither the combined addition or the reduced/conditional potential second addition you pick either PK, SOTA or SOTA+ as the winner, it's not about just choosing the lowest k.

[lleoha]

This is where I disagree, the Pollard kangaroo method (4 kangaroos method to be exact) starts off with k=1.71 and gets worse by some constant o(1) when DP bits increases

It starts off with k=1.71 only if you are working on a generic group (where an element and its inverse do not need to be easily derivable one from the other). For secp256k1, you're walking in an interval in which the first half mirrors the second half on the X property, so any detected DP collisions apply to two different points with the same X, but different distances, for each kangaroo, so there are around 7 different cases of computing the potential private key. So the base case with DP=0 for the 3-kang PK starts off much lower, at around 1.1.

See RC's post above, he's correct. Computing in batches both P±J + shared inverse + storing all unique X's + 7-way matching on collision + proper cycle exiting = k 0.55 (and no, this doesn't mean that the additions are 2x slower, since you get 2 points per addition almost for free instead of doing 2 additions).

k goes to 0.98 as DP goes up (without including the DP overhead). So if the computing device can optimize better the speed of eiither the combined addition or the reduced/conditional potential second addition you pick either PK, SOTA or SOTA+ as the winner, it's not about just choosing the lowest k.

You are mixing Pollard Kangaroo and Gaudry-Schost. What you describe would only work for GS or SOTA/SOTA+ (or more generically on methods relaying on birthday attack analysis) but not Pollard Kangaroo. It doesn't matter how many points you compute "at once" in Pollard Kangaroo, because distance between tame and wild, wouldn't change. Or in other words, it doesn't matter if tame catches wild (or wild catches tame) on the plus side going forward, or on the minus side going backwards, both are perfect mirror of each others and for methods that start at one location and never "restart" (i.e. PK) this wouldn't work.