Why not simply AES-256 encrypt the private key and be done with it in, like, 3 lines? No password hashing and so on.

I solved puzzle #66 but I'm very afraid to sweep it. Since no one claimed it yet, they definitely belong to me, right? Here's my proof: the encrypted private key is:
First 16 bytes are the IV, then 32 bytes of private key. I removed the padding, since it's 16 bytes of 0x10 (e.g. no bytes in last block).

If anyone steals my prize I will divulge the decryption key.

Or, simply hash it once together with some secret value, you only need to prove you knew the hashed value before anyone else, not to protect the actual data.

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.

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 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.

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".

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.

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.

What good does it do if you will most likely overflow the 128-bit after just a few jumps, no matter what start distance you begin with?

I never stated I'm solving 66 with pen and paper, only that 66 is a hashing rate contest that has nothing to do with ECDLP at all.
I believe you were the one thinking we only need something like 2* 2**33 kangaroos or whatever to solve #130 in something like 2**66 steps... when the reality is we need many exabytes of stored data to have a 50% chance for a collision, in that many steps you mentioned.

A true random source of 65536**2 range values can (and will) spit out a (42, 42, ...) sequence out just as equally likely as (0x7b03aa9f, 0x33bcf51c, ...). If your argument is that it's less likely for same sub-ranges to be part of a combined range, that is correct, but the sum of probabilities for all these cases is in the below 0.00000...01% of the entire count of possibilities - as demonstrated by your huge generated files. So, a lot of convoluted work to exclude a (relatively few) close to zero edge-cases.

Hello OP,
I'm expressing my gratitude for stepping in to clear out this matter. Obviously, it should be a good lesson for absolutely anyone to always take with a big grain of salt what some users are trying to convince people of their "guaranteed" truth.

For everybody else - make your own judgments always in everything. Most of the claims done in these forums are complete bogus, with no actual underlying rationale to cover it up. Start by grabbing a statistics fast course, don't expect to miraculously reduce space-time algorithmic complexities, unless you change the fundamental hypothesis some way. Otherwise the Universe will just slap you in the face, since it's rules don't work according to our (very bad) intuition and perception.

That's not how probabilities work. The sum of all probabilities is always the same no matter what way you "split" the possibilities.

That's a very complicated way to waste performance, instead of simply generating a single random number.
Numbers do not "convert to hex", they are numbers. Representations convert.

There's zero-proof for your statement. You believe in simulating what? A single observation out of a gazllion choices, each with identical probability?
Statistics work long-term, you can't have a conclusion from a single expected result.
A key with value 0xFFFFFFF....F has exactly the same chances as any other random key. It seems to me you are trying to say that randomness follows some "model", when in fact it's only definition is total impredictibility and any lack of rules or patterns.

Sorry for you addiction.

If you dont trust it, just dont use it. NEVER use any exe you didnt compile

Better yet:
- review the source code line by line, if anything seems suspicious or don't understand it, it's likely a threat on so many levels;
- review the compiler, check all SHA signatures for all downloaded and installed packages (use https to get sigs from authors, verify certificates, compare against results on another computer which you never touched)
- dump Windows. You may have viruses already which you never knew about, or ever will.
- clear CMOS / flash UEFI or BIOS and make sure secure boot is on and  that you never signed insecure kernel modules to load at boot time

Lastly:
- make sure you protect against RF attacks (keystrokes and such can travel a long way in the EM field). Use a mechanical keyboard and a CRT monitor (not a digital display, pixels can be trapped with a correctly tuned analog-to-digital converter and some decoding software)
- for maximal anti-virus protection you need to also disconnect from the internet, run all software on VMs.

Compile everything from scratch.

So your estimated times include the DP overhead?
Because I did a lot of simulations on lower puzzles to get min/avg/max jumps and stored footprints, and, as you can guess, when the DP criteria kicks in, storage goes down, number of jumps until a collision goes up. And there's a lot of ways to improve either space or time, but not both.

So it is not fair to still call the time complexity anywhere near O(sqrt(n)) when you're using 2*sqrt(sqrt(n)) stored items instead of the average 2*sqrt(n).

Steps until a collision can range between expected average / 10, and 3 * the expected average.

And JLP kangaroo is not some godly reference, I did not use it at all, for one I don't even agree with the way jumps and hashmap keys are used, but that's another story.

No one says you need to have 50/50 tames and kangs. And no one says you even need to store the entire traveled distance. There are various techniques.

And those are running on some zero-point module free energy?

No (to all of the questions). Have you looked at the 2**65 keyspace? It's 36893488147419103232.
BTW it only takes around 16 bytes / key to store hundreds of billions of tame kangaroos for 129 bit case.
Ofcourse I'm not simply "printing pubs and privs" to a text file, that's an over-simplification.
If you want some hints: the more keys a hash table has, the less space/key is required.

I think you are kidding with your 9 billion kangaroos. You are missing something critical about the underlying theory.
Otherwise, you can solve all puzzles with 2 kangaroos, if you wait a trillion years.

If you are so sure #120 / #125 were solved with existing software, did you also do the math about how many kangaroos would have been needed? At DP 0 /1 / 2 etc? Your times have no meaning without space complexity attached to them.

Friendly reminder that to solve #130 in 2**65.5 average steps you need to store 2**65 kangaroo jumps (e.g. thousands of exabytes with constant time random access).
If we go with distinguished points space goes down, expected time goes up. There's no free lunch.
Currently testing ~ 500 billion tame kangaroos footprints against wilds, I don't really expect a collision but who knows. I'd need like millions of times more storage.

I don't think #120 or #125 were solved by existing (public) software, it just seems unrealistic from a resources / cost perspective. There's something else going on there.

Hundreds of years.
Once you crack it you'll want to spend it, so you'll have to disclose the public key over the network.
Once everyone sees the public key and knows it has a 66-bit private key, they will crack the private key in
a few seconds at most and double spend, making your efforts completely futile.
So I guess the reward for ruining a lots of hardware and paying for the power goes straight to zero, since everyone will fight to double spend, making the fee higher and higher and the net profit going to zero.

That is assuming pollard kang remains best time reduction algo in the next, say, 100 years. Look, we all have beliefs. I believe cracking both SHA and RIPE of an insanely big number is far less likely than screwing around with EC properties until O(sqrt(n)) goes down in some way or another. We shall see.

Wrong. First of all, #66 is a 65-bit problem. Bit 66 is always 1. Computationally it can be discarded, just like all the known 0 bits.


10 days to find requires 38 TH/s (7% of total current Bitcoin network hash rate)
200GH/s requires 1988 days.

Now, a "hash" means "obtain some EC point for which k is known + SHA + RIPE + check match".  No one said those are zero-overhead operations.

I'd dare to assert that #130 will be found before #66.  I have some theoretical and practical thoughts that make me conjunct that puzzles 135 to 160 will also be found before #66, in absence of any surplus proved bit of information we don't yet know (not non-sense).

I think you have the answer already by looking whether #66 was emptied or not. That is, the creator surely has the public key as he surely has the private key. Otherwise, someone would have used kangaroos long time ago, if pubKey was known.

I think it's pointless to "brute-force" the pubKey. I assume what you are thinking is somewhere along the lines:
1. Find some 256-bit number X (32 bytes) that results in RIPE(SHA('03' | X)) = decodeBase58(address)
2. Use ECDLP solver on P(X, y(X)) since you know it has a known long prefix.

Flaws
- you assume that there's only one X that results in the first equality. Chances are 1 in 2**96 that you'll get an X corresponding to a 66-bit private key. There's 2**256 SHA hashes that map to 2**160 RIPE hashes, so 1 address can be obtained (in theory) in 2**96 ways.
One of those 2**96 X's is the one having a 66-bit key. Most of all others will be in the 256-bit range.
- you're limited by SHA256 computing power of the hardware. Assuming you're after finding a collision, and let's say you have some GPUs providing 10 GH/s you're still looking at around 100 years of more until you find such a collision, which only guarantees you some 1 in 2**96 rate of success.

So to speed-up your search by a factor of 2**96, you'll need to brute-force the private key in order to do (correctly):
RIPE(SHA('03' | P.x)) = decodeBase58(address)
where P is the public key of the private key.

It will still take you same amount of time due to SHA limit above, but you have the guarantee of success.

Good luck.

Related thread: https://bitcointalk.org/index.php?topic=5440058.0

Posting this as a wake-up call about how far people would go to scam you into sending them your BTC.

So this guy (or more probably organization) spammed the internet (multiple domains / websites / GitHub repos referencing each other like crazy) about so-called "attacks" based on actual research. His claims are backed by lots of step by step pictures and theoretical information about the how and the why, making it seem as if it's authentic, but hiding the actual code that would be the attack itself.

His/their latest invention: attack 28, or so-called "dust attack with confirmation of isomorphism"

This blends the harmless but annoying dust transactions method (which can only be used to track links between transactions really) with some magical recently disclosed on the "dark web" method to use Montgomery ladder to create "confirmations of isomorphism" that allegedly forces a receiver wallet to send you back your own wallet balance.

Makes sense so far? Sure, let's digest a little. So you go through endless screenshots from how you setup your environment to make it seem like you're a hacker of some sorts. For ofcourse, this is all made for "research" purposes to prove its validity!

Then sure enough, to make the attack work, you'll need to create and fill your own wallet with as much money as possible. Because as it's already "proven", dust transactions + magical "confirmation of isomorphism" will send you back that same amount back to your wallet.

Ofcourse this is all really advanced stuff, so sure you'll need to create some transaction to send out some dust and provide your private key in some scripts and the attacked wallet's last TXID, because yeah, the research scripts need them to create the "raw transaction" to send out the dust BTC. All this besides the "source code" packaging some weird EC math modules and why not, the entire pip package manager itself zipped in some weird way, to make things smooth. No worries so far...

The steps show you exactly how completely valid this raw transaction looks because, OMG, you can verify it in various 3rd party services like any transaction decoder. Nothing wrong so far, right?

During all this you are indicated that it's very important to shut off your internets while you generate the raw transaction, because oh no, some malicious app can intercept your private key of your wallet (you know, you just filled it with lots of BTC to make you rich twice that).

Then, after reading the 13th time a screenshot and a link to the Montgomery ladder theory (copy pasted from SafeCurves), you have to isomorph the hell out of your 100% valid raw transaction, because yeah math works out and Montogomery issue and why not, and its just revealed on darknet in January 2024 and it's been used in 2022 and everyone is freaking out about it, so this method of making your own dust attack is on the hype today!

But HOW do you create the isomoprhic transaction so that miners (you need two it seems) confirm it and the attacked wallet sends you back double of your funds? Oh well, that is classified material because this guy apparently worked out the Montgomery ladder scriptSig stuff for you, so all you need to do is input your raw valid transaction on his website via a form input! ANd this will return back the motherf**a isomoporhism in a split second!

But because this is very complicated stuff, you do need to replace some bytes in the returned transaction to make it valid again. No worries, the steps are very clear on how to copy paste some public keys and hashes back into that blob of data. Because the magical server script was too busy working out the isomorphism attack so it forgot to do it itself Sure seems very legit so far since ofcourse your own private key is safe and sound, right? You even turned off the internet access to create the damn transaction, and you knew exactly where you send out the dust and the change - back to you.

Then ofcourse you verify the final transaction, with the "twist" that the attack does require you to create a SegWit address to get back your funds. Ofcourse, that is a wallet address you create yourself as well, because you sure as hell can trust the source code, nothing spooky going on inthere. You own the private key!

And ofcourse, at the end you broadcast this valid transaction that will make you rich once 2 miners confirm the isomorphism.

Backed up by this attack are examples of succesfull attacks on 2 5000 BTC wallets! With the raw transaction, and the isomorphic results, and everything you need to be sure this is 100% legit! I mean hard wallets and online exchanges are fighting this attack for years, because llook what can happen!

But at a closer inspection, what the hell just happened?

- you created a transaction for unspent outputs you didn't own, but signed those inputs with your private key (e.g. complete nonsense, though mathematically valid)
- the nonce used for all those signatures depends on the transaction hash, as the source code shows
- you then sent out all of those signatures to some server located who knows where
- got back a new set of signatures from server

Nevermind the fact that the raw transaction "example" provided as a successful attack is the actual transaction that emptied the 5000 BTC wallets, since it contains the public key of the address. The public key was only first ever available AFTER that specific transaction took place, so clearly the example raw transaction could have never ever be created just from the target wallet address.

So the only "attack" this method shows is the "researcher"s attack on your inteligence.
YOUR PRIVATE KEY is easily recomputed by the magical server using either the forged known nonces or probably through the final transaction that you need to "fix".
Your wallet funds will probably be emptied even before you manage to do all the stupid copy-pasting required to "fix" the "isomorphic" transaction.