secp256k1

package module
v0.0.0-...-f261603 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 25, 2023 License: BSD-3-Clause Imports: 11 Imported by: 2

README

secp256k1-voi - Yet another secp256k1 implementation

Yawning Angel (yawning at schwanenlied dot me)

Ponzi schemes exist in stable disequilibrium. This means that while they can’t ultimately succeed, they can persist indefinitely—until they don’t.

--Harry Markopolos

This is a correctness/simplicity-first implementation of the secp256k1 elliptic curve used by shitcoins, written as an elaborate cry for help.

The following techniques and tools are used for "correctness/simplicity":

Warning

This product can expose you to chemicals which are know to the State of California to cause cancer. For more information visit www.P65Warnings.ca.gov.

Features

  • Formally verified field and scalar arithmetic.
  • Constant time curve and scalar arithmetic operations unless explicitly noted otherwise.
  • Fast s * G routine using precomputed tables.
  • Fast variable-time u1 * G + u2 * P routine for signature verification.
  • Safe-by-default API, that makes it extremely hard to create invalid points and scalars.
  • Point s11n per SEC 1, Version 2.0, Section 2.3.3.
  • ECDH per SEC 1, Version 2.0, Section 3.3.1.
  • ECDSA per SEC 1, Version 2.0, Section 4.1.3/4.1.4 and BIP-0066.
  • ECDSA with RFC 6979 + SHA256 for compatibility.
  • ECDSA public key recovery per the various shitcoins.
  • Schnorr signatures per BIP-0340.
  • Hash to curve per RFC 9380.

Notes

  • No, this has not been audited. Unless you are willing to pay for it, do not ask about it. If you do not know how much that will cost, you can not afford it.
  • The API and some interals are heavily inspired by Filippo's edwards25519 and nistec packages.
  • Only the 64-bit implementations of the underlying field arithmetic are used, as 32-bit architectures are either increasingly irrelevant (x86, ARM) or fucking garbage (WASM). I may reconsider this when Golang gets build tags that make this easy (and no, keeping track of all the architectures is not "easy").
  • No attempt is made to sanitize memory. It is a lost cause in most languages, and totally, utterly hopeless in Go.
  • SIMD is used to accelerate the constant time table lookups. Building with purego disables the use of assembly. It is almost, but not quite, not even worth having variable-time variants of the multiplies on amd64 due to the vectorized table lookup.
  • The fiat-crypto ToBytes/FromBytes routines are not used due to our need to handle non-canonical encodings, and the fact that fiat expects and outputs little-endian, while big-endian is customary for this curve.
  • Worms in my brain, get them out.
Performance

While this does try to be reasonably performant, the primary goal is to be the most (obviously) correct Golang secp256k1, not the fastest Golang secp256k1.

In short (only relevant figures listed):

cpu: AMD Ryzen 7 5700G with Radeon Graphics
BenchmarkPoint/GLV/ScalarMult-16          	   18753	     64955 ns/op     176 B/op	       3 allocs/op
BenchmarkPoint/ScalarBaseMult-16          	   47127	     24230 ns/op       0 B/op	       0 allocs/op
BenchmarkPoint/DoubleScalarMultBasepointVartime-16         	   15546	     78549 ns/op	     176 B/op	       3 allocs/op
BenchmarkPoint/s11n/UncompressedBytes-16                   	  192446	      5517 ns/op	       0 B/op	       0 allocs/op
BenchmarkPoint/s11n/CompressedBytes-16                     	  219115	      5520 ns/op	       0 B/op	       0 allocs/op

"It's alright". Compared to dcrd/dcrec/secp256k1 (aka btcec), verification performance is basically the same, signing is slower, ECDH ranges from slightly faster (on x86-64) to slower (purego). On the other hand, this library is timing side-channel safe on reasonable architectures.

Potential improvements:

  • Sit and wait for Go 1.21 to come out, it seems to do better.
  • wNAF based point multiplication is probably a gain.
  • Go and add "multiply a field element by a small integer" to fiat.
  • Pippenger's multi-scalar multiply would be better in certain cases.

Documentation

Overview

Package secp256k1 implements the secp256k1 elliptic curve as specified in SEC 2, Version 2.0, Section 2.4.1.

Index

Constants

View Source 
const (
	// CompressedPointSize is the size of a compressed point in bytes,
	// in the SEC 1, Version 2.0, Section 2.3.3 encoding (`Y_EvenOrOdd | X`).
	CompressedPointSize = 33

	// UncompressedPointSize is the size of an uncompressed point in
	// bytes in the SEC 1, Version 2.0, Section 2.3.3 encoding
	// (`0x04 | X | Y`).
	UncompressedPointSize = 65

	// IdentityPointSize is the size of the point at infinity in bytes,
	// in the SEC 1, Version 2.0, Section 2.3.3 encoding (`0x00`).
	IdentityPointSize = 1

	// CoordSize is the size of a coordinate in bytes, in the SEC 1,
	// Version 2.0, Section 2.3.5 encoding.
	CoordSize = 32
)
View Source 
const ScalarSize = 32

ScalarSize is the size of a scalar in bytes.

Variables

This section is empty.

Functions

func SplitUncompressedPoint 

func SplitUncompressedPoint(ptBytes []byte) ([]byte, uint64)

SplitUncompressedPoint splits the SEC 1, Verson 2.0, Section 2.3.3 uncompressed encoding of a point into the 32-byte big-endian byte encoding of the x-coordinate, and a uint64 indicating if the y-coordinate is odd.

Types

type Point 

type Point struct {
	// contains filtered or unexported fields
}

Point represets a point on the secp256k1 curve. All arguments and receivers are allowed to alias. The zero value is NOT valid, and may only be used as a receiver.

Properly initialized Points will always either be on the curve, or the point at infinity, and all of the curve arithmetic routines handle the point at infinity correctly.

func NewGeneratorPoint 

func NewGeneratorPoint() *Point

NewGeneratorPoint returns a new Point set to the canonical generator.

func NewIdentityPoint 

func NewIdentityPoint() *Point

NewIdentityPoint returns a new Point set to the identity element (point at infinity).

func NewPointFrom 

func NewPointFrom(p *Point) *Point

NewPointFrom returns a new Point set to an existing Point.

func NewPointFromBytes 

func NewPointFromBytes(src []byte) (*Point, error)

NewPointFromBytes creates a new Point from either of the SEC 1 encodings (uncompressed or compressed).

func NewPointFromCoords 

func NewPointFromCoords(xBytes, yBytes *[CoordSize]byte) (*Point, error)

NewPointFromCoords creates a new Point from the big-endian encoded x and y coordinates.

func RecoverPoint 

func RecoverPoint(xScalar *Scalar, recoveryID byte) (*Point, error)

RecoverPoint reconstructs a point from the Scalar representation of the x-coordinate, and a "recovery ID" in the range `[0,3]`.

func (*Point) Add 

func (v *Point) Add(p, q *Point) *Point

Add sets `v = p + q`, and returns `v`.

func (*Point) CompressedBytes 

func (v *Point) CompressedBytes() []byte

CompressedBytes returns the SEC 1, Version 2.0, Section 2.3.3 compressed or infinity encoding of `v`.

func (*Point) ConditionalNegate 

func (v *Point) ConditionalNegate(p *Point, ctrl uint64) *Point

ConditionalNegate sets `v = p` iff `ctrl == 0`, `v = -p` otherwise, and returns `v`.

func (*Point) ConditionalSelect 

func (v *Point) ConditionalSelect(a, b *Point, ctrl uint64) *Point

ConditionalSelect sets `v = a` iff `ctrl == 0`, `v = b` otherwise, and returns `v`.

func (*Point) Double 

func (v *Point) Double(p *Point) *Point

Double sets `v = p + p`, and returns `v`. Calling `Add(p, p)` will also return correct results, however this method is faster.

func (*Point) DoubleScalarMultBasepointVartime 

func (v *Point) DoubleScalarMultBasepointVartime(u1, u2 *Scalar, p *Point) *Point

DoubleScalarMultBasepointVartime sets `v = u1 * G + u2 * P`, and returns `v` in variable time, where `G` is the generator.

func (*Point) Equal 

func (v *Point) Equal(p *Point) uint64

Equal returns 1 iff `v == p`, 0 otherwise.

func (*Point) Generator 

func (v *Point) Generator() *Point

Generator sets `v = G`, and returns `v`.

func (*Point) Identity 

func (v *Point) Identity() *Point

Identity sets `v = id`, and returns `v`.

func (*Point) IsIdentity 

func (v *Point) IsIdentity() uint64

IsIdentity returns 1 iff `v` is the identity point, 0 otherwise.

func (*Point) IsYOdd 

func (v *Point) IsYOdd() uint64

IsYOdd returns 1 iff `v.y` is odd, 0 otherwise.

func (*Point) MultiScalarMult 

func (v *Point) MultiScalarMult(scalars []*Scalar, points []*Point) *Point

MultiScalarMult sets `v = sum(scalars[i] * points[i])`, and returns `v`.

func (*Point) MultiScalarMultVartime 

func (v *Point) MultiScalarMultVartime(scalars []*Scalar, points []*Point) *Point

MultiScalarMultVartime sets `v = sum(scalars[i] * points[i])`, and returns `v` in variable time.

func (*Point) Negate 

func (v *Point) Negate(p *Point) *Point

Negate sets `v = -p`, and returns `v`.

func (*Point) ScalarBaseMult 

func (v *Point) ScalarBaseMult(s *Scalar) *Point

ScalarBaseMult sets `v = s * G`, and returns `v`, where `G` is the generator.

func (*Point) ScalarMult 

func (v *Point) ScalarMult(s *Scalar, p *Point) *Point

ScalarMult sets `v = s * p`, and returns `v`.

func (*Point) Set 

func (v *Point) Set(p *Point) *Point

Set sets `v = p`, and returns `v`.

func (*Point) SetBytes 

func (v *Point) SetBytes(src []byte) (*Point, error)

SetBytes sets `p = src`, where `src` is a valid SEC 1, Version 2.0, Section 2.3.3 encoding of a point. If `src` is not a valid encoding of `p`, SetBytes returns nil and an error, and the receiver is unchanged.

func (*Point) SetCompressedBytes 

func (v *Point) SetCompressedBytes(src []byte) (*Point, error)

SetCompressedBytes sets `p = src`, where `src` is a valid SEC 1, Verson 2.0, Section 2.3.3 compressed encoding of a point. If `src` is not a valid compressed encodiong of a point, SetCompressedBytes returns nil and an error, and the receiver is unchanged.

func (*Point) SetUncompressedBytes 

func (v *Point) SetUncompressedBytes(src []byte) (*Point, error)

SetUncompressedBytes sets `p = src`, where `src` is a valid SEC 1, Verson 2.0, Section 2.3.3 uncompressed encoding of a point. If `src` is not a valid uncompressed encodiong of a point, SetUncompressedBytes returns nil and an error, and the receiver is unchanged.

func (*Point) SetUniformBytes 

func (v *Point) SetUniformBytes(src []byte) *Point

SetUniformBytes sets `v = map_to_curve(OS2IP(src) mod p)`, where `src` MUST have a length in the range `[32,64]`-bytes, and returns `v`.

If called with exactly 48-bytes of data, this can be used to implement `encode_to_curve` and `hash_to_curve`, per "Hashing to Elliptic Curves". With a cryptographically insignificant probability, the result may be the point at infinity.

Most users SHOULD use a higher-level `encode_to_curve` or `hash_to_curve` implementation instead.

func (*Point) Subtract 

func (v *Point) Subtract(p, q *Point) *Point

Subtract sets `v = p - q`, and returns `v`.

func (*Point) UncompressedBytes 

func (v *Point) UncompressedBytes() []byte

UncompressedBytes returns the SEC 1, Version 2.0, Section 2.3.3 uncompressed or infinity encoding of `v`.

func (*Point) XBytes 

func (v *Point) XBytes() ([]byte, error)

XBytes returns the SEC 1, Version 2.0, Section 2.3.5 encoding of the x-coordinate, or an error if the point is the point at infinity.

type Scalar 

type Scalar struct {
	// contains filtered or unexported fields
}

Scalar is an integer modulo `n = 2^256 - 432420386565659656852420866394968145599`. All arguments and receivers are allowed to alias. The zero value is a valid zero element.

func NewScalar 

func NewScalar() *Scalar

NewScalar returns a new zero Scalar.

func NewScalarFrom 

func NewScalarFrom(other *Scalar) *Scalar

NewScalarFrom returns a new Scalar set to an existing Scalar.

func NewScalarFromBytes 

func NewScalarFromBytes(src *[ScalarSize]byte) (*Scalar, uint64)

NewScalarFromBytes creates a new Scalar from the 32-byte big-endian encoding of `s`, and returns `s, 0`. If `src` is not a canonical encoding of `s`, `src` is reduced modulo n, and NewScalarFromBytes returns `s, 1`.

func NewScalarFromCanonicalBytes 

func NewScalarFromCanonicalBytes(src *[ScalarSize]byte) (*Scalar, error)

NewScalarFromCanonicalBytes creates a new Scalar from the canonical 32-byte big-endian byte representation.

func NewScalarFromUint64 

func NewScalarFromUint64(l0 uint64) *Scalar

NewScalarFromUint64 creates a new Scalar from a uint64.

func (*Scalar) Add 

func (s *Scalar) Add(a, b *Scalar) *Scalar

Add sets `s = a + b` and returns `s`.

func (*Scalar) Bytes 

func (s *Scalar) Bytes() []byte

Bytes returns the canonical big-endian encoding of `s`.

func (*Scalar) ConditionalNegate 

func (s *Scalar) ConditionalNegate(a *Scalar, ctrl uint64) *Scalar

ConditionalNegate sets `s = a` iff `ctrl == 0`, `s = -a` otherwise, and returns `s`.

func (*Scalar) ConditionalSelect 

func (s *Scalar) ConditionalSelect(a, b *Scalar, ctrl uint64) *Scalar

ConditionalSelect sets `s = a` iff `ctrl == 0`, `s = b` otherwise, and returns `s`.

func (*Scalar) Equal 

func (s *Scalar) Equal(a *Scalar) uint64

Equal returns 1 iff `s == a`, 0 otherwise.

func (*Scalar) Invert 

func (z *Scalar) Invert(x *Scalar) *Scalar

Invert sets `z = 1/x` and returns `z`. If `x == 0`, `z` is set to `0`.

func (*Scalar) IsGreaterThanHalfN 

func (s *Scalar) IsGreaterThanHalfN() uint64

IsGreaterThanHalfN returns 1 iff `s > n / 2`, where `n` is the order of G, 0 otherwise.

func (*Scalar) IsZero 

func (s *Scalar) IsZero() uint64

IsZero returns 1 iff `s == 0`, 0 otherwise.

func (*Scalar) Multiply 

func (s *Scalar) Multiply(a, b *Scalar) *Scalar

Multiply sets `s = a * b` and returns `s`.

func (*Scalar) Negate 

func (s *Scalar) Negate(a *Scalar) *Scalar

Negate sets `s = -a` and returns `s`.

func (*Scalar) One 

func (s *Scalar) One() *Scalar

One sets `s = 1` and returns `s`.

func (*Scalar) Product 

func (s *Scalar) Product(vec ...*Scalar) *Scalar

Product sets `s = vec[0] * ... * vec[n]` and returns `s`. If `vec` is empty, `s` will be set to `1`.

func (*Scalar) Set 

func (s *Scalar) Set(a *Scalar) *Scalar

Set sets `s = a` and returns `s`.

func (*Scalar) SetBytes 

func (s *Scalar) SetBytes(src *[ScalarSize]byte) (*Scalar, uint64)

SetBytes sets `s = src`, where `src` is a 32-byte big-endian encoding of `s`, and returns `s, 0`. If `src` is not a canonical encoding of `s`, `src` is reduced modulo n, and SetBytes returns `s, 1`.

func (*Scalar) SetCanonicalBytes 

func (s *Scalar) SetCanonicalBytes(src *[ScalarSize]byte) (*Scalar, error)

SetCanonicalBytes sets `s = src`, where `src` is a 32-byte big-endian encoding of `s`, and returns `s`. If `src` is not a canonical encoding of `s`, SetCanonicalBytes returns nil and an error, and the receiver is unchanged.

func (*Scalar) Square 

func (s *Scalar) Square(a *Scalar) *Scalar

Square sets `s = a * a` and returns `s`.

func (*Scalar) Subtract 

func (s *Scalar) Subtract(a, b *Scalar) *Scalar

Subtract sets `s = a - b` and returns `s`.

func (*Scalar) Sum 

func (s *Scalar) Sum(vec ...*Scalar) *Scalar

Sum sets `s = vec[0] + ... + vec[n]` and returns `s`.

func (*Scalar) Zero 

func (s *Scalar) Zero() *Scalar

Zero sets `s = 0` and returns `s`.

Source Files

View all Source files

Directories

Path Synopsis
internal
disalloweq
Package disalloweq provides a method for disallowing struct comparisons with the `==` operator.
 Package disalloweq provides a method for disallowing struct comparisons with the `==` operator.
fiat/secp256k1montgomery
Code generated by Fiat Cryptography.
 Code generated by Fiat Cryptography.
fiat/secp256k1montgomeryscalar
Code generated by Fiat Cryptography.
 Code generated by Fiat Cryptography.
field
Package field implements arithmetic modulo p = 2^256 - 2^32 - 977.
 Package field implements arithmetic modulo p = 2^256 - 2^32 - 977.
helpers
swu
Package swu implements the Simplified Shallue-van de Woestijne-Ulas method.
 Package swu implements the Simplified Shallue-van de Woestijne-Ulas method.
asm Module
Package secec implements the common primitives on top of secp256k1, with an API that is close to the runtime library's `crypto/ecdsa` and `crypto/ecdh` packages.
 Package secec implements the common primitives on top of secp256k1, with an API that is close to the runtime library's `crypto/ecdsa` and `crypto/ecdh` packages.
bitcoin
Package bitcoin implements the bitcoin specific primitives.
 Package bitcoin implements the bitcoin specific primitives.
h2c
Package h2c implements Hashing to Elliptic Curves as specified in RFC 9380.
 Package h2c implements Hashing to Elliptic Curves as specified in RFC 9380.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.