Ack, nice catch!  I have updated the image in Dropbox.   Maybe I'll keep it in Dropbox for a while, until I get a little more feedback like this...

I had no idea OP_CHECKSIG was so complicated either... until I started trying to figure out what I needed to hash to verify the signature.  That was like 2-3 days ago, and only now did I get it!

-Eto

Base58 is the same concept as Base64, but without the '/', '=', 'I', 'l', '0', and 'O' characters.  This guarantees that the address consists only of alphanumeric characters, and ones that are easily identifiable in any font.

Since python handles arbitrarily large integers, Base58 can be defined the "mathematical" way without having to worry about integer overflows.  The left-most digits are the most significant bits:


Then:

Because:
46736 = index('E') * 58^2 + index('t') * 58 + index('o') = 13*58*58 + 51*58 + 46

Hope that helps!
-Eto

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

That's great.  I just hope my block serialization is identical to the format in the file!   I know my headers are... I guess this will be a good test for whether all my serialization code works.

The one last question I have is:  if blk0001.dat has all the block data, what does blkindex.dat hold?  I would guess it's just headers, but there should only be 12 MB worth of headers.  What I downloaded has 170MB.

-Eto

Alright!  After spending a dozen hours figuring out the OP_CHECKSIG procedure, and working out all the endianness issues and other details in my code, I decided no one else should have to go through this as confused as I was!  So, I hereby present the illustrated guide to OP_CHECKSIG (with SIGHASH_ALL only).   Again, click on it for the full-detail image.



Please let me know if you spot any errors.  I would like to make this diagram as accurate as possible.

Btw, this was a lot of work!  So, if you get some benefit out of this diagram, please consider donating 0.1 BTC to me!  My address is in my signature. (and I would love to show my girlfriend that it's possible to get compensated for all the time I spend on the computer! )

Enjoy!
-Eto

I wanted to be able to read the block-index and blockchain in my client, as well as create a possible "recovery/repair" script for these files.  I know that everything is in these two files, yet I can't find any documentation about how they are stored. 

blkindex.dat:   first 10 kB is mostly zeros with some scattered non-zero bytes.  I stopped checking after that, realizing I have no idea what I'm looking for

blk0001.dat:   first four bytes are the main network magic number, but then after that I don't know what I'm looking at.  Here's the byte breakdown of the first four 32-bit words:


Can anyone offer some guidance on what I'm looking at?  Or more likely, link me to somewhere that actually explains the file format?  I looked through the reference client code, but I couldn't figure out the reading and writing code.  Ugh... I work in C++ for a living, and I can't figure out the reference client code!

-Eto

As part of the effort I invested to really understand the BTC protocol, I made some SVG images to help me piece everything together.  I got most of the difficult details I needed from the BTC forums, so here is me giving back

The first image is a breakdown of an entire transaction.  I could not put the full-size image into this post, because it had to be saved at 800 DPI in order to capture all the small text describing the scripts.  Click on it for the full-sized image.



I have a couple more images coming, showing the process for OP_CHECKSIG, but they need to be cleaned up before I can post them here.  Please let me know if you find any errors so I can fix them.  

Enjoy!
-Eto

P.S. - I would like the full-sized images to be stored somewhere permanently on the forums instead of in my dropbox folder, but I can't put them in a post without flooding your browser screen.  Any recommendations?

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?

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.

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

Update:  After enough hex-diving and specification documents, I figured out how they are encoded.  I'm sure it would be irresponsible to blindly decode a DER chunk without checking byte codes/flags, but I imagine this will never change in Bitcoin, so I am foregoing a proper DER library.

Byte Listing:
--------------
1:  \x30
2:  1-byte length of DER-encoded (r,s) pair (assume 68)

3:  \x02
4:  1-byte length of r-value  (assume 32)
5-36:  integer value of r

37:  \x02
38:  1-byte length of s-value (assume 32)
39-70: integer value of s

71:  \x01
--------------

The values of r and s aren't always 32 bits so you still need to read all the length bytes.  The \x30 and \x02 bytes are bit strings of flags related to DER encoding scheme.

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? 

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

Okay, so the ECDSA library by Lis is fantastic, except I'm missing one critical piece of the puzzle -- I cannot for my life figure out how signatures are encoded.  A signature consists of two integers, (r,s), DER-encoded.  I'm digging through the very-dry DER encoding document, and I can't figure it out.  Most people use an SSL library for DER encoding/decoding, but I am trying not to have such dependencies in my client.

Is anyone familiar enough with the DER encoding to know how to break apart a binary signature into the two integers r and s?

Wow, that is exactly what I was looking for!  Everything you need in a single, dependency-less python file!  I will surely donate to Lis!

P.S. - I did a search for "python ecdsa" in the forum search bar.  I only got 3 hits (probably 4 now, with this post).  I guess I needed to dig a little deeper.

-Eto

As I work on developing my python backend for a BTC client, and finding it difficult to find a decent ECDSA implementation in python that would be sufficient for my purposes.  I have looked at the following:

M2Crypto -- looks like it's the best implementation in general, but I can't get the binary strings of the keys and signatures out of it.  I can only save them to PEM files. 
python-nss -- doesn't look to be cross-platform
pycrypto -- doesn't have ECDSA
python-ecdsa(*) -- temporary winner! -- https://github.com/warner/python-ecdsa

There's a lot of good info on cryptography packages, here:  http://mikeivanov.com/pc/python-crypto.pdf

M2Crypto would be my first choice, but  as far as I can tell, there's no way to get the binary keys directly from the library.  You can generate a key, generate signatures, and save things to PEM files, but no access to the keys themselves.  I am not fond of writing the keys to HDD and then reverse-engineering the PEM file format to get the key out.  Maybe if you could write it to a RAM file... but still seems like a hack.  (maybe someone has experience with this?)

python-ecdsa seems to be the best choice, as it doesn't appear to have any limitations, or any non-standard dependencies beyond it's own files, and should work on any platform.  It looks slow, but I'm not convinced that's a problem unless you're going to verify the entire block-chain.

Anyone know of any other python library, or technique for getting python to do the DSA signing/verification needed for Bitcoin? 

You, sir, deserve 0.7 BTC!  0.5 for the bounty and a tip for providing lots of great reference code.  A request:  please add and commit that to your git repo so that it is easier for others to find in the future.  That will be most helpful! 

By the way, did you just make up that block?  What block has only 3 transactions?  And lastly, when you say "reversed", are you really just talking about switching the byte order to little-endian?  Or is this is a different kind of reversal?

Thanks again!

Sam,

It looks like you're part of the way there.  Is it possible for you to put the data into binary files, exactly as it would appear in a getheaders/getdata reply?  I think someone should be able to download the files into a "UnitTest" directory, and be able to check that their code successfully reads and verifies the hashes and signatures, without having to organize the various CLI commands you listed below.  Any associated text file should simply clarify what data is there, in case the person is having trouble getting things to work.

And thanks for the link to your github project.  It looks like it will be a really useful reference, since I'm developing my own python implementation.  Or maybe I should just use yours as a starting point...?  I started from the pybitcoin code that is a year old, assuming I would get a great lesson in BTC in the process of updating it.  But, it's been a little overwhelming so far...

Thanks,
-Eto

P.S. - you mention in your README that it will work with any crypto library -- you might consider using M2Crypto.  It should have everything anyone would need for bitcoin, combined with hashlib.

I second this request.  As someone working on developing a new client, having an example block would be extraordinarily useful as a verification unit test for all the crypto/hashing code.  The mixed endian-ness and multiple-hashings are extremely confusing and easy mess up.   This kind of thing exists for all crypto algorithms, usually found on their wiki page (look at the SHA-2 wiki page).  BTC client development would be a lot easier with a full example listed somewhere.

Yes, I should be able to use tcpdump or wireshark, but I don't have it or know how to use it.  And even if I did, I'm not confident I pulled the data correctly and what form the bits are in.  How do I know if the nonce is listed in little-endian or big-endian, since it could be either.  

*** BOUNTY 0.5 BTC ***

Since some people do consider this task to be easy, I'm sure someone would be willing to do it for 0.5 BTC.  This is what I want:

(BINARY FILE)  Any block header with resulting hash
(BINARY FILE)  The block data for that header
(TEXT FILE)   ID the header fields, and the human-readable form of those fields (hexdigests/integers/base58 values of hashes/numbers/keys/addresses/etc)
(TEXT FILE)   Explain the block data -- number of transactions, and the human-readable components of the first and second transaction in the block (one coinbase, one regular)

Between these four files, I will get an example of a full public key, private key signature, script bits, base58 address, transaction hash, merkle root, block hashes, and any other common bit representation.  Where multiple representations are possible, it would be nice to see all of them.  Preferably, these four files can be posted to the bitcoin wiki, and the wiki page for bitcoin.  Perhaps OP will offer 0.5 BTC too!

Thanks,
-Eto

I guess my point is, either that block is valid or not.  If it's valid, it has both a static block number and a valid hash.  If it's not, none of it matters.   

The reason it concerns me, is it seems rather inefficient to have to search through hundreds of thousands of block headers just to find the right one.  If that hash is valid, then so it's linear height from the genesis node, and you might as well include both.  The client can check that block 125,329 in his own blockchain has <hash>, and if not, he will do a full search for it. 

Now that I think about it, the block headers are probably stored in a tree-structure indexed by hash, in which case everything I just said is irrelevant... I think I'll go dig into the source code before attacking this thread again.

Thanks,
-Eto