Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

New API Proposal: Add SECG curves, especially secp256k1 #8

Closed
Sajjon opened this issue Feb 3, 2020 · 34 comments
Closed

New API Proposal: Add SECG curves, especially secp256k1 #8

Sajjon opened this issue Feb 3, 2020 · 34 comments

Comments

@Sajjon
Copy link
Contributor

Sajjon commented Feb 3, 2020

New API Proposal: Add secp256k1curve

Motivation:

I REALLY think we should add EC Curve secp256k1.

I can make a PR - if I know Apple will not reject it automatically just because it is a SECG curve and not a NIST curve?(or due it being "the Bitcoin curve")

If we were to allow SECG curves (the whole crypto community would love it if we did), then it would make sense to renamed the existing curve using NIST naming to use SECG naming instead, see Appendix A in RFC4492

Why add support for secp256k1? Well, Crypto currencies are on the rise (despise crypto winter of 2018/2019), and App Store contains lots of wallets already - a vast share of which are crypto currencies using the secp256k1 (since most coins are ERC20 tokens based on Ethereum, and all coins in top 8 use sec256k1, I approximate 95% of the total market cap of cryptocurrencies rely on secp256k1).

Since there are no native Swift lib for secp256k1, we see lots of unsafe libs, such as my own EllipticCurveKit, hyugit/EllipticCurve, EllipticSwift, all of which, including mine are unsafe.

One of the most popular projects is a wrapper of C library secp256k1, named BitcoinKit, but it does many things, including HD Wallet and is a bit messy.

So in order to protect users of iOS crypto wallets from losing funds due to errors/unsafe code, I think it is important that we add this curve.

Importance:

No we cannot use this curve today, but it is easy to add it I can make a PR.. I've dabbled in Crypto a bit before EllipticCurveKit, PRs into BitcoinKit.

@Sajjon Sajjon changed the title Add SECG curves, especially sec256k1 - I can create a PR. Add SECG curves, especially secp256k1 - I can create a PR. Feb 3, 2020
@Lukasa
Copy link
Contributor

Lukasa commented Feb 3, 2020

Thanks for this! Can you begin by filling out the API proposal template? This would help focus the discussion more clearly.

@Sajjon
Copy link
Contributor Author

Sajjon commented Feb 3, 2020

@Lukasa of course, how silly of me, I got so excited when I saw this, and directly clone and found no secp2561, started coding a PR and realized I ought to ask first, but missed reading CONTRIBUTING.

Before I saw your comment I started with a rationale, I'm updating to conform to the template.

@Sajjon Sajjon changed the title Add SECG curves, especially secp256k1 - I can create a PR. New API Proposal: Add SECG curves, especially secp256k1 Feb 3, 2020
@Sajjon
Copy link
Contributor Author

Sajjon commented Feb 3, 2020

@Lukasa Is this format OK? Need any more input? Should I change anything?

Thanks!

@Lukasa
Copy link
Contributor

Lukasa commented Feb 3, 2020

This update is fab, thanks. We’ll have a conversation and get to our feelings about whether secp256k1 is in-scope for addition to Swift Crypto.

@paulmillr
Copy link

paulmillr commented Feb 4, 2020

It’s pretty bad to NOT implement this. secp256k1 is one of a few elliptic curves that are really popular, today.

If you’re open sourcing a library, but don’t want contributions for a curve that’s used in every third project — what’s the point? We can continue to use our own libs...

@Lukasa
Copy link
Contributor

Lukasa commented Feb 6, 2020

Thanks very much for this proposal! You did a good job laying out the use-cases for secp256k1 (and, in #22, RIPEMD) support in Swift Crypto.

After careful consideration, my colleagues and I have concluded that we do not believe secp256k1 support meets the bar for entry into the Swift Crypto API at this time. Before I explain why in more detail, I want to clarify that this is not because we believe that secp256k1 is flawed or that we think it has no use-cases, and we absolutely believe there is space in the open-source Swift ecosystem for a library that provides good APIs for accessing this curve. Unfortunately, we do not believe that Swift Crypto is the right place for this implementation. Please note that if circumstances change and the cryptography landscape changes, we may revisit this decision.

In the case of Swift Crypto, our explicit goal is to build a library that focuses on constructions that are, amongst other criteria, “broadly useful”. An important corollary of this goal is that we need to avoid providing too many constructions that do similar things with unclear distinctions. To take an example from a different part of the API surface of this library, each additional AEAD cipher construction we add to this library forces users to ask themselves whether they should use that construction, instead of another.

In the case of the elliptic curves, we already have a reasonably large number of them. This sets the “broadly useful” bar for each additional curve we add even higher, as the curve now needs not only to be useful enough to be included but also to justify adding to the decision matrix for users who need to pick a curve for their use-cases. The question is, does secp256k1 enable a sufficient set of use-cases to justify adding it to the API?

In this case, secp256k1 is used almost exclusively in the cryptocurrency community. Outside of that community, secp256k1 is a highly unusual curve to use. This means that it has a fairly narrow set of use-cases in which it is a reasonable default. This adds asymmetrical API risk to the API: users building cryptocurrency wallets will immediately know that they need secp256k1 and can dismiss the other choices, while users building other constructions (of whom there are vastly more) will now need to research and consider secp256k1 to validate whether it is suitable before they dismiss it. The burden of this new API falls much more heavily on the more-common use-cases. For better or worse, P-256 has much wider deployment than secp256k1, and therefore has an easier time justifying its presence in Swift Crypto than secp256k1 does.

Additionally, BoringSSL does not have an optimised implementation of secp256k1. We can have BoringSSL implement it using the custom curves functionality, but this will make the performance of secp256k1 substantially worse than the optimised NIST curves currently exposed via Swift Crypto. That’s an unfortunate and surprising performance cliff to hit for unsuspecting users who may reasonably assume that the performance of these curves could be expected to be broadly similar.

In this instance, then, our recommendation is that you continue to pursue a high-quality secp256k1 implementation outside of Swift Crypto. If the API design of Swift Crypto is appealing for your intended use-case, the API design here is entirely available under Apache 2.0 and may freely be imitated in third-party libraries. As noted above, we will continue to keep an eye on the ecosystem and will be willing to revisit this decision if things change.

We understand that this is disappointing, but we believe that this choice will give the best results for everyone involved: those who need access to this primitive will almost invariably know to search for it, and we would love for them to be able to find a high quality implementation in the Swift open source ecosystem. We look forward to seeing the community's work in this space.

@Lukasa Lukasa closed this as completed Feb 6, 2020
@paulmillr
Copy link

Folks, it's pretty simple — Apple is doing everything in their power to slow down adoption of crypto projects.

That's disappointing, because they'll add it anyway in a couple years, when the adoption would be higher. Whatevs.

@KevinVitale
Copy link

"Please note that if circumstances change and the cryptography landscape changes, we may revisit this decision."@Lukasa.

Where does this leave the contributing community? Google describes BoringSSL as: "...a fork of OpenSSL that is designed to meet Google's needs.". You (and the team) could probably saved yourself many more drawn-out spats by being equally transparent about this project's goals.

@Lukasa
Copy link
Contributor

Lukasa commented Feb 11, 2020

You (and the team) could probably saved yourself many more drawn-out spats by being equally transparent about this project's goals.

I understand your frustration, but I don't believe there is a problem with transparency here. We have said in every project forum, including this repository's readme, that it is not a goal of Swift Crypto to support every cryptographic primitive in use today. This necessarily means that proposals for some (indeed, most) primitives will be refused.

On the issue of introducing specific additional elliptic curves to the supported set, we are not drawing bright lines in the sand ruling in or out specific curves and committing to the decision forever. Good stewardship of a library like this is necessarily fluid: as the landscape shifts, decisions can and should be revisited. However, we consider it vital to keep the supported set small to avoid non-expert users drowning under the weight of curve choices. At this time, we believe that rules out secp256k1. If the calculus changes here (e.g. because secp256k1 becomes widely used in less-specialised contexts, or other supported curves are removed) we will re-evaluate.

Where does this leave the contributing community?

We continue to welcome proposals from the community. We will continue to evaluate each proposal on its specific merits at the time of its proposal. The fact that we said no to this proposal does not mean we'll say no to others.

@Sajjon
Copy link
Contributor Author

Sajjon commented Apr 4, 2021

@Lukasa I see what you did here (This is an EC SPKI object with an unsupported named curve.) 😅

@Cyclic
Copy link

Cyclic commented Nov 4, 2021

Thanks very much for this proposal! You did a good job laying out the use-cases for secp256k1 (and, in #22, RIPEMD) support in Swift Crypto.

After careful consideration, my colleagues and I have concluded that we do not believe secp256k1 support meets the bar for entry into the Swift Crypto API at this time. Before I explain why in more detail, I want to clarify that this is not because we believe that secp256k1 is flawed or that we think it has no use-cases, and we absolutely believe there is space in the open-source Swift ecosystem for a library that provides good APIs for accessing this curve. Unfortunately, we do not believe that Swift Crypto is the right place for this implementation. Please note that if circumstances change and the cryptography landscape changes, we may revisit this decision.

In the case of Swift Crypto, our explicit goal is to build a library that focuses on constructions that are, amongst other criteria, “broadly useful”. An important corollary of this goal is that we need to avoid providing too many constructions that do similar things with unclear distinctions. To take an example from a different part of the API surface of this library, each additional AEAD cipher construction we add to this library forces users to ask themselves whether they should use that construction, instead of another.

In the case of the elliptic curves, we already have a reasonably large number of them. This sets the “broadly useful” bar for each additional curve we add even higher, as the curve now needs not only to be useful enough to be included but also to justify adding to the decision matrix for users who need to pick a curve for their use-cases. The question is, does secp256k1 enable a sufficient set of use-cases to justify adding it to the API?

In this case, secp256k1 is used almost exclusively in the cryptocurrency community. Outside of that community, secp256k1 is a highly unusual curve to use. This means that it has a fairly narrow set of use-cases in which it is a reasonable default. This adds asymmetrical API risk to the API: users building cryptocurrency wallets will immediately know that they need secp256k1 and can dismiss the other choices, while users building other constructions (of whom there are vastly more) will now need to research and consider secp256k1 to validate whether it is suitable before they dismiss it. The burden of this new API falls much more heavily on the more-common use-cases. For better or worse, P-256 has much wider deployment than secp256k1, and therefore has an easier time justifying its presence in Swift Crypto than secp256k1 does.

Additionally, BoringSSL does not have an optimised implementation of secp256k1. We can have BoringSSL implement it using the custom curves functionality, but this will make the performance of secp256k1 substantially worse than the optimised NIST curves currently exposed via Swift Crypto. That’s an unfortunate and surprising performance cliff to hit for unsuspecting users who may reasonably assume that the performance of these curves could be expected to be broadly similar.

In this instance, then, our recommendation is that you continue to pursue a high-quality secp256k1 implementation outside of Swift Crypto. If the API design of Swift Crypto is appealing for your intended use-case, the API design here is entirely available under Apache 2.0 and may freely be imitated in third-party libraries. As noted above, we will continue to keep an eye on the ecosystem and will be willing to revisit this decision if things change.

We understand that this is disappointing, but we believe that this choice will give the best results for everyone involved: those who need access to this primitive will almost invariably know to search for it, and we would love for them to be able to find a high quality implementation in the Swift open source ecosystem. We look forward to seeing the community's work in this space.

Adding secp256k1 to swift-crypto should be reconsidered. Banking is adopting crypto, NFTs have become mainstream, and having a library such as SwiftCrypto adopt this curve will help a lot of developers build leaner, cleaner, and more reliable software. In addition, the argument that developers might be confused or have to research the performance differences when they're selecting the appropriate curve, by adding a popular, additional option, is a red herring. Please reconsider adding secp256k1 as soon as possible and help businesses and developers cleanup their swift dependencies.

@Sajjon
Copy link
Contributor Author

Sajjon commented Nov 4, 2021

@Cyclic I think we better make a case with some statistics - which shows the rapid user growth of Ethereum and Bitcoin users

@Sajjon
Copy link
Contributor Author

Sajjon commented Dec 11, 2021

@Lukasa Since I wrote this proposal soon two years ago Bitcoin and the crypto space as a whole have seen incredible growth.

Motivation

@Lukasa in Feb 2020 you wrote the following motivation for why secp256k1 was not a good fit for swift-crypto, it argued that the most important aspect for including new APIs to swift-crypto was the number of different applications it had. Furthermore, it seemed you counted all Distributed Ledger Technology (DLT) projects as one singular application. All due respect, this is not only unfair but in fact completely incorrect. Bitcoin is primary a cryptocurrency, that is true. But there are so many different applications built on top of Ethereum that aren't just implementations of a currency. This includes, but is not limited to (see more here):

Application of secp256k1

This is just a very short excerpt and mostly dApps on Ethereum. Many other DLT/networks using curve secp256k1 have rich ecosystems them too. E.g. Zilliqa (Zillion Staking, DEX ZilSwap, Pillar Protocol lending/dao).

So there are at least 13 completely different applications on top of DLT relying on secp256k1 except just being a "currency".

Adoption

Adopters

Since I wrote this proposal in beginning of 2020

The list goes on and on and on. All huge -- years ago (by some) unthinkable -- breakthroughs in Bitcoin and crypto adoption.

Usage

BTC active address growth: +42%

Here is ETH active address growth: +250%

Value

Total cryptocurrency market cap growth: +750%

TLV DeFi

Total Locked Value (TLV) in various lending and staking protocols in the Decentralize Finance (DeFi) world has grown by over 900% since beginning 2020
tlv_defi

Conclusion

I hope it is abundantly clear that secp256k1 both as many applications and also is widely used by a huge and exponentially growing user base. I see no reason to not assume that iPhone/Mac usage ratio of the general population would not apply to the current (and future) crypto user growd, i.e. we have millions upon millions of users on platforms running apps written in Swift. But still, to date, there are no secp256k1 library available for us Swift developers to write safe apps for our users. And these are not Candy Crush apps... these are applications "storing" billions of dollars of value.

So I implore you, please, to read through this update carefully and reconsider.

Solution

I believe the best solution is to include bitcoin-core/secp256k1 in swift-crypto, just like BoringSSL is included, and re-use the same nice Swifty bindings that swift-crypto provides for the other curves.

Schnorr

Now except for the need of the curve secp256k1, we also need the Schnorr signatures of bitcoin-core/secp256k1. Taproot which enables secure Bitcoin Lightning network (LN) channels require Schnorr signatures. LN has seen a 226% increase just in a year

Also above mentioned DLT Zilliqa uses Schnorr signatures

Luckily bitcoin-core/secp256k1 contains a great Schnorr sig implementation

@Sajjon
Copy link
Contributor Author

Sajjon commented Dec 11, 2021

One in four Americans own Bitcoin (sample size of 1000)

@Sajjon
Copy link
Contributor Author

Sajjon commented Jan 4, 2022

These images show growth of Bitcoin LN over the past three years:

https://twitter.com/documentingbtc/status/1478363439961681926?s=21

@Lukasa
Copy link
Contributor

Lukasa commented Jan 4, 2022

@Sajjon Thanks for these updates! The research you've done and the statistics you're providing are really valuable. I'd also like to thank you for being a continued voice in these discussions. The Swift community needs lots of users with different use-cases to help push the language and ecosystem forward.

Let me start with the top-level takeaway: at this time, we do not believe the fundamental trade-offs outlined in my original response have meaningfully changed, so we are still declining to support secp256k1. I would once again like to expressly underline that this is a point-in-time decision on an issue that will constantly evolve. We absolutely will regularly revisit this decision, and I encourage users like @Sajjon to continue to actively engage with us to keep that discussion going.

I'd like to take this opportunity to clarify some of the original points I made. Firstly, I'd like to address this comment:

@Lukasa in Feb 2020 you wrote the following motivation for why secp256k1 was not a good fit for swift-crypto, it argued that the most important aspect for including new APIs to swift-crypto was the number of different applications it had. Furthermore, it seemed you counted all Distributed Ledger Technology (DLT) projects as one singular application. All due respect, this is not only unfair but in fact completely incorrect.

I absolutely said "the cryptocurrency community" in my original response. I agree with the criticism that cryptocurrency is not the only distributed ledger use-case, and it's an inappropriate shorthand. Mea culpa, and I'm sorry for the error.

However, I did not intend to suggest that number of use-cases had any particular bearing on whether or not an algorithm is included. The concern we had was focused on the difficulty faced by users that is caused by having a wide range of primitives available that all appear to be very similar. In these circumstances, users are forced to attempt to understand what the specific trade-offs are between those choices, and why they may want to choose one or the other.

In the original response I noted that for secp256k1, this burden falls unequally. Expert users, attempting to build distributed ledger applications, will feel confident in reaching for that curve. Non-expert users, searching for an appropriate key exchange or signing primitive for their application, will need to tease out which choice will be better. This burdens the users least able to make informed decisions with the requirement to make an informed decision.

To analogise to a different use-case, swift-crypto does not provide more than one of the range of Salsa families of AEADs, despite choices other than ChaCha20 being used in prominent use-cases. This is because of the set, ChaCha20 is the most generally useful, and so earns pride of place.

This is not to say that we would never duplicate a use-case. After all, Crypto has two AEADs in it, and a good argument could be made that that represents a duplication as well. What we're saying instead is that we are doing our best to make judgement calls as to when the trade-off is worthwhile, and that we don't believe secp256k1 has yet reached that place. Again, I want to stress that this is our position as of early January 2022: the cryptography space is fluid, and the passage of time changes all things.

The other thing I said in my original post was that we would like to see a high-quality secp256k1 Swift open source project made available, potentially with a compatible API. This remains our primary recommendation. A Swift wrapper of the bitcoin-core implementation (or any other preferred high-quality implementation), following the API design principles used in this library, used widely by best-in-class applications, is the single strongest existence proof for the value of the curve. We'd love to see the community start there, and use that as the basis of further discussion.

@KevinVitale
Copy link

KevinVitale commented Jan 4, 2022

"...we would like to see a high-quality secp256k1 Swift open source project made available, potentially with a compatible API. This remains our primary recommendation. A Swift wrapper of the bitcoin-core implementation (or any other preferred high-quality implementation)"

There's been several, many which were available around the time this issue was created; however, I'll point to mine, which was extremely deliberate in making it Swifty (and wholly self-contained):

Stripping all the cryptocurrency-protocol APIs means adding secp256k1 is a couple of lines of code + a target in a Package.swift file.

These primitives are as critical to the web3 ecosystem as TLS/SSL is to HTTPS, and need no further technical explanation for why being included is important; it is a fundamental block to its particular public-key infrastructure. And while I applaud the community continuing to make a push for its inclusion, it's not happening folks. Also: Happy New Year! 🎉

@benjamin-wilson
Copy link

at this time, we do not believe the fundamental trade-offs outlined in my original response have meaningfully changed

Didn't @Sajjon provide detailed metrics on how it has changed by orders of magnitude? During the timespan of this discussion the crypto market cap has caught up with the entire market cap of Apple with similar increases in users and usage with no signs of slowing down.

The concern we had was focused on the difficulty faced by users that is caused by having a wide range of primitives available that all appear to be very similar. In these circumstances, users are forced to attempt to understand what the specific trade-offs are between those choices, and why they may want to choose one or the other.

Is it not assumed a developer with sufficient knowledge to use swift-crypto would understand or be capable of researching the choices offered by the library? They would have to be capable of this anytime there is more than one to choose from. To say developers would be completely overwhelmed and incapable of making the correct choice for their needs is patronizing.

What we're saying instead is that we are doing our best to make judgement calls as to when the trade-off is worthwhile, and that we don't believe secp256k1 has yet reached that place.

Can you share the criteria that would have to be met to include secp256k1 in swift-crypto with the community? Otherwise it appears as if there are moving goalposts.

@Lukasa
Copy link
Contributor

Lukasa commented Jan 4, 2022

Can you share the criteria that would have to be met to include secp256k1 in swift-crypto with the community? Otherwise it appears as if there are moving goalposts.

I hope I haven't ever given the impression that there was some secret objective criteria that had to be met. There is not. There exists no "you must be this tall to ride" standard against which we are measuring secp256k1. I'm sympathetic to the frustration you feel here, but I think I've been entirely fair throughout this process: I never claimed there existed some objective criteria that had to be met. I feel that I've been extremely clear that this is an exercise in design and in tradeoffs.

@Lukasa
Copy link
Contributor

Lukasa commented Jan 4, 2022

@KevinVitale Your implementation seems very cool! Can you point me to some applications or projects that use it?

@KevinVitale
Copy link

KevinVitale commented Jan 4, 2022

I really appreciate the kind words, @Lukasa. I'm extremely happy to say that the specific secp256k1 code in my project is simply the same implementation used by several millions of web3 applications @Sajjon has provided evidence to.


For added context: my project's aim was more motivated by seeing too many other similar projects that weren't importing these C-based crypto primitives in ways which seemed considerate to what the SPM was capable of; or rather: I wasn't seeing obvious uses of the tooling I would expect, given my many years as a professional Swift developer.

The result was great! I educated myself with how to implement cryptocurrency wallets, I was able to quickly port Swift code (with tests!) to Linux, and learned a great deal about inner workings of the Swift Package Manager, even going so far as to share the almighty PRO TIPS!

@benjamin-wilson
Copy link

I hope I haven't ever given the impression that there was some secret objective criteria that had to be met.

I will admit I did get that impression from your original response:

...we do not believe secp256k1 support meets the bar for entry
...our explicit goal is to build a library that focuses on constructions that are, amongst other criteria, “broadly useful”.
The question is, does secp256k1 enable a sufficient set of use-cases to justify adding it to the API?
...it has a fairly narrow set of use-cases

The second main point of your response was the added 'decision matrix' and performance costs for 'unsuspecting users' which I had addressed. I don't think you're giving users of swift-crypto the credit they deserve and under that argument it seems like adding any additional functionality would be opposed, no matter how broadly useful it is - if it is similar to existing functionality.

I would like to see a more concise and to the point explanation as to why secp256k1 will not be currently added as all the discussion and response has made it unclear.

@KevinVitale
Copy link

gm

@Lukasa
Copy link
Contributor

Lukasa commented Jan 5, 2022

under that argument it seems like adding any additional functionality would be opposed, no matter how broadly useful it is - if it is similar to existing functionality.

It would not be opposed, it would simply have to be more valuable. The more similar something is to already supported functionality, the more value it must provide to justify inclusion. Swift Crypto explicitly considers it a non-goal to support a wide range of primitives: we are picking and choosing. As an example, consider the relatively limited RSA support: RSA has substantially more prominent and varied uses than secp256k1, and support for it was added in a very grudging and limited fashion. For another example, consider the non-inclusion of Curve448.

None of these are ruled in or out forever. We are constantly re-evaluating (as demonstrated by the fact that we did, eventually, include some RSA functionality).

I would like to see a more concise and to the point explanation as to why secp256k1 will not be currently added as all the discussion and response has made it unclear.

At this time, we believe that it imposes more cognitive burden for users in the aggregate than the value it brings in enabling new use cases and enhancing existing ones.

@Sajjon
Copy link
Contributor Author

Sajjon commented Jan 5, 2022

@Lukasa thank you Cory for your patience with all of us demanding Bitcoiners. You probably have to count on us writing here until end of time, or until secp256k1 gets added. I hope people lobbying the support for it will keep it civil and constructive, not only letting our frustration shine through.

So OK still no secp256k1 support for now, got it. So let's try another idea.

I've started working on an "extension" of swift-crypto in a fork, I call it K1,
I use another approach than GigaBitcoin/secp256k1.swift (which is also a fork of swift-crypto), I want to reuse the GYB Boilerplate to make my APIs identical to e.g. P256 (secp256r1) which is part of swift-crypto. I don't remember the state of my mess of a fork... it has been 9months since I started. But anyway, here is a commit in which I needed to alter the GYB files, to support other curves than NIST curves - as the name of this issue suggests:
SECG curves.

I am not at all any Swift Package Manager pro... but could we update the current implementation to make it easier to - in forks/consumers of this repo - add custom curves, kind of in a plugin manner? Regarding SPM, I was thinking of SE-0303: Extensible Build Tools, which was implemented in Swift 5.6. I'm most likely lost here... anyway, do you have any creative idea, what you would be willing to support/include/implement that would make it easier to support custom curves?

I will probably write more questions and motivations for inclusion of secp256k1 at a later time. I hope we ALL keep it civil and constructive here in the mean time, so that @Lukasa don't feel like muting this issue 😅

Hope you all have a great start of 2022 🥳

@Lukasa
Copy link
Contributor

Lukasa commented Jan 6, 2022

You probably have to count on us writing here until end of time, or until secp256k1 gets added.

I look forward to it! I mean this genuinely: good decisions are not made in a vacuum, and silent constituencies are hard to serve. There are no final decisions in this business, only temporary ones.

I am not at all any Swift Package Manager pro... but could we update the current implementation to make it easier to - in forks/consumers of this repo - add custom curves, kind of in a plugin manner?

Can you clarify what exactly you envision a custom curve plugin interface looking like? Is this something that manifests programmatically? Or are you thinking more like a codegen tool that will spit out the scaffolding of an EC key API, and defers to a backing implementation?

@Sajjon
Copy link
Contributor Author

Sajjon commented Jan 8, 2022

@Lukasa I thought maybe we could ease the addition of custom curves via GYB using SPM plugins, if SE-0303 allowed for the execution of GYB before compilation... but never mind that!

As I see it two completely different can be used to support different ECC curves:

  1. Individual types - Signing.PrivateKey and Signing.PublicKey - under separate namespaces, like enum P256 and enum P384
  2. Generics, like PrivateKey<Curve: ECCurve>

swift-crypto has chosen design 1), but could easily be changed to 2) and then be solved with a typealias like so:

protocol ECCurve { ... }

struct ECPrivateKey<Curve: ECCurve> {}

// namespace provider for P256, also named secp256r1
public enum P256 {}

public enum CurveP256: ECCurve { ... }

public extension P256 {
    typealias PrivateKey = ECSigningKey<CurveP256>
}

Now API is unchanged, we have P256.PrivateKey like before, which is nongeneric and specific for the NIST curve P256.

  1. Alternative requires the use of GYB to generate the boilerplate code, this is not needed using 2). Also using 2) is more extensible consumers of swift-crypto can easily create their own curves (and typealiaes as shortcuts).

This is exactly how I designed it in Sajjon/EllipticCurveKit.

let privateKey = PrivateKey<Secp256r1>(hex: "0x7D7DC5F71EB29DDAF80D6214632EEAE03D9058AF1FB6D22ED80BADB62BC1A534")!
let publicKey = PublicKey<Secp256r1>(privateKey: privateKey)
XCTAssertEqual(publicKey.hex.compressed, "03EAD218590119E8876B29146FF89CA61770C4EDBBF97D38CE385ED281D8A6B230")

Where the ECCurve protocol looks like this, below named EllipticCurve and full code here:

public protocol EllipticCurve {
    static var form: EllipticCurveForm { get }
    typealias Point = AffinePoint<Self>
    static var P: Number { get }
    static var a: Number { get }
    static var b: Number { get }
    static var G: Point { get }
    static var N: Number { get }
    static var h: Number { get }
    static var name: CurveName { get }
}

public extension EllipticCurve {
    static var form: EllipticCurveForm { return .shortWeierstrass }
}

And P256 (also named secp256r1) (full code here)

typealias Number = BigInt // some big int...

/// The curve E: `y² = x³ + ax + b` over Fp
/// `secp256r1` Also known as `prime256v1`, `NIST P-256` or just `P-256`
/// Used by `Neo` and `Cardano`
/// https://www.ietf.org/rfc/rfc5480.txt
public struct Secp256r1: EllipticCurve {

    /// `2^256 - 2^224 + 2^192 + 2^96 - 1` <=> `2^224 * (2^32 − 1) + 2^192 +2^96 − 1`
    public static let P = Number(hexString: "0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")!

    public static let a = Number(hexString: "0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")!
    public static let b = Number(hexString: "0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")!
    public static let G = Point(
        x: Number(hexString: "0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296")!,
        y: Number(hexString: "0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")!
    )

    public static let N = Number(hexString: "0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551")!
    public static let h = Number(1)
    public static let name = CurveName.secp256r1
}

The advantage of this is that it is easy for consumers to add custom curves!

Let's just add secp256k1:

/// The curve E: `y² = x³ + ax + b` over Fp
/// `secp256k1` Also known as the `Bitcoin curve` (though used by Ethereum, Zilliqa, Radix)
public struct Secp256k1: EllipticCurve {

    /// `2^256 −2^32 −2^9 −2^8 −2^7 −2^6 −2^4 − 1` <=> `2^256 - 2^32 - 977`
    public static let P = Number(hexString: "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F")!

    public static let a = Number(0)
    public static let b = Number(7)
    public static let G = Point(
        x: Number(hexString: "0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798")!,
        y: Number(hexString: "0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8")!
    )

    public static let N = Number(hexString: "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141")!
    public static let h = Number(1)
    public static let name = CurveName.secp256k1
}

Done! And Let's add tests:

let privateKey = PrivateKey<Secp256k1>(hex: "29EE955FEDA1A85F87ED4004958479706BA6C71FC99A67697A9A13D9D08C618E")!
let publicKey = PublicKey<Secp256k1>(privateKey: privateKey)
XCTAssertEqual(publicKey.hex.compressed, "F979F942AE743F27902B62CA4E8A8FE0F8A979EE3AD7BD0817339A665C3E7F4F")

The more I think of it I think using generics and protocols - like I've done in EllipticeCurveKit - makes it the most easy to add custom curves. swift-crypto could then contain the implementation of ECDSA, ECDH, EdDSA like it does to day, and define the curces it does today, but consumers of the library can add custom curves like secp256k1.

@paulmillr
Copy link

@Sajjon

  1. customers should not add "custom curves", because most of the time they don't know what is what curve-wise.
  2. adding a custom curve is not as simple as changing curve variables. For example, secp256k1 can utilize endomorphism because it's koblitz curve and faster equations because its a=0. curve25519 cannot be reused in this way because its equation is completely different Montgomery curve and requires different addition/multiplication formulas. BLS12-381 uses two elliptic curves and does pairings between them that produce 12-degree polynomials. How do you specify complex numbers with this typeclass? Etc

@Sajjon
Copy link
Contributor Author

Sajjon commented Jan 8, 2022

@paulmillr yeah those are more advanced examples. I've written a Swift library called EquationKit for multivariable differentiation just to support solving any Weierstraß form equation.

Pairing friendly curves used for BLS should probably not be added until we agree to add support for additional signature schemes. And adding Schnorr signing scheme should probably have higher priority since it is much simpler to support it. And if secp256k1 is added, Schnorr has a bigger user base thanks to Taproot than BLS applications at this time, I think.

So to conclude @paulmillr, ofc support any curve is hard. But at least any kublitz curve is easy to support.

@Lukasa
Copy link
Contributor

Lukasa commented Jan 11, 2022

In additional to @paulmillr's note, I'd like to add two more issues with "custom curve" type designs. The first is the more pragmatic and common of the issues, which is that custom curve implementations are usually slower than specialised curve implementations. Any design that allows custom curves wants to have some escape hatch for using specific implementations that don't rely on the general-purpose curve math, if only for performance reasons. In the case of Swift Crypto, all of its current curve implementations want to use specific, accelerated implementations.

The second reason to avoid custom curve implementations is that invariably someone tries to use them to support arbitrary curves with peer-supplied data, and it's pretty easy to miss the security implications of that until something like CVE-2020-0601 (Curveball) comes along. This is not an argument in favour of forbidding such a primitive: many primitives have sharp edges that may be misused. But it's definitely an argument in favour of thinking very hard about where that primitive lives, and I'm inclined to say that it probably shouldn't live in Swift Crypto.

@Sajjon
Copy link
Contributor Author

Sajjon commented Mar 16, 2023

The 2023 annual update by me, 15 months after my update on 2021-12-11:

Adoption

Daily active Ethereum Addresses remain unchanged in the past 15 months, despite over 50% value decrease
Screenshot 2023-03-16 at 21 16 13

Bitcoin active address remain unchanged in the past 15 months despite over 50% value secrease
Screenshot 2023-03-16 at 21 18 56

libsecp256k1 maturity

Since 2022-12-12 Bitcoin Cores libsecp256k1 does semantic versioning) (last tag 0.3.0 from last week).

Prominent Bitcoin Core developer Pieter Wuille says that "Going forward we plan to make tagged releases when improvements are merged"

Implementation

I've worked a lot with my Swift wrapper of libsecp256k1 called K1, It might be the most unit tested SECP256k1 lib out there. I've implemented every known test vectors to the interwebz, all Wycheproof vectors of course. And I've put a lot of work into generating more test vectors, using at least 3 different other repos as cross reference (e.g. extensive ECDH+KDF).

I have even made some API's compatible with CryptoKit, e.g. sharedSecretFromKeyAgreement:with which return a CryptoKit.SharedSecret (using unsafeBitCast:to), so that users of K1 can use x963 and hkdf directly on it, like with CryptoKit's Curves' ECDH.

Conclusion

Adoption is increasing, libsecp256k1 is mature to act as an underlying implementation thank to SemVer and I've proved with K1 that the fit with CryptoKit is good.

Can I ask you again @Lukasa to check with the rest of the Apple team to give this another thought? Thank you for reading! And thank you for all the amazing features in Swift that was delivered during 2022. I'm really looking forward to WWDC this summer 😍.

Sincerely
Alexander Cyon

@benjamin-wilson
Copy link

I would also like to point out that not only the broad use of libsecp256k1 continues to increase but it is now seen as a component of National Strategic Significance, an idea which is a best seller in Computers & Technology on Amazon. I think we have past secp256k1 enabling a sufficient set of use-cases into it being the most important elliptic curve of all.

@Lukasa
Copy link
Contributor

Lukasa commented Mar 23, 2023

@Sajjon Thanks so much for keeping this alive, we really appreciate it. I'll take these updates to the team and keep them posted. In the meantime, thankyou for developing and maintaining K1 in support of the Swift community!

@Sajjon
Copy link
Contributor Author

Sajjon commented Mar 24, 2023

@Sajjon Thanks so much for keeping this alive, we really appreciate it. I'll take these updates to the team and keep them posted.

@Lukasa oh btw, Wycheproof recently (4 weeks ago) updated (all?) test vectors in a new folder, testvectors_v1. I've created a PR updating some of the vectors. Wycheproofs new version now include vectors specifically for Bitcoin:

ecdsa_secp256k1_sha256_bitcoin_test.json. This vector was not present the the previous set of vectors from 4 years ago.

From the vectors header, quote:

"Test vectors of type EcdsaBitcoinVerify are meant for the verification of a ECDSA variant used for bitcoin, that add signature non-malleability."

That Google added this new vector also speaks to Bitcoins adoption.

And just this week we heard word about Microsoft's upcoming Crypto wallet inside its browser Edge, also speaking to adoption of secp256k1!

In the meantime, thankyou for developing and maintaining K1 in support of the Swift community!

Thank you, I just today merged a large rewrite changing the API of K1 to much better match CryptoKit/swift-crypto (using seperate key pairs for key agreement, Schnorr, ECDSA recoverable signatures and ECDSA non recoverable. Furthermore all APIs almost 1:1 maps to CryptoKit/swift-crypto 😊

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

6 participants