6 ms·

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?

• n2d4 2y ago
  Or someone "just" finding a fault in the cryptographic algorithms used in Bitcoin. Or whoever created the puzzles leaking their information.
  • sigmoid10 2y ago
    >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.
    • owl57 2y ago
      Is it likely that these particular private keys were wiped ~immediately after creation?
    • Powdering7082 2y ago
      > 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: https://decrypt.co/91000/ethereum-founder-vitalik-buterin-dumped-7-billion-shib-how-why https://decrypt.co/91000/ethereum-founder-vitalik-buterin-du... > 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.
      • LikesPwsh 2y ago
        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.
        • pas 2y ago
          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.
          • akoboldfrying 2y ago
            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.
          • pcthrowaway 2y ago
            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.
  • scotty79 2y ago
    I don't think they kept private keys because why would they if their intentions were to give the money away not just dangle it briefly.
• deleted 2y ago
  [deleted]
• Maken 2y ago
  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.
  • mapt 2y ago
    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.
    • oniony 2y ago
      Except your analogy doesn't work because every single bitcoin address has the same brand of lock.
      • beepbooptheory 2y ago
        Each key is a brand in the analogy.
        • GTP 2y ago
          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.
• red_admiral 2y ago
  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.
  • ernesto95 2y ago
    Do you have a personal book recommendation on the group and/or number theory of this type of cryptography?
    • red_admiral 2y ago
      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-signature-algorithms/ 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 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 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.
• Cthulhu_ 2y ago
  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)
  • GTP 2y ago
    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.
• zikduruqe 2y ago
  That, or it is a trap to catch time travelers. :)
  • EGreg 2y ago
    If someone solves Puzzle #72 before #67 it would be quite impressive ;-)
  • marcosdumay 2y ago
    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.
• TrapLord_Rhodo 2y ago
  That's all bitcoin is... If someone had a quantum-supreme solution they would go after the sitoshi wallets. Some addresses have like $1B+ and combined represent ~$200B.
  • alex_duf 2y ago
    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.
    • Scramblejams 2y ago
      Coin ignorant here: Why would it not be worth anything?
      • BlarfMcFlarf 2y ago
        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?
        • Scramblejams 2y ago
          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.
        • julianeon 2y ago
          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.
      • buzzert 2y ago
• andrewla 2y ago
  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.