As all of you following our blog are aware, we have previously released several bitcoin-related packages (btcwire, btcjson, btcutil, btcdb, btcec, and btcscript) on our way towards the full release of btcd.
We are happy to announce our next package from btcd. The package is named btcchain and it implements the bitcoin block handling and chain selection rules. The code can be reviewed on github here:
https://github.com/conformal/btcchain
Overall Package Design
The bitcoin block handling and chain selection rules are an integral, and quite likely the most important, part of bitcoin. Unfortunately, at the time of this writing, these rules are also largely undocumented and had to be ascertained from the bitcoind source code. At its core, bitcoin is a distributed consensus of which blocks are valid and which ones will comprise the main block chain (public ledger) that ultimately determines accepted transactions, so it is extremely important that fully validating nodes agree on all rules.
At a high level, this package provides support for inserting new blocks into the block chain according to this distributed consensus of rules. It includes functionality such as rejecting duplicate blocks, ensuring blocks and transactions follow all rules, orphan handling, and best chain selection along with reorganization.
Notifications
One of the design goals for the packages used to build btcd has been reusability. To that end, btcchain optionally provides notifications via an asynchronous channel when certain modifications to the block chain take place. For an example of how these notifications are actually used within btcd, when an orphan block is processed, the missing blocks need to be requested from the peer that sent the orphan. Rather than trying to make the chain code understand peers and network requests thus tightly coupling it to other sub-systems, btcd listens for a notification and requests the missing blocks. In this way, btcchain is completely agnostic to the rest of the sub-systems.
Another example of how notifications might be used by a caller is to update wallets with transactions paying coins to the addresses in the wallet. As in the previous example, this means btcchain does not need to know anything about wallets.
Test Coverage
The test coverage for chain is currently only around 60%, but it does include a full blown unit test for chain reorganization using test data provided on the bitcoin talk forums as outlined in this post. Credits for the following diagram go to etotheipi, the author of the linked post and image.
The reorganization test in btcchain uses a slight tweak in the order the blocks are loaded as compared to the order presented in the referenced post in order to ensure orphan handling and a reorganization caused by inserting the parent of an orphaned side chain works correctly as well. In particular, it loads the first 4 blocks from the main chain (1-4 in the diagram), then the second block from the side chain (4A), the third block from the side chain (5A), and finally the first block on the side chain (3A) which completes the side chain and forces it to become the new main chain due to higher difficulty.
We do plan to increase the test coverage further, though testing the error conditions will likely take a while as it will require quite an effort to mine a suite of blocks that are mostly valid except for the specific errors being tested.
What’s next?
This will be the final package released before btcd. That’s right folks, you read it here first. The next release will be btcd!
Does it pass the Bitcoin block tester test suite? How do you only have 60% coverage (I assume thats LOC and not MC/DC?) on validation code with the standard network tests?
Yes the approximate 60% figure is Lines of Code as detailed in the test coverage report here: https://github.com/conformal/btcchain/blob/master/test_coverage.txt
All conditional and error paths (MC/DC) were fully tested during development by intentionally reversing checks and such, but as pointed out in the blog post, there are not yet automated tests to exercise all of those code paths because doing so requires blocks which are valid enough to make it through all of the rules up until the specific error path you are trying to test. We absolutely want and plan to generate a suite of blocks for that purpose, but creating those blocks and building the infrastructure around it will take some time.
As far as your first question, which test suite in particular are you referring to? I ask because we have come across various test suites and everything we’ve tested so far works as expected, but I want to be sure we’re on the same page. We really tried to take great care in matching bitcoind even when there were cases that appear to be bugs. For an example of such a case, see the note in the source code for calculating the median time of previous blocks here https://github.com/conformal/btcchain/blob/355502c97087530b89e737fed3c3d4b5fe8f0764/chain.go#L426-L438
The only test I’m aware of that does a (somewhat) good job at testing block acceptance rules is the bitcoinj “BitcoindComparisonTool”, which gets run on bitcoind and can be found at https://code.google.com/p/bitcoinj/source/browse/core/src/test/java/com/google/bitcoin/core/BitcoindComparisonTool.java . If you have any additional tests that do a good job, please tell me so I can add them to https://github.com/TheBlueMatt/test-scripts which gets run against each new change in bitcoind
Thanks for the response, Matt. The test bits we are/were aware of are the one you linked, the bitcoin protocol test harness by Gavin (https://github.com/gavinandresen/Bitcoin-protocol-test-harness), the reorg test detailed in this blog post, and a few invalid blocks obtained through Google searches. For the invalid blocks, we simply tried to process them to verify we did in fact get the expected error as there was not test harness around them.