From 6f3902d09504838e4e486825f073df971c412595 Mon Sep 17 00:00:00 2001
From: Clawd <ai@clawd.bot>
Date: Thu, 19 Feb 2026 21:20:09 -0800
Subject: Add Schnorr signatures (BIP-340 compatible)

---
 schnorr.go      | 236 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 schnorr_test.go | 242 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 478 insertions(+)
 create mode 100644 schnorr.go
 create mode 100644 schnorr_test.go

diff --git a/schnorr.go b/schnorr.go
new file mode 100644
index 0000000..a9ff3b7
--- /dev/null
+++ b/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())
+}
diff --git a/schnorr_test.go b/schnorr_test.go
new file mode 100644
index 0000000..acd709c
--- /dev/null
+++ b/schnorr_test.go
@@ -0,0 +1,242 @@
+package secp256k1
+
+import (
+	"bytes"
+	"encoding/hex"
+	"math/big"
+	"testing"
+)
+
+func TestTaggedHash(t *testing.T) {
+	// Just verify it produces 32 bytes
+	result := TaggedHash("test", []byte("hello"))
+	if len(result) != 32 {
+		t.Errorf("expected 32 bytes, got %d", len(result))
+	}
+
+	// Same inputs should produce same output
+	result2 := TaggedHash("test", []byte("hello"))
+	if !bytes.Equal(result, result2) {
+		t.Error("tagged hash should be deterministic")
+	}
+
+	// Different tag should produce different output
+	result3 := TaggedHash("other", []byte("hello"))
+	if bytes.Equal(result, result3) {
+		t.Error("different tags should produce different hashes")
+	}
+}
+
+func TestLiftX(t *testing.T) {
+	// Lift G.x should give us G (or its negation with even y)
+	p, err := liftX(Gx)
+	if err != nil {
+		t.Fatalf("failed to lift G.x: %v", err)
+	}
+
+	if !p.IsOnCurve() {
+		t.Error("lifted point should be on curve")
+	}
+
+	// x should match
+	if p.x.value.Cmp(Gx) != 0 {
+		t.Error("lifted x should match input")
+	}
+
+	// y should be even (BIP-340 convention)
+	if !hasEvenY(p) {
+		t.Error("lifted point should have even y")
+	}
+}
+
+func TestLiftXInvalid(t *testing.T) {
+	// x = 0 is not on the curve (0³ + 7 = 7, and 7 has no sqrt mod p)
+	_, err := liftX(big.NewInt(0))
+	if err == nil {
+		t.Error("x=0 should not be on curve")
+	}
+}
+
+func TestSignAndVerify(t *testing.T) {
+	priv, _ := GeneratePrivateKey()
+	pub := priv.PublicKey()
+	message := []byte("hello world")
+
+	sig, err := Sign(priv, message)
+	if err != nil {
+		t.Fatalf("signing failed: %v", err)
+	}
+
+	if !Verify(pub, message, sig) {
+		t.Error("signature should verify")
+	}
+}
+
+func TestSignatureIsDeteministic(t *testing.T) {
+	priv, _ := NewPrivateKeyFromHex("0000000000000000000000000000000000000000000000000000000000000001")
+	message := []byte("test message")
+
+	sig1, _ := Sign(priv, message)
+	sig2, _ := Sign(priv, message)
+
+	if sig1.R.Cmp(sig2.R) != 0 || sig1.S.Cmp(sig2.S) != 0 {
+		t.Error("BIP-340 signing should be deterministic")
+	}
+}
+
+func TestVerifyWrongMessage(t *testing.T) {
+	priv, _ := GeneratePrivateKey()
+	pub := priv.PublicKey()
+
+	sig, _ := Sign(priv, []byte("correct message"))
+
+	if Verify(pub, []byte("wrong message"), sig) {
+		t.Error("signature should not verify with wrong message")
+	}
+}
+
+func TestVerifyWrongPublicKey(t *testing.T) {
+	priv1, _ := GeneratePrivateKey()
+	priv2, _ := GeneratePrivateKey()
+	pub2 := priv2.PublicKey()
+	message := []byte("test")
+
+	sig, _ := Sign(priv1, message)
+
+	if Verify(pub2, message, sig) {
+		t.Error("signature should not verify with wrong public key")
+	}
+}
+
+func TestVerifyTamperedSignature(t *testing.T) {
+	priv, _ := GeneratePrivateKey()
+	pub := priv.PublicKey()
+	message := []byte("test")
+
+	sig, _ := Sign(priv, message)
+
+	// Tamper with s
+	tamperedSig := &Signature{
+		R: sig.R,
+		S: new(big.Int).Add(sig.S, big.NewInt(1)),
+	}
+
+	if Verify(pub, message, tamperedSig) {
+		t.Error("tampered signature should not verify")
+	}
+}
+
+func TestSignatureBytes(t *testing.T) {
+	priv, _ := GeneratePrivateKey()
+	message := []byte("test")
+
+	sig, _ := Sign(priv, message)
+	b := sig.Bytes()
+
+	if len(b) != 64 {
+		t.Errorf("signature should be 64 bytes, got %d", len(b))
+	}
+}
+
+func TestSignatureRoundTrip(t *testing.T) {
+	priv, _ := GeneratePrivateKey()
+	message := []byte("test")
+
+	sig1, _ := Sign(priv, message)
+	b := sig1.Bytes()
+	sig2, err := SignatureFromBytes(b)
+	if err != nil {
+		t.Fatalf("failed to parse signature: %v", err)
+	}
+
+	if sig1.R.Cmp(sig2.R) != 0 || sig1.S.Cmp(sig2.S) != 0 {
+		t.Error("signature should survive round-trip")
+	}
+}
+
+func TestSignatureFromBytesInvalid(t *testing.T) {
+	_, err := SignatureFromBytes(make([]byte, 63))
+	if err == nil {
+		t.Error("should reject wrong-length input")
+	}
+}
+
+// BIP-340 Test Vector 0
+func TestBIP340Vector0(t *testing.T) {
+	privHex := "0000000000000000000000000000000000000000000000000000000000000003"
+	msgHex := "0000000000000000000000000000000000000000000000000000000000000000"
+	expectedSigHex := "e907831f80848d1069a5371b402410364bdf1c5f8307b0084c55f1ce2dca821525f66a4a85ea8b71e482a74f382d2ce5ebeee8fdb2172f477df4900d310536c0"
+
+	priv, err := NewPrivateKeyFromHex(privHex)
+	if err != nil {
+		t.Fatalf("failed to parse private key: %v", err)
+	}
+
+	msg, _ := hex.DecodeString(msgHex)
+
+	sig, err := Sign(priv, msg)
+	if err != nil {
+		t.Fatalf("signing failed: %v", err)
+	}
+
+	sigHex := sig.Hex()
+	if sigHex != expectedSigHex {
+		t.Errorf("signature mismatch\ngot:  %s\nwant: %s", sigHex, expectedSigHex)
+	}
+
+	// Also verify it
+	pub := priv.PublicKey()
+	if !Verify(pub, msg, sig) {
+		t.Error("BIP-340 test vector should verify")
+	}
+}
+
+// BIP-340 Test Vector 1
+func TestBIP340Vector1(t *testing.T) {
+	privHex := "b7e151628aed2a6abf7158809cf4f3c762e7160f38b4da56a784d9045190cfef"
+	msgHex := "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89"
+	auxHex := "0000000000000000000000000000000000000000000000000000000000000001"
+	expectedSigHex := "6896bd60eeae296db48a229ff71dfe071bde413e6d43f917dc8dcf8c78de33418906d11ac976abccb20b091292bff4ea897efcb639ea871cfa95f6de339e4b0a"
+
+	priv, err := NewPrivateKeyFromHex(privHex)
+	if err != nil {
+		t.Fatalf("failed to parse private key: %v", err)
+	}
+
+	msg, _ := hex.DecodeString(msgHex)
+	aux, _ := hex.DecodeString(auxHex)
+
+	sig, err := Sign(priv, msg, aux)
+	if err != nil {
+		t.Fatalf("signing failed: %v", err)
+	}
+
+	sigHex := sig.Hex()
+	if sigHex != expectedSigHex {
+		t.Errorf("signature mismatch\ngot:  %s\nwant: %s", sigHex, expectedSigHex)
+	}
+
+	pub := priv.PublicKey()
+	if !Verify(pub, msg, sig) {
+		t.Error("BIP-340 test vector should verify")
+	}
+}
+
+func TestXOnlyBytes(t *testing.T) {
+	priv, _ := NewPrivateKeyFromHex("0000000000000000000000000000000000000000000000000000000000000001")
+	pub := priv.PublicKey()
+
+	xOnly := pub.XOnlyBytes()
+	if len(xOnly) != 32 {
+		t.Errorf("x-only pubkey should be 32 bytes, got %d", len(xOnly))
+	}
+
+	// Should match G.x
+	expectedX := make([]byte, 32)
+	gxBytes := Gx.Bytes()
+	copy(expectedX[32-len(gxBytes):], gxBytes)
+
+	if !bytes.Equal(xOnly, expectedX) {
+		t.Error("x-only bytes should match G.x")
+	}
+}
-- 
cgit v1.2.3