Signature Generation/Verification - WTF?

[etotheipi]

Of course, the devil is in the details... I've been pouring over the bitcoin specification protocol, finally figuring most of what I need, in terms of pulling public keys and signature components out of a transaction on block explorer.  Now that I have the public key and signature from a particular transaction, I want to verify the signature... but I can't figure out what block of data to verify! 

By the way block explorer is organized, it looks like it's signing the OutPoint structure, but that doesn't make sense, because the recipient address would have to be in the signed data (or else the node receiving the transaction could just replace the recipient addr with their own).  So what is it?

theSignature = privateKey.sign( sha256(sha256( WHAT?!? ) ) )

I've been pounding my head over it, source diving, searching the internet and reading specs.  Unfortunately, the C++ code is too abstract for me to follow.  I hope someone can just tell me!

Thanks,
Eto

[1714851389]

1714851389

[1714851389]

1714851389

[1714851389]

1714851389

[1714851389]

1714851389

[1714851389]

1714851389

[Stefan Thomas]

This is one of the most complicated parts of Bitcoin imho. The data that is signed is a double-SHA256 hash of a specially serialized version of the transaction.

First, the transaction is copied. The input being signed is replaced with the scriptPubKey of the corresponding txout.

With the default hashType SIGHASH_ALL, we're done now. But for the other hashTypes SIGHASH_NONE and SIGHASH_SINGLE as well as the SIGHASH_ANYONECANPAY flag, some more steps are needed. See the function SignatureHash in script.cpp for details.

After that, the transaction is serialized and the hashType is appended as a single byte, followed by three zero bytes, e.g. 01000000.

Then Bitcoin calculates the double SHA256 of that and signs the resulting hash.

I implemented this twice, once in pure JavaScript, once in Node.js. Both times it was a royal pain in the ***.

[etotheipi]

Wow, I guess I can't feel bad about this.  I wasn't even close to figuring it out!  Why is this not documented anywhere!?! 

So I am trying to submit a new transaction (TxNew) which will have multiple OutPoints from multiple old transactions in other blocks (TxOld1, TxOld2, ...)

Which transaction is being copied? 

TxNew = [version,  numIn,  {TxIn1, TxIn2, TxIn3},  numOut,  {TxOut1, TxOut2},  locktime]

Each TxIn object has a script in it   [ TxOldHash, OutIndex, numScriptBytes, SCRIPT, Sequence ]
Each TxOut object has a script in it [ Amt, numScriptBytes, PK_SCRIPT]

First of all... I have broken apart ONE of these scripts, but I can't even remember which one.  It is [DerSignature, PublicKey] ... is this SCRIPT?  or PK_SCRIPT?  Or is that only part of one of those scripts?
Second, which scripts and which parts of them am I moving around?   And which transaction is serialized?
Third, if my transaction has multiple inputs, won't I need multiple signatures?

Wow, this is so terribly confusing.  And I'm relatively fluent in C++, but I'm having a terrible time tracing through the code...

-Eto

P.S. -- BTW, what should the locktime be?  What is the sequence value?   What is your BTC address so I can send you a small donation for answering all these questions? 

[Stefan Thomas]

Which transaction is being copied?

The one you're signing, TxNew.

It is [DerSignature, PublicKey] ... is this SCRIPT?  or PK_SCRIPT?  Or is that only part of one of those scripts?

This is scriptPubKey, that's what you replace the input that is being signed with.

Second, which scripts and which parts of them am I moving around?

See my original post for the hashType == 1 case. It sounds like you're trying to sign transactions you create yourself, so you probably don't have to worry about other hashTypes.

And which transaction is serialized?

You serialize the copy you created in the first step.

Third, if my transaction has multiple inputs, won't I need multiple signatures?

Yes, you repeat the procedure for each input.

Wow, this is so terribly confusing.  And I'm relatively fluent in C++, but I'm having a terrible time tracing through the code...

I recommend again the function SignatureHash(). Read it, sleep on it, read it again, you'll get it.

P.S. -- BTW, what should the locktime be?

Locktime should be 0 unless you want to do some fancy stuff.

What is the sequence value?

Sequence should be the maximum value: 0xffffffff (which is the same as -1)

What is your BTC address so I can send you a small donation for answering all these questions? 

Not necessary. But if you can't restrain yourself: 1DEjwkdqcpteKsxXTxtMfgrpS6LjqW7k4K

[Mike Hearn]

If you can't read C++ you may find the Java version easier:

   http://code.google.com/p/bitcoinj/source/browse/trunk/src/com/google/bitcoin/core/Transaction.java#311

This stuff is documented, on the wiki page for the CHECKSIG  opcode:

https://en.bitcoin.it/wiki/OP_CHECKSIG

[vector76]

The entire transaction (serialized and hashed) is what is signed, minus the scriptSig fields, because it is impossible for a signature to sign itself.

When generating the signature, the scriptSig fields are left blank.  Then after the signatures have been generated, they are filled in.  When verifying the signature, the scriptSig fields are wiped out, and the signature is verified.

Now, what I've written above is almost but not exactly what happens, because in fact all the scriptSig fields are blank except for the one being signed/verified.  For the one being signed/verified, the scriptSig field is populated with the public key and only the signature is absent.

I don't really understand why the public key is inserted rather than the simpler method of leaving them entirely blank, but I am guessing someone smarter than me found an important reason for it.

[etotheipi]

As soon as I think I understand it, I don't understand it anymore!  Step three in the thread above talks about "blanking" the signature field in the subscript.  But this is on the TxOut script, which doesn't have a sig/pubkey... I thought...?

The way I understand it is NewTx contains a TxIn object referencing a TxOut on an OldTx object. 

Execute 1:  NewTx.TxIn.script is only [<signature> <pubkey>]
Execute 2:  OldTx.TxOut.script is  ["OP_DUP OP_HASH160 <recipient addr hash> OP_EQUALVERIFY OP_CHECKSIG"]

So the first script is run first to put the sig and key onto the stack, then the second script is run with the stack from the first script, which will verify the public key matches the addr and verify the signature.  But I thought that the OldTx.TxOut.script doesn't contain a signature/pubkey.  But only TxOut.script contains OP_CHECKSIG which is what would be OP'ing the verification.  So, what am I missing?

-Eto

[casascius]

As soon as I think I understand it, I don't understand it anymore!  Step three in the thread above talks about "blanking" the signature field in the subscript.  But this is on the TxOut script, which doesn't have a sig/pubkey... I thought...?

The way I understand it is NewTx contains a TxIn object referencing a TxOut on an OldTx object.  

Execute 1:  NewTx.TxIn.script is only [<signature> <pubkey>]
Execute 2:  OldTx.TxOut.script is  ["OP_DUP OP_HASH160 <recipient addr hash> OP_EQUALVERIFY OP_CHECKSIG"]

So the first script is run first to put the sig and key onto the stack, then the second script is run with the stack from the first script, which will verify the public key matches the addr and verify the signature.  But I thought that the OldTx.TxOut.script doesn't contain a signature/pubkey.  But only TxOut.script contains OP_CHECKSIG which is what would be OP'ing the verification.  So, what am I missing?

-Eto

The two scripts are combined together to create one script, which is executed.  If the script is executed and leaves TRUE on the stack, the coins are unlocked and can be spent.
Step 1, signature is pushed on to the stack.
Step 2, pubkey is pushed onto the stack.  Stack contains from top: pubkey, signature
Step 3, OP_DUP duplicates the top item.  Stack contains from top: pubkey, pubkey, signature.  (it is duplicated because two copies are needed: one copy will be consumed by OP_HASH160, the other by OP_CHECKSIG)
Step 4, OP_HASH160 converts pubkey into addrhash.  Stack contains from top: addrhash, pubkey, signature.
Step 5, the recipient address hash is pushed to the stack, so (assuming they match) the hash appears twice.  Stack from top: addrhashR, addrhash, pubkey, signature
Step 6, OP_EQUALVERIFY confirms that addrhashR equals addrhash, consuming both.  Transaction fails if they're not equal.  Stack now: pubkey, signature
Step 7, OP_CHECKSIG makes sure that signature is a valid transaction signature with respect to pubkey.  Transaction fails if not valid, leaves behind TRUE if valid.

My guess as to what "blanking" means - the signature isn't known at the time the hash is being created, because the hash is needed for the signature.  So I would guess that blanking means that a placeholder is hashed in place of the signature before its final value is known.  When you are creating a transaction, you are signing that transaction (the new one not the old one).

[etotheipi]

I would've loved this description 12 hours ago before I spent all day studying understanding scripting, and then coded it all up in python.  Of course, the one OP code I'm struggling with is OP_CHECKSIG...

Your first line is what confuses me.  You say they are combined to create one script, but they don't appear to be, in that example on the other thread:

     subscript = tx1.txout[0].script   
     subscript = subscript.replace(chr(len(signature)) + signature, "")

New.TxIn contains the [sig, pubkey], Old.TxOut contains the script to be run afterwards.  But that script does not contain a signature/pubkey, so when I am running that script and told to blank it out... why am I doing it?

I need a really good graphical solution... maybe when I finally understand this, I will make one.

[vector76]

New.TxIn script pushes the pubkey and signature onto the stack, which effectively become inputs to the Old.TxOut script.

Old.TxOut script verifies that the pubkey and signature (provided by New.TxIn) satisfy the requirement:  The pubkey must hash to the specified value, and the pubkey must verify the signature of the transaction.

OldTx.TxOut.script does reference a pubkey, because it contains the hash of the pubkey.  You cannot supply any old pubkey.  And then the private key corresponding to the pubkey is required to claim the funds, because the transaction must be signed by the private key corresponding to the pubkey.  Only then will the signature of the transaction verify against the pubkey and unlock the funds.

When the transaction signature is being generated or verified is the only time when the scripts are temporarily blanked, because the signatures themselves cannot be included in the data being signed.


Suppose you have a hash function
hash = H(data)
And you also have a signature function:
signature = S(privkey, data)
And a corresponding signature verification function
true/false = V(pubkey, signature, data)
And you also have a 'simplification' function which strips out the input scripts and/or signatures of a transaction
T' = Q(T)

The OldTx.TxOut.script effectively says:
To claim the funds in this output, place on the stack a pubkey K and a signature G in a transaction T such that H(K) matches the specified value, and V(K, G, Q(T)) verifies to true.

Only someone with the private key can produce G.  Malicious nodes cannot modify T and pass it along, because doing so would cause the signature verification V(K, G, Q(T)) to fail. 

In case it wasn't already clear, V(K, G, Q(T)) is what OP_CHECKSIG does, using K and G from the stack.  It gets T through other means (not an input from the stack, but an implicit input to OP_CHECKSIG).

[etotheipi]

Gah, I really appreciate your guys' explanation, but you are explaining everything else I have already spent a dozen hours figuring out.  I completely understand scripting, OP codes, script stacks, signing, hashing and cryptography in general (I have programmed EC cryptography modules before).   What I don't get is Q(T) which is step 3 identified in https://en.bitcoin.it/wiki/OP_CHECKSIG.  I didn't understand why step 3 says to blank out the signature in "subscript" when subscript doesn't contain a signature.  I thought maybe I didn't understand, and maybe it does actually contain one...

However, I have been looking at this thread:  http://forum.bitcoin.org/index.php?topic=18051.0 and realized I could actually execute the python code there... if I assume that that code is correct, then my question is further justified.  I printed out the state of "subscript" before and after step 3:

Before:
76 a9 1402bf4b2889c6ada8190c252e70bde1a1909f9617 88 ac 30

After:
76 a9 1402bf4b2889c6ada8190c252e70bde1a1909f9617 88 ac 30

Both are the same:
(OP_DUP) (OP_HASH160)  <AddrHash>  (OP_EQUALVERIFY) (OP_CHECKSIG) \x30


So indeed, there is no sig/key in the txout script, step 3 does nothing. 
So let me ask more directly:  If this script is correct, what is the point of step 3?  Only for non-standard scripts?  If it is not correct, what is wrong with it?

[vector76]

Oh, you're right, that is weird.  I thought it was stripping the signature out of NewTx.TxIn, but it is instead stripping the signature from OldTx.TxOut (which will not normally contain the signature anyway) and it inserts the stripped OldTx.TxOut into the transaction's input script slot before verifying the signature.

I don't see a reason for it in the usual transaction, and I can't see how it would ever be useful.  Someone with a better idea of some of the strange transaction structures will have to describe how it could be useful.

[etotheipi]

FYI, I have created the mother of all illustrative diagrams and posted it in it's own thread.  I think this should finally clear up everything (since it describes exactly what I did to finally get my code working!).

http://forum.bitcoin.org/index.php?topic=29416.msg370321#msg370321

Please let me know if you see any errors in the diagram so I can fix them!

-Eto