Ekliptic
This package provides primitives for cryptographic operations on the secp256k1 curve, with zero dependencies and excellent performance. It provides both Affine and Jacobian interfaces for elliptic curve operations. Aims to facilitate performant low-level operations on secp256k1 without overengineering or kitchen-sink syndrome.
ALPHA STATE
This library is not finished, stable, or audited - depend on it at your own peril!
Examples
Deriving a public key from a private key:
privateKey, _ := new(big.Int).SetString("c370af8c091812ef7f6bfaffb494b1046fb25486c9873243b80826daef3ec583", 16)
x := new(big.Int)
y := new(big.Int)
ekliptic.MultiplyBasePoint(privateKey, x, y)
fmt.Println("Public key:")
fmt.Printf(" x: %x\n", x)
fmt.Printf(" y: %x\n", y)
// output:
// Public key:
// x: 76cd66c6cca75278ff408ce67290537367719154ae2b96448327fe4033ddcfc7
// y: 35663ecbb64397bb9bd79155a1e6b138c2fb8fa1f11355f8e9e97ddd88a78e49
Deriving a Diffie-Hellman shared-secret:
alice, _ := new(big.Int).SetString("94a22a406a6977c1a323f23b9d7678ad08e822834d1df8adece84e30f0c25b6b", 16)
bob, _ := new(big.Int).SetString("55ba19100104cbd2842999826e99e478efe6883ac3f3a0c7571034321e0595cf", 16)
var alicePub, bobPub struct{ x, y big.Int }
// derive public keys
MultiplyBasePoint(alice, &alicePub.x, &alicePub.y)
MultiplyBasePoint(bob, &bobPub.x, &bobPub.y)
var yValueIsUnused big.Int
// Alice gives Bob her public key, Bob derives the secret
bobSharedKey := new(big.Int)
MultiplyAffine(&alicePub.x, &alicePub.y, bob, bobSharedKey, &yValueIsUnused, nil)
// Bob gives Alice his public key, Alice derives the secret
aliceSharedKey := new(big.Int)
MultiplyAffine(&bobPub.x, &bobPub.y, alice, aliceSharedKey, &yValueIsUnused, nil)
fmt.Printf("Alice's derived secret: %x\n", aliceSharedKey)
fmt.Printf("Bob's derived secret: %x\n", bobSharedKey)
// output:
// Alice's derived secret: 375a5d26649704863562930ded2193a0569f90f4eb4e63f0fee72c4c05268feb
// Bob's derived secret: 375a5d26649704863562930ded2193a0569f90f4eb4e63f0fee72c4c05268feb
Hacking on Ekliptic
| Command | Usage |
|---|---|
go test |
Run unit tests. |
go test -bench=. |
Run benchmarks. |
go test -bench=. -benchmem |
Run benchmarks with memory profile. |
go generate |
Regenerate precomputed base point doubles. |
Performance Optimizations
Memory
All methods use and accept golang-native big.Int structs for math operations. In most cases we require the caller to pass pointers in which results will be stored.
x := new(big.Int).SetString("3e61e957cb7eb9252155722d37056b581cacd9949cd7daeba682d81ee829826d", 16)
y := new(big.Int).SetString("0c9b31d4b3f13c2dcec21b5d446a06cd655056d83495f63f05135ff4434e7ba5", 16)
z := new(big.Int).SetString("4c4619154810c1c0daa4ddd8c73971d159db91705f2113ce51b9885e4578874d", 16)
doubleX := new(big.Int)
doubleY := new(big.Int)
doubleZ := new(big.Int)
ekliptic.DoubleJacobi(
x3, y3, z3,
doubleX, doubleY, doubleZ,
)
While slightly more awkward to use, exposing this C-style API allows for better memory performance when doing large numbers of sequential operations. The garbage collector isn't doing as much work, because we don't have to keep re-allocating new big.Ints every time a call returns. We have some benchmarks for addition and doubling which demonstrate this method can save about 6 allocs/op, and a few hundred bytes of memory for every call involving Jacobian points.
You can even safely pass the input pointers as the output pointers, to modify them in place.
ekliptic.DoubleJacobi(
x3, y3, z3,
x3, y3, z3,
)
big.Int structs can be re-used when the values they hold are no longer required. This is why you'll see patterns like this if you read Ekliptic's code:
e := a.Mul(a, three)
a = nil
mod(e)
In the above example, a is no longer needed, so we reclaim its memory as a new variable to avoid allocating an entirely new big.Int struct for e.
Jacobian Points
This library offers support for both affine and Jacobian point math. Affine coordinates are 'normal' two-dimensional coordinates, x and y, which unambiguously describes a point on the plane. Jacobian coordinates are a three-dimensional representation of an affine point, (Ax, Ay), in terms of three variables: (x, y, z) such that:
Ax = x / z²
Ay = y / z³
This relationship means there are an absurdly large number of possible Jacobian coordinate triplets which describe the same affine point. Each affine coordinate is basically converted into a ratio of x:z and y:z, thus proportional ratios simplify to the same affine point.
Why would we want to represent points this way? Elliptic curve multiplication - a critical primitive for almost any elliptic-curve cryptography - involves performing many addition operations in a row. That's what multiplication means, after all. When you add two affine (x, y) points together in an elliptic curve, you have to perform some finite field division, AKA modular inversion, to get a result back in affine form. Modular inversion is a very expensive operation compared to multiplication. Instead of dividing after every addition operation, you can defer the division until the end of the multiplication sequence, by accumulating in the divisor coordinate z. After the multiplication operation is done, the point can be converted back to affine, or used for new EC operations, as needed.
To demonstrate, notice how expensive a naive affine multiplication is compared to a Jacobian multiplication:
BenchmarkMultiplyJacobi-4 600 ops 1926201 ns/op 639940 B/op 7261 allocs/op
BenchmarkMultiplyAffine-4 606 ops 1926115 ns/op 641480 B/op 7284 allocs/op
BenchmarkMultiplyAffineNaive-4 481 ops 2457812 ns/op 545873 B/op 9147 allocs/op
ekliptic.MultiplyJacobi and ekliptic.MultiplyAffine both use Jacobian math for multiplication operations under the hood. ekliptic.MultiplyAffineNaive is a naive implementation which uses affine addition and doubling instead of Jacobian math. It should be used for demonstrative purposes only.
Precomputation
You can improve multiplication performance even more by using precomputed doubles of the secp256k1 base-point. Precomputing G * 2^i for i in [0..256] significantly boosts performance for base-point double-and-add multiplication, especially if the precomputed doubles are saved in affine form. Values are computed using the ekliptic.ComputePointDoubles function, triggered by go generate.
Other Performance Notes
- We have a special implementation which checks for Jacobi point validity without costly affine conversion.
- Golang's
big.Inthas some operations which are more costly than others. For example, doingn.Exp(n, two, P)is more costly than doingn.Mul(n, n); mod(n). This holds for squaring and cubing, but exponents beyond 3 require.Expfor the best performance.
Thanks!
I wrote this library as a learning exercise. Thanks a ton to the following people and their amazing guides, with which I followed along and learned from.
Many test vectors in this package were either duplicated from, generated by, or derived from other Elliptic Curve Crypto implementations:
paulmillr/noble-secp256k1btcsuite/btcec(note: they use a different algorithm to add jacobians, but it works out to the same affine coordinates at the end. I modified a few of their test fixtures' jacobian ratios.)
Donations
If you're interested in supporting development of this package, show your love by dropping me some Bitcoins!
