Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo

[kTimesG]

How many pieces of DIN A4 paper are needed to find #135?

Now we're talking! Great question!

Let's organize the setup:

A4 sheets: 0.1mm x 21mm x 29.7mm
Average height of human calligraphy: 14pt (around 28 rows / sheet)

Estimated group operations on secp256k1: 2**66 optimistically, 2**68 pessimistically (warning: this may go lower or higher)

Each group operation, given that we'll use all sorts of optimization tricks (batched inversion, shared inverse, pseudo-Mersenne reductions during MUL and SQR), is composed, let's say, of:

1 INV (inversion) for, let's say, each n = 1000 points (go as high as you can, but logistically it may become a problem: are there enough A4 papers at disposal, per batch?)

3 * (n - 1) MUL (256-bit multiplications, and reduction, mod p) for the Montgomerry trick (batched inversion prefix and postfix products)

2 * n MUL for computing each slope, for P + Q and P - Q

2 * n SQR + 4 * ADD needed to compute each x3

2 * n MUL + 4 * ADD for each y3

Note: we can use some temp for the shared (- x1 - x2) so YMMV here.

Now, let's add up the required resources.

1 inversion: probably bingcd / safegcd / EEA XGCD would take some good 200 sheets of A4. I think gmaxwell brought it down to around ~ 500 half divisions. You need to know your matrix calculus pretty well though. Otherwise, keep it simple and use Fermat's Little Theorem, but you'll probably need lots more paper.

1 MUL: maybe 10 sheets (but likely with very very small hand writing, you do end up with physical limitations when multiplying some 80-ish digit numbers!

If you want to be cool, do the reduction while multiplying. If you know your shit even better, use Karatsuba, or even the FFT O(log log log n) multiplication, to save on space.

1 SQR: slighly less, maybe 8 sheets. Yeah, some digit pairs show up twice, so you finish faster!

1 Addition / subtraction: 1 sheet per each.

Now, you may notice that this all varies by the number of points (e.g. number of walks you are prepared to compute at once).

It's stupid to simply do a single walk (though it works just fine) since you lose the batch inversion benefits). Let's not be dumb, we're likely better off with around 100 million walks, for such a great adventure like Puzzle #135.

So, for n = 100 million:

Optimistic scenario: 2**66 ops
Batched steps: 2**66 / 100.000.000

That's 148 trillion A4 sheets just for all the INV for all the walks.

Prefix/postfix MULs: 2 * 10 * 2.21 * 10**20 sheets.
For slopes: 10 * 1.47 * 10**20 sheets
For x3: 8 * 1.47 * 10**20 sheets
For y3: 10 * 1.47 * 10**20 sheets

I haven't included the sheets needed for the ADD ops, I mean you can use some corners or something, they're pretty cheap.

FINAL BREAKDOWN (computation part only, optimistic scenario):

The total height of your A4 sheets would come down around to 8.536×10**14km
That is around 5.7 million AU (astronomical units), or 90 light years.

Total weight: 4.268×10**19 kg (around 0.00072% of the Earth's mass)
That is around 10.000 times the mass of all humanly built things over the course of history.

Now, you'll also need a DP database so you know when to end this thing. However, you'll need some hooks at this point, together with post-it notes, since the lookup tree needs to be dynamically balanced as you add DPs to it. If you also want to know "how many hooks and post-it notes do I need to solve 135" please LMK. Glad to help.

[onepuzzle]

How many pieces of DIN A4 paper are needed to find #135?

Now we're talking! Great question!
...

That’s one hell of a breakdown. 90 light-years of paper? I’m going to need to deforest half the Milky Way just to handle the first batch of points.

I’m especially curious about those hooks and post-its for the DP database. How many hooks per square meter are we talking about before the drywall gives up under 0.00072% of the Earth’s mass? And how am I supposed to balance that lookup tree without accidentally knocking over a decade’s worth of SQR ops?

Jokes aside, thanks for the actual math. Seeing the Montgomery trick laid out in terms of A4 sheets really puts into perspective what a GPU is actually pulling off every millisecond.

Honestly, I think I’ll skip the paper and just invest in 85,000 RTX 5090s instead. It’s slightly more efficient than hiring 7 billion planets to write on Post-its, and definitely easier on my local stationery store's supply chain.

[kTimesG]

I’m especially curious about those hooks and post-its for the DP database. How many hooks per square meter are we talking about before the drywall gives up under 0.00072% of the Earth’s mass? And how am I supposed to balance that lookup tree without accidentally knocking over a decade’s worth of SQR ops?

You're absolutely right, hooks won't cut it, especially when rotating the subtrees during DP insertion re-balancing.

If the intense friction becomes problematic, maybe it's better to introduce some elastic springs to manage all of that post-it parent nodes swinging around, changing the indirections around like crazy. Just imagine: you only need to fiddle around with the springs, and barely bother moving around the post-its themselves. Just follow the path!

Just make sure to use two colors: red for right node, green for left node. Spatial concreteness is just a construct.

[onepuzzle]

I’m especially curious about those hooks and post-its for the DP database. How many hooks per square meter are we talking about before the drywall gives up under 0.00072% of the Earth’s mass? And how am I supposed to balance that lookup tree without accidentally knocking over a decade’s worth of SQR ops?

You're absolutely right, hooks won't cut it, especially when rotating the subtrees during DP insertion re-balancing.

If the intense friction becomes problematic, maybe it's better to introduce some elastic springs to manage all of that post-it parent nodes swinging around, changing the indirections around like crazy. Just imagine: you only need to fiddle around with the springs, and barely bother moving around the post-its themselves. Just follow the path!

Just make sure to use two colors: red for right node, green for left node. Spatial concreteness is just a construct.

I took your advice and started the first point addition for #135 on A4. I’m only halfway through calculating the slope λ, and I already have a headache, a coffee stain, and I'm running out of ink.

https://imgur.com/bqgMR0K

[kTimesG]

I took your advice and started the first point addition for #135 on A4. I’m only halfway through calculating the slope λ, and I already have a headache, a coffee stain, and I'm running out of ink.

That's the spirit! Hopefully slope 2 uses +y2 though. No room for mistakes. Even a single lost carry can make the difference between total failure and  a sounding success.

[RetiredCoder]

While you are talking about really important things like solving #135 with paper, I did some benchmarks for my latest turbo kernels (SOTAv2) with 100% power:

6000Pro powlim 100% - 20.0 GH/s
5090 powlim 100% - 19.3 GH/s
4090 powlim 100% - 14.5 GH/s

It was funny to improve the algo and tech implementation one more time
You can use these numbers to try to improve your private kernels if you have them, these numbers are real.
I still think that it's not a good idea to share sources right now (also they are not prepared for that yet), so I will share them as soon as #135 is solved (so this year, not so long to wait).

[Ykra]

While you are talking about really important things like solving #135 with paper, I did some benchmarks for my latest turbo kernels (SOTAv2) with 100% power:

6000Pro powlim 100% - 20.0 GH/s
5090 powlim 100% - 19.3 GH/s
4090 powlim 100% - 14.5 GH/s

It was funny to improve the algo and tech implementation one more time
You can use these numbers to try to improve your private kernels if you have them, these numbers are real.
I still think that it's not a good idea to share sources right now (also they are not prepared for that yet), so I will share them as soon as #135 is solved (so this year, not so long to wait).

Those speeds are crazy, didn't expect you to be continuing the push on performance but respect it.

I've made some strides on my custom kernel reaching 14.4 GK/s (peak) on my 5090 build but I am already "cheating" a bit taking advantage of overclocking core clock and setting power limit.
The part I guess I'm missing is further PTX / SASS tuning, but at such a gap between our speeds there's likely a lot more.
Not after a hand out or "how to" but would love some hints to any fine tuning instruction you've used to help get your turbo kernels to that point. Thanks.

[mjojo]

While you are talking about really important things like solving #135 with paper, I did some benchmarks for my latest turbo kernels (SOTAv2) with 100% power:

6000Pro powlim 100% - 20.0 GH/s
5090 powlim 100% - 19.3 GH/s
4090 powlim 100% - 14.5 GH/s

It was funny to improve the algo and tech implementation one more time
You can use these numbers to try to improve your private kernels if you have them, these numbers are real.
I still think that it's not a good idea to share sources right now (also they are not prepared for that yet), so I will share them as soon as #135 is solved (so this year, not so long to wait).

You deserve this Sir.. even you not transfer for many years after solved, I believe no one catch your rewards. Thats why I give congrats early.. I dont care with who that always negative comment and no contribution in every page

[kTimesG]

Not after a hand out or "how to" but would love some hints to any fine tuning instruction you've used to help get your turbo kernels to that point. Thanks.

My guess list, in order of speedup:

1. A much faster inversion (I have around seven fe_inv variants and tweaks, even a parallel one under work).
2. A much faster multiplication.
3. Some hand-written inline of the addition sequence.
4. Getting rid of inversion altogether (highly unlikely, but who knows). This alone would double the speed.
5. RetiredCoder worked for NVidia. He has access to hidden SASS ops for secp256k1 primitives that he added in secrecy to the HW blueprints ever since 2009. Hence the need for "additional tools" - probably custom firmware updater.

[Ykra]

Not after a hand out or "how to" but would love some hints to any fine tuning instruction you've used to help get your turbo kernels to that point. Thanks.

My guess list, in order of speedup:

1. A much faster inversion (I have around seven fe_inv variants and tweaks, even a parallel one under work).
2. A much faster multiplication.
3. Some hand-written inline of the addition sequence.
4. Getting rid of inversion altogether (highly unlikely, but who knows). This alone would double the speed.
5. RetiredCoder worked for NVidia. He has access to hidden SASS ops for secp256k1 primitives that he added in secrecy to the HW blueprints ever since 2009. Hence the need for "additional tools" - probably custom firmware updater.

Yeah, I've focused a bit on 1-2 which has already helped my current implementations become faster but it's proving difficult to make them much faster while balancing tradeoffs~ but you know all this, interested to hear how the paralell work comes along.

5. Haha, ye RC hook us up with those undocumented SASS operations .
You might be onto something with custom firmware, not explored this area at all for this project. In the past i've meddled in those areas with NVFlash on a 3090 and many years ago PBE (Polaris Bios Editor) for AMD GPUs so I can see there is potential, cheers.

[onepuzzle]

While you are talking about really important things like solving #135 with paper, I did some benchmarks for my latest turbo kernels (SOTAv2) with 100% power:

6000Pro powlim 100% - 20.0 GH/s
5090 powlim 100% - 19.3 GH/s
4090 powlim 100% - 14.5 GH/s

It was funny to improve the algo and tech implementation one more time
You can use these numbers to try to improve your private kernels if you have them, these numbers are real.
I still think that it's not a good idea to share sources right now (also they are not prepared for that yet), so I will share them as soon as #135 is solved (so this year, not so long to wait).

Let’s look at the math for #135 based on your 19.3 GH/s benchmark. I am calculating with 2 * sqrt(N) operations (2^68) for full coverage and a rental rate of $0.325/hr per card.

Timeframe	RTX 5090s Needed	Rental Cost
1 Hour	4,247,955	$1,380,585
1 Day	176,999	$1,380,585
1 Week	25,286	$1,380,585
1 Month	5,900	$1,380,585
1 Year	485	$1,380,585

Total rental costs come out to approximately $1.38 Million. Since the 13.5 BTC reward is worth around $1.3M at current market prices, renting hardware for this is basically a break-even or a net loss. Your confidence for "this year" only makes sense if you’re already sitting on a massive private farm with free juice.

Honestly though, haven't you already suffered permanent economic damage just from all this testing and benchmarking? How high was the electricity bill so far? Or are you already financially underwater from the benchmarks alone?

I’m almost tempted to jinx your hardware out of pure jealousy for those GH/s numbers, but I’ll stick to knocking on wood for you instead. As for me, I’ll just continue solving it on paper. It’s slower, but at least the ink is cheaper than your power bill

[WanderingPhilospher]

While you are talking about really important things like solving #135 with paper, I did some benchmarks for my latest turbo kernels (SOTAv2) with 100% power:

6000Pro powlim 100% - 20.0 GH/s
5090 powlim 100% - 19.3 GH/s
4090 powlim 100% - 14.5 GH/s

It was funny to improve the algo and tech implementation one more time
You can use these numbers to try to improve your private kernels if you have them, these numbers are real.
I still think that it's not a good idea to share sources right now (also they are not prepared for that yet), so I will share them as soon as #135 is solved (so this year, not so long to wait).

Let’s look at the math for #135 based on your 19.3 GH/s benchmark. I am calculating with 2 * sqrt(N) operations (2^68) for full coverage and a rental rate of $0.325/hr per card.

Timeframe	RTX 5090s Needed	Rental Cost
1 Hour	4,247,955	$1,380,585
1 Day	176,999	$1,380,585
1 Week	25,286	$1,380,585
1 Month	5,900	$1,380,585
1 Year	485	$1,380,585

Total rental costs come out to approximately $1.38 Million. Since the 13.5 BTC reward is worth around $1.3M at current market prices, renting hardware for this is basically a break-even or a net loss. Your confidence for "this year" only makes sense if you’re already sitting on a massive private farm with free juice.

Honestly though, haven't you already suffered permanent economic damage just from all this testing and benchmarking? How high was the electricity bill so far? Or are you already financially underwater from the benchmarks alone?

I’m almost tempted to jinx your hardware out of pure jealousy for those GH/s numbers, but I’ll stick to knocking on wood for you instead. As for me, I’ll just continue solving it on paper. It’s slower, but at least the ink is cheaper than your power bill

He did solve 120, 125, and 130. I think he is still sitting on:

26.69983464 bitcoin, valued at today's price =  $1,798,681.

And if he sold at higher than today's prices...even more.

So I think he is doing OK, whether you try to jinx him or not.

Why would bench-marking cause damage? Even if you rented hardware for the bench-marking?!?! Maybe you do not understand bench-marking since you are taking this on via the paper and ink route.

But since you haven't been on the forums for a year, maybe you are new to the puzzle and.or its history as well.

Either way, RC is doing just fine, jinx or no jinx.

Also, I hope your manual paper and ink skills are better than your math skills of taking today's BTC price and multiplying it by 13.5

[walletrecovery]

While you are talking about really important things like solving #135 with paper, I did some benchmarks for my latest turbo kernels (SOTAv2) with 100% power:

6000Pro powlim 100% - 20.0 GH/s
5090 powlim 100% - 19.3 GH/s
4090 powlim 100% - 14.5 GH/s

It was funny to improve the algo and tech implementation one more time
You can use these numbers to try to improve your private kernels if you have them, these numbers are real.
I still think that it's not a good idea to share sources right now (also they are not prepared for that yet), so I will share them as soon as #135 is solved (so this year, not so long to wait).

Why should we wait? Are you so greedy that you can't even give people the source code.
Haven't you already found a few dozen bitcoins and become rich?
All your expenses have already paid for themselves.
So don't be so mercenary, open the source code for your program, let people have a chance.
Find the thread "The story of how "puddinpop" got 10K BTC and disappeared." on this forum.
He got 10,000 BTC for his source code and disappeared... probably because he was very greedy.

[RetiredCoder]

Not after a hand out or "how to" but would love some hints to any fine tuning instruction you've used to help get your turbo kernels to that point. Thanks.

Ok, here is one hint for now: forget about nvcc and go pure SASS if you are strong enough.
But please don't blame me for this hint if you get any mental issues.

Honestly though, haven't you already suffered permanent economic damage just from all this testing and benchmarking? How high was the electricity bill so far? Or are you already financially underwater from the benchmarks alone?

Please don't worry about me, I do it not for money, but just for fun. I'm retired and sometimes have time for this.

Why should we wait? Are you so greedy that you can't even give people the source code.

Hey troll, don't tell me what I should do with my software, make your own and do whatever you want.

[onepuzzle]

Oh God, I really hope that when I retire, I'll enjoy my life and not spend my time bitterly searching for puzzles. Amen.

[RetiredCoder]

Oh God, I really hope that when I retire, I'll enjoy my life and not spend my time bitterly searching for puzzles. Amen.

That's the main reason why people fail: they don't like what they do and just want money.

[Ykra]

Not after a hand out or "how to" but would love some hints to any fine tuning instruction you've used to help get your turbo kernels to that point. Thanks.

Ok, here is one hint for now: forget about nvcc and go pure SASS if you are strong enough.
But please don't blame me for this hint if you get any mental issues.

Thanks for the hint, I was afraid the continued gains might be something this deep but I enjoy the learning process so will start exploring further in this direction even if it does challenge my mental fortitude.

[WanderingPhilospher]

Oh God, I really hope that when I retire, I'll enjoy my life and not spend my time bitterly searching for puzzles. Amen.

Buuuut, you are not retired and are still bitterly searching for puzzles lol. Go "enjoy" your life now! Don't bitterly search for puzzles now and in retirement!