2 ms·

My understanding is Bitcoin unspent transaction outputs (spendable bitcoins) are spendable depending on the script (some opcodes that are agreed upon). The most

My understanding is Bitcoin unspent transaction outputs (spendable bitcoins) are spendable depending on the script (some opcodes that are agreed upon). The most common is pay to public key hash. So you not only need to solve secp256k1 ecdsa, but your bitcoin utxo is also protected by the hash function which derives the address. Put another way, starting with an address, you need to reverse engineer a hash collision (super difficult) to find a public key as that has not been announced yet. Then find a private key for that. So you need to break two technologies. Also my understanding is that quantum can only reduce complexity by sqrt, so 2^256 problem is reduced only to 2^128 which is unsolvable. I think we’re safe for now. And if ecdsa does get broken, it will be more like “we can generate keys in 2 years” and practically speaking, everybody can transfer their bitcoin utxo’s to a new script by only exposing their public key for a short time (tens of minutes) into the transaction mempool. Not enough time to break it.

tromp 5y ago
> Also my understanding is that quantum can only reduce complexity by sqrt, so 2^256 problem is reduced only to 2^128 which is unsolvable. The sqrt speedup is for Grover's unstructured search algorithm, which is the only known quantum speedup for breaking hash functions such as RIPE160 protecting public keys in P2PKH. So it would still take on the order of 2^80 quantum steps to find a hash preimage. But to find the private key corresponding to a given public key, Shor's algorithm provides exponential speedup, so a large scale quantum computer would completely break ECDSA. There are large amounts of bitcoin protected only by P2PK (i.e. without the RIPE160 hash), or protected by P2PKH with already known public keys (from widespread key reuse), so Bitcoin would be quickly destroyed by successful application of Shor's algorithm alone. That said, I consider projections of large scale quantum computers existing within 10 years wildly optimistic, even more so than nuclear fusion being "just a few decades away".

tromp 5y ago

> Also my understanding is that quantum can only reduce complexity by sqrt, so 2^256 problem is reduced only to 2^128 which is unsolvable. The sqrt speedup is for Grover's unstructured search algorithm, which is the only known quantum speedup for breaking hash functions such as RIPE160 protecting public keys in P2PKH. So it would still take on the order of 2^80 quantum steps to find a hash preimage. But to find the private key corresponding to a given public key, Shor's algorithm provides exponential speedup, so a large scale quantum computer would completely break ECDSA. There are large amounts of bitcoin protected only by P2PK (i.e. without the RIPE160 hash), or protected by P2PKH with already known public keys (from widespread key reuse), so Bitcoin would be quickly destroyed by successful application of Shor's algorithm alone. That said, I consider projections of large scale quantum computers existing within 10 years wildly optimistic, even more so than nuclear fusion being "just a few decades away".