Hacker News Reader

Comment by mrb | Hacker News Reader

No private key was posted too early. What happened is the person who spent all the computing power to brute force the 66 bits broadcasted, naively, a transaction to send the 6.6 BTC reward to his wallet. However, when doing so, the public key is by design revealed on the blockchain. Someone's bot whose sole purpose is to steal this puzzles rewards was monitoring the blockchain and spotted the transaction before it got confirmed (on average confirmations occur every 10 minutes), then it processed the now known public key from which the private key can be recovered in 2^33 operations (2^(n/2)), then crafted another transaction to send the reward to his wallet, with a higher fee, so his transaction got confirmed, instead of the discoverer's lower-fee transaction.

This is a well-known attack. The discoverer was sophisticated enough to brute force, but not enough to know about this risk :)

View on HN

This is another useful example to have handy against the canard: "You're only skeptical of cryptocurrencies/blockchain because you haven't learned enough about how they work."

I believe the correlation is the other way around... at least once you get past some early local maxima near "people who don't understand how money can be in a computer."

P.S.: To digress (rant) a bit: The linchpin is whether your system needs to allow anybody to create and control any number of new participant-nodes at any time. That fundamental requirement is actually very rare, and it's also the root causing a cascading tree of workarounds, compromises, inefficiencies, and risks.

This attack wouldn't have worked in a mining free, fee-less cryptocurrency with sub-second confirmation times (ie, block lattice).

The only reason we're still talking about BTC is bag-holders. It's vastly technologically inferior on every metric.

Talking about BTC's failures as if they exemplify cryptocurrency is just like attacking solar panels on the basis of whale oil's flaws.

How is this "block lattice" secured?

Quite well, thank you! Coming up on nine years without hacks, and apparently quantum-resistant.

The next release of Nano (the original and best imo*) manages spam to the point where fee-less sub-second transactions can be maintained even while under a directed spam attack.

If you want to learn more there's plenty of documentation:

Overview: https://docs.nano.org/what-is-nano/overview/

More technical docs: https://docs.nano.org/#

* - I love how it was distributed, and the team are extremely focused on making it work at a "commercial grade" as opposed to working up hype.

I was wondering where your previous comment was heading - I assumed you were referring to Yet Another Niche Cryptocoin, and that was confirmed. Thanks!

People said the same thing about renewable energy for decades ... "It's so niche! How could it ever replace fossil fuel?".

The point stands - BTC's limitations mean nothing to the potential of digital currency as a whole. Cryptocurrency has been proven not to need fees or mining, and yet people love to attack it on that basis. Anything to feel superior I guess.

It’s not about superiority, it’s about the pie in the sky claims made by crypto, none of which have demonstrably helped real world use cases at any scale.

Even taking your example coin, they’re making it production-grade, for what? How many people seriously use it? What is the real plan to adoption? Or is it just another fun tech project.

Each transaction uses a tenth the energy of a credit card, confirmed in milliseconds. It's decentralized. It's secure. Isn't controlled by a shadowy entity working to hoard wealth and power backed up by military threat. Etc.

Why am I doing basic research for you?

These aren't "pie in the sky" "claims", they are statements of fact that can be verified by trying it out yourself. I already linked the docs if you want to know how it works, what the upcoming milestones are, what work has already been done, etc.

One example of a great use case is Nano-gpt(.com), where you can try the latest AI models straight away and pay by the question. The bottleneck here is your imagination.

My point about the features you claim have to do with adoption and scale. You don’t need crypto to make a more efficient payment network.

Regarding nano-gpt, that’s already a solved problem. Literally all API platforms support pay-as-you-go credits. I went to your link, and I loved the irony of them asking for a 0.10$ minimum deposit - note the complete lack of crypto rates. That is par for the course for crypto apps, nobody cares what the coin conversion is - it’s just a gimmick.

> nobody cares what the coin conversion is

TBF, that particular data-point tends to have a "damned if you do, damned if you don't" extrapolation, ex:

1. "If sellers only care about what regular currency it can be turned into, that means it has failed as a currency because it's just an intermediate payment scheme."

2. "If sellers don't care about what regular currency it can become, that probably means it has failed as a currency because it's really just a speculative-bubble asset."

Sure, but it’s really easy to list both - even that almost never happens.

imo nano had it's time in the limelight to shine and has just slowly died out.

The Raiblocks and BitGrail hack sealed it's death.

Raiblocks was never hacked, an exchange was (though it could have been an inside job, and BitGrail was at the very least negligent). Very different, though yes, still damaging.

And this isn't about personal beliefs, market cap, market share, etc. The conversational point was that it's technically vastly superior to BTC, which it undeniably is. On market cap, adoption and hype, BTC wins hands down, for now, but there's no reason at all for that to always be the case.

People here love dunking on cryptocurrency for the slow times and the mining and the hacks (like this post) - yet none of that is a necessary characteristic of cryptocurrency.

Btw, Nano is very much alive. V27 is coming out soon making major improvements, regardless of like, your opinion man.

I love crypto, not dunking on it.

The FranciscoTheBomber admin of BitGrail should have served prison time over the entire thing. He got off basically with zero consequences.

Nano will never be in the top 100 of crypto projects ever again. That's just a fact.

> That's just a fact.

Do I need to paste the definitions of fact, vs prediction, prophecy, belief and opinion in here?

I remember hearing similar pronouncements presented as 'ironclad fact' after Mt. Gox, and after the DAO hack, and even during the Bitcoin Cash debate. The field is more full to the brim of people presenting opinions as fact than I would ever have believed. Even if you were someone I'd heard of and respected, a known expert; if you claimed your opinion in this space as fact I would yawn and put my respect for you down a notch.

And, the discussion wasn't about market cap, top 100, or anything like that - just verifiable technical characteristics.

The scam talked about in this thread wouldn't work in Nano, because Nano doesn't require mining or fees. Many other coins have the same characteristics, Nano was an example. I would bet that any other example would have been just as triggering to people.

As much as this sucks, I absolutely love how the blockchain is real life version of a Dark Forest

You will like this 2020 classic piece by the folks at Paradigm: https://www.paradigm.xyz/2020/08/ethereum-is-a-dark-forest

I have read this and I LOVE it.

As long as it isn’t used for anything in the real world, I agree. It’s a fascinating ecosystem to watch from far away. If the crypto bros get their way and integrate blockchains with the real world, that becomes a horror show

Broadcasting the secret and it immediately getting annihilated by some anonymous, stronger third party. Very much so.

That must hurt. In case I crack the next puzzle... how should I go about collecting the prize without having to mine a block myself or trust a miner not to screw me over?

To avoid this risk: either you solo mine your transaction, or you submit your transaction to a mining pool that will not broadcast it to the P2P network until it is mined. Some pools offer this as a service (eg. https://slipstream.mara.com/). This is kludgey but this is because the puzzle is inherently limited by its technical design.

Note that this issue doesn't exist with puzzle numbers that are multiple of 5, because these addresses have their public key already known. So everyone is on a level playing field. The multiple of 5 have been solved up to #125: https://privatekeys.pw/puzzles/bitcoin-puzzle-tx

There is also another puzzle for finding a sha256 collision, the address script just checks if the 2 inputs are different but have the same hash and if true it unlocks the coins.

That one is even easier to steal because it doesn't even require a digital signature and there are tons of bots out there inspecting live transactions and if they don't require a signature they just create a new transaction with an increased fee and their own address as recipient.

I didn't know there was a formal service for it, that's very cool. Still, it relies on the miner keeping its word instead of cracking the private key. In practice it would definitely not bother risking its reputation like that, but I wonder if there's way around it, with smart contracts or something.

I am not a bitcoiner, but I think there is a way to have transactions on bitcoin that are the hash of the script you want. So maybe you could submit the script hash and then submit the script in the next block? IDK if how that would work but I overheard some sort of hash-of-script functionality described by bitcoiners to save space. Hold on, let me see if I can find it.

Edit: nevermind, I got confused with P2SH: https://learnmeabitcoin.com/technical/script/p2sh/ pretty sure you can't unlock outputs with a hashed script unless the creator of those outputs did it ahead of time.

That is correct. Basically you have to get lucky that after submitting the transaction a new block would be confirmed within 1-2 minutes which I think is around the timeframe what it will take for a top consumer GPU to bruteforce the private key.

I'd be curious to know if it is possible at all to "securely" send the funds of these puzzles or if there is some hard limit that requires the pubkey to be published with the transaction.

> processed the now known public key from which the private key can be recovered in 2^33 operations (2^(n/2))

So anybody that has sent a transaction can have their private key cracked just from their public address? How is this considered secure? That's absurd...

Normal keys can't be cracked as they use 256-bit public keys providing 128-bit security, which is still secure.

Well this isn't a normal key. It's a key with extremely reduced entropy for the sake of the puzzle. Most of the private key is already known and is in fact all zero.

So this would not be possible with a normal Bitcoin transaction with regular entropy.

How is most of the let known of it's a puzzle? Why would people make their progress public?

Because this is how the puzzle works. Most of the key bytes are zero. Only the last 66 had to be guessed. And their solution was made public by doing the payment.

mrb describes it better: https://news.ycombinator.com/item?id=41547443

But I guess this means that all Bitcoin transactions have half the entropy we think they do?

All security assumptions on bitcoin rely on 128bit entropy (256 bits in a private key divided by 2)

Is that true for all of the future? I suppose it's only a matter of time before Satoshi's and all the lost wallets will be broken?

Even if it's 70 years from now before we have the compute to do that, the wallets will be worth so much by then that whoever does that will end up with a level of money that is high enough to menace and threaten entire countries if they are malicious.

Why doesn't Bitcoin require keys to get longer over time? Require 256 bit now but require 65536 bit in 20 years to make any transaction?

How would you enforce this to cold wallets? The owner would still have to prove their ownership with the old key.

I think you underestimate how big the number of 2^128 ECDSA operations are. It is 20 orders of magnitude bigger than the puzzle that was just solved (that took 2 years). There is no way we scale our compute that much in 70 years unless we start building Dyson spheres.

To answer your question that change in bitcoin can happen at any point in time with a protocol update. It would probably won’t even require a hard fork, a soft fork would suffice.

> no way we scale our compute that much in 70 years

Huh? Ask someone in 1950 if we would ever achieve petaflops on a desktop-sized PC. Yet here we are with H100's. About 10 decimal orders of magnitude faster than the state of the art in 1950.

Quantum computing will also happen, and I think 70 years is more than a realistic time frame.

The bottleneck is energy you can’t scale human energy consumption by 20 orders of magnitude (not in 70 years anyway). There is just not enough of it.

Effectively, yes.

Well, no, because "we" think it has half the entropy their length implies. This is widely known, and the length was selected with that information in mind.

But how could he have avoided this attack? I'm only familiar with Bitcoin's blockchain on a begginner level. But I assume the only way would be to avoid revealing the answer key (public) when sending the transaction to get the reward?

One way would be to not broadcast the transaction publicly but send it to a mining pool directly

Private mempool transaction

I’m a relatively smart person, probably above average, but glad bitcoin hasn’t taken over banking because I don’t understand any of this.

You don't need to. Most of us will never understand the complexity of banking either

You mean the one where someone else pays a higher ATM fee and scoops my cheque deposit? We can talk about reduced bits in the puzzle vs a regular transaction but when you need to consider how you are going to safely claim your money as if you are laundering you have to admit this is a little nuts.

The only reason that this opportunity exists to swoop in and forge a transaction is that the reward in question is a reward for fundamentally breaking a weak version of the cryptography underlying the BTC blockchain, the technqiue for which happens to have a second mathematical weakness.

No other transactions are subject to this weakness, and it's this puzzle which proves that.

idk $34 billion in annual global card fraud is also a little nuts.

You're discounting how nuts it is that a third party has veto over whether you can spend your money and how.

I think it's part of living in a society with rules and law. It also protects me from rampant fraud and theft and also helps ensure taxes are paid for the benefits I use like roads, hospitals, and education.

You can run your own node and then mine the transaction into the block or use private pools.

Look up MEV

I've never used any coins in my life, but I think what is unique here is that the reward IS the entire wallet itself, not just a transaction from the "contest holder". They revealed many of the bits of the private key already. Somehow, you cannot use the wallet without briefly revealing the rest of the private bits.

Yes, no such thing as dark pools in traditional finance /s

There is actually no way to avoid this, aside from setting the Fee nearly to the reward.

It's essentially MitM all the way down.

even the private mempool can attempt a double-spend with a larger fee, get one transaction ahead, then try to maintain an edge long enough to be the "longest branch" for consensus - the 51% attack only needs 33% in reality, much less when your the private mempool that can take advantage of the birthday paradox to jump two blocks ahead.

you have to literally mine your own coin with the reward transaction included.

of course, zpk+ would solve this issue entirely.

Alice and Bob wouldn't ever doubt each other again.

Of course, you could avoid this entirely with Hedera HBAR and fair consensus on the hashgraph. But the puzzles are on BTC where the money is.

Isn't this a bit insane? Does this not imply the entire Bitcoin protocol is fundamentally flawed?

No because it is not normal to have such low entropy for private keys. It wasn't designed with these puzzles in mind, nor should it be.

Your reply and Jerrrrrrry's closed this understanding for me.

The attack itself can't be mitigated because there's the incentive to try to force the blockchain with your own theft block because your fee is much higher for what appears to be the same transaction. But this attack, like you said, is only feasible for this niche domain of low entropy private keys.

The bitcoin protocol isn't fundamentally flawed, but it is fundamentally outdated. If it wasn't for public bitcoin/crypto FOMO, bitcoin would have been deprecated years ago.

It shouldn't be so easy to derive a private key from the corresponding public key. Is the attack you're referring to working because most of the bits of the private key are already known or am I missing something else here?

That's precisely what happened, knowing the public key of an address is commonplace (as long as the address has done at least one tx) and doesn't compromise the security of its private key

> It shouldn't be so easy to derive a private key from the corresponding public key.

What specifically are you calling "so easy"?

If we're talking about "2^(n/2)", I don't see the problem. Why shouldn't it be that?

The problem is that OP specifically said 2^33, which is quite darn easy. I didn't immediately realize that he was saying so just because, in this specific case, only 66 bits needed to be found, which indeed gives 2^33 by applying the usual formula.

You need 2^65 operations so this is likely not what happened. What you're thinking about is the birthday attack that only works to find collisions and not to find a specific "pre-image"

No knowing the public key reduces the number of keys you have to attempt to find the corresponding private key. If it required the same number of attempts they would have just found it first without having to wait for the broadcast to snipe it.

https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_...

Wait Pollard rho runtime is based on the order of the group not the size of the private key. Maybe there's more to it? This strikes me as more of a hidden number problem. But to make it work you need to observe something using that small number. A transaction might have been enough.

The exact details are beyond me but knowing the public key cuts the required private keys you need to test in half. Public keys are included in the transaction but normal keys have enough bits they're effectively protected even with their raw entropy cut in half. 128 bits are still more than you can effectively brute force but the 33 bits left for this challenge is far easier which let the attacker snipe the reward by exploiting the low fee offered on the original solve message sent to the transaction pool.

Half of 2^66 is 2^65

I meant the entropy in bits is cut by half.

It's very easy to make sqrt(n) DLP solvers for known subranges.

Here is a trivial one:

In advance, make a table of all the pubkeys xG for secret key s = (0,2^33].

When you get a target key T, compute T - (2^33)xG for x = (0,2^33] and look up the result in the table.

When you get a hit, you've found the private key for T it's (2^33)x + s.

Of course, this is a trivialized example, many optimizations are possible and you can specialize any generic DL solver to work in a known range.

But that's not the range in question, this one has 66 bits. You're describing a meet in the middle attack but the runtime would be too high

My example is specifically for a 66-bit range. There are two loops in my post, one removes 2^33 multiples of 2^33, the other builds a table to check for values with a 33-bit range. My example will find a solution in a 66-bit range using only 2^34 point operations and 2^33 table lookups.

Work thought it, I think it'll be more informative than me simply repeating myself further. If you're still confused, ask specific questions and I'll be glad to answer.

Oh right nevermind. For about 300GB of data. I would assume this is what they did them

How would said bot have recognized this transaction was one of these puzzles, and thus worth brute-forcing?

Given only a random public key, is it possible to quickly recognize when its corresponding private key has weak entropy?

The bot was written specifically to steal the winnings of the puzzle.

> Given only a random public key, is it possible to quickly recognize when its corresponding private key has weak entropy?

No, but it is possible to quickly recognise that it matches a published puzzle address, which is derived from the public key. And the amount held by that address is public knowlege (it's on the blockchain).

Let me see if I understand it.

If someone knows that a given address has a huge sum of money, they can create a bot to monitor that particular address, overriding any transactions to his own address?

Would that be possible???

If you have the private key you can send money as you see fit.

The purpose of the puzzle is to find the private key given only 75% of it.

Let’s imagine that takes 1 year to brute force the last 25%. But if you have the public key as well, it only takes 1 minute.

As soon as the coins were sent, the private key was known since it inherently revealed the public key.

No that’s not how it works. When a transaction is submitted on the blockchain to withdraw funds from an address it needs to be signed by the private key and it exposes the full public key. A bot that would monitor such transactions would therefore see the public key. With just the public key you can’t create a valid signature, you still need the private key, however for this particular case, knowing the public key reduces the entropy of the puzzle by a factor of 2 (from 66 bits to 33 bits), so this puzzle was easier to solve for the bot knowing the public key published by the person who found the private key. This is very specific to this specific puzzle which had 66 bits of entropy. In general, bitcoin transactions have 256 bits of entropy.

What is the less-naive way to claim this type of puzzle?

https://slipstream.mara.com/

Aren't you effectively trusting that service not to front run you?

Yes, the only other way is to mine it yourself. They are a public company that run their own miners if it makes you feel any better.

If you were designing this puzzle, could you do better so that this wasn't necessary? Maybe a two step protocol:

- Send some money to an address, which would temporarily stop accepting money from anywhere else. The fee gives the sender the exclusive right to solve the puzzle for, say, 15 blocks.

- After that transaction is validated, a second transaction (which now cannot be forged by bots) can be sent through.

I am pretty sure you could do something like this on Ethereum but I don't know if the BTC protocol would allow this. I also know very little about the guts of the respective VMs in general.

So there is an avenue to sue them / ruin their reputation

No, the other way would be for the organizer to author proper scripts that prevent front-running.

Please provide substantive feedback, I don't mind a downvote, but there is no learning opportunity without feedback content.

I wish HN eliminated downvotes without posting associated feedback

I stand by my point: pay peanuts, get monkeys.

If you don't take extra measures to ensure the safe reception of the reward, don't be surprised your security gauge turns out sticky.

How much would the solver have paid as a fee if he had used this service?

noob here:

but are not the public keys anyway available on block chain? that means literally every thing can be brute forced?

The puzzles have a set number of unknown bits smaller than the total key length making them more vulnerable to these attacks. For true unknown keys the reduction in your search space doesn't bring it down into the range where it's computationally possible to do.

Reply on news.ycombinator.com