Algorithms used in Bitcoin are expected to be strong until at least 2030

[NotATether]

That's going to have to involve sending your coins to a completely different set of HDKeys because if the curve is also broken in addition to ECDSA, then just signing all local transactions with the new signature algorithm won't be enough.

I'm pretty sure that's what Satoshi was saying in that quote - the software would automatically send all your money to the new address type we end up with. As ranochigo points out above, I don't think it is possible to leave coins on current addresses but transition to some form of "hardened ECDSA".

Interesting to see what that would look like though. ECDSA in bitcoin hasn't been exploited yet so it's not possible to pinpoint exactly the weak spots, but I'd assume that we'd have to break ECDSA public key recovery in the process - as in, you could sign the transaction using XYZ quantum-safe signatures, and then sign that with the legacy ECDSA signatures and broadcast that. The transaction can still be verified as correct by everyone, but you can no longer get the public key back, like Schnorr signatures.

[o_e_l_e_o]

-snip-

If ECDSA is broken and it is possible to recover the private key from the public key, then even if we depreciate ECDSA signatures then there is nothing stopping an attacker still recovering the private key and also making a transaction on the new algorithm and stealing your coins. As discussed above, the only way around this would be to require a zero knowledge proof of some other piece of information such as the parent chain code or the seed phrase which derived that private key, but that would only be possible for addresses which were part of an HD wallet.

Rather, we would need to have a quantum resistant address type well in advance of ECDSA being broken, everyone would have to generate new quantum resistant addresses from new private keys, and then move their coins to these addresses prior to them becoming vulnerable.

[garlonicon]

Interesting to see what that would look like though.

You can try to explore that, by using some totally broken elliptic curve (for example the one you can find in my avatar), and then try to make some "hardened" version. Or, you can use any curve with more bits, if 7-bit curve is too small to figure it out. You can add more and more bits, until you will reach sufficient space to be unable to use brute force, then you can try some attacks, and then hardening.

I think it is very similar case, as with hash functions, like SHA-1: you could replace it with something bigger, if 160 bits are not enough, or you can try to harden those 160 bits alone, like it was in SHA-1, based on the attack. For 160-bit hash, the attack on SHA-1 requires around 2^64 operations, so to test something similar for elliptic curves, you can try using some 25-bit curve, and assume there is some attack that allows reaching some private key after 2^10 operations. And then, you can try hardening your elliptic curve, and see, what options are available.

ECDSA in bitcoin hasn't been exploited yet so it's not possible to pinpoint exactly the weak spots

Of course. You can only guess and assume. For example, you can split some space containing around 2^25 points into sub-spaces with around 2^10 points each, and then assume, that the attacker can somehow figure it out, which sub-space is taken by a given public key. And then, you can prepare your counter-attack, based on that. In general, your protection will reflect your ability to attack, because it will work only for your scenario, nothing else. If some attacker could make a rainbow table instead, and break any 25-bit key in O(1) time, then your protection will obviously collapse, exactly as if someone could mount some preimage attack on SHA-1, then even hardened version may be vulnerable.

So, to sum up: if you want to know, what is possible, and what is not, then write some code, explore some simplified cases, and then you will learn more about it.

[Flexystar]

Good to know (after reading rest discussion) it’s not really possible to break the code until it really happens. It also made me think that Satoshi did not make it so easy as his plan is for hundreds of years until 2140 by when the last Bitcoin would be mined.

It’s seems it will get more stronger with the time as the complexity of network keeps increasing.

By 2140? Lol, it has nothing to do with "network complexity" whatever that means.

Simple and pure mathematics is what keeps the coins safe, in order to make it harder for quantum computers we just need more complex math/equations.

Enigma in WW2, was the ultimate crypto/math problem, but the first computer invented managed to break the encryption, now it's the other way around, we need to invent an equation so the new computer generation can't break it.

Satoshi just chose one of the strongest curves at that time, even he knew 20 years later people will have to change the key to their safe.😉

Damn seriously? I thought network difficulty has got something to do with the complexity over the period of time? I mean as we keep saying that for every halving that occurs, the reward also decreases, while each time network difficulty is rising too. Just for the info, in what relation are we saying that network difficulty is rising.

Has it got no relationship with the maths/equation solving mechanism? I mean if it is getting difficult then it is getting difficult to solve right?

Yeah, the Enigma was something crazy for sure. Turing exactly knew what he was doing, I just hope we do not have another Turing solving the same. Lolz

[ranochigo]

Damn seriously? I thought network difficulty has got something to do with the complexity over the period of time? I mean as we keep saying that for every halving that occurs, the reward also decreases, while each time network difficulty is rising too. Just for the info, in what relation are we saying that network difficulty is rising.

Has it got no relationship with the maths/equation solving mechanism? I mean if it is getting difficult then it is getting difficult to solve right?

Network difficulty is not directly associated with reward halving, in fact the hashrate should decrease in theory. Increasing the difficulty has nothing to do with what we are talking about here, unless you're talking about a pre-image attack. For which, a pre-image attack on SHA256 would go beyond speedups on hashrates which would only concern the first pre-image attack. Collisions and second pre-image attack on SHA256 are by far more potent with regards to the security of Bitcoin.

[NotATether]

Network difficulty is not directly associated with reward halving, in fact the hashrate should decrease in theory.

That's actually not good at all, it means we are looking at a significantly flattened (as in the curves are not as extreme) Bell curve for Bitcoin global hashrate between 2009 and 2140. I guess this is why people have been saying that more incentives for Bitcoin miners are required to guarantee that the hashrate stays more or less stable once block rewards in BTC denominations start to become scarce.

[ranochigo]

That's actually not good at all, it means we are looking at a significantly flattened (as in the curves are not as extreme) Bell curve for Bitcoin global hashrate between 2009 and 2140. I guess this is why people have been saying that more incentives for Bitcoin miners are required to guarantee that the hashrate stays more or less stable once block rewards in BTC denominations start to become scarce.

Nope, indirectly associated. I'm assuming a theory whereby circulation remains constant and all the other factors being invariable, which is often not what happens in real life. Bitcoin gets deflationary, fees increases, etc; Satoshi's rationale on reward halving may very well hold true assuming improved efficiency in mining and a compensation in fees. Reward halving doesn't encourage more miners to join, the fee compensation and the other monetary factors (real cost - reward, etc) are what makes it attractive.

Regardless, discussion about this would be diverging from the issues that is being discussed here. Would be more of an economics question rather than technical.

[o_e_l_e_o]

Has it got no relationship with the maths/equation solving mechanism? I mean if it is getting difficult then it is getting difficult to solve right?

As global hashrate goes up, then we find blocks more quickly. As we find blocks more quickly, the difficulty adjusts every 2016 blocks in order to maintain the average block time at 10 minutes. It does this by reducing the target number miners are trying to find. By making the target smaller, we need more hashes in order to find a number which meets that target, hence it is more difficult.

Sometimes the hashrate falls and so the difficulty adjusts downwards (making the target larger), but it's been pretty close to an exponential trend upward for many years. You can see all difficulty adjustments here: https://btc.com/stats/diff

This, however, is all to do with mining blocks, which uses hash functions. This is completely separate to the security of private keys, which uses elliptic curve mathematics. The security of your private keys will be 128 bits regardless of where the network as a whole has 100 hashes per second or 100 trillion hashes per second.

[internetional]

Can anyone explain the final bit about transitioning to a new algorithm not being too difficult?

If ECDSA will be broken (and only that), then we can just create a new address type, and move all coins there.

There are millions active addresses. The process of moving coins from them would be very long and very expensive.

[ABCbits]

Simple and pure mathematics is what keeps the coins safe, in order to make it harder for quantum computers we just need more complex math/equations.

Enigma in WW2, was the ultimate crypto/math problem, but the first computer invented managed to break the encryption, now it's the other way around, we need to invent an equation so the new computer generation can't break it.

Let inventing such thing to cryptography expert. Adobe (which is big company) tried building their own cryptography, but ended in huge failure[1].

Can anyone explain the final bit about transitioning to a new algorithm not being too difficult?

If ECDSA will be broken (and only that), then we can just create a new address type, and move all coins there.

There are millions active addresses. The process of moving coins from them would be very long and very expensive.

That's probably only true for company and individual with complex wallet setup. Most people just need to wait their wallet software/hardware to support new address format, then they could just send their coin. I would worry more about security risk when people creating new wallet and move their coin.

[1] https://nakedsecurity.sophos.com/2013/11/04/anatomy-of-a-password-disaster-adobes-giant-sized-cryptographic-blunder/

[ertil]

There are millions active addresses. The process of moving coins from them would be very long and very expensive.

Long? Maybe. Expensive? It depends, it doesn't have to be.

For example, it is quite easy to implement one-time-fee-discount. I wonder why altcoins that forked from BTC didn't do that in the first place, instead of replay protection. For example, it is possible to create a rule, where you can move some coin for free, if that coin was included before block number X. Then, transition from some old to new address type could be free, but only once, and at the same time, people won't move back from new to old address type, because then their transaction will be included in some later block, and they will pay a regular price for that.

Also, I am not sure if the current fee model will still be present in the future, when ECDSA will be broken. More and more often, there are problems with UTXO set size. That means, some future fee model could be based on how many UTXOs you consume or create. And in that case, a single transaction that will sweep a lot of coins into some single new address, could be cheaper, or even free, if the number of UTXOs will be a bottleneck for pruned nodes.

Another thing is that even if you sweep everything to a single address, it doesn't mean everything would be traced into a single owner. Taproot already can support N-of-N multisig, hidden behind a single key, I won't be surprised if some new address type for "hardened secp256k1" would also contain some privacy-preserving features, and then N people could join forces to move their on-chain coins cheaper (even if developers won't add any discount to encourage true owners to protect their coins). Also, maybe they will land even in LN directly, or some another subnetwork. It is hard to predict, how the whole situation will change, by the time we will get there.

[Flexystar]

I think I have asked all sort of dumb questions about the difficulty and it’s relationship with the rewards, security of the network, or even complexity getting more or less. I know few questions were out of the line but I think I am trying to learn a subject which is not really my expertise or close field. Though I got good replies from the experts I am still not understanding half of the terminology and could only connect the dots.

Basically I just hope that security of the bitcoin lyes within our hands no matter how advance the technology becomes. That is the only way to keep up with the Bitcoin as is in the long term and until we mine the last bitcoin really.

[serveria.com]

Few days ago when I was on this forum, I saw this:

According to NIST and ECRYPT II, the cryptographic algorithms used in Bitcoin are expected to be strong until at least 2030. (After that, it will not be too difficult to transition to different algorithms.)

You know that there is no forum ad again, but sometimes you can see meaningful information there to read and I saw it.

Is it true that cryptographic algorithm that bitcoin is using will likely no more be safe by 2030? What are bitcoin developers doing to make bitcoin safer?

I'm really doubtful regarding this. Computer and IT progress is slowing down and quantum computers seem to be too far away atm. Honestly, I suspect Bitcoin will be safe also beyond 2030 even with currently used algos. I don't think devs are doing something specifically against this issue. If aint broken, don't try to fix it they say. 

[ranochigo]

Long? Maybe. Expensive? It depends, it doesn't have to be.

For example, it is quite easy to implement one-time-fee-discount. I wonder why altcoins that forked from BTC didn't do that in the first place, instead of replay protection. For example, it is possible to create a rule, where you can move some coin for free, if that coin was included before block number X. Then, transition from some old to new address type could be free, but only once, and at the same time, people won't move back from new to old address type, because then their transaction will be included in some later block, and they will pay a regular price for that.

Miners won't like it. Transactions incur costs, often implicit that falls on the community as a whole, for eg. those who run nodes, those who mines the coin. The former already doesn't receive monetary compensation while the latter has always been receiving it in the form of fees. The cost of moving your coins shouldn't be discounted just because you want to encourage people to move to a new address format. The onus should always be on the user; if you don't want your funds to be lost, move it. We have no obligations whatsoever to encourage you to do so because it serves no benefits for the rest of us.

Also, replay protection is still needed regardless.

Also, I am not sure if the current fee model will still be present in the future, when ECDSA will be broken. More and more often, there are problems with UTXO set size. That means, some future fee model could be based on how many UTXOs you consume or create. And in that case, a single transaction that will sweep a lot of coins into some single new address, could be cheaper, or even free, if the number of UTXOs will be a bottleneck for pruned nodes.

That encourages spam. It is unnecessary to implement, adding in the complexity and lowering fees for miners significantly. Having large UTXOs are already discouraged, by having fees proportional to the size. That is not ideal for the network and you'll face significant bottleneck for the rest.

The privacy preserving feature is something to be thought of and worked out when the time comes.

More likely than not, we might have something truly better than Bitcoin when ECDSA finally gets cracked, which is a long time from now.

[pooya87]

For example, it is quite easy to implement one-time-fee-discount. I wonder why altcoins that forked from BTC didn't do that in the first place, instead of replay protection. For example, it is possible to create a rule, where you can move some coin for free, if that coin was included before block number X. Then, transition from some old to new address type could be free, but only once, and at the same time, people won't move back from new to old address type, because then their transaction will be included in some later block, and they will pay a regular price for that.

You are forgetting that what you pay as transaction fee is actually the money you pay for the scarce space on the blockchain which means it does not matter at all whether your coins were created 10 seconds ago or 10 years ago if the portion of the block space you want to "purchase" is the same. Not to mention that fees are not enforced at protocol level, it is only policy rules (miners preference).

As for altcoins, they don't cost much anyway so their fees are super cheap which means there is no reason to bother with any changes like that