Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo - page 7.

albertajuelo

newbie

Activity: 3

Merit: 0

Executing the puzzle #85 on RTX 4060

Quote

CUDA devices: 1, CUDA driver/runtime: 12.7/12.6
GPU 0: NVIDIA GeForce RTX 4060 Laptop GPU, 8.00 GB, 24 CUs, cap 8.9, PCI 1, L2 size: 32768 KB
Total GPUs for work: 1

MAIN MODE

Solving public key
X: 29C4574A4FD8C810B7E42A4B398882B381BCD85E40C6883712912D167C83E73A
Y: 0E02C3AFD79913AB0961C95F12498F36A72FFA35C93AF27CEE30010FA6B51C53
Offset: 0000000000000000000000000000000000000000001000000000000000000000

Solving point: Range 84 bits, DP 16, start...
SOTA method, estimated ops: 2^42.202, RAM for DPs: 3.062 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 523.378.
GPU 0: allocated 841 MB, 147456 kangaroos.
GPUs started...
MAIN: Speed: 1180 MKeys/s, Err: 0, DPs: 174K/77175K, Time: 0d:00h:00m, Est: 0d:01h:11m
...
MAIN: Speed: 1132 MKeys/s, Err: 0, DPs: 154839K/77175K, Time: 0d:02h:28m, Est: 0d:01h:14m
Stopping work ...
Point solved, K: 2.310 (with DP and GPU overheads)

PRIVATE KEY: 00000000000000000000000000000000000000000011720C4F018D51B8CEBBA8

I compare the number of operations with JLP:

Quote

Kangaroo v2.1
Start:1000000000000000000000
Stop :1FFFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^84
Jump Avg distance: 2^42.03
Number of kangaroos: 2^23.32
Suggested DP: 16
Expected operations: 2^43.12
Expected RAM: 6347.6MB
DP size: 16 [0xFFFF000000000000]

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

?

Activity: -

Merit: -

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.

albertajuelo

newbie

Activity: 3

Merit: 0

Thanks for sharing your repositories and source code.

Great job!

Lolo54

member

Activity: 131

Merit: 32

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

?

Activity: -

Merit: -

Quote from: Lolo54 on December 12, 2024, 09:14:24 AM

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.

Lolo54

member

Activity: 131

Merit: 32

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?

?

Activity: -

Merit: -

As promised, here is the third and final part: RCKangaroo, Windows/Linux, open source:
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.

stilichovandal

jr. member

Activity: 34

Merit: 5

Quote from: ? on December 11, 2024, 04:39:38 AM

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

Thank you,

?

Activity: -

Merit: -

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

?

Activity: -

Merit: -

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

?

Activity: -

Merit: -

Quote from: ?? on ??

I see a lot talking about GPU, yes for brute force calculation it seems relevant, but due to this issue of parallelism with multi tasks it seems to be the CPU and ram that count, am I right in saying that?

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.

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: ? on November 25, 2024, 11:14:54 AM

First of all, thank you guys for all your support! Grin

Slowly, but I keep working on making my ideas public, here is Part 2 of 3:

Open source: 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.

?

Activity: -

Merit: -

First of all, thank you guys for all your support! Grin

Slowly, but I keep working on making my ideas public, here is Part 2 of 3:

Open source: 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!

?

Activity: -

Merit: -

Quote from: Etar on November 23, 2024, 03:02:13 PM

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

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.

Etar

sr. member

Activity: 652

Merit: 316

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.

?

Activity: -

Merit: -

Quote from: mamuu on November 16, 2024, 04:39:57 PM

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
Or this paper with 1.36*sqrt(N) required ops:
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.

mamuu

member

Activity: 73

Merit: 19

Quote from: ? on November 16, 2024, 04:34:43 AM

Quote from: mamuu on November 15, 2024, 04:36:08 PM

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

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.

?

Activity: -

Merit: -

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

b0dre

newbie

Activity: 22

Merit: 1

Quote from: Tepan on November 16, 2024, 05:25:23 AM

Hi!
can it tested on MacOS ?

Windows only and You need Visual Studio with MFC

Tepan

jr. member

Activity: 79

Merit: 1

Hi!
can it tested on MacOS ?

Topic: Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo - page 7. (Read 4671 times)