2 files changed, 478 insertions, 0 deletions

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")
+        }
+}