Topic: Pollard's kangaroo ECDLP solver - page 67. (Read 59389 times)

I don't know your setup so I'm just asking questions.

So each tame or wild thread, must jump, check for dp, if dp send to hashtable and then jump again, if no dp, jump again, rinse and repeat.

In your test, you merely walked through 1 billion random points, correct?

Exactly, but i'don't think it will decreases dramatically the performance.

in the way i'm imagine the system, the clients (lots of ARM CPUs) will be only dedicated to be wild or tame kangaroo and to performs pure increments in the random walk.

If a distinguished point is found (i've to find a way to  be faster as possible) : example (AND mask beetween the first   of the 5 limbs (5*52bits)of X  and the desired DP,
 the client   send the X coordinate through a socket to the centralized server (computer with and hashtable checking continuously if a collision is found between received x coordinate and previously ones ).
I think it will  not slow significantly the computing because a client send a message to the server  only 1 on 2^DP times on average and a the stop of computing during the socket communication can be optimised to be fast.
 

So your speed (30MKey/s) does not include actually searching for/finding and writing/storing distinguished points to RAM/file?

In fact this speed is achieved with a modified version of the secp256k1 library of bitcoin core where every verification instructions have been removed for field and group function.
The library field_5*52.h  (instead of 10*26 for x86 cpu) (limbs registers) is automatically include for 64bits architecture and you've right it's maybe 10x faster.

I will study the NEON instructions to improve but it will be difficult because this benchmark doesn't include the DP detection code.
It's only a pure random walk benchmark on 1 Billion points.

 

That's an impressive speed, considering that Xeon E3-1230 @3.2GHz with 4c/8t only does 10MKeys/s and that the CPU inside this is:


So clock speed and thread count is halved on this silicon but yet it's 3x faster. And this makes sense because x86_64 has 16 64-bit registers and 8 128-bit SSE registers (Kangaroo doesn't use AVX yet), while armv8-a (the arch used in Cortex A72) has 64 registers and 32 more of the wider registers.

x86 was always an inefficient arch anyway because of all the backward compatibility it had to preserve. With ARM it's like "recompile for our new generation or else" and stuff written for armv8 won't work on armv7 AFAIK.


A 2080Ti costs $1000 and can do about ~1100MKeys/s per my guessing. A Raspberry Pi 4 costs $35 and you can buy up 28 of those for each 2080Ti, and all those Pi 4's combined can do 30x28=840 MKeys/s which is only a little slower than GPU's speed. If you manage to push it a little over 30MKeys/s (like by using Neon instruction set) then you can match GPU performance.

Hi everybody,
I'm writing a  light beta library in C  to run Pollard kangaroo algorithm on ARM64 CPU.

I am at the very beginning of this project but i am able to do benchmark.

when the library will be functionnal i will posted it on github.

the library (a shared object file) will be callable by python with ctypes module
The herds  of kangaroos will be controlled directly with python (for convenience and ease).
The idea is to have a lot of clients running on ARM64 low cost CPU to compute parallelized secp256k1 points additions  .
The memory (DP  points of a client) will be returned with a client-server socket data transfer (server will have the main hashtable of DP ) as the Kangaroo software from Jean-Luc Pons.

The first benchmark on ARM (Raspberry PI 400 without overclocking ) are better than I expected (around 30MKeys/s with 4 cores).

What do you think about this performance ?
Do you know if there is a very low cost card (mini PC) with ARM CPU (similar to raspberry pi compute module 4 see link below)  to do the work (in a parallelized way) and see if the ratio (computing power)/price might be better compared to the latest GPU CUDA Compatible graphics card.

https://www.raspberrypi.org/products/compute-module-4/?variant=raspberry-pi-cm4001000

yes I use nano edit "Makefile"

Did you do this first?

I use "make" only
make can compile success and can run kangaroo but can not using option -gpu
show error GPU code not compiled, use -DWITHGPU when compiling.





I will try on real Ubuntu on small harddisk try install

Did you just type "make" or "make gpu=1"? (What will work is "make gpu=1 ccap=52" or 61 or 75 or whatever your CUDA compute cap is)

By the way. WSL speed will be slower than just compiling it on Windows itself, because WSL emulates system calls. The GPUs will also not be recognized unless you install the Ubuntu(?) WSL drivers from NVIDIA's download page, the Windows drivers don't work from WSL.

I try this version
https://github.com/JeanLucPons/Kangaroo

on my linux subsystem (windows 10)

I compile with command  make success
make

and use
./kangaroo -gpu in.txt

I got message

GPU code not compiled, use -DWITHGPU when compiling.

gpu meter not show

[GPU 0.00 MK/s]

How I can compile with gpu code?

Yes

Can kangaroo compile with CUDA 10.1 or 11 ?
I don't have cuda 8.0

For some reason nobody updated the CUDA path so you need to edit the Makefile yourself and find the line that says


And replace it with


The CUDA installer creates a symlink at /usr/local/cuda to whatever the actual installed CUDA version is.

How I can compile kangaroo on windows?
upper command is compile on linux right?

Thank you.


It's not that, I'm just working under shitty environmental conditions e.g we just had a major power outage yesterday that lasted the entire day, and the internet's so $@&#ing slow here   This was supposed to be a one-week gig.

I *feel* that it's almost done but when we apply DevOps Borat's Law "To estimate project duration we apply Celsius to Fahrenheit formula. C is internal estimate and F is what we tell PM: C x 9/5+ 32 = F days." I estimate I am about 75% of the way there.  

Silly project management.


The problem is that there are three different representations of big (>64) bits in the Kangaroo program, a fixed-width 4-element array used in CUDA solver, the int128_t struct you showed me earlier and that Int class which is artificially masked to 125 bits, and all of these occurrences have to be expanded or otherwise decrippled.

And a bunch of unrelated stuff are shoved into the distance Int variables do all of those have to either be moved somewhere else or otherwise phased out (hence my deterministic hashtable index function using XOR of all the 64-bit parts, because apparently that used to be in bits64[2] of the distance variable!)

Kangaroo type also had to be moved out to a 32-bit variable. Sign bit was completely removed, it was only needed because Int arithmetic already %modulus's down negative numbers obtained from arithmetic overflow.


May I ask which custom program is it you are referring to?

---

Things like this are a step backwards, why does it assume my CUDA lives in cuda-8.0/ ?

We appreciate it.

Seems like it is more difficult than what I had thought.  JLP said it was an easy 'mod' to take it to 256 bits.

I was thinking one just needed to store/save the point and distances in a 256 format versus the current 128.  Program I use is much easier...it's 256 and I can just change the size limit to store how ever many characters in the point and distance rows.

For this kangaroo program... for the tames, the distance is a private key and the point is that private keys pubkey, so the program already knows the full point/pubkey, it has already calculated it, but pubkey was choked down to 32 characters to save RAM/file storage space... it was just a matter of storing the full pubkey (64 chars) and padding the private key/distance with zeros to equal 64 characters.

Confirmed that my custom Kangaroo mods function properly with 125 bit, 160 bit and 256 bit ranges on CPU, I will keep you guys updated as I fix up GPU/networking/merge.

Thank you
I will try again tonight

Like I said, the program will give you an estimated RAM usage.  If you are using save option, that is how much storage space you will need. 

Another way to look at it. If you are trying the full range of #120, you will need to perform 2^60 + 1 = 2^61. Now, take the -d you are or may want to use and subtract that from 2^61. So if you are using -d 30, you will need to save 2^31 points. If you are using -d 10, you will need to save 2^51 points. The lower your -d, the more storage space/RAM (if not using the save option) you will need.