Topic: Pollard's kangaroo ECDLP solver - page 4. (Read 58537 times)

The DPs are first loaded into memory. You control how often the DPs are written to the workfile. Once every minute, hour, 2 hours, 12 hours, however often. And this is good depending on how much RAM you have and/or the DP size. With higher DP size, you will have less DPs found and entered into hash table so you can write often or as seldom as you wish. With lower DPs, many will be found so you would need to write to file based on RAM constraints. If you are trying to solve a smaller bit range or a very large DP, then you do not have to use/create workfiles and the solution will be found via all RAM, i.e. all points and distances are kept in RAM until solution is found.

If you are using a server, then all clients send their DPs to it and it stores/writes to file all DPs found by each client, again, as often or as seldom as you wish. This is how Zielar did it I do believe. A server with many clients. And yes, he was merging the workfiles every so often (I am not sure how often) on the server side, to check for collision/solution.

The only I/O operations should just be on the server side. But again, it isn't writing to file every time a DP is found, you control how often or seldom. And with the wsplit option, you can tell the program to create a new workfile every x amount of minutes/hours/days etc. so you are only writing to disk once every x amount of time. Sometimes a solution is found within a single workfile, but most likely the solution will be found via the merging of these individual workfiles.

Exceeding the upperbounds with JLPs unmodded program is true, the whole 125 bit max. But there are other programs out there that basically mimic this program that have limits of 192-256.

No, I do not get your point. I was trying to show you that one does not need exabytes of RAM or storage to solve 130. One can solve with GBs or TBs (based on DP) and there isn't a massive I/O operation constantly going on. Of course it will take many GPUs to solve within a faster time frame, less if one is patient, but storage requirement is no where near 1 exabyte, to find a solution.


AT best case scenario, with algo averages, you would need to store 2^38.55 DPs to solve 130 using DP 27, which would roughly equate into storage requirements somewhere in the neighborhood of 300+GB multiplied by 36.5, so almost 11 TBs if my math is correct...A lot, lol. Which there are many hard drives out there to store all of that, the problem would be trying to merge all of those workfiles. GPU power can be as few or as many, GPU power gives you a rough time frame to find a solution and plays into overall DPs (overhead, which does affect storage space size) as JLP talks about in his github readme.

Those are the ones I was asking about.


I took a look into Hashmap.cpp and header.

It is storing 16 bytes for X (out of full 32) and 16 bytes for distance (out of which 3 bits are used for other things as seen in header, so 125 bits).

In these conditions yes, you can fit 2^33.36 points in 300 GB. But is there a fine print about the possibility of hash collision on those missing 129 bits in the DP? You have a missing Y sign bit hint and 128 bits of lost information about the X coordinate. Are these factored in into the probability? I see nothing about this in the README.

There is also the 125-bit distance issue. So making "shortcuts" into whatever is stored affects some of the estimations, and in thie #115 case it is translated into exceeding the number of operations that were required (2^58.36). This was a trade-off between storage and time which I don't see documented.


Since target range gets offset by target start, we can just think about a distance from 0 to....? and here's the catch: it really depends on how many jumps on average a kangaroo would need to make, in order to fill the DP table.

Yes, using a single kangaroo would basically traverse a lot of space to fill the DP table.
Using 2 kangaroos halves the distance, 256 kangaroos gets rid of 8 more bits of the distance, etc.


Yes, a distance of 0 should take up the same space as a distance of 2^max. So the individual entry size needs to increase, to accomodate.

There is research literature that tells you exactly how much a distance on average a kangaroo would require (and by effect how many jumps you need) if you have N kangaroos running in parallel. And if you look it up, it will exceed your range upper bound by some good bits.

If you look into the Hashmap.cpp (since you're a guru in this software), answer me these:

1. Why is the file loaded into memory? You almost state you can just read/write from the file to do DP storage/lookup operations, so why is it read and operated in the RAM?
2. Would you say the solution (collision) was found during a file merge from 2 different X GB files, or after a GPU loop? If the latter, that would mean the hashmap file was scanned and written to, for each DP, which by all means sounds unfeasible, at least for the simple structure it uses.

My best guess - it was found after a file merge, one after a LOT of file merges from N different backends, each using the available RAM for DP operations. So a lot of I/O stress there. If you extrapolate to #130 for whatever DP you wish for, no matter how small or large your files end up to be, you'd need to consider their I/O overhead. It's pointless to use a higher DP to save on storage unless you distribute your load across an enormous amount of servers and wait for a magical "master" merge of mini-files at some point to find your collision, which is in general agreement with what JLP stated: that you need several years on a render farm. Maybe now you somehow get my point.

Nice conversation between you two.
Considering those calculations and the comparison with 115#, what would be the neccessary requirements to at least "try" to solve 130# with let's say DP 27 in matter of storage and GPU power ?

It was close to JLPs program estimates, I want to say within 2.5%.

Also, the jumps (each jump) aren't stored. All the kangaroos are jumping via jumps but only those that land on a DP (leading 0s with this program) are stored.

I think for 115, it took a total of 2^58.36 total jumps and the workfile(s) contained 2^33.36 DPs (DP 25); and it took right around 13 days to solve. 130 at DP 32 would contain a little more than 115 at DP 25; but even if you doubled it, you are looking at 600+GB, triple it 1TB, quadrupled it 1.4 TB, etc. it is still no where close to 1 exabyte of storage required.

Distances do not really increase in size, in the same range/group. They are spread out randomly at program start and then, for say 115, they have average jump size of somewhere around 2^57ish; so each jump is about 2^57, but inside a 2^114 range, so in order to really increase, each kangaroo would have to make more than 2^57 jumps (which would take a lifetime).

But yes, a larger range would have more hex characters stored for the distance (which would take up more storage space), compared to a smaller range, but the points (DPs) would all be the same size/length, regardless of the range. So 130 compared to 115 range would equal around 3-4 more hex characters per distance.

Cool, but can you also tell me how many jumps were actually stored in those 300 GB?

Was it completed before the expected number of kangaroos of each type filled each set, to reach even a probabilistic 50%? Without such details, the best I have was estimates, and the estimates derive from the number of operations.
So if you tell me the data storage was 100 kB after 2**58 operations, anything is possible, but that would just mean not a lot of DPs were found, not that the estimates were wrong.

Does the required storage per entry scale linearly when you increase the DP? Because logically, a higher DP under a higher keyspace requires way more jumps to find all DPs, which means the travelled average distance of any kangaroo increases in size, which means your storage also increases in size because you have to store longer distances.

I fully understand the code and how this program works. All aspects.

115 was solved with a little more than 300GB of, wait, checks notes, “files”.

That was your first rant, exabytes lol.

I hope no SSDs were lost solving 110 and 115 with this program. RIP SSDs and all of your exabytes that you stored. 😁

I believe you are the one who should look into the source code, before making any other statements about it. Maybe check the hash lookup part, you will be surprised?...

Let's say you wait 1 year to fill up your DP cache (in RAM) and decide to write it to disk. Do you think you will have to write the same amount of data you have in RAM? Before answering, maybe create a simple C program that maps a 2 TB file to memory and write a single byte at offset 10 GB for example. No seeks, no nothing. I don't think you get the actual difference between offline storage and accessing random addresses of volatile memory which is in O(1). This is why it's called "random address" indexing, any byte you want to read it gets completed in constant time.

You are right though about the storage size difference, it's just 2**(0.5) between #115 with DP 25 and #130 with DP 40.
I cannot answer you how many actual storage bytes were required because I don't care about how the program stored them, just their count.

2**58.38 operations = 57.37 bits jump for each kang set = 2**(57.37 - 25) stored jumps each, so storage space was around 2*2**32.37 items for the complete merged "central table" / hashmap. Which is almost perfeclty equal to my estimates.

You are in this thread spouting non sense. That’s the issue. You have no clue as to how this program works.

You say solving 130 will require exabytes of RAM/storage, which is false. So I ask how many would it take for 115 with DP 25, how many exa or terabytes? You couldn’t answer in terms of bytes.

You talk about crashing SSDs, more info that you don’t know about this program or how it works. If an SSD can’t handle being written to, 12 times a day, then what’s the point of even owning one lol. Yes, this program, you control what and how often DPs are saved to your hard drive.

Now you claim 130 with DP 32 is magnitudes more than 115 with DP 25, which further shows you don’t know how kangaroo or this program works. Magnitudes? lol.

Maybe look at the code for this program that you are commenting on, before commenting on it.

What exactly is wrong with my calculations, to be precise?... You were specifically asking something about #130 with a specific DP. Now you want to know why #115 is a manageable effort? OK...

Keyspace: 114 bits.
T size: 57 bits
W size: 57 bits
DP = 25, so Tdp size = 32 bits
Wdp size = 32 bits

Required memory for hashmap: 2*2**32 bits entries = 8 billion entries * sizeof(jump entry)
Requires steps: 2*2**57 + numKang * 2**25
Probability(success) = 1 - (1 - 2**-57) ** (2**57) = 63%

I do not believe you understand how a hash map needs to work, in order to check for a collision.
In simplest terms, you will need some sort of a sorted list. Optimally, a balanced binary search tree. That one has O(log n) lookup and insert complexity. So, for a DP 25, that is filled with 2**33 entries, it requires 33 steps for a single lookup, IN AVEGAGE CASE scenario, when your search tree is balanced.

The memory requirement difference between #115 with DP 25 and #130 with DP 32 is orders of magnitudes higher!

It doesn't matter if you use a single CPU with few TB of RAM or many CPUs each with less RAM each. You will end up with the same problem of having to merge / query the DP "central table" / search tree / sorted list, call it whatever you want.

Good luck with your "files".

No need to test #115, I already know the answer, I just wanted kTimesG to continue to put his foot in his mouth lol.

He really has no clue what he is saying nor understands this program. This program being the program that this thread is about. I like to have good laughs and was looking forward to his follow up answer but maybe he now realizes he is wrong and won't comment again lol.

As far as Etar's program, it is good and works and works up to 192 bits. The only drawback is it is written in PureBasic and many people who use Linux, struggle trying to compile it.

I don't understand so deeply how kangaroo works but @Etar has created one distributed kangaroo.
Here are the links:
- https://github.com/Etayson/Server-Client-apps-for-Etarkangaroo
- https://github.com/Etayson/Etarkangaroo

If someone has the resources needed to run a 130# puzzle operation we can try to gather some gpu power.

Regarding what @WanderingPhilospher is asking to @kTimesG we can try to run this tool for 115# and see how long it takes and how many resources do we need/use. 
If so just PM me here.

They can be in many forms, here is trailing, with 0s:
824EDCFE76F16D85BB77626BE00000000

Or could be leading, with 0s:
00000000824EDCFE76F16D85BB77626BE

Those are both, at least, DP 32.

With those DPs, you would also have a distance/private key.

So if you get a tame DP to match a wild DP, then you would have a collision and possible solution to whatever public key you are looking for.

Tame:
824EDCFE76F16D85BB77626BE00000000  1000
Wild:
824EDCFE76F16D85BB77626BE00000000  0001

Then subtract wild distance from tame distance and that would be the private key to the public key being searched for. Priv key = 999

This is an example, those do not match up in the real curve, I just used them for an easy explanation.

Can someone show at least 2 DPs? I'd like to know more about them and to know what makes them useful in finding a collision.

Just answer the question, how much storage or RAM do you think one would need, solving a 115 bit range key, using a DP of 25? According to your previous calculations...

Glad to see some progress. Did you factor in the entire overhead of using a non-O(1) lookup and item storage for DP? Or are you talking in abstract?

You have only 2 options:
a. Insist on a constant time factor to solve the puzzle, with all the assumptions factored in. One of those requirements is a O(1) DP lookup / storage. You will need a few TB of random access memory at a physical level, not in "files".
b. Actually understand how real-life limitations kick in.

Since the DP points are impossible to predict or compute them in "ranges", actual overheads like disk page reads / writes kick in.
Reading to a SSD is thousands of times slower than reading from physical RAM.
Writing to files involves reading entire pages of data, combining it, and writing it back.

Since DP values are uniformly spread out across the entire range, so say goodbye to "fast" SSD speeds when reading and writing even a single DP entry, since it is not sequential, and you have almost 0% chance to even have two same DP points in a close range.

But sure, if you wait like 5 seconds to compute a DP, store it to a file, and using this as your base, sure, it's a 2**65.5 + DP overhead total time. But you'll end up at the end with a broken SSD with an exceeded write failures count.

A lot to unpack here.

First thing, I would not be using RAM. All DP info stored in files.

You still think it would require exabytes? To store all of those DPs?

Before more deep diving, riddle me this, based on your calculations for 130 bit range and DP 32 (which you say would require exabytes), how much would 115 bit range at DP 25 need, according to your calculations?

I think you are forgetting something about real-life constraints. Let's go by your example.
I will use log2 (bits) as a base to simplify calculations.

Puzzle #130 - keyspace = N = 129 bits.

We have two sets: T (tame) and W (wild), each having sqrt(N) elements (64.5 bits).

At this point probability of a collision (T and W intersection is not empty) is:
P(success) = 1 - P(failure) = 1 - (1 - 2**(-64.5)) ** (2 ** 64.5) = 63%

Total operations so far: 2 * 2**64.5 = 2 ** 65.5

Adding DP = 32 into the mix. So we store on average every T point out of every other 2 ** 32 and every W point out of every 2 ** 32.

So size of T = 2 ** (64.5 - 32) = 2 ** 32.5
Size of W = 2 ** (64.5 - 32) = 2 ** 32.5

Remember we didn't change nothing about probability, so these numbers are still for a 63% success probability.

Now, since DP only reduces storage by a factor of 2**DP, then the number of operations until T and W collide increases by:
2 * 2**DP / 2 on average (operations between real collision and reaching the DP point, on average for T and W) = 2 ** DP

So total ops for a 63% chance of success = 2 ** 65.5 + 2 ** DP

Now, you may say: oh, so I should apologize because I stated we need much more storage. Well, let's go back to real-life:

- set of size T with DP 32 = 2**32.5 elements
- set of size W with DP 32 = 2**32.5 elements
- P(success) = 63%

Now, how many kangaroos do we use? The naive answer is, it doesn't matter, because we are counting OPERATIONS total.

But it does matter when having to think how to store the traveled distances.
Let's see what distance a single kangaroo would travel, on average.

Jump distances = [2**0, 2**1, 2**2, ... 2**128]
Avg(jump dist) = (2**129 - 1) / 129 which almost equals 2**(129 - 7) = 2 ** 122

Number of jumps performed by the kangaroo to fill the T or W set is NOT 2**32.5, but 2**64.5 (because we still jumped even if not reaching a DP)

So total traveled distance = 2**64.5 * avgJumpSize = 2 ** (122 + 64.5) = 186.5 bits = 24 bytes

So storing a jump requires:
- jump position / key, let's say 33 bytes (X + Y sign)
- distance traveled (24 bytes) + kang type

Just by doing some simple estimations this would require a lot of TB (terabytes) of RAM.
You will need to increase the number of kangaroos by a factor of 256 to get rid of one byte in the stored DP.
65536 kangaroos to get rid of two bytes. Etc...

So to conclude:

- you need 2**32.5 tames DP, each around 60+ bytes
- you need 2**32.5 wilds DP, each around 60+ bytes
- your chances after 2**65.5 operations are around 63%
- the more kangaroos you have, the more DP overhead increases: 2**32 * numKangaroos
- the kangaroo jumps and the lookup for stored jumps needs to be in the complexity range of O(1) - e.g. RAM, not some swap file

If you can prove me that you can fit in real-life the two T and W sets without having to rely on memory swap to a storage device, then yes, you were right.

So, it goes without saying that maybe a real-life approach would not even get anywhere near storing the DP points, in our lifetime. Simply due to resource constraints.

Why did I say we need exabytes of data? Well, sir, I will let this as an exercise for the reader.

Dear @Jean_Luc, What is your opinion about Stride in Kangaroo Algo, if probabilistically it can be shown to have lower total key space in that particular stride or stride range.

The jumptables are already defined and also the Paths of Kangaroos are deterministic based on X, so stride is possible in this algo or not?

Thank you buddy. But we are not software developers, we have difficulty understanding and running the programs we use, so it is not possible for us to make changes to these programs. We would like to thank the software developers who share their programs for free without expecting anything in return.
We run the program and wait for luck to strike us.

It is possible to reduce a little bit the complexity of the classic kangaroo algorithm by spreading the starting kangaroo in a non uniform maner.
Roughly speaking, if the private key lies in certain areas it will be found faster. As a counterpart if it lies in certain other areas it will be found slower.
But in average, considering the whole range, the compexity is well reduced.
It you read and understand carefully the reference in the gitbub page, you will find the trick