If an evm contract has the opcode BLOCKHASH, the relayer should include the necessary block headers. I.e. if evm code includes BLOCKHASH 3, relayer includes block header for block 3 in the transaction.
We're still far from the point where we need this, but I just faced it and wanted to document it for future.