<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-08-23T20:18:05.973Z
You're right, a message-derived nonce seems like a very good solution for the problem. I've just learned about http://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
CC BY-SA 3.0
2013-08-24T05:36:47.387Z
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
CC BY-SA 3.0
2013-09-03T10:09:32.087Z
That's definitely true for bitcoind/bitcoin-qt. Seems like deterministic wallets would be unaffected, though.
lxgr
CC BY-SA 3.0
2013-08-23T19:29:09.753Z
2013-08-23T19:29:09.753Z
Nakedible
<p>The recent <a href="http://bitcoin.org/en/alert/2013-08-11-android" rel="nofollow">problem</a> with Android's <a href="http://android-developers.blogspot.com/2013/08/some-securerandom-thoughts.html" rel="nofollow">SecureRandom</a> PRNG once again shows that using (EC)DSA can <a href="http://blog.cryptographyengineering.com/2012/03/surviving-bad-rng.html" rel="nofollow">go horribly wrong</a> if the signature nonce is ever reused.</p>

<p>There is an elliptic curve signature scheme that doesn't share this property: <a href="http://ed25519.cr.yp.to/" rel="nofollow">Ed25519</a>.</p>

<p>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?</p>

<p>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?</p>

<p>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?</p>

<signature><ecdsa>
Would a transition to a different signature scheme be feasible?
lxgr
# Would a transition to a different signature scheme be feasible?

(Asked by: username_0 on 2013-08-23)

The recent [problem](http://bitcoin.org/en/alert/2013-08-11-android) with Android's [SecureRandom](http://android-developers.blogspot.com/2013/08/some-securerandom-thoughts.html) PRNG once again shows that using (EC)DSA can [go horribly wrong](http://blog.cryptographyengineering.com/2012/03/surviving-bad-rng.html) if the signature nonce is ever reused.

There is an elliptic curve signature scheme that doesn't share this property: [Ed25519](http://ed25519.cr.yp.to/).

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?

**Tags:** signature, ecdsa


---

## 1 answers

### Answer by username_1 on 2013-08-23. Score: 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.

> **Comments:**
> **username_0**: You're right, a message-derived nonce seems like a very good solution for the problem. I've just learned about http://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!  
> **username_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...  
> **username_0**: That's definitely true for bitcoind/bitcoin-qt. Seems like deterministic wallets would be unaffected, though.  

---

