A bitcoin blockchain parser in a few (thousand) lines of C++

[jratcliff63367]

I just wrote a bitcoin blockchain parser in a tiny code snippet.  This is implemented as just two source files, one header and one CPP, without any external dependencies.  This code snippet does not use any memory allocation, templates, containers, STL, Boost, or anything more complicated than 'fopen, fread, fclose'.

I wrote this mostly as a learning tool so I could understand the blockchain format myself.

While writing it I ran into a couple of minor issues.  One, is that sometimes a blockchain data file will just run out of data, the rest of the file containing zeros.  I don't know if this is normal or expected, but I treat it as an end-of-file condition.  

The other is that some blocks contain less data than is indicated by the block length; meaning that after all of the transactions are read in, the file pointer has not advanced as far as the 'block length' which was indicated.  I am going to assume this is normal and expected?

This code snippet parses my copy of the blockchain (9.2gb) in roughly 95 seconds; which I figured was pretty good; though I don't know what I have to compare to.

At any rate, if anyone finds this code snippet useful or just wants to better understand the data layout of the bitcoin blockchain you can find it here:

http://codesuppository.blogspot.com/2013/07/a-bitcoin-blockchain-parser-as-single.html

Feedback, bugfixes, suggestions, all welcome.

Thanks,

John

[1714948573]

1714948573

[1714948573]

1714948573

[etotheipi]

I just wrote a bitcoin blockchain parser in a tiny code snippet.  This is implemented as just two source files, one header and one CPP, without any external dependencies.  This code snippet does not use any memory allocation, templates, containers, STL, Boost, or anything more complicated than 'fopen, fread, fclose'.

I wrote this mostly as a learning tool so I could understand the blockchain format myself.

While writing it I ran into a couple of minor issues.  One, is that sometimes a blockchain data file will just run out of data, the rest of the file containing zeros.  I don't know if this is normal or expected, but I treat it as an end-of-file condition.  

The other is that some blocks contain less data than is indicated by the block length; meaning that after all of the transactions are read in, the file pointer has not advanced as far as the 'block length' which was indicated.  I am going to assume this is normal and expected?

This code snippet parses my copy of the blockchain (9.2gb) in roughly 95 seconds; which I figured was pretty good; though I don't know what I have to compare to.

At any rate, if anyone finds this code snippet useful or just wants to better understand the data layout of the bitcoin blockchain you can find it here:

http://codesuppository.blogspot.com/2013/07/a-bitcoin-blockchain-parser-as-single.html

Feedback, bugfixes, suggestions, all welcome.

Thanks,

John

Being someone who wrote a blockchain parser from scratch (which is what Armory does on every load/rescan), I can tell you that everything about that is normal (except for the second point below).   And 95 seconds is pretty good.  It depends what else you're doing while you're scanning.  In my case, my code scans in about 150-240 seconds depending on HDD caching, but it's also identifying all the transaction scripts in order to search for coins that are related to my wallet (so I additionally parse and identify individual scripts and then do a lookup in a set<Address160> structure to see if it's relevant).

• The zeros at the end of files are due to pre-allocation.  Since Bitcoin-Qt version 0.8, they now always allocate blk*.dat files in chunks of 16 MB to reduce disk thrashing.  i.e. if you keep appending to a file over and over again, the OS is forced to keep reallocating that space, or fragmenting it.  By preallocating with zero-padding, the number of disk reallocations are cut down dramatically
• I'm not sure what would cause the numBytes field to be incorrect.  How often do you see it?  Do you have an example?

I think doing exactly what you did is one of the best ways to learn the ins and outs of Bitcoin.  If you want to do more, I recommend you pick some addresses and try adding code to watch for that address and accumulate its balance and spendable UTXOs.

[piotr_n]

sorry, what do you mean by "blockchain parser"?
of course it doesn't need any external dependencies, since it doesn't even seem to bother about needing sha256 at any place.
but myself, I cannot imagine a bitcoin blockchain parser that would not need to use sha256

[jratcliff63367]

Thanks for the feedback, I agree this is the best way to learn about the blockchain.

By 'parser' I mean something that can scan every file in the block-chain on disk and return each block in a data structure suitable for further processing.

That is all my code snippet does, nothing more and nothing less.  It's a first starting point anyone would need to do if they wanted to crack the walnut of data inside the block-chain files.

The next step is to actually interpret the data in those blocks and convert them into specific transactions.  That requires actually parsing the input and output scripts.  To do that, I have to implement the script virtual machine.  Now, I could do that by borrowing someone else's source code, or I could just write it for myself as a learning exercise.

My personal goal is to extract all of the transaction data.  I don't want to write a full client, I don't want to submit or even validate transactions.  I suppose the question is can I parse out the transactions without also having to do the full validation?  If I have to, then so be it, if not, that's fine too.

My personal motivation in doing this is that I want a way to track the embedded 'value' in all outstanding bitcoin transactions by comparing the value of the coin in US dollars at the time it was last transferred.  I'm particular interested in large quantities of BTC which haven't moved for years but suddenly 'come to life'.

Perhaps someone has already written such an analysis tool, but I haven't seen one yet. 

At any rate, I'm mostly doing this to satisfy my own personal curiosity and if someone else finds the source code useful and/or educational, that's a bonus.

So, I guess my follow up question is this.  What part of the scripts represent the actual transaction; i.e. 'This amount from this BTC address to this BTC address.' Is that in both the input and output script?  Do I have to run the full cryptography to get that answer, or is that just part of the basic information when you parse the script?

Thanks,

John

[TierNolan]

I suppose the question is can I parse out the transactions without also having to do the full validation?  If I have to, then so be it, if not, that's fine too.

I don't think the reference client actually writes blocks to disk unless they have been validated.

One problem is that all blocks are written to the disk when validated, so you may have some blocks from orphan chains on the disk.  You would need to exclude them from your analysis.

The easiest way would be to just take the longest chain in terms of blocks without worrying about POW.

If you ignore the last 100 blocks in the main chain, then you should get a single clean chain without having to worry about orphans.

[ProfMac]

I also do projects like this to learn.  I figure when someone says I don't understand something, a piece of from scratch working code is a powerful answer.

My next step would be to find the code snippets in the reference client that can do the parsing, and comprehend them with my new found knowledge, then write a utility that uses the reference client code when possible.  I always do that sort of thing, I usually get frustrated mid-way through.

[etotheipi]

Worrying about block validation is a whole new world you don't want to get into.  For now you can simply leverage the fact that if the block is in the blk*.dat files it is valid along with all the transactions in it.   As TierNolan said though, you'll probably have a few orphans in there, so you probably need your scanning code to either compute longest chain (which is a good exercise in itself) or just not assume that 100% of the blocks in those files are in the main chain.

For a first exercise, you don't need a full script evaluation engine.  Just program in enough to recognize common TxOut scripts and ignore the non - std scripts.  Although in terms of computing balances, it's kind of arbitrary... You can store every TxOut in a map<OutPoint, RawTxOut> and remove them as you see TxIns that spend them.  When you're done, you should have a map containing all unspent TxOuts on the network.

Also for your analysis of looking for dormant coins being spent, look up "bitcoin days destroyed"

[bluemeanie1]

I've been doing Block Chain processing as well in Java.

http://i.imagebanana.com/img/g11ev2ol/Selection_018email.png

this diagram shows the famous Hal Finney transaction (block #170), which spends an output from block #9.  This output is later spent in block #181, then #182, and then spent in both #183 and #221.

I'm getting my data from the Bitcoind REST APIs though, it's a bit slower, but once the primary ETL is done then you don't have to worry much about it.

the data set though is far too large for the typical end user of Bitcoin though.


............. another cool one.  looks like a miner collected a bunch of coins into one account and then spent it to another.

http://i.imagebanana.com/img/9e42925q/Selection_019.png

[jratcliff63367]

Does anyone know of a better explanation of how script processing works than I have found online?

Or could someone post an pseudo-code style description here?

My question is this.

There are (n1) input scripts and (n2) output scripts.

Does n1 always equal n2?

Does each input match up with each output?

In other words, in what order are the scripts executed and do they share the same stack?

For example, does input one script push values on the stack which are then popped by output script one?

It's not entirely clear to me must from reading the online documentation the order of execution and how the stack is shared between scripts.

Thanks,

John

[TierNolan]

There are (n1) input scripts and (n2) output scripts.

Right

Does n1 always equal n2?

No

Does each input match up with each output?

This works for certain kinds of multi-sig.  You can say that your signature is conditional on a the matching output being unchanged (but you don't care about any of the other outputs).

In other words, in what order are the scripts executed and do they share the same stack?

They are all independent.  However, some of the hashing steps for signatures blank include/exclude some outputs.

[etotheipi]

The TxIns and TxOuts are independent.  Think of the network as containing a bunch of floating [unspent coins].  Each of those unspent TxOuts is like a bill (like $20 bill).  The TxIn is simply a reference to a particular bill with a signature proving you are authorized to spend it.  If you want to send someone 10 BTC, you need to collect enough bills (say, a 4 BTC bill/TxOut, a 2 BTC bill/TxOut, and a 7 BTC bill/TxOut).  10BTC output, and one output sending the remainder back to yourself (3 BTC).  

You can think of transactions as eating unspent TxOuts, and producing out new TxOuts (and you are authorizing the spending of the old TxOuts by the signatures in the TxIns). A transaction takes TxOuts of some ownership, and converts them into TxOuts of a new ownership.  You can split them or merge them in any quantity, as long as you have at least one TxIn (corresponding to a previous TxOut being eaten) and one new TxOut.

Here's a random picture I made a long time ago that attempts to illustrate it.  



The dotted lines for the TxIns illustrates that they are really kind of "transient" data.  They're simply for the network to see that you were authorized to move those coins, but in the far future, the old spent TxOuts, and the TxIns that moved them can all be pruned off.

[jratcliff63367]

Ok, I think I'm making progress understanding this; a bit.

I now understand that each block as a certain number of transactions and each transaction has a certain number of inputs and outputs (potentially representing where btc is coming from and where it is going to).

Could you guys help clarify some things in regards to simply parsing the raw blockchain data to get a meaningful transaction history out?

(1) Can you confirm that it is true that a program which only wants to navigate the transaction history of the blockchain does not actually have to parse either the input or the output scripts?  This is true, correct?  Those scripts are only used for validating transactions but since I'm reading the blockchain off of my hard drive, they represent all properly validated transactions. Correct?

(2) All of the information needed to understand the blockchain (i.e. see the same kind of information shown on blockchain.info) can be found simply by parsing the blockchain data files (blkNNNNN.dat) files?

(3) When looking at the block data; there is a timestamp for the block; but I don't see a timestamp for individual transactions.  Is this correct?

(4) When processing an input it specifies an input transaction hash and a transaction index number; how does one go from that hash/index and figure out a specific output transaction in a previous block?

(5) On BlockChain info, if you just look at Block #1 https://blockchain.info/block/00000000839a8e6886ab5951d76f411475428afc90947ee320161bbf18eb6048  It specifies both a hash and a previous block hash.  I'm a little confused on that point; there is no 'previous' block to block #1.  Also, there is no 'hash' field on block-chain data structure; only a previous hash field.

(6) On the same block #1 page, it shows an output address '12c6DSiU4Rq3P4ZxziKxzrL5LmMBrzjrJX'.  Where does that value come from?  Was it in the script?  I don't see it anywhere in the data structures?  Also, this address isn't a hex value; is there some published algorithm that converts a binary hash into this ASCII string format?

Thanks,

John

[TierNolan]

(1) Can you confirm that it is true that a program which only wants to navigate the transaction history of the blockchain does not actually have to parse either the input or the output scripts?  This is true, correct?  Those scripts are only used for validating transactions but since I'm reading the blockchain off of my hard drive, they represent all properly validated transactions. Correct?

(2) All of the information needed to understand the blockchain (i.e. see the same kind of information shown on blockchain.info) can be found simply by parsing the blockchain data files (blkNNNNN.dat) files?

Right

(3) When looking at the block data; there is a timestamp for the block; but I don't see a timestamp for individual transactions.  Is this correct?

Transactions don't have timestamps.  They are "locked" to a time when they are included in a block.  If they had a timestamp, then they would only work for a particular block, but miners decide which blocks to place transactions into. 

They do have a "locktime".  Transactions cannot be added into a block until that time has arrived (or that block number if < 50000000 or so).

(4) When processing an input it specifies an input transaction hash and a transaction index number; how does one go from that hash/index and figure out a specific output transaction in a previous block?

You need to create a map of hash(transaction) -> transaction (possibly file pointer).

You have to hash the entire transaction as it appears in the file.  That is sha256(sha256(transaction)).  Sometimes people get the big-endian/little-endian the wrong way around.

(5) On BlockChain info, if you just look at Block #1 https://blockchain.info/block/00000000839a8e6886ab5951d76f411475428afc90947ee320161bbf18eb6048  It specifies both a hash and a previous block hash.  I'm a little confused on that point; there is no 'previous' block to block #1.  Also, there is no 'hash' field on block-chain data structure; only a previous hash field.

Yes there is, blocks start from block 0, there is no previous to block zero though. 

However, the genesis block is presumably not in the file, since it is hard-coded.

(6) On the same block #1 page, it shows an output address '12c6DSiU4Rq3P4ZxziKxzrL5LmMBrzjrJX'.  Where does that value come from?  Was it in the script?  I don't see it anywhere in the data structures?  Also, this address isn't a hex value; is there some published algorithm that converts a binary hash into this ASCII string format?

They calculate that from the script.  There are a few standard transactions.

[ProfMac]

Ok, I think I'm making progress understanding this; a bit.

(5) On BlockChain info, if you just look at Block #1 https://blockchain.info/block/00000000839a8e6886ab5951d76f411475428afc90947ee320161bbf18eb6048  It specifies both a hash and a previous block hash.  I'm a little confused on that point; there is no 'previous' block to block #1.  Also, there is no 'hash' field on block-chain data structure; only a previous hash field.

Block #0 exists.  Your link has a field for "Previous Block" on the right hand side.

[xavier]

This is pretty cool! Thanks for doing this. I'll check it out over the weekend.

[jratcliff63367]

Ok, thanks, that helps quite a bit.

I'm really surprised that transactions don't have a time stamp.  You mean there is no way to know 'when' a transaction occurred?

So, it sounds like I don't need to parse the scripts to know the transactions but if I want to know the source/destination addresses of the public keys I *do* have to parse the scripts?

I guess I'm still a little confused on that point.  I started writing a script parser, but the scripts I try to run against it are all kind of incomplete.  The input scripts generally just push data on the stack but have no actual instructions to 'do' anything.

The output scripts tend to execute an instruction such as 'OP_CHECKSIG' which requires that two items are on the stack, but when I get here there is usually only one item on the stack; and I'm on clear on what was supposed to have been executed prior to it.

I'm not really understanding I guess how the input scripts match up to the output scripts and how current state of the stack is retained; I mean do you like run an input script; which pushes some stuff on the stack for the output script, or vice versa?  And, if so, how do you know which input scripts match which output scripts?

For example, the block #1 output script pushes 65 bytes of data on the stack and then tries to execute OP_CHECKSIG which immediately fails in my VM and the reference code for bitcoin-qt because it requires there be at least two arguments on the stack.  

Regarding my other question about the 'public-key' part of bitcoin addresses, I found that it's using this 'Elliptic Curve Digital Signature Algorithm' thing.  What I can't find is a reference to how one converts the binary data for the key into the ASCII representation; this would be useful for debugging.

Sorry for the annoying questions but I will try to make up for it by posting some articles and open-source code snippets if I ever get this transaction analysis tool working.

Does anyone know of a C/C++ program someone else has already written that does what I'm trying to do here; just walk the block-chain and track transactions?  All of these code bases have sooo...many dependencies that you dive into crytographic hell trying to decipher them.

Thanks,

John

[etotheipi]

You shouldn't be surprised there's no timestamps on transactions - that's the whole point of Bitcoin which is for a whole network of thousands of independent nodes to all agree on the ordering of transactions.   In essence, a transaction doesn't even really exist until it is included in a block.  Therefore, the block timestamp is when the TX became "real".  Everyone has different clocks and receives the tx in different orders and times.  The point of Bitcoin is for this network with no central authority to agree on which ones actually happened.

As for C++ code, go look at the Armory code base which had code that does exactly what you're looking for in the  cppForSWIG directory.  BlockUtils cppForSWIG.   Should be a function called parseEntireBlockchain of something like that.

[piotr_n]

I guess I'm still a little confused on that point.  I started writing a script parser, but the scripts I try to run against it are all kind of incomplete.  The input scripts generally just push data on the stack but have no actual instructions to 'do' anything.

That's what the output scripts are.
The spending scripts pull this data from the stack and verify against signatures.

What is put on the stack is the public key that you need to convert into 25 bytes of a "version+hash+chksum" - then you base58 encode it and that is the address.

[TierNolan]

I guess I'm still a little confused on that point.  I started writing a script parser, but the scripts I try to run against it are all kind of incomplete.  The input scripts generally just push data on the stack but have no actual instructions to 'do' anything.

The output scripts tend to execute an instruction such as 'OP_CHECKSIG' which requires that two items are on the stack, but when I get here there is usually only one item on the stack; and I'm on clear on what was supposed to have been executed prior to it.

That is intentional.

Each transaction has half of the script.

You run the script for the input and then run the script for the output.

The standard address scripts are:

Output: OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG
Input: scriptSig: <sig> <pubKey>

The input is run and then the output.

So, the output says "Anyone who can setup the stack so that this script verifies can spend this coin".

The full instuctions are

OP_DUP: Copy the top of the stack
OP_HASH160: Apply RIPE-160 to the top of the stack
<pub-key-hash>: Push that value onto the stack
OP_EQUALVERIFY: Make sure the top 2 values on the stack are the same (and pop both)
OP_CHECKSIG: Check the signature

If you run the input, it pushes 2 values onto the stack

<sig> <public key>

This sets up a successful run for the output

OP_DUP: <sig> <public key> <public key>
OP_HASH160: <sig> <public key> RIPE-160(<public key>)
<pub-key-hash>: <sig> <public key> RIPE-160(<public key>) <pub-key-hash>
OP_EQUAL_VERIFY: <sig> <public key>   (Also checked RIPE-160(<public key>) was equal to <pub-key-hash>)
OP_CHECKSIG: checks that sig is a valid signature using the public key

I'm not really understanding I guess how the input scripts match up to the output scripts and how current state of the stack is retained; I mean do you like run an input script; which pushes some stuff on the stack for the output script, or vice versa?  And, if so, how do you know which input scripts match which output scripts?

Right, each is half.

Regarding my other question about the 'public-key' part of bitcoin addresses, I found that it's using this 'Elliptic Curve Digital Signature Algorithm' thing.  What I can't find is a reference to how one converts the binary data for the key into the ASCII representation; this would be useful for debugging.

Addresses are encoded using Base 58 encoding.  Normal keys etc are normally shown using hex encoding.

[jratcliff63367]

>>You run the script for the input and then run the script for the output.

Ok, I had previously asked in this thread how the input and output scripts related to each other and I did not get a clear answer.


In the transaction header there are (n1) input scripts and (n2) output scripts; how do I know which input script to run on the virtual-machine prior to running a particular output script?

Thanks,

John