Would a transition to a different signature scheme be feasible?

Question

The recent problem with Android's SecureRandom PRNG once again shows that using (EC)DSA can go horribly wrong if the signature nonce is ever reused.

There is an elliptic curve signature scheme that doesn't share this property: Ed25519.

Is there a mechanism in the Bitcoin protocol to allow transition to a new address/signature format? Would there have to be a new opcode, or does OP_CHECKSIG already support different key types?

What would happen to clients that don't support a new key format, but receive transactions from such a new address/key? Would SPV clients trust a transaction that they can't verify themselves, or reject the block containing it as invalid?

In any case, the new format can only be used once (nearly) all clients support it, but could this be implemented at some point, and enabled some time later?

Answer 1

Well, for starters I must say that the problem with ECDSA nonce can be avoided even when using ECDSA via the same method used in Ed25519, and indeed this method is not even novel to Ed25519. But, let's assume we need to change the signature algorithm for some reason.

OP_CHECKSIG does not support different key types per se. The public key given as input is either an uncompressed or compressed EC point, starting with 0x04, 0x03 or 0x02. Any other starting byte could be used for different transaction types, if desired. However, a separate opcode would (IMHO) be cleaner.

The only required changes are on the script side, either modifications to OP_CHECKSIG opcode or the introduction of a new opcode. And after this, miners need to start accepting transactions containing the new style signatures as "standard" scripts.

All "full" bitcoin clients verify all transactions that are present in a block (run all scripts). This means that they will refuse to accept a block that can not be verified (even if it only has one transaction failing verification). This means that if such a change is incorporated, the block chain will fork for the clients that do not support such transactions.

Nearly all clients will need to support the new signatures and the clients that do not will become unusable when encountering the first block that has a transaction with a new signature.