[COMPLETE] Unit test for blockchain reorganization

[etotheipi]

EDIT:  I added a bounty to this thread, but then did it myself.  See 4 posts down.

I'm working on making sure that my code will properly handle a blockchain reorganization, especially with a tx that is valid on a chain but then invalidated by a reorg that doesn't involve that transaction.  What I really need is some header&block data that represents a blockchain reorg, and create a unit-test out of it.  

I found some invalid blocks in my blk0001.dat file, and started trying to construct a unit test based on that.  The problem is, all the transactions in the invalid block were included in the replacement block, with the exact same Tx hash.  Thus, I have no examples of a real double-spend to know if my code will properly find and handle invalidated transactions.  I am left with either leaving that code untested, or having to construct a fake chain by hand -- I'm hoping someone else constructed something like this, since it seems like a bit of work.

[pc]

I haven't constructed something like that, but it does seem like it'd be very useful. It wouldn't surprise me if nobody had ever tried a double-spend on the main network that actually invalidated a transaction that was already in a block, at least not recently, since it'd be pretty tough to pull off at current difficulties unless you're a good-sized pool operator.

Your best bet for trying to construct one yourself is probably with something like the Testnet in a box, although the way I'm thinking of it you'd need to copy the setup and tweak the ports to get a third Bitcoin instance that you can run at once with the two it gives you. I think the procedure would be:

• Back up the wallet of Wallet 1 (which starts out with the money mined in the Testnet-in-a-box).
• Have Wallet 1 connected to just Wallet 2. Leave the bitcoin instance for Wallet 3 off and disconnected.
• Perform a transaction to move all the funds from Wallet 1 to Wallet 2.
• Perform mining on Wallet 2 until it finds a block. Since it's a difficulty 1 network, it ought to be doable even with just CPU mining.
• Close the bitcoin instance for Wallet 2 so that it's not connected.
• Restore the backed-up wallet on Wallet 1. This should make Wallet 1 forget the transaction so that you can try to double-spend.
• Have Wallet 1 connected to just Wallet 3. Leave the bitcoin instance for Wallet 2 off and disconnected.
• Perform a transaction to move all the funds from Wallet 1 to Wallet 3. (This is the double-spend attempt.)
• Perform mining on Wallet 3 until it finds two blocks. (This should give it a chain longer than the one Wallet 2 has.)
• Turn the bitcoin for Wallet 2 back on and connect it to your network. It should read the longer chain, re-org away the block it originally mined, and the transaction it had of money going to it should now be invalid since Wallet 3 has it instead.

Seems like a lot of work, but unless somebody's done it already I'm not sure you're going to find a better way for what you're looking for.

[etotheipi]

Testnet-in-a-box looks like a great tool.  I'm going to have to play with that.

You proposed an interesting method, but I'm not sure if it will actually work, unless I misunderstood how testnet-in-a-box works.  Won't all of the wallets be using the same blk0001.dat file?  If so, then the moment a wallet is "connected," it will read the blkfile and see the original transaction and reject the attempt to make a new, conflicting transaction.  I probably don't totally understand and/or there's probably a way to hack it... but as you said, it's a lot of work.   I might just try to hand-construct headers and transactions and inject them into a special test blk0001.dat file, since I don't actually need the header hashes to have leading zeros for the test.   Maybe I should just pay someone else to do this...

I'll pay a 5 BTC bounty for a small blk0001.dat file containing this unit test.  It should resemble the regular blk0001.dat file:  contain a sequence of block data with the same format:

Code:

MagicBytes(4B) 
NumBlkBytes(4B)
Header(80B)
numTx(VAR_INT) 
Tx1 
Tx2 
...
TxN

I don't care how the blocks are constructed, and the headers don't have to have leading zeros.  Preferably this blkfile would have 3 regular blocks to start, with a few different addresses and a few regular transactions.   Then the next block will be 4a which will contain two transactions, one to be invalidated.  Next will be block 4b which will have one tx using the same outputs as one of the tx in 4a, but to a different address.   Then block 5 which will extend 4b and force a reorg.   I'm sure I'll break down and do something like this myself, eventually, but I'd rather pay someone to do it for me

[pc]

I guess you'd need to backup the other data files in addition to the wallet file before sending and mining the transaction you're trying to invalidate, and then restore them when rolling it back to attempt the double-spend.

The bounty makes it tempting, but I don't think I'll have time to try it myself this weekend. Perhaps some other time.

[etotheipi]

UPDATE:  I have created an exhaustive reorg unit test with a double-spend.  I used the actual main-network genesis block, and then created 3 new addresses from simple private keys and generated about 10 tx's between these addresses.  I spent a few hours of CPU time to manually find nonce's that give the blockheaders leading zeros for difficulty 1, and used unit-tested ECDSA code to give the tx's actual signatures.  This is a completely valid blockchain, just a very short one.  (NOTE:  actually, it's only valid if you set COINBASE_MATURITY=1).

The blockchain is illustrated below:



The idea is to feed in blocks {0,1,2,3,4} into your code first (blk_0_to_4.dat) as the base blockchain, then feed in {3A, 4A, 5A} one at a time (blk_3A.dat, etc).   Block 5A will force a blockchain reorganization, in which there are two coinbase tx invalidated, and a double-spend by C.   There's also two transactions that appear in both chains, which happens in a real reorg. I used the actual main-network genesis block so that if you have the genesis block hardcoded in your program, it won't choke when it finds something else.  This is also why there are no transactions from Addr A to any other address:  I would have to have Satoshi's private key (I assume the first block was awarded to him).

After loading the initial blockchain (Blocks 0 through 4), you should see the following balances:  {A: 100 | B: 0 | C: 50 | D: 100}
After loading the alternate chain (Blocks 3A, 4A, 5A), you should see the following balances:  {A: 150 | B: 10 | C: 0 | D: 140}

The unit-test files are in the same format as blk0001.dat:
  

Code:

magicNum(4) + totalBlkByts(4) + Header(80) + numTx(var_int) + tx1 + tx2 + ... + txN

http://dl.dropbox.com/u/1139081/reorgtest/blk_0_to_4.dat
http://dl.dropbox.com/u/1139081/reorgtest/blk_3A.dat
http://dl.dropbox.com/u/1139081/reorgtest/blk_4A.dat
http://dl.dropbox.com/u/1139081/reorgtest/blk_5A.dat
http://dl.dropbox.com/u/1139081/reorgtest/reorgtest.hex

Finally, here is the raw hex of all the blocks (also in reorgtest.hex):

Code:

File path: reorgTest/blk_0_to_4.dat
   f9beb4d9
   1d010000

      01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
      00000000 3ba3edfd 7a7b12b2 7ac72c3e 67768f61 7fc81bc3 888a5132 3a9fb8aa 
      4b1e5e4a 29ab5f49 ffff001d 1dac2b7c 
   01

      01000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 
      00000000 00ffffff ff4d04ff ff001d01 04455468 65205469 6d657320 30332f4a 
      616e2f32 30303920 4368616e 63656c6c 6f72206f 6e206272 696e6b20 6f662073 
      65636f6e 64206261 696c6f75 7420666f 72206261 6e6b73ff ffffff01 00f2052a 
      01000000 43410467 8afdb0fe 55482719 67f1a671 30b7105c d6a828e0 3909a679 
      62e0ea1f 61deb649 f6bc3f4c ef38c4f3 5504e51e c112de5c 384df7ba 0b8d578a 
      4c702b6b f11d5fac 00000000 

   f9beb4d9
   d4000000

      01000000 6fe28c0a b6f1b372 c1a6a246 ae63f74f 931e8365 e15a089c 68d61900 
      00000000 aee7e7fc 832d028f 454d4fa1 ca60ba2f 1760d35a 80570cb6 3fe0d6dd 
      4755087a 81ad5f49 ffff001d 3eadf78a 
   01

      01000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 
      00000000 00ffffff ff0404a7 b689ffff ffff0100 f2052a01 00000043 41046868 
      0737c76d abb801cb 2204f57d be4e4579 e4f710cd 67dc1b42 27592c81 e9b5cf02 
      b5ac9e8b 4c9f49be 5251056b 6a6d011e 4c37f6b6 d17ede6b 55faa235 19e2ac00 
      000000 

   f9beb4d9
   95010000

      01000000 1b5514b8 3257d924 be7f10c6 5b95b1f3 c0e50081 e1dfd894 3eece5eb 
      00000000 7bf583e6 b91af0b6 405d2b25 30488edd 37d5f52a a8b2bd02 472b205a 
      9840e789 daaf5f49 ffff001d ac1901ce 
   02

      01000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 
      00000000 00ffffff ff04bcba 7261ffff ffff0100 f2052a01 00000043 41046868 
      0737c76d abb801cb 2204f57d be4e4579 e4f710cd 67dc1b42 27592c81 e9b5cf02 
      b5ac9e8b 4c9f49be 5251056b 6a6d011e 4c37f6b6 d17ede6b 55faa235 19e2ac00 
      000000 

      01000000 01aee7e7 fc832d02 8f454d4f a1ca60ba 2f1760d3 5a80570c b63fe0d6 
      dd475508 7a000000 004a4930 46022100 38fcc428 e8f28ebe a2e8682a 611ac301 
      2aedf528 9535f377 6c3b3acf 5fbcff74 022100c5 1c373fab 30abd0e9 a594be13 
      8bdd99a2 1cdcdb22 58cf9795 c3d569ac 25c3aa01 ffffffff 0200ca9a 3b000000 
      001976a9 14cb2abd e8bccacc 32e893df 3a054b9e f7f227a4 ce88ac00 286bee00 
      00000019 76a914ee 26c56fc1 d942be8d 7a24b2a1 001dd894 69398088 ac000000 
      00 

   f9beb4d9
   96020000

      01000000 979fc396 16bf1dc6 b1f88167 f76383d4 4d65ccd0 fc99b7f9 1bcb2c95 
      00000000 f514b5bb 76a2f0e1 2ab5ece6 b677dbc9 a28df272 f429ced3 101ea2cc 
      0e2723bc 33b25f49 ffff001d e06e1da7 
   03

      01000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 
      00000000 00ffffff ff0432b7 5a74ffff ffff0100 f2052a01 00000043 4104b95c 
      249d84f4 17e3e395 a1274254 28b54067 1cc15881 eb828c17 b722a53f c599e21c 
      a5e56c90 f340988d 3933acc7 6beb832f d64cab07 8ddf3ce7 32923031 d1a8ac00 
      000000 

      01000000 017f47ca aade4bd2 5b1dc863 9411600f d5c279e4 02bd01c0 a0b3c703 
      caf05cc2 29010000 008c4930 46022100 8ae7eadb 9e9c0de8 1b478869 08df8720 
      9bea1cfa d02ba7de 9bb54cf0 6209da6a 0221005b b2e487cb 05464b31 305bd34e 
      742d1dd7 0675cfe5 0c80391f c6b2a578 781c9c01 41046868 0737c76d abb801cb 
      2204f57d be4e4579 e4f710cd 67dc1b42 27592c81 e9b5cf02 b5ac9e8b 4c9f49be 
      5251056b 6a6d011e 4c37f6b6 d17ede6b 55faa235 19e2ffff ffff0100 286bee00 
      00000019 76a914c5 22664fb0 e55cdc5c 0cea73b4 aad97ec8 34323288 ac000000 
      00 

      01000000 017f47ca aade4bd2 5b1dc863 9411600f d5c279e4 02bd01c0 a0b3c703 
      caf05cc2 29000000 008c4930 46022100 5dfc506e 455cd745 20b55f30 e23b7c57 
      4476d82a 0a93ced9 17b2819e 2cf0089c 022100d0 33afc4b1 39bb5493 d6b35055 
      8752692b 04d7f0d2 12ec5cb3 9f9b19c6 a1a29201 4104b95c 249d84f4 17e3e395 
      a1274254 28b54067 1cc15881 eb828c17 b722a53f c599e21c a5e56c90 f340988d 
      3933acc7 6beb832f d64cab07 8ddf3ce7 32923031 d1a8ffff ffff0100 ca9a3b00 
      00000019 76a914c5 22664fb0 e55cdc5c 0cea73b4 aad97ec8 34323288 ac000000 
      00 

   f9beb4d9
   73010000

      01000000 50f8231e 5fd476f4 70e1ba49 37bc97cb 304136c9 6c765339 308935bc 
      00000000 9569f145 11daa8a1 19da79c2 1596a6a4 394f9665 7b15ec3e 2828cadc 
      969b3e18 8bb45f49 ffff001d e3a9e568 
   02

      01000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 
      00000000 00ffffff ff0425a1 4091ffff ffff0100 f2052a01 00000043 4104678a 
      fdb0fe55 48271967 f1a67130 b7105cd6 a828e039 09a67962 e0ea1f61 deb649f6 
      bc3f4cef 38c4f355 04e51ec1 12de5c38 4df7ba0b 8d578a4c 702b6bf1 1d5fac00 
      000000 

      01000000 019b2468 285fc191 b7a033b2 f32b3de8 f0c39d1e ac622f51 32565f1e 
      a8ca74ec 8d000000 004a4930 46022100 7a284fa2 1364d749 389ff623 28e837dd 
      2676cbe4 e202c076 6e3950cb d0a911e4 0221005a c1541e38 1b6d358d f08cce6a 
      2869b76d 5ffe05b6 aaca5c03 ebcba855 9c4ede01 ffffffff 0100f205 2a010000 
      001976a9 14c52266 4fb0e55c dc5c0cea 73b4aad9 7ec83432 3288ac00 000000 

File path: reorgTest/blk_3A.dat

   f9beb4d9
   96020000

      01000000 979fc396 16bf1dc6 b1f88167 f76383d4 4d65ccd0 fc99b7f9 1bcb2c95 
      00000000 2d18a10c 7f32af3c e3b92a12 8380045a 2d44ffba 2fe37317 6bc2f11e 
      dd01aa08 32b25f49 ffff001d f2c86150 
   03

      01000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 
      00000000 00ffffff ff041069 b8e0ffff ffff0100 f2052a01 00000043 4104ed83 
      704c95d8 29046f1a c2780621 1132102c 34e9ac7f fa1b7111 0658e5b9 d1bdedc4 
      16f5cefc 1db0625c d0c75de8 192d2b59 2d7e3b00 bcfb4a0e 860d880f d1fcac00 
      000000 

      01000000 017f47ca aade4bd2 5b1dc863 9411600f d5c279e4 02bd01c0 a0b3c703 
      caf05cc2 29010000 008c4930 46022100 8ae7eadb 9e9c0de8 1b478869 08df8720 
      9bea1cfa d02ba7de 9bb54cf0 6209da6a 0221005b b2e487cb 05464b31 305bd34e 
      742d1dd7 0675cfe5 0c80391f c6b2a578 781c9c01 41046868 0737c76d abb801cb 
      2204f57d be4e4579 e4f710cd 67dc1b42 27592c81 e9b5cf02 b5ac9e8b 4c9f49be 
      5251056b 6a6d011e 4c37f6b6 d17ede6b 55faa235 19e2ffff ffff0100 286bee00 
      00000019 76a914c5 22664fb0 e55cdc5c 0cea73b4 aad97ec8 34323288 ac000000 
      00 

      01000000 017f47ca aade4bd2 5b1dc863 9411600f d5c279e4 02bd01c0 a0b3c703 
      caf05cc2 29000000 008c4930 46022100 c6b68668 5134337a daf4b5a5 e3e654c9 
      12eb3de1 938b9e44 8f3ed6d4 9995f0aa 0221001d 6d972ae1 783ebe81 8f20d038 
      bbc57bee a609950e 59b1235f d8da36dc a6e93f01 4104b95c 249d84f4 17e3e395 
      a1274254 28b54067 1cc15881 eb828c17 b722a53f c599e21c a5e56c90 f340988d 
      3933acc7 6beb832f d64cab07 8ddf3ce7 32923031 d1a8ffff ffff0100 ca9a3b00 
      00000019 76a914ee 26c56fc1 d942be8d 7a24b2a1 001dd894 69398088 ac000000 
      00 

File path: reorgTest/blk_4A.dat

   f9beb4d9
   d4000000

      01000000 dd63f62e f59d5b6a 6da2a364 07f76e4e 28026a3f d3a46700 d2844247 
      00000000 7fa55061 fc4bd2a3 558da5bd 1e2f9492 25ec6a44 a1e52c1b 9a1aed35 
      5dd5d305 8ab45f49 ffff001d f83345c6 
   01

      01000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 
      00000000 00ffffff ff04e81e 7029ffff ffff0100 f2052a01 00000043 4104678a 
      fdb0fe55 48271967 f1a67130 b7105cd6 a828e039 09a67962 e0ea1f61 deb649f6 
      bc3f4cef 38c4f355 04e51ec1 12de5c38 4df7ba0b 8d578a4c 702b6bf1 1d5fac00 
      000000 

File path: reorgTest/blk_5A.dat

   f9beb4d9
   73010000

      01000000 bfa20402 28161021 69b4e1d4 f78cdf77 258048f6 d1428214 4cc01d55 
      00000000 db4a7250 0780d4ad afee03d5 ff2e0c5e a9545eb2 b1e73914 947d3c3d 
      c6c1c3b0 e2b65f49 ffff001d 261f5142 
   02

      01000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 
      00000000 00ffffff ff042e69 6e7affff ffff0100 f2052a01 00000043 4104678a 
      fdb0fe55 48271967 f1a67130 b7105cd6 a828e039 09a67962 e0ea1f61 deb649f6 
      bc3f4cef 38c4f355 04e51ec1 12de5c38 4df7ba0b 8d578a4c 702b6bf1 1d5fac00 
      000000 

      01000000 019b2468 285fc191 b7a033b2 f32b3de8 f0c39d1e ac622f51 32565f1e 
      a8ca74ec 8d000000 004a4930 46022100 7a284fa2 1364d749 389ff623 28e837dd 
      2676cbe4 e202c076 6e3950cb d0a911e4 0221005a c1541e38 1b6d358d f08cce6a 
      2869b76d 5ffe05b6 aaca5c03 ebcba855 9c4ede01 ffffffff 0100f205 2a010000 
      001976a9 14c52266 4fb0e55c dc5c0cea 73b4aad9 7ec83432 3288ac00 000000 


Addr A: 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa (PrivKey: <not available>  (Satoshi))
Addr B: 1NiEGXeURREqqMjCvjCeZn6SwEBZ9AdVet (PrivKey:bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb)
Addr C: 1KXFNhNtrRMfgbdiQeuJqnfD7dR4PhniyJ (PrivKey:cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc)
Addr D: 1JyMKvPHkrCQd8jQrqTR1rBsAd1VpRhTiE (PrivKey:dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd)

I have plugged this data through my own blockchain org/reorg code, and confirmed that everything works as expected.  There was some difficulty at first with mismatches hashes, but it's all been worked out.  Please let me know if you would like this in another form, as it's very easy to use my Python tools to convert the data to another format.

-Eto

[Gavin Andresen]

Nice work!

That's almost exactly the direction I'm heading with the cross-platform testing framework I've been working on, although I was planning on storing blocks in JSON format and was planning on using Python's Twisted/Trial framework to feed the different chains to the implementations to see if they accept or reject them.

I got sidetracked by the 0.5 release and then sidetracked again because I couldn't resist experimenting with the "OP_EVAL" idea and multisignature bitcoin addresses...

[etotheipi]

Nice work!

That's almost exactly the direction I'm heading with the cross-platform testing framework I've been working on, although I was planning on storing blocks in JSON format and was planning on using Python's Twisted/Trial framework to feed the different chains to the implementations to see if they accept or reject them.

I got sidetracked by the 0.5 release and then sidetracked again because I couldn't resist experimenting with the "OP_EVAL" idea and multisignature bitcoin addresses...

I remember seeing a post of yours requesting exactly this, but I couldn't find it to put a link to here.

I still haven't gotten into networking at all, so I'm still digging around at the bit-level and not at all that familiar with JSON.  But the data can easily be converted into any other format.  In the hex file, each "block" of hex corresponds to a single object.  So it should be easy to extract any header or tx in that blockchain.  Or, if you give me some guidance/reference for JSON, I can convert it pretty easily:  I should probably integrate a JSON writer/parser into my codebase, anyway.

[pc]

The only thing that seems strange to me is that in the real network, coin creations can't be spent for 100 blocks, precisely to make it harder for transactions involving them to become invalidated. While you may have a set of "real blocks", I don't think they'd be recognized as valid by a real client, since you're spending money as soon as it's created. It may be good enough for your testing purposes, however.

[Mike Hearn]

You can see how this is done in BitCoinJ here:

  http://code.google.com/p/bitcoinj/source/browse/trunk/tests/com/google/bitcoin/core/ChainSplitTests.java

(this isn't all the block chain related tests obviously).

The general idea is to factor out network parameters and that lets you create a "unit test chain" of difficulty so low that you can solve a block with only a few attempts. You can then quickly generate new blocks and plug them together with whatever contents you like. If your unit tests consist of giant binary structures that are a pain to generate, it's harder for people to really be confident in the codes correctness IMHO.

[Steve]

Nice work!

That's almost exactly the direction I'm heading with the cross-platform testing framework I've been working on, although I was planning on storing blocks in JSON format and was planning on using Python's Twisted/Trial framework to feed the different chains to the implementations to see if they accept or reject them.

I got sidetracked by the 0.5 release and then sidetracked again because I couldn't resist experimenting with the "OP_EVAL" idea and multisignature bitcoin addresses...

Gavin, have you abandoned any effort to utilize Stefan's bitcoinjs/nodejs stuff for this testing framework?

[Gavin Andresen]

Gavin, have you abandoned any effort to utilize Stefan's bitcoinjs/nodejs stuff for this testing framework?

I never started with bitcoinjs/nodejs, because I'm not a JavaScript programmer (and I'm too busy to take the time to learn).

It would be lovely if somebody who is a JavaScript programmer decided to show me how easy it would be and took bitcoinjs/nodejs and created a really nice cross-implementation testing framework with a bunch of test chains.

RE: Mike's point that creating full-difficulty test chains is a pain in the ass:  I think that one-time pain is worthwhile, because I don't think we can count on every bitcoin implementor making it easy to run their implementation in a unit-test mode with super-low difficulty. And creating difficulty-1 blocks with a GPU is actually pretty darn quick...

[Steve]

RE: Mike's point that creating full-difficulty test chains is a pain in the ass:  I think that one-time pain is worthwhile, because I don't think we can count on every bitcoin implementor making it easy to run their implementation in a unit-test mode with super-low difficulty. And creating difficulty-1 blocks with a GPU is actually pretty darn quick...

What if a client made it so that you could change the desired rate of block creation?  Wouldn't that be the only thing you'd need a client to support?  If you set it to 1 second instead of 10 minutes, then the difficulty shouldn't rise above 1 and all other code can work unchanged (thus making the test mode as realistic as possible while making it easy to generate blocks).

[etotheipi]

The only thing that seems strange to me is that in the real network, coin creations can't be spent for 100 blocks, precisely to make it harder for transactions involving them to become invalidated. While you may have a set of "real blocks", I don't think they'd be recognized as valid by a real client, since you're spending money as soon as it's created. It may be good enough for your testing purposes, however.

That's a good point about COINBASE_MATURITY.  I forgot about that when I was making the test, but I don't have a good way around it.  The reason I made this test was so that I, as a human, can examine the exact state of the blockchain in memory at each step, to make sure my code is handling it all correctly.  That gets significantly more complicated if I have to have 100+ blocks.   So you're right, for this test you'd have to change COINBASE_MATURITY to 1.

[etotheipi]

Update:

I still use this data to test the re-org logic in the Armory block utilities when I make changes.  However, I had considered for a while that I could try to add a couple blocks to it to force a re-org back onto the original chain.  That would really be nifty and represent an even-more-stressful situation that the block utilities should be able to handle.

Of course, all this time of procrastinating, I never realized it's already there (it seems kind of obvious in hindsight).  The test was written with the intention of running the blocks through [1, 2, 3, 4, 3A, 4A, 5A] (where blue-underline represents a block that triggers a reorg).   But there's no reason you can't do [1, 2, 3,  3A, 3, 4, 4A, 5A].  Then 3A is actually the "original", block 4 pulls you off of that branch, then 5A pulls you back to the original branch.  It effectively exposes your code to a transaction that is valid, then double-spent, then reverted back to valid when the original chain becomes longest again.

Also, someone just posted a question about reorg testing, so I thought I would bump this thread, since it was written so long ago but still remains useful (at least, for me).

[Mike Hearn]

Cool. Matt did a really great job of making block acceptance and regression tests (which include re-orgs) for bitcoinj. You can see it here:

https://code.google.com/p/bitcoinj/source/browse/core/src/test/java/com/google/bitcoin/core/BitcoindComparisonTool.java

It runs against any bitcoind that is in regtest mode.