To steal something implies that there was a legitimate owner of that something. Be it a physical thing or intellectual property.

Now, if someone is stupid enough to think that they own information which is computable in a way that holds no patents or rights, then they very much deserve a lesson in what "property" means from a legal (social-enforced) perspective.

Now, do you understand what "public" means in the compound term of "public key"?

It means that some bits of information is known to everyone, and it is information that does not have any owner or rights attached to it.

Now, back to basics. Let us say you create a "private key" and you declare yourself as its owner. What rights do you have over it? ZERO.

Did someone buy the rights to use the bits 0 and 1 to represent information and we didn't get the memo?

There is no such thing as an owner of a private key. There is only the art of trying to protect a freaking mathematical number to remain undisclosed.

Now - did someone buy the rights to use numbers? Did someone bought an actual number, and has the legal right to be the single entity in the society that has the rights to ever use it? We didn't get the memo on that as well.

No one ever fought a class suit process because somebody else used some number they wrote on some piece of paper.

EVERYONE owns ALL the numbers that can ever exist. You cannot "steal" a number from someone.

But it is true that stupidity costs a lot. We have a saying in my country: the one who's stupid is not the one who ASKS, but the one who GIVES.

So, if you give out your number, and you worked a LOT to get at it, guess what? You never owned it.

There's no hashing for kangaroo, just plain point addition as fast as possible. Which translates to 256-bit arithmetic mambo-jambo.

JLP's kangaroo for example is definitely not fully optimized when it comes to this. But SHA and RIPEMD hashing were heavily studied and lots of hand-written optimized code exists, so the optimization upper bound is likely reached since long ago and nothing better (faster) is likely, just linear speed-up with better hardware. And even if it is, why the hell would one search for a key that, once public, is broken in a matter of seconds anyway? This is a logic fracture...

This is not the case with secp256k1 P + Q, since the longer the private key, the time to break it increases exponentially, but the computations are the same for any length. So it makes sense for scammers to try to convince naive people to contribute the results of some 256-bit mambo-jambo gymnastics (e.g. the bill they pay for running a GPU at full load) for their own benefit (e.g. build a msssively contributed kangaroo jump points database and simply scan for wild-tame collisions). A true non-scam collaborative effort would require that the finder of the key cannot know what the key is, and the owner of the pool cannot know what the key is, but that anyone can verify that the key is correct. So at spend time, a correct prize is distributed. So something like a ZKP protocol for miners.

I think the puzzles are the least problems of agencies, they definitely have access to special-purpose hardware that is beyond our imagination. If FPGAs to break RSA were already built in the 1970s, imagine how things look for them in 2024. We have chips with hundreds of billions of logic gates in our smartphones and call that high-end. How much processing power would, let's say, some processing "chip" that has the size of a basement?

It's not really so difficult, I started creating a CUDA kernel from scratch. There are lots of things to improve on to the way JLP did it, beginning with the way points are stored and accessed in the memory by each thread, up to the inefficient instructions that are used (why is it using 64-bit? CUDA doesn't have such a thing - instant performance drop right there). The list of issues is too long. I'm not dismissing his work, it just seems very convoluted so it's understandably hard to follow. But still some script kiddie copy pastes such a project, runs make, and than brags about him asking for cryptography programmers to join his Kangaroo2 project, lol.

Good joke, so your business model is to find idiots that mine DP for you. Using software that doesn't even support puzzle 130 anyway. With zero innovations, fixes, or changes to the code, probably because you have zero idea how to even read it. Just adding a "2" at the end. It's also, most likely, not even forked by you.

Can anyone explain why a sloppy modular multiplication is used? The 3rd step is missing, otherwise there exist probability of an incorrect result. Or is it proven that only 2 steps were sufficient (I doubt it)?

For 10 bits and a billion random trials you'll get the number 0 around 976562 times, on average.

If we replace each possible value from 0 to 2**66 - 1 with some emoticon for a thing in the universe, what exactly makes 0 to be more special than some other value? The values are just labels, it makes zero sense to discriminate them. The only valid affirmation you have is that there is a 100% chance that some random value in some 2**66 set of elements is contained in the set. It doesn't matter how you look at them.

Also, it would be weird as well if somehow the maximum probability solution (some value with maximum entropy and with exactly 33 bits of zeros and 33 bits of ones, in some arrangement that has the least possible compression form) is the one that's correct. So, why not exclude stuff from the other end of this mindset as well? It's like: if you throw a coin in the air 100 times, chances are very low you'll get a 50/50, but still, these are the maximum chances as well.

What world do you live in, in which the computer can generate "at least 100 million keys per second", I wanna move there.

If you are simply talking about a private key, then a "computer" can generate "number of cores" * "core frequency" private keys per second, but what the hell are you gonna do with a bunch of numbers?

Do you understand the difference between a public key and a private key, and how the first one is computed through the second one? I mean, all the math that's required is not some simple a + b.

120 exakeys = 120.000.000.000 gigakeys

Pretending some 4Ghz CPU generates, sequentially, one key per cycle (it doesn't, more like one key over 300 cycles on average, and that's with all possible optimizations) it would still take 30.000.000.000 CPU cores to reach that speed.

Or (300 cycles/key): 9.000.000.000.000 cores that are running all at 100% with no OS, nothing else running, all working at full speed doing nothing except crunching numbers inside the CPU registers.

I think maybe that speed reflects space coverage rather than operating time, and space coverage speed is logarithmic not linear.

SHA hashes: 134217728 speed: 7485947 hashes/s

Hashed bytes: 22145925120 speed: 1712 MB/s

So 1.7 GB/s with your everyday SHA hasher is not bad, what's bad is that it's doing a single hash of a 22 GB message, not hundreds of millions of hashes of 33 bytes.
In our case, the hash context needs to be reinitialized for every public key we need to hash, so AVX512 and so on maybe can bring a 50% speed-up, nothing to write home about.

Benchmarked OpenSSL / Apple CommonCrypto and fast SHA with SSE3.2 intrinsics (last one was like 10% faster, probably because of inlining). I would bet that the CPUs that have hardware support for SHA instructions are actually used by the SHA routines available from the system APIs, and we wouldn't need to hack them ourself.

For AVX you'd actually need a distributed scheduling: https://github.com/minio/sha256-simd

That was my point, read carefully the question

Any sort of strategy is useless if you use either Python or ASM as long as any sort of higher-level op like SHA / RIPEMD is the actual bottleneck.

But if we only operate on EC then it's another story, this is where kangaroo / rho / bsgs comes into play, and we can start optimizing the operations that are the bottleneck at THAT level. It's one thing to do a few thousand mul/s in Python and another to do batched additions (with a single inversion) on a GPU, to reach giga adds/second. Millions of times faster for identical results. And ofcourse it's still not enough even at that level, so...

Something to think about on 256-bit modular math:
- a single inversion is ~60 times slower than a multiplication (GCD algo, not a simple operation at all)
- a multiplication is ~2 times slower than a squaring
- a squaring is ~3 times slower than an addition, ~2 slower than a normalization

A simple point addition requires one inversion, 2 multiplications, a squaring, 2 normalizations, and 6 additions.
A simple point multiplication requires a bunch of point additions (in truth, it's somewhat faster bcz of Jacobian shortcut, but still a lot of multiplications).

So stuff like doing point-scalar multiplication is a bad joke, compared to the problem of optimizing the primitives

Is it non-pointless even if writing it in assembler? Some dick size updates: 11 million point additions/s (affine coords). There is a trick that even JLP's VanitySearch is missing which allows for some optimization on batch additions (8.5 Mkeys/s with that one). It's all about the branch processing.

This is very misleading. We only get the result key, not 3.500.000, simply because it does 3500000 Jacobian additions and a single final affine conversion. I don't even need to disassemble the DLL to be 100% sure about this, because the fastest known algorithm to do an modular inversion on 256-bit numbers requires 4000 CPU cycles on my i9 13th gen CPU, which means it can never ever do more than around 1 million inversions per second. But Jacobian point additions? 8 million. But those intermediary points are useless since they do not have any invariant characteristic unless you actually reduce the fractions it holds (so, the expensive mod inverse).

Anyway, all this is completely irrelevant for puzzle 66, even if magically we can do an infinite amount of additions / second, it has zero impact on the speed, because all the hashing required is many times slower than any EC operation.

Did you account for the implicit "1"s I mentioned about?
E.g. in decimal if I give you the number "42" but you also know it's a 64-bit value, there are implicit "0"s in front of 42, if your goal is to make some stats on base10 digits of 64-bit values. Because it would not be fair to only count 0s in numbers such as "402", "420", "81505" and so on.

Same principle for a BTC address. For base58 the implicit symbol is "1" (the first symbol of base58).
This has nothing to do with the "1" which you actually see at the start of an address. And even more, if you have multiple "1"s at the start, all of them are just a convention that says "so many bytes at the start are 0x00", NOT "this so many digits at the front of the base58 representation are 1". So some work is involved here if you truly want to make a histogram on base58 usage (which I don't really understand why you would, it's much more direct and error-free if you just use the binary representation).


Modulus bias. It is not about the random function, it's about the domain size vs. the modulus (base in this case) which is used. base58 is just done like in any other case: divide a big integer, use remainder, repeat with quotient.

The only bias here is about the bias of base58 representation, not on RIPEMD.


I did it in C. PrivKey (sequential) to PubKey to RIPEMD and then memcmp with the static constant target RIPEMD (which ofcourse returns false as soon as the first byte is different, come on...). You CAN't do it faster than this, and it can only scale linearly with thread count. But it's quickly obvious that it's unfeasible, I mean it's the only real way to do it without knowing the public key, but it's both a O(n) complexity AND it involves SHA256 + RIPEMD at every step. That's why I strongly believe #130 will be found next, not #66. Much more room for breakthroughs and exploration there, and while the complexity seems similar it runs WAY, way faster (no hashing nonsense).

btw we need a ton of signatures to break ECDSA, we only have one here. And the nonces are deterministic (checked), so we're screwed.

Not really, you started off from a wrong premise.

RIPEMD: 160 bits. 2**160 choices.

2**160 does not divide by 58 so your probability doesn't take into account the bias for the last remainder (only 52 choices out of 58, hence fewer z w x... was this your secret information to keep for yourself lol?), and neither the implicit "1" characters found at the beginning, when the address is shorter than the maximum length (explaining fewer "1"s). Those leading zeros are actually the character "1" in base58. The leading "1" in the address is discardable since it's just a hint that the first byte of the number is 0, which is always true.

Maybe run the stats on the base2 160 bits instead? base58 strings don't map 1:1 with any bitstring, since there is no power of 2 to divide 58, so their space lengths don't fill each other exactly, e.g. I can give you base58 "addresses" with a length identical to a correct one, but that will require more than 160 bits.

[LE] It's actually worse than this. Because there's 4 bytes of checksum added to the RIPEMD, and THEN it goes into the base58 encoder, we have 2**192 % 58 = 38 as a remainder. So this might explain your findings better. Last symbol is heavily biased, it only covers 2/3 of the possible choices.

It is a known theorem that if two numbers do not divide each other, then bias occurs when using one of them to produce ranges in the other one. Take for example the hidden issues when (naively) doing something like this:

A histogram on r will reveal pretty fast that (assuming random() is uniform) you will have a big bias between the range [0, n) and the range [n, 7}, where n = MAX_RAND % 7. Because there's more possibilities to choose from one range than the other one, due to the remainder.

k pls just hurry up so we can call it a day

I hope you are joking. That is NOT what a logarithm is.

Number: 7
Representing 7 in different ways:
Base 10: 7
Base 2: 0111
Base 7: 10
Base 16: 0x07
Base 1: <potato> <potato> <potato> <potato> <potato> <potato> <potato>

Shall I go on?

Logarithm of 7 in the infinite field of real numbers:
Base 2: 2.8073549221... (infinite number of decimals) - it counts how many bits you need to represent value 7
Base e: 1.9459101490553132... (infinite number of decimals) - it counts how many natural numbers you need that, raised to this power, yields 7

Logarithm of 7 in some modular finite field with N = 3:
log(7) = mod 3 (oh no, this doesn't work, hmm... is it 0? 1? 2? damn, something is missing, maybe we didn't even define the neutral element yet? or not even an binary addition operator?)

So, do YOU know what you are talking about?

If I would be the creator I would laugh so hard about some of the things discussed here.

Guys, a logarithm is an abstract concept, not some math function.

You get a thing called a "base change". In this case we're dealing with a change of base of an element from some position in a finite field (private keys) to an element in the same position in a finite group (EC public keys) and the problem is to solve for the position without a way to go back from the latter to the first (which is assumed to be hard, but not yet proven). And this in the best case that we even have such an element, and not some fingerprint of it (an address), which makes the problem levels of more absurdly difficult. WTF is with the real numbers field log2 discussion, it makes no sense, we already know the ranges double in size at each step, of course any polynomial regression or whatever is a straight line. Dividing 1 by (2**64) is four levels of magnitude below a double-precision IEEE floating point, so what errors do you expect, they will always be after the 64-th zero decimal digit in reality. Nevermind the fact that there's an infinity of real numbers between any two real numbers, so an infinity of computations. Take 7 as a private key and try to solve back from [1/4, 1/8) interval, mission impossible.

This is not an analytical problem, it's a group theory problem.

Too bad the points need to be on the curve. We already know about the endomorphisms.

I'd say any attempt to break a private key that involves more than a constant amount of scalar multiplications (no matter how well optimized by precomputed tables), has very few chances of success.
Any multiplication means, by definition, more than one addition, more time.

Random key -> multiply and match -> good luck waiting.

First level of magnitude reduction: don't do scalar multiplications.

Second wall to break is then the point addition (and there's one more after that, and finally one more after).  I already said too much, but I believe there's something that can run around 20x in less time (fewer computations) if we know the public key and simplify the question.  Some known details around secp256k1 help a lot.

Irrelevant. EC field (x, y) is always 256-bit, so this is the size of the operands always even for private key 0x1. Scalar (private key) size does not matter, beyond the initial multiplication. Jump points are precomputed, so we only have additions. The larger keyspace is only problematic due to its size, it doesn't affect the speed itself. Finding a 30-bit or 256-bit solution runs at the same speed. Actually, you don't even need to have any knowledge of the group size itself, just of the interval size.

What we need is algorithms breakthrough, or lots of coordinated "potatoes" and patience.

No idea, but I can tell you how fast it would go in C using the GMP routines, as I benchmarked a lot of tweaks and misc. formulas.

Close to 690k jumps /s, in-place point addition, no reallocs - this with using lowest level mpn_* routines (assembler optimized).
Around 638k jumps/s with the mpz_* routines.

Compare this to using the routines in libsecp256k1 field_impl.h and same formula steps:
affine + affine: 852k jumps/s (1 inversion, 2 multiplications, 1 squaring)

libsecp256k1 jacobian + affine addition -> jacobian result:
7.5M jumps/s (8M 3S) - removed safety checks since no point is the infinity and neither can be the result)
But... non-deterministic, I struggled for weeks to find a way to use a J point represented in multiple different ways to produce a stable hash, even a single one bit 50% probability hash as a base for deterministic jump). Seems we can only compare two J points for equality or non-equality, comparison result can vary its sign due to Z scaling.

It doesn't matter what Rust compiles down to, it can never ever generate machine code that runs faster than what the lowest level assembler routines can handle.

So we either need lots of threads (GPU) or some special hardware to speed things up.

Breaking the address (pubkey hash) automatically implies searching through the entire field range (~ 2^96 pub keys per address, in the 2^256 field)
Breaking the key searches through the key range.

TL;DR it makes no sense to try to first break the pub key in hope of using that later to find the private key. And it also doesn't make sense to break the pub key if you constrain the search to the private keys range, because this is equivalent to basically finding the solution, not breaking anything, but solving the puzzle.