Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo

[kTimesG]

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.

You are missing the fact that in PK all walks go in a single direction.

Hence, only the points are mirrored, not the walks.This means that once you hit one of two points with the same X, the next point is different depending on whether the current point was on the left or right side.

So once you have a DP collision, you have two distances, not one, because the DP might have been on one of two sides, hence different distances to the respective base point (two offsets to the tame base, and two offsets to the public key and the symmetric one).

Maybe actually implement this and see for yourself? You don't have to believe me, I am simply stating facts.

[lleoha]

You are missing the fact that in PK all walks go in a single direction.

I am very aware of that.

Maybe actually implement this and see for yourself? You don't have to believe me, I am simply stating facts.

Already did that, more than one time.
https://github.com/lleoha/kangaroo-lab (experiments to compare K with what papers say)
https://github.com/lleoha/coin-cracker (CUDA "mirrorless" SOTAv2, gives k=1.6 but it processes more points/s than RCKangaroo, there's also some math behind SOTAv2's "k").

[kTimesG]

I am very aware of that.

Great then. You continue to confuse secp256k1 with a generic group. Here's your fallacy:

The leading constant should not depend on whether the group is this additive group, an elliptic-curve group, or another cyclic group of comparable order

because the exact opposite is true: the constant depends on whether the group has special properties.

PK 1.71 is for generic groups, not for groups with equivalence classes. But you should know better what you're looking for, after all. EOF

[verybitcoinwow]

Question from a newbie: Did RC have the public keys for puzzles #120, #125, and #130?

[nc50lc]

Question from a newbie: Did RC have the public keys for puzzles #120, #125, and #130?

Those pubKeys are already available to public ever since the puzzle owner revealed those divisible-by-five puzzle ranges.

For clarification,
It's not directly posted, the owner just sent and spent 1000sat UTXO to those, by doing so, he reveled the pubKeys.
(then sent more bitcoins back to the same addresses)

Those pubKeys can be seen in this "transaction" that spent those: 17e4e323cfbc68d7f0071cad09364e8193eedf8fefbcbd8a21b4b65717a4b3d3
Click "Details+" and look for each address' pubKey next to the signature.

[verybitcoinwow]

Question from a newbie: Did RC have the public keys for puzzles #120, #125, and #130?

Those pubKeys are already available to public ever since the puzzle owner revealed those divisible-by-five puzzle ranges.

For clarification,
It's not directly posted, the owner just sent and spent 1000sat UTXO to those, by doing so, he reveled the pubKeys.
(then sent more bitcoins back to the same addresses)

Those pubKeys can be seen in this "transaction" that spent those: 17e4e323cfbc68d7f0071cad09364e8193eedf8fefbcbd8a21b4b65717a4b3d3
Click "Details+" and look for each address' pubKey next to the signature.

Thanks. That explains it

[JDScreesh]

Hello there!

Congratulations RetiredCoder for solve the puzzle # 135.

 

[RetiredCoder]

Thanks.
Yeah, finally I solved #135, it took about 5 months on 200GPUs.
It was... long. I quit, officially. Happy solving #140 without me.
To help you with this, today I will update RCKangaroo with complete sources for ASM turbo kernels.
I will also publish pk for #135 but later, not right now, when I have some time I will think up another mini-puzzle for that.

[Torin Keepler]

Thanks.
Yeah, finally I solved #135, it took about 5 months on 200GPUs.

Congratulations on your determined and systematic approach, which has led you to yet another victory!

I have a question: which jump tables did you use for the main step and for escaping loops?

Did you use jump tables from the ranges of previous puzzles, taking advantage of the existing database, or did you start all over again?

Thank you very much, and once again, please accept my sincere congratulations!

[RetiredCoder]

RCKangaroo v4.0:
https://github.com/RetiredC/RCKangaroo

I managed to exclude inverse calculation from main loop and applied Montgomery trick three times in total, so I call it "Triple Montgomery trick" 
That was fun!

I have a question: which jump tables did you use for the main step and for escaping loops?
Did you use jump tables from the ranges of previous puzzles, taking advantage of the existing database, or did you start all over again?

I had reasons not to use old databases, so I used fresh jump tables.

[citramonb]

Thanks.
Yeah, finally I solved #135, it took about 5 months on 200GPUs.
It was... long. I quit, officially. Happy solving #140 without me.
To help you with this, today I will update RCKangaroo with complete sources for ASM turbo kernels.
I will also publish pk for #135 but later, not right now, when I have some time I will think up another mini-puzzle for that.

Congratulations! You’ve made history—no one will ever be able to replicate what you’ve achieved! You wrote the software and gave it away for free, yet you still outclassed everyone; pools with 20, 30, 50, 100, or even more members failed to do what you did—you beat them all to the punch once again. Congratulations! It was a pleasure watching your journey. 👏🏼🤝🏼

[b0dre]

RCKangaroo v4.0:
https://github.com/RetiredC/RCKangaroo

I managed to exclude inverse calculation from main loop and applied Montgomery trick three times in total, so I call it "Triple Montgomery trick" 
That was fun!

I have a question: which jump tables did you use for the main step and for escaping loops?
Did you use jump tables from the ranges of previous puzzles, taking advantage of the existing database, or did you start all over again?

I had reasons not to use old databases, so I used fresh jump tables.

Congratulations legendary.

"fresh jump tables" every try or how?

[kTimesG]

Thanks.
Yeah, finally I solved #135, it took about 5 months on 200GPUs.
It was... long. I quit, officially. Happy solving #140 without me.

CongSats! So did you even make a profit off #135? Your post's sentiment inclines a bit toward some frustration. Don't worry, your code will be dissected to blood and stand as the basis of future optimizations until the dawn of secp256k1.

[RetiredCoder]

"fresh jump tables" every try or how?

It means I used own set of jumps for #135, not from previous puzzles.

So did you even make a profit off #135? Your post's sentiment inclines a bit toward some frustration.

Sure I got profit, but I won't do it again, no fun anymore, it was too boring to pay bills for five months  

Don't worry, your code will be dissected to blood and stand as the basis of future optimizations until the dawn of secp256k1.

Yeah, feel free to improve it by x10!  

The range closest to the actual key is here. Is this correct
...

Please keep all magic predictions/circles/etc away from this thread, you have a whole separate 680-pages thread for this!  

[crytoestudo]

Congrats, bro—you're a total legend. Could you tell us which GPU models they are?

Thanks.
Yeah, finally I solved #135, it took about 5 months on 200GPUs.
It was... long. I quit, officially. Happy solving #140 without me.
To help you with this, today I will update RCKangaroo with complete sources for ASM turbo kernels.
I will also publish pk for #135 but later, not right now, when I have some time I will think up another mini-puzzle for that.

[damiankopacz87]

5 months instead of AT LEAST 20 expected? Did You search at smaller ranges, eg. 1024 x 124bit ranges? Random choice or one by one?
If You are leaving quest, are You willing to give DP base You used to community? Apes together strong

Best Regards
Damian

[toshisa_toshisa]

Congratulations on solving Bitcoin Puzzle 135! That's an incredible achievement and a testament to your skill, patience, and dedication.

I have to admit, seeing your success is bittersweet for me. I've spent so much money, countless hours, and an enormous amount of effort chasing these puzzles, hoping one day I'd solve one myself. After hearing the news, I honestly feel pretty hopeless.

Still, you earned this, and I sincerely congratulate you. Enjoy the moment—you've accomplished something that many of us have been chasing for a long time. Wishing you all the best, and thanks for showing what's possible.