Hal (OP)
VIP
Sr. Member
Offline
Activity: 314
Merit: 3991
|
Bitcoin uses elliptic curve cryptography for its keys and signatures, but the specific curve used is pretty unusual. It is called secp256k1, from a standard called SEC2, published by a group called SECG, http://www.secg.org/index.php?action=secg,docs_secg. Taking the name secp256k1 apart, sec comes from the standard, p means that the curve coordinates are a prime field, 256 means the prime is 256 bits long, k means it is a variant on a so-called Koblitz curve, and 1 means it is the first (and only) curve of that type in the standard. This is all fine and common, except for the Koblitz part. Koblitz curves are a special kind of elliptic curves that have some internal structure that can be used to speed up calculations. Standards bodies have tended to shy away from Koblitz curves out of fear that this internal structure could someday be exploited to yield a new attack. Indeed certain Koblitz curves, but not secp256k1, lose a couple dozen bits of security to a known attack. Most standards use what are called random curves when they are using prime fields. SEC2 also includes random curves, and the very next one after secp256k1 is called secp256r1. This curve, secp256r1, is widely standardized and used, including by the U.S. government, which calls it P-256. I don't know the rationale behind using secp256k1. It has the potential for speed - I've seen estimates from 33% to 50% speedup - but the techniques are quite esoteric as it is not a conventional Koblitz curve, and I doubt that the OpenSSL implementation exploits this. I'm not losing much sleep over the theoretical possibility of an attack on secp256k1, but it is likely to be less widely implemented. I looked at BouncyCastle, a widely used Java crypto library, and they had commented out the code for secp256k1. Whereas secp256r1 (P-256) might well be a default curve for the native crypto keys in future OS's. It wouldn't be a change to make lightly, but we might want to consider changing to this more widely used standard curve. We'd have to mark the new keys to distinguish them, and be prepared to handle both kinds of signatures. One question is whether we would ever reach a point where clients could eliminate support for the old curve? Maybe just miners could retain support, and the fact that a transaction got into a block with some confirmations would be good enough evidence that it was valid.
|
Hal Finney
|
|
|
Mike Hearn
Legendary
Offline
Activity: 1526
Merit: 1129
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 09, 2011, 01:04:21 PM |
|
Have you mailed Satoshi to ask him? I would be interested in why this was chosen too. Unfortunately I didn't really get solid answers last time I asked Satoshi to explain the choice of a few implementation details (eg why 21M coins, answer "educated guess") but maybe you'd have better luck.
BitCoin addresses already have version codes in them, so it wouldn't technically be too hard to switch curves for newly created keys - just a matter of waiting long enough for people to upgrade their clients. I don't think it's likely support for old addresses would ever be removed, being able to do a full block chain verification is likely to be a feature desired by any non-thin client implementor.
That said, there should be a strong rationale. Lack of support doesn't seem to be a good enough reason. I have a Java implementation based on Bouncy Castle working fine with this curve, and helmut in IRC mentioned he had it working in Python too. Worst case you have to specify the parameters to the library yourself, but this isn't hard.
The possibility of an attack on Koblitz curves is a stronger reason, even if it's only a perceived risk rather than a credible one. Support could be phased in slowly over time, for instance, clients could be programmed to start creating secp256r1 keys by default a year after their introduction as measured in block time. This would reduce the disruption significantly.
|
|
|
|
Gavin Andresen
Legendary
Offline
Activity: 1652
Merit: 2297
Chief Scientist
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 09, 2011, 05:44:15 PM |
|
I agree with mh-- if there are real compatibility issues or weaknesses, then those would be a good reason to switch curves.
If there aren't, sep256k1 seems plenty good enough for the forseeable future. I think most programmers (myself included) have a tendency to worry about small-probability "what if" problems that we know how to solve, when we'd be better off thinking about high-probability problems that we don't want to think about because we don't already know how to solve them.
Like multifactor wallet authentication so trojans don't steal users' wallets....
|
How often do you get the chance to work on a potentially world-changing project?
|
|
|
Cdecker
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 09, 2011, 06:43:11 PM |
|
Finding an implementation in Java that would not conflict with the BC version on Android was a bit hard, but I found flexiprovider[1] which has a decent implementation in Java, no idea if they use some of the speedup tricks. But for mobile devices being able to verify transactions involving my own address is a must have, and then using a simpler/faster algorithm would make sense :-) [1] http://flexiprovider.de/
|
|
|
|
Mike Hearn
Legendary
Offline
Activity: 1526
Merit: 1129
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 09, 2011, 08:46:12 PM |
|
It's still worth considering a move away from secp256k1 as changes like this are much easier to make in the projects early days than later, and to be convincing the cryptography behind BitCoin must be unquestionable. If one day BitCoin has hundreds of thousands of users we don't want people using this as a club to beat us over the head with.
That said Gavin is totally right that compared to other security problems BitCoin has (malware, DoS) this one sounds kind of trivial.
How about suggesting a rollout schedule to Satoshi and seeing what he thinks? Implementation wise it'd not be a huge burden, I think.
BTW Chris, you can use Bouncy Castle on Android, you just have to use the lightweight API and rename it to not have the same package names. A good IDE can do this automatically.
|
|
|
|
davux
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 09, 2011, 09:03:06 PM |
|
Have you mailed Satoshi to ask him?
OMG. Would anyone mail Satoshi to inform him of the existence of this forum? Sorry for being bitter, but this is becoming frustrating.
|
1DavuxH9tLqU4c7zvG387aTG4mA7BcRpp2 México (Oaxaca) – France - Leeds
|
|
|
Mike Hearn
Legendary
Offline
Activity: 1526
Merit: 1129
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 09, 2011, 09:55:59 PM |
|
Satoshi does communicate both over email and this forum. I've had several good conversations with him about aspects of the BitCoin system.
Changing curves would mean a new address version (easy), a new OP_CHECKSIG equivalent for the new curve and a network upgrade to understand both of these. Anything else I forgot?
/mike
|
|
|
|
ByteCoin
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2011, 01:08:37 AM |
|
prime is 256 bits long, k means it is a variant on a so-called Koblitz curve, and 1 means it is the first (and only) curve of that type in the standard. This is all fine and common, except for the Koblitz part. Koblitz curves are a special kind of elliptic curves that have some internal structure that can be used to speed up calculations.
I'm not aware of any academic cryptography papers that refer to any curves over prime fields as Koblitz curves. The standards bodies publications do not count as academic papers and I believe that their inclusion of "k" in the name is idiosyncratic. Indeed the standard states "Here ..[the term "Koblitz"] is generalized to refer also to curves over F_p which possess an efficiently computable endomorphism. [Allong the lines of the paper of Gallant, Lambert and Vanstone "Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms"] This scheme tends to be referred to in the literature as the "GLV method" When selecting appropriate cryptography you can vary the "size" parameter which has an obvious effect on security. You can also vary the "peculiarity" paramter which can substantially increase the speed at the cost of a small reduction in the effective "size". Before worrying whether the special nature of the secp256k1 curve loses a few bits of security relative to a random curve we need to examine what reasoning informed the selection of a 256bit curve. Possibly a 224 bit or 192 bit curve would have been perfectly satisfactory. That being the case, the theoretical loss of security due to the special nature of the secp256k1 curve is inconsequential while the speed increase is still useful. I forsee a general trend towards the use of more specialized curves over the vanilla random elliptic curves as the performance gains are substantial. This is comparable to the shift away from vanilla RSA towards the more specialized ECC in return for shorter keys, that happened about ten years ago. I see little justification for retiring secp256k1 without a complete redesign of Bitcoin to address existing deficiencies in scalability and implementation security. Future schemes, however, should avoid hard-coding any particular implementation of the essential cryptographic primitives. ByteCoin
|
|
|
|
Mike Hearn
Legendary
Offline
Activity: 1526
Merit: 1129
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2011, 10:35:03 AM |
|
I believe the key factor in the choice of curve, size and indeed ECC itself was the size of the block chain - which is ultimately based on a set of educated guesses. The key.h file has a list of signature sizes at the top along with a comment that the script system can encode signatures of up to 75 bytes with a single size opcode. It's hard to know if that's the reason or not but it seems likely.
Becoming fully generic would mean encoding curve parameters into ... where? Addresses? Scripts and thus the block chain? All of those would make transactions much much larger and reduce the scalability of the network as a result. We know Satoshi cares a lot about block chain size, this is why we cannot embed messages into transactions.
/mike
|
|
|
|
ronaldmaustin
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2011, 02:28:50 PM |
|
I am not the cryptographer that all of you appear to be but, to me, this discussion raises a disturbing point. You all appear to be saying that the encryption algorithm for Bitcoin generation and future security is changeable at this time. How is that? I thought this was all some open source program and client that was all put "out there" in P2P space with no central authority. The fact that this person Satoshi (the inventor?) has the power to change the encryption method at will, does that not mean that he is a central authority, not unlike a bank, that can alter how the rest of the 75% 21 million coins are minted?
|
|
|
|
caveden
Legendary
Offline
Activity: 1106
Merit: 1004
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2011, 02:42:49 PM |
|
Anyone could perform such change. It's open source.
If you make a fundamental change, you'll probably end up forking the project. Some might follow you, some will remain using the previous branch.
|
|
|
|
ronaldmaustin
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2011, 02:47:40 PM |
|
I guess I'd follow whomever releases the client, whether I knew it contained changes or not. Most would.
|
|
|
|
0x6763
Guest
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2011, 03:17:30 PM |
|
I am not the cryptographer that all of you appear to be but, to me, this discussion raises a disturbing point. You all appear to be saying that the encryption algorithm for Bitcoin generation and future security is changeable at this time. How is that? I thought this was all some open source program and client that was all put "out there" in P2P space with no central authority. The fact that this person Satoshi (the inventor?) has the power to change the encryption method at will, does that not mean that he is a central authority, not unlike a bank, that can alter how the rest of the 75% 21 million coins are minted?
Satoshi is the creator and main developer of Bitcoin. He can make changes to the software, creating a new version, and allow others to download this new updated version...it's everyone else's choice as an individual whether they will download the new version and use it, use an older version, use someone else's version of bitcoin, write their own version, or not use bitcoin anymore. Satoshi can't just modify the code on anyone else's machine. He has no control over the software running on anyone else's machines, but is merely the most popular provider of Bitcoin software. Since his software is currently used by the majority of Bitcoin users, it effectively defines the Bitcoin protocol standard, which means that Satoshi currently defines the protocol standard. But this is not a technical issue, but rather a social one. If some other implementation of bitcoin gains in popularity, it can lead to either someone else setting the protocol standards, or a fork in the block chain. If there are two or more alternative bitcoin implementations out there, and none of them have a majority of the users, then it can still lead to forks of the block chain unless the developers of the different implementations continue to agree on a standard. Those that don't agree with the standard and fork the block chain will most likely lose users as a forked block chain will be less secure as well as incompatible with the other chain(s), which is not in the interest of many users. So currently, Satoshi has a significant social influence on the bitcoin protocol, but he does not have control over the network or anyone's software. The apparent "centralization" is merely a voluntary/anarchistic social one, that will remain only as long as enough users agree with or will tolerate Satoshi's decisions. If he makes a choice that most users won't like, bitcoin will either collapse or (more likely) the block chain will be forked and not implement the unwanted changes. Satoshi's influence is not brought about by force, and is therefore not comparable to that of a government created/protected central bank that can change the monetary system at a whim without the peoples' say.
|
|
|
|
Mike Hearn
Legendary
Offline
Activity: 1526
Merit: 1129
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 11, 2011, 10:31:40 PM |
|
I discussed this with Satoshi. There is no particular reason why secp256k1 is used. It just happened to be around at the time.
However it sounds like there's no real consensus that the k1 curve is really a terrible thing and indeed it may even be helpful in future as ECDSA verification is the primary CPU bottleneck for running a network node. So if Koblitz curves do indeed perform better we might end up grateful for that in future ...
|
|
|
|
ByteCoin
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 12, 2011, 03:03:21 AM |
|
Becoming fully generic would mean encoding curve parameters into ... where?
One plausible option for a future bitcoin-like system is to allow a selection from a numbered range of pre-selected curves. Smaller transactions or balances could use smaller keysizes if necessary. this is why we cannot embed messages into transactions.
You can still embed messages into transactions see http://bitcointalk.org/index.php?topic=2393.msg32288#msg32288ByteCoin
|
|
|
|
bitanarchy
Newbie
Offline
Activity: 43
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 12, 2011, 05:35:34 PM Last edit: January 12, 2011, 11:53:48 PM by bitanarchy |
|
I also discussed with satoshi, and he said that his employers at the NSA wanted him to create the first P2P currency with a back door in it. That back door happens to be in this specific elliptic curve. Government supercomputers searched for a random elliptic curve that contained a back door.
Just joking, but that's my conspiracy theory. Actually if there is no particular reason for this elliptic curve to be chosen, that is actually suspicious...
|
|
|
|
0x6763
Guest
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 14, 2011, 02:10:43 AM |
|
I looked at BouncyCastle, a widely used Java crypto library, and they had commented out the code for secp256k1.
The current version of BouncyCastle (version 1.45 at the time I'm writing this) has secp256k1 available as far as I can tell. org.bouncycastle.asn1.sec.SECNamedCurves.getNames() will give you a list of some named curves (including "secp256k1"). org.bouncycastle.asn1.sec.SECNamedCurves.getByName("secp256k1") will give you an org.bouncycastle.asn1.x9.X9ECParameters object Here's an example of what I get in Clojure: user> (enumeration-seq (org.bouncycastle.asn1.sec.SECNamedCurves/getNames)) ("sect233r1" "secp112r2" "secp112r1" "secp256k1" "sect113r2" "secp521r1" "sect113r1" "sect409r1" "secp192r1" "sect193r2" "sect131r2" "sect193r1" "sect131r1" "secp160k1" "sect571r1" "sect283k1" "secp384r1" "sect163k1" "secp256r1" "secp128r2" "secp128r1" "secp224k1" "sect233k1" "secp160r2" "secp160r1" "sect409k1" "sect283r1" "sect163r2" "sect163r1" "secp192k1" "secp224r1" "sect239k1" "sect571k1") user> (org.bouncycastle.asn1.sec.SECNamedCurves/getByName "secp256k1") #<X9ECParameters org.bouncycastle.asn1.x9.X9ECParameters@aab35699>
|
|
|
|
Realpra
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 23, 2012, 05:53:31 PM |
|
Don't know if anyone knows this, but how do you take advantage of the speedup built into the koblitz curve?
Is it automatic? You do something special?
Is the BTC client already using the speedup opportunity? Even if it's not, could someone point me to the source code location of said algorithm?
Thanks in advance and sry for bumping.
|
|
|
|
kjj
Legendary
Offline
Activity: 1302
Merit: 1026
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 23, 2012, 07:48:25 PM |
|
Google "GLV method". I didn't see any source code, but several academic papers and slide decks about it.
To use it, you need to be able to precompute a multiple of a point (which is a property of the curve used), then you can factor a future multiplication on that curve into two multiplications each with half as many bits. For what bitcoin does, I don't think the complexity is worth a 30% to 50% gain in speed.
|
17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8 I routinely ignore posters with paid advertising in their sigs. You should too.
|
|
|
Realpra
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 23, 2012, 09:43:49 PM |
|
For what bitcoin does, I don't think the complexity is worth a 30% to 50% gain in speed.
Thanks a bunch. I'm researching this to develop a btc smart card which is more limited. If it's easy to do it it may be worth it...
|
|
|
|
|