I understand that one can never be certain that an alt Bitcoin client is fully in consensus, but what is it about the consensus rules that makes them so hard to implement in other clients?
Because they're not known.
This may sound surprising, but you have to realize that Bitcoin's consensus rules are defined by what (economically relevant) full nodes actually enforce. We can assume at this point that that is mostly various versions of Bitcoin Core, and derived projects, but that may change over time.
However, they are certainly not defined by some document that people blessed into being the rules. Even if we would somehow create such a document, and everyone would agree to it, what would happen if we realized that there was a bug in actual implementations? In that case, you could call the implementation buggy, but you can't just change it. Any (uncoordinated) change to implementations could result in them ending up in their own fork, resulting in all preexisting coins being spendable twice on each side (the precise thing the blockchain was designed to prevent). Thus, in such a situation there would be no choice but to change the document. Essentially, Bitcoin's consensus rules can be described, but not prescribed.
All of the above is to illustrate that it is not sufficient to replicate any specific intended behaviour; you must mimick the exact behaviour of existing software. You must:
- Accept every valid block, but you also reject every edge case exactly that causes rejection.
- Guarantee that nodes can find each other
- Guarantee that nodes continue to download blocks from each other in various circumstances
- Prevent transitive disconnects/bans (A should not be able to relay a block to B - which possibly runs different software - in such a way that when B relays it to C, C disconnects or bans B).
- Take performance considerations into account. If a block or transaction can be constructed that a significant amount of time to validate, you simplify selfish mining attacks. If validation time can be caused to take close to the block interval time (10 minutes), convergence across the network may fail entirely.
Even worse, all of these properties must be maintained under adversarial circumstances. Blocks may not only contain randomly stumbled-upon edge cases; people may actively try to trigger them.
Mimicking the behaviour of software exactly is a very hard problem. While there is some progress in the field of provably correct software (which includes proving equivalence between two programs), it is nowhere near advanced enough to apply to something like Bitcoin's consensus rules. As a result, the only approach for replication is reimplementing the rules as you believe they are implemented already, without strong methods to guarantee you're right.
In short, in order to replicate the behaviour, you must know the existing behaviour. And history has shown that in many cases, the existing behaviour is not exactly known:
The OP_CHECKMULTISIG redundant stack pop. This one has been known for a long time, but it probably was not known in the first months or even years of Bitcoin's history. The OP_CHECKMULTISIG opcode pops one more element off the stack than needed. People have worked around it by pushing an extra OP_0 when spending a multisig output. BIP 147 has been proposed to require that to be an OP_0 even. In Bitcoin's early days, a reimplementer would likely have incorrectly replicated this.
Compressed and hybrid public keys. According to various specifications, secp256k1 public keys can be encoded in uncompressed, compressed or hybrid formats. Bitcoin initially only used uncompressed keys (comments in the source code indicate that the original author of the software was not aware of compressed keys), but as every node at the time was using OpenSSL for validation, people were able to just start using compressed keys and the network accepted them. In this case, an unknown part of the rules was 'abused' for an improvement.
OP_SIZE does not pop the stack. All opcodes that inspect a stack element also pop that element. There is one exception to this (OP_SIZE), which at least one reimplementation got wrong.
The distinction between signature validation failure and script execution failure. Some reimplementations have initially treated signature failures as script failures (which is a correct assumption for almost all scripts, but not all). Consider a script of the form
<pubkey> OP_CHECKSIG OP_NOT. This is a script that consumes one signature from the stack, and requires it to a signature that is invalid in order to pass.
Serialized size vs. normative size. Various resource limitations exists on the size of blocks, transactions, scripts, ... However, these sizes are defined in terms of the number of bytes that would be produced by serializing the data structure. Sometimes, multiple valid serializations used to exist. At least one reimplementation for period of time used the size of a block - as sent on the wire - to check against the block size limit. However, a 999999 byte block could have been sent using a longer-than-necessary serialization of the number of transactions in it, resulting in perhaps 1000001 bytes. This is a valid block, but the reimplementation would reject it.
OpenSSL's inconsistent DER parser. OpenSSL used to support signatures encoded using various deviations from the DER standard, often with arbitrary restrictions and weird differences (an integer could be encoded as a struct containing an integer), implemented in thousands of lines of hard to read C code. At the time, every reimplementation that did not use OpenSSL could have been trivially forked off by creating a transaction that abused on of those weird deviations. This is a very good example, as it is likely that nobody ever exactly knew what OpenSSL accepted and didn't. This was eventually fixed by BIP66 which made signature parsing much more restrictive, and allowed us to move away from OpenSSL after it became a network rule.
OpenSSL signature parser inconsistency. The OpenSSL signature parsing story goes further: it was discovered that one of its permitted DER deviations was platform dependent. A particular length descriptor was allowed to be up to 4 bytes on 32-bit systems and 64-bit Windows, and up to 8 bytes on others. This resulted in Bitcoin Core instances on different platforms to be inconsistent with each other even, much less be consistent with reimplementations at the time. This discovery was indirectly fixed by BIP66 as well, by requiring that the shortest possible length descriptor had to be used. The full timeline is in this disclosure.
The BDB lock limit. Early versions of Bitcoin Core (before it was called that way), up to version 0.7.x, used a chainstate database implemented in BDB. BDB is a multi-process database environment (something we don't need) that needs a preallocated number of locks to prevent concurrent access to records and deadlock detection. Turns out that the number of locks chosen was mostly enough for processing Bitcoin blocks, until one unfortunate block on March 11th 2013. This was a block with a remarkably large number of inputs (and few outputs), resulting in way more transaction records in the database model of that time being affected. The preconfigured number of locks was exceeded, the database operation failed, and Bitcoin was unable to process that block. As a result, a fork appeared. It was compounded by the fact that many miners had already upgraded to version 0.8.0 (which used LevelDB and no longer had this lock limitation), while many other nodes had not. More information can be found in the post mortem document BIP50.
... Who knows which things we don't know about yet?