The use of Guy Fawkes Signature in case of ECDSA zero-day exploits

[jl2012]

Senarios: ECDSA is suddenly broken. Private key of a public key could be derived in less than 10 minutes on an average desktop computer.

Bitcoins in reused addresses will not be protected at all, but we can allow people to safely transfer bitcoins from an first time address to a new scheme address (e.g. Lamport address).

We can use Guy Fawkes Signature scheme. To spend bitcoins in an old pay-to-keyhash or P2SH address, the user will sign the transaction as usual, but not publishing the transaction. The user will then timestamp the transaction hash to the blockchain. After 6 or more confirmations (the longer the safer), the user will publish the transaction, with the SPV proof of the timestamp. A new soft-fork rule requires miners to accept a transaction of this type only if it contains such SPV proof.

Thoughts?

(Minor notes: inserting SPV proof to the transaction will change the transaction hash, but one can't obtain the SPV proof before the hash is calculated. This becomes a chicken and egg problem. Therefore, miners have to calculate the transaction hash with the SPV proof removed, and compare with the timestamp.)

[Etlase2]

Thoughts?

Doesn't protect against a mining operation that is attempting to subvert signed transactions with its own, which is generally accepted as a requirement needed to (reliably) steal funds from transactions sent into the wild. Unless, as part of the soft-fork, miners are directed to reject blocks containing non-"SPV" transactions after having received an "SPV" one, this is, however, a ridiculously easy way for anyone to troll the network.

[jl2012]

Thoughts?

Doesn't protect against a mining operation that is attempting to subvert signed transactions with its own, which is generally accepted as a requirement needed to (reliably) steal funds from transactions sent into the wild. Unless, as part of the soft-fork, miners are directed to reject blocks containing non-"SPV" transactions after having received an "SPV" one, this is, however, a ridiculously easy way for anyone to troll the network.

With the soft-fork, any old-style transactions without a SPV proof are simply invalid.

[Etlase2]

With the soft-fork, any old-style transactions without a SPV proof are simply invalid.

Pretty sure that invalidating the de facto transaction is a hard fork.

[jl2012]

With the soft-fork, any old-style transactions without a SPV proof are simply invalid.

Pretty sure that invalidating the de facto transaction is a hard fork.

No. Invalidating a valid transaction is soft-fork by definition.

[piotr_n]

This solution has flaws, but is better than nothing.

The concerns about a possible weaknesses in ECDSA are serious and not addressing them ASAP is irresponsible, to say the least.

[behindtext]

This solution has flaws, but is better than nothing.

The concerns about a possible weaknesses in ECDSA are serious and not addressing them ASAP is irresponsible, to say the least.

agree on it being better than nothing.

the best countermeasure immediately available is spreading coins across addresses, making sure to never have more than a few 1000 USD worth in any one address.

[hashman]

First thought:  broken ECDSA would spell the end of BTC despite the very cute hidden public key.  Funds are likely to migrate to a secure DSA. 

Second thought:  did you just find a way to make a secure DSA based only on hash functions and a block chain?

[piotr_n]

First thought:  broken ECDSA would spell the end of BTC despite the very cute hidden public key.  Funds are likely to migrate to a secure DSA.  

unless we manage to diversify between different digital signature algos; besides ECDSA, there is at least the old fashion RSA and the DSA.

it is not even that one could diversify his savings between different algos.
giving the scripting language that is already in the protocol, one could protect an unspent output using several different signing algos at the same time, one after another.
and it is very unlikely that all of them would get broken.

but this requires a hard fork and having in mind that the satoshi client has a mining monopoly these days, we won't introduce a new signing method without an active support from the dev team.

[kjj]

This solution has flaws, but is better than nothing.

The concerns about a possible weaknesses in ECDSA are serious and not addressing them ASAP is irresponsible, to say the least.

Protection against a potential weakness in ECDSA has been included since day 1.  Don't reuse keys.

Also, in reality, a sudden catastrophic break in ECDSA is pretty much unimaginable.  There have been zero sudden breaks of that magnitude in modern cryptosystems.  What really happens is that they weaken gradually over many years.

Should such a thing happen, the method described in the first post appears, at first look, to allow migration, and the world would implement it or something like it very rapidly.

There may be some value to adding this to the system in advance of the need to use it.  It may even enable some other useful things.  But it would be a fork.

[piotr_n]

This solution has flaws, but is better than nothing.

The concerns about a possible weaknesses in ECDSA are serious and not addressing them ASAP is irresponsible, to say the least.

Protection against a potential weakness in ECDSA has been included since day 1.  Don't reuse keys.

It doesn't help, if someone can crack the key before your tx gets confirmed and has a better access to miners.

Use your imagination, mr bitcoin elite.

[Etlase2]

Also, in reality, a sudden catastrophic break in ECDSA is pretty much unimaginable.  There have been zero sudden breaks of that magnitude in modern cryptosystems.

How is it unimaginable when the trapdoor is based on math we think is hard? "It hasn't happened before, ergo..." is a logical fallacy. "Modern" cryptography has been primarily based around symmetric crypto which is much simpler and does not rely on trapdoors.

There may be some value to adding this to the system in advance of the need to use it.  It may even enable some other useful things.  But it would be a fork.

There is definitely value in additional protection. However, I have to agree with hashman that it is essentially the end of any trust in bitcoin as there will be many unprotected addresses, especially a lot of the early coinbase tx that will never be protected by anything added to the protocol later.

[jl2012]

First thought:  broken ECDSA would spell the end of BTC despite the very cute hidden public key.  Funds are likely to migrate to a secure DSA.  

unless we manage to diversify between different digital signature algos; besides ECDSA, there is at least the old fashion RSA and the DSA.

it is not even that one could diversify his savings between different algos.
giving the scripting language that is already in the protocol, one could protect an unspent output using several different signing algos at the same time, one after another.
and it is very unlikely that all of them would get broken.

but this requires a hard fork and having in mind that the satoshi client has a mining monopoly these days, we won't introduce a new signing method without an active support from the dev team.

No. You can change pretty much anything in the protocol with soft-fork. Adding new DSAs and Hash algorithms are certainly soft-forks. Imagine to have a script protected by 3 different DSAs and 5 Hash algorithms.....

[piotr_n]

No. You can change pretty much anything in the protocol with soft-fork. Adding new DSAs and Hash algorithms are certainly soft-forks. Imagine to have a script protected by 3 different DSAs and 5 Hash algorithms.....

Can you?
Maybe I miss something, but there is no opcode to do RSA or DSA verify - so how can you add it without a hard fork?

[gmaxwell]

Can you?
Maybe I miss something, but there is no opcode to do RSA or DSA verify - so how can you add it without a hard fork?

You can. You simply add them.  You write a transaction which looks like an {anyone can spend} to old nodes, but looks like {$XYZ required to spend}. Old nodes are happy, and the transactions are safe to use as soon as a supermajority of miners imposes the new rule.

[piotr_n]

Can you?
Maybe I miss something, but there is no opcode to do RSA or DSA verify - so how can you add it without a hard fork?

You can. You simply add them.  You write a transaction which looks like an {anyone can spend} to old nodes, but looks like {$XYZ required to spend}. Old nodes are happy, and the transactions are safe to use as soon as a supermajority of miners imposes the new rule.

But it will still cause a hard fork, if you try to spend it with a wrong signature, while having some old mining nodes in the network, won't it?

[gmaxwell]

But it will still cause a hard fork, if you try to spend it with a wrong signature, while having some old mining nodes in the network, won't it?

Thats part of the definition of a soft fork. If there is a super-majority of miners enforcing the rule the majority will pull over the old mining nodes, they'll lose some blocks here and there but the consensus will be preserved.

[piotr_n]

But it will still cause a hard fork, if you try to spend it with a wrong signature, while having some old mining nodes in the network, won't it?

Thats part of the definition of a soft fork. If there is a super-majority of miners enforcing the rule the majority will pull over the old mining nodes, they'll lose some blocks here and there but the consensus will be preserved.

OK, thanks for explaining.
But a super-majority is a relative term.
What we are talking about here is in fact any majority, meaning: more than 50%.

If we want to have a super-majority around this, in a close future, you guys better put these new opcodes into the reference client ASAP, and I will follow you adding them to mine, because that would be one of a few changes in the chain protocol that I am supporting today with my all hands.

I am sure the members of the core dev team also own lots of bitcoins and I hope they don't all have the "sudden catastrophic break in ECDSA is pretty much unimaginable" approach.
If not for me, do it for your own interest. Please.

[gmaxwell]

OK, thanks for explaining.
But a super-majority is a relative term.
What we are talking about here is in fact any majority, meaning: more than 50%.

It technically takes a majority, but a slim majority is unsafe because the length of a reorg that results from it is unbounded. E.g. if it's 50.001%  they split and maybe the reorg is a day long when the forkers decisively overtake.

We actually can make sure a super-majority of whatever level we think is needed exists in a soft-fork.  The way this works miners indicate their intention to support a particular softfork in their coinbase, and then we can have the softfork activate when, say, 90% of the last 1000 blocks have the indication that they're on-board. Then they'll all switch at once and the change is automatically decisive. The downside is that miners can drag their heels and delay the change.

An example of this is described in BIP 34.

If not for me, do it for your own interest. Please.

The faux-urgency of speculative ideas is not helpful. Rushing in changes "ASAP" is a danger to the network with probabilities much higher that spontaneous EC weakness.  I've proposed having an alternative non-hidden-subgroup-problem signature algorithm at least as far back as early 2011, and written out some more concrete descriptions, though I'm a bit disinclined to post an implementation where some crap altcoin will just rip it off and claim an advantage over Bitcoin. But, regardless, it's not something we can or should rush into.

In terms of deployment, miners who can't update rapidly to softfork enforcing software could start mining no transactions while they update to reduce their exposure. Even if a full implementation is complicated, a simple one that reduces orphaning is likely not so hard.

I have doubts about the viability of non-essential changes in the future, with sadness and regret. The addition of P2SH happened several years ago, and today many popular wallet implementations— including ones that didn't exist when P2SH was created— do not implement it, so people can still not even start using multikey security to secure their wallets because people could not send them coin (Android wallet, Multibit, Blockchain.info, and Armory are the most notable). The non-deployment of P2SH also inhibits the deployment of a new checksig, because even if you start using a wallet secured by an improved signature scheme the whole world needs to be updated before they can send to you... p2sh was intended to resolve this chicken and egg problem with deploying new wallet security measures, by taking the sender out of the loop when they don't need to be in the loop.

[piotr_n]

The faux-urgency of speculative ideas is not helpful. Rushing in changes "ASAP" is a danger to the network with probabilities much higher that spontaneous EC weakness.  I've proposed having an alternative non-hidden-subgroup-problem signature algorithm at least as far back as early 2011, and written out some more concrete descriptions, though I'm a bit disinclined to post an implementation where some crap altcoin will just rip it off and claim an advantage over Bitcoin. But, regardless, it's not something we can or should rush into.

You are so right.
But if you have been waiting for your idea to go through since 2011, how much longer do you plan to wait, if you don't mind me asking, before concluding that it's already too long?
You obviously understand the seriousness of a potential problem and all the cons of rushing the solution - that's the approach we need.
Therefore you should be able to judge a good balance between the two things. And where do you see the balance being finally implemented? I hope not in 2020