Bit-error in Block 108009, Tx 23 ?

[etotheipi]

While testing my blockchain scanning tools I have been able to match up block explorer on every single blockheader hash and tx hash except for a single transaction.  I get the correct answer for 1.5 million transactions, and the wrong answer for exactly 1.  I have spent a lot of time investigating this and I believe I've narrowed it down to a single bit error!?!  How on earth this would happen?  Shouldn't the client choke on this?  Does anyone else have this?

It is in Block 108009, in transaction #23.  In the blk0001.dat file, the tx starts at byte 77,582,676 and is 258 bytes long.  More specifically, the byte in question should be a sequence of four zero-bytes around byte 77,582,930.

Here is the raw transaction as it appears in my blockchain:

Code:

01000000 01a359fe 89ccaf10 07cb285a f28ae745 548fa4e6 b8424eab 70f6bab9 
fae180fa af000000 008b4830 45022058 386a1553 2b610495 db44a8a6 3647d03f 
4ec3ed62 89cfd016 2cb634a5 14514302 2100f7f1 f795dd0e 955aa398 f5e01397 
0ffa7bc4 ef9296b7 c20e6738 525dda2b 3e150141 04dcf7a3 14525ad5 9e749990 
cddd7e7d e0dd4fca 7b77d5f1 7eead167 f0f51856 27a8354b 83a50384 495f37bb 
1463bf6d 11052392 ff6003aa f230035c 4dea8b3e b2ffffff ff02408f e1080000 
00001976 a914c515 97215026 9a7761be ea7a4ecd c750de5f 87d888ac c0ccd208 
01000000 1976a914 e5484641 d51e83d6 7882329f 7cc4c723 69c8db13 88ac0004 0000

The last 4 bytes (8 characters) represent nLockTime.  This transaction appears to have an nLockTime of 0x00040000 (1024)!?!  BlockExplorer says it should be 0 (as expected).  This couldn't be malicious, because nLockTime is disabled and an nLockTime of 1024 in block 108009 is pointless.   This has been driving me crazy, and now I am baffled how my client has let me get away with this.  What is the client supposed to do if it reads a tx from the blk0001.dat that doesn't match the merkle root in the header?

[maaku]

Bit atrophy? A stray cosmic ray?

[etotheipi]

My question is:  what is the client supposed to do when this happens?  It has the correct block headers, but doesn't read the correct tx.  So does he go to the network and request the tx list for that block, again?  If so, then wouldn't the replacement be appended to the end of the file, effectively making blk0001.dat file contain out-of-order block data?

I've never experienced a bit error like this in any application on any computer, ever (or at least never noticed).  It seems like one of those boundary conditions where I bet the client isn't prepared to handle this...

[theymos]

I believe that the error will be detected and fixed if you run Bitcoin with -checkblocks. Bitcoin only checks the last 2500 blocks by default.

[etotheipi]

So if the error occurred in a block with less than 2500 confirmations, the client would find it and correct it in-place?  What if the new block ends up being a different size than the original block on disk? 

Last week, I was trying to decide if I could make the assumption that I will always be able to read the blocks in the file order of blk0001.dat and know that all TxIns read will reference a TxOut that I've seen before.  If the block data is corrected by appending to the end of the file, this assumption fails.  But it also seems like it would be "difficult" to correct the block in place if it's a different size than the original, erroneous block data.

Until spending four hours looking for this bit-flip, I had actually ruled out any possibility of the blocks being out of order.  If I can't make this assumption, tx scanning gets more complicated, since TxIns don't always identify the redeeming address.  You have to look at its TxOut to know for sure.   If the correct TxOut is after the TxIn,  then you have no way to tell if it's yours.  Perhaps requiring two scans of the block chain to find all your transactions...

[maaku]

If you're this thorough about everything in life, I'm surprised you haven't encountered such an error before. Random one-bit errors do happen--I work with big data on consumer hardware and encounter this sort of thing about once a year or so. (That's why ECC memory and RAID exists.) With networks the situation is even worse, because there are some combinations of hardware routers and firmware versions that cause checksum fields to be overwritten rather than verified--and the chances of a transmission error over a network is much larger.

That said, there's no reason for the client to re-verify the transaction until it is actually used. I would hope that it would then discover the error and request the correct version from another node.

[etotheipi]

If you're this thorough about everything in life, I'm surprised you haven't encountered such an error before. Random one-bit errors do happen--I work with big data on consumer hardware and encounter this sort of thing about once a year or so. (That's why ECC memory and RAID exists.) With networks the situation is even worse, because there are some combinations of hardware routers and firmware versions that cause checksum fields to be overwritten rather than verified--and the chances of a transmission error over a network is much larger.

Well, when it comes to Bitcoin, hashing, cryptography, and millions of dollars, I don't have much of a choice but to be extremely thorough.  There is no "partial credit,"   and the cost of mishandling large transactions is not worth the time saved by taking shortcuts.  I want to get this stuff right from the start.

This problem is the kind of thing that happens so rarely, it may not be handled elegantly in the current client.  I'm actually more concerned with the fact that I've made an assumption about blk0001.dat that, if it doesn't hold, will botch my tx scanning code.  If it's an extreme boundary condition, then perhaps I can just work on detecting it and redownload/rescan the chain when it does.  It's annoying, but happens infrequently enough to not cause major problems.

[maaku]

Here's paper on the frequency of random-bit errors:

http://www.cs.toronto.edu/~bianca/papers/sigmetrics09.pdf

If you are doing anything involving transactions of real-world value and you are not using ECC and RAID, you're doing it wrong. If you're handling transactions of extremely high value and you are not using redundant computation (asking multiple machines to generate/process transactions, and comparing results), you're doing it wrong.

The database systems that handle transactions for stock exchanges, air travel, heath devices, etc. have redundant storage, redundant memory, and redundant processing. Google "HP NonStop" for a good commercial example.

[iamzill]

How about running 3 computers, each with their own client and blk0001.dat and a copy of your scanner. When an error occurs take a democratic vote.  If the error rate is X then this system will reduce the error rate down to X*X.

I hope Philip K. Dick's estate doesn't sue me for this post 

[casascius]

I think it is extremely unlikely that this is a hardware-related bit error, compared to the probability that this still-in-beta software actually wrote the file as it is.

Hard drives already use ECC and Reed-Solomon (or similar) encoding internally, even when they're not RAID.  That said, RAID offers no protection against the possibility of a hard drive responding to reads with "success" but the wrong data - something hard drives generally don't do.  RAID only steps in to fill in the gaps when drives report failures and/or an inability to read sectors.

In my view, the odds that the software abused a pointer and overwrote the data in question, or has a bug and isn't behaving like it's supposed to, is about a kazillion times greater than the odds that a stray blip of radiation hit the DRAM in just the right spot and set the bit for the brief interval between receipt of this block and it being flushed to disk.

[maaku]

@casascius: RAID with any kind of redundancy (i.e, not RAID-0 or JBOD) *does* compare reads and notify of an error and/or fill in the gaps if possible.

If this were a software error, you'd see errors a lot more often than 1-in-a-trillion+.

@iamzill: why would Philip K. Dick's estate sue you? that's exactly how high-reliability systems have worked since the invention of the computer.

[casascius]

@casascius: RAID with any kind of redundancy (i.e, not RAID-0 or JBOD) *does* compare reads and notify of an error and/or fill in the gaps if possible.

That is true if a drive is reporting failure, but isn't true if a drive is simply returning wrong data and reporting success (assuming that actually happened), which would be consistent with a "bit failure" scenario that ignores the built-in coding redundancy present in all modern hard drives.

The most the RAID system would see in the event of a "wrong read" is incorrect parity/qvalues(raid5,6) or an inconsistent mirror (raid1).  The most it could do is log the discrepancy advising the operator to do a full-disk verify, start one on its own, and/or recalculate the parity/qvalues(raid5,6) or choose one version of the mirror to overwrite the other, to eliminate the inconsistent-state condition of the volume.

None of the common RAID setups (0,1,5,6,10,50,60) is equipped by design to validate or correct the output of a hard drive that is reporting successful reads but returning incorrect data.  The RAID system relies on the failure reports of non-functioning drives (or the observation that one or more is missing) to know which drive(s) it needs to work around.

If this were a software error, you'd see errors a lot more often than 1-in-a-trillion+.

There are only 15 million transactions per the OP, so it is not clear to me what the 1-in-a-trillion figure is based on.  This transaction could easily be the results of someone experimenting with the network.  If this were a hardware error, even a 1-in-a-trillion one, I would expect his machine to be unstable, locking up constantly, his file system growing errors on its own and constantly needing to be fsck'd/repaired/etc.  Software errors can be responsible of errors that occur with literally any magnitude of frequency, from one in a zillion all the way to constantly.

[theymos]

So if the error occurred in a block with less than 2500 confirmations, the client would find it and correct it in-place?  What if the new block ends up being a different size than the original block on disk? 

Bitcoin will fix it by invalidating the broken block and all later blocks. Then it will redownload them all. I'd guess that a copy of the broken blocks and all later blocks would be appended, though I am not very familiar with Bitcoin's database. Try it and see what happens.

This kind of error is not very important. If corruption causes you to make a wrong network decision, then your client will detect that an invalid chain is longer than your chain and your client will go into safe mode.

[bitrick]

If this were a hardware error, even a 1-in-a-trillion one, I would expect his machine to be unstable, locking up constantly, his file system growing errors on its own and constantly needing to be fsck'd/repaired/etc.  Software errors can be responsible of errors that occur with literally any magnitude of frequency, from one in a zillion all the way to constantly.

I think the experience of myself and maaku differs from yours. I had a similar belief during my first 15 years of working in the computer industry.  I did a lot of things with a lot of data and never encountered an obvious internal bit error.

However, in the last ten years I have worked more closely with hardware and I've seen enough errors to believe that hardware is a perfectly reasonable possible source of error in this case. The recent DEFCON paper on bitsquatting awakened a lot of people to the potential for hardware bit errors. Bandwidth of various transmission types, external and internal, and storage capacity has increased so dramatically, that bit errors are popping up in places that previously were so rare as to be ignorable.

I have personally diagnosed a repeatable bit error which flipped a particular bit of the destination address of a DMA transfer on a PCI bus. It only occurred once every several hours on a heavily loaded network device. It caused one connection to be dropped and there were no other obvious ill effects.

Error correction technology is a slam dunk solution for these types of problems, but it has not yet been applied to all the systems that need it.




 

[casascius]

I've seen enough errors to believe that hardware is a perfectly reasonable possible source of error in this case.

I am fully in agreement that hardware could possibly be the cause.  Perhaps what I'm really trying to say could be summarized like this.

• Because this software is in beta, it too could be the cause, in fact this is very likely for that reason alone.  I have had it crash for no reason at all (usually it complaining about its own database files after an improper shutdown).  This could be happening to everybody and we may just not know it.
• RAID is not a solution to the specific conjecture offered.  If this were a hardware error under identical circumstances, RAID would have given no benefit, just because of what RAID is and isn't.
• Software issues that could contribute to this include the following: misuse of stray pointers, accessing freed memory, threading-related issues, buffer overruns.  Or, it could be hardware.
• A potential tool to help rule out software issues might be to distribute this blockchain verification code and have others run it.  I'd run it.  Who knows.  Maybe my copy of the block chain will have a similar kind of corruption in a different block.  If it did, then there's likely a software gremlin lurking.

EDIT: Here might be a good way for any volunteers to quickly rule out this same thing.

If I do:

Code:

head -c 610000000 blk0001.dat | sha256sum

Then we should all get the same results, right?  (my blk0001.dat is currently 617037299 bytes long)
Mine is 808717dfd1a8af65b60243c4278aff43454fb8df3b3dc597df67265acf851642.

[etotheipi]

If this were a hardware error, even a 1-in-a-trillion one, I would expect his machine to be unstable, locking up constantly, his file system growing errors on its own and constantly needing to be fsck'd/repaired/etc.  Software errors can be responsible of errors that occur with literally any magnitude of frequency, from one in a zillion all the way to constantly.

Error correction technology is a slam dunk solution for these types of problems, but it has not yet been applied to all the systems that need it.

Luckily, in the context of bitcoin, this isn't so critical.  There's redundancy everywhere, since there are hashes for everything, and a million other nodes checking your solution before it's accepted.  The only real risk is getting your client dorked up, submitting what you think is a valid transaction and being confused when it's not accepted by the network.  I don't think millions of dollars will be lost in Bitcoins due to this, but certainly, a client that can't recover from a bit error in the blockchain file could cause all sorts of problems for a high-volume user/company that would lose money from downtime.

I have never appreciated the value of ECC RAM, because I've done computation on computers for 10 years without ever noticing an explicit error.  Although, I can see how certain applications need the guarantees against it.  Regular RAM errors are measured in errors/day, whereas ECC RAM errors are measured in errors/century.  

[theymos]

EDIT: Here might be a good way for any volunteers to quickly rule out this same thing.

If I do:

Code:

head -c 610000000 blk0001.dat | sha256sum

Then we should all get the same results, right?  (my blk0001.dat is currently 617037299 bytes long)
Mine is 808717dfd1a8af65b60243c4278aff43454fb8df3b3dc597df67265acf851642.

This is not reliable because orphan blocks are also stored there. My hash is different.

[etotheipi]

Someone who downloads the blockchain from scratch will get a blk0001.dat file that contains only blocks on the main chain.  However, after the initial download, if you leave your client running, you will invariably pick up the occasional invalid block which will get stored in the blk0001.dat file (because you don't know it's going to be invalid until it's already been added to your file).  This means that your calculated hash will only match between two people if they both just downloaded the blockchain.

[casascius]

Someone who downloads the blockchain from scratch will get a blk0001.dat file that contains only blocks on the main chain.  However, after the initial download, if you leave your client running, you will invariably pick up the occasional invalid block which will get stored in the blk0001.dat file (because you don't know it's going to be invalid until it's already been added to your file).  This means that your calculated hash will only match between two people if they both just downloaded the blockchain.

Given that, maybe this might be of some use, marginal, I suppose... but if you just downloaded a month ago and there's a difference before byte 200,000,000 such as this one at offset 77,000,000 then it might be worth a further look.  Do you know how old is the block chain file you are using?  My blockchain on this particular machine most likely started downloading on 6/24/2011.

Code:

root@ubuntuZK:~/.bitcoin# head -c 100000000 blk0001.dat | sha256sum
75be1a1d816c11466cdf795cdf52d838fdeaa75b5b585fb1b9846d0f840b5322  -
root@ubuntuZK:~/.bitcoin# head -c 200000000 blk0001.dat | sha256sum
e01158d4b962fa0aa99f16565505f9653cfd6662540f4df44c6cbe1e28b87b6b  -
root@ubuntuZK:~/.bitcoin# head -c 300000000 blk0001.dat | sha256sum
9dfa7d83cf98cd25008c67a549e3baf08916c28289e3e702b5a0347f3d71d2a4  -
root@ubuntuZK:~/.bitcoin# head -c 400000000 blk0001.dat | sha256sum
11131852dcd16fe60a7e28b122732f89af923fa39bac41695abe220f7cc61961  -
root@ubuntuZK:~/.bitcoin# head -c 500000000 blk0001.dat | sha256sum
3e335d6e1720236512d7676f53b1d821d1a2f023a3b61b0ddae4d68cb0542ec2  -

[etotheipi]

It would take a little bit longer, but it seems it could be checked very reliably through a simple header+merkle root scan.  The blk0001.dat file has the following form:

Code:

MagicBytes(4) |  NumBytesInBlock(4) | Header (80) | NumTx(var_int) | Tx1 | Tx2 | ... | TxN |
MagicBytes(4) |  NumBytesInBlock(4) | Header (80) | NumTx(var_int) | Tx1 | Tx2 | ... | TxN |
...

If there's a bit error in a header, it won't have the leading zeros.  If there's a bit error in a transaction, the merkle root won't match up.  We know the magic bytes in advance, and if the numBytes or numTx values are off, our parser will crash.  With an efficient algorithm for scanning the blockchain, the entire check could be done in less than a minute.