Am I correct in assuming that beyond a certain point, this is basically an existence proof for somebody having a quantum-supreme solution to Shor's Algorithm?
"Here's $400,000 sitting on the table, hope nobody takes it" which triggers an alarm telling us to replace all our old prequantum cryptography.
If anyone developed a solution to integer factorization, I'm sure they would be after larger prices than mere 400k in crypto. A practical application of this puzzle could be to have an estimation of how long it takes to break a public key by conventional means. The moment one of these prices can be claimed in mere months you know it's time to double the size of the Bitcoin public keys.
If you want to prove that somebody has the ability to pick locks in order to protect your valuables, you leave the prize sitting on the kitchen table (at 66 bits of entropy) behind your relatively easy front door lock, not in a secure vault with triple redundant mechanisms. Somebody with the solution is going to be able to claim the money in far, far less computing time than they could claim a larger prize by breaking industry standard prequantum key sizes.
The $400,000 is an inducement for any participant in that engineering effort to break the conspiracy and take the bag. It's effective during the period between the time that a quantum Shor's solver has been achieved for a given algorithm in theory for 256 bits (and in practice for 66 bits), and the time that a practical solution at 256 bits has been implemented.
Let's say a given intelligence agency's quantum computing efforts have Shor working for 16 bit keys in 2025, for 64 bit keys in 2028, for 128 bit keys in 2033, and for 256 bit keys in 2038. Let's say competing intelligence agencies are 1-3 years behind. Let's say we make it to Puzzle 69 over the next four years. Nice.
I don't know how plausible that timeline is either in spacing or accuracy.
Sometime in early 2029, a bunch of people suddenly find that they're eligible for a $400,000 cash prize if they manage to secretly steal a bit of time on a working quantum computer. In 2030, that group of people doubles, and incorporates a new agency with its own security weaknesses. By 2031 we're talking about four separate countries with their own engineers that have managed to achieve the capability to claim that cash prize. Private corporations are somewhere on the horizon. Very soon this becomes an urgent imperative to anyone inclined, because the prize, like cash, disappears the moment that somebody else seizes it.
It's hard to keep conspiracies, particularly with a verifiable open offer of large amounts of highly portable money on the table to the first person to reveal secrets, and a gradually widening circle of access. The gradually expanding circle of access is what ensures we get some kind of alarm LONG before 2038. Keeping that secret to even 2033 requires hundreds of people and four agencies with diverse motivation and values to consistently turn down cash money for years on end in the interest of keeping their quantum capabilities hidden from the world.
Based on the other comments, is that true? The top comment here implied that the puzzle explicitly had a private key with all 0s except for 66 bits, so that lock was definitely weaker than a key with all bits unknown, right?
Why should the analogy consider each key as a different brand of lock? Each key needs to be cracked separately, but you can use the same method for all of them (assuming one finds a general method and not one based on some property that only a subset of the keys has). So it should be akin to locks of the same brand, using different keys to open them. But that, being of the same brand, can be picked in the same way.
Perhaps each key is not a different brand, but given that the puzzle had only 66 known bits, it seems equivalent to knowing what some of the cuts are on a physical key.
I just think maybe public key crypto is not broken so far because there is no motivation for enough people to work on that. What whould one get, without endangering himself, if he breaks integer factorization?
>Or whoever created the puzzles leaking their information.
Or getting hacked. This is super common among people who are known to have high value wallets. Between physical attacks and zero days in everyday software, there's no chance to stay safe when you put that kind of target on your back.
> there's no chance to stay safe when you put that kind of target on your back.
Vitalik Buterin seems to be a counter example here, his net worth peaked around $1.46 billion. He has some interesting writing on how he stays secure. At one point the SHIBA token sent a huge amount of funds to his cold wallet and he details what he did to securely access those funds:
> The funds, he said, were initially in a cold wallet in the form of two numbers written on separate pieces of paper. Buterin said he had to combine the two numbers to get the private key. "One of those numbers was with me; the other number was with my family in Canada," he said. "So I had to call up my family in Canada and tell them to read their number to me."
> Buterin said that he entered the numbers into the computer he purchased from Target after putting the two numbers together. "I sent my ETH out by generating a transaction and then on a computer that I bought from Tarjay [Target] for about $300 bucks for just this purpose."
> Before disconnecting the laptop from the internet entirely, Buterin said he downloaded a program to generate QR codes. After generating the Ethereum transaction, he scanned the QR code with his phone, copied it to the laptop, and then put it into etherscan.io/push Tx. Finally, Buterin said he began sending out the tokens.
Vitalik got indirectly pwned by the infamous DAO smart contract hack, but had the social clout to pause/rollback the supposedly decentralised/immutable Blockchain.
Maybe not the best example of cryptographic security.
> ... but had the social clout to pause/rollback the supposedly decentralised/immutable Blockchain
Vitalik (and all DAO ETH hodlers) luckboxed in that the ETHs locked in the DAO, although "stolen", couldn't be withdrawn by the attacker before a few weeks.
There has been zero pause and zero rollback. Most people don't understand that: by chance the stolen funds were inaccessible to the attacker for a few weeks.
What Vitalik did is he forked (soft fork) the ETH blockchain to modify the rules. That soft fork happened before the cooldown period expired, so the attacker never got to access his funds.
Some members of the community said "adding new rules is against the spirit of decentralization, so we keep using the old chain". The old chain was named "Ethereum classic" while the forked chain kept the name "Ethereum".
Vitalik didn't rollback the chain. The entire community agreed that it was the correct thing to do and did it. Thats how consensus mechanisims work. This was easier then because the community was tiny. It would be impossible now.
The proof of this is that some people didn't agree with undoing that transaction. They stayed on the old chain, which is now worthless.
This is such a boring and widely known story now, but it has to come up literally any time someone wants to play crypto tribalisim.
I was going to write a more indirect response by way of analogy, but it got too unwieldy. TL;DR: I was predisposed to taking the position you are advocating for, but this argument is incredibly weak while demonstrating the problem, to the point it made me wonder about my own priors. Shape-shifts from "this was totally fine and normal" to "but totally couldn't do it today" to "and guess what the ppl who didn't want to rollback went to 0" to "boring story" to "crypto tribalism", whatever that has to do with anything in this context.
That's what it means to have two chains. One chain undid the transaction. One did not. Do I really need to explain this? Both things happened because there are 2 chains. Only one of them is worth something but they both exist.
I think you got too spun up by the evil They you usually hear talking about this: whatever you're saying here sounds obvious.
The reason why people got confused with your comment is because ex. you purport it was fine, it can never happen again, and everyone who didn't agree went to 0.
Lot of tensions between those things.
We also understand how one person could have those views and even steelman it into something intellectually consistent. But then the post seems really off because it's sort of a rushed, poor, justification for why you believe something, coupled to bemoaning some sort of unrelated group none of us are privy to.
Yeah, it's strange, the first paragraph seems to just say he didn't roll it back alone, it was a consensus thing, and then the second says actually it wasn't even rolled back because other people kept using the old chain (and somehow this "proves" what was said in the 1st place).
how would anything ever be immutable if people can reassign the symbol/pointer/name?
the DAO hack happened, immutably, no one disputes it. the hashes and blocks and transactions are well-known. so there was a "schism", that explicitly validates the fact that without this large-scale cooperation, without the redefinition of what Ethereum is, it would be still be what is on that other branch. these both provide evidence for the immutably and decentralization.
The version of Ethereum after the hack became known as Ethereum Classic. The Ethereum foundation decided to go with a fork of the chain prior to the hack, and pretty much all the devs and the community followed. The value of Ethereum is entirely derived from what people are willing to pay for it, and community is a big part of that. The version of Ethereum which underwent the attack didn't cease to exist, and people can still use it; it's just called "Ethereum classic" now, whereas people who want to use the version of the chain that didn't suffer from the hack can use that version (generally understood to be "Ethereum".
The fact that there are far fewer users of Ethereum Classic (and the market cap is significantly lower) is a testament to how much people care about the community which chose to follow a different history of the Ethereum network.
Small nitpick. In both chains the attack happened.
But in one chain the whole community decided to disown the attacker by injecting hard coded transactions that would send the Ethers back to their original owners.
It wasn't a rollback in much the same way that UPDATEing a row in an MVCC database doesn't actually overwrite that row, it just creates a new version of it that becomes the version that people tend to care about from that point on.
Is this basically saying he sent all the ETH out of his "account" (presumably to another one that was pre-generated & pre-shared half the private key with his family), so that it just had the Shiba tokens left in it?
Then he didn't have to worry about the Shiba related transactions affecting his ETH?
He didn't want to have the signal be that he was happy holding SHIBA and was uncomfortable with that much power & control over SHIBA. So he wanted to be able to transfer his SHIBA out to a hot wallet and then burn most of it and donate the rest, given the amount of money involved he took extra steps like buying a new computer to generate the new keys, airgapping it from the internet while it held the cold wallet keys etc
If you want to enable recovery, you should give ownership of things to smart contracts, which enable things like succession rules and a heatbeat checkin etc.
Public/private keys are not designed to solve that kind of governance problem.
I saw a few places stop accepting cash during covid days but most have started accepting it again. The one place that I frequent that still doesn’t is the haircut store in my town. There are not a lot of options so it’s card or go somewhere that charges almost double.
What's weird to me is that you guys frame it as a bad thing. For me as a European it's the opposite, I'm in trouble if someone doesn't take card. Nobody carries cash any more.
I think pretty much all stores still accept cash, but most people here just never withdraw any. It's pretty much just old people and people buing illegal stuff
What you deem illegal may not be the next day. Being able to do illegal things is actually healthy for a society. Otherwise we already have the technology to stop all crimes world wide. We could force every person to wear a body cam at all times and failure to do so results in life in prison. Done crime solved. But that would not be good no one wants that. But if we did stop every crime imagine how the world would be. Imagine 60 years ago we could stop all crime. Any homosexual would be found and persecuted. Anyone who became a whistleblower would be found a jailed. There are just so many reasons why being able to break the law is fundamental for a society to progress and thrive.
So this is why cash IS a good thing. Sex workers want to do their thing and Johns want to not be instantly called out for using sex workers. The people who long ago realized magic mushrooms work to cure depression want to be be able to get it without being jailed. Now, here in Canada, sex work is protected and magic mushrooms will not get you thrown in jail.
So even though you may deem things illegal, I ask you think of a greater good that cash allows as everything being digital reveals a lot of information that not all people are comfortable their government knowing. Be it homosexuals, depressed people trying illicit treatments, or extremely lonely discarded individuals reaching out to sex workers verses suicide.
Lastly according to a quick google search and a few spots I looked at, most only showing 2022 as latest information, most point of sale transactions in Europe are made with cash not card [1].
[1] https://www.statista.com/statistics/786680/share-of-cash-tra...
Just for the record I don't condemn victimless crimes. I'm fine with willing sex workers and I'm fine with drugs. As far as I'm concerned, alcohol is worse than most illegal drugs, and most of the harm from most illegal drugs comes from their illegal status not the drugs themselves. If it was up to me I'd legalize everything. You want to buy heroin just take a mandatory safety class explaining safe use, then go buy it at the pharmacy. People can get it either way, might as well get clean and taxed stuff. I realize that's probably not entirely realistic but that's my opinion anyway. Especially for lighter stuff, heroin and meth might be the exceptions but again, anyone can buy it whenever so honestly I don't see why they shouldn't be able to do it at a pharmacy.
And in northern Europe, pretty much nobody uses cash. In the rest of Europe, at least the places I've been, pretty much every store accepts card and often other digital payment methods.
I don't doubt your statistics, just stating my experience. I just think it's strange that people prefer cash for legitimate purchases. I definitely want cash to stay around, but these days we can use crypto for illegal stuff anyway do it's not really a big deal.
Cash is superior to crypto for anonymity and most people have it, know how to use it and accept it. Bitcoin and the majority of other coins will leave a permanent trail which can be easily associated to the person due to KYC policies and onchain analysis firms. Sure there are privacy coins like Monero but they aren't trivial to acquire without KYC and to find someone that accepts it. So I'm happy that people still use cash despite not doing anything illegal (or immoral) and mostly making payments with card and instant payments.
Was this refusal of a normal cash transaction, or something silly (unreasonably large transaction/transaction all in one cent coins/transaction which would raise money laundering alarms etc)? Like, if you try to pay 10,000 dollars in cash, or, say, buy a stack of prepaid debit cards with cash, most places are going to be sceptical of that.
a small shopping trip with ordinary items totaling less than thirty dollars, actually. Many places of various kinds in California are not accepting cash today - San Francisco passed local law to require accepting cash as one result.
But touch that $1B+ wallet and suddenly nothing is worth anything... so if I had the capability to silently steal money from the bitcoin blockchain, I would go slow, and in discrete places.
All transactions are publicly visible, so everyone would know that it was now possible for someone to take bitcoins from people. Value depends on resale. Why would anyone ever buy a bitcoin or accept payment with them if they can just disappear at any time?
Ah, I read it too fast and missed the theft context regarding Satoshi's wallet. Thanks. Part of me hopes that in the not-too-distant future Satoshi will do a tiny transaction on his wallet just so all the speculation ramps up again and we get another wave of entertainment.
If that's the problem, you just say "this person had lax security" or "their computer was compromised." In the absence of real proof that will be the default expectation anyway.
I think the other factor to consider is that once you try to sell $200B worth of Bitcoin, the value of Bitcoin suddenly drops to near zero (due to supply/demand).
Which is also why all those company market caps you see quoted everywhere are totally ridiculous. A company is not worth the latest price of a small share transaction multiplied by all the outstanding shares.
There's enough depth in the stock market to make company market caps pretty real. If you had a big chunk of a company, you could sell it for close to the trading price. I'd be shocked if you couldn't get half, as a nice round example number.
I would not be shocked if trying to sell $200B in bitcoin gets you far less than half.
Or some other number-theoretic advance that is significantly below exponential time on the particular type of field or curve being used.
The reason that we use elliptic curves these days, or if we must then something like 8k bit keys to get 128 bits of security over finite fields, is that for the old Z^*_q/Z_p setup, such a faster algorithm exists (index calculus).
Someone could in theory find a better calculus that works only for groups with some specific characteristics of Curve25519, for example. No quantum computers needed.
EDIT: we know that no _generic_ faster algorithm exists, that is one independent of the representation of the group involved, for the traditional computing model. But that doesn't exclude algorithms, as I said above, that work for very particular cases.
Most of what I've learnt here was less from books and more from colleagues/seminars and reading research papers.
You can get a brief introduction at https://soatok.blog/2020/04/26/a-furrys-guide-to-digital-sig... (your own choice if you want that open in a tab at work or not, but there's nothing NSFW in the usual sense in there), and then read the details of each scheme in the RFCs. Some of the RFCs even talk about security implications.
"djb" as he is known in the crypto world has a good paper at https://eprint.iacr.org/2024/1265 , it's 68 pages so "almost a book". He also has a lot of resources on his page https://cr.yp.to . Be aware that he is sometimes ... controversial (not racist or anything, just has strong opinions on FIPS and the NSA and has actually taken the US government to court in the past over this). He's the author of Curve25519.
Except that the Bitcoin only has value so long as the cryptography behind it is secure. If it is broken, then the value drops to zero and all your coins are worth nothing.
Well, a time-traveling computer can solve problems of an entirely different (much larger and a strict superset) category than the ones a quantum computer can.
You don't even need to travel far. A second or so is enough to break all cryptography, even the post-quantum one.
Not necessarily, if there's e.g. a trillion keys to try, every tried key as a 1 in 1-trillion chance to be it, so it could be found by chance after just one try.
(disclaimer, I don't know statistics, cryptography, bitcoin or chances)
Yes, but in your example the probability of finding it at the first try would be one in a trillion, which is already so small to be negligible. And 2^66 is much bigger than that.
"Here's $400,000 sitting on the table, hope nobody takes it" which triggers an alarm telling us to replace all our old prequantum cryptography.