gavinandresen/InvalidBlockProofs.md

## InvalidBlockProofs.md

      
    Raw
  

              InvalidBlockProofs.md
            
          
    For head-first relaying of blocks, I implemented an 'invalidblock' message that, like a 'block' message, broadcasts the full block data when the header of the block was valid but the full block turned out to be invalid.
This should be a very rare occurrence-- miners are incentivized to fix bugs that cause them to produce invalid blocks. So transmitting the full block data once or twice a year shouldn't be an issue... but perhaps it will be an issue if partial validation ever becomes necessary to scale.
First, I assume the 80-byte block header is valid: its hash satisifes proof-of-work.
Proving that the block reward in the coinbase transaction is <= sum(fees)+subsidy requires the full block data (although once segwit is deployed, signatures in the witness data aren't needed).
Proving the block is over size or sigop or sighash limits requires all of the transaction data up to the first transaction that puts the block over the limit (and proof that those transactions are in the block, so a partial merkle tree that includes them).
Then there are all the ways a transaction can be invalid. They all require the transaction data and a merkle path to the merkle root in the block header (to prove the invalid transaction is actually part of the block).
For some invalid transactions, that is all that is required (empty inputs or outputs, over-max-block-size transaction, more-than-21-million-coin output, duplicated inputs, coinbase scriptSig limits, null input for non-coinbase -- the stuff checked by the reference implementation's CheckTransaction).
To prove that a transaction has an invalid signature, you also need:  which txin is bad, transaction data for the output being spent (and if segwit, signature and witness merkle path)
To prove a transaction is spending an output already spent, you also need: other spending transaction and a merkle path to earlier in the block or a previous block.
To prove a transaction is spending an output not in the UTXO set: need all the txids for previous transactions in the block plus proof that they are all in the block (partial merkle tree that contains them).