Introducing an updated version of Pollard's kangaroo secp256k1 ECDLP solver

18 replies 227 views
Posts: 28 · Reputation: 229
#1Jul 11, 2019, 04:32 PM
Hey everyone, I’m excited to share my program that’s largely built on JeanLucPons’ work. Right now, it’s only focused on CPUs, but I’ve tweaked it for a 3x speed boost thanks to some cool stuff: * Utilizing the properties of secp256k1 endomorphism * Streamlined modular arithmetic for better performance * Cleaned up the code to cut down on unnecessary operations This version can currently handle a 125-bit search interval, but I’m aiming for the next one to handle at least 160 bits. Check it out on GitHub at https://github.com/GiladLeef/kangaroo. I’d love to hear your thoughts on this, thanks a lot!
6 Reply Quote Share
Posts: 28 · Reputation: 229
#2Jul 11, 2019, 04:37 PM
You mean you think i'm that second account that replied? it's not me, i think it's a bot/someone with bad English...
1 Reply Quote Share
hash_bossLegendary
Posts: 1166 · Reputation: 5261
#3Jul 11, 2019, 06:55 PM
I'm not interested to crack Bitcoin address or puzzle. But for starter, adding simple guide on how to compile the software would be great. I would bet it's account created for SEO spam, where the spam link added few days later to avoid being reported. Here's an example, https://bitcointalk.org/index.php?topic=5482297.msg64478670#msg64478670.
3 Reply Quote Share
Posts: 28 · Reputation: 229
#4Jul 11, 2019, 07:30 PM
Are you on windows or unix? You need to have a gnu system with g++ and make installed, then simply run "make" inside the directory.
1 Reply Quote Share
hash_bossLegendary
Posts: 1166 · Reputation: 5261
#5Jul 11, 2019, 09:47 PM
I see, it's rather simple. You might want to mention this on your GitHub repository. This user really like to perform SEO spam on this thread.
3 Reply Quote Share
Posts: 28 · Reputation: 229
#6Jul 12, 2019, 03:47 AM
We also started a pool, you can join, IP: 129.159.146.90 get the code at https://github.com/GiladLeef/kangaroo contact me on telegram (@renloi) for more information or drop me a message here. A telegram group will be created soon. If you join the pool, make sure you have a STATIC IP ADDRESS! We will distribute the reward according to the work done by your IP, and we need you to have the same IP when we finished cracking the 130th puzzle so you can prove your ownership of the work. take care
5 Reply Quote Share
Posts: 28 · Reputation: 229
#7Jul 12, 2019, 08:51 AM
I forgot to mention in the last message that the current version uses 256-bit integers, so we now have a 254-bit interval search range. Also, ARM is supported! - a bit tricky to compile, but i can write a tutorial on how to compile it. Tomorrow morning I will start setting up on a few computers, I have access to about 40 idle PCs with i5 CPUs ranging from 4th to 8th gen. (mostly 4th to 6th though). GPU users can join, but they need to adjust the code a little, (not my repository, but use other GPU implementations) to use the correct parameters in the networking part.
3 Reply Quote Share
Posts: 28 · Reputation: 229
#8Jul 12, 2019, 10:58 AM
CUDA supported added, and our official pool is created, we already have 3 4090s, 1 4070 Ti, 1 1080 Ti and 1 1080, and a few CPUs. soon we will have a lot more 4090s - one of my friends will rent those out. now is the time to join!
3 Reply Quote Share
5tack5atsSenior Member
Posts: 142 · Reputation: 897
#9Jul 12, 2019, 04:59 PM
Did you make any improvements on the actual CUDA code? How many op/s are you getting on the CPU and GPU side? I'm curious if it beats my own records: CPU: 10.5 M op/s on a single-threaded i9 13900H GPU: 5560 M op/s on a RTX 6000 Ada (prob the same on a 4090) Note that my CUDA kernel has almost no resemblance to the JLP code, so just curious about whether you optimized anything on that or not. I reached a HW limitation on the GPU side, all cores are used at 100% peak
3 Reply Quote Share
Posts: 28 · Reputation: 229
#10Jul 13, 2019, 04:40 PM
On the CPU side my i7 13700f does a lot better than your i9 13900h (relatively speaking)... About the GPU, nothing changed from the original version in terms of the code inside the GPU folder, nothing CUDA-performance related. It depends on a lot of other factors though, like OS you use, firmware, clock speeds, memory, and so on... so we can't really compare like this. However I can share that my workstation has 64gb ddr4 memory running at 3000mhz, as i said i7 13700f, 1080 and 1080 Ti, and totally with the whole two GPUs and CPU I get almost 2000 Mkey/s (Using default settings), depending on the clock speed. I will tweak some settings and write the best results I get to, probably will be done in half an hour. * EDIT * - On a single thread on my i7 13700f running at a fixed speed of 5Ghz I get between 13.92 and 14 Mkey/s on Windows 11 via ubuntu 24.04 running on WSL2. Anyways, happy you are interested in the code
7 Reply Quote Share
5tack5atsSenior Member
Posts: 142 · Reputation: 897
#11Jul 15, 2019, 03:59 PM
Really? This is what I get (32 GB DDRAM, everything idle, no VM, Ubuntu 22.04) 100% usage on perf core #1 doesn't pass 8 MK/s I haven't touched winblowz in years but it would be weird if it runs 2x faster simply because it's on a different OS.
4 Reply Quote Share
Posts: 28 · Reputation: 229
#12Jul 15, 2019, 09:26 PM
What clock speed you used? I assume this is the i9 13900h right?
1 Reply Quote Share
5tack5atsSenior Member
Posts: 142 · Reputation: 897
#13Jul 15, 2019, 11:04 PM
3800 MHz. But anyway, I found the explanation - your CPU is 35% more powerful than mine, and besides that, it uses three times more power. My i13900 H used 14 - 15W while running the single-thread test, and was probably throttled by thermal guards since it's on a laptop. So yeah, comparing CPUs doesn't make sense. But comparing same CPU does. I get 10.5 M op/s if using carry-free 52 bit limbs for the EC field arithmetic, against a max of 7 - 8 M op/s with your / JLP code. So around 40% speed increase on CPU side.
6 Reply Quote Share
Posts: 28 · Reputation: 229
#14Jul 16, 2019, 12:54 AM
Yeah, but what speed you get with the original JLP version? after all, we don't compare it with your custom one but with JLP's...
1 Reply Quote Share
5tack5atsSenior Member
Posts: 142 · Reputation: 897
#15Jul 16, 2019, 01:25 AM
The real speed is actually lower than this in both JLP's and your own, since you borrowed the same bugs in the speed computation. Basically, it's setting the start time later than when the threads actually started (more work in less time? oook...), hence it also shows an initial spike (which is of-course wrong). If you remove the "smoothing filter" the speed (real) goes down...
4 Reply Quote Share
Posts: 28 · Reputation: 229
#16Jul 17, 2019, 10:48 PM
I'll check that out. I actually noticed the first second has the most iterations per second on the CPU. however it's not the case on the GPU.
6 Reply Quote Share
Posts: 28 · Reputation: 229
#17Jul 18, 2019, 02:18 AM
I just want to update that the code now supports 254-bit range and multiple GPUs (on linux only).
3 Reply Quote Share
Posts: 8 · Reputation: 71
#18Jul 18, 2019, 08:00 AM
Can not compile it: Merge.cpp:10:21: error: 'filesystem' is not a namespace-name    10 | namespace fs = std::filesystem;       |                     ^~~~~~~~~~ Merge.cpp: In function 'bool isRegularFile(const string&)': Merge.cpp:20:12: error: 'fs' has not been declared    20 |     return fs::is_regular_file(filePath);       |            ^~ Merge.cpp: In member function 'void Kangaroo::MergeDir(std::string&, std::string&)': Merge.cpp:77:30: error: 'fs' has not been declared    77 |     for (const auto& entry : fs::directory_iterator(dirName)) {       |                              ^~ Merge.cpp:78:13: error: 'fs' has not been declared    78 |         if (fs::is_regular_file(entry.path())) {       |             ^~ make: *** [Makefile:60: obj/Merge.o] Error 1
4 Reply Quote Share
Posts: 28 · Reputation: 229
#19Jul 19, 2019, 12:41 AM
What version of gcc/c++ are you using? You need a modern version with support of the cross platform filesystem library.
4 Reply Quote Share

Related topics