Pages:
Author

Topic: [SOLVED] Can someone explain the details of how OP_CHECKSIG operates? (Read 9278 times)

Hal
vip
Activity: 314
Merit: 4276
I was able to verify the signature using the openssl command line and a bunch of cutting and pasting of hex dumps. The data input to the hash is
Code:
01 00 00 00 03 30 f3 70  1f 9b c4 64 55 2f 70 49  |.....0.p...dU/pI|
57 91 04 08 17 ce 77 7a  d5 ed e1 6e 52 9f cd 0c  |W.....wz...nR...|
0e 94 91 56 94 00 00 00  00 19 76 a9 14 02 bf 4b  |...V......v....K|
28 89 c6 ad a8 19 0c 25  2e 70 bd e1 a1 90 9f 96  |(......%.p......|
17 88 ac ff ff ff ff 72  14 2b f7 68 6c e9 2c 6d  |.......r.+.hl.,m|
e5 b7 33 65 bf b9 d5 9b  b6 0c 2c 80 98 2d 59 58  |..3e......,..-YX|
c1 e6 a3 b0 8e a6 89 00  00 00 00 00 ff ff ff ff  |................|
d2 81 28 bb b6 20 7c 1c  3d 0a 63 0c c6 19 dc 7e  |..(.. |.=.c....~|
7b ea 56 ac 19 a1 da b1  27 c6 2c 78 fa 1b 63 2c  |{.V.....'.,x..c,|
00 00 00 00 00 ff ff ff  ff 01 00 a6 f7 5f 02 00  |............._..|
00 00 19 76 a9 14 9e 35  d9 3c 77 92 bd ca ad 56  |...v...5.97 dd eb f0 43 53 d9 a5  e1 96 88 ac 00 00 00 00  |....CS..........|
01 00 00 00                                       |....|

and the hash is

e8a875b4a6b23e507cdad56d1d74285f22fec05bfd6be2f737923c43fcc23987

If you have this value, it is correct, and you can look elsewhere.
Activity: -
Merit: -
I'm going to mark this thread as solved since the OP_CHECKSIG stuff is all figured out now.

I'll start a new thread for BouncyCastle related stuff.
Activity: -
Merit: -
Sorry, I can't give you any more code.

Consider the following things:

1) Are you trying to make an Android client? You don't want to verify transactions if so.

2) ECDSA signature verification is a pure function of hash+pubkey+curve params. That isn't much potential for problems. Remember that anything handled by OpenSSL is big endian, thus both hash and pubkey should be BE. Try swapping things around if this doesn't come good.

Also make sure you're correctly deserializing the co-ordinates from the ASN.1 structure. I used the Bouncy Castle ASN.1 decoder to achieve this.



No problem.  Thanks for all the help you were able to give, though!! Smiley  I'll play around with things and see if I can't get it working.
legendary
Activity: 1526
Merit: 1134
Sorry, I can't give you any more code.

Consider the following things:

1) Are you trying to make an Android client? You don't want to verify transactions if so.

2) ECDSA signature verification is a pure function of hash+pubkey+curve params. That isn't much potential for problems. Remember that anything handled by OpenSSL is big endian, thus both hash and pubkey should be BE. Try swapping things around if this doesn't come good.

Also make sure you're correctly deserializing the co-ordinates from the ASN.1 structure. I used the Bouncy Castle ASN.1 decoder to achieve this.

Activity: -
Merit: -
Okay, I did that too, and the secret is that the scriptSig is entirely removed and replaced with the scriptPubKey from the source (old) transaction. I'm still a little confused about how this works in the source.

VerifyScript() doesn't actually concatenate the two scripts. It runs scriptSig, and that leaves stuff on the stack, then it runs the old scriptPubKey with the stack left by scriptSig. The only connection is the stack. So when we run the scriptPubKey, which holds the OP_CHECKSIG, the "current script" is just that, the old scriptPubKey. This is the script which gets OP_CODESEPARATOR stripped and then put in place of the scriptSig, for hashing.

Yes, I believe you are correct.  I added a few more lines to the official client to print out the actual transaction, the hash of the actual transaction, and the hash of the tmpTx.

What I found out is that my OP_CHECKSIG code is now correct, and I get the same hash of tmpTx.  So now I have narrowed my problem down to my signature verification code.  I believe dirtyfilthy said his wasn't working either, and we are both using the same classes/methods for our signature verification.  [mike], however, is doing it a different way, of which I think it was implied to be working correctly for him.

So, [mike]...would you be able to help us out a little bit, here?? Wink
legendary
Activity: 1526
Merit: 1134
I used the Bouncy Castle ECDSA API directly. I don't have any Java JCE code in my app.
administrator
Activity: 5222
Merit: 13032
But it doesn't make sense, because there is no signature in scriptPubKey, which is where this opcode is found. This line doesn't seem to do anything, and advice to remove a nonexistent signature is misleading.

It's legal to put a signature in the scriptPubKey -- Bitcoin just doesn't do so.
Hal
vip
Activity: 314
Merit: 4276
Okay, I did that too, and the secret is that the scriptSig is entirely removed and replaced with the scriptPubKey from the source (old) transaction. I'm still a little confused about how this works in the source.

VerifyScript() doesn't actually concatenate the two scripts. It runs scriptSig, and that leaves stuff on the stack, then it runs the old scriptPubKey with the stack left by scriptSig. The only connection is the stack. So when we run the scriptPubKey, which holds the OP_CHECKSIG, the "current script" is just that, the old scriptPubKey. This is the script which gets OP_CODESEPARATOR stripped and then put in place of the scriptSig, for hashing.

What I don't understand is this line from the OP_CHECKSIG code:

                    // Drop the signature, since there's no way for a signature to sign itself
                    scriptCode.FindAndDelete(CScript(vchSig));

This is apparently the basis for the advice to "remove the signature" for hashing. But it doesn't make sense, because there is no signature in scriptPubKey, which is where this opcode is found. This line doesn't seem to do anything, and advice to remove a nonexistent signature is misleading.
Activity: -
Merit: -
For now I'm going to take [mike]'s approach at making the official client print the transactions that are about to be hashed to the log file.

This is in the SignatureHash() function in script.cpp around line 930, right at the very end of the function.  I added the PrintHex line, which prints a hex version of ss to the debug.log file in ~/.bitcoin/
Code:
uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType)

    // other code here
    ...

    // Serialize and hash
    CDataStream ss(SER_GETHASH);
    ss.reserve(10000);
    ss << txTmp << nHashType;
    PrintHex(ss.begin(), ss.end(), "ss: %s\n"); // I added this line here
    return Hash(ss.begin(), ss.end());
}

As soon as it got the next block, I got a few examples to work with.  I'm going to dig through those sometime, and I'll post back here (probably tomorrow) with what I find out.
Activity: -
Merit: -
I looked at [mike]'s example, but I couldn't find anything that I'm doing wrong, yet.

I'm starting to wonder if maybe we (JVM-based developers) should be using org.bouncycastle.crypto.signers.ECDSASigner for signing and verification instead of java.security.Signature.  I'd like to try it, but I need to figure out what parameters I need to give it...
Activity: -
Merit: -
What you are doing looks pretty good to me now that I understand it better. I tried hashing your data and got 90377525e05bd71ce8ba413a84fdaea299766732f165fab28a69d30c83337f9b, don't know if that matches yours. The only other thing I can think of would be to try reversing the hash on input to the ECDSA functions.

That's the same hash I'm getting...I'm trying different things but not getting it to verify.  I still need to look a little closer at [mike]'s code posted above...
Hal
vip
Activity: 314
Merit: 4276
What you are doing looks pretty good to me now that I understand it better. I tried hashing your data and got 90377525e05bd71ce8ba413a84fdaea299766732f165fab28a69d30c83337f9b, don't know if that matches yours. The only other thing I can think of would be to try reversing the hash on input to the ECDSA functions.
legendary
Activity: 1526
Merit: 1134
The tx is hashed in a form where all the inputs are cleared except the one you are calculating, and that one is set to the connected outputs scriptPubKey.

See below for an example.

Code:
public void signInputs(@NotNull SigHash hashType, @NotNull Wallet wallet) throws ScriptException {
        assert inputs.size() > 0;
        assert outputs.size() > 0;

        // I don't currently have an easy way to test other modes work, as the official client does not use them.
        assert hashType == SigHash.ALL;

        // The transaction is signed with the input scripts empty except for the input we are signing. In the case
        // where addInput has been used to set up a new transaction, they are already all empty. The input being signed
        // has to have the connected OUTPUT program in it when the hash is calculated!
        //
        // Note that each input may be claiming an output sent to a different key. So we have to look at the outputs
        // to figure out which key to sign with.

        byte[][] signatures = new byte[inputs.size()][];
        ECKey[] signingKeys = new ECKey[inputs.size()];
        for (int i = 0; i < inputs.size(); i++) {
            TransactionInput input = inputs.get(i);
            assert input.scriptBytes.length == 0 : "Attempting to sign a non-fresh transaction";
            // Set the input to the script of its output.
            input.scriptBytes = input.outpoint.getConnectedPubKeyScript();
            // Find the signing key we'll need to use.
            byte[] connectedPubKeyHash = input.outpoint.getConnectedPubKeyHash();
            ECKey key = wallet.findKeyFromPubHash(connectedPubKeyHash);
            // This assert should never fire. If it does, it means the wallet is inconsistent.
            assert key != null : "Transaction exists in wallet that we cannot redeem: " + Utils.bytesToHexString(connectedPubKeyHash);
            // Keep the key around for the script creation step below.
            signingKeys[i] = key;
            // The anyoneCanPay feature isn't used at the moment.
            boolean anyoneCanPay = false;
            byte[] hash = hashTransactionForSignature(hashType, anyoneCanPay);
            Utils.LOG("  signInputs hash=" + Utils.bytesToHexString(hash));
            // Set the script to empty again for the next input.
            input.scriptBytes = TransactionInput.EMPTY_ARRAY;

            // Now sign for the output so we can redeem it. We use the keypair to sign the hash,
            // and then put the resulting signature in the script along with the public key (below).
            try {
                ByteArrayOutputStream bos = new ByteArrayOutputStream();
                bos.write(key.sign(hash));
                bos.write((hashType.ordinal() + 1) | (anyoneCanPay ? 0x80 : 0)) ;
                signatures[i] = bos.toByteArray();
            } catch (IOException e) {
                throw new RuntimeException(e);  // Cannot happen.
            }
        }

        // Now we have calculated each signature, go through and create the scripts. Reminder: the script consists of
        // a signature (over a hash of the transaction) and the complete public key needed to sign for the connected
        // output.
        for (int i = 0; i < inputs.size(); i++) {
            TransactionInput input = inputs.get(i);
            assert input.scriptBytes.length == 0;
            ECKey key = signingKeys[i];
            input.scriptBytes = Script.createInputScript(signatures[i], key.getPubKey());
        }

        // Every input is now complete.
    }
Activity: -
Merit: -
Okay, I've confirmed that hashes OK using sha256sum and gets your value, 0f898c5494eaa468d12cf0630a0c0b238cc1149c1c53bbc592d16497094e95ff. So the question remains to verify the sig.

You will have to add 01 00 00 00 to the end before you hash, for the hashtype.

I'm not sure about your scriptsig shortening. You removed the sig ok, but there seems to be more stuff added at the end, after the pubkey.

Yeah, I'm adding those 4 bytes before hashing.

As for the extra stuff after the pubkey, what I'm (possibly incorrectly) doing there is using the combined scripts of scriptSig (from TxIn) and scriptPubKey (from prev TxOut), then removing the signature and OP_CODESEPARATOR (which there are none in any examples I've tried so far).  So that extra stuff is the scriptPubKey...it's possible it's not supposed to be there, but even when I remove that, it still doesn't verify anyway, so I don't know yet if that's a problem, too.

Here's the original scriptSig from TxIn:
Code:
49 30 46 02 21 00 f5 74 6b 0b 25 4f 5a 37 e7 52
51 45 9c 7a 23 b6 df cb 86 8a c7 46 7e dd 9a 6f
dd 1d 96 98 71 be 02 21 00 88 94 8a ea 29 b6 91
61 ca 34 1c 49 c0 26 86 a8 1d 8c bb 73 94 0f 91
7f a0 ed 71 54 68 6d 3e 5b 01 41 04 47 d4 90 56
1f 39 6c 8a 9e fc 14 48 6b c1 98 88 4b a1 83 79
bc ac 2e 0b e2 d8 52 51 34 ab 74 2f 30 1a 9a ca
36 60 6e 5d 29 aa 23 8a 9e 29 93 00 31 50 42 3d
f6 92 45 63 64 2d 4a fe 9b f4 fe 28


Signature size:
 49
Signature:
 30 46 02 21 00 f5 74 6b 0b 25 4f 5a 37 e7 52 51
 45 9c 7a 23 b6 df cb 86 8a c7 46 7e dd 9a 6f dd
 1d 96 98 71 be 02 21 00 88 94 8a ea 29 b6 91 61
 ca 34 1c 49 c0 26 86 a8 1d 8c bb 73 94 0f 91 7f
 a0 ed 71 54 68 6d 3e 5b 01


Broken down further:

Public key size:
 41
Public key:
 04
 X:
  47 d4 90 56 1f 39 6c 8a 9e fc 14 48 6b c1 98 88
  4b a1 83 79 bc ac 2e 0b e2 d8 52 51 34 ab 74 2f
 Y:
  30 1a 9a ca 36 60 6e 5d 29 aa 23 8a 9e 29 93 00
  31 50 42 3d f6 92 45 63 64 2d 4a fe 9b f4 fe 28

and here's the concatenated scripts with the signature removed:
Code:
41 04 47 d4 90 56 1f 39 6c 8a 9e fc 14 48 6b c1
98 88 4b a1 83 79 bc ac 2e 0b e2 d8 52 51 34 ab
74 2f 30 1a 9a ca 36 60 6e 5d 29 aa 23 8a 9e 29
93 00 31 50 42 3d f6 92 45 63 64 2d 4a fe 9b f4
fe 28 76 a9 14 02 bf 4b 28 89 c6 ad a8 19 0c 25
2e 70 bd e1 a1 90 9f 96 17 88 ac


Broken down further:

Public key size:
41
Public key:
04
 X:
  47 d4 90 56 1f 39 6c 8a 9e fc 14 48 6b c1 98 88
  4b a1 83 79 bc ac 2e 0b e2 d8 52 51 34 ab 74 2f
 Y:
  30 1a 9a ca 36 60 6e 5d 29 aa 23 8a 9e 29 93 00
  31 50 42 3d f6 92 45 63 64 2d 4a fe 9b f4 fe 28
scriptPubKey:
 76 - OP_DUP
 a9 - OP_HASH160
 14 - number of bytes to push
 02 bf 4b 28 89 c6 ad a8 19 0c 25 2e 70 bd e1 a1 90 9f 96 17 - push these bytes onto stack
 88 - OP_EQUALVERIFY
 ac - OP_CHECKSIG

Is scriptPubKey supposed to be in here, too, when created the new temporary transaction to be hashed?  So far any docs I've found make it sound like it's there or just don't specify what script or combination of scripts it's supposed to deal with when verifying a transaction.
Hal
vip
Activity: 314
Merit: 4276
Okay, I've confirmed that hashes OK using sha256sum and gets your value, 0f898c5494eaa468d12cf0630a0c0b238cc1149c1c53bbc592d16497094e95ff. So the question remains to verify the sig.

You will have to add 01 00 00 00 to the end before you hash, for the hashtype.

I'm not sure about your scriptsig shortening. You removed the sig ok, but there seems to be more stuff added at the end, after the pubkey.
Activity: -
Merit: -
Wow, that's bizarre that the byte order of the hashes is reversed on the wire like that. Have you tried reproducing the published transaction hash by hashing the raw transaction? Does that work? What do you get, 0f89... as it is on the wire, or the reverse, ff95... as blockexplorer has it? And do you need to byte reverse the embedded hashes in the tx in order to get the right answer?

Yeah, I can take a raw transaction from blk0001.dat or from the wire and hash it, and I get the same bytes that are shown on those websites, but in reverse order.  From what I just found out in IRC, bitcoin internally treats these hashes as little endian BigNumbers, and then when their hex code is printed out, it's in reverse order from the actual data.
Hal
vip
Activity: 314
Merit: 4276
Wow, that's bizarre that the byte order of the hashes is reversed on the wire like that. Have you tried reproducing the published transaction hash by hashing the raw transaction? Does that work? What do you get, 0f89... as it is on the wire, or the reverse, ff95... as blockexplorer has it? And do you need to byte reverse the embedded hashes in the tx in order to get the right answer?
Activity: -
Merit: -
I don't see how that hex dump corresponds to the transaction. You have outpoint hashes starting with 30 f3, 72 14, and d2 81, none of which are in the transaction.

This is a difference between the byte order as pulled from blk0001.dat and as shown on sites like blockexplorer and blk.bitcoinwatch.com.  I know when I lookup a block or transaction hash in the blkindex.dat file, I have to lookup the reverse of what is shown on those websites, and I although I'm setting my ChannelBuffer's to little endian, when reading bytes rather than numbers, it should be reading them left-to-right.  To top it off, however, my packet sniff's have also shown these hashes to be in the opposite order from what is found on blockexplorer and blk.bitcoinwatch.com.

Code:
This is the reverse byte order of --------------------------------> This
945691940e0ccd9f526ee1edd57a77ce170804915749702f5564c49b1f70f330 -- 30f3701f9bc464552f70495791040817ce777ad5ede16e529fcd0c0e94915694

I wrote the hashes on my previous post to match the order found at those sites, but perhaps I should edit my post.  At least they'd be consistent in my posts, then.  No reason to make my posts confusing because some sites are doing things backwards.

EDIT: I changed the byte-order of those hashes.
Hal
vip
Activity: 314
Merit: 4276
I don't see how that hex dump corresponds to the transaction. You have outpoint hashes starting with 30 f3, 72 14, and d2 81, none of which are in the transaction.
legendary
Activity: 1526
Merit: 1134
Yes, this took a while for me to get right as well.

I'm afraid you just have to pay REALLY careful attention to endian-ness and data element size. Note that at one point the hash type marker is serialized as a uint32 (four bytes) and at another point it's serialized as one byte.

In the end I did this by instrumenting the official client and making it dump out what it was hashing. After fixing some bugs I got them to match and was able to successfully send/receive coins with my own Java code.

I really wish I could release this code to help you! Unfortunately for reasons I won't delve into here, I can't do so (at the moment). Good luck!
Pages:
Jump to: