Signature verification in python using compressed public key

Question

I am trying to learn bitcoin blockchain programming. I am trying to verify signature in Transaction with txid: 4269fdc239d027922dcec96f1ae283dbaff10e2d1bd49605661d091e79714956

I am getting BadSignatureError

Raw Transaction

./bitcoin-cli getrawtransaction 4269fdc239d027922dcec96f1ae283dbaff10e2d1bd49605661d091e79714956
01000000017f950ab790838e0c05e79856d25d586823fe139e1807405a3f207ff33f9b7663010000006b483045022100d8629403cd3b49950da9293653c6279149c029e6b7b15371342d0d2ce286c8f2022078787985a644e94fd9246f6c25733336c94af5f00d9d34a07dc2f9e0987ef990012102b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d90ffffffff021bf03c000000000017a91469f3757380a56820abc7052867216599e575cddd8777c1ca1c000000001976a914d5f950abe0b559b2b7a7ab3d18a507ea1c3e4ac688ac00000000

Decode Raw Transaction

./core/bitcoin-0.16.0/bin/bitcoin-cli decoderawtransaction 01000000017f950ab790838e0c05e79856d25d586823fe139e1807405a3f207ff33f9b7663010000006b483045022100d8629403cd3b49950da9293653c6279149c029e6b7b15371342d0d2ce286c8f2022078787985a644e94fd9246f6c25733336c94af5f00d9d34a07dc2f9e0987ef990012102b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d90ffffffff021bf03c000000000017a91469f3757380a56820abc7052867216599e575cddd8777c1ca1c000000001976a914d5f950abe0b559b2b7a7ab3d18a507ea1c3e4ac688ac00000000
{
  "txid": "4269fdc239d027922dcec96f1ae283dbaff10e2d1bd49605661d091e79714956",
  "hash": "4269fdc239d027922dcec96f1ae283dbaff10e2d1bd49605661d091e79714956",
  "version": 1,
  "size": 224,
  "vsize": 224,
  "locktime": 0,
  "vin": [
    {
      "txid": "63769b3ff37f203f5a4007189e13fe2368585dd25698e7050c8e8390b70a957f",
      "vout": 1,
      "scriptSig": {
        "asm": "3045022100d8629403cd3b49950da9293653c6279149c029e6b7b15371342d0d2ce286c8f2022078787985a644e94fd9246f6c25733336c94af5f00d9d34a07dc2f9e0987ef990[ALL] 02b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d90",
        "hex": "483045022100d8629403cd3b49950da9293653c6279149c029e6b7b15371342d0d2ce286c8f2022078787985a644e94fd9246f6c25733336c94af5f00d9d34a07dc2f9e0987ef990012102b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d90"
      },
      "sequence": 4294967295
    }
  ],
  "vout": [
    {
      "value": 0.03993627,
      "n": 0,
      "scriptPubKey": {
        "asm": "OP_HASH160 69f3757380a56820abc7052867216599e575cddd OP_EQUAL",
        "hex": "a91469f3757380a56820abc7052867216599e575cddd87",
        "reqSigs": 1,
        "type": "scripthash",
        "addresses": [
          "3BMEXVvXXRFh2eJ9Eji115xfqJjWmLTCf8"
        ]
      }
    },
    {
      "value": 4.83049847,
      "n": 1,
      "scriptPubKey": {
        "asm": "OP_DUP OP_HASH160 d5f950abe0b559b2b7a7ab3d18a507ea1c3e4ac6 OP_EQUALVERIFY OP_CHECKSIG",
        "hex": "76a914d5f950abe0b559b2b7a7ab3d18a507ea1c3e4ac688ac",
        "reqSigs": 1,
        "type": "pubkeyhash",
        "addresses": [
          "1LWPbaYN2jqhv9oZvYHxYKXuaiR1qJn52i"
        ]
      }
    }
  ]
}

Here "asm" contains Signation and Public Key

  "vin": [
    {
      "txid": "63769b3ff37f203f5a4007189e13fe2368585dd25698e7050c8e8390b70a957f",
      "vout": 1,
      "scriptSig": {
        "asm": "3045022100d8629403cd3b49950da9293653c6279149c029e6b7b15371342d0d2ce286c8f2022078787985a644e94fd9246f6c25733336c94af5f00d9d34a07dc2f9e0987ef990[ALL] 02b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d90",
        "hex": "483045022100d8629403cd3b49950da9293653c6279149c029e6b7b15371342d0d2ce286c8f2022078787985a644e94fd9246f6c25733336c94af5f00d9d34a07dc2f9e0987ef990012102b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d90"
      },
      "sequence": 4294967295
    }
  ],

To obtain Signature

3045022100d8629403cd3b49950da9293653c6279149c029e6b7b15371342d0d2ce286c8f2022078787985a644e94fd9246f6c25733336c94af5f00d9d34a07dc2f9e0987ef990
=>
0x30 DER
0x45 Length
0x02 Type Integer
0x21 Length of R
0x00d8629403cd3b49950da9293653c6279149c029e6b7b15371342d0d2ce286c8f2 (R)
0x02 Type Integer
0x20 Length of S
0x78787985a644e94fd9246f6c25733336c94af5f00d9d34a07dc2f9e0987ef990 (S)

Removing 00 from R
Signature = R + S = d8629403cd3b49950da9293653c6279149c029e6b7b15371342d0d2ce286c8f278787985a644e94fd9246f6c25733336c94af5f00d9d34a07dc2f9e0987ef990

Compressed Public Key 02b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d90

Uncompressing Public Key Code

def getFullPubKeyFromCompressed(x_str: str):
        prefix = x_str[0:2]
        print("prefix = %s" % (prefix))
        x_str = x_str[2:]
        x = int(x_str, 16)
        print("x = %x" % (x))
        p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
        y_squared = (x**3 + 7) % p
        y = modular_sqrt(y_squared, p)
        y_str = "%x" % y
        print("y_str = %s" % (y_str))
        y_is_even = (int(y_str[-1], 16) % 2 == 0)
        if prefix == "02" and y_is_even == False or prefix == "03" and y_is_even == True:
                y = p - y
                y_str = "%x" % y
        print("y = %s" % (y_str))
        return "04" + x_str + y_str

prefix = pubkey[0:2]
if prefix == "02" or prefix == "03":
        pubkey = getFullPubKeyFromCompressed(pubkey)[2:]
elif prefix == "04":
                pubkey = pubkey[2:]
print("full public key = %s" % pubkey)

Output:

x = b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d90
y_str = cacc567dc3036f2fceb1b6f16676285b153821eb79825dae124b17b9e29479cb
y = 3533a9823cfc90d0314e490e9989d7a4eac7de14867da251edb4e8451d6b8264
full public key = b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d903533a9823cfc90d0314e490e9989d7a4eac7de14867da251edb4e8451d6b8264

Transaction single time SHA256 hashing as this will be done again signature verification Code

hashval = binascii.hexlify(hashlib.sha256(bytes.fromhex(raw_txn)).digest())
txn_sha256 = bytes.decode(hashval)
print("txn_sha256 = %s" % (txn_sha256))

Output

txn_sha256 = fb0c792bfba8139654cffd2818bdd56f3541d11fb43ea46f646c3477de3d2e40

We have all three information to verify signature now

txn_sha256 = fb0c792bfba8139654cffd2818bdd56f3541d11fb43ea46f646c3477de3d2e40
pubkey = b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d903533a9823cfc90d0314e490e9989d7a4eac7de14867da251edb4e8451d6b8264
sig = d8629403cd3b49950da9293653c6279149c029e6b7b15371342d0d2ce286c8f278787985a644e94fd9246f6c25733336c94af5f00d9d34a07dc2f9e0987ef990

I execute check signature program

sig_b = bytes.fromhex(sig)
txn_sha256_b = bytes.fromhex(txn_sha256)
vk = ecdsa.VerifyingKey.from_string(bytes.fromhex(pubkey),curve=ecdsa.SECP256k1)
if vk.verify(sig_b, txn_sha256_b, hashlib.sha256) == True: # True
        print("Signature is Valid")
else:
        print("Signature is not Valid")

But I get BadSignatureError

Traceback (most recent call last):
  File "bitcoin_localapis.py", line 294, in <module>
    sigcheck(sig, pubkey, raw_txn)
  File "bitcoin_localapis.py", line 202, in sigcheck
    if vk.verify(sig_b, txn_sha256_b, hashlib.sha256) == True: # True
  File "/home/vizeet/anaconda3/lib/python3.6/site-packages/ecdsa/keys.py", line 101, in verify
    return self.verify_digest(signature, digest, sigdecode)
  File "/home/vizeet/anaconda3/lib/python3.6/site-packages/ecdsa/keys.py", line 113, in verify_digest
    raise BadSignatureError
ecdsa.keys.BadSignatureError

Please help me solve this issue.

Answer 1

Problem was with the Raw Transaction I used for signature verification.

Original Raw Transaction

./bitcoin-cli getrawtransaction 4269fdc239d027922dcec96f1ae283dbaff10e2d1bd49605661d091e79714956
01000000017f950ab790838e0c05e79856d25d586823fe139e1807405a3f207ff33f9b7663010000006b483045022100d8629403cd3b49950da9293653c6279149c029e6b7b15371342d0d2ce286c8f2022078787985a644e94fd9246f6c25733336c94af5f00d9d34a07dc2f9e0987ef990012102b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d90ffffffff021bf03c000000000017a91469f3757380a56820abc7052867216599e575cddd8777c1ca1c000000001976a914d5f950abe0b559b2b7a7ab3d18a507ea1c3e4ac688ac00000000

Parsing this manually

01 00 00 00 Version 
01 Input Count 
7f 95 0a b7 90 83 8e 0c 05 e7 98 56 d2 5d 58 68 23 fe 13 9e 18 07 40 5a 3f 20 7f f3 3f 9b 76 63 (32 Bytes of Previous Transaction ID)
01 00 00 00 Output Index (vout index) 
6b Script Length (107 bytes) (Replace this)
48 30 45 02 21 00 d8 62 94 03 cd 3b 49 95 0d a9 29 36 53 c6 27 91 49 c0 29 e6 b7 b1 53 71 34 2d 0d 2c e2 86 c8 f2 02 20 78 78 79 85 a6 44 e9 4f d9 24 6f 6c 25 73 33 36 c9 4a f5 f0 0d 9d 34 a0 7d c2 f9 e0 98 7e f9 90 01 21 02 b7 26 d7 ea e1 1a 6d 5c f3 b2 36 2e 77 3e 11 6a 61 40 34 7d ce e1 b2 94 3f 4a 28 97 35 1e 5d 90 Script (and Replace this)
ffffffff021bf03c000000000017a91469f3757380a56820abc7052867216599e575cddd8777c1ca1c000000001976a914d5f950abe0b559b2b7a7ab3d18a507ea1c3e4ac688ac00000000 Remaing bytes 
01 00 00 00 Append SIGHASH_ALL

Replace Portion of transaction marked above with scriptPubKey. There seems to be no reason why we do this. Refer this discussion:

https://bitcointalk.org/index.php?topic=102487.msg1123257#msg1123257

compressed pubkey = 02b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d90

Address from Public Key: Code

def sha256d(bstr):
    return hashlib.sha256(hashlib.sha256(bstr).digest()).digest()

def convertPKHToAddress(prefix, addr):
    data = prefix + addr
    return base58.b58encode(data + sha256d(data)[:4])

def pubkeyToAddress(pubkey_hex):
        pubkey = bytearray.fromhex(pubkey_hex)
        round1 = hashlib.sha256(pubkey).digest()
        h = hashlib.new('ripemd160')
        h.update(round1)
        pubkey_hash = h.digest()
        return convertPKHToAddress(b'\x00', pubkey_hash)

Output Address

1LWPbaYN2jqhv9oZvYHxYKXuaiR1qJn52i

Hash160 of Address (from https://blockchain.info/address/1LWPbaYN2jqhv9oZvYHxYKXuaiR1qJn52i)

d5 f9 50 ab e0 b5 59 b2 b7 a7 ab 3d 18 a5 07 ea 1c 3e 4a c6

Adding size to hashed address

14 d5 f9 50 ab e0 b5 59 b2 b7 a7 ab 3d 18 a5 07 ea 1c 3e 4a c6

Input Transaction Hash = 63769b3ff37f203f5a4007189e13fe2368585dd25698e7050c8e8390b70a957f

This transaction has following out scriptPubKey. One of them is spent in this transaction which we will find out.

out index 0: 76 a9 14 89 df 43 9f 5e 48 c0 e7 ec d6 91 af fa 1f b8 39 15 7e 0a 71 88 ac
out index 1: 76 a9 14 d5 f9 50 ab e0 b5 59 b2 b7 a7 ab 3d 18 a5 07 ea 1c 3e 4a c6 88 ac

Decoding scriptPubKey

OP_DUP = 0x76 (first byte of both)
OP_HASH160 = 0xa9 (second byte of both)
OP_EQUALVERIFY = 0x88 (second last byte of both)
OP_CHECKSIG = 0xac (last byte of both)

So we need Hash160 of public key in scriptSig of transaction we are investigating. This we have already calculated. Adding script to hash160 from public key we get

76 a9 14 d5 f9 50 ab e0 b5 59 b2 b7 a7 ab 3d 18 a5 07 ea 1c 3e 4a c6 88 ac

Size of New script = 25 = 0x19

New script

19 76 a9 14 d5 f9 50 ab e0 b5 59 b2 b7 a7 ab 3d 18 a5 07 ea 1c 3e 4a c6 88 ac

So we found that this is equal to scriptPubKey of second out of input transaction. This out is marked spent.

Now after inserting this script to Raw Transaction.
We get new Raw Transaction

01 00 00 00 Version 
01 Input Count 
7f 95 0a b7 90 83 8e 0c 05 e7 98 56 d2 5d 58 68 23 fe 13 9e 18 07 40 5a 3f 20 7f f3 3f 9b 76 63 (32 Bytes of Previous Transaction ID)
01 00 00 00 Output Index (vout index)
19 76 a9 14 d5 f9 50 ab e0 b5 59 b2 b7 a7 ab 3d 18 a5 07 ea 1c 3e 4a c6 88 ac (New Script)
ffffffff021bf03c000000000017a91469f3757380a56820abc7052867216599e575cddd8777c1ca1c000000001976a914d5f950abe0b559b2b7a7ab3d18a507ea1c3e4ac688ac00000000 (Remaining)
01 00 00 00 Append SIGHASH_ALL

Which becomes New Raw Transaction

01000000017f950ab790838e0c05e79856d25d586823fe139e1807405a3f207ff33f9b7663010000001976a914d5f950abe0b559b2b7a7ab3d18a507ea1c3e4ac688acffffffff021bf03c000000000017a91469f3757380a56820abc7052867216599e575cddd8777c1ca1c000000001976a914d5f950abe0b559b2b7a7ab3d18a507ea1c3e4ac688ac0000000001000000

We need to just apply SHA256 once as signature verify method also applies SHA256. Code

hashval = binascii.hexlify(hashlib.sha256(bytes.fromhex(raw_txn)).digest())
txn_sha256 = bytes.decode(hashval)
print("txn_sha256 = %s" % (txn_sha256))

Output :

txn_sha256 = 3d3b8997cc9c0e2275bd0f694b862f7d0bee4f7aee2456891e038322884070ad

Now we have all three variables required for signature verification

pubkey = b726d7eae11a6d5cf3b2362e773e116a6140347dcee1b2943f4a2897351e5d903533a9823cfc90d0314e490e9989d7a4eac7de14867da251edb4e8451d6b8264
sig = d8629403cd3b49950da9293653c6279149c029e6b7b15371342d0d2ce286c8f278787985a644e94fd9246f6c25733336c94af5f00d9d34a07dc2f9e0987ef990
txn_sha256 = 3d3b8997cc9c0e2275bd0f694b862f7d0bee4f7aee2456891e038322884070ad

Now execiting Signature Verification code code

sig_b = bytes.fromhex(sig)
txn_sha256_b = bytes.fromhex(txn_sha256)
vk = ecdsa.VerifyingKey.from_string(bytes.fromhex(pubkey),curve=ecdsa.SECP256k1)
if vk.verify(sig_b, txn_sha256_b, hashlib.sha256) == True: # True
        print("Signature is Valid")
else:
        print("Signature is not Valid")

Gives Signature is Valid