Title: [COMPLETE] Unit test for blockchain reorganization Post by: etotheipi on September 30, 2011, 11:54:28 PM EDIT: I added a bounty to this thread, but then did it myself. See 4 posts down (https://bitcointalk.org/index.php?topic=46370.msg577556#msg577556).
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. Title: Re: Unit test for blockchain reorganization Post by: pc on October 01, 2011, 12:42:46 AM 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 (https://bitcointalk.org/?topic=4483.0), 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:
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. Title: Re: Unit test for blockchain reorganization Post by: etotheipi on October 01, 2011, 01:42:09 AM 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) 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 :) Title: Re: Unit test for blockchain reorganization Post by: pc on October 01, 2011, 06:52:47 PM 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. Title: Re: Unit test for blockchain reorganization [BOUNTY] Post by: etotheipi on October 16, 2011, 01:50:42 PM 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: https://dl.dropboxusercontent.com/u/1139081/BitcoinImg/ReorgUnitTest.png 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_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 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 Title: Re: [COMPLETE] Unit test for blockchain reorganization Post by: Gavin Andresen on October 16, 2011, 06:43:06 PM 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... Title: Re: [COMPLETE] Unit test for blockchain reorganization Post by: etotheipi on October 16, 2011, 08:18:30 PM 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. Title: Re: [COMPLETE] Unit test for blockchain reorganization Post by: pc on October 17, 2011, 11:08:46 AM 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.
Title: Re: [COMPLETE] Unit test for blockchain reorganization Post by: Mike Hearn on October 17, 2011, 11:40:36 AM 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. Title: Re: [COMPLETE] Unit test for blockchain reorganization Post by: Steve on October 17, 2011, 01:37:11 PM Nice work! Gavin, have you abandoned any effort to utilize Stefan's bitcoinjs/nodejs stuff for this testing framework?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... Title: Re: [COMPLETE] Unit test for blockchain reorganization Post by: Gavin Andresen on October 17, 2011, 02:24:35 PM 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... Title: Re: [COMPLETE] Unit test for blockchain reorganization Post by: Steve on October 17, 2011, 02:33:39 PM 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).Title: Re: [COMPLETE] Unit test for blockchain reorganization Post by: etotheipi on October 17, 2011, 04:41:50 PM 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. Title: Re: [COMPLETE] Unit test for blockchain reorganization Post by: etotheipi on June 18, 2013, 08:49:34 PM 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). Title: Re: [COMPLETE] Unit test for blockchain reorganization Post by: Mike Hearn on June 19, 2013, 07:30:10 AM 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. |