Do you seriously think a sane person would try to actually calculate that?

I'd say the answer lies in the order of millions or more, since you have all the possible front matches, multiplied by the number of all possible combination pairs of the other criteria (e.g. 2 base58 digits out of whatever many remain after the front digits). Then you scale down to some interval size and apply the approximations of a uniform distribution.

Also, this has zero relevance since I can assure you that whatever two numbers you ever provide, in whatever base you choose them to be, there is always some other common representation that makes them look like they're siamese sisters.

Well, since you found the match, the probability is 100% to have exactly 1 of those prefixes, in an interval of size one, starting at the key you've found.

I really hope you solve any puzzle up to #100. I can definitely re-assure you that the fail-safe methods you'll use will not be proven to be wrong in mere minutes (or rather sub-seconds for trivial problems like #71).

The guy who'd prove you wrong would probably either sleep or be at the beach, not staring on a screen waiting to spin up 1000 GPUs, you know?

Yes, thanks. I noticed that as well. Too bad it’s impossible to parallelize a sequential process. For now, it looks like any restart can affect finding a collision, since we can only detect it on the second occurrence of the same DP along a trajectory — which takes time. I’ve been thinking about this in two ways: first, adding progress checkpoints and setting an acceptable DP threshold; second, deliberately forcing trajectories to reset right after a DP is found. That way, we slightly improve the speed of reaching a DP — though not to be confused with overall performance.
[/quote]

The DPs and the kang's position are already the checkpoints. RC's rightfully outlined that having too many kangs (which is JLP's strategy) increases the DP overhead, so much that it can easily outmatch the core complexity. When dealing with tens or hundreds of GPUs, and a high DP (which is needed to lower storage requirements) that would be a very, very stupid scenario to end up in.

I don't get why you would reset the trajectory once you have a DP. If you read the analysis, the whole argument is that continuing the walks increases the chances of an eventual collision. And this does not depend at all on whether a DP was found or not.

That's a fortunate case. I asked it to count 1 to 100 and it skipped 6. So 6 does not exist, ok?

Though I don't see how this would be an issue for most people that ask it to break crypto.

No, Freddie's song is a homage to the puzzles private keys.

Excuse me, but how do you expect to compute a private key of some point, when the only property you have is something that applies to all the points on the curve?

What's new and complicated is forgetting the basics and switching to "let's compute public keys from scratch, because why not".

I always struggle to understand why would one choose to deliberately drop the speed by a factor of hundred or more, while dismissing less than a fraction of the keys they want to scan

It just makes no sense. I am not talking about concrete drops in speed, but inevitable mathematical slowdowns, since exchanging point addition with point multiplication isn't something that can ever be run "fast" even if you set up a billion GPUs to do the work that would have been done by a million GPUs.

A - B = P

A and B have same Y so are related by B = [lambda] * A (or maybe lambda**2, didn't bother to check which one, it can easily be done by comparing the X ratios)

So you have [1 - lambda] * A = P

To get P's key, you need to know either A's of B's key.

To get A's or B's key, you need to know P's key.

This is the only "advantage" in the equation you want to solve.

If you don't know either key, this property only reduces the discrete log problem complexity accordingly, by a factor of sqrt(6), but only when searching over the entire group order, which is in 256-bit key-space. Hence, only slightly reducing the secp256k1 security to around 125 bits or so.

If the key is in any interval less than 253 bits in size, this property is useless.

Yes. But just when the only information you have is that the private key is anywhere between 1 and n - 1.

In other words: good luck finding the specific pair of points that add up to P (or one of its equivalent X endos).

Unless you burned around 15.000 $ for the last week, did you honestly expect to find one?

The correct expected average is 395013.

For 10000 random ranges of size 2**70, 9999 of them will have between 392679 and 397353 such matches. That is, the probability to have a ≠ 3000 deviation is 0.01%

There are too many zeros for the probability to only find 1353 matches. It's more likely that the entire galaxy implodes today, than the chances to only find 1353 of those matches in a 2**70 range.

I don't wanna be an ass but what happened with JLP's copyright and license in your project? Do you understand what an GPL license implies?

Yeah, that endo property is the reason why a vanity search can be sped up when the actual key range does not matter. But think about it: the SHA will get 32 new bytes for pubKey (X * lambda), so not much to reuse unfortunately. For 02 vs 03 - maybe. But the avalanche effect will inevitably do its job.

I think crypto guys are at a current state where they agree that using the endo as an attack vector doesn't really work. They tried and failed. No one found a way yet. It only helps with speeding up ECDSA verification today, to multiply random points with random scalars.

When I meant compiler, I was referring to the CUDA compiler, not a CPU one. For nvcc, any register in the code that isn't eventually useful (e.g. printed or written to memory) gets its entire traceback code completely removed. No useless instructions ever execute, because, well, all the instructions and all the branches always execute. Also, usually recomputing data ends up being much faster than reusing data. It's crazy.

It won't make it any easier, but it will definitely make it a lot harder, for no reason except placebo
Every time some range gets "split" into 2 distinct ranges of size (N/2) each, by whatever means (subtract into two halves, or dividing pubKey by 2) the total solve time increases by a factor of 1.4142. Imagine doing that 35 times in a row. Worst case, divide all bits and end up with what is basically a brute-force O(n) search.


If we treat a public key as a truly random variable the only predictable inputs would be having the first byte (0x2 or 0x3) and the other 31 bytes of the SHA input block (zeros, padding, and bit length).

But these paths are already accounted for and shrinked when, for example, building a GPU kernel. The same goes with all constant precomputable steps, like the initial SHA state and the round state finalization. Even better, this also continues into the RIPEMD step, and even further, when comparing the desired fnal bits with some constant static H160 target. If some useless dependency between these steps exists, the compiler would remove it already.

For example, if one does not care about the first 32 bits of the H160, trust me, that part of the hash is never computed (unless something else depends on it).

That is why I also stated that since the H160 first spits out the MIDDLE 32 bits before the other 128 bits, some hashing steps automatically never execute (and are not part of the kernel at all).

But the truth is disheartning to prefix theorists since the resulting H160s that match in the middle has no pretty base58 similarities whatsoever.

I managed to find a way to approximate the future (yey to quantum computers).

Only got glimpses for Wednesday, Aug. 22 2029, page 1782 of thread "Bitcoin puzzle transaction ~32 BTC prize to who solves it".

"we ?ust nee? to sim?ly c?eck if the ?rivate ke? is o?d or eve?, the? re?uce the ran?e to ? ?its"

"I w?ll sol?e Puzzle ?? by to?ight, ever?one ?uit searc?ing"

"do?s a??one kn?w if prefi?es are use?ul? we ?an ski? 9?% of ran?e pat?erns"

"its ?ll ? frau?"

"??u do??t un?er???nd ??obab?l??ies"

"w?at ?f we spl?t"

It depends on the CPU. I think 211 kB is larger than the L1 cache, so if you lower the loop count and set the OMP affinity to a single core (maybe through the env vars) I'd say it may run faster.

You can also enable -march=native and various compiler flags like enable/disable AVX512. I experienced different results (better or worse) when playing with these options - for example, with some flags it is much better when running just a single thread, but worse when using more threads, due to AVX bottlenecks.

For specific purposes the speed can go even higher. As it is, both X and Y get computed and converted from 5x52 to 4x64. I would conjecture that a BSGS implementation can be blazing fast with these tweaks:

- Y is not needed (except for the last computed point, which updates the center pivot)
- use directly the 5x52 native representation

Baby steps ("i" index + key hash) would then be stored into the DB (for example the hash can be just the lower 48 bits of X, which is the lower 64-bit limb of the native FE). This will be slow because insertions can't be parallelized.

Giant steps ("j") would then simply run in parallel and do the lookups and collision handling also in parallel (DB is read only). But this requires updating the code to allow a stride size (giant step multiples), which is was, I think, the main reason it was requested by shinji366.

AFAIK this will solve in at most 1.41 * sqrt(b) additions the ECDLP, over a interval of size b, where half of them are the baby steps.

Maybe I will add the stride option in a few weeks and try some BSGS on top. Not a huge priority for me since it doesn't really scale well for high bits.

If it took you a year to grasp why the method works, and still don't get it, I suggest maybe spending your time on more productive things. If it's still unclear after all the diagrams, pictures, and the dozens of academic papers, not sure what more you'd expect (except some magic software that finds solution of 135 in less than 20 seconds maybe).

I'm not a big fan of point multiplications. But the one in that repo is doing it through projective coordinates. Big boys do it via Jacobian since it uses less field operations (faster). For high capacity multiplications, much larger window sizes can be used, for even less operations. And so on, more optimizations depend on how much data can be reused or precomputed.

A few of these concepts are already implemented in stuff like libsecp256k1. However for GPUs directly working with 8 x 32-bit numbers is the fastest possible aithmetic (while for CPUs, the 5x52 is much faster instead due to the hardware latency while carry-adding the big integer limbs).

I think 0.1 isn't cheap. And also you assume that a 4090 can only do 7 GK/s just because that's the fastest public SW. Anyway, 69 was too risky from the start.