BUIP009: User-configurable public-key cryptography (let users choose from predefined cryptosystems)

[bitcartel]

Status: Draft (call for input and discussion)
Proposer: Simon Liu
Revision: 1
Submitted on: 9 Jan 2016

Summary

Add configuration option so users can choose a public-key cryptography system to use for key generation and transaction validation. This will enable the community to better safeguard their Bitcoins by being both prepared for and able to react swiftly to advances in cryptography and cryptanalysis.

Background

Bitcoin uses elliptic curve cryptography (ECC) to sign transactions so that network participants can verify funds are being spent by their rightful owners.

Specifically, Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) with secp256k1 parameters (also known as a Koblitz curve), to generate a public/private key pair.

In 2011, Bitcoin developers questioned [1] the use of secp256k1 instead of a more widely-used curve such as secp256r1.

• "The specific curve used is pretty unusual... I'm not losing much sleep over the theoretical possibility of an attack on secp256k1, but it is likely to be less widely implemented." -- Hal Finney
• "I discussed this with Satoshi. There is no particular reason why secp256k1 is used. It just happened to be around at the time." -- Mike Hearn
• "One plausible option for a future bitcoin-like system is to allow a selection from a numbered range of pre-selected curves." -- ByteCoin

Today, Ethereum and Ripple also use ECDSA with secp256k1 but both are planning to add support for and even transition to another ECC based system, Ed25519 [2].

• "It is becoming increasingly understood that the specific kind of signature used by Bitcoin is far from optimal; ed25519 is increasingly recognized as a superior alternative particularly because of its simpler implementation, greater hardness against side-channel attacks and faster verification." -- Vitalik Buterin [3]
• "Ed25519 addresses many of the ongoing security concerns surrounding commonly used cryptosystems… and avoids several design constraints inherent to secp256k1 ECDSA." -- Ripple [4]

Ed25519 makes use of Curve25519 which is widely deployed[5] and considered "safe" whereas secp256k1 is "unsafe"[6] due to an increased risk of error during implementation.

However, in August 2015, the U.S. National Security Agency (NSA) released a policy statement [7] advising against investing resources into ECC but instead prepare for a transition to quantum resistant algorithms. This has resulted in much debate and speculation amongst cryptographers [8][9].

Given the above, this BUIP recommends taking pragmatic and pro-active steps to safeguard users by adding flexibility and agility into the key generation and transaction validation processes.

High Level Design

Add a configuration option so users can choose a cryptosystem and when it starts and expires. The default will be to use Bitcoin's current system, ECDSA with secp256k1. For example, the following configuration would start generating keys with Ed25519 from block 500,000 with miners and other validators accepting keys from the old key system for another 100,000 blocks:

Default,0-600000
Ed25519,500000​

A different address prefix (version byte) could be used for keys created with different cryptosystems. This would result in addresses beginning with a leading symbol different from regular Bitcoin addresses which begin with 1, making them easily identifiable for humans. This would enable multiple cryptosystems to be used at the same time, rather than merely transition from one to another. If the Bitcoin community adopted this model, it would then be possible to transfer funds associated with a secp384r1 key to a Ed25519 key. Configuration might look like this:

Default,0
Ed25519,500000
Secp384r1,500000​

Today, OP_CHECKSIG only verifies ECDSA secp256k1 signatures. In future, it could verify different signature algorithms based upon the address prefix or an over-riding configuration option. It would also be possible to create new OP_CHECKSIG commands for different algorithms, but this would be at the expense of using up opcodes.

This BUIP recommends adding support for a new cryptosystem and leaving it disabled by default. For example, Ed25519 would keep Bitcoin on par with its cryptocurrency peers and establish a process for adding and testing new algorithms. The choice of cryptosystem should be based upon input from the cryptographic community, taking into account the characteristics of potential candidates which are best suited for Bitcoin e.g. speed, signature size, available (patent-free) implementations.

With a second cryptosystem already deployed, in the event of a vulnerability with secp256k1, miners and users could easily and rapidly switch over with a simple change to the configuration of their node or wallet. If the community had in fact adopted usage of multiple cryptosystems, a vulnerability discovered in one algorithm would not necessarily affect all Bitcoin users, as it would today.

Links of interest:

FourQ elliptic curve "FourQ is around four to five times faster than the original NIST P-256 curve and between two and three times faster than curves that are currently under consideration as NIST alternatives, such as Curve25519"
http://research.microsoft.com/en-us/projects/fourqlib/

“A Riddle Wrapped in an Enigma” by Neal Koblitz and Alfred J. Menezes
https://eprint.iacr.org/2015/1018.pdf

References:

[1] https://bitcointalk.org/?topic=2699.0

[2] http://ed25519.cr.yp.to/

[3] https://blog.ethereum.org/2015/07/05/on-abstraction/

[4] https://ripple.com/dev-blog/curves-with-a-twist/

[5] http://ianix.com/pub/curve25519-deployment.html

[6] http://safecurves.cr.yp.to/

[7] https://www.nsa.gov/ia/programs/suiteb_cryptography/

[8] https://www.schneier.com/blog/archives/2015/08/nsa_plans_for_a.html

[9] http://blog.cryptographyengineering.com/2015/10/a-riddle-wrapped-in-curve.html

 

[YarkoL]

This BUIP recommends adding support for a new cryptosystem and leaving it disabled by default.

Why disabled? If keys generated with different cryptosystems were distinguished from each other by address prefixes and software being able to validate each of them, then why not simply let the user pick whatever she likes?

edit - ah OK I didn't see reading the BUIP for the 1st time that you included that scenario too.
But do you see some utility in having everyone using the same cryptosystem if several are possible?

 

[solex]

@bitcartel
This is a very sophisticated change which has not yet had much public feedback, so I would like to defer voting on it. Votes are likely to be monthly, so it does not have to be deferred for long if there is enthusiasm for it.

 

[Roy Badami]

I don't think this BUIP is sufficiently complete in order to allow meaningful voting.

Address prefixes don't appear on the blockchain so I don't see how OP_CHECKSIG can depend on them. A standard P2PKH transaction (OP_DUP OP_HASH160 <pubkeyhash> OP_EQUALVERIFY OP_CHECKSIG) contains only the hash of the public key.

This is a change in the consensus rules yet there is no proposal on how to handle that the consensus change. A hard fork? A soft fork? In practice, a soft fork seems too dangerous but in any case the fork will require overwhelming consensus. Unless there's a realistic prospect of coming up with a proposal that will have support of an overwhelming supermajority of pools, this is a non starter IMO.

roy
[doublepost=1454017936][/doublepost]Just to add: to my mind as it stands, this is more a statement of work than a technical proposal. There's nothing wrong with that - it might be quite useful for people to be able to submit non-binding proposals for workstreams, which members could vote on, in order to help inform the project as to the priorities of the membership.

I think such proposals could usefully be in a separate document stream from BUIPs, though; it seems more useful for BUIPs to be limited to proposals that are substantially complete and implementable.