2

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?

Improve this question
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.

Improve this answer
3
  • 1
    You're right, a message-derived nonce seems like a very good solution for the problem. I've just learned about tools.ietf.org/html/rfc6979, which seems to fix the problem for Bitcoin in a completely backwards-compatible way. Thanks for still explaining how an algorithm change would work! – lxgr Aug 23 '13 at 20:18
  • 1
    Also, do note that if randomness generation is broken, then all new addresses are bad as well. With the nature of bitcoin being what it is, new addresses are generated almost as often as signatures - so making signatures deterministic just hides the bad randomness problem longer... – Nakedible Aug 24 '13 at 5:36
  • That's definitely true for bitcoind/bitcoin-qt. Seems like deterministic wallets would be unaffected, though. – lxgr Sep 3 '13 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.