3 files changed, 471 insertions, 0 deletions

diff --git a/compat_test.go b/compat_test.go
new file mode 100644
index 0000000..b5cbde7
--- /dev/null
+++ b/compat_test.go
@@ -0,0 +1,453 @@
+package secp256k1
+
+import (
+        "bytes"
+        "crypto/sha256"
+        "encoding/hex"
+        "math/big"
+        "testing"
+
+        "github.com/btcsuite/btcd/btcec/v2"
+        "github.com/btcsuite/btcd/btcec/v2/schnorr"
+)
+
+// TestKeyDerivationCompatibility verifies that our key derivation
+// produces the same public key as btcec for the same private key
+func TestKeyDerivationCompatibility(t *testing.T) {
+        testCases := []string{
+                "0000000000000000000000000000000000000000000000000000000000000001",
+                "0000000000000000000000000000000000000000000000000000000000000002",
+                "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140", // N-1
+                "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798", // random
+                "b7e151628aed2a6abf7158809cf4f3c762e7160f38b4da56a784d9045190cfef", // from BIP-340
+        }
+
+        for _, tc := range testCases {
+                t.Run(tc[:8]+"...", func(t *testing.T) {
+                        privBytes, err := hex.DecodeString(tc)
+                        if err != nil {
+                                t.Fatalf("invalid hex: %v", err)
+                        }
+
+                        // Our implementation
+                        ourPriv, err := NewPrivateKeyFromBytes(privBytes)
+                        if err != nil {
+                                t.Fatalf("our NewPrivateKeyFromBytes failed: %v", err)
+                        }
+                        ourPub := ourPriv.PublicKey()
+
+                        // btcec implementation
+                        btcPriv, btcPub := btcec.PrivKeyFromBytes(privBytes)
+                        _ = btcPriv
+
+                        // Compare uncompressed public keys
+                        ourPubBytes := ourPub.Bytes()
+                        btcPubBytes := btcPub.SerializeUncompressed()
+
+                        if !bytes.Equal(ourPubBytes, btcPubBytes) {
+                                t.Errorf("uncompressed public key mismatch\nours: %x\nbtcec: %x",
+                                        ourPubBytes, btcPubBytes)
+                        }
+
+                        // Compare compressed public keys
+                        ourPubCompressed := ourPub.BytesCompressed()
+                        btcPubCompressed := btcPub.SerializeCompressed()
+
+                        if !bytes.Equal(ourPubCompressed, btcPubCompressed) {
+                                t.Errorf("compressed public key mismatch\nours: %x\nbtcec: %x",
+                                        ourPubCompressed, btcPubCompressed)
+                        }
+
+                        // Compare x-only public keys (BIP-340)
+                        ourXOnly := ourPub.XOnlyBytes()
+                        btcXOnly := schnorr.SerializePubKey(btcPub)
+
+                        if !bytes.Equal(ourXOnly, btcXOnly) {
+                                t.Errorf("x-only public key mismatch\nours: %x\nbtcec: %x",
+                                        ourXOnly, btcXOnly)
+                        }
+                })
+        }
+}
+
+// TestOurSignatureVerifiesWithBtcec tests that signatures we create
+// can be verified by btcec
+func TestOurSignatureVerifiesWithBtcec(t *testing.T) {
+        messages := [][]byte{
+                []byte("Hello, Bitcoin!"),
+                []byte(""),
+                []byte("The quick brown fox jumps over the lazy dog"),
+                make([]byte, 32), // 32 zeros
+        }
+
+        for i, msg := range messages {
+                t.Run(string(rune('A'+i)), func(t *testing.T) {
+                        // Generate a key pair with our implementation
+                        ourPriv, err := GeneratePrivateKey()
+                        if err != nil {
+                                t.Fatalf("key generation failed: %v", err)
+                        }
+                        ourPub := ourPriv.PublicKey()
+
+                        // Hash the message (BIP-340 signs 32-byte messages)
+                        msgHash := sha256.Sum256(msg)
+
+                        // Sign with our implementation
+                        ourSig, err := Sign(ourPriv, msgHash[:])
+                        if err != nil {
+                                t.Fatalf("our Sign failed: %v", err)
+                        }
+
+                        // Parse the signature with btcec
+                        btcSig, err := schnorr.ParseSignature(ourSig.Bytes())
+                        if err != nil {
+                                t.Fatalf("btcec couldn't parse our signature: %v", err)
+                        }
+
+                        // Parse our public key with btcec
+                        btcPub, err := schnorr.ParsePubKey(ourPub.XOnlyBytes())
+                        if err != nil {
+                                t.Fatalf("btcec couldn't parse our pubkey: %v", err)
+                        }
+
+                        // Verify with btcec
+                        if !btcSig.Verify(msgHash[:], btcPub) {
+                                t.Error("btcec failed to verify our signature")
+                        }
+                })
+        }
+}
+
+// TestBtcecSignatureVerifiesWithOurs tests that signatures created by btcec
+// can be verified by our implementation
+func TestBtcecSignatureVerifiesWithOurs(t *testing.T) {
+        messages := [][]byte{
+                []byte("Hello, Bitcoin!"),
+                []byte(""),
+                []byte("The quick brown fox jumps over the lazy dog"),
+                make([]byte, 32), // 32 zeros
+        }
+
+        for i, msg := range messages {
+                t.Run(string(rune('A'+i)), func(t *testing.T) {
+                        // Generate a key pair with btcec
+                        btcPriv, err := btcec.NewPrivateKey()
+                        if err != nil {
+                                t.Fatalf("btcec key generation failed: %v", err)
+                        }
+                        _ = btcPriv.PubKey() // ensure it's valid
+
+                        // Hash the message
+                        msgHash := sha256.Sum256(msg)
+
+                        // Sign with btcec
+                        btcSig, err := schnorr.Sign(btcPriv, msgHash[:])
+                        if err != nil {
+                                t.Fatalf("btcec Sign failed: %v", err)
+                        }
+
+                        // Parse the private key with our implementation
+                        ourPriv, err := NewPrivateKeyFromBytes(btcPriv.Serialize())
+                        if err != nil {
+                                t.Fatalf("our NewPrivateKeyFromBytes failed: %v", err)
+                        }
+                        ourPub := ourPriv.PublicKey()
+
+                        // Parse the signature with our implementation
+                        ourSig, err := SignatureFromBytes(btcSig.Serialize())
+                        if err != nil {
+                                t.Fatalf("our SignatureFromBytes failed: %v", err)
+                        }
+
+                        // Verify with our implementation
+                        if !Verify(ourPub, msgHash[:], ourSig) {
+                                t.Error("our implementation failed to verify btcec signature")
+                        }
+                })
+        }
+}
+
+// TestCrossSignAndVerify tests sign with one, verify with the other,
+// for the same key pair
+func TestCrossSignAndVerify(t *testing.T) {
+        // Generate key with our implementation
+        ourPriv, err := GeneratePrivateKey()
+        if err != nil {
+                t.Fatalf("key generation failed: %v", err)
+        }
+        ourPub := ourPriv.PublicKey()
+
+        // Get the same key in btcec
+        btcPriv, btcPub := btcec.PrivKeyFromBytes(ourPriv.Bytes())
+
+        msg := sha256.Sum256([]byte("cross-implementation test"))
+
+        // Test 1: Sign with ours, verify with both
+        ourSig, err := Sign(ourPriv, msg[:])
+        if err != nil {
+                t.Fatalf("our Sign failed: %v", err)
+        }
+
+        if !Verify(ourPub, msg[:], ourSig) {
+                t.Error("our signature failed our verification")
+        }
+
+        btcSigFromOurs, _ := schnorr.ParseSignature(ourSig.Bytes())
+        btcPubParsed, _ := schnorr.ParsePubKey(ourPub.XOnlyBytes())
+        if !btcSigFromOurs.Verify(msg[:], btcPubParsed) {
+                t.Error("our signature failed btcec verification")
+        }
+
+        // Test 2: Sign with btcec, verify with both
+        btcSig, err := schnorr.Sign(btcPriv, msg[:])
+        if err != nil {
+                t.Fatalf("btcec Sign failed: %v", err)
+        }
+
+        btcPubForVerify, _ := schnorr.ParsePubKey(schnorr.SerializePubKey(btcPub))
+        if !btcSig.Verify(msg[:], btcPubForVerify) {
+                t.Error("btcec signature failed btcec verification")
+        }
+
+        sigFromBtcec, _ := SignatureFromBytes(btcSig.Serialize())
+        if !Verify(ourPub, msg[:], sigFromBtcec) {
+                t.Error("btcec signature failed our verification")
+        }
+}
+
+// BIP340TestVector represents an official BIP-340 test vector
+type BIP340TestVector struct {
+        Index     int
+        SecretKey string // hex, empty for verification-only tests
+        PublicKey string // hex, 32 bytes x-only
+        AuxRand   string // hex, 32 bytes
+        Message   string // hex, 32 bytes
+        Signature string // hex, 64 bytes
+        Valid     bool
+        Comment   string
+}
+
+// TestBIP340Vectors tests against official BIP-340 test vectors
+func TestBIP340Vectors(t *testing.T) {
+        // Official test vectors from BIP-340
+        // https://github.com/bitcoin/bips/blob/master/bip-0340/test-vectors.csv
+        vectors := []BIP340TestVector{
+                {
+                        Index:     0,
+                        SecretKey: "0000000000000000000000000000000000000000000000000000000000000003",
+                        PublicKey: "f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9",
+                        AuxRand:   "0000000000000000000000000000000000000000000000000000000000000000",
+                        Message:   "0000000000000000000000000000000000000000000000000000000000000000",
+                        Signature: "e907831f80848d1069a5371b402410364bdf1c5f8307b0084c55f1ce2dca821525f66a4a85ea8b71e482a74f382d2ce5ebeee8fdb2172f477df4900d310536c0",
+                        Valid:     true,
+                },
+                {
+                        Index:     1,
+                        SecretKey: "b7e151628aed2a6abf7158809cf4f3c762e7160f38b4da56a784d9045190cfef",
+                        PublicKey: "dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659",
+                        AuxRand:   "0000000000000000000000000000000000000000000000000000000000000001",
+                        Message:   "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89",
+                        Signature: "6896bd60eeae296db48a229ff71dfe071bde413e6d43f917dc8dcf8c78de33418906d11ac976abccb20b091292bff4ea897efcb639ea871cfa95f6de339e4b0a",
+                        Valid:     true,
+                },
+                {
+                        Index:     2,
+                        SecretKey: "c90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b14e5c9",
+                        PublicKey: "dd308afec5777e13121fa72b9cc1b7cc0139715309b086c960e18fd969774eb8",
+                        AuxRand:   "c87aa53824b4d7ae2eb035a2b5bbbccc080e76cdc6d1692c4b0b62d798e6d906",
+                        Message:   "7e2d58d8b3bcdf1abadec7829054f90dda9805aab56c77333024b9d0a508b75c",
+                        Signature: "5831aaeed7b44bb74e5eab94ba9d4294c49bcf2a60728d8b4c200f50dd313c1bab745879a5ad954a72c45a91c3a51d3c7adea98d82f8481e0e1e03674a6f3fb7",
+                        Valid:     true,
+                },
+                {
+                        Index:     3,
+                        SecretKey: "0b432b2677937381aef05bb02a66ecd012773062cf3fa2549e44f58ed2401710",
+                        PublicKey: "25d1dff95105f5253c4022f628a996ad3a0d95fbf21d468a1b33f8c160d8f517",
+                        AuxRand:   "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
+                        Message:   "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
+                        Signature: "7eb0509757e246f19449885651611cb965ecc1a187dd51b64fda1edc9637d5ec97582b9cb13db3933705b32ba982af5af25fd78881ebb32771fc5922efc66ea3",
+                        Valid:     true,
+                },
+                // Verification-only vectors (public key only, testing invalid signatures)
+                {
+                        Index:     4,
+                        PublicKey: "d69c3509bb99e412e68b0fe8544e72837dfa30746d8be2aa65975f29d22dc7b9",
+                        Message:   "4df3c3f68fcc83b27e9d42c90431a72499f17875c81a599b566c9889b9696703",
+                        Signature: "00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c6376afb1548af603b3eb45c9f8207dee1060cb71c04e80f593060b07d28308d7f4",
+                        Valid:     true,
+                        Comment:   "sG - eP is infinite",
+                },
+                {
+                        Index:     5,
+                        PublicKey: "eefdea4cdb677750a420fee807eacf21eb9898ae79b9768766e4faa04a2d4a34",
+                        Message:   "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89",
+                        Signature: "6cff5c3ba86c69ea4b7376f31a9bcb4f74c1976089b2d9963da2e5543e17776969e89b4c5564d00349106b8497785dd7d1d713a8ae82b32fa79d5f7fc407d39b",
+                        Valid:     false,
+                        Comment:   "public key not on curve",
+                },
+                {
+                        Index:     6,
+                        PublicKey: "dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659",
+                        Message:   "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89",
+                        Signature: "fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a14602975563cc27944640ac607cd107ae10923d9ef7a73c643e166be5ebeafa34b1ac553e2",
+                        Valid:     false,
+                        Comment:   "has_even_y(R) is false",
+                },
+                {
+                        Index:     7,
+                        PublicKey: "dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659",
+                        Message:   "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89",
+                        Signature: "1fa62e331edbc21c394792d2ab1100a7b432b013df3f6ff4f99fcb33e0e1515f28890b3edb6e7189b630448b515ce4f8622a954cfe545735aaea5134fccdb2bd",
+                        Valid:     false,
+                        Comment:   "negated message",
+                },
+                {
+                        Index:     8,
+                        PublicKey: "dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659",
+                        Message:   "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89",
+                        Signature: "6cff5c3ba86c69ea4b7376f31a9bcb4f74c1976089b2d9963da2e5543e177769961764b3aa9b2ffcb6ef947b6887a226e8d7c93e00c5ed0c1834ff0d0c2e6da6",
+                        Valid:     false,
+                        Comment:   "negated s value",
+                },
+                {
+                        Index:     9,
+                        PublicKey: "dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659",
+                        Message:   "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89",
+                        Signature: "0000000000000000000000000000000000000000000000000000000000000000123dda8328af9c23a94c1feecfd123ba4fb73476f0d594dcb65c6425bd186051",
+                        Valid:     false,
+                        Comment:   "sG - eP is infinite (edge case)",
+                },
+                {
+                        Index:     10,
+                        PublicKey: "dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659",
+                        Message:   "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89",
+                        Signature: "00000000000000000000000000000000000000000000000000000000000000017615fbaf5ae28864013c099742deadb4dba87f11ac6754f93780d5a1837cf197",
+                        Valid:     false,
+                        Comment:   "sig[0:32] is not an X coordinate on the curve",
+                },
+                {
+                        Index:     11,
+                        PublicKey: "dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659",
+                        Message:   "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89",
+                        Signature: "4a298dacae57395a15d0795ddbfd1dcb564da82b0f269bc70a74f8220429ba1d69e89b4c5564d00349106b8497785dd7d1d713a8ae82b32fa79d5f7fc407d39b",
+                        Valid:     false,
+                        Comment:   "sig[0:32] is equal to field size",
+                },
+                {
+                        Index:     12,
+                        PublicKey: "dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659",
+                        Message:   "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89",
+                        Signature: "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f69e89b4c5564d00349106b8497785dd7d1d713a8ae82b32fa79d5f7fc407d39b",
+                        Valid:     false,
+                        Comment:   "sig[0:32] is equal to field size",
+                },
+                {
+                        Index:     13,
+                        PublicKey: "dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659",
+                        Message:   "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89",
+                        Signature: "6cff5c3ba86c69ea4b7376f31a9bcb4f74c1976089b2d9963da2e5543e177769fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
+                        Valid:     false,
+                        Comment:   "sig[32:64] is equal to curve order",
+                },
+        }
+
+        for _, v := range vectors {
+                name := "vec" + string(rune('0'+v.Index))
+                if v.Comment != "" {
+                        name += "_" + v.Comment[:min(20, len(v.Comment))]
+                }
+
+                t.Run(name, func(t *testing.T) {
+                        pubBytes, _ := hex.DecodeString(v.PublicKey)
+                        msgBytes, _ := hex.DecodeString(v.Message)
+                        sigBytes, _ := hex.DecodeString(v.Signature)
+
+                        // If we have a secret key, test signing as well
+                        if v.SecretKey != "" {
+                                secBytes, _ := hex.DecodeString(v.SecretKey)
+                                auxBytes, _ := hex.DecodeString(v.AuxRand)
+
+                                // Test our signing produces the expected signature
+                                priv, err := NewPrivateKeyFromBytes(secBytes)
+                                if err != nil {
+                                        t.Fatalf("failed to create private key: %v", err)
+                                }
+
+                                sig, err := Sign(priv, msgBytes, auxBytes)
+                                if err != nil {
+                                        t.Fatalf("Sign failed: %v", err)
+                                }
+
+                                if !bytes.Equal(sig.Bytes(), sigBytes) {
+                                        t.Errorf("signature mismatch\ngot:  %x\nwant: %x",
+                                                sig.Bytes(), sigBytes)
+                                }
+
+                                // Verify public key matches
+                                pub := priv.PublicKey()
+                                if !bytes.Equal(pub.XOnlyBytes(), pubBytes) {
+                                        t.Errorf("public key mismatch\ngot:  %x\nwant: %x",
+                                                pub.XOnlyBytes(), pubBytes)
+                                }
+                        }
+
+                        // Test verification
+                        pubPoint, err := liftX(new(big.Int).SetBytes(pubBytes))
+                        if err != nil {
+                                if v.Valid {
+                                        t.Errorf("liftX failed for valid vector: %v", err)
+                                }
+                                return // Can't test verification if pubkey is invalid
+                        }
+                        pub := &PublicKey{Point: pubPoint}
+
+                        sig, err := SignatureFromBytes(sigBytes)
+                        if err != nil {
+                                if v.Valid {
+                                        t.Errorf("SignatureFromBytes failed for valid vector: %v", err)
+                                }
+                                return
+                        }
+
+                        result := Verify(pub, msgBytes, sig)
+                        if result != v.Valid {
+                                t.Errorf("Verify returned %v, expected %v", result, v.Valid)
+                        }
+                })
+        }
+}
+
+// TestTaggedHashFormat verifies our tagged hash follows BIP-340 format:
+// SHA256(SHA256(tag) || SHA256(tag) || msg)
+func TestTaggedHashFormat(t *testing.T) {
+        // Verify the structure is correct by checking determinism and length
+        tags := []string{"BIP0340/challenge", "BIP0340/aux", "BIP0340/nonce"}
+
+        for _, tag := range tags {
+                t.Run(tag, func(t *testing.T) {
+                        msg := []byte("test message")
+                        result1 := TaggedHash(tag, msg)
+                        result2 := TaggedHash(tag, msg)
+
+                        if len(result1) != 32 {
+                                t.Errorf("expected 32 bytes, got %d", len(result1))
+                        }
+
+                        if !bytes.Equal(result1, result2) {
+                                t.Error("TaggedHash is not deterministic")
+                        }
+
+                        // Different tags should produce different results
+                        otherResult := TaggedHash("different/tag", msg)
+                        if bytes.Equal(result1, otherResult) {
+                                t.Error("different tags produced same hash")
+                        }
+
+                        // Different messages should produce different results
+                        differentMsg := TaggedHash(tag, []byte("different"))
+                        if bytes.Equal(result1, differentMsg) {
+                                t.Error("different messages produced same hash")
+                        }
+                })
+        }
+}
diff --git a/go.mod b/go.mod
index f8eed0f..7d2f45d 100644
--- a/go.mod
+++ b/go.mod
@@ -1,3 +1,11 @@
 module secp256k1-learn
 
 go 1.23.5
+
+require github.com/btcsuite/btcd/btcec/v2 v2.3.6
+
+require (
+        github.com/btcsuite/btcd/chaincfg/chainhash v1.0.1 // indirect
+        github.com/decred/dcrd/crypto/blake256 v1.0.0 // indirect
+        github.com/decred/dcrd/dcrec/secp256k1/v4 v4.0.1 // indirect
+)
diff --git a/go.sum b/go.sum
new file mode 100644
index 0000000..3f06a00
--- /dev/null
+++ b/go.sum
@@ -0,0 +1,10 @@
+github.com/btcsuite/btcd/btcec/v2 v2.3.6 h1:IzlsEr9olcSRKB/n7c4351F3xHKxS2lma+1UFGCYd4E=
+github.com/btcsuite/btcd/btcec/v2 v2.3.6/go.mod h1:m22FrOAiuxl/tht9wIqAoGHcbnCCaPWyauO8y2LGGtQ=
+github.com/btcsuite/btcd/chaincfg/chainhash v1.0.1 h1:q0rUy8C/TYNBQS1+CGKw68tLOFYSNEs0TFnxxnS9+4U=
+github.com/btcsuite/btcd/chaincfg/chainhash v1.0.1/go.mod h1:7SFka0XMvUgj3hfZtydOrQY2mwhPclbT2snogU7SQQc=
+github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
+github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/decred/dcrd/crypto/blake256 v1.0.0 h1:/8DMNYp9SGi5f0w7uCm6d6M4OU2rGFK09Y2A4Xv7EE0=
+github.com/decred/dcrd/crypto/blake256 v1.0.0/go.mod h1:sQl2p6Y26YV+ZOcSTP6thNdn47hh8kt6rqSlvmrXFAc=
+github.com/decred/dcrd/dcrec/secp256k1/v4 v4.0.1 h1:YLtO71vCjJRCBcrPMtQ9nqBsqpA1m5sE92cU+pd5Mcc=
+github.com/decred/dcrd/dcrec/secp256k1/v4 v4.0.1/go.mod h1:hyedUtir6IdtD/7lIxGeCxkaw7y45JueMRL4DIyJDKs=