Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo

[Ykra]

Thank you for the suggestion, but I described my own approach to solving it. I know it will probably take longer.

If I’m not mistaken, in your example you solved a private key with missing characters in raw HEX format, while mine is in WIF format, and the process is a bit different there. I’m also not sure that the same method can be applied in my case.

That small puzzle was actually very useful for me because it showed that this particular method probably won’t work for my situation.

So I will continue with my slower and more methodical approach: I will substitute the first 3 unknown characters one by one, and for the remaining unknown section I will simply define a range and check it.

I adjusted my solver to work with broken WIF's - different to the method used for Puzzle6. Puzzle6 made me realise it's possible to solve (with some complexity shift) on WIFs with gaps.

That is why I suggested you create a new WIF key on https://iancoleman.io/bip39/ or wherever, post the WIF with the broken parts only (same structure as yours: [26 known characters] + [3 unknown characters] + [5 known characters] + [10 unknown characters] + [8 known characters]) and the pubkey and I'll return you the full WIF.

If you are not interested, no worries and good luck!

[farou9]

the speds varies depending on the language and the libraries , on python using ecdsa its very slow i think 80k/s but if we used coincurve it goes up (114,956 EC additions/sec) , but on c++ the speed is better never tested it but i can predict it coincurve uses libsecp so if we used the 4threads we can achive 500-700k/s , just tested it it can reach Speed: 548779 EC additions/sec using 4 threads in  c++

BTW, you talk about knowledge and intelligence, but use slow python and its libs instead of writing own optimized lib in c. So optimizing is not a part of intelligence in you opinion?
Performance always matters here, if I had only CPU I would create heavy-optimized lib for it to be able to perform more tests and researches.

i only use python because it is eay and fast to write and easy-fast to fix if an error shows up. also i only use it to test my ideas.
for real tests i use c of course (i cant say i do build optemized libs too lazy for that) but i use every available optimization in math i can think of.
"Performance always matters here" that is if you know you have a chance "and damn good one too"

[Bram24732]

Thank you for the suggestion, but I described my own approach to solving it. I know it will probably take longer.

If I’m not mistaken, in your example you solved a private key with missing characters in raw HEX format, while mine is in WIF format, and the process is a bit different there. I’m also not sure that the same method can be applied in my case.

That small puzzle was actually very useful for me because it showed that this particular method probably won’t work for my situation.

So I will continue with my slower and more methodical approach: I will substitute the first 3 unknown characters one by one, and for the remaining unknown section I will simply define a range and check it.

I adjusted my solver to work with broken WIF's - different to the method used for Puzzle6. Puzzle6 made me realise it's possible to solve (with some complexity shift) on WIFs with gaps.

That is why I suggested you create a new WIF key on https://iancoleman.io/bip39/ or wherever, post the WIF with the broken parts only (same structure as yours: [26 known characters] + [3 unknown characters] + [5 known characters] + [10 unknown characters] + [8 known characters]) and the pubkey and I'll return you the full WIF.

If you are not interested, no worries and good luck!

I think the guy’s method will work even if slower.
A slow method and not sharing keys is always better than a faster one requiring to send your keys to a stranger.
Congrats on the mini puzzle win ! I was sleeping when it was posted so couldn’t compete sadly !

[dextronomous]

Why should we wait? Let's have fun right now!   
https://bitcointalk.org/index.php?topic=5577390

as was doing my try to find the key,

the code i had showed this, nothing hardcoded for that address in the code btw but still there,

==================================================================
  VERIFY — Scale-Reduction Puzzle  (community example)
==================================================================

  k = Scale * pK  (mod n)    Scale = 4*2^192 + 3*2^128 + 2*2^64 + 1
  k in four 64-bit lanes:
    k[255:192]=4*pK  k[191:128]=3*pK  k[127:064]=2*pK  k[063:000]=1*pK

  Community member's approach:
    1. Compute Scale and its modular inverse on secp256k1 order
    2. Q' = inv(Scale)*PubKey  =>  Q' = pK*G  (standard 1D DLP)
    3. BSGS on Q' in ~[2^63, 2^64) range — solved in 2 min on a PC
    4. Reconstruct full key: k = Scale*pK mod n

  pK      = 0x3380374721080fff  (62 bits)
  k       = ce00dd1c84203ffc9a80a5d563182ffd67006e8e42101ffe3380374721080fff
  Address = 1PGRtg6XjiYSB1VJAhsqLQc6hQeBqFGVPD

  inv(Scale)*PubKey == pK*G : VERIFIED

  Lane check:
    4*pK = ce00dd1c84203ffc   3*pK = 9a80a5d563182ffd
    2*pK = 67006e8e42101ffe   1*pK = 3380374721080fff
  Combined = ce00dd1c84203ffc9a80a5d563182ffd67006e8e42101ffe3380374721080fff
  k (mod n)= ce00dd1c84203ffc9a80a5d563182ffd67006e8e42101ffe3380374721080fff  match

================================================================== saw later it was puzzle 5's address, weird or normal.

[arulbero]

But you know what? Cycles don't really need so much exhaustive burnout if you mastermind the behavioral headaches of roundabouts in a much more simpler way. No hoverboard needed.

I'm glad that you finally like cycles

Yo Doc. I'm honestly in a loop on loop handling. I frankesteined my way to do a sorta' but not identical SOTA+ (let's call it SOTA++) in CUDA because I want that 1.0 sqrt after all. Was seriously thinking this is what your RCKang does already (based on some code comments in Kang1 or Kang2 that sounded like "on a GPU, we always compute both of x3, because no benefits etc.". My bad. I'm using 8 as group size so basically I'm jumping 80% faster than a forward-only creature.

But it all got nuked when I got to the point of having to escape cycles. Detecting them was a breeze. Escaping them? It's simpler to get out of a Guantanamo Bay prison in one piece.

Check this out: a simple 4 cycle:

A -> B -> C -> B -> A -> D

Now, the problem with this circuit is that B and C are in a 2-cycle that needs to exit at B (to keep up symmetric walk), but also B and A are in a 2-cycle as well (this dude's exiting on A), so D's the exit point because B's just been visited. Crap.

Yeah, the 4-cycle auto-exited by itself during the second 2-cycle handling. That's totally f***d up, but also so beautiful.

I hate cycles.

Did you read this https://eprint.iacr.org/2011/003.pdf ?

[kTimesG]

Did you read this https://eprint.iacr.org/2011/003.pdf ?

It's easy to generically handle cycles. But it needs to be very efficient on GPU hardware, in this case, not to simply "fix" the problem. As I said, I found a way to very elegantly escape cycles when using the negation map (up to some maximum detected length of course, but those are so rare it doesn't really matter anyway).

My method guarantees with 100% certainty that, after some number of jumps are performed, no walk is in a cycle, and that opposite (symmetric) walks definitely continue in a symmetrical way, because they escape cycles in opposite directions for sure. No need for weird separate jump tables or separate kernels, like in RC's approach. If some walk is in a undetected cycle, it's gonna get detected for sure during the next kernel launch.

The biggest challenge was handling the problem of escaping a cycle only to immediately (or eventually) get back inside the cycle, due to the jump rules. This is where the "elegant" part comes in, since there is a way to ensure this can never (and I mean *never*) happen.

[arulbero]

Did you read this https://eprint.iacr.org/2011/003.pdf ?

It's easy to generically handle cycles. But it needs to be very efficient on GPU hardware, in this case, not to simply "fix" the problem. As I said, I found a way to very elegantly escape cycles when using the negation map (up to some maximum detected length of course, but those are so rare it doesn't really matter anyway).

My method guarantees with 100% certainty that, after some number of jumps are performed, no walk is in a cycle, and that opposite (symmetric) walks definitely continue in a symmetrical way, because they escape cycles in opposite directions for sure. No need for weird separate jump tables or separate kernels, like in RC's approach. If some walk is in a undetected cycle, it's gonna get detected for sure during the next kernel launch.

The biggest challenge was handling the problem of escaping a cycle only to immediately (or eventually) get back inside the cycle, due to the jump rules. This is where the "elegant" part comes in, since there is a way to ensure this can never (and I mean *never*) happen.

To escape: just do P_min (P with the minimum x in the cycle) + G, so it breaks the cycle

but you said you have found a way to be sure to not get back to the cycle? You store all P_min of all cycles you have found in a single walk?

[kTimesG]

To escape: just do P_min (P with the minimum x in the cycle) + G, so it breaks the cycle

but you said you have found a way to be sure to not get back to the cycle? You store all P_min of all cycles you have found in a single walk?

Your suggestion is part of the escape logic (actually, its the last step, but not the most important one), but it needs lots of refinement because you have to deal with both simple 2-cycles and cycles longer than 2, all while keeping the symmetries, maximizing DP production, minimizing core logic, and avoiding overhead. So what sounds good and simple in theory may end up with unexpected bad results in practice. Of course I'm not storing or accessing any more memory than what's needed to detect whether a walk went cycle-mode. Also the jump table really matters a lot since it can be constructed to totally avoid certain cycles (most will disagree and say it breaks some types of collisions, but it's not just the jump table at work).

[arulbero]

To escape: just do P_min (P with the minimum x in the cycle) + G, so it breaks the cycle

but you said you have found a way to be sure to not get back to the cycle? You store all P_min of all cycles you have found in a single walk?

Your suggestion is part of the escape logic (actually, its the last step, but not the most important one), but it needs lots of refinement because you have to deal with both simple 2-cycles and cycles longer than 2, all while keeping the symmetries, maximizing DP production, minimizing core logic, and avoiding overhead. So what sounds good and simple in theory may end up with unexpected bad results in practice. Of course I'm not storing or accessing any more memory than what's needed to detect whether a walk went cycle-mode. Also the jump table really matters a lot since it can be constructed to totally avoid certain cycles (most will disagree and say it breaks some types of collisions, but it's not just the jump table at work).

So the idea is like:

if all jumps are even and you do Pmin​+G, you change parity: before the cycle, the kangaroo walks on even (for example) points; after the escape, it walks on odd points. If the kangaroo falls in a new cycle, it changes again parity, and so on;

a jump table defines a partition of the interval-> A U B = interval I, and to escape from a cycle you jump from A to B and viceversa;
 
in any case, a jump table defines always a partition of the interval -> A U B = I, where |A| = (1-1/e)*|I| and |B| = (1/e)*|I|; in general case, A is the set of the points you can reach with a pseudorandom walk, B is the set of the points you can't reach.  

If I can divide A = A_even U A_odd,  if P is in A_even (P = k*G, with k even) then -P is in A_even too (cause -P=-k*G); but the kangaroo could pass from a "even" cycle 1 to an "odd" cycle 2 and then again on the original "even" cycle 1?  

[kTimesG]

So the idea is like:

if all jumps are even and you do Pmin​+G, you change parity: before the cycle, the kangaroo walks on even (for example) points; after the escape, it walks on odd points. If the kangaroo falls in a new cycle, it changes again parity, and so on;

If I would say just two things more about that first "if", I'd spill way too much.

I'm not wiggling around 2 search spaces just because cycles are exited, that would be dumb. If you go with even-only jumps, this is solved by adding/subbing 2G instead of G, and hence no splitting the search zones.

OK, maybe I should rephrase what I meant by "100% certainty that it won't re-enter the cycle".

It can't re-enter the cycle after the next jump, because 1 (G) isn't a table jump.

But it also can't enter the cycle during the second jump as well (because there is no jump in table such that ±A ± 1 = ±B).

Let's continue. It can't enter the cycle either during the third jump, because, well, the situation is impossible given the values of the jump table.

4th time? Possible, but at this point this would occur only in 1 out of (N*2)^4 cases or so, which is acceptable.

Why "possible"? Because constructing a jump table that guarantees all possible four sums don't cancel each other (ideally a Sidon set) requires a supercomputer, so I'm fine with 3 levels of construction (heuristically close to ideal, already taking a massive amount of time to build).

[arulbero]

So the idea is like:

if all jumps are even and you do Pmin​+G, you change parity: before the cycle, the kangaroo walks on even (for example) points; after the escape, it walks on odd points. If the kangaroo falls in a new cycle, it changes again parity, and so on;

If I would say just two things more about that first "if", I'd spill way too much.

I'm not wiggling around 2 search spaces just because cycles are exited, that would be dumb. If you go with even-only jumps, this is solved by adding/subbing 2G instead of G, and hence no splitting the search zones.

OK, maybe I should rephrase what I meant by "100% certainty that it won't re-enter the cycle".

It can't re-enter the cycle after the next jump, because 1 (G) isn't a table jump.

But it also can't enter the cycle during the second jump as well (because there is no jump in table such that ±A ± 1 = ±B).

Let's continue. It can't enter the cycle either during the third jump, because, well, the situation is impossible given the values of the jump table.

4th time? Possible, but at this point this would occur only in 1 out of (N*2)^4 cases or so, which is acceptable.

Why "possible"? Because constructing a jump table that guarantees all possible four sums don't cancel each other (ideally a Sidon set) requires a supercomputer, so I'm fine with 3 levels of construction (heuristically close to ideal, already taking a massive amount of time to build).

first jump: +1  =  ±S  (impossible)   from P1(even)  to P2 (odd)

second jump: ±A ± 1  = ±S   (impossible)  from P2(odd) to P3(odd)

third jump:   ±B ±A ± 1 = ± 1  (possible)

could be ±B  = ±A   then another 2-cycle    from P3(odd) to P2(odd)

fourth jump: ± 1 = ±1 (possible)  from P2(odd) to P1(even) -> a 4-cycle

2 consecutive 2-cycles are like a single 4-cycle from a probability point of view?

Idea: escape jump = +1G from a 2-cycle, escape jump +3G from a 4-cycle

[kTimesG]

2 consecutive 2-cycles are like a single 4-cycle from a probability point of view?

Idea: escape jump = +1G from a 2-cycle, escape jump +3G from a 4-cycle

Yes, it's a 4 cycle and it really happens in a sequence such as (A, B, -A, -B) or permutations. Same goes for 6 cycles, 8-cycles, etc.

But you can't escape a 2 cycle by doing another ad-hoc addition, since you lose the shared inverse (speed drops), and besides you need to always exit from the same end of a 2-cycle, otherwise symmetric walks diverge (a walk may hit one end of the 2-cycle, another walk the other end, but they must both exit from the same point). All while maximizing DP production

So, it's not that easy.

[RetiredCoder]

OMG, I see interesting comments here finally! 

...a walk may hit one end of the 2-cycle, another walk the other end, but they must both exit from the same point...

Or you can don't care about it and lose just 0.1% of K.

BTW, I still don't understand why you bother about all these boring cycles, you have much better algo for a long time!

47 bits, DP 10

Code:

[2] Ops: avg 11267030 = 0.950 * sqrt(b) min 7221075 max 15312985 dp_ovh: 1536.0 mul: 10.50
Stored footprints: avg   25820 min 16542 max 35099

No cycles.

I wouldn't believe it either, so that's fine. Everything is already checked, counted, and verified to be correct.
I verified it also for higher bit ranges, that jump on GPU.
Those figures are the total op count including DP overhead (complexity excludes DP overhead).
And I'm using more than 3 kangaroos. Pure math and skills, you should understand that.

[kTimesG]

BTW, I still don't understand why you bother about all these boring cycles, you have much better algo for a long time!

It ran too slow. btw you can get to 0.95 with SOTA+. Not sure why you don't like it for GPU, my assumption is that you trade some higher speed (1.5x points instead of 2x each step) with the higher k of SOTA?

[RetiredCoder]

BTW, I still don't understand why you bother about all these boring cycles, you have much better algo for a long time!

It ran too slow. btw you can get to 0.95 with SOTA+. Not sure why you don't like it for GPU, my assumption is that you trade some higher speed (1.5x points instead of 2x each step) with the higher k of SOTA?

1. Slow?? Well, ok
2. Oh, it's easy: SOTA+ requires additional MUL+SQR, so it's just not profitable if you have really cheap inversion.

[arulbero]

BTW, I still don't understand why you bother about all these boring cycles, you have much better algo for a long time!

It ran too slow. btw you can get to 0.95 with SOTA+. Not sure why you don't like it for GPU, my assumption is that you trade some higher speed (1.5x points instead of 2x each step) with the higher k of SOTA?

1. Slow?? Well, ok
2. Oh, it's easy: SOTA+ requires additional MUL+SQR, so it's just not profitable if you have really cheap inversion.

Let me guess: you compute Q = P + J and Q' =   P - J, and you choose the point with minimum x.

[castonrecovery]

got it working with AMD Radeon RX 9070 RDNA 4. Used hipify-perl to port and had to use x-thread to stop wilds corrupting.

Here is the repo for the HIP port.

https://github.com/caston1981/RCKangaroo-hip

I hope someone finds it helpful. I certainly did. It works on nonces too 

[RetiredCoder]

Let me guess: you compute Q = P + J and Q' =   P - J, and you choose the point with minimum x.

Almost, it's all described here (also there are some comments in sources):
https://github.com/RetiredC/Kang-1

[ldabasim]

got it working with AMD Radeon RX 9070 RDNA 4. Used hipify-perl to port and had to use x-thread to stop wilds corrupting.

Here is the repo for the HIP port.

https://github.com/caston1981/RCKangaroo-hip

I hope someone finds it helpful. I certainly did. It works on nonces too  

Cool. It works although not quite out of the box, had to give it to codex, makefile rewritten for hip among other few changes. a billion keys/s on a 6700.

[castonrecovery]

Cool. It works although not quite out of the box, had to give it to codex, makefile rewritten for hip among other few changes. a billion keys/s on a 6700.

Thanks for testing it out and I am glad to hear it's working with your 6700. Please let me know if you wish to commit your improvements.