8 ms·
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 transactio
by mrb 2y ago
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 :)
- motoxpro 2y agoAs much as this sucks, I absolutely love how the blockchain is real life version of a Dark Forest
- nadahalli 2y agoYou will like this 2020 classic piece by the folks at Paradigm: https://www.paradigm.xyz/2020/08/ethereum-is-a-dark-forest https://www.paradigm.xyz/2020/08/ethereum-is-a-dark-forest
- motoxpro 2y agoI have read this and I LOVE it.
- dgellow 2y agoAs 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
- lelandfe 2y agoBroadcasting the secret and it immediately getting annihilated by some anonymous, stronger third party. Very much so.
- deleted 2y ago[deleted]
- Terr_ 2y agoThis 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.
- mandmandam 2y agoThis 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.
- killerstorm 2y agoHow is this "block lattice" secured?
- mandmandam 2y agoQuite 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/ https://docs.nano.org/what-is-nano/overview/ More technical docs: https://docs.nano.org/# 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.
- 2y ago
- fernandopj 2y agoBut 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?
- drexlspivey 2y agoOne way would be to not broadcast the transaction publicly but send it to a mining pool directly
- hoerzu 2y agoPrivate mempool transaction
- nkrisc 2y agoI’m a relatively smart person, probably above average, but glad bitcoin hasn’t taken over banking because I don’t understand any of this.
- a_dabbler 2y agoYou don't need to. Most of us will never understand the complexity of banking either
- zeagle 2y agoYou 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.
- pushedx 2y agoThe 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.
- thrtythreeforty 2y agoWhat is the less-naive way to claim this type of puzzle?
- drexlspivey 2y agohttps://slipstream.mara.com/ https://slipstream.mara.com/
- thrtythreeforty 2y agoAren't you effectively trusting that service not to front run you?
- drexlspivey 2y agoYes, 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.
- thrtythreeforty 2y agoIf 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.
- lyu07282 2y agoSo there is an avenue to sue them / ruin their reputation
- DoctorOetker 2y agoNo, the other way would be for the organizer to author proper scripts that prevent front-running.
- Stagnant 2y agoThat 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.
- Dibby053 2y agoThat 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?
- deleted 2y ago[deleted]
- mrb 2y agoTo 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/ 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 https://privatekeys.pw/puzzles/bitcoin-puzzle-tx
- drexlspivey 2y agoThere 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.
- Dibby053 2y agoI 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.
- 2y ago
- hanniabu 2y ago> 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...
- mrb 2y agoNormal keys can't be cracked as they use 256-bit public keys providing 128-bit security, which is still secure.
- wkat4242 2y agoWell 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.
- hanniabu 2y agoHow is most of the let known of it's a puzzle? Why would people make their progress public?
- wkat4242 2y agoBecause 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 https://news.ycombinator.com/item?id=41547443
- dheera 2y agoBut I guess this means that all Bitcoin transactions have half the entropy we think they do?
- drexlspivey 2y agoAll security assumptions on bitcoin rely on 128bit entropy (256 bits in a private key divided by 2)
- rkagerer 2y agoHow 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?
- fragmede 2y agoThe bot was written specifically to steal the winnings of the puzzle.
- aaronmdjones 2y ago> 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).
- GTP 2y agoIt 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?
- shakiXBT 2y agoThat'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
- Dylan16807 2y ago> 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?
- GTP 2y agoThe 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.
- funnyfoobar 2y agonoob here: but are not the public keys anyway available on block chain? that means literally every thing can be brute forced?
- rtkwe 2y agoThe 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.
- the_clarence 2y agoYou 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"
- rtkwe 2y agoNo 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_logarithms https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_...
- the_clarence 2y agoWait 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.
- rtkwe 2y agoThe 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.
- the_clarence 2y agoHalf of 2^66 is 2^65
- 2y ago
- jamalaramala 2y agoLet 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???
- KMnO4 2y agoIf 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.
- quentinadam 2y agoNo 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.