Lmao it was a simple example to show why some algorithms are faster. And yes scalar multiplication is slower than point addition otherwise give me proof.

Looks like you also fall into the category of people who cannot read properly. Lmao.

@Cricktor — With all due respect, maybe it’s better to stay out of topics like these if you clearly don’t understand how ECC actually works. You didn’t even attempt to answer the question. The user asked why a low-bit private key can be recovered — and your answer was just name-dropping “BSGS” and “Kangaroo” with zero explanation. What's the Point in answering if you cannot answer a simple question?

As for the answer to the original question:
Suppose your search space is from 1G to 20G, and the target private key is 14G.
Let’s say the final hash160 of the public key is: 726d44b7af8228257c030bafe764d3c5839d5c02


This hash is derived via RIPEMD160(SHA256(pubkey)) therefore any arithmetic on it will be useless.
The only way is to try every private key:
1. 751e76e8199196d454941c45d1b3a323f1433bd6
2. 06afd46bcdfd22ef94ac122aa11f241244a37ecc
3. 7dd65592d0ab2fe0d0257d571abf032cd9db93dc
…
14. 726d44b7af8228257c030bafe764d3c5839d5c02 (match)
If you started from the beginning this would take us 14 operations, from the end 7 operations.
Thats why we say the runtime of bruteforce is O(N) where N is the number of candidates in your search so you have to do at worst N operations.

__________________

Baby step giant step

Now suppose you’re given the actual public key, like: 03499fdf9e895e719cfd64e67f07d38e3226aa7b63678949e6e49b241a60e823e4
or in affine coordinates: P(499fdf9e895e719cfd64e67f07d38e3226aa7b63678949e6e49b241a60e823e4, cac2f6c4b54e855190f044e4a7b3d464464279c27a3f95bcc65f40d403a13f5)


Because you now have an actual elliptic curve point, you can do math with it.
You precompute a table of baby steps:
map[G * 1] = 1 
map[G * 2] = 2 
... 
map[G * 10] = 10

Now you walk backward from the target using giant steps:
Q - G * 10 → check if in map 
Q - G * 20 → check again 

So in our case:
1) 14G - 10G = 4G | Is 4G in the map? Yes → index = 4
Then we can calculate the real private key by doing tablesize * iterations + index, so 1*10 + 4 = 14
Again, scale this up to a babystep table of 1 billion then you can check 1 billion keys in less than a second, thats why its much much faster than bruteforce.

As for pollard kangaroo it works kinda differently, but the actual operations are much much slower simply because scalar multiplication is needed where in bsgs - you can do it with point addition.

What he said is technical misleading. A mutex might not strictly be necessary if you use atomic operations, but you need some synchronization, otherwise its data race and therefore undefined behaviour in C++/C.
Im not claiming to be any good at coding (even though I coded when since I was 12 and I have an education in it) - but that statement from Alexander was just misleading.

Btw, thanks for your answers on my rust question weeks back. You were 100% right. Batched affine point addition (using montgomerys trick) is the fastest possible way to generate as many points as possible - thats pretty much what JLP/Cyclone (what everybody talks about nowadays) is doing. I implemented Montgomerys trick on affine points (in montgomerys form) and surprise surpise - 44 Mkeys/s (with avx2 sha2/ripemd) - so pretty much on par with cyclone - except for the fact Ive implemented the math myself using a highly optimized C library - and the code does not suck that hard like on Cyclone.

take care

Hey guys,

I've been relatively new to the cryptography space and read many things about ECC and coded BSGS and kangaroo successfully in rust.
However, since im using the k256 crate, performance is not really there (compared to keyhunt or cyclone).
According to my tests, sha256 and ripemd160 are less intense than the creation of the public keys (or the affine points on the secp256k1 curve to be specific).

So I think I need to optimize the core ECC operations. What I know is that:
- Affine points are the (X,Y) coordinates on the actual curve
- Projective points (X,Y,Z=1) additions are computational cheaper than affine point addition / multiplication
- Using some batched inversion at an amortized cost to convert affine points to projective points helps increasing performance

However, even when keeping at this in mind, I roughly generate 2MKeys/thread using k256 and using 12 threads basically results in around 12MKeys/s - so I thought are there more algorithms which could be used along with k256 or do I need another library to generate those points quicker?

I read that many cpp implementations use the base of jean-luc pons, but I don't really understand what's going on there. The only thing I see is that he basically precomputes G points from 0..255 (+ and -) but I'm not really sure about the math behind it - but it seems to be faster because keyhunt (which uses his implementations) runs at 35Mkeys/s on 12 threads and 5Mkeys/s on 1 thread (normal bruteforce).

BTW: When I talk about Mkeys/s, I literally mean million points per second (no bsgs or whatever) - just to messure how many public points I can create in a second.

Any ideas, libraries, tutorials or whatever would be appreciated!

cheers

Not sure why it's useful to know how many prefixes of exactly 10 matching chars exist within the 66 key space, since public keys are distributed randomly within the curve and since the ripemd hashing loses information anyways I would not consider this helpful in any way. However, log2(58) = 5.858 * 10 = 58.57 bits, so for 66 bit range 66 - 58.57 = 7.43 so 2^7.43 equals approx. 172 possible prefixes.

However, how is that useful?

This is only partly true. The only thing a GPU is better at in this scenario is higher electricity costs.
GPUs can do insane amount of parallel work and thats because the Pollard Kangaroo algorithm is statistically faster than BSGS on a GPU, because the nature of the algorithm relies on collision delection and random walks. However, there is no garuantee that you find said solution in sqrt(k2-k1) steps.

BSGS on the other side, receives its performance due to a big precomputed baby step table. This means for every known public key in the table, you can reduce the number of ECC operations (which are known to be slow, even when optimized).
The only constraint here is available memory so in practise this means BSGS will most likely never achieve perfect runtime simply because there is not enough memory in the world. However, if you have high CPU cores and high RAM - it most likely performs better on CPU than on GPU due to more memory available.


Well, the fact that you realized how hard it is, to crack the ECDLP, even when the problem is made much easier on purpose is valuable. That means you most likely understand now the main point of those puzzles.

Ah right my bad, you're 100% correct. As soon as the transaction is broadcasted to the network it becomes publicly visible.


The closer your transaction is to being mined (i.e., the shorter the remaining time in the current block cycle), the less time the attacker has to act.
My idea was to reduce the time any potential attacker has. Maybe I'm wrong though, still learning about blockchain
In the end, it doesn't really matter until anyone finds a low entropy private key.

I guess it's still mostly speculation of what exactly has happened to puzzle 66.
But in short, let's assume you got really really lucky, and manage to find the private key of puzzle 67, convert the hex private key to wif, login via Electron and start a spending transaction.
As soon as there is a confirmation on the blockchain, the corresponding public key of said wallet is exposed to the public and it's not really hard to write a bot which checks the latest transaction history from any wallet.
That means, if some bot manages to get the public key in time, bruteforcing the private key via bsgs or kangaroo algorithm is not very hard and on any modern gpu would not take longer than a couple of seconds to minutes.
So any stealer can then replace your transaction with higher sats which means the blockchain will prioritize those transactions and you receive nothing.

To answer your question of which puzzles are "safe": Any puzzle with high enough entropy which cannot be solved via bsgs/pollard rho/pollard kangaroo within 10 minutes is a safe bet.
However, keep in mind that each time a puzzle is solved, the next one essentially doubles in difficulty, that's why it currently makes little sense to attempt to solve puzzle 68, 69, 70, etc. or 160 via kangaroo.
Stick with either puzzle 67 (normal bruteforcing) or puzzle 135 (kangaroo, not BSGS because BSGS is useless here).

What to really do if you manage to solve low-entropy puzzles
Again, highly speculative but as far as timing goes right - each block is mined approx. every 10 minutes. So if you get your timing right, you should be able to do the spending transaction and the next block is mined within the next seconds which should in theory increase your odds of claiming the reward.
Apart from that, I would likely try to get my timing right and combine it with Mara's slipstream, which I personally have never used, but will when I manage to find some private keys.

In any case, document anything carefully with evidence that YOU found the private key of said wallet which could be viewed at later on if anything goes wrong.

Best regards

Most likely not. I even wonder how you were thinking that anyone would pay $200 for a program which is said to find the solution of btc puzzle 67 which in return is, around $600k. My alarm bell would ring hard.
If it's a shitty python script then don't even waste your computational resources with it. If it's just generating random addresses from any private key within the range begin and range end - also don't waste your time due to the birthday paradox.

I wonder why people always come up with such stupid statements and I'm so sick and tired of it.
We are talking about the 67 bitcoin puzzle which has approx. 73 quintillion possible solutions. ECC operations are slow, even if optimized.
I'm a rust developer and I optimized every possible ECC operation, yet my programs don't match the speed of albertos keyhunt (even though I'm using optimization techniques like point addition rather than scalar multiplication).
There is no shortcut to iterate over the entire keyspace faster. You only can reduce the needed steps to find the solution if you can make use of some algorithms like BSGS or Pollard Rho - However, currently we can only use those algorithms on known public keys due to the nature of these algorithms (so 135 and above).

I'm sorry if this came out rude - but my code is likely faster than your program and I would never think about to sell it for even 1 cent. That's because it's far more likely to get hit by lightning rather than finding a needle in a haystack of 73 quintillion keys with the current computational limit of home PCs.