Merge embed-secp256k1: zero-dependency implementation

4 files changed, 670 insertions, 0 deletions

diff --git a/internal/secp256k1/field.go b/internal/secp256k1/field.go
new file mode 100644
index 0000000..13cdffd
--- /dev/null
+++ b/internal/secp256k1/field.go
@@ -0,0 +1,92 @@
+package secp256k1
+
+import (
+        "fmt"
+        "math/big"
+)
+
+// The prime for secp256k1: 2^256 - 2^32 - 977
+// All field arithmetic happens mod this number
+var P, _ = new(big.Int).SetString(
+        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F",
+        16,
+)
+
+// FieldElement represents a number in our finite field (mod P)
+type FieldElement struct {
+        value *big.Int
+}
+
+// NewFieldElement creates a field element from a big.Int
+// It automatically reduces mod P
+func NewFieldElement(v *big.Int) *FieldElement {
+        result := new(big.Int).Mod(v, P)
+        return &FieldElement{value: result}
+}
+
+// NewFieldElementFromInt64 is a convenience for small numbers
+func NewFieldElementFromInt64(v int64) *FieldElement {
+        return NewFieldElement(big.NewInt(v))
+}
+
+// Add returns (a + b) mod P
+func (a *FieldElement) Add(b *FieldElement) *FieldElement {
+        result := new(big.Int).Add(a.value, b.value)
+        return NewFieldElement(result)
+}
+
+// Sub returns (a - b) mod P
+func (a *FieldElement) Sub(b *FieldElement) *FieldElement {
+        result := new(big.Int).Sub(a.value, b.value)
+        return NewFieldElement(result)
+}
+
+// Mul returns (a * b) mod P
+func (a *FieldElement) Mul(b *FieldElement) *FieldElement {
+        result := new(big.Int).Mul(a.value, b.value)
+        return NewFieldElement(result)
+}
+
+// Div returns (a / b) mod P
+// Division in a field = multiply by the inverse
+func (a *FieldElement) Div(b *FieldElement) *FieldElement {
+        // a / b = a * b^(-1)
+        // b^(-1) mod P = b^(P-2) mod P  (Fermat's little theorem)
+        inverse := b.Inverse()
+        return a.Mul(inverse)
+}
+
+// Inverse returns a^(-1) mod P using Fermat's little theorem
+// a^(-1) = a^(P-2) mod P
+func (a *FieldElement) Inverse() *FieldElement {
+        // P - 2
+        exp := new(big.Int).Sub(P, big.NewInt(2))
+        // a^(P-2) mod P
+        result := new(big.Int).Exp(a.value, exp, P)
+        return &FieldElement{value: result}
+}
+
+// Square returns a² mod P (convenience method)
+func (a *FieldElement) Square() *FieldElement {
+        return a.Mul(a)
+}
+
+// Equal checks if two field elements are the same
+func (a *FieldElement) Equal(b *FieldElement) bool {
+        return a.value.Cmp(b.value) == 0
+}
+
+// IsZero checks if the element is zero
+func (a *FieldElement) IsZero() bool {
+        return a.value.Sign() == 0
+}
+
+// String returns hex representation
+func (a *FieldElement) String() string {
+        return fmt.Sprintf("%064x", a.value)
+}
+
+// Clone returns a copy
+func (a *FieldElement) Clone() *FieldElement {
+        return &FieldElement{value: new(big.Int).Set(a.value)}
+}
diff --git a/internal/secp256k1/keys.go b/internal/secp256k1/keys.go
new file mode 100644
index 0000000..fde5d26
--- /dev/null
+++ b/internal/secp256k1/keys.go
@@ -0,0 +1,171 @@
+package secp256k1
+
+import (
+        "crypto/rand"
+        "fmt"
+        "math/big"
+)
+
+// PrivateKey is a scalar (1 to N-1) used for signing
+type PrivateKey struct {
+        D *big.Int // the secret scalar
+}
+
+// PublicKey is a point on the curve (D * G)
+type PublicKey struct {
+        Point *Point
+}
+
+// GeneratePrivateKey creates a random private key
+func GeneratePrivateKey() (*PrivateKey, error) {
+        // Generate random bytes
+        bytes := make([]byte, 32)
+        _, err := rand.Read(bytes)
+        if err != nil {
+                return nil, fmt.Errorf("failed to generate random bytes: %w", err)
+        }
+
+        // Convert to big.Int and reduce mod N
+        d := new(big.Int).SetBytes(bytes)
+        d.Mod(d, N)
+
+        // Ensure it's not zero (extremely unlikely but must check)
+        if d.Sign() == 0 {
+                d.SetInt64(1)
+        }
+
+        return &PrivateKey{D: d}, nil
+}
+
+// NewPrivateKeyFromBytes creates a private key from 32 bytes
+func NewPrivateKeyFromBytes(b []byte) (*PrivateKey, error) {
+        if len(b) != 32 {
+                return nil, fmt.Errorf("private key must be 32 bytes, got %d", len(b))
+        }
+
+        d := new(big.Int).SetBytes(b)
+
+        // Validate: must be in range [1, N-1]
+        if d.Sign() == 0 {
+                return nil, fmt.Errorf("private key cannot be zero")
+        }
+        if d.Cmp(N) >= 0 {
+                return nil, fmt.Errorf("private key must be less than curve order N")
+        }
+
+        return &PrivateKey{D: d}, nil
+}
+
+// NewPrivateKeyFromHex creates a private key from a hex string
+func NewPrivateKeyFromHex(hex string) (*PrivateKey, error) {
+        d, ok := new(big.Int).SetString(hex, 16)
+        if !ok {
+                return nil, fmt.Errorf("invalid hex string")
+        }
+
+        // Validate range
+        if d.Sign() == 0 {
+                return nil, fmt.Errorf("private key cannot be zero")
+        }
+        if d.Cmp(N) >= 0 {
+                return nil, fmt.Errorf("private key must be less than curve order N")
+        }
+
+        return &PrivateKey{D: d}, nil
+}
+
+// PublicKey derives the public key from the private key
+// PublicKey = D * G
+func (priv *PrivateKey) PublicKey() *PublicKey {
+        point := G.ScalarMul(priv.D)
+        return &PublicKey{Point: point}
+}
+
+// Bytes returns the private key as 32 bytes (big-endian, zero-padded)
+func (priv *PrivateKey) Bytes() []byte {
+        b := priv.D.Bytes()
+        // Pad to 32 bytes
+        if len(b) < 32 {
+                padded := make([]byte, 32)
+                copy(padded[32-len(b):], b)
+                return padded
+        }
+        return b
+}
+
+// Hex returns the private key as a 64-character hex string
+func (priv *PrivateKey) Hex() string {
+        return fmt.Sprintf("%064x", priv.D)
+}
+
+// Bytes returns the public key in uncompressed format (65 bytes: 0x04 || x || y)
+func (pub *PublicKey) Bytes() []byte {
+        if pub.Point.IsInfinity() {
+                return []byte{0x00} // shouldn't happen with valid keys
+        }
+
+        result := make([]byte, 65)
+        result[0] = 0x04 // uncompressed prefix
+
+        xBytes := pub.Point.x.value.Bytes()
+        yBytes := pub.Point.y.value.Bytes()
+
+        // Copy x (padded to 32 bytes)
+        copy(result[1+(32-len(xBytes)):33], xBytes)
+        // Copy y (padded to 32 bytes)
+        copy(result[33+(32-len(yBytes)):65], yBytes)
+
+        return result
+}
+
+// BytesCompressed returns the public key in compressed format (33 bytes: prefix || x)
+// Prefix is 0x02 if y is even, 0x03 if y is odd
+func (pub *PublicKey) BytesCompressed() []byte {
+        if pub.Point.IsInfinity() {
+                return []byte{0x00}
+        }
+
+        result := make([]byte, 33)
+
+        // Prefix based on y parity
+        if pub.Point.y.value.Bit(0) == 0 {
+                result[0] = 0x02 // y is even
+        } else {
+                result[0] = 0x03 // y is odd
+        }
+
+        xBytes := pub.Point.x.value.Bytes()
+        copy(result[1+(32-len(xBytes)):33], xBytes)
+
+        return result
+}
+
+// Hex returns the public key as uncompressed hex (130 characters)
+func (pub *PublicKey) Hex() string {
+        return fmt.Sprintf("%x", pub.Bytes())
+}
+
+// HexCompressed returns the public key as compressed hex (66 characters)
+func (pub *PublicKey) HexCompressed() string {
+        return fmt.Sprintf("%x", pub.BytesCompressed())
+}
+
+// Equal checks if two public keys are the same
+func (pub *PublicKey) Equal(other *PublicKey) bool {
+        return pub.Point.Equal(other.Point)
+}
+
+// ParsePublicKeyXOnly parses a 32-byte x-only public key (BIP-340 format)
+func ParsePublicKeyXOnly(xOnlyBytes []byte) (*PublicKey, error) {
+        if len(xOnlyBytes) != 32 {
+                return nil, fmt.Errorf("x-only public key must be 32 bytes, got %d", len(xOnlyBytes))
+        }
+
+        x := new(big.Int).SetBytes(xOnlyBytes)
+        point, err := LiftX(x)
+        if err != nil {
+                return nil, fmt.Errorf("invalid x-only public key: %w", err)
+        }
+
+        return &PublicKey{Point: point}, nil
+}
diff --git a/internal/secp256k1/point.go b/internal/secp256k1/point.go
new file mode 100644
index 0000000..1def176
--- /dev/null
+++ b/internal/secp256k1/point.go
@@ -0,0 +1,171 @@
+package secp256k1
+
+import (
+        "fmt"
+        "math/big"
+)
+
+// secp256k1 curve: y² = x³ + 7
+// The 'a' coefficient is 0, 'b' is 7
+var curveB = NewFieldElementFromInt64(7)
+
+// Generator point G for secp256k1
+var (
+        Gx, _ = new(big.Int).SetString("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16)
+        Gy, _ = new(big.Int).SetString("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", 16)
+        G     = &Point{
+                x:        NewFieldElement(Gx),
+                y:        NewFieldElement(Gy),
+                infinity: false,
+        }
+)
+
+// Curve order (number of points on the curve)
+var N, _ = new(big.Int).SetString("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16)
+
+// Point represents a point on the secp256k1 curve
+type Point struct {
+        x, y     *FieldElement
+        infinity bool // true if this is the point at infinity (identity)
+}
+
+// NewPoint creates a point from x, y coordinates
+// Returns error if the point is not on the curve
+func NewPoint(x, y *FieldElement) (*Point, error) {
+        p := &Point{x: x, y: y, infinity: false}
+        if !p.IsOnCurve() {
+                return nil, fmt.Errorf("point (%s, %s) is not on the curve", x.String(), y.String())
+        }
+        return p, nil
+}
+
+// Infinity returns the point at infinity (identity element)
+func Infinity() *Point {
+        return &Point{infinity: true}
+}
+
+// IsInfinity returns true if this is the point at infinity
+func (p *Point) IsInfinity() bool {
+        return p.infinity
+}
+
+// IsOnCurve checks if the point satisfies y² = x³ + 7
+func (p *Point) IsOnCurve() bool {
+        if p.infinity {
+                return true
+        }
+        // y² = x³ + 7
+        left := p.y.Square()                      // y²
+        right := p.x.Square().Mul(p.x).Add(curveB) // x³ + 7
+        return left.Equal(right)
+}
+
+// Equal checks if two points are the same
+func (p *Point) Equal(q *Point) bool {
+        if p.infinity && q.infinity {
+                return true
+        }
+        if p.infinity || q.infinity {
+                return false
+        }
+        return p.x.Equal(q.x) && p.y.Equal(q.y)
+}
+
+// Add returns p + q using the elliptic curve addition formulas
+func (p *Point) Add(q *Point) *Point {
+        // Handle infinity (identity element)
+        if p.infinity {
+                return q
+        }
+        if q.infinity {
+                return p
+        }
+
+        // If points are inverses (same x, opposite y), return infinity
+        if p.x.Equal(q.x) && !p.y.Equal(q.y) {
+                return Infinity()
+        }
+
+        // If points are the same, use doubling formula
+        if p.Equal(q) {
+                return p.Double()
+        }
+
+        // Standard addition formula for P ≠ Q:
+        // slope = (y2 - y1) / (x2 - x1)
+        // x3 = slope² - x1 - x2
+        // y3 = slope * (x1 - x3) - y1
+
+        slope := q.y.Sub(p.y).Div(q.x.Sub(p.x))
+        x3 := slope.Square().Sub(p.x).Sub(q.x)
+        y3 := slope.Mul(p.x.Sub(x3)).Sub(p.y)
+
+        return &Point{x: x3, y: y3, infinity: false}
+}
+
+// Double returns 2P (point added to itself)
+func (p *Point) Double() *Point {
+        if p.infinity {
+                return Infinity()
+        }
+
+        // If y = 0, tangent is vertical, return infinity
+        if p.y.IsZero() {
+                return Infinity()
+        }
+
+        // Doubling formula:
+        // slope = (3x² + a) / (2y)  -- for secp256k1, a = 0
+        // x3 = slope² - 2x
+        // y3 = slope * (x - x3) - y
+
+        three := NewFieldElementFromInt64(3)
+        two := NewFieldElementFromInt64(2)
+
+        slope := three.Mul(p.x.Square()).Div(two.Mul(p.y))
+        x3 := slope.Square().Sub(two.Mul(p.x))
+        y3 := slope.Mul(p.x.Sub(x3)).Sub(p.y)
+
+        return &Point{x: x3, y: y3, infinity: false}
+}
+
+// ScalarMul returns k * P (point multiplied by scalar)
+// Uses double-and-add algorithm
+func (p *Point) ScalarMul(k *big.Int) *Point {
+        result := Infinity()
+        addend := p
+
+        // Clone k so we don't modify the original
+        scalar := new(big.Int).Set(k)
+
+        for scalar.Sign() > 0 {
+                // If lowest bit is 1, add current addend
+                if scalar.Bit(0) == 1 {
+                        result = result.Add(addend)
+                }
+                // Double the addend
+                addend = addend.Double()
+                // Shift scalar right by 1
+                scalar.Rsh(scalar, 1)
+        }
+
+        return result
+}
+
+// Negate returns -P (same x, negated y)
+func (p *Point) Negate() *Point {
+        if p.infinity {
+                return Infinity()
+        }
+        // -y mod P
+        negY := NewFieldElement(new(big.Int).Sub(P, p.y.value))
+        return &Point{x: p.x.Clone(), y: negY, infinity: false}
+}
+
+// String returns a readable representation
+func (p *Point) String() string {
+        if p.infinity {
+                return "Point(infinity)"
+        }
+        return fmt.Sprintf("Point(%s, %s)", p.x.String()[:8]+"...", p.y.String()[:8]+"...")
+}
diff --git a/internal/secp256k1/schnorr.go b/internal/secp256k1/schnorr.go
new file mode 100644
index 0000000..ae7fa75
--- /dev/null
+++ b/internal/secp256k1/schnorr.go
@@ -0,0 +1,236 @@
+package secp256k1
+
+import (
+        "crypto/sha256"
+        "fmt"
+        "math/big"
+)
+
+// Signature represents a Schnorr signature (r, s)
+// r is the x-coordinate of R (32 bytes)
+// s is the scalar response (32 bytes)
+type Signature struct {
+        R *big.Int // x-coordinate of the nonce point
+        S *big.Int // the response scalar
+}
+
+// TaggedHash computes SHA256(SHA256(tag) || SHA256(tag) || msg)
+// This is BIP-340's domain separation technique
+func TaggedHash(tag string, data ...[]byte) []byte {
+        tagHash := sha256.Sum256([]byte(tag))
+        h := sha256.New()
+        h.Write(tagHash[:])
+        h.Write(tagHash[:])
+        for _, d := range data {
+                h.Write(d)
+        }
+        return h.Sum(nil)
+}
+
+// LiftX recovers a point from just its x-coordinate
+// Returns the point with even y (BIP-340 convention)
+func LiftX(x *big.Int) (*Point, error) {
+        // Check x is in valid range
+        if x.Sign() < 0 || x.Cmp(P) >= 0 {
+                return nil, fmt.Errorf("x out of range")
+        }
+
+        // Compute y² = x³ + 7
+        xFe := NewFieldElement(x)
+        ySquared := xFe.Square().Mul(xFe).Add(curveB)
+
+        // Compute y = sqrt(y²) mod p
+        // For secp256k1, sqrt(a) = a^((p+1)/4) mod p
+        exp := new(big.Int).Add(P, big.NewInt(1))
+        exp.Div(exp, big.NewInt(4))
+        y := new(big.Int).Exp(ySquared.value, exp, P)
+
+        // Verify it's actually a square root
+        ySquaredCheck := new(big.Int).Mul(y, y)
+        ySquaredCheck.Mod(ySquaredCheck, P)
+        if ySquaredCheck.Cmp(ySquared.value) != 0 {
+                return nil, fmt.Errorf("x is not on the curve")
+        }
+
+        // BIP-340: use the even y
+        if y.Bit(0) == 1 {
+                y.Sub(P, y)
+        }
+
+        return &Point{
+                x:        NewFieldElement(x),
+                y:        NewFieldElement(y),
+                infinity: false,
+        }, nil
+}
+
+// hasEvenY returns true if the point's y-coordinate is even
+func hasEvenY(p *Point) bool {
+        if p.infinity {
+                return false
+        }
+        return p.y.value.Bit(0) == 0
+}
+
+// xOnlyBytes returns the 32-byte x-coordinate of a public key
+func (pub *PublicKey) XOnlyBytes() []byte {
+        result := make([]byte, 32)
+        xBytes := pub.Point.x.value.Bytes()
+        copy(result[32-len(xBytes):], xBytes)
+        return result
+}
+
+// Sign creates a Schnorr signature for a message
+// Follows BIP-340 specification
+// aux is optional auxiliary randomness (32 bytes); nil uses zeros
+func Sign(priv *PrivateKey, message []byte, aux ...[]byte) (*Signature, error) {
+        // Get the public key point
+        P := G.ScalarMul(priv.D)
+
+        // BIP-340: if P.y is odd, negate the private key
+        d := new(big.Int).Set(priv.D)
+        if !hasEvenY(P) {
+                d.Sub(N, d)
+                P = P.Negate()
+        }
+
+        // Serialize public key x-coordinate (32 bytes)
+        pBytes := make([]byte, 32)
+        pxBytes := P.x.value.Bytes()
+        copy(pBytes[32-len(pxBytes):], pxBytes)
+
+        // BIP-340 nonce generation:
+        // t = d XOR tagged_hash("BIP0340/aux", aux)
+        // k = tagged_hash("BIP0340/nonce", t || P || m)
+        // For deterministic signing, use aux = 32 zero bytes
+        dBytes := make([]byte, 32)
+        dBytesRaw := d.Bytes()
+        copy(dBytes[32-len(dBytesRaw):], dBytesRaw)
+
+        // Use provided aux or default to 32 zero bytes
+        var auxBytes []byte
+        if len(aux) > 0 && len(aux[0]) == 32 {
+                auxBytes = aux[0]
+        } else {
+                auxBytes = make([]byte, 32)
+        }
+        auxHash := TaggedHash("BIP0340/aux", auxBytes)
+
+        t := make([]byte, 32)
+        for i := 0; i < 32; i++ {
+                t[i] = dBytes[i] ^ auxHash[i]
+        }
+
+        kHash := TaggedHash("BIP0340/nonce", t, pBytes, message)
+        k := new(big.Int).SetBytes(kHash)
+        k.Mod(k, N)
+
+        // k cannot be zero (extremely unlikely)
+        if k.Sign() == 0 {
+                return nil, fmt.Errorf("nonce is zero")
+        }
+
+        // R = k * G
+        R := G.ScalarMul(k)
+
+        // BIP-340: if R.y is odd, negate k
+        if !hasEvenY(R) {
+                k.Sub(N, k)
+                R = R.Negate()
+        }
+
+        // Serialize R.x (32 bytes)
+        rBytes := make([]byte, 32)
+        rxBytes := R.x.value.Bytes()
+        copy(rBytes[32-len(rxBytes):], rxBytes)
+
+        // Compute challenge e = hash(R.x || P.x || m)
+        eHash := TaggedHash("BIP0340/challenge", rBytes, pBytes, message)
+        e := new(big.Int).SetBytes(eHash)
+        e.Mod(e, N)
+
+        // Compute s = k + e * d (mod N)
+        s := new(big.Int).Mul(e, d)
+        s.Add(s, k)
+        s.Mod(s, N)
+
+        return &Signature{
+                R: R.x.value,
+                S: s,
+        }, nil
+}
+
+// Verify checks if a Schnorr signature is valid
+// Follows BIP-340 specification
+func Verify(pub *PublicKey, message []byte, sig *Signature) bool {
+        // Check signature values are in range
+        if sig.R.Sign() < 0 || sig.R.Cmp(P) >= 0 {
+                return false
+        }
+        if sig.S.Sign() < 0 || sig.S.Cmp(N) >= 0 {
+                return false
+        }
+
+        // Lift R from x-coordinate
+        R, err := LiftX(sig.R)
+        if err != nil {
+                return false
+        }
+
+        // Get public key with even y
+        P := pub.Point
+        if !hasEvenY(P) {
+                P = P.Negate()
+        }
+
+        // Serialize for hashing
+        rBytes := make([]byte, 32)
+        rxBytes := sig.R.Bytes()
+        copy(rBytes[32-len(rxBytes):], rxBytes)
+
+        pBytes := make([]byte, 32)
+        pxBytes := P.x.value.Bytes()
+        copy(pBytes[32-len(pxBytes):], pxBytes)
+
+        // Compute challenge e = hash(R.x || P.x || m)
+        eHash := TaggedHash("BIP0340/challenge", rBytes, pBytes, message)
+        e := new(big.Int).SetBytes(eHash)
+        e.Mod(e, N)
+
+        // Verify: s*G == R + e*P
+        sG := G.ScalarMul(sig.S)
+        eP := P.ScalarMul(e)
+        expected := R.Add(eP)
+
+        return sG.Equal(expected)
+}
+
+// Bytes returns the signature as 64 bytes (r || s)
+func (sig *Signature) Bytes() []byte {
+        result := make([]byte, 64)
+
+        rBytes := sig.R.Bytes()
+        sBytes := sig.S.Bytes()
+
+        copy(result[32-len(rBytes):32], rBytes)
+        copy(result[64-len(sBytes):64], sBytes)
+
+        return result
+}
+
+// SignatureFromBytes parses a 64-byte signature
+func SignatureFromBytes(b []byte) (*Signature, error) {
+        if len(b) != 64 {
+                return nil, fmt.Errorf("signature must be 64 bytes")
+        }
+
+        r := new(big.Int).SetBytes(b[:32])
+        s := new(big.Int).SetBytes(b[32:])
+
+        return &Signature{R: r, S: s}, nil
+}
+
+// Hex returns the signature as a 128-character hex string
+func (sig *Signature) Hex() string {
+        return fmt.Sprintf("%x", sig.Bytes())
+}